Without the futex, it's futile
h4x0r.org
h4x0r.org
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!
In that case, why not just say, ideally it would be 256K words, or whatever?
The signaling of multiple events is implemented efficiently with atomic bit set and bit clear operations, which are supported since Intel 80386 in 1985, so they are available in all Intel/AMD CPUs, and they are also available in 64-bit Arm CPUs starting with Armv8.2-A, since Cortex-A55 & Cortex-A75, in 2017-2018 (in theory the atomic bit operations were added in Armv8.1-A, but there were no consumer CPUs with that ISA).
With atomic bit operations, each thread signals its event independently of the others and there are no waiting loops. The monitoring thread can determine very fast the event with the highest priority using the LZCNT (count leading zeroes) or equivalent instructions, which is also available on all modern Arm-based or Intel/AMD CPUs.
When a futex is used to implement waiting for multiple events, despite not having proper support in the kernel, the thread that sets its bit to signal an event must also execute a FUTEX_WAKE, so that the monitoring thread will examine the futex value. Because the atomic bit operations are fetch-and-OP operations, like fetch-and-add or atomic exchange, the thread that signals an event can determine whether the previous event signaled by it has been handled or not by the monitoring thread, so it can act accordingly.
So currently on Linux you are limited to waiting for up to 32 events. The number of events can be extended by using a multi-level bitmap, but then the overhead increases significantly. Using a 64-bit futex value would have been much better.
In theory compare-and-swap or the equivalent instruction pair load-exclusive/store-conditional are more universal, but in practice they should be avoided whenever high contention is expected. The high performance algorithms for accessing shared resources are all based on using only fetch-and-add, atomic exchange, atomic bit operations and load-acquire/store-release instructions.
This fact has forced the Arm company to correct their mistake from the first version of the 64-bit ARM ISA, where there were no atomic read-modify-write operations, so they have added all such operations in the first revision of the ISA, i.e. Armv8.1-A.
> This fact has forced ... there were no atomic read-modify-write operations, so they have added all such operations in the first revision of the ISA, i.e. Armv8.1-A.
I'm not sure if you meant for these two paragraphs to be related, but asking too make sure:
- Isn't compare-and-swap (CMPXCHG on x86) also read-modify-write, which in the first quoted paragraph you mention is slow?
- I think I've benchmarked LOCK CMPXCHG vs LOCK OR before, with various configurations of reading/writing threads. I was almost sure it was going to be an optimization, and it ended up being inobservable. IIRC, some StackOverflow posts lead me to the notion that LOCK OR still needs to acquire ownership of the target address in memory (RMW). Do you have any more insights? Cases where LOCK OR is better? Or should I have used a different instruction to set a single bit atomically?As CAS has become more and more important as the world has scaled out, hardware companies have been more willing to favor "performance" in the cost / performance tradeoff. Meaning, it shouldn't surprise you if uncontended CAS as fast as a fetch-and-or, even if the later is obviously a much simpler operation logically.
But hardware platforms are a very diverse place.
Generally, if you can design your algorithm with a load-and-store, there's a very good chance you're going to deal with contention much better than w/ CAS. But, if the best you can do is use load-and-store but then have a retry loop if the value isn't right, that probably isn't going to be better.
For instance, I have a in-memory debugging "ring buffer" that keeps an "epoch"; threads logging to the ring buffer fetch-and-add themselves an epoch, then mod by the buffer size to find their slot.
Typically, the best performance will happen when I'm keeping one ring buffer per thread-- not too surprising, as there's no contention (but impact of page faults can potentially slow this down).
If the ring buffer is big enough that there's never a collision where a slow writer is still writing when the next cycle through the ring buffer happens, then the only contention is around the counter, and everything still tends to be pretty good, but the work the hardware has to do around syncing the value will 100% slow it down, despite the fact that there is no retries. If you don't use a big buffer, you have to do something different to get a true ring buffer, or you can lock each record, and send the fast writer back to get a new index if it sees a lock. The contention still has the effect of slowing things down either way.
The worst performance will come with the CAS operation though, because when lots of threads are debugging lots of things, there will be lots of retries.
But, last I checked (the last release, early last year) MUSL still does not provide a 128 bit version, which is disappointing, and hopefully the AVX related semantics changes will encourage them to add it? :)
What matters is where the designers of the system in question got their inspiration. If they learned it from Windows, they're aping Windows. If they invented it independently, they're not imitating anyone at all.
[0] https://lore.kernel.org/all/414e292195d720c780fab2781c749df3... [1] https://blog.linuxplumbersconf.org/2013/ocw/system/presentat...
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.
https://github.com/digital-fabric/uringmachine/blob/main/ext...
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.
The correct way to teach material at the collegiate level is to teach it correctly. Useful lies and omissions are for grade school. Where material is simplified for narrative clarity, it should be in a framing that immediately points to the materials for the more fully correct information.
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.
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...
Yes, this is exactly what's done. The queue node is an declared as a local variable in kernel code, i.e. on the kernel stack, and its address is passed to the wait function which links it into the waitqueue and then blocks in the scheduler.
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.
While it could be useful to have a "fast" variation that offers no guarantee at all, what you would end up with (because people are vain) is that too may people would use those instead "because perf", even though the actual usage is not performance critical, and have code that breaks whenever the compiler or platform changes.
For many other languages, I'd agree with '99%', but in the case of c++, performance is one of the main reasons it's still used, so I doubt the number is nearly that high.
With hindsight, I'd say that std::unordered_map is fine for what it is, but there are a lot of cases where it's really not suitable due to having a dynamic allocation for each element and the resulting lack of cache locality, and because of that many people have to go looking elsewhere for a usable hash map. There are good reasons why we have both std::vector and std::list.
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).
That is suppose we have two std::unordered_map<Goose> labelled A and B, and we put a particular Goose in A, later we get a reference to it, and we might, or might not, move it to B, but it definitely still exists. Do you need that? (As I understand it this is in fact what you get in std::unordered_map today)
Or for your purposes is it enough that it works only so long as the goose we're referring to is in A still and if we moved it out of A then it's fine that the reference is invalidated ?
For me it is usually when I need a multi indexed map where I use a fast map of pointers for the fast access and unordered_map both to keep the object alive and as a secondary access key.
Really I should use boost intrusive or boost multiindex, but these days I value the implementation simplicity in many cases, even if I have to keep the indices in sync myself
Map<shared_ptr<obj>> with weak_ptr probably is the best general solution. If the object decided to delete itself the weakptr will be set to null.
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
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)
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.
No idea what you mean by "builtin locks".
For example, the best baseline at the time futexes were introduced would have been MS's CRITICAL_SECTION, which was:
- Builtin in the sense that it shipped with the OS and part of that OS's standard library.
- Not a kernel call except on slow paths.
Prior to futexes, LinuxThreads already provided a lock implementation in pthread_mutex that was better than sysv, just worse than CRITICAL_SECTION, and worse than the futex-based one. But that old implementation already achieved the no-kernel-call fast path.
Also worth noting that today, the fastest widely available lock impl is MS's SRWLock, which obviously isn't futex based. So it's not like futexes are even the best
> So I was thinking more, "what does my language's standard library provide", which has mostly moved from sysv (or worse, sure) -> futex.
No, it hasn't. Before and after futexes, folks use pthread_mutex. Before and after futexes, pthread_mutex was faster than sysv. Before and after futexes, pthread_mutex was not based on sysv.
> 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?
Both ParkingLot and thin locks bottom out in a lock-and-condition-variable-per-thread implementation (or semaphore-per-thread if that's what the OS has). Then the lock and condition variable (or semaphore) may or may not use futexes.
> If so, how much of a win is that, really? I'm surprised it'd be worth the effort.
Portability. If you build a fast lock implementation on futexes, then it won't work on all OSes. You could get it to be portable to different OSes by virtue of the fact that the major OSes these days provide futex-like primitives, but even then, you'd be in a world of hurt because the details are different.
But ParkingLot can be built out of pthread_mutex/pthread_cond so it'll work well on any POSIX
> - thin locks (what JVMs use)
> - ParkingLot (a futex-like primitive that works entirely in userland and doesn’t require that the OS have futexes)
Worth nothing that somewhere under the hood, any modern lock is going to be using a futex (if supported). futex is the most efficient way to park on Linux, so you even want to be using it on the slow path. Your language's thread.park() primitive is almost certainly using a futex.
Sure that uses futex under the hood, but the point is, you use futexes on Linux because that’s just what Linux gives you
That's interesting, I'm more familiar with the Rust parking-lot implementation, which uses futex on Linux [0].
> Sure that uses futex under the hood, but the point is, you use futexes on Linux because that’s just what Linux gives you
It's a little more than that though, using a pthread_mutex or even thread.park() on the slow path is less efficient than using a futex directly. A futex lets you manage the atomic condition yourself, while generic parking utilities encode that state internally. A mutex implementation generally already has a built-in atomic condition with simpler state transitions for each thread in the queue, and so can avoid the additional overhead by making the futex call directly.
[0]: https://github.com/Amanieu/parking_lot/blob/739d370a809878e4...
No, it absolutely isn’t.
The dominant cost of parking is whatever happens in the kernel and at the microarchitectural level when your thread goes to sleep. That cost is so dominant that whether you park with a futex wait or with a condition variables doesn’t matter at all.
(Source: I’ve done that experiment to death as a lock implementer back when I maintained Jikes RVM’s thin locks and then again when I wrote and maintained ParkingLot.)
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.
I think TAOMPP is fine for what it is (teaching high-level concurrency concepts) and discussing OS-level implementation details would be out of place. The important thing it teaches is how to think about concurrency, not how to write your own synchronization primitives. E.g., the Peterson or bakery locks are useless in the real world (as the book admits), but understanding their proofs of correctness will help you reason about the concurrent algorithms you have to write yourself.
I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for.
Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing.
Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack.
* Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.
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).
There's a couple of other ways to achieve wait freedom on hazard pointer loads (protect) but they haven't been published so they're kind of moot.
"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. "
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.
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.
But of course consistency is only maintained if the algorithm is implemented correctly; if you are trying to robustly protect against a process randomly crashing, you might not want to rely on the correctness of that process (or that process randomly writing to shared memory on its way to a segfault).
In one discussion of supporting 64 bit integers for futexes, Linus suggested that you can just use 64 bit atomics in userspace, but only use 32 bits of that 64 bit integer for the futex, as long as the bits that change on a wakeup are in those 32 bits.
However, AFAICT, using mixed-size atomics in c/c++ is undefined behavior, although on most modern hardware it does work. But looking at the implementation of semaphore in glibc, that is exactly what it does. The semaphore uses a 64 bit integer, with the number of waiters in the high 32 bits, and the value of the semaphore in the low 32 bits, with userspace atomic operations on the whole 64 bit integer, but using just the low 32 bits for the futex.
Is my question is, does gcc specifically consider this defined behavior, or is it ok because the 32 bit access happens in a separate (kernel) process that isn't part of the same compilation, or is it actually undefined behavior in glibc?
Honestly I think if you really want to understand this topic, getting exposed to atomic memory ordering early on and writing simplified spin locks / SPSC queues is the way to go. You don’t even have to implement them correctly - the implementation just needs to teach you what could go wrong. The book operates at an abstraction level that makes it not very useful inexperienced students.
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??
Or C++ also adding std::atomic::wait which is basically a thin [1] wrapper over futex.
[1] implementations still manage to mess it up.
The advantage of futex provided by the kernel is ABI stability and cross process support.
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.
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.
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.
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?
[1] https://en.cppreference.com/w/c.html
[2] https://pubs.opengroup.org/onlinepubs/9699919799.2018edition...
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".
[1] https://cis.temple.edu/~giorgio/cis307/readings/futex.pdf
I can not give you thi final feedback at the moment, I only breefly looked through the articles for not.
The first ones are very accessible (given my prior lnowledge of lamport clocks and happens before as in Java memory model), the later ones I am currently not sure are very clear.
But are easier than the docs I used when first approached this topic in the past, like Documentation/memory-barriers.txt and the Doug Lea's texts.
for now
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).
Haven't ever heard of barriers as a counter-like primitive (sounds like a semaphore or CountDownLatch)
https://www.researchgate.net/publication/228824849_Memory_Ba...
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
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.
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.
The part of NICs address space is mapped to a process (control registers and memory rings), and whole driver just runs in your process without going through the kernel. Of course, it ignores usual stuff like firewalls, iptables, etc, but who cares when all you need is the lowest latency possible )
Like Microsoft's Apple's approach is slightly smaller (one byte not four) and over a decade later.