7 ms·
Finding the “second bug” in glibc’s condition variable
- ncmncm 4y agoSomeone should be very embarrassed about how they have handled this whole process. Surely code to operate condition variables correctly is in the public domain, that does not involve mitigations or stolen signals.
- gpderetta 4y agoIs there? There are multiple papers describing cond vars implementations. Many have been found to have errors after years. I'm sure the BSDs have posix cond vars implementations, but they won't use futexes but some BSD specific signalling primitive, and will likely have different scalability profiles than the one in gilibc, which has been tuned mostly for the needs of Red Hat, Oracle and other big Linux vendors.
- ajross 4y agoSkimming this, this isn't something glibc can do reliably. This has to be a kernel fix. The underlying FUTEX_OP operation is... obtuse. Futexes were originally designed for simple locking and semaphores, and only later extended to condition variables, and the result isn't pretty. (To be fair: it's a very hard problem on kernels that need to scale to hundreds of cores across many levels of memory interconnect.) Trying to fix this in userspace is just about tuning to try to suppress the underlying issues, and recovering cleanly when things break.
- jart 4y agoHow is this the kernel's fault? The article says "pthread_cond_signal() will signal on the wrong futex". Yes I understand futexes are tricky, but I don't see how they're broken.
- ajross 4y agoTo be clear: I'm not assigning "fault", I'm saying the design is flawed. The current futex abstraction forces userspace to do things like "pick a thread to wake up", which is inherently racy when viewed from outside the kernel. So yes, you have to fix this particular issue in glibc because the microbug is in glibc. But glibc shouldn't have tried to solve the problem in the first place. IPC is just really hard, we struggle with exactly this in Zephyr too (though we have mostly managed to avoid this particular kind of mistake as in an RTOS the kernel/API boundary is thinner), at a much smaller scale. Add NUMA and cache-locality-concern to the mix and things get harder still.
- jart 4y agoOn Linux and OpenBSD you can use futex(FUTEX_WAKE, 1) to wake precisely any one of the threads or processes waiting on futex(FUTEX_WAIT). Are you telling me that's broken? I understand that sophisticated synchronization primitives usually maintain a list of waiters, but I wasn't under the impression they do that because kernels are broken, but rather because userspace libraries want to be in control of which waiter gets selected. The reason why things are racey as you describe probably has more to do with userspace libraries wanting to avoid issuing a system call, than it does with the kernel's design. Things would probably be easier if you always used a system call, such as the case with most WIN32 locks, but it's slow so people try not to do it and sometimes fail. Also yes, I understand it's hard. That's why Google tasked the guy who built their fiercest rival (Altavista) with building their locking primitives (Chubby and *NSYNC).
- mannykannot 4y agoI'm not sure whether to read your comment as disputing the author's claim of having a fix for this particular problem, or that there will inevitably be other cases where condition variables fail unless futexes are fixed in the kernel.
- jart 4y agoIf you need really good synchronization primitives while Glibc is fixing things then I've had a lot of success with *NSYNC https://github.com/google/nsync https://github.com/google/nsync which is what Cosmopolitan Libc uses to implement pthread_cond_t.
- jeffbee 4y agoIts design is similar to absl::Mutex, which is available to c++ users. They may also have been written initially by Mike Burrows?
- jart 4y agoYes. *NSYNC was built by Mike Burrows. The guy famous for building Chubby and Altavista. You wouldn't think it though, considering the project only has 188 stars.
- aaaaaaaaaaab 4y ago
- eloff 4y agoRust doesn't help with implementing low level primitives like this, you'd have to use unsafe code.
- cesarb 4y ago> Rust doesn't help with implementing low level primitives like this A charitable reading of the parent comment might be that Rust already implements these particular low-level primitives, so that by using Rust, you are not using the problematic glibc pthread code. See https://blog.rust-lang.org/2022/06/30/Rust-1.62.0.html#thinner-faster-mutexes-on-linux https://blog.rust-lang.org/2022/06/30/Rust-1.62.0.html#thinn... for the relevant announcement: "Previously, Mutex, Condvar, and RwLock were backed by the pthreads library on Linux. [...] Rust's standard library now ships with a raw futex-based implementation of these locks on Linux, [...]"
- jstimpfle 4y agoIn either case you need to use some implementation of synchronisation primitives, and that could contain bugs. Where's the difference?
- asveikau 4y agoWhich means they have plenty of opportunities to introduce their own bugs.
- dundarious 4y agoglibc's impl is a "raw futex-based" one as well. I'm no great fan of glibc as an organization or body of code, but the comparative benefits of Rust here are not well explained.
- tialaramex 4y ago
- wizeman 4y agoJust a word of caution: I've tried replacing the mitigation patch (which I had been using for 18 months) with the author's minimal fix (the first out of the 6 patches, which is supposed to fix the issue) and I've immediately ran into a deadlock while building Poly/ML 5.9 (3 times, in fact), whereas previously I hadn't encountered this bug before, despite having built Poly/ML many times. This was on a 32-core machine with lots of background compilation going on at the same time (i.e. with a high load). It could be a coincidence or an unrelated bug, but it's also possible that the author's patch might not fix the issue completely.
- KyleSanderson 4y agoApply the entire series... That's what was likely tested the most.
- FeepingCreature 4y agoIf the patch that contains the entire fix (minus cleanup) doesn't work, then the entire patchset is unreliable, since the author necessarily doesn't understand it.
- robocat 4y agoYou are being wayyyy too harsh - the author is clearly amazingly competent but lacked time to validate the code. This is open source software and if you want your problem diagnosed and fixed then the canonical response is to tell you to stop kvetching and to go ahead and fix it yourself. I couldn’t diagnose or debug some intermittent faults in poor multi-threaded code (written by someone who struggles to think concurrently). I threw the code away and wrote it properly from scratch and that got rid of the data or race conditions causing the intermittent fault. I have had to fix multi-threaded code many many times because I am better than most at properly fixing it.
- AnssiH 4y agoIndeed. But for the record, the author has since found the issue, and in this case it indeed was a bug in the first patch that was inadvertently fixed by a later patch in the series: https://probablydance.com/2022/09/17/finding-the-second-bug-in-glibcs-condition-variable/#comment-15150 https://probablydance.com/2022/09/17/finding-the-second-bug-...
- deleted 4y ago[deleted]
- mort96 4y agoThis seems like some really good debugging effort, kudos. But, my takeaway from this is that there’s a glibc bug which causes deadlocks in correct code, and a proposed fix (even if partial) has been available for years, and glibc still hasn’t shipped a version with the fix so it’s up to distros and users to patch the broken glibc code. Reminds me of how a glibc update broke GNU m4 and GNU didn’t ship a fix to m4 for years, so it was up to distros and users to patch the latest release of GNU m4 to make it compile with the latest version of GNU glibc. And then a couple of years later GNU shipped another version of glibc which broke m4. GNU doesn’t strike me as an organisation which places a lot of value on software quality and reliability.
- rekado 4y ago> GNU doesn’t strike me as an organisation which places a lot of value on software quality and reliability. This stems from a misunderstanding of what GNU is. Ideally all projects under the GNU umbrella would work towards a unified operating system, but that's sadly not what it's like. The GNU project is not much of a project in the common sense of the word, nor is it much of an organisation. This is one of the many reasons why https://gnu.tools https://gnu.tools exists, a subset of GNU with common goals and values, including collaborative project management.
- xwolfi 4y agoIt sounds silly for deep theoricians and a somewhat politically active organization like GNU to have wanted to go all the way to an OS, the kind of software where you really need to throw all the beauty out of the window and solve dumb users tangible problems, like how to read a bluray from an obscure proprietary drive or how to run a game with a monopolistic corporation's binary drivers. GNU can never succeed at it because it can never compromise and maybe that's fine. It's a shame that it s considered a failure when they accomplished so much in the OS scaffolding part.
- mort96 4y agoI kind of get that. And if a change in GNU glibc caused a bug in GNU wget, I would hope that wget would release a fix relatively quickly, but I wouldn't necessarily have any special expectations just because glibc and wget are both part of GNU. But I wish that the projects in the GNU toolchain would at the very least collaborate. The combination of glibc + gcc + autotools + m4 makes such a core part of any GNU system that you'd hope that GNU cares to keep them mutually compatible. So when they release an update to glibc which breaks m4 which makes it impossible to compile the current version of the GNU toolchain using the current version of the GNU toolchain, that's extremely disappointing.
- sbf501 4y agoWhat bothers me is that the OCaml code looks so harmless: static void st_masterlock_acquire(st_masterlock * m) { pthread_mutex_lock(&m->lock); while (m->busy) { m->waiters ++; custom_condvar_wait(&m->is_free, &m->lock); m->waiters --; } m->busy = 1; pthread_mutex_unlock(&m->lock); } How is this bug not more common with such a simple invocation?
- asveikau 4y agoProbably you can get away with that simple invocation "most of the time", but what matters is the higher level code that calls it triggers the bug where other access patterns would not. Also, I do wonder why they roll their own mutex using condition variables. Most people probably would use a mutex and thus wouldn't hit the condition variable at all. Condition variables are more niche than mutex.
- mbac32768 4y agoAccording to Xavier Leroy (OCaml language dev): > It is possible to use a plain POSIX mutex as master lock, but fairness is awful. https://discuss.ocaml.org/t/is-there-a-known-recent-linux-locking-bug-that-affects-the-ocaml-runtime/6542/11?u=mbacarella https://discuss.ocaml.org/t/is-there-a-known-recent-linux-lo...
- sbf501 4y agoThanks. I've learned more about pthread just from this HN post than I've learned anywhere else online in the past few years. Makes me worried about some of my earlier code now. O_o
- jwatte 4y agoThat kinda depends on what custom_condvar_wait() does, right?
- grogers 4y agoJust 6 days ago they merged a custom condvar implementation based on futex directly to workaround the glibc bug. Before that it was just pthread_cond_wait
- chrsig 4y agoAwesome to see the author post TLA+ instructions & model source. One day I'll get around to actually learning it. In the meantime, what's posted is too involved for me to grok at first glance, but I'm still glad to see more real world uses pop up.
- oldtimer1901 4y agoOld timers will recall that when Java first became popular in the mid 90s it brought to light all sorts of bugs in various operating systems' thread implementations - particularly in SunOS/Solaris. It is discouraging that such basic bugs still exist in GNU/Linux after 25 years. But it's not surprising - if anyone tells you that they understand all possible multi-threaded scenarios and race conditions in the implementation of these libraries - they are mistaken. It's all trial and error.
- deleted 4y ago[deleted]
- ArrayBoundCheck 4y agoThat's not true at all. I wrote a simple set of threading functions and had 0 deadlocks no matter what I do to it. On youtube I watched a guy write out every possible state of his data structure for hashmap. It's implemented using atomics. It preformed pretty well according to the person and it also did not deadlock after being used in production for years
- dgan 4y agocan we have a "formal semantics for multi-threading" ? why it's not a thing?
- baq 4y agoIt’s super duper hard, mostly.
- kjeetgill 4y agoThere are. They're called memory models. I know Java's is pretty readable (see below). I think C and C++ have them too now. But when you're building on these things there's always lots of room to get them wrong! [0]: https://en.wikipedia.org/wiki/Java_memory_model https://en.wikipedia.org/wiki/Java_memory_model [1]: https://docs.oracle.com/javase/specs/jls/se18/html/jls-17.html#jls-17.4 https://docs.oracle.com/javase/specs/jls/se18/html/jls-17.ht...
- tsimionescu 4y agoAnother poster shared the Java memory model, and C++ and C have them as well. The article we're discussing shows another kind of formal model for multithreaded code in TLA+, and actually uses it to investigate this bug. There is also Tony Hoare's Communicating Sequential Processes formal model, first presented in 1978; and an entire field of CS research called process calculus. So, pick a formal model and use it - though note that formal methods tend to add significant extra effort to use, and may or may not pay off depednig on your domain and desired outcomes.
- metadat 4y agoIs there a way to bundle and use an more up-to-date version of glibc inside my docker containers? Is it a straightforward matter of creating an intermediate build-base-image where glibc gets compiled and copying over the resulting glibc .so artifact files to the final image? I suspect there may be additional concerns, but I'm not a glibc expert and have not needed to mess with it much. Also, does musl libc [0] have less bugs, on average? [0] https://musl.libc.org/ https://musl.libc.org/
- sanxiyn 4y agoYes. In fact, musl 1.2.0's pthread_mutex_t was verified in 2021 without changes. The same work found a bug in seL4 (obviously in unverified part, but still). The author remarks that this is in part because musl is conservative, and identifies barriers in musl that can be removed. But I think musl should get credits for being conservative here. Also in benchmarks, redundant barriers showed no performance impact. https://people.mpi-sws.org/~viktor/papers/asplos2021-vsync.pdf https://people.mpi-sws.org/~viktor/papers/asplos2021-vsync.p...
- keepquestioning 4y agoWould macOS see this issue too?
- saagarjha 4y agomacOS uses its own pthreads implementation: https://github.com/apple-oss-distributions/libpthread https://github.com/apple-oss-distributions/libpthread
- pengaru 4y agoIn 2022 a POSIX OS with a broken pthread_cond_t implementation is a broken OS, full stop. This is the POSIX API for implementing sleeping synchronization mechanisms in threaded programs. The glibc project should be incredibly embarrassed by this, assuming there's anyone even still paying attention there.
- nix23 4y agoWell it's gnu/linux, a multiuser unix that is not usable as a multiuser system (read the sdf.org story). It's a cheap hw-framework to run more or less reliable...but no problem we have kubernetes and containers to cover/perfume the stinking parts.
- Jasper_ 4y agoIsn't a semaphore usually a better choice than a condition variable / event, because you can still race if you try and wake the condition variable multiple times? e.g. https://devblogs.microsoft.com/oldnewthing/20060622-00/?p=30773 https://devblogs.microsoft.com/oldnewthing/20060622-00/?p=30... Why pthreads included condition variables but not semaphores, I don't know. Maybe because POSIX already had them?
- pengaru 4y agoNot sure I follow, there are semaphores (sem_init(3)) and you get them via -pthread on my glibc system. These are the semaphores I'm familiar with, which are plain counting semaphores you can also implement trivially using condition variables. The condition variable is a lower-level concept which pairs an OS-level signaling object and a mutex, it places no limits on what the condition may be, unlike a counting semaphore. Personally I find it more odd that they'd bother with sem_t when they already have pthread_cond_t. Perhaps there's an optimization opportunity in sem_t when the condition is specialized to involving just an integer counter, justifying the specialized interface? WRT waking the condition variable multiple times, properly handling spurious wakeups is kind of central to the proper use of them. That's why the condition test is always part of a loop, e.g.: pthread_mutex_lock(&lock); while (!condition_satisfied(shared_state)) pthread_cond_wait(&cond, &lock); { do things with condition satisfied and lock held } I always found condition variables to be nicely composable and ergonomic when writing pthread programs in C. But they come up short when you start wanting a file descriptor event to trigger the condition wakeup. In that case you end up doing silly things like spawning a thread just for the purpose of monitoring for fd events and turning them into a pthread_cond_signal() on the appropriate pthread_cond_t. AIUI the Windows WaitForMultipleObjects() interface does this better, so I hear, but I've never really dealt with Windows.
- userbinator 4y agoConcurrency is bug-prone. Complex code is bug-prone. glibc's CV implementation combines both. In my experience, both writing and teaching concurrency, there's a very strong sentiment of "I'll just use another CV/lock/etc." whenever people encounter a bug and try to fix it, which seldom fully solves the problem but usually makes it even more subtle and compounds the number of resulting states. One of my tricks to increase chances for race conditions and deadlocks when testing is to use a modified sampling profiler to randomly delay and pause threads, but with such a long sequence of steps as this bug requires, that would've been unlikely to help. Yet Murphy's Law says that it will happen in practice...