Windows did not gain a WaitForMultipleObjects, it had it since the first Windows NT, more than 30 years ago.
While WaitForMultipleObjects was an advantage of Windows NT over UNIX, it was nothing new. IBM PL/I had an equivalent function already in 1965, almost 30 years before Windows NT.
The "wait" function of IBM PL/I was actually the model for the UNIX "wait", but the UNIX function was extremely simplified and much weaker than its model, like it was also the case with the many features inherited by UNIX from Multics. Unfortunately, many decades had to pass until the descendants of UNIX began to gain features comparable in sophistication with those of the ancestors of UNIX.
However the Microsoft WaitForSingleObject and WaitForMultipleObjects did not have an efficient implementation, which is why they had to add WaitOnAddress, the equivalent of Linux futex.
It is true however that the Linux futex had and still has some annoying limitations, like the size of only 32 bits of the futex value, instead of 64 bits, and the fact that it is possible to wait only on a single event. Using atomic bit operations on the futex value it is actually possible to wait on multiple events, though not in the most efficient way. However here is where the 32-bit size of the futex value becomes annoying.
Therefore the work that attempts to combine the advantages of "futex" with some of the advantages of WaitForMultipleObjects is very welcome.
However this does not ape Windows, but it just reimplements techniques that are much older than the Microsoft company, which were well known more than a half of century ago.
garaetjjte · 51m ago
>However the Microsoft WaitForSingleObject and WaitForMultipleObjects did not have an efficient implementation, which is why they had to add WaitOnAddress
WaitForSingle/MultipleObjects wait for kernel objects, similiar to poll. WaitOnAddress is lightweight synchronization, equivalent to futex. Windows doesn't have something like WaitForMultipleAddresses. futex_waitv was used by Wine patches because they implement NT kernel objects in userspace, and there were some semantic differences that made it hard to represent them as eventfds.
PS: But using futexes to emulate kernel objects breaks security boundaries of a process. That's why it was never merged into upstream Wine, and NTSYNC was developed.
viega · 1h ago
That's very interesting history, thanks.
I agree with Linux still only supporting 32-bit futexes is a bit baffling. The only reason the width matters is for the race condition check, but that's a huge reason. I'd want to have the option to wait on values as wide as whatever the underlying hardware supports, at least!
adrian_b · 58m ago
The futex width matters if you implement your own waiting on multiple events, with one bit per event. The events can be signaled with atomic bit operations.
ciconia · 1h ago
io_uring support for futexes is really nice. I used it to implement mutexes and queues for working with Ruby fibers:
Futex has nothing to do with WFMO. Futex is equivalent to keyed events.
The linux equivalent of WFMO is select/poll/epoll.
jlokier · 2h ago
Perhaps they meant to write WaitOnAddress, which is the same as a basic futex.
gpderetta · 1h ago
yes, sorry, I meant WaitOnAddress. I thought they were also called keyed events (or at least that was the NT name) but I might be wrong.
garaetjjte · 1h ago
Keyed event is older thing, somewhat similar but lacks value comparison.
ape4 · 1h ago
WaitOnAddress() allows 32 or 64 bit addresses. "[in] AddressSize The size of the value, in bytes. This parameter can be 1, 2, 4, or 8."
jauntywundrkind · 2h ago
Maybe perhaps, but its not clear to me what makes you argue that, and it doesn't match up from what I've read. From the article:
> People often describe the futex as, "Wait on memory address". That overlooks the notification side, but it’s a much more apt name, and why Windows’ name for this API (WaitOnAddress) is superior API naming (to be fair, they did have a decade to think about the name).
The difference between an Address and an Object feels pretty abstract to me. The API surfaced otherwise feels extremely similar. So I'm not sure that there's a ton of ground to stand on for this distinction you are trying to draw. Your assertions could use some argumentation to back them up.
From the Futex2 pull requests in 5.16:
> Add a new sys_futex_waitv() syscall which allows to wait on multiple futexes. The main use case is emulating Windows' WaitForMultipleObjects which allows Wine to improve the performance of Windows Games.
mmastrac · 4h ago
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.
Exactly! At the same time you also don't want to call into the kernel's internal malloc() whenever a thread ends up blocking on a lock to allocate the data structures that are needed to keep track of queues of blocked threads for a given lock.
To prevent that, many operating systems allocate these 'queue objects' whenever threads are created and will attach a pointer to it from the thread object. Whenever a thread then stumbles upon a contended lock, it will effectively 'donate' this queue object to that lock, meaning that every lock having one or more waiters will have a linked list of 'queue objects' attached to it. When threads are woken up, they will each take one of those objects with them on the way out. But there's no guarantee that they will get their own queue object back; they may get shuffled! So by the time a thread terminates, it will free one of those objects, but that may not necessarily be the one it created.
I think the first operating system to use this method was Solaris. There they called these 'queue objects' turnstiles. The BSDs adopted the same approach, and kept the same name.
> 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?".
ori_b · 3h ago
If you overspecify, you close the door to better implementations. This is why, for example, C++ standard hash tables and regexes are an order of magnitude slower than third party ones.
The standard didn't say "you must implement std::unordered_map as a hash table with chained buckets and extra memory allocations", but ithe standard specified several guarantees that make it very difficult to implement hash tables with open addressing.
Every constraint that you specify potentially locks out a better implementation.
For recursive rwlocks, there's a lot of ways to implement them. Do you want to lock out high performance implementations that do less error checking, for example?
jesse__ · 1h ago
This is exactly the issue, and unordered_map exemplifies it perfectly.
On paper, unordered_map sounds great. It lists all the admirable properties you would theoretically want in a hashtable. Then in practice when you go to implement it, you realize that you've painted yourself into a garbage fire, as the saying goes.
I suppose this is a failing of the design by committee method, where the committee isn't directly responsible for implementation either before or during standard writing.
dragontamer · 2h ago
To clarify, I believe the issue is C++ unordered map iterators and when / where they are allowed to go invalid.
OpenAddressing means that an address of map[thing] could change on insert. Which means iterators and pointer invalidation concepts can go stale on insert.
C++11 standard for unordered_map guarantees this won't happen. But that forces slower implementations.
And now people rely upon the standard so we can't change it. At best we do fast_unordered_map or unordered_map2 with different guarantees.
tialaramex · 1h ago
There are numerous factors where std::unordered_map makes API design choices that you would not make today and the invalidation of iterators (or lack thereof) is just one. A particularly frustrating issue is that std::unordered_map promises some things we suspect nobody cares about, but whereas Rust routinely does "crater runs" in which they discover to a good approximation whether their changes break the ecosystem (via hidden ABI dependencies, Hyrum's law etc.) there is little equivalent for C++ and much scare mongering about claimed large codebases hidden from sight which may use absolutely anything.
The most stupid thing about std::unordered_map is that it was standardized in 2011, so it isn't from 1998 like much of the C++ standard library containers, it's newer and yet apparently nothing was learned.
gpderetta · 4m ago
It was standardized in c++11, but it was standardizing hash_map that was in the original STL pre-C++98 and was available as an extension in most STL derived standard libraries.
For me the remaining reason I still reach for unordered_map is if I need reference stability as most faster hash tables don't provide it (and I don't care enough about performance to build reference stability on top of a better hash map).
Joker_vD · 2h ago
And if you underspecify, you force the users to invent their own hacks and workarounds, often very poorly.
And no, I don't want to "high performance" lock implementations that regularly completely deadlock the whole process (deadlocked processes are not very performant) unless wrap every single one of the several hundred uses of them in a test with dubiously-predictable branches, or worse, just completely break the lock invariants (e.g., the lock is now permanently unlocked, even after a lock() on it succeeds) ― it really is not that important how fast you can do the wrong thing.
ori_b · 1h ago
The thing is: recursive locking is a bad idea overall, and the tracking needed to make it work on relock contexts isn't worth the overhead it imposes in the common case.
It would be better if the spec simply said it was disallowed.
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.
viega · 3h ago
I wrote the article; it was motivated by reading the book, which to my estimation is not well aimed for either academics or practitioners. That's a problem across a big chunk of academia right now, and I hear it not just from industry who would like to have people more prepared coming out of college, but from masters students who realize that they're not learning what they want to be good.
So in no way was it meant to be a strawman around a "hey, learn about the futex!" post (as evidenced by other complaints at the end of things lacking). The fact is, I was disappointed enough with the book, that I put aside another post I was writing for it.
But as for Phil, we did work together several years ago, and he reads my stuff. I didn't just start writing, and have never had problems finding an audience in the past, Phil or not.
f1shy · 1h ago
Please think about removing the “2025” footer, as it takes almost half my screen on the phone if I put it horizontal. I had to switch to read mode. I suppose is ok, but I assume the article is to be read…
viega · 58m ago
Yeah, a few other people have mentioned this too; I looked and it is indeed abysmal. I'm not the person responsible for the layout, but I will make sure it gets fixed before posting anything else, even if I have to go tweak it myself.
chillingeffect · 2h ago
Yeah the part about not even calling the previous sysv style a dinosaur bc it implies it was once mighty is like standing on the shoulders of giants and pooping on their heads. A little humility is all that is required.
viega · 1h ago
Fair. That was meant as tongue in cheek-- sysv was impressive for its day, and its day lasted a long time.
I appreciate that not everyone loves my style of humor, but I know when I read things with similar styles, it keeps me more engaged with the material.
Still, I am not trying to make jokes at the expense of actual people, so I'll take the note and try to avoid, thanks.
garaetjjte · 2h ago
> 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.
inetknght · 2h ago
> 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.
My biggest worry with that kind of thing is that the lock was guarding something which is now in an inconsistent state.
Without thoroughly understanding how/why the particular thread crashed, there's no guarantee that the data is in any sort of valid or recoverable state. In that case, crashing the whole app is absolutely a better thing to do.
It's really cool that the capabilities exist to do cleanup/recovery after a single thread crashed. But I think (off-the-cuff guess) that 95% of engineers won't know how to properly utilize robust locks with robust data structures, 4% won't have the time to engineer (including documentation) that kind of solution, and the last 1% are really really well-paid (or, should be) and would find better ways to prevent the crash from happening in the first place.
monocasa · 1h ago
I think the point isn't to expose this to normal developers, but instead do stuff like enable rust like poisoned states in locks.
viega · 1h ago
Yes, good comment on something I glossed over for sure (I tried to stop the mutex discussion at the process boundary, to keep from going forever).
"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.
"
mwcampbell · 3h ago
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?
garaetjjte · 2h ago
Neither CRITICAL_SECTION nor SRWLock enters the kernel when uncontended. (SRWLock is based on keyed events, CRITICAL_SECTION nowadays creates kernel object on-demand but falls back to keyed event on failure)
musjleman · 1h ago
SRW lock uses the WaitOnAddress primitives nowadays, not keyed events.
reinhardt1053 · 2h ago
So what's recommended as a better alternative to The Art of Multiprocessor Programming?
Jtsummers · 2h ago
The Art of Multiprocessor Programming. It does talk about reentrant locks and other things this review says it doesn't. The more interesting parts of it though are the back half, after going through lock implementations and such it actually starts solving problems using both lock-based and lock-free designs.
Follow it up with something appropriate to the language you're using, like C++ Concurrency in Action for C++ (much of it transfers to other languages).
viega · 1h ago
I will also say, it's likely this is the best text book on concurrency. There are some first principles where it's explanations are engaging and clear.
It's just that book ignores the very real changes that are at the core of modern concurrency (including Async), and that I don't believe is a positive.
And while it did mention recursion, I looked really hard for it to cover things like shared lock-cleanup on `fork()` or thread crash, and a number of other important (often encountered) real-world concerns, and didn't find anything.
viega · 1h ago
I didn't say it doesn't deal with recursive locks. I said it is so cursory that they don't even acknowledge that their guidance can't really be applied to a RW lock.
Half of the source code is colored very-light-on-white, which is impossible to read. I'm using Chrome on Android.
viega · 56m ago
Interesting, and thanks; that's not how it's supposed to look for sure. I'll ask someone to look at the whole mobile experience, definitely not my area.
smallstepforman · 2h ago
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)?
tialaramex · 1h ago
As others have explained the Benaphore is a speed-up for an existing OS primitive, but the futex is a new primitive that's often much better suited to the problem you have. Benoit Schillings uses this name "Benaphore" but never claims explicitly to have invented it in the article naming it, either way though Benoit worked for Be Inc. which were making an entire OS including its kernel, so they could have provided the better primitive. But they didn't, BeOS provided the limited semaphore primitive you'd have seen in a typical 1980s or 1990s Unix.
Given that primitive, the Benaphore is a good way to use it, like if you've got a 1930s refrigerator and you've got a clever technique to reduce frost build-up - a modern fridge has a smarter controller and so it'll just defrost itself anyway automatically, no sweat. The Benaphore is thus redundant today - like that anti-frost technique for your 90 year old fridge.
garaetjjte · 1h ago
Benaphore is a kernel synchronization object behind atomic counter for uncontended path. But the kernel object needs to be always here, initialized and destroyed when appropriate.
Futex doesn't need any kernel initialization, and from perspective of kernel it doesn't exist at all when there are no waiters.
(see also CRITICAL_SECTION, which originally always had kernel object created with it, but it was later changed to create them on-demand falling back to keyed event on failure. SRWLock only uses keyed events. Keyed event only needs one object per process, and otherwise consumes kernel resources only if there are any waiters.)
the_mitsuhiko · 2h ago
Other then avoiding a syscall on an uncontended path they are not really similar. A benaphore is just a semaphore with an extra atomic counter in userspace to count waiters.
You can’t really use semaphores to implement things that can’t mutexes or semaphores so the overall utility is limited compare to futexes that you can use for condvars and other primitives too.
afr0ck · 4h ago
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.
viega · 4h ago
Also, I should say, in user-land you can efficiently enough save thread state, go off and do something else with that thread, then come back to it, never hitting the kernel while something blocks. That's pretty much async in a nutshell (or green threads).
The point of the article anyway is that it's inexcusable to have a modern concurrency textbook and not cover the futex, since it's at the core of any efficient primitive on modern hardware.
koverstreet · 4h ago
The problem with green threads, historically, was that there was no way to do arbitrary syscalls async; if your syscall blocks it blocks all your other green threads. Doh.
io_uring is supposed to be about solving this, but it's quite the kitchen sink so I have no idea how complete it is on the "arbitrary syscall async" front.
viega · 4h ago
Yes, it's gotten quite large, but I think with far fewer wrong turns in the API compared to the futex. Enough was available async via `epoll()` + having fd interfaces to things that I never was as worried about the arbitrary latency of syscalls, but it's still incredibly cool, especially in the number of calls it avoids outright.
johncolanduoni · 3h ago
`epoll` doesn’t actually do any IO though, so it doesn’t help with syscall latency. It just avoids the overhead of doing IO via a large number of threads (memory overhead, hard context switches, etc.).
viega · 3h ago
No it doesn't, which is one key reason why I am a fan of `io_uring`. I brought `epoll` up because it does help with the blocking though, for most of the things that matter when it comes to async (at a cost to latency, of course).
viega · 4h ago
You actually issue the `futex` system call to get yourself on the wait queue tied to the memory address. It separates out the waiting from the locking.
And that can absolutely save a bunch of system calls, especially vs. polling mixed with `sleep()` or similar.
ajross · 4h ago
> It separates out the waiting from the locking.
It does not, in fact the two are fundamentally inseparable and the state of the memory address must be treated atomically with the waiting state. The magic of futex is that you can use a hardware atomic operation (c.f. lock cmpxchg on x86) to get the lock in the common/uncontended case, but if you have to wait you need to tell the kernel both that you need to wait and the address on which you're waiting, so it can use the same hardware interlocks along with its own state locking to put you to sleep race-free.
viega · 4h ago
It quite does; the kernel is not the keeper of the lock, it only needs to detect the race condition that would result in a spurious sleep. It cares not one bit about the rest of your semantics.
It's true you could use it that way, but it's not the way it's meant to be used, defeating the purpose by requiring a system call even for uncontended locks.
ajross · 1h ago
I think you're misunderstanding how futexes work, or else making an essentially irrelevant semantic argument around a definition for "keeper". The kernel is, 100%, absolutely, the "keeper" of that lock data for the duration of the system call. It knows that (hardware) address and matches it to any other such syscall from any other process on the system. And that requires tracking and intelligence and interaction with the VM system and arch layer up and down the stack.
It just doesn't "allocate" it on its own and lets the process use its own mapped memory. But to pretend that it doesn't have to do any work or that the memory is "separated" betrays some misunderstandings about what is actually happening here.
viega · 1h ago
The kernel is responsible for maintaining the wait queues, and making sure that there is no race condition on the state that should preclude queueing.
It does not care how you use the queue, at all. It doesn't have to be done with a locking primitive, whatsoever. You absolutely can use the exact same mechanism to implement a thread pool with a set of dormant threads, for instance.
The state check in the basic futex is only done to avoid a race condition. None of the logic of preventing threads from entering critical sections is in the purview of the kernel, either. That's all application-level.
And most importantly, no real lock uses a futex for the locking parts. As mentioned in the article, typically a mutex will directly try to acquire the lock with an atomic operation, like an atomic fetch-and-or, fetch-and-add, or even compare-and-swap.
A single atomic op, even if you go for full sequential consistency (which comes w/ full pipeline stalls), is still a lot better than a trip into the kernel when you can avoid it.
Once again, I'm not saying you couldn't use the futex state check to decide what's locked and what's not. I'm saying nobody should, and it was never the intent.
The intent from the beginning was to separate out the locking from the waiting, and I think that's pretty clear in the original futex paper (linked to in my article).
ajross · 4h ago
Why is this gray!? This is absolutely correct. Futex was added as an ad hoc solution to the obvious needs of SMP processes communicating via atomic memory operations who still wanted blocking IPC. And it had to be updated and reworked repeatedly as it moved out of the original application (locks and semaphores) into stuff like condition variables and priority inheritance where it didn't work nearly as well.
In point of fact futex is really not a particularly simple syscall and has a lot of traps, see the man page. But the core idea is indeed "not that deep".
viega · 4h ago
As the article says, the futex system call is overly complicated. But one shouldn't downplay its importance. Every major OS has had a slimmed down equivalent for about a decade, and the futex is at the core of any good modern lock.
Many things are obvious after, but there was plenty of time before for other people to do the same thing, it's not like we didn't know sysv semaphores didn't scale well.
"ad hoc" feels like an opinion here. My opinion is that when separation of concerns leads to big gains like the futex did, that's elegant, and an achievement. No need to diminish the good work done!
bicolao · 3h ago
If this is ad hoc solution, what's the "right" approach?
ajross · 2h ago
Futex is a fine solution for locks and semaphores (FUTEX_WAIT/WAKE operations). It's been extended repeatedly to handle the needs of condition variables, priority inheritance, timeouts, interop with file descriptors and async/io_uring, etc... with the result that a lot of the API exists to support newer operations with oddball semantics and not a few genuine mistakes and traps (often undocumented). See the glibc condition variable code for how complicated this can get.
Also, while googling for some examples for you I was reminded of this LWN article from a few years back that details some of the issues: https://lwn.net/Articles/823513/
viega · 1h ago
Just because the Linux futex call is currently a Swiss Army knife with some parts that add no value (which I do say in the article) doesn't mean that it's not valuable, or important.
The fact that Linux has extended it in so many ways is, in fact, a testament to it to how impactful the futex concept has been to the world of concurrency.
The fact that it's also at the core of other OS primitives does as well. At least on the MacOS side, those primitives do have much simpler APIs, as well. For instance, here's the main wait function:
The wake side is equally simple, with two calls, one to wake one thread, one to wake all threads. No other number matters, so it's a great simplification in my view.
Your fundamental point is that the futex is actually a pretty unimportant construct. Clearly I don't agree, and it's okay not to agree, but I really am struggling to see your counter-argument.
If futexes aren't important to good locks, then, if modern OSes all felt compelled to jettison the futex for some reason, you'd have pthread implementations do ... what exactly??
f1shy · 1h ago
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!
viega · 1h ago
Yeah, I don't love the mobile experience. I'll try to get that fixed soon, thanks.
avodonosov · 2h ago
Can anyone suggest a good explanation of memory barriers?
junon · 1h ago
If you mean memory barriers in terms of concurrency, it's just a primitive for concurrency that counts downward atomically once per participant (e.g. a group of threads) and then each atomically waits until the counter reaches zero before continuing. It's used to synchronize (i.e. put into lockstep) two concurrent processes such that they must all wait at a given point before continuing more or less all at once, often as part of a larger process.
If you mean a barrier in terms of a memory "fence", that's an event on CPUs whereby any pending memory instructions that have been pipelined and thus not committed are forced to commit and complete before continuing. Usually only relevant for a single core, but they're used to make sure that other cores will see the same memory values and your pending writes would reflect (or, conversely, sometimes making sure your own core sees the reads from other cores as fresh as possible before the actual read op).
inetknght · 1h ago
tl;dr:
In a multi-threaded context, memory reads and writes can be reordered by hardware. It gets more complicated with shared cache. Imagine that you have core 1 writing to some address at (nearly) the same time that core 2 reads from that. Does core 2 read the old or the new? Especially if they don't share the same cache -- core 1 might "write" to a given address, but it only gets written to core 1's cache and then "scheduled" to be written out to main memory. Meanwhile, later core 2 tries to read that address, it's not in its cache, so it pulls from main memory before core 1's cache has flushed. As far as core 2 is concerned, the write happened after it read from the address even though physically the write finished in core 1 before core 2's read instruction might have even started.
A memory barrier tells the hardware to ensure that reads-before is also "happens-before" (or after) a given writen to the same address. It's often (but not always) a cache and memory synchronization across cores.
I found Fedora Pikus's cppcon 2017 presentation [1] to be informative, and Michael Wong's 2015 presentation [0] filled in some of the gaps.
C++, being a generic language for many hardware implementations, provides a lot more detailed concepts for memory ordering [2], which is important for hardwares that have more granularity in barrier types that what most people are used to with x86-derived memory models.
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.
whstl · 3h ago
You're right. With the caveat that it's the moving in and out of the kernel that's the expensive part, so putting things inside it also helps with performance... at the expense of security and reliability, of course, so userspace it is!
toast0 · 1h ago
Piling on with others; it's avoiding the context switching and copying between user and kernel that improves performance.
If you can stay in user space, or stay in kernel space, that is likely to be better performance than going back and forth.
This is why sendfile is great; rather than storage -> kernel memory -> user memory -> kernel memory -> network, you get storage -> kernel memory -> network. That's two less copies, and fewer context switches.
It depends on the relative cost of what you're doing of course, but in general, yes, the cost of entering the kernel can be impactful, if you are making a lot of calls into it, since a lot of work has to happen every time.
There are definitely user-land TCP/IP implementations, thread implementations (Go's being particularly notable) and even file systems (FUSE).
bicolao · 3h ago
fuse probably isn't a good example here because you still have to enter kernel space if i'm not mistaken, then out again to the fs driver in userspace then probably back to kernel space (block driver). fuse has many upsides, but I don't think performance is one of them.
viega · 3h ago
Well, you still have to enter the kernel to actually queue an OS-level thread w/ a futex. The kernel supporting being able to move stuff to userland sure doesn't guarantee better performance-- the main opportunity from that perspective is minimizing how often you cross the boundary.
You're 100% right that there are plenty of other considerations, often positive for lifting things out, like minimization of ring 0 attack surface.
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
While WaitForMultipleObjects was an advantage of Windows NT over UNIX, it was nothing new. IBM PL/I had an equivalent function already in 1965, almost 30 years before Windows NT.
The "wait" function of IBM PL/I was actually the model for the UNIX "wait", but the UNIX function was extremely simplified and much weaker than its model, like it was also the case with the many features inherited by UNIX from Multics. Unfortunately, many decades had to pass until the descendants of UNIX began to gain features comparable in sophistication with those of the ancestors of UNIX.
However the Microsoft WaitForSingleObject and WaitForMultipleObjects did not have an efficient implementation, which is why they had to add WaitOnAddress, the equivalent of Linux futex.
It is true however that the Linux futex had and still has some annoying limitations, like the size of only 32 bits of the futex value, instead of 64 bits, and the fact that it is possible to wait only on a single event. Using atomic bit operations on the futex value it is actually possible to wait on multiple events, though not in the most efficient way. However here is where the 32-bit size of the futex value becomes annoying.
Therefore the work that attempts to combine the advantages of "futex" with some of the advantages of WaitForMultipleObjects is very welcome.
However this does not ape Windows, but it just reimplements techniques that are much older than the Microsoft company, which were well known more than a half of century ago.
WaitForSingle/MultipleObjects wait for kernel objects, similiar to poll. WaitOnAddress is lightweight synchronization, equivalent to futex. Windows doesn't have something like WaitForMultipleAddresses. futex_waitv was used by Wine patches because they implement NT kernel objects in userspace, and there were some semantic differences that made it hard to represent them as eventfds.
PS: But using futexes to emulate kernel objects breaks security boundaries of a process. That's why it was never merged into upstream Wine, and NTSYNC was developed.
I agree with Linux still only supporting 32-bit futexes is a bit baffling. The only reason the width matters is for the race condition check, but that's a huge reason. I'd want to have the option to wait on values as wide as whatever the underlying hardware supports, at least!
https://github.com/digital-fabric/uringmachine/blob/main/ext...
The linux equivalent of WFMO is select/poll/epoll.
> People often describe the futex as, "Wait on memory address". That overlooks the notification side, but it’s a much more apt name, and why Windows’ name for this API (WaitOnAddress) is superior API naming (to be fair, they did have a decade to think about the name).
The difference between an Address and an Object feels pretty abstract to me. The API surfaced otherwise feels extremely similar. So I'm not sure that there's a ton of ground to stand on for this distinction you are trying to draw. Your assertions could use some argumentation to back them up.
From the Futex2 pull requests in 5.16:
> Add a new sys_futex_waitv() syscall which allows to wait on multiple futexes. The main use case is emulating Windows' WaitForMultipleObjects which allows Wine to improve the performance of Windows Games.
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
To prevent that, many operating systems allocate these 'queue objects' whenever threads are created and will attach a pointer to it from the thread object. Whenever a thread then stumbles upon a contended lock, it will effectively 'donate' this queue object to that lock, meaning that every lock having one or more waiters will have a linked list of 'queue objects' attached to it. When threads are woken up, they will each take one of those objects with them on the way out. But there's no guarantee that they will get their own queue object back; they may get shuffled! So by the time a thread terminates, it will free one of those objects, but that may not necessarily be the one it created.
I think the first operating system to use this method was Solaris. There they called these 'queue objects' turnstiles. The BSDs adopted the same approach, and kept the same name.
https://www.oreilly.com/library/view/solaristm-internals-cor...
https://www.bsdcan.org/2012/schedule/attachments/195_locking...
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?".
The standard didn't say "you must implement std::unordered_map as a hash table with chained buckets and extra memory allocations", but ithe standard specified several guarantees that make it very difficult to implement hash tables with open addressing.
Every constraint that you specify potentially locks out a better implementation.
For recursive rwlocks, there's a lot of ways to implement them. Do you want to lock out high performance implementations that do less error checking, for example?
On paper, unordered_map sounds great. It lists all the admirable properties you would theoretically want in a hashtable. Then in practice when you go to implement it, you realize that you've painted yourself into a garbage fire, as the saying goes.
I suppose this is a failing of the design by committee method, where the committee isn't directly responsible for implementation either before or during standard writing.
OpenAddressing means that an address of map[thing] could change on insert. Which means iterators and pointer invalidation concepts can go stale on insert.
C++11 standard for unordered_map guarantees this won't happen. But that forces slower implementations.
And now people rely upon the standard so we can't change it. At best we do fast_unordered_map or unordered_map2 with different guarantees.
The most stupid thing about std::unordered_map is that it was standardized in 2011, so it isn't from 1998 like much of the C++ standard library containers, it's newer and yet apparently nothing was learned.
For me the remaining reason I still reach for unordered_map is if I need reference stability as most faster hash tables don't provide it (and I don't care enough about performance to build reference stability on top of a better hash map).
And no, I don't want to "high performance" lock implementations that regularly completely deadlock the whole process (deadlocked processes are not very performant) unless wrap every single one of the several hundred uses of them in a test with dubiously-predictable branches, or worse, just completely break the lock invariants (e.g., the lock is now permanently unlocked, even after a lock() on it succeeds) ― it really is not that important how fast you can do the wrong thing.
It would be better if the spec simply said it was disallowed.
I hate it, but it's true
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.
So in no way was it meant to be a strawman around a "hey, learn about the futex!" post (as evidenced by other complaints at the end of things lacking). The fact is, I was disappointed enough with the book, that I put aside another post I was writing for it.
But as for Phil, we did work together several years ago, and he reads my stuff. I didn't just start writing, and have never had problems finding an audience in the past, Phil or not.
I appreciate that not everyone loves my style of humor, but I know when I read things with similar styles, it keeps me more engaged with the material.
Still, I am not trying to make jokes at the expense of actual people, so I'll take the note and try to avoid, thanks.
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.
My biggest worry with that kind of thing is that the lock was guarding something which is now in an inconsistent state.
Without thoroughly understanding how/why the particular thread crashed, there's no guarantee that the data is in any sort of valid or recoverable state. In that case, crashing the whole app is absolutely a better thing to do.
It's really cool that the capabilities exist to do cleanup/recovery after a single thread crashed. But I think (off-the-cuff guess) that 95% of engineers won't know how to properly utilize robust locks with robust data structures, 4% won't have the time to engineer (including documentation) that kind of solution, and the last 1% are really really well-paid (or, should be) and would find better ways to prevent the crash from happening in the first place.
"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. "
Follow it up with something appropriate to the language you're using, like C++ Concurrency in Action for C++ (much of it transfers to other languages).
It's just that book ignores the very real changes that are at the core of modern concurrency (including Async), and that I don't believe is a positive.
And while it did mention recursion, I looked really hard for it to cover things like shared lock-cleanup on `fork()` or thread crash, and a number of other important (often encountered) real-world concerns, and didn't find anything.
https://man7.org/tlpi/
https://marabos.nl/atomics/
Given that primitive, the Benaphore is a good way to use it, like if you've got a 1930s refrigerator and you've got a clever technique to reduce frost build-up - a modern fridge has a smarter controller and so it'll just defrost itself anyway automatically, no sweat. The Benaphore is thus redundant today - like that anti-frost technique for your 90 year old fridge.
Futex doesn't need any kernel initialization, and from perspective of kernel it doesn't exist at all when there are no waiters.
(see also CRITICAL_SECTION, which originally always had kernel object created with it, but it was later changed to create them on-demand falling back to keyed event on failure. SRWLock only uses keyed events. Keyed event only needs one object per process, and otherwise consumes kernel resources only if there are any waiters.)
You can’t really use semaphores to implement things that can’t mutexes or semaphores so the overall utility is limited compare to futexes that you can use for condvars and other primitives too.
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.
The point of the article anyway is that it's inexcusable to have a modern concurrency textbook and not cover the futex, since it's at the core of any efficient primitive on modern hardware.
io_uring is supposed to be about solving this, but it's quite the kitchen sink so I have no idea how complete it is on the "arbitrary syscall async" front.
And that can absolutely save a bunch of system calls, especially vs. polling mixed with `sleep()` or similar.
It does not, in fact the two are fundamentally inseparable and the state of the memory address must be treated atomically with the waiting state. The magic of futex is that you can use a hardware atomic operation (c.f. lock cmpxchg on x86) to get the lock in the common/uncontended case, but if you have to wait you need to tell the kernel both that you need to wait and the address on which you're waiting, so it can use the same hardware interlocks along with its own state locking to put you to sleep race-free.
It's true you could use it that way, but it's not the way it's meant to be used, defeating the purpose by requiring a system call even for uncontended locks.
It just doesn't "allocate" it on its own and lets the process use its own mapped memory. But to pretend that it doesn't have to do any work or that the memory is "separated" betrays some misunderstandings about what is actually happening here.
It does not care how you use the queue, at all. It doesn't have to be done with a locking primitive, whatsoever. You absolutely can use the exact same mechanism to implement a thread pool with a set of dormant threads, for instance.
The state check in the basic futex is only done to avoid a race condition. None of the logic of preventing threads from entering critical sections is in the purview of the kernel, either. That's all application-level.
And most importantly, no real lock uses a futex for the locking parts. As mentioned in the article, typically a mutex will directly try to acquire the lock with an atomic operation, like an atomic fetch-and-or, fetch-and-add, or even compare-and-swap.
A single atomic op, even if you go for full sequential consistency (which comes w/ full pipeline stalls), is still a lot better than a trip into the kernel when you can avoid it.
Once again, I'm not saying you couldn't use the futex state check to decide what's locked and what's not. I'm saying nobody should, and it was never the intent.
The intent from the beginning was to separate out the locking from the waiting, and I think that's pretty clear in the original futex paper (linked to in my article).
In point of fact futex is really not a particularly simple syscall and has a lot of traps, see the man page. But the core idea is indeed "not that deep".
Many things are obvious after, but there was plenty of time before for other people to do the same thing, it's not like we didn't know sysv semaphores didn't scale well.
"ad hoc" feels like an opinion here. My opinion is that when separation of concerns leads to big gains like the futex did, that's elegant, and an achievement. No need to diminish the good work done!
Also, while googling for some examples for you I was reminded of this LWN article from a few years back that details some of the issues: https://lwn.net/Articles/823513/
The fact that Linux has extended it in so many ways is, in fact, a testament to it to how impactful the futex concept has been to the world of concurrency.
The fact that it's also at the core of other OS primitives does as well. At least on the MacOS side, those primitives do have much simpler APIs, as well. For instance, here's the main wait function:
`extern int os_sync_wait_on_address(void * addr, uint64_t value, size_t size, os_sync_wait_on_address_flags_t flags);`
There's also one with a timeout.
The wake side is equally simple, with two calls, one to wake one thread, one to wake all threads. No other number matters, so it's a great simplification in my view.
Your fundamental point is that the futex is actually a pretty unimportant construct. Clearly I don't agree, and it's okay not to agree, but I really am struggling to see your counter-argument.
If futexes aren't important to good locks, then, if modern OSes all felt compelled to jettison the futex for some reason, you'd have pthread implementations do ... what exactly??
If you mean a barrier in terms of a memory "fence", that's an event on CPUs whereby any pending memory instructions that have been pipelined and thus not committed are forced to commit and complete before continuing. Usually only relevant for a single core, but they're used to make sure that other cores will see the same memory values and your pending writes would reflect (or, conversely, sometimes making sure your own core sees the reads from other cores as fresh as possible before the actual read op).
In a multi-threaded context, memory reads and writes can be reordered by hardware. It gets more complicated with shared cache. Imagine that you have core 1 writing to some address at (nearly) the same time that core 2 reads from that. Does core 2 read the old or the new? Especially if they don't share the same cache -- core 1 might "write" to a given address, but it only gets written to core 1's cache and then "scheduled" to be written out to main memory. Meanwhile, later core 2 tries to read that address, it's not in its cache, so it pulls from main memory before core 1's cache has flushed. As far as core 2 is concerned, the write happened after it read from the address even though physically the write finished in core 1 before core 2's read instruction might have even started.
A memory barrier tells the hardware to ensure that reads-before is also "happens-before" (or after) a given writen to the same address. It's often (but not always) a cache and memory synchronization across cores.
I found Fedora Pikus's cppcon 2017 presentation [1] to be informative, and Michael Wong's 2015 presentation [0] filled in some of the gaps.
C++, being a generic language for many hardware implementations, provides a lot more detailed concepts for memory ordering [2], which is important for hardwares that have more granularity in barrier types that what most people are used to with x86-derived memory models.
[0]: https://www.youtube.com/watch?v=DS2m7T6NKZQ
[1]: https://www.youtube.com/watch?v=ZQFzMfHIxng
[2]: https://en.cppreference.com/w/cpp/atomic/memory_order.html
[1] https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
If you can stay in user space, or stay in kernel space, that is likely to be better performance than going back and forth.
This is why sendfile is great; rather than storage -> kernel memory -> user memory -> kernel memory -> network, you get storage -> kernel memory -> network. That's two less copies, and fewer context switches.
https://en.wikipedia.org/wiki/Microkernel
There are definitely user-land TCP/IP implementations, thread implementations (Go's being particularly notable) and even file systems (FUSE).
You're 100% right that there are plenty of other considerations, often positive for lifting things out, like minimization of ring 0 attack surface.