It's not that deep. The futex was developed just to save you from issuing a special system call to ask the OS to put you on a wait queue.
The whole point is that implementing a mutex requires doing things that only the privileged OS kernel can do (e.g. efficiently blocking/unblocking processes). Therefore, for systems like Linux, it made sense to combine the features for a fast implementation.
I think the coolest part of the futex is that it's a handle-less concept. There's no allocation or deallocation via syscall, just a kernel-based memory watcher that turns out to be incredibly useful as a primitive.
Everything goes cleanly away when there are no more waiters, and the kernel never even sees a mutex where there's no contention.
I would be interested in a technical deep dive of how the kernel manages these in a performant way, however.
Lets be clear here; the book sets itself up as a way to gain understanding of multiprocessor programming, in a way that promotes skilled reasoning that is applicable across many subdomains. In many places it points out that you should avoid implementing constructs yourself, but instead use a library/language/system provided construct. It specifically calls this out for mutexes.
The book is quite clearly about concurrency in general, and not for a specific platform. The author of this article has set up a straw man to facilitate the writing and marketing of an otherwise moderately interesting article on futexes.
Personally I find the approach taken by this article more than a little distasteful - presenting from a point of exaggerated conflict is both tiresome and likely to confuse. This article could easily have been written from the perspective "what TAoMP doesn't tell you" and in that vein be taken a lot more collaboratively.
Of course it doesn't escape me that this blog is new, this article was posted by Phil, and Phil has promoted one of their other articles before.
Is it just me or moving things out of kernel space improves performance in general? Like context switching, mutex or entire TCP stack. I wonder what else can be moved into user space.
As the article mentions, Windows introduced a futex-like thing in Windows 8. I know that the original Win32 critical section is based on a kernel-level semaphore. What about the SRW lock introduced in Vista?
> And in practice, behavior across common implementations [of recursive locks] is not remotely consistent. There’s a good reason why this was left undefined – it’s kind of hard.
This is such a frustrating stance that most standards have, honestly. "Well, obviously we can't expect the OS/language implementers to be able to reliably implement feature X ― let's just leave it to the application programmer to deal with; they are, after all, are expected to have great skill sets and could easily work around it". Or rather, "well, we can't force feature X on the people who will actually implement the standard (they are the members of this very committee, after all), but we can't trivially force the downstream users to cope with the feature's absence because seriously, what can those losers do? Switch the vendors?".
I still haven’t seen a good comparison between Futex and Benaphore. Benaphores I understand, it predates Futexes by almost a decade, but what do Futexes add to the equation since hardly anyone talks about Benaphores (or is it a case of not invented here)?
> Many people won’t worry about crashed threads, as they often will crash the whole program. However, you can catch the signal a crash generates and keep the overall process from terminating.
That doesn't help if the entire process dies for any reason and you want to clean up the locks. Solution to that is called "robust" locks. You can register list of held futexes with the kernel using sys_set_robust_list, and when the thread dies kernel for each entry will set a specific bit and wake waiter if there's one.
"The requeue-once rule is enforced by only allowing requeueing to the futex previously passed to futex_wait_requeue_pi as uaddr2, so it's not possible to requeue from A to B, then from B to C - but it is possible to requeue from B to B.
When this happens, if (!q.rt_waiter) passes, so rt_mutex_finish_proxy_lock is never called. (Also, AFAIK, free_pi_state is never called, which is true even without this weird requeue; in the case where futex_requeue calls requeue_pi_wake_futex directly, pi_state will sit around until it gets cleaned up in exit_pi_state_list when the thread exits. This is not a vulnerability.) futex_wait_requeue_pi exits, and various pointers to rt_waiter become dangling.
"
I’m right now working with this topic, so vey happy to find it here. The only problem: I like to read with the phone horizontally. If you do that the 2025 footer takes 45% of screen… I mias plain HTML so much!
Maybe you'd like Anthony Williams's _C++ Concurrency in Action_, which doesn't cover futexes (or how to write your own synchronization primitives in general), but does cover real-world details like memory orderings and SMR for lock-free data structures. If that's still too high-level, then maybe check out Paul McKenney's excellent free monograph "Is Parallel Programming Hard, And, If So,
What Can You Do About It?" for a more hardware-focused perspective (which doesn't cover futexes in detail either but does direct you to the canonical reference for implementing futex-based primitives, namely Ulrich Drepper's "Futexes Are Tricky").
I think TAOMPP is fine for what it is (teaching high-level concurrency concepts) and discussing OS-level implementation details would be out of place. The important thing it teaches is how to think about concurrency, not how to write your own synchronization primitives. E.g., the Peterson or bakery locks are useless in the real world (as the book admits), but understanding their proofs of correctness will help you reason about the concurrent algorithms you have to write yourself.
Bakery locks are good for spin locks. They're more cache friendly. Plus you can do reader/writer spin locks. They're going to be strictly FIFO though.
I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for.
Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing.
Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack.
* Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.
> Going back to the original futuex paper in 2002, it was immediately clear that the futex was a huge improvement in highly concurrent environments. Just in that original paper, their tests with 1000 parallel tasks ran 20-120 times faster than sysv locks..
I think this is a misunderstanding.
The baseline isn’t sysv locks. The baseline isn’t even what Linux was doing before futexes (Linux had a very immature lock implementation before futexes).
The baseline is all of the ways folks implement locks if they don’t have futexes, which end up having roughly the same properties as a futex based lock:
- fast path that doesn’t hit kernel for either lock or unlock
- slow path that somehow makes the thread wait until the lock is available using some kernel waiting primitive.
The thing futexes improve is the size of the user level data structure that is used for representing the lock in the waiting state. That’s it.
And futexes aren’t the only way to get there. Alternatives:
- thin locks (what JVMs use)
- ParkingLot (a futex-like primitive that works entirely in userland and doesn’t require that the OS have futexes)
This led me down a bit of a rabbit-hole involving linux's limitation of only supporting 32 bit integers for futexes, and why that is, and the implementation of semaphores in glibc.
In one discussion of supporting 64 bit integers for futexes, Linus suggested that you can just use 64 bit atomics in userspace, but only use 32 bits of that 64 bit integer for the futex, as long as the bits that change on a wakeup are in those 32 bits.
However, AFAICT, using mixed-size atomics in c/c++ is undefined behavior, although on most modern hardware it does work. But looking at the implementation of semaphore in glibc, that is exactly what it does. The semaphore uses a 64 bit integer, with the number of waiters in the high 32 bits, and the value of the semaphore in the low 32 bits, with userspace atomic operations on the whole 64 bit integer, but using just the low 32 bits for the futex.
Is my question is, does gcc specifically consider this defined behavior, or is it ok because the 32 bit access happens in a separate (kernel) process that isn't part of the same compilation, or is it actually undefined behavior in glibc?
FWIW I resonate a lot with what the author says about the art of multiprocessor programming. When I learned it in college (from the author himself no less), it felt like a very theoretical introduction to a deeply practical problem domain. I could complete the practice problems well, but that didn’t teach me the intuition for writing multithreaded programs. Later on once I’ve been through the trenches in the industry and came back to the book, everything started to make more sense and I started to see parallels with distributed systems.
Honestly I think if you really want to understand this topic, getting exposed to atomic memory ordering early on and writing simplified spin locks / SPSC queues is the way to go. You don’t even have to implement them correctly - the implementation just needs to teach you what could go wrong. The book operates at an abstraction level that makes it not very useful inexperienced students.
23 comments
[ 2.6 ms ] story [ 45.2 ms ] threadThe whole point is that implementing a mutex requires doing things that only the privileged OS kernel can do (e.g. efficiently blocking/unblocking processes). Therefore, for systems like Linux, it made sense to combine the features for a fast implementation.
Everything goes cleanly away when there are no more waiters, and the kernel never even sees a mutex where there's no contention.
I would be interested in a technical deep dive of how the kernel manages these in a performant way, however.
EDIT: TIL about futex2 as well: https://docs.kernel.org/userspace-api/futex2.html
The book is quite clearly about concurrency in general, and not for a specific platform. The author of this article has set up a straw man to facilitate the writing and marketing of an otherwise moderately interesting article on futexes.
Personally I find the approach taken by this article more than a little distasteful - presenting from a point of exaggerated conflict is both tiresome and likely to confuse. This article could easily have been written from the perspective "what TAoMP doesn't tell you" and in that vein be taken a lot more collaboratively.
Of course it doesn't escape me that this blog is new, this article was posted by Phil, and Phil has promoted one of their other articles before.
[1] https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
This is such a frustrating stance that most standards have, honestly. "Well, obviously we can't expect the OS/language implementers to be able to reliably implement feature X ― let's just leave it to the application programmer to deal with; they are, after all, are expected to have great skill sets and could easily work around it". Or rather, "well, we can't force feature X on the people who will actually implement the standard (they are the members of this very committee, after all), but we can't trivially force the downstream users to cope with the feature's absence because seriously, what can those losers do? Switch the vendors?".
There's been a nice stream of improvements to futex2 since.
NUMA support (finally landing!), https://www.phoronix.com/news/FUTEX2-NUMA-Small-Futex https://www.phoronix.com/news/FUTEX2-Improvements-Linux-6.16 (see also this fantastic recent submission on NUMA in general, absolutely critical performance stuff, https://news.ycombinator.com/item?id=44936575)
Io_uring support in 6.7 (2024), (with a nice write up on it speeding up postgresql aio), https://www.phoronix.com/news/IO_uring-FUTEX-Linux-6.7
Small requeue and single wait additions in 6.7, https://www.phoronix.com/news/Linux-6.7-Locking-FUTEX2
That doesn't help if the entire process dies for any reason and you want to clean up the locks. Solution to that is called "robust" locks. You can register list of held futexes with the kernel using sys_set_robust_list, and when the thread dies kernel for each entry will set a specific bit and wake waiter if there's one.
"The requeue-once rule is enforced by only allowing requeueing to the futex previously passed to futex_wait_requeue_pi as uaddr2, so it's not possible to requeue from A to B, then from B to C - but it is possible to requeue from B to B.
When this happens, if (!q.rt_waiter) passes, so rt_mutex_finish_proxy_lock is never called. (Also, AFAIK, free_pi_state is never called, which is true even without this weird requeue; in the case where futex_requeue calls requeue_pi_wake_futex directly, pi_state will sit around until it gets cleaned up in exit_pi_state_list when the thread exits. This is not a vulnerability.) futex_wait_requeue_pi exits, and various pointers to rt_waiter become dangling. "
I think TAOMPP is fine for what it is (teaching high-level concurrency concepts) and discussing OS-level implementation details would be out of place. The important thing it teaches is how to think about concurrency, not how to write your own synchronization primitives. E.g., the Peterson or bakery locks are useless in the real world (as the book admits), but understanding their proofs of correctness will help you reason about the concurrent algorithms you have to write yourself.
I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for.
Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing.
Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack.
* Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.
[0] https://marabos.nl/atomics/os-primitives.html#linux
Is there any really nice listing/walk through these standard libraries/rustdoc like website?
Does everyone just dig through header files and man pages all day?
I think this is a misunderstanding.
The baseline isn’t sysv locks. The baseline isn’t even what Linux was doing before futexes (Linux had a very immature lock implementation before futexes).
The baseline is all of the ways folks implement locks if they don’t have futexes, which end up having roughly the same properties as a futex based lock:
- fast path that doesn’t hit kernel for either lock or unlock
- slow path that somehow makes the thread wait until the lock is available using some kernel waiting primitive.
The thing futexes improve is the size of the user level data structure that is used for representing the lock in the waiting state. That’s it.
And futexes aren’t the only way to get there. Alternatives:
- thin locks (what JVMs use)
- ParkingLot (a futex-like primitive that works entirely in userland and doesn’t require that the OS have futexes)
In one discussion of supporting 64 bit integers for futexes, Linus suggested that you can just use 64 bit atomics in userspace, but only use 32 bits of that 64 bit integer for the futex, as long as the bits that change on a wakeup are in those 32 bits.
However, AFAICT, using mixed-size atomics in c/c++ is undefined behavior, although on most modern hardware it does work. But looking at the implementation of semaphore in glibc, that is exactly what it does. The semaphore uses a 64 bit integer, with the number of waiters in the high 32 bits, and the value of the semaphore in the low 32 bits, with userspace atomic operations on the whole 64 bit integer, but using just the low 32 bits for the futex.
Is my question is, does gcc specifically consider this defined behavior, or is it ok because the 32 bit access happens in a separate (kernel) process that isn't part of the same compilation, or is it actually undefined behavior in glibc?
Honestly I think if you really want to understand this topic, getting exposed to atomic memory ordering early on and writing simplified spin locks / SPSC queues is the way to go. You don’t even have to implement them correctly - the implementation just needs to teach you what could go wrong. The book operates at an abstraction level that makes it not very useful inexperienced students.