9 ms·
You could have invented futexes
- rektide 3y agoOmg the multi-threaded code examples are amazing. The active line is highlighted. Amazingly illuminating, so so good.
- moonchild 3y agoQuestion: do people find that sort of animation easier to grok than showing the interleaving visually, as I do at https://outerproduct.net/boring/2023-01-27_trans-locks.html#table https://outerproduct.net/boring/2023-01-27_trans-locks.html#...? I prefer the latter, because it lets me see everything at once, but may switch to the former presentation style if other people prefer it.
- jesse__ 3y agoFWIW coming from some random stranger on the internet, I like the animations. They're short enough that even though all the information isn't on the screen at once, I can remember/interpret the whole thing after it's run once. I could also imagine for demonstrating longer-running bugs (of more than just a few instructions) a user-controlled slider might be nice.
- taeric 3y agoThe answer is almost certainly yes. For both directions of the question. Few things have a single visualization that is the best.
- TechBro8615 3y agoNot that it would apply in this particular case, but my all-time favorite visualization of concurrency is this 2016 blog post called "Visualizing Concurrency in Go" [0]. So good. [0] https://divan.dev/posts/go_concurrency_visualize/ https://divan.dev/posts/go_concurrency_visualize/
- rektide 3y agoUsing time to represent time is a pretty helpful & intuitive strategy, very nicely on display in this example & the submission. It does require some waiting around to see how things develop (versus the at-a-glance approach) but it really feels so very graspable & clear to me.
- tavianator 3y agoI think for anything more complicated than my examples, animations would be worse than your explicit interleavings. That said, I don't really think interleavings are the best way to show weak memory effects either, since they give the impression that there is some global order that is the same in all threads. I'm not sure how to do a nice visualization of the reality though. One idea: show the interleaving of atomic operations, and based on that, show what values each other read might see. Maybe even let the user change the interleaving by dragging stuff around, and show how it changes which other values can be observed.
- RustyRussell 3y agoOh, blast from the past! The original futex code used physical addresses, and pinned the page, which is simple: if you can share memory somehow, you can use a futex. Of course, most people use pthreads and increasingly the idea of a Linux userspace locking primitive gave way to a glibc-pthread accelerator...
- cperciva 3y agoif you can share memory somehow, you can use a futex. If you can share memory and you have coherent caches you can use a futex. (In particular, many embedded systems have weaker cache coherency than x86, so "it works on my laptop" is not enough!) In the worst case, without coherent caches you may need to do a cache shootdown IPI, which means entering the kernel anyway.
- RustyRussell 3y agoUm, does Linux run on such systems? There's a broad assumption that atomic ops work efficiently (or at least, that was true when I dropped out 7 years ago...)
- cperciva 3y agoI'm not the right person to ask about this, but some ARM systems definitely have weaker coherence than x86 -- in FreeBSD we have a whole bunch of memory barrier primitives which compile away to nothing on x86 because they exist only for weaker platforms. I have a vague recollection that it's something to do with whether caches snoop the memory bus for reads of lines they "own" but I could be mistaken. Whatever it was, there were cases where buggy code meant that a core could read a stale value from memory for multiple seconds after another core wrote to the same address.
- chc4 3y agoThe terminology is that x86 has a Total Store Order memory model, while ARM doesn't; acquire operations on x86 imply that all relaxed store operations on the core that released are also visible to the reader, which is not true on ARM unless the released value has a data dependency, or until you execute a memory barrier. ARM still has a coherent cache, however. Basically every modern OS and program depends on having a coherent data cache (though ARM doesn't keep i-cache and d-cache coherent with each other, which basically only comes in play with self-modifying code)
- jesse__ 3y agoThanks for writing this up -- I'll be coming back to it when I need to implement mutexes. As an aside -- it would be interesting to see what the analog on Windows is. I know from experience the platform-provided mutex implementation on win32 is horrendously slow, and it would be nice to know if it's even possible on that platform to implement a 'real' mutex that doesn't suck. Anyone know of a reference implementation of mutexes on Windows?
- johncolanduoni 3y agoit’s called WaitOnAddress: https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96265 https://devblogs.microsoft.com/oldnewthing/20170601-00/?p=96...
- atq2119 3y agoThat blog slightly misrepresents futex. Or perhaps it's outdated. It's written as if futexes can only be used with a 1/0/negative protocol, but that's not true. The values used are up to user space.
- firstlink 3y agoIndeed, in another article Chen actually explicitly claims that msft invented (what we understand to be) futexes and that Linux switched their futex syscall from semaphores to futexes by copying windows. It is truly a wildly incorrect and implausible view of history.
- mastax 3y agoI don't know if this is the "best" recommendation, but it's the one I know. https://crates.io/crates/parking_lot https://crates.io/crates/parking_lot IIRC the only platform specific part is the thread parking logic, so I'd assume it's pretty fast on Windows in the common case.
- thayne 3y agoThe rust standard library has incorporated a lot of parking_lot. On platforms that have futex-like primatives (like linux and windows) it uses those. But I think it uses a parking lot implementation if the OS doesn't support such an operation.
- Animats 3y agoIt's more like UNIX and Linux being way behind on threading technology. User space mutexes were in QNX over two decades ago. And on the UNIVAC 1108 half a century ago.[1] Here's a implementation from 1972, by John Walker. . DIJKSTRA P FUNCTION . . . LA,U A0,<QUEUE> . LMJ X11,P . <RETURN> X5 DESTROYED . P* TS QHEAD,A0 LOCK THE QUEUE LX X5,QN,A0 LOAD QUEUE COUNT ANX,U X5,1 BACK UP THE COUNT SX X5,QN,A0 REPLACE THE COUNT IN THE QUEUE TN X5 DO WE NEED TO DEACTIVATE HIM ? J PDONE NO. SKIP DEACTIVATION ON TSQ=0 LX X5,QHL,A0 LOAD BACK LINK OF QUEUE SX X5,QHL,X4 PUT INTO BACK LINK OF ACTIVITY SX X4,QFL,X5 CHAIN ACTIVITY TO LAST ACTIVITY SA A0,QFL,X4 CHAIN HEAD TO NEW ACTIVITY SX X4,QHL,A0 MAKE THE NEW ACTIVITY LAST ON QUEUE CTS QHEAD,A0 RELEASE PROTECTION ON QUEUE HEAD SCHDACT* DACT$ . DEACTIVATE PROCESS OFF ON TSQ C$TSQ QHEAD,A0 WAIT FOR C$TSA OFF J 0,X11 RETURN AFTER ACTIVATION . PDONE CTS QHEAD,A0 UNLOCK THE QUEUE J 0,X11 RETURN And that followed Djykstra's paper, published in Dutch in the late 1960s. [1] https://www.fourmilab.ch/documents/univac/fang/ https://www.fourmilab.ch/documents/univac/fang/
- gpderetta 3y agoYou can fast path an userspace mutex (or any blocking primitive) on top of pretty much any blocking system call (semaphores, pipes, poll, sigwait, whatever). The nifty thing with futexes and hashed waitqueues in general is that they consume kernel resources only when actively being waited on. It is not obvious (but certainly possible) that's the case with the UNIVAC implementation above.
- tialaramex 3y agoYup. The fast path trick was well known, BeOS made a big deal of its Benaphore, which is exactly this trick with its OS semaphore. Exactly as you said, the problem with a Benaphore is that if your program wants 100 Benaphores, you're creating 100 OS-wide semaphores, even if your program is literally never experiencing contended locking, that's 100x scarce OS resource used up just in case. If you ask for one million Benaphores, the program won't run, the entire OS only allows (IIRC) 65536 total. Putting together this fast path + the wait queue idea = a futex, very fast yet very cheap.
- kazinator 3y agoHashing an address to map to a wait queue was done by early Unix kernels. The address was called a "wait channel" (wchan for short). There was no object declared at the address; any object or function could be waited on. The ps utility still has a field called "wchan" you can select, which tells you where the process is waiting. Hashing is basically way to add properties to an object (identified by an address) without physically extending the structure located at that address. We can give any address a wait queue, for instance. E.g. Javascript object properties are like this. If we have some futex object in Javascript, and give it a futex.waitQueue property, it's basically the same: the futex thing is hashed somehow to access that property. The main point of futexes is efficiency in the face of user/kernel separation. Futexes are intended to be used in a double-checked pattern, avoiding a call into the kernel. User space can check the state of the futex memory location and avoid calling wait. The wait operation in the kernel will do the same check again (this time atomically) possibly avoiding the wait.. If that weren't done, there would be a lost-wakeup problem in the use of mutexes. Futexes are fast in the uncontended case; hence the F. Fast means in the context of the expensive user/kernel boundary. You would never need futexes without such a boundary; they are not used in the kernel. Futexes inside a single protection space are indeed a non-invention; the invention is the idea that something outside of the protected space can inspect the value and act on it.
- orf 3y ago> If we have some futex object in Javascript, and give it a futex.waitQueue property, it's basically the same: the futex thing is hashed somehow to access that property. I’m not sure that’s correct, it’s “waitQueue” that is hashed. In a super naive simple implementation the attributes are just a hash map.
- bullen 3y agoWhy write workarounds instead of simply using arrays of 64 byte atomic structures for your data? That way you avoid cache misses and cache invalidation at the same time. And your software can run at full speed across multiple threads/cores.
- throwawaylinux 3y agoBecause it's not always so simple to structure your solution in a way that's amenable to having multiple processors work on the data without cache conflicts. Locks are extremely common, they are not a "workaround" rather just another of many tools to control concurrency. Also, few or no CPUs can perform atomic operations on 64 bytes of memory without using transactional memory (which has its own drawbacks), and in any case atomic operations and cacheline alignment don't save you from cache misses and invalidations if CPUs operate on the same data.
- gpderetta 3y agoAlso futexes are not just for locks, but more generally are used for signaling.
- bullen 3y agoYou don't modify the entire 64 bytes at the same time. That's why you fill it with atomic variables that you can modify _without_ locking. You need the array to contain structures that fill the cache line to avoid invalidation when two cores write/read structures close to each other. When two cores write/read to/from the same atomic variable in the same structure you of course need to know what the consequences will be, but most of the time it will only result on gliches and not crashes... say if the position of a player is updated by the physics and incoming network at the same time and read by the render core... the player will glitch to some location that might be wrong for the other writing core so you have to make sure that is handled to not behave in a non playable way, but performance on the CPU is the _only_ bottleneck we will ever have and we're already there. You could also look at Javas concurrency package. It's mostly atomic.
- jiveturkey 3y agoApparently Solaris uses park() to the same effect. I can't readily find a history of either. Anyone know which came first, Solaris or Linux? In part I'm reacting to @Animats statement that UNIX is behind.
- defrost 3y agoBeing an old OS hacker of that day I was about for the release of both; Linux was 1991 - as a minimal monolithic single arch student level kludge made from studying SunOS API calls and the MINIX project. Solaris was 1993 .. a succusor to SunOS and a turn away from the SunOS BSD roots towards UNIX System V Release 4. Both Linux and Solaris had deep prior art roots in the "Unix-like" sphere, many ideas cropped up over there originally but only really gained traction somewhere else. ( Other ideas of that time, such as capability based permissions, never really took off until decades later )
- jiveturkey 3y agoSorry, I didn't mean when did Linux and Solaris first see light of day. I meant, when did the futex (linux) and park() (Solaris) functionality become available in both? Some Linux things have an [uncredited] history as a Solaris feature first.
- defrost 3y ago<doh> my bad, skimming too fast, reading too little. To the best of my recollection, with some links I see that back this: Futex appeared in Linux circa 2002 ( late kernel ver 2.5 series ), (Net) BSD _lwp_park() appeared circa 2009 but ... I have an inkling it popped up earlier in sources I don't have online access to right now (archived drives | tapes in a shed some distance away) This post 2000 era is right when I moved away from heavy Sun workstation usage and low level tinkering and into other domains.
- sgt 3y agoI got into both Linux and SunOS around 1996. At the time, I got the impression (perhaps correctly so) that Linux was a "play thing" and mostly good for small businesses, while SunOS was the only thing that would properly scale to the type of volume an Internet business could expect.
- alex-moon 3y agoI really loved the little UI element in this showing the concurrent executing paths as highlighted lines in the code (with soothing little transitions no less).
- sgt 3y agoSeems so simple but I haven't seen that before either. Novel
- fenaer 3y agoThere is a typo in the first code example, “memoy” instead of “memory”
- tavianator 3y agoFixed, thanks!
- compumike 3y agoJust a reminder that glibc / pthread has a known futex-related threading bug in the wild that has been open for three years: https://sourceware.org/bugzilla/show_bug.cgi?id=25847 https://sourceware.org/bugzilla/show_bug.cgi?id=25847 It was discussed here two years ago: https://news.ycombinator.com/item?id=24958504 https://news.ycombinator.com/item?id=24958504 But I only recently believe I ran into it in the wild when testing some high-concurrency multithreading code for several days. It would run a few hundred million operations successfully and then hang, CPU busy, on pthread_cond_wait().
- tavianator 3y agoI have been trying to come up with an efficient but simple and correct condition variable implementation based on futexes for the last couple days and it's surprisingly tricky.
- gpderetta 3y agoespecially if correct means fully POSIX conforming, including realtime scheduling, priority inheritance, cross process support, robust mutex support, cancellation, etc.