14 ms·
Implement mechanism to wait on any of several futexes
- jdsully 7y agoI like how they won’t say the windows API’s name. WaitForMultipleObjects is quite nice - an epoll that works with all sorts of things not just fds. This is kind of a half assed implementation - sometimes I wish Linux would admit Windows has a good idea once in a while.
- monocasa 7y agoThis isn't really like WaitForMultipleObjects; WFMO is more like epoll with a whole lot more restrictions. This legit isnt really like anything in Windows, the closest thing I can think of is you'd be able to do something like this with XOK wake predicates.
- jdsully 7y agoThats my point. They should just bite the bullet and implement WaitForMultipleObjects instead of having all these disjoint APIs. Plus sometimes you want to wait for both and this is very difficult with Linux. Its also telling Linux has gone through the whole select/poll/epoll madness while WaitForMultipleObjects has worked well in windows NT since the 90s. Its a proven design.
- monocasa 7y agoI mean.. epoll is already better than WFMO. It doesn't have that silly 64 item cap, or O(N) entry and exit on the wait like it's 1995 all over again. (And that's not to say that epoll is the pinnacle of design, just that WFMO is worse. We can do better than both) And this better too, you don't need to register futexes with the kernel, the futex wait call is just "I want to sleep until the data at this memory address changes", and now you can say "I want to sleep until _these addresses_ change". NT doesn't give you any equivalent, you need to build in kernel objects to do the same thing. And if you want to wait for both, you just wrap it into an eventfd and epoll on that.
- mehrdadn 7y agoThe thing is, on Windows, you're not supposed to wait on a thousand handles at once. You're supposed to use overlapped I/O, completion ports, etc. which work quite well.
- monocasa 7y agoThis use case in the article isn't about I/O at all though. Futexes are user space mutexes. Overlapped I/O and completion ports don't help you in that case.
- mehrdadn 7y agoRight, but when do you need to simultaneously wait on more than 64 things other than for I/O? I've never had to wait on that many mutexes... (P.S. there is a really ugly way to get around this on Windows if for some bizarre reason you really need to, which is to have 1 thread per 64 handles, then wait on the thread handle instead. I've never found a need do even get close to doing such a thing though.)
- monocasa 7y agoOff the top of my head, timers?
- mehrdadn 7y agoDoesn't Windows have timers that actually notify you via window messages or callbacks (like SetTimer())?
- monocasa 7y agoWindows has a ton of subsystem specific hacks each with their own drawbacks. Which brings me back to my main point against the GPs > They should just bite the bullet and implement WaitForMultipleObjects instead of having all these disjoint APIs
- wbl 7y agoPoll and select predate linux. The issues with epoll were in the 2000's and kqueue has been very stable by comparison.
- jdsully 7y agoKqueue is quite nice. BSD is much better designed and I enjoy working with it more. Linux suffers from people doing just enough to solve their specific problem and then no more. The result is APIs are not orthogonal and follow differing styles. Sometimes they don’t even work at all (e.g. futex fds) I admire what Linux accomplishes functionally. But it is just as ugly as win32 in my opinion. The two are really more alike in their pragmatism than they would care to admit - but mutual hatred prevents learning from each others mistakes.
- wbl 7y agoI've never worked with Win32, just read about the more core bits of NT, and those seem quite nice although perhaps overgeneral. But I've always had a soft spot for oddball systems.
- dingu 7y agoepoll was a problem child API on linux, with a number of missteps early on. It's much better now. It does everything WFMO does and more. What disjoint APIs are you talking about? You can just use epoll and be done with it? What are you talking about by "wait for both"? But jesus, the windows API in this area is hot garbage. A hard 64 limit and O(N)? It's a terrible design.
- jlokier 7y agoLinux has WaitForMultipleObjects already: fds are equivalent to Windows HANDLEs, and WaitForMultipleObjects() is equivalent to poll(). But, Linux also has epoll() which scales better for non-trivial numbers of things, and Windows has IOCP. So WaitForMultipleObjects isn't particularly special. Both Windows and Linux have things that don't work with these interfaces. Nonetheless, Linux has been trending towards "waiting on all sorts of things" by makng more and more things into fds that can be waited on with pol;/epoll. Examples: timerfd, signalfd, eventfd. It's quite a unixy approach. In fact, Wine already uses eventfd to implement WaitForMultipleObjects. This kernel change is just an optimisation, to speed up Wine, and a workaround for some distros setting Wine's max fd limit too low for Windows apps. Futexes used to support waiting on multiple futexes, using FUTEX_FD. That was arguably better than the new patch FUTEX_WAIT_MULTIPLE, because in old Linux you could wait for futexes and other fds at the same time - it did work with "all sorts of things". But FUTEX_FD was removed after searches online found no code using it, and kernel devs didn't like keeping it. (To my mind, this was a suprising, unusual breakage of system call binary compatibility) The new FUTEX_WAIT_MULTIPLE allows programs like Wine to wait for multiple futexes faster than before, but it's more limited than the old FUTEX_FD because you can't mix them with other things.
- jdsully 7y agoepoll only works with file descriptors and is therefore not equivalent. The whole point is WaitForMultipleObjects works with many different types.
- dingu 7y agoYou are confused. File descriptors on linux represent "many different types." They are not just for "disk files". Please see signalfd, timerfd, eventfd, inotify, let alone sockets (which themselves represent things other than IP sockets). FD is essentially like handle. epoll therefore works with many different types.
- jdsully 7y agoWhile the Unix philosophy is that everything is a file - that is not the case with Linux. Futexs being a good example. There was an attempt to integrate them but it was done incorrectly with inherent race conditions and abandoned. The VMS and NT philosophies of everything being an object are a bit more general and easier to follow in practice.
- asveikau 7y agoWaitForMultipleObjects is problematic for a few reasons: * limited to 64 handles. * passes the entire handle buffer to the kernel on every call. That is also a key reason poll is worse than epoll/kqueue. A better way is to let the kernel retain the list of handles across calls. * when two handles are signalled, the one earlier in the array is always the one returned. So handle with a lower array index being frequently signalled can starve out your opportunity to process the later ones. * since everything happens by returning an index, when multiple handles are signalled, you can only process one at a time, needing a new syscall for each.
- wahern 7y agoThe `abs_time` argument to both the futex_wait and new futex_wait_multiple is a pointer, but nowhere is the address checked for validity. (Tracing the syscall path, it seems to be dereferenced in futex_setup_timer without any validity check beforehand.) It's never written to AFAICT, only loaded, but it still seems like leaving around a loaded gun. More importantly, couldn't this unchecked address be used to probe kernel memory to test for values like NULL, or possibly any value with enough sampling? Note that the futex address itself is also a pointer, but it's validated with access_ok in get_futex_key.
- monocasa 7y agoIt's not a user pointer, it's a pointer to the kernel stack that's constructed here: https://elixir.bootlin.com/linux/latest/source/kernel/futex.c#L3675 https://elixir.bootlin.com/linux/latest/source/kernel/futex....
- shmerl 7y agoNice to see Valve pushing Linux gaming advancements like that!
- cryptonector 7y agoI'd like a way to wait on multiple condition variables. Windows has this... Or to treat condition variables as file descriptors so that select/poll/epoll can be used to wait on them (you'd get a notification of a signal, though it might be spurious, so you still have to take the lock and check the condition before you consider the CV signaled).
- ot 7y agoI wonder if they have considered implementing futexes in userland so they don't have to wait for the kernel implementing this. WebKit has its own implementation (see the ParkingLot in https://webkit.org/blog/6161/locking-in-webkit/ https://webkit.org/blog/6161/locking-in-webkit/) which inspired an implementation in folly (https://github.com/facebook/folly/blob/master/folly/synchronization/ParkingLot.h https://github.com/facebook/folly/blob/master/folly/synchron...). Surprisingly, implementing futexes in userland can have performance benefits wrt kernel futexes (because of better control over the fast path, possibly avoiding syscalls) and a richer interface (for example the value doesn't need to be 32 bit, just any atomic).
- Kuraj 7y agoThe scale goes from 0 to 80. It's not horribly misleading, but just saying
- aardvarklegend 7y agoI believe that’s because it’s frames per second, not an abstract percentile.
- Kuraj 7y agoOh, wow. I'm an idiot
- donaltroddyn 7y agoNot at all - it's a poor graph with an unlabelled axis.
- dhritzkiv 7y agoWhile I was able to intuit the the Y axis was FPS, it's not wholly obvious. Labeling the graph (or at the very least, just that axis) would help.
- sedatk 7y agoThis is apparently for improving the performance of Wine emulator on Linux mainly, not native Linux games like the headline suggests.
- rbanffy 7y agoWould it be useful to native programs?
- Someone1234 7y agoWine is a native program, so yes. But it is a niche facility that Wine benefits from, and other programs that handle a lot of locks/queues also do, but may not directly benefit Linux native game performance.
- ufo 7y agoValve's post suggests that they believe this to be the case, although they didn't explain the specific details. > We think that if this feature (or an equivalent) was adopted upstream, we would achieve efficiency gains by adopting it in native massively-threaded applications such as Steam and the Source 2 engine.
- rbanffy 7y agoI got that. I intended to go for "actually useful".
- kbenson 7y agoSource 2 has a linux port I believe, and it's an engine that other games could (do?) use to get easy linux support for a lot of their codebase. I think that counts for actually useful. Depending on what they mean by "massively-threaded", that might cover some other popular network applications that thread to handle requests, but I'm not sure how much work they would put into a linux specific solution if it complicated their codebase.
- 7y ago
- robin_reala 7y agoThe specific proposal (linked to from the article) is https://lkml.org/lkml/2019/7/30/1399 https://lkml.org/lkml/2019/7/30/1399
- Sahhaese 7y agoDepressing to see reviewers waste review bandwidth bringing up issues such as "wasted newline" and "incorrect comment format". Do kernel developers not use auto-formatters?
- megous 7y agoPatch submitter should use checkpatch, which will warn about many of these issues.
- cbsks 7y agocheckpatch isn't as thorough as you might expect. I ran it on the submitted patch and it didn't catch any of the code style mistakes.
- nixgeek 7y agoOn the contrary, I think the feedback provided was excellent and far better than just saying “Doesn’t conform to our style guidelines, please try again”. Bravo Peter. This may be someone’s first submission and they may consequently not be aware of style guides, tools which can help lint, etc?
- db48x 7y agoAgreed. Also "missing {}" is a super important "style" comment.
- peterzz 7y agoBecause bugs due to missing {} happen, and are a royal pain, the rule is that any nontrivial statement; especially any multi-line; must have braces. Also, given the amount of patches I have to read, uniform style really does matter. Unconventional style breaks the flow and detracts from the important bits. Also, I'm not aware of a lint like tool that works on diffs. Many of the patches never get further than my MUA.
- scohesc 7y agoAm I interpreting the graph on their page all wrong? It looks like the older version of Proton provides better performance? Unless they're graphing function call return time? The graph and the text around it doesn't do a good job of explaining that.
- GranPC 7y ago4.11 is newer than 4.2
- geddy 7y agoI have no idea why this took me so long to realize. Must be the versions I'm used to seeing but my brain parsed `4.11` as `4.1.1`. Weird. Thanks for pointing out the obvious for those of us who missed it!
- falcrist 7y agoYou parse it the same way I usually do. As a decimal fraction, 4.2 > 4.11... however, version numbers aren't decimal fractions. In any case, you're not alone.
- belltaco 7y ago4.11 is 9 versions newer than 4.2
- sjwright 7y agoThe thing to remember is that version numbers aren’t decimals. They’re two or three integers separated by periods. 11 is higher than 2.
- kleer001 7y agoHarumph. Then it should be padded with zeros. So, 4.002 and 4.011 /grumpy edit: nope, it's fine as is. my experience in frame numbers, dates, and so forth do not scale to releases
- swiley 7y agoThis looks to me like the main change is to make it easier to create mutexes with timeouts. Isn’t a mutex timing out an indication that: a) a lock wasn’t needed in the first place or b) the program is incorrect? It feels more like they just want the api to match win32 better but most of the multithreaded programming I’ve done lately has just used go’s channels so I totally could be missing something.
- pizlonator 7y agoIts much more than timeouts. Here’s the killer use case outside wine: - program with fine grained locks - you have an algorithm that needs to acquire N of those locks, one at a time, and can do it in any order In that case, you really want to: - first attempt fast path locking on all of them in any order - if that fails tell the kernel about all of the locks you are waiting on at once. This means that you will become unblocked as soon as any lock becomes available. That will make your program run faster. Therefore, it’s a good improvement for futexes in my opinion.
- pjc50 7y agoYou can't acquire locks in any order, that's a recipe for deadlock when one process has acquired half the locks and another has the different half, resulting in them waiting on each other. Use of WaitForMultipleObjects is more usually for completion of tasks, in the way that win32 "overlapped" works.
- pizlonator 7y agoYou absolutely can try to acquire locks in any order if you are just trying to find the first one that is available. Remember, the algorithm in my example is one where you hold locks one at a time. You can acquire locks in any order if you hold them one at a time. Also my example is intentionally not about wine or win32. I’m articulating why this interface is independently valuable.
- deleted 7y ago[deleted]
- mabbo 7y agoLinux Gaming with Steam is actually quite nice these days. I spent about 3 years using an Ubuntu desktop for all my gaming at home. Most of the games I played installed via steam and worked great on Linux. The only reason I switched back to a Windows Desktop was that there were just one or two games I specifically wanted to try, but couldn't install to Linux. And once I had switched back (and paid the price for Windows) there were no games that needed Linux, so no motivation to go back.
- Scaevolus 7y agoThe article is discussing optimizing Proton, a version of Wine embedded in Steam, meaning you can (try to) play Windows-only games on Linux with minimal effort. It works quite well, though graphically intensive games are more likely to experience glitches or slowdown from the translation.
- washadjeffmad 7y agoI don't have the nerves to bear a native Windows install in my environment, so I turned their LTSC into a "Windows Gaming Container" with VFIO. Alright, it's a headless VM, but it's pared down with 'unfuck' and other telemetry- and uselessness- neutering projects into something safer. Lookingglass peers into one of my GPU's framebuffers, so it lives inside a window on my Linux host. It's also been at least a year since I've needed it, though, since Steam and wine cover everything else I'd want to play or run, so it might be time to cut it loose for good.
- Shorel 7y ago> there were no games that needed Linux That will never happen. You game in Linux because you need Linux first and games second.
- nibblerbro 7y agoLmaoooooooo @ gayming on loomix
- gnufied 7y agoPersonally for me - the problematic part of gaming on Linux has been input(i.e mouse) latency and acceleration profile. I am not sure if this is just my experience but when using libinput on Fedora for example - the cursor movement is not exactly precise. This is not obvious when working but while gaming this is a deal breaker.
- ilikehurdles 7y agoThere is a "flat" profile that can be toggled in the Gnome Tweak Tool, assuming you're using Gnome in Fedora.
- sandov 7y agoLast time I tried it, flat didn't work correctly when using a touchpad, only when using a mouse. Touchpad flat profile was flat up to a certain velocity, but when you exceeded that it accelerated a lot. Flat profile on a physical mouse worked correctly. Even if I yanked the device, it wouldn't accelerate. This is one of the reasons why I'm sticking to Ubuntu 16.04: "xset m 1 0" disables all acceleration on xinput.
- Barrin92 7y agowow thank you for this comment, for months i've struggled with the annoying acceleration.
- adrianmonk 7y agoSeems like in an ideal world, games would select that profile programmatically. Assuming, of course, that there's no reason to prefer mouse acceleration and that we're talking about using the mouse as a linear controller for stuff like aiming or moving.
- TrueDuality 7y agoIdeally yes, but remember that a lot of these games aren't designed for Linux but are effectively running in a compatibility layer for Windows. There is no way for the programmers to know that they need to be interacting with a Linux window manager's behavior.
- Asooka 7y agoI know the patch mentions interactive multimedia applications (games) in particular, but an actual mechanism to implement WaitForMultipleObjects on Linux would be very welcome for many high-performance multi-threaded applications. Say you have one worker thread per CPU core. On Windows, each thread would get an Event object and you would WaitOnMultiple to be able to act on the first unit of work that was complete. On Linux you would have to roll your own solution using lower-level primitives and it will not be correct. Being able to wait on multiple events on Linux will be awesome.
- badamp 7y agoLinux already has what you’re talking about with eventfd and epoll. In Linux each thread can get an eventfd and you can POLLIN all of them. In fact I would argue that using futexes is the “roll your own solution” using lower level primitives (and easier to fuckup) much more so than eventfd and epoll. As mentioned somewhat poorly in the post, using futexes gives a performance boost which is not surprising since they are fast user mutexes. FWIW I didnt think windows events had a fast user space path but I may be mistaken. For most worker pool scenarios you’re describing, the overhead of eventfd is probably in the noise.
- Taniwha 7y agoThey point out that they already have an implementation that does just this .... and it fails on some programs due to running out of file descriptors (they have one program that needs ~1 million of them ...)
- mjevans 7y agoI recall higher performance browsers also use up large numbers of FDs; I suspect it might be for this very reason.
- badamp 7y agoIf you read the full thread that is a bit of a red herring and beside the point (thats why I said the conveyance of the performance implication was poor)... indeed window WFMO only supports 64 objects per call. They mention that the fd issue is due to leaking objects in many windows programs..which was an odd mention and a little off the main subject. The main motivator is performance. If eventfds performed better it would likely be better to fix the fd leak issue with a cache. Again.. eventfd and epoll covers the same use case as WFMO and EVENTs.
- alexchamberlain 7y agoThis is awesome. If I understand this correctly, this would allow you to write a library that allows you to wait on multiple, fully independent queues from a single consumer thread. At the moment, those queues would have to share a mutex.