17 ms·

Proposed futex2 allows Linux to mimic the NT kernel for better Wine performance

389 points by marcodiego 6y ago

alexhutcheson 6y ago
Bummer that this doesn’t seem to support or explicitly plan for the proposed FUTEX_SWAP operation[1] (unless I’m missing it). [1] https://lwn.net/Articles/824409/ https://lwn.net/Articles/824409/
- dundarious 6y ago
  I haven't read anything about FUTEX_SWAP since Aug 2020. Do you know is there ongoing progress?
maxfurman 6y ago
Can someone please ELI5 what is a futex? Is it like a mutex?
- hulitu 6y ago
  As far as i remember a futex is a fast mutex
- corbet 6y ago
  See https://lwn.net/Articles/823513/ https://lwn.net/Articles/823513/ for a look at both the old and proposed new futex interfaces.
- achernya 6y ago
  futex is a Fast Userspace muTEX. It's the syscall to help implement a mutex when there are two or more threads waiting on the lock to let other processes/threads schedule and do useful work during the wait.
- hyperman1 6y ago
  Futex stands for fast userspace mutex. It is a basic building block for implementing a mutex (amongst others). Afaik, if locking a mutex succeeds, futexes avoid a context switch to and from the kernel. The fast path happens completely in userspace. Only when a mutex lock causes a thread to sleep, the kernel is needed. All of this improves mutex performance. There are other locking primitives than mutexes, and the current futex interface is not optimal for implementing common windows ones. Hence this proposal.
  - xxs 6y ago
    >"context switch to and from the kernel" This is a common misconception, a "context" switch is a lot more expensive than a "mode" switch that goes from user mode to the kernel mode (and back). Of course, if the futex has to wait, it'd be a context switch for real.
  - ece 6y ago
    ESYNC is the way this is currently done, it's hit and miss in that it doesn't work unless the number of open files is set high enough for some games. It's also slower than this proposal.
  - deleted 6y ago
    [deleted]
- gpderetta 6y ago
  A futex is an ephemeral list of waiting threads or processes keyed on an address. It can be used to implement any synchronization or signaling primitive, like mutexes, condition variables, semaphores, etc.
  - tialaramex 6y ago
    This is a really nice insight into the kernel's model of what's going on. It's probably not the best way for an absolute beginner to think about why they want this, but it's much better than some of the other explanations if you have trickier technical or performance questions, and it makes it obvious why it's clever and why you need the OS kernel to actually implement it.
- whoisburbansky 6y ago
  It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty good rundown: https://eli.thegreenplace.net/2018/basics-of-futexes/ https://eli.thegreenplace.net/2018/basics-of-futexes/
  - bogomipz 6y ago
    This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"Before the introduction of futexes, system calls were required for locking and unlocking shared resources (for example semop)." >"A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true" The first indicates futexes are an improvement because they avoid the overhead of system call but the second states that futex() is a system call. Is this similar to how a vDSO or vsyscall works where a page from kernel address space is mapped into all users processes? In other words is it similar to how gettimeofday works?[1] [1] https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
    - kccqzy 6y ago
      It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
      - gpderetta 6y ago
        IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. Any kernel state is created lazily when needed (i.e on the first wait) and destroyed automatically when not needed (i.e. when the last waiter is woken up). Coupled with the minimal userspace space requirements (just a 32 bit word) it means that futexes can be embedded very cheaply in a lot of places.
- DSingularity 6y ago
  Okay, consider a multi-threaded program. These programs have multiple threads running on multiple cores. Sometimes you want to coordinate the execution of multiple threads in such programs. A common example is when a thread is in a "critical section" where it is only safe for one thread to access/modify state. Sometimes threads will have to wait for each other. This is where the futex comes in. Instead of the thread to wait while using the processor it can tell the OS that it needs to wait for this futex to become free. The OS will then suspend the thread and find another one to schedule in its place.
  - bogomipz 6y ago
    Ah Interesting. So is the concept of futex() similar to how a process in kernel mode will yield the CPU by putting itself on a wait_queue and call the schedule() function before it issues an I/O request then? I realize that one is userspace and the other kernel but would the above be the right mental model?
    - gpderetta 6y ago
      Yes, a futex is basically a waitqueue abstraction coupled with a TOCTOU guard.
- ROARosen 6y ago
  Can someone please ELI5 what is a mutex?
  - marcodiego 6y ago
    Mutex is named after "mutual exclusion" a primitive that is used to guarantee that some parts of code will run exclusively, never at the same time. This is important for good performance and synchronization on multiple threaded programs.
  - __init 6y ago
    (Edited because I transposed "mutex" and "semaphore" in my mind.) A mutex is a lock -- if multiple users attempt to access a resource simultaneously, they each attempt to acquire the lock serially, and those not first are excluded (blocked) until the current holder releases the lock. Mutexes are typically implemented with semaphores: First a more developer-oriented explanation (because I imagine that's what you really want): A semaphore locks a shared resource by implementing two operations, "up" and "down". First, the semaphore is initialized to some positive integer, which represents how many concurrent "users" (typically threads) can use that resource. Then, each time a user wants to take advantage of that resource, it "down"s the semaphore , which atomically subtracts one from the current value -- but the key is that the semaphore's value can _never_ be negative, so if the value is currently zero, "down"ing a semaphore implies blocking until it's non-zero again. "Up"ing is just what you'd imagine: atomically increment the semaphore value, and unblock someone waiting, if necessary. Semaphores are generally seen as a fundamental primitive (one reason being that locks/mutexes can be implemented trivially as a semaphore initialized to one), but they also have broad use as a general synchronization mechanism between threads. For a true ELI5 of semaphores (I enjoy writing these): Imagine everyone in class needs to write something, but there are only three pencils available, so you devise a system (a system of mutual exclusion, per se) for everyone to follow while the pencils are used: First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the semaphore) you subtract one from the number in your head and give them a pencil. But if that number is zero, you don't have any pencils left, so you ask the person to wait. When someone returns and is done with their pencil, you hand it off to someone waiting, or, if nobody is waiting, you add one to that number in your head and take the pencil back ("up"ing the semaphore). It's important that you decide to only handle one request at a time (atomicity) -- if you tried to do too many things at once, you might lose track of your pencil count and accidentally promise more pencils than you have.
- Iwan-Zotow 6y ago
  it is thing behind/inside mutex. It is making uncontested mutex acquire/release ops pure userspace thingy.
- brandmeyer 6y ago
  The best introduction is probably the original presentation paper from 2002. Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pd... Another great paper that came after some additional experience by glibc developers: Futexes are Tricky, by Ulrich Drepper https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf
  - MaxBarraclough 6y ago
    I see Drepper resisted the urge to pluralise futex to futices.
- bogomipz 6y ago
  I just found this article which I think is really helpful as it has some good historical context as well: "Detailed approach of the futex" http://www.rkoucha.fr/tech_corner/the_futex.html http://www.rkoucha.fr/tech_corner/the_futex.html
a-dub 6y ago
what's the nt api call called? WaitForMultipleObjects? takes me back 20 years just thinking about it...
- Joker_vD 6y ago
  By the way, hearing about futex implementation and their API considerations should also bring everyone about 20 years back.
- dboreham 6y ago
  The NT api would begin ntXxxx WaitForMultipleObjects is a Win32 function.
  - poizan42 6y ago
    I don't know why you are being downvoted, you are completely right. The NT api function is NtWaitForMultipleObjects. The Win32 apis WaitForMultipleObjects and WaitForMultipleObjectsEx are thin wrappers over this.
    - AndriyKunitsyn 6y ago
      Is this NT API actually possible to be called from userspace? Or even from drivers?
      - poizan42 6y ago
        Yes of course, they are all exported from ntdll.dll (in userspace) and ntoskrnl.exe (in kernelspace). You may need to link dynamically or make your own import libraries for many of them though.
      - andrealmeid 6y ago
        Sure, here's an userspace example: https://docs.microsoft.com/en-us/windows/win32/sync/waiting-for-multiple-objects https://docs.microsoft.com/en-us/windows/win32/sync/waiting-...
      - 6y ago
c7DJTLrn 6y ago
This might get me some angry replies, but does the feature set of Linux ever end? Will there ever be a day where someone says "you know what, Linux isn't built for this and your code adds too much complexity, let's not". It really just seems like Linux has become a dumping ground for anyone to introduce whatever they feel like as long as it passes code review, with nobody looking at the big picture.
- trillic 6y ago
  So what? This code (and most drivers, modules, additional fucntionality, etc) will only be compiled in if necessary and will only actually be run if you use the feature.
  - c7DJTLrn 6y ago
    My concern is not about what my flavor of kernel includes. It's about the size of the codebase, and whether the limited number of maintainers can keep up with the countless features being introduced.
    - coolreader18 6y ago
      I mean I think in terms of maintainer resources Linux is one of the projects with the least to worry about, there are always companies who are willing to have a team work on stuff.
      - Ericson2314 6y ago
        Those megacorps also accumulate endless complexity internally, as does the industry as a whole. It's a problem larger than the discipline of reviewers of C code could ever hope to fix. Even the larger world outside the field is somewhat aware of the the looming complexity problem: https://www.theatlantic.com/technology/archive/2017/09/saving-the-world-from-code/540393/ https://www.theatlantic.com/technology/archive/2017/09/savin... Basically on our current trajectory we will end up with something like the biosphere that can do stuff but too complex to fully understand --- but also probably well more fragile than that?
marcodiego 6y ago
Artificial benchmarks show a 4% improvement in some cases, which is huge. There aren't many tests to demonstrate the improvements on common use cases but there are already reports of subjective improvements with games having less stutter: https://www.phoronix.com/forums/forum/phoronix/latest-phoronix-articles/1253763-updated-futex2-system-call-patches-posted-for-helping-wine-proton-other-use-cases?p=1253803#post1253803 https://www.phoronix.com/forums/forum/phoronix/latest-phoron...
- savant_penguin 6y ago
  Really curious, why is 4% improvement huge?
  - k1rcher 6y ago
    This is interesting. Does anyone know of previous figures on Windows virtualization improvement?
    - delroth 6y ago
      It's not 4% improvement for the wine use case, it's 4% improvement in existing synthetic benchmarks for the futex syscall. And a 21% regression in performance in another synthetic benchmark. It's likely the wine WMO implementation is getting a much more significant increase in performance than 4%, but the patch description doesn't provide numbers.
  - deleted 6y ago
    [deleted]
  - marcodiego 6y ago
    Because you don't have to change one line of your previously running software to get this benefit or replace your hardware. Of course, will need a new version of the kernel and wine, but that is a matter of time to hit distro repositories. Also, consider that this will accumulate when combined with new user space libs, servers, compilers, drivers... Software will improve without any change just by keeping your distro updated. Yes, a 4% improvement is huge.
zamalek 6y ago
> The use case lies in the Wine implementation of the Windows NT interface WaitMultipleObjects. This can't only be a win for emulating Windows, surely (future) Linux native code could benefit from this too?
- deleted 6y ago
  [deleted]
- CoolGuySteve 6y ago
  Linux's answer is io_uring with eventfd. I've noticed it has higher latency than WaitForMultipleObjects though. I've had a hard time getting the 99th percentile latency below 5usec. It would be nice if io_uring polling had a futex-like feature that spinned in userspace rather than having to syscall io_uring_wait every time. I feel like that feature would be more universal than futex2. Adding an atomic int somewhere in the userspace would add ~100ns in the kernel path but save many microseconds in the userspace-spin path during high contention so it seems like a win to me.
  - the8472 6y ago
    My understanding of io_uring is that you can already poll the CQ with atomics without any syscall. io_uring_enter() is only needed to inform the kernel that new SQ entries exist and that too can be replaced by polling via IORING_SETUP_SQPOLL in privileged processes.
  - vardump 6y ago
    Spinning consumes a lot of power, so I'd guess one would only want to do that when very low latency is truly required. At least I'd certainly wouldn't want it to be the default for the generic case. Of course a low latency option should also exist for those cases that require it and currently that pretty much means spinning.
  - guenthert 6y ago
    > I've had a hard time getting the 99th percentile latency below 5usec. Can we take a moment to appreciate how mind-blowing astonishing a 99th percentile latency in the us range is given a general-purpose, multi-user OS with support for virtual memory is?
aasasd 6y ago
I lowkey have to wonder why Linux seemingly goes all-in on monster functions that implement a variety of operations depending on the arguments (as far as I can see from casual encounters). In my experience, such code often both reads poorly on the calling side and looks very messy inside. I came to prefer making distinct functions that spell out their intended action in the names. Windows apparently went the same path. E.g.: syscall doesn't accept multiple handles and other bells and whistles? Well duh, it's not supposed to—just make a new one that does. Of course, it's probably too late to change this design choice now...
- whatshisface 6y ago
  I can only offer speculation, but it could be that the alternative, a complicated API that requires several subsequent calls to use, is seen as more of a risk for bad programming and state mis-tracking. We definitely don't want programs leaving the kernel in a bad state by calling the first half of a sequence of syscalls then later on getting distracted or crashing and never finishing it. A single call gives atomicity guarantees that are otherwise hard to come by in languages without state tracking primitives like futures or borrow checked references. Another thing to remember is that in C, it's easier to make a call more specific, by hardcoding values than it is to make it more general, by picking between variants in a branch. I can see programmers wishing the API was more dynamic while writing a giant if-else tree to select the appropriate version of the syscall, but the opposite problem, when the same invocation is always needed but the API takes a lot of dynamic options, is not as bad because it is easy to write a bunch of literals in the line that calls the function. (If C had named arguments that approach would be almost flawless.)
  - aasasd 6y ago
    I don't see how `an_op_syscall(param)` is ‘more complicated’ or requires more calls or state than `a_syscall(OP_NAME, param)`.
    - whatshisface 6y ago
      Since C doesn't have first-class functions, if you needed to dynamically pick between values of OP_NAME you'd be glad it was a parameter. Imagine ten options parameters, which your program needs to choose between depending on the circumstances. That's a huge branch tree. Imagine choosing between two options - you'd need to keep track of function pointers, or at least write your own enum. C makes it far nicer to handle enum values than it is to handle functions, because ints are first-class. I agree that there's no difference between a symbol in the name and a value in the args when your program always needs the same value, but sometimes it needs dynamism.
Cloudef 6y ago
What happened to NTSYNC? https://lore.kernel.org/lkml/f4cc1a38-1441-62f8-47e4-0c67f5ad1d43@codeweavers.com/T/#u https://lore.kernel.org/lkml/f4cc1a38-1441-62f8-47e4-0c67f5a...
- elynl 6y ago
  It's still a thing! kernel: https://repo.or.cz/linux/zf.git/shortlog/refs/heads/winesync https://repo.or.cz/linux/zf.git/shortlog/refs/heads/winesync wine: https://repo.or.cz/wine/zf.git/shortlog/refs/heads/fastsync2 https://repo.or.cz/wine/zf.git/shortlog/refs/heads/fastsync2 They decided to rename it since the kernel maintainers don't want NT interfaces and having NT in the name doesn't help
  - Cloudef 6y ago
    Thats good to hear. Darling devs also went with kernel module approach. Its weird wine devs did not do the same until now. Wineserver is nice but as we see, its sometimes impossible to do accurate emulation of some apis there. https://docs.darlinghq.org/internals/basics/system-call-emulation.html https://docs.darlinghq.org/internals/basics/system-call-emul...
    - elynl 6y ago
      I guess they didn't go down that path in order to increase portability. A good chunk of crossover (wine with paid support) customers run macOS.
      - Cloudef 6y ago
        Thats a good point
monocasa 6y ago
Too bad bpf isn't allowed for non root yet. A bpf futex program like xok's wake programs would be more general, and way nicer.
- fefe23 6y ago
  What are you talking about? I have been using bpf in seccomp for non-root for years. Maybe your distro patched that out. The stock kernel allows bpf for non-root.
  - monocasa 6y ago
    Sort of... there's been push back in the post spectre days of expanding non root usage of BPF. Right now, a subset of trace programs and seccomp are allowed for non-root, but that hasn't expanded since 2016. Everything else requires CAP_SYS_ADMIN. They would probably remove those too if the balance of Linux didn't put "don't break user space" higher than "defense in depth security".
    - broodbucket 6y ago
      Just in recent months we've had CVE-2020-2717{0,1} (memory exposure) followed by CVE-2021-29154 (arbitrary code execution on x86). None of which have even had fixes applied by certain distros[0]. I don't really know what the use cases for unprivileged BPF are though. [0] https://access.redhat.com/security/cve/cve-2021-29154 https://access.redhat.com/security/cve/cve-2021-29154
Shadonototro 6y ago
if linux people focused on offering compelling ecosystem for app/game distribution, they wouldn't need to bloat their os with slow and bloated emulators like wine the reason why linux isn't gaining shares on steam anymore is because valve openly said linux has no ecosystem and is forced to emulate windows -- proton
- ijlx 6y ago
  Wine is not an emulator, it is a compatibility layer for Windows system calls on a Unix-like platform. If something runs on wine, the performance overhead should be unnoticeable/very small for the typical user.
  - chungy 6y ago
    Ironically, it seems quite often that Wine runs apps/games faster than Windows does.
  - encryptluks2 6y ago
    A compatibility layer wouldn't require that you essentially emulate the same file system layout, registry and functionality. It is basically emulating a Windows environment.
    - anthk 6y ago
      So Windows 10 emulates Windows XP/2000/98 too?
      - encryptluks2 6y ago
        Pretty much... they took a pile of crap and kept adding onto it.
        Dah00n 6y ago
        That has nothing in common with emulating though. Running ARM code in x64 is emulating. If adding code were emulating than Linux is emulating Linux v0.1. Wine isn't an emulator. PCSX2 is an emulator.
twoodfin 6y ago
Unclear to me from the writeup: Would it be possible to implement the original futex() API on top of futex2() or is Linux doomed to preserve most of two complete futex implementations?
- guipsp 6y ago
  Would it be possible? Probably yes, but not performant.
nwmcsween 6y ago
A bit OT but I don't understand why kernel interfaces are single purpose vs a data-driven api, it seems like such a wasted opportunity to optimize and to have a fluid api
jwilk 6y ago
I find the lore.kernel.org UI much nicer: https://lore.kernel.org/lkml/20210427231248.220501-1-andrealmeid@collabora.com/ https://lore.kernel.org/lkml/20210427231248.220501-1-andreal...

389 points by marcodiego 6y ago

Bummer that this doesn’t seem to support or explicitly plan for the proposed FUTEX_SWAP operation[1] (unless I’m missing it). [1] https://lwn.net/Articles/824409/ https://lwn.net/Articles/824409/

dundarious 6y ago
I haven't read anything about FUTEX_SWAP since Aug 2020. Do you know is there ongoing progress?

maxfurman 6y ago

Can someone please ELI5 what is a futex? Is it like a mutex?

hulitu 6y ago
As far as i remember a futex is a fast mutex
corbet 6y ago
See https://lwn.net/Articles/823513/ https://lwn.net/Articles/823513/ for a look at both the old and proposed new futex interfaces.
achernya 6y ago
futex is a Fast Userspace muTEX. It's the syscall to help implement a mutex when there are two or more threads waiting on the lock to let other processes/threads schedule and do useful work during the wait.
hyperman1 6y ago
Futex stands for fast userspace mutex. It is a basic building block for implementing a mutex (amongst others). Afaik, if locking a mutex succeeds, futexes avoid a context switch to and from the kernel. The fast path happens completely in userspace. Only when a mutex lock causes a thread to sleep, the kernel is needed. All of this improves mutex performance. There are other locking primitives than mutexes, and the current futex interface is not optimal for implementing common windows ones. Hence this proposal.
- xxs 6y ago
  >"context switch to and from the kernel" This is a common misconception, a "context" switch is a lot more expensive than a "mode" switch that goes from user mode to the kernel mode (and back). Of course, if the futex has to wait, it'd be a context switch for real.
- ece 6y ago
  ESYNC is the way this is currently done, it's hit and miss in that it doesn't work unless the number of open files is set high enough for some games. It's also slower than this proposal.
- deleted 6y ago
  [deleted]
gpderetta 6y ago
A futex is an ephemeral list of waiting threads or processes keyed on an address. It can be used to implement any synchronization or signaling primitive, like mutexes, condition variables, semaphores, etc.
- tialaramex 6y ago
  This is a really nice insight into the kernel's model of what's going on. It's probably not the best way for an absolute beginner to think about why they want this, but it's much better than some of the other explanations if you have trickier technical or performance questions, and it makes it obvious why it's clever and why you need the OS kernel to actually implement it.
whoisburbansky 6y ago
It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty good rundown: https://eli.thegreenplace.net/2018/basics-of-futexes/ https://eli.thegreenplace.net/2018/basics-of-futexes/
- bogomipz 6y ago
  This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"Before the introduction of futexes, system calls were required for locking and unlocking shared resources (for example semop)." >"A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true" The first indicates futexes are an improvement because they avoid the overhead of system call but the second states that futex() is a system call. Is this similar to how a vDSO or vsyscall works where a page from kernel address space is mapped into all users processes? In other words is it similar to how gettimeofday works?[1] [1] https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
  - kccqzy 6y ago
    It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
    - gpderetta 6y ago
      IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. Any kernel state is created lazily when needed (i.e on the first wait) and destroyed automatically when not needed (i.e. when the last waiter is woken up). Coupled with the minimal userspace space requirements (just a 32 bit word) it means that futexes can be embedded very cheaply in a lot of places.
DSingularity 6y ago
Okay, consider a multi-threaded program. These programs have multiple threads running on multiple cores. Sometimes you want to coordinate the execution of multiple threads in such programs. A common example is when a thread is in a "critical section" where it is only safe for one thread to access/modify state. Sometimes threads will have to wait for each other. This is where the futex comes in. Instead of the thread to wait while using the processor it can tell the OS that it needs to wait for this futex to become free. The OS will then suspend the thread and find another one to schedule in its place.
- bogomipz 6y ago
  Ah Interesting. So is the concept of futex() similar to how a process in kernel mode will yield the CPU by putting itself on a wait_queue and call the schedule() function before it issues an I/O request then? I realize that one is userspace and the other kernel but would the above be the right mental model?
  - gpderetta 6y ago
    Yes, a futex is basically a waitqueue abstraction coupled with a TOCTOU guard.
ROARosen 6y ago
Can someone please ELI5 what is a mutex?
- marcodiego 6y ago
  Mutex is named after "mutual exclusion" a primitive that is used to guarantee that some parts of code will run exclusively, never at the same time. This is important for good performance and synchronization on multiple threaded programs.
- __init 6y ago
  (Edited because I transposed "mutex" and "semaphore" in my mind.) A mutex is a lock -- if multiple users attempt to access a resource simultaneously, they each attempt to acquire the lock serially, and those not first are excluded (blocked) until the current holder releases the lock. Mutexes are typically implemented with semaphores: First a more developer-oriented explanation (because I imagine that's what you really want): A semaphore locks a shared resource by implementing two operations, "up" and "down". First, the semaphore is initialized to some positive integer, which represents how many concurrent "users" (typically threads) can use that resource. Then, each time a user wants to take advantage of that resource, it "down"s the semaphore , which atomically subtracts one from the current value -- but the key is that the semaphore's value can _never_ be negative, so if the value is currently zero, "down"ing a semaphore implies blocking until it's non-zero again. "Up"ing is just what you'd imagine: atomically increment the semaphore value, and unblock someone waiting, if necessary. Semaphores are generally seen as a fundamental primitive (one reason being that locks/mutexes can be implemented trivially as a semaphore initialized to one), but they also have broad use as a general synchronization mechanism between threads. For a true ELI5 of semaphores (I enjoy writing these): Imagine everyone in class needs to write something, but there are only three pencils available, so you devise a system (a system of mutual exclusion, per se) for everyone to follow while the pencils are used: First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the semaphore) you subtract one from the number in your head and give them a pencil. But if that number is zero, you don't have any pencils left, so you ask the person to wait. When someone returns and is done with their pencil, you hand it off to someone waiting, or, if nobody is waiting, you add one to that number in your head and take the pencil back ("up"ing the semaphore). It's important that you decide to only handle one request at a time (atomicity) -- if you tried to do too many things at once, you might lose track of your pencil count and accidentally promise more pencils than you have.
Iwan-Zotow 6y ago
it is thing behind/inside mutex. It is making uncontested mutex acquire/release ops pure userspace thingy.
brandmeyer 6y ago
The best introduction is probably the original presentation paper from 2002. Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pd... Another great paper that came after some additional experience by glibc developers: Futexes are Tricky, by Ulrich Drepper https://www.akkadia.org/drepper/futex.pdf https://www.akkadia.org/drepper/futex.pdf
- MaxBarraclough 6y ago
  I see Drepper resisted the urge to pluralise futex to futices.
bogomipz 6y ago
I just found this article which I think is really helpful as it has some good historical context as well: "Detailed approach of the futex" http://www.rkoucha.fr/tech_corner/the_futex.html http://www.rkoucha.fr/tech_corner/the_futex.html

a-dub 6y ago

what's the nt api call called? WaitForMultipleObjects? takes me back 20 years just thinking about it...

Joker_vD 6y ago
By the way, hearing about futex implementation and their API considerations should also bring everyone about 20 years back.
dboreham 6y ago
The NT api would begin ntXxxx WaitForMultipleObjects is a Win32 function.
- poizan42 6y ago
  I don't know why you are being downvoted, you are completely right. The NT api function is NtWaitForMultipleObjects. The Win32 apis WaitForMultipleObjects and WaitForMultipleObjectsEx are thin wrappers over this.
  - AndriyKunitsyn 6y ago
    Is this NT API actually possible to be called from userspace? Or even from drivers?
    - poizan42 6y ago
      Yes of course, they are all exported from ntdll.dll (in userspace) and ntoskrnl.exe (in kernelspace). You may need to link dynamically or make your own import libraries for many of them though.
    - andrealmeid 6y ago
      Sure, here's an userspace example: https://docs.microsoft.com/en-us/windows/win32/sync/waiting-for-multiple-objects https://docs.microsoft.com/en-us/windows/win32/sync/waiting-...
    - 6y ago

c7DJTLrn 6y ago

This might get me some angry replies, but does the feature set of Linux ever end? Will there ever be a day where someone says "you know what, Linux isn't built for this and your code adds too much complexity, let's not". It really just seems like Linux has become a dumping ground for anyone to introduce whatever they feel like as long as it passes code review, with nobody looking at the big picture.

trillic 6y ago
So what? This code (and most drivers, modules, additional fucntionality, etc) will only be compiled in if necessary and will only actually be run if you use the feature.
- c7DJTLrn 6y ago
  My concern is not about what my flavor of kernel includes. It's about the size of the codebase, and whether the limited number of maintainers can keep up with the countless features being introduced.
  - coolreader18 6y ago
    I mean I think in terms of maintainer resources Linux is one of the projects with the least to worry about, there are always companies who are willing to have a team work on stuff.
    - Ericson2314 6y ago
      Those megacorps also accumulate endless complexity internally, as does the industry as a whole. It's a problem larger than the discipline of reviewers of C code could ever hope to fix. Even the larger world outside the field is somewhat aware of the the looming complexity problem: https://www.theatlantic.com/technology/archive/2017/09/saving-the-world-from-code/540393/ https://www.theatlantic.com/technology/archive/2017/09/savin... Basically on our current trajectory we will end up with something like the biosphere that can do stuff but too complex to fully understand --- but also probably well more fragile than that?

marcodiego 6y ago

Artificial benchmarks show a 4% improvement in some cases, which is huge. There aren't many tests to demonstrate the improvements on common use cases but there are already reports of subjective improvements with games having less stutter: https://www.phoronix.com/forums/forum/phoronix/latest-phoronix-articles/1253763-updated-futex2-system-call-patches-posted-for-helping-wine-proton-other-use-cases?p=1253803#post1253803 https://www.phoronix.com/forums/forum/phoronix/latest-phoron...

savant_penguin 6y ago
Really curious, why is 4% improvement huge?
- k1rcher 6y ago
  This is interesting. Does anyone know of previous figures on Windows virtualization improvement?
  - delroth 6y ago
    It's not 4% improvement for the wine use case, it's 4% improvement in existing synthetic benchmarks for the futex syscall. And a 21% regression in performance in another synthetic benchmark. It's likely the wine WMO implementation is getting a much more significant increase in performance than 4%, but the patch description doesn't provide numbers.
- deleted 6y ago
  [deleted]
- marcodiego 6y ago
  Because you don't have to change one line of your previously running software to get this benefit or replace your hardware. Of course, will need a new version of the kernel and wine, but that is a matter of time to hit distro repositories. Also, consider that this will accumulate when combined with new user space libs, servers, compilers, drivers... Software will improve without any change just by keeping your distro updated. Yes, a 4% improvement is huge.

zamalek 6y ago

> The use case lies in the Wine implementation of the Windows NT interface WaitMultipleObjects. This can't only be a win for emulating Windows, surely (future) Linux native code could benefit from this too?

deleted 6y ago
[deleted]
CoolGuySteve 6y ago
Linux's answer is io_uring with eventfd. I've noticed it has higher latency than WaitForMultipleObjects though. I've had a hard time getting the 99th percentile latency below 5usec. It would be nice if io_uring polling had a futex-like feature that spinned in userspace rather than having to syscall io_uring_wait every time. I feel like that feature would be more universal than futex2. Adding an atomic int somewhere in the userspace would add ~100ns in the kernel path but save many microseconds in the userspace-spin path during high contention so it seems like a win to me.
- the8472 6y ago
  My understanding of io_uring is that you can already poll the CQ with atomics without any syscall. io_uring_enter() is only needed to inform the kernel that new SQ entries exist and that too can be replaced by polling via IORING_SETUP_SQPOLL in privileged processes.
- vardump 6y ago
  Spinning consumes a lot of power, so I'd guess one would only want to do that when very low latency is truly required. At least I'd certainly wouldn't want it to be the default for the generic case. Of course a low latency option should also exist for those cases that require it and currently that pretty much means spinning.
- guenthert 6y ago
  > I've had a hard time getting the 99th percentile latency below 5usec. Can we take a moment to appreciate how mind-blowing astonishing a 99th percentile latency in the us range is given a general-purpose, multi-user OS with support for virtual memory is?

aasasd 6y ago

I lowkey have to wonder why Linux seemingly goes all-in on monster functions that implement a variety of operations depending on the arguments (as far as I can see from casual encounters). In my experience, such code often both reads poorly on the calling side and looks very messy inside. I came to prefer making distinct functions that spell out their intended action in the names. Windows apparently went the same path. E.g.: syscall doesn't accept multiple handles and other bells and whistles? Well duh, it's not supposed to—just make a new one that does. Of course, it's probably too late to change this design choice now...

whatshisface 6y ago
I can only offer speculation, but it could be that the alternative, a complicated API that requires several subsequent calls to use, is seen as more of a risk for bad programming and state mis-tracking. We definitely don't want programs leaving the kernel in a bad state by calling the first half of a sequence of syscalls then later on getting distracted or crashing and never finishing it. A single call gives atomicity guarantees that are otherwise hard to come by in languages without state tracking primitives like futures or borrow checked references. Another thing to remember is that in C, it's easier to make a call more specific, by hardcoding values than it is to make it more general, by picking between variants in a branch. I can see programmers wishing the API was more dynamic while writing a giant if-else tree to select the appropriate version of the syscall, but the opposite problem, when the same invocation is always needed but the API takes a lot of dynamic options, is not as bad because it is easy to write a bunch of literals in the line that calls the function. (If C had named arguments that approach would be almost flawless.)
- aasasd 6y ago
  I don't see how `an_op_syscall(param)` is ‘more complicated’ or requires more calls or state than `a_syscall(OP_NAME, param)`.
  - whatshisface 6y ago
    Since C doesn't have first-class functions, if you needed to dynamically pick between values of OP_NAME you'd be glad it was a parameter. Imagine ten options parameters, which your program needs to choose between depending on the circumstances. That's a huge branch tree. Imagine choosing between two options - you'd need to keep track of function pointers, or at least write your own enum. C makes it far nicer to handle enum values than it is to handle functions, because ints are first-class. I agree that there's no difference between a symbol in the name and a value in the args when your program always needs the same value, but sometimes it needs dynamism.

Cloudef 6y ago

What happened to NTSYNC? https://lore.kernel.org/lkml/f4cc1a38-1441-62f8-47e4-0c67f5ad1d43@codeweavers.com/T/#u https://lore.kernel.org/lkml/f4cc1a38-1441-62f8-47e4-0c67f5a...

elynl 6y ago
It's still a thing! kernel: https://repo.or.cz/linux/zf.git/shortlog/refs/heads/winesync https://repo.or.cz/linux/zf.git/shortlog/refs/heads/winesync wine: https://repo.or.cz/wine/zf.git/shortlog/refs/heads/fastsync2 https://repo.or.cz/wine/zf.git/shortlog/refs/heads/fastsync2 They decided to rename it since the kernel maintainers don't want NT interfaces and having NT in the name doesn't help
- Cloudef 6y ago
  Thats good to hear. Darling devs also went with kernel module approach. Its weird wine devs did not do the same until now. Wineserver is nice but as we see, its sometimes impossible to do accurate emulation of some apis there. https://docs.darlinghq.org/internals/basics/system-call-emulation.html https://docs.darlinghq.org/internals/basics/system-call-emul...
  - elynl 6y ago
    I guess they didn't go down that path in order to increase portability. A good chunk of crossover (wine with paid support) customers run macOS.
    - Cloudef 6y ago
      Thats a good point

monocasa 6y ago

Too bad bpf isn't allowed for non root yet. A bpf futex program like xok's wake programs would be more general, and way nicer.

fefe23 6y ago
What are you talking about? I have been using bpf in seccomp for non-root for years. Maybe your distro patched that out. The stock kernel allows bpf for non-root.
- monocasa 6y ago
  Sort of... there's been push back in the post spectre days of expanding non root usage of BPF. Right now, a subset of trace programs and seccomp are allowed for non-root, but that hasn't expanded since 2016. Everything else requires CAP_SYS_ADMIN. They would probably remove those too if the balance of Linux didn't put "don't break user space" higher than "defense in depth security".
  - broodbucket 6y ago
    Just in recent months we've had CVE-2020-2717{0,1} (memory exposure) followed by CVE-2021-29154 (arbitrary code execution on x86). None of which have even had fixes applied by certain distros[0]. I don't really know what the use cases for unprivileged BPF are though. [0] https://access.redhat.com/security/cve/cve-2021-29154 https://access.redhat.com/security/cve/cve-2021-29154

Shadonototro 6y ago

if linux people focused on offering compelling ecosystem for app/game distribution, they wouldn't need to bloat their os with slow and bloated emulators like wine the reason why linux isn't gaining shares on steam anymore is because valve openly said linux has no ecosystem and is forced to emulate windows -- proton

ijlx 6y ago
Wine is not an emulator, it is a compatibility layer for Windows system calls on a Unix-like platform. If something runs on wine, the performance overhead should be unnoticeable/very small for the typical user.
- chungy 6y ago
  Ironically, it seems quite often that Wine runs apps/games faster than Windows does.
- encryptluks2 6y ago
  A compatibility layer wouldn't require that you essentially emulate the same file system layout, registry and functionality. It is basically emulating a Windows environment.
  - anthk 6y ago
    So Windows 10 emulates Windows XP/2000/98 too?
    - encryptluks2 6y ago
      Pretty much... they took a pile of crap and kept adding onto it.
      - Dah00n 6y ago
        That has nothing in common with emulating though. Running ARM code in x64 is emulating. If adding code were emulating than Linux is emulating Linux v0.1. Wine isn't an emulator. PCSX2 is an emulator.

twoodfin 6y ago

Unclear to me from the writeup: Would it be possible to implement the original futex() API on top of futex2() or is Linux doomed to preserve most of two complete futex implementations?

guipsp 6y ago
Would it be possible? Probably yes, but not performant.

nwmcsween 6y ago

A bit OT but I don't understand why kernel interfaces are single purpose vs a data-driven api, it seems like such a wasted opportunity to optimize and to have a fluid api

jwilk 6y ago

I find the lore.kernel.org UI much nicer: https://lore.kernel.org/lkml/20210427231248.220501-1-andrealmeid@collabora.com/ https://lore.kernel.org/lkml/20210427231248.220501-1-andreal...