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.
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.
>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.
This is an extremely interesting and useful observation, thank you for making it.
Futexes are missing a lot of useful functionality - see the OP, and as another example it's very hard to integrate them with an event loop - so I've been dreading building anything with them, but I thought I needed it to get fast synchronization. But for my use cases, I already have setup and teardown calls. Maybe I can do fast userspace synchronization on top of some other kernel object - a pipe, or something, as you suggest.
Do you have any more to share about this observation, or pointers to any implementations of fast userspace synchronization on top of something other than futexes?
You can use eventfd as a pollable waiting primitive.
But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases.
>But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases.
I'm not sure what you mean, can you elaborate? Suppose I had a mutex (synchronization) implemented with a futex, and a shared memory queue (waiting) implemented with a futex; suppose both are being used to coordinate between multiple processes. I guess you're suggesting that one of those two doesn't need to be integrated with an event loop? But why? Both of those seem useful to have as part of an event loop.
You wouldn't want to use an event loop to wait for a mutex as it doesn't really make much sense. It does make sense to use an event loop to wait for empty/non empty events (which on a normal queue you would implement with a cond var).
You have two options: you can use an eventfd to implement the queue full/empty event, or provide a generic notification interface (i.e. a callback). Any non event loop users wiuld simply have the callback signal a futex, but it allows for more complex use case: obviously you can wakeup the event loop from the callback, but you could resume a coroutine, send an async signal or whatever makes sense for the application.
>'The key phrase is "only when" in the second sentence'
Thank you for pointing this out. That makes sense. This is sort of like the idea that the fastest system call is the one that is never made. Can you say how does something in userland know if something "would" block without actually crossing the user/kernel boundary? Does the kernel expose a queue length counter or similar via a read-only page?
The trick is, the memory address futex cares about is how you signal. Normally, in the "uncontended" case, everybody involved uses atomic memory access to manipulate this memory location (for example they set it to 1 as a flag to say somebody is in the mutually excluded code and then back to zero to say now nobody is in there) and they pay no kernel cost at all for this feature. The kernel has no idea the memory is even special.
But in the contended case the flag is already set by somebody else, so you leave a sign (maybe you set it to 42) about the contention in the memory address, and you tell the kernel that you're going to sleep and it should wake you back up once whoever is blocking you releases. When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you.
None of the conventional semantics are enforced by the operating system. If you write buggy code which just scribbles nonsense on the magic flag location, your program doesn't work properly. Too bad. The kernel does contain some code that helps do some tricks lots of people want to do using futexes, and so for that reason you should stick to the conventions, but nobody will force you to.
Thanks for this insight. A couple quick questions:
>"When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you.
Did you mean to say "and it's time to release to you" here?
>"None of the conventional semantics are enforced by the operating system"
Ah OK, this is the part that I feel is maybe always left out of the things I've read on futex(). I guess this is just always implied then that some library implements these semantics correctly? And that library is generally going to glibc?
> Ah OK, this is the part that I feel is maybe always left out of the things I've read on futex(). I guess this is just always implied then that some library implements these semantics correctly? And that library is generally going to glibc?
Yup. For example, the pthread_foo functions are futexes under the hood.
The POSIX threading API accommodates many possible implementations, and so in Linux many of the bits that look expensive (and might be on other systems) are more or less free thanks to futexes, e.g. setting up the mutex in Linux is just allocating an aligned 32-bit value on the heap and setting it to some initialising value, but on some systems it involves an OS system call to get a mutex handle.
This is the true benefit of the futex. The typical scheme for using it looks almost exactly like a well known trick for speeding up conventional mutual exclusion features that have low contention, which you'd see in say BeOS as the Benaphore, or described in several books about high performance programming. But those tricks all imply the expense of first obtaining a handle from the operating system for every such mutex whereas with a futex that part is free and you only talk to the operating system at all once there is contention for it to help you manage.
>"The typical scheme for using it looks almost exactly like a well known trick for speeding up conventional mutual exclusion features that have low contention, which you'd see in say BeOS as the Benaphore, or described in several books about high performance programming."
Do you have any links that document this trick in Linux? Is there name for it or search term I could use to find out more?
The phrase you'd have used to describe this when it wasn't just how everything works on a good OS is "Lightweight mutex". Here's Be explaining the "Benaphore" for example:
Note that when I say "typical scheme for using it" I did not mean, that your program should implement such a scheme itself, instead futex is intended for the sort of people who implement the concurrency features in your language or APIs to use - and this is how they'd go about doing that to deliver the features you just use. So, for most of us this is interesting to know about but unlikely to impact our day-to-day practice.
The most common implementation of mutexes using futex() is that the userland simply spins a while waiting to acquire the mutex (just atomic operations, no system call). After a while the userland gives up spinning and makes the system call.
