8 ms·

Without the futex, it's futile

306 points by eatonphil 1y ago

afr0ck 1y 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 1y 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 1y 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 1y 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 1y 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 1y 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).
        gpderetta 1y ago
        You are of course completely right. In fact sometimes I wish that the kernel would do slightly more with the memory location, like optionally reserving a bit to show the empty/non empty state of the queue: the kernel should be able to keep it up to date cheaply as part of the wait/wake operations while is more complicated for userspace.
    - immibis 1y ago
      This sort of thing can be implemented in the kernel without special hardware operations by adding the thread to the wake list, then suspending the thread, then checking the value. If the value has changed, undo that and return, else just return leaving the thread suspended. Special hardware multi-atomic instructions are not required, but the details are very dependent on how kernel's thread switching is designed.
- viega 1y 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 1y 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 1y 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 1y 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 1y 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).
- ajross 1y 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 1y 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 1y ago
    If this is ad hoc solution, what's the "right" approach?
    - ajross 1y 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/ https://lwn.net/Articles/823513/
mmastrac 1y 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. EDIT: TIL about futex2 as well: https://docs.kernel.org/userspace-api/futex2.html https://docs.kernel.org/userspace-api/futex2.html
- EdSchouten 1y ago
  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. https://www.oreilly.com/library/view/solaristm-internals-core/0130224960/0130224960_ch03lev1sec7.html https://www.oreilly.com/library/view/solaristm-internals-cor... https://www.bsdcan.org/2012/schedule/attachments/195_locking.pdf https://www.bsdcan.org/2012/schedule/attachments/195_locking...
  - senderista 1y ago
    This is a really dumb question from someone unfamiliar with the kernel's futex implementation, so bear with me. In userspace locks (e.g. in parking_lot), wait queues can be threaded through nodes allocated on the stack of each waiting thread, so no static or dynamic allocation of wait queue nodes is necessary. Is it possible to allocate wait queue nodes on the kernel stacks of waiting threads as well?
Normal_gaussian 1y ago
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 1y 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 1y 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…
nromiun 1y ago
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.
- Jtsummers 1y ago
  Most things can be moved into user space. https://en.wikipedia.org/wiki/Microkernel https://en.wikipedia.org/wiki/Microkernel
- viega 1y ago
  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 1y 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 1y 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.
- whstl 1y 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!
wizerno 1y ago
Another great read on futexes is Ulrich Drepper’s paper "Futexes Are Tricky" [1]. [1] https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
mwcampbell 1y 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 1y 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 1y ago
    SRW lock uses the WaitOnAddress primitives nowadays, not keyed events.
    - jstarks 1y ago
      Well, technically both WaitOnAddress and SRWLOCK use the same "wait/wake by thread ID" primitive. WaitOnAddress uses a hash table to store the thread ID to wake for an address, whereas SRWLOCK can just store that in the SRWLOCK itself (well, in an object on the waiter's stack, pointed to by the SRWLOCK).
  - Sesse__ 1y ago
    What _is_ the big difference between CRITICAL_SECTION and a futex, really? I always assumed that futexes were meant to be pretty similar to CRITICAL_SECTION (mostly-userspace locks that didn't have fatal spinning issues on contention).
    - gpderetta 1y ago
      A critical_section is a mutex, a futex is a general synchronization primitive (a critical_section might be implemented on a more general primitive of course, I'm not a Windows expert).
Joker_vD 1y ago
> 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 1y 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?
  - dragontamer 1y 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 1y ago
jauntywundrkind 1y ago
Windows gained a WaitForMultipleObjects, which Linux 5.16 (end 2021) aped with a new Futex2. https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv 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-NUMA-Small-Futex https://www.phoronix.com/news/FUTEX2-Improvements-Linux-6.16 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 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 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 https://www.phoronix.com/news/Linux-6.7-Locking-FUTEX2
- gpderetta 1y ago
  Futex has nothing to do with WFMO. Futex is equivalent to keyed events. The linux equivalent of WFMO is select/poll/epoll.
  - jauntywundrkind 1y 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.
smallstepforman 1y 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)?
- the_mitsuhiko 1y 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.
  - krackers 1y ago
    i mean you can use semaphores to implement condition variables, but it's extremely tricky to the point where you've got to be Mike Burrows in order to do it right [1] (in fact, that's how it's done in the nsync library, as a fallback when every faster option is unavailable). [1] http://birrell.org/andrew/papers/ImplementingCVs.pdf http://birrell.org/andrew/papers/ImplementingCVs.pdf
    - the_mitsuhiko 1y ago
      > i mean you can use semaphores You absolutely can use semaphores for it, but the benefits of a benaphore would not work with when you build a condition variable with it. The wait on the CV would need to go through the kernel.
- garaetjjte 1y 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.)
reinhardt1053 1y ago
So what's recommended as a better alternative to The Art of Multiprocessor Programming?
- belter 1y ago
  These two: https://man7.org/tlpi/ https://man7.org/tlpi/ https://marabos.nl/atomics/ https://marabos.nl/atomics/
- Jtsummers 1y 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 1y 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.
  - viega 1y 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.
  - pjmlp 1y ago
    Although a bit outdated, Java Concurrency in Practice is also a very good one, written by Brian Goetz, before he became one of the leading architects on Java.
garaetjjte 1y 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.
- viega 1y 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).
- inetknght 1y 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 1y 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.
  - simonask 1y ago
    The concern about state consistency applies to all error conditions, not just those that occur while holding a mutex lock. It doesn’t matter if multiple threads are running or just one - the process could be in the middle of updating a memory-mapped file, or communicating with another process via shared memory, or a thousand other things. Ensuring consistency is excruciatingly hard. If it truly matters, the best we have is databases.
avodonosov 1y ago
Can anyone suggest a good explanation of memory barriers?
- inetknght 1y 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. [0]: https://www.youtube.com/watch?v=DS2m7T6NKZQ https://www.youtube.com/watch?v=DS2m7T6NKZQ [1]: https://www.youtube.com/watch?v=ZQFzMfHIxng https://www.youtube.com/watch?v=ZQFzMfHIxng [2]: https://en.cppreference.com/w/cpp/atomic/memory_order.html https://en.cppreference.com/w/cpp/atomic/memory_order.html
  - avodonosov 1y ago
    Than you.
- junon 1y 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).
supernetworks 1y ago
A particularly tricky exploit in the linux futex implementation from 2014, by Pinkie Pie, https://issues.chromium.org/issues/40079619 https://issues.chromium.org/issues/40079619 "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. "
f1shy 1y 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 1y ago
  Yeah, I don't love the mobile experience. I'll try to get that fixed soon, thanks.
ptspts 1y ago
Half of the source code is colored very-light-on-white, which is impossible to read. I'm using Chrome on Android.
- viega 1y 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.
senderista 1y ago
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.
- j_seigh 1y ago
  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.
  - senderista 1y ago
    Maybe you mean ticket locks? That’s kind of the practical version of the bakery algorithm. It’s not the same because ticket locks require fetch-and-add (or its emulation over another atomic RMW like CAS), while the bakery algorithm uses only reads and writes (which makes it impractical). Using a futex to allow ticket locks to block in the kernel does have a thundering herd problem. Fortunately you can do “smart sleeps” by measuring the time elapsed since the last wakeup and the change in the turn counter since then, and using that to estimate the time until the current thread’s turn (we don’t want to block the queue by oversleeping, so sleep for half of that estimate, then redo the estimate again, etc). (The same logic can be applied to spinning during the waiter’s timeslice, to avoid unnecessary cache coherence traffic.) I assume you’re referring to Guy Blelloch’s work on wait-free hazard pointers? That’s very cool although I doubt it’s solving a practical problem. The practical issue with hazard pointers is the StoreLoad barrier on the read side (which can be moved to the GC side via membarrier(2) etc).
sn9 1y ago
Mara Bos' Rust Atomics and Locks has a section on futexes [0]. [0] https://marabos.nl/atomics/os-primitives.html#linux https://marabos.nl/atomics/os-primitives.html#linux
hardwaresofton 1y ago
Where does everyone browse the C standard library, posix library, and separately glibc? 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?
- gpderetta 1y ago
  cppreference [1] has also entries for the C standard library. POSIX/SuS is directly available from opengroup [2]. glibc is better browsed from local man pages, or for a more organic discussion, info pages. Searching 'man function-name' also usually works. [1] https://en.cppreference.com/w/c.html https://en.cppreference.com/w/c.html [2] https://pubs.opengroup.org/onlinepubs/9699919799.2018edition/ https://pubs.opengroup.org/onlinepubs/9699919799.2018edition...
  - hardwaresofton 1y ago
    Thanks! Yeah CPP reference is what I tend to find on the internet, but quite surprised there isn't something a bit more "modern" that combines all these. Searching also revealed some good university guides, the standards, ETC -- just very surprising that people doing day to day work with C are fine with that tooling-wise, though of course people have jump-to-definition so maybe reading header files is "good enough".
zools 1y ago
[dead]
pizlonator 1y ago
> 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)
- aktau 1y ago
  Thanks for that reference. Do you know if the JVM still uses thin locks? Did they migrate to thin locks? I ask because I found a 9 year old reference with a JVM calling futex: https://stackoverflow.com/questions/32262946/java-periodically-hangs-at-futex-and-very-low-io-output https://stackoverflow.com/questions/32262946/java-periodical....
  - pizlonator 1y ago
    OpenJDK has used thin locks since back when it was called HotSpot. The fact that the JVM is hanging in futexes doesn’t meant anything for the purpose of this discussion. Futexes are _the_ OS locking primitive on Linux so I would expect modern JVM thin locks to bottom out in a futex syscall. That doesn’t mean that the JVM is “using” futexes in the sense of the original post.
- viega 1y ago
  If you baseline against what people do when they skip builtin locks, then yes, that's spot on. Though, I was more coming from the assumption that most people are really learning about the primitives that are going to be there, and they're going to be reaching for in the real world. So I was thinking more, "what does my language's standard library provide", which has mostly moved from sysv (or worse, sure) -> futex. It's true though, there have been some recent defections to custom waiting. I haven't looked at any of the well-used parking lot implementations in any depth. It's a bit of a tangent, but obviously, such constructs can be done completely in userland if you're running your own scheduler. But I assume most of them are not, so if they're not using a futex, I'd assume they're instead writing to a blocking FD and managing their own queues? If so, how much of a win is that, really? I'm surprised it'd be worth the effort.
thayne 1y ago
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?
squirrellous 1y ago
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.

306 points by eatonphil 1y 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 1y 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 1y 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 1y 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 1y 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 1y 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).
        gpderetta 1y ago
        You are of course completely right. In fact sometimes I wish that the kernel would do slightly more with the memory location, like optionally reserving a bit to show the empty/non empty state of the queue: the kernel should be able to keep it up to date cheaply as part of the wait/wake operations while is more complicated for userspace.
  - immibis 1y ago
    This sort of thing can be implemented in the kernel without special hardware operations by adding the thread to the wake list, then suspending the thread, then checking the value. If the value has changed, undo that and return, else just return leaving the thread suspended. Special hardware multi-atomic instructions are not required, but the details are very dependent on how kernel's thread switching is designed.
viega 1y 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 1y 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 1y 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 1y 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 1y 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).
ajross 1y 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 1y 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 1y ago
  If this is ad hoc solution, what's the "right" approach?
  - ajross 1y 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/ https://lwn.net/Articles/823513/

mmastrac 1y 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. EDIT: TIL about futex2 as well: https://docs.kernel.org/userspace-api/futex2.html https://docs.kernel.org/userspace-api/futex2.html

EdSchouten 1y ago
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. https://www.oreilly.com/library/view/solaristm-internals-core/0130224960/0130224960_ch03lev1sec7.html https://www.oreilly.com/library/view/solaristm-internals-cor... https://www.bsdcan.org/2012/schedule/attachments/195_locking.pdf https://www.bsdcan.org/2012/schedule/attachments/195_locking...
- senderista 1y ago
  This is a really dumb question from someone unfamiliar with the kernel's futex implementation, so bear with me. In userspace locks (e.g. in parking_lot), wait queues can be threaded through nodes allocated on the stack of each waiting thread, so no static or dynamic allocation of wait queue nodes is necessary. Is it possible to allocate wait queue nodes on the kernel stacks of waiting threads as well?

Normal_gaussian 1y ago

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 1y 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 1y 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…

nromiun 1y ago

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.

Jtsummers 1y ago
Most things can be moved into user space. https://en.wikipedia.org/wiki/Microkernel https://en.wikipedia.org/wiki/Microkernel
viega 1y ago
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 1y 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 1y 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.
whstl 1y 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!

wizerno 1y ago

Another great read on futexes is Ulrich Drepper’s paper "Futexes Are Tricky" [1]. [1] https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf

mwcampbell 1y 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 1y 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 1y ago
  SRW lock uses the WaitOnAddress primitives nowadays, not keyed events.
  - jstarks 1y ago
    Well, technically both WaitOnAddress and SRWLOCK use the same "wait/wake by thread ID" primitive. WaitOnAddress uses a hash table to store the thread ID to wake for an address, whereas SRWLOCK can just store that in the SRWLOCK itself (well, in an object on the waiter's stack, pointed to by the SRWLOCK).
- Sesse__ 1y ago
  What _is_ the big difference between CRITICAL_SECTION and a futex, really? I always assumed that futexes were meant to be pretty similar to CRITICAL_SECTION (mostly-userspace locks that didn't have fatal spinning issues on contention).
  - gpderetta 1y ago
    A critical_section is a mutex, a futex is a general synchronization primitive (a critical_section might be implemented on a more general primitive of course, I'm not a Windows expert).

Joker_vD 1y ago

> 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 1y 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?
- dragontamer 1y 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 1y ago

jauntywundrkind 1y ago

Windows gained a WaitForMultipleObjects, which Linux 5.16 (end 2021) aped with a new Futex2. https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv https://www.phoronix.com/news/Linux-5.16-sys_futex_waitv 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-NUMA-Small-Futex https://www.phoronix.com/news/FUTEX2-Improvements-Linux-6.16 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 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 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 https://www.phoronix.com/news/Linux-6.7-Locking-FUTEX2

gpderetta 1y ago
Futex has nothing to do with WFMO. Futex is equivalent to keyed events. The linux equivalent of WFMO is select/poll/epoll.
- jauntywundrkind 1y 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.

smallstepforman 1y 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)?

the_mitsuhiko 1y 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.
- krackers 1y ago
  i mean you can use semaphores to implement condition variables, but it's extremely tricky to the point where you've got to be Mike Burrows in order to do it right [1] (in fact, that's how it's done in the nsync library, as a fallback when every faster option is unavailable). [1] http://birrell.org/andrew/papers/ImplementingCVs.pdf http://birrell.org/andrew/papers/ImplementingCVs.pdf
  - the_mitsuhiko 1y ago
    > i mean you can use semaphores You absolutely can use semaphores for it, but the benefits of a benaphore would not work with when you build a condition variable with it. The wait on the CV would need to go through the kernel.
garaetjjte 1y 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.)

reinhardt1053 1y ago

So what's recommended as a better alternative to The Art of Multiprocessor Programming?

belter 1y ago
These two: https://man7.org/tlpi/ https://man7.org/tlpi/ https://marabos.nl/atomics/ https://marabos.nl/atomics/
Jtsummers 1y 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 1y 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.
- viega 1y 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.
- pjmlp 1y ago
  Although a bit outdated, Java Concurrency in Practice is also a very good one, written by Brian Goetz, before he became one of the leading architects on Java.

garaetjjte 1y 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.

viega 1y 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).
inetknght 1y 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 1y 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.
- simonask 1y ago
  The concern about state consistency applies to all error conditions, not just those that occur while holding a mutex lock. It doesn’t matter if multiple threads are running or just one - the process could be in the middle of updating a memory-mapped file, or communicating with another process via shared memory, or a thousand other things. Ensuring consistency is excruciatingly hard. If it truly matters, the best we have is databases.

avodonosov 1y ago

Can anyone suggest a good explanation of memory barriers?

inetknght 1y 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. [0]: https://www.youtube.com/watch?v=DS2m7T6NKZQ https://www.youtube.com/watch?v=DS2m7T6NKZQ [1]: https://www.youtube.com/watch?v=ZQFzMfHIxng https://www.youtube.com/watch?v=ZQFzMfHIxng [2]: https://en.cppreference.com/w/cpp/atomic/memory_order.html https://en.cppreference.com/w/cpp/atomic/memory_order.html
- avodonosov 1y ago
  Than you.
junon 1y 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).

supernetworks 1y ago

A particularly tricky exploit in the linux futex implementation from 2014, by Pinkie Pie, https://issues.chromium.org/issues/40079619 https://issues.chromium.org/issues/40079619 "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. "

f1shy 1y 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 1y ago
Yeah, I don't love the mobile experience. I'll try to get that fixed soon, thanks.

ptspts 1y ago

Half of the source code is colored very-light-on-white, which is impossible to read. I'm using Chrome on Android.

viega 1y 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.

senderista 1y ago

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.

j_seigh 1y ago
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.
- senderista 1y ago
  Maybe you mean ticket locks? That’s kind of the practical version of the bakery algorithm. It’s not the same because ticket locks require fetch-and-add (or its emulation over another atomic RMW like CAS), while the bakery algorithm uses only reads and writes (which makes it impractical). Using a futex to allow ticket locks to block in the kernel does have a thundering herd problem. Fortunately you can do “smart sleeps” by measuring the time elapsed since the last wakeup and the change in the turn counter since then, and using that to estimate the time until the current thread’s turn (we don’t want to block the queue by oversleeping, so sleep for half of that estimate, then redo the estimate again, etc). (The same logic can be applied to spinning during the waiter’s timeslice, to avoid unnecessary cache coherence traffic.) I assume you’re referring to Guy Blelloch’s work on wait-free hazard pointers? That’s very cool although I doubt it’s solving a practical problem. The practical issue with hazard pointers is the StoreLoad barrier on the read side (which can be moved to the GC side via membarrier(2) etc).

sn9 1y ago

Mara Bos' Rust Atomics and Locks has a section on futexes [0]. [0] https://marabos.nl/atomics/os-primitives.html#linux https://marabos.nl/atomics/os-primitives.html#linux

hardwaresofton 1y ago

Where does everyone browse the C standard library, posix library, and separately glibc? 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?

gpderetta 1y ago
cppreference [1] has also entries for the C standard library. POSIX/SuS is directly available from opengroup [2]. glibc is better browsed from local man pages, or for a more organic discussion, info pages. Searching 'man function-name' also usually works. [1] https://en.cppreference.com/w/c.html https://en.cppreference.com/w/c.html [2] https://pubs.opengroup.org/onlinepubs/9699919799.2018edition/ https://pubs.opengroup.org/onlinepubs/9699919799.2018edition...
- hardwaresofton 1y ago
  Thanks! Yeah CPP reference is what I tend to find on the internet, but quite surprised there isn't something a bit more "modern" that combines all these. Searching also revealed some good university guides, the standards, ETC -- just very surprising that people doing day to day work with C are fine with that tooling-wise, though of course people have jump-to-definition so maybe reading header files is "good enough".

zools 1y ago

[dead]

pizlonator 1y ago

> 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)

aktau 1y ago
Thanks for that reference. Do you know if the JVM still uses thin locks? Did they migrate to thin locks? I ask because I found a 9 year old reference with a JVM calling futex: https://stackoverflow.com/questions/32262946/java-periodically-hangs-at-futex-and-very-low-io-output https://stackoverflow.com/questions/32262946/java-periodical....
- pizlonator 1y ago
  OpenJDK has used thin locks since back when it was called HotSpot. The fact that the JVM is hanging in futexes doesn’t meant anything for the purpose of this discussion. Futexes are _the_ OS locking primitive on Linux so I would expect modern JVM thin locks to bottom out in a futex syscall. That doesn’t mean that the JVM is “using” futexes in the sense of the original post.
viega 1y ago
If you baseline against what people do when they skip builtin locks, then yes, that's spot on. Though, I was more coming from the assumption that most people are really learning about the primitives that are going to be there, and they're going to be reaching for in the real world. So I was thinking more, "what does my language's standard library provide", which has mostly moved from sysv (or worse, sure) -> futex. It's true though, there have been some recent defections to custom waiting. I haven't looked at any of the well-used parking lot implementations in any depth. It's a bit of a tangent, but obviously, such constructs can be done completely in userland if you're running your own scheduler. But I assume most of them are not, so if they're not using a futex, I'd assume they're instead writing to a blocking FD and managing their own queues? If so, how much of a win is that, really? I'm surprised it'd be worth the effort.

thayne 1y ago

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?

squirrellous 1y ago

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.