Windows NT synchronization primitives for Linux

Posted Feb 16, 2024 19:23 UTC (Fri) by abatters (✭ supporter ✭, #6932)
Parent article: Windows NT synchronization primitives for Linux

> Futexes work well for many applications, but not all.

The timing of this made me laugh. A week ago I ran into this years-old bug for the first time:

pthread_cond_signal failed to wake up pthread_cond_wait due to a bug in undoing stealing

To be fair though it is a glibc bug not a futex bug.

Windows NT synchronization primitives for Linux

Posted Feb 17, 2024 7:16 UTC (Sat) by alonz (subscriber, #815) [Link] (8 responses)

But this does illustrate that synchronization primitives are hard.

Windows NT synchronization primitives for Linux

Posted Feb 17, 2024 8:50 UTC (Sat) by Sesse (subscriber, #53779) [Link] (7 responses)

The only thing that's harder is not using them! Lock-free programming is… subtle.

(I guess you could argue that implementing mutexes is a form of lock-free programming…)

Windows NT synchronization primitives for Linux

Posted Feb 17, 2024 9:20 UTC (Sat) by pbonzini (subscriber, #60935) [Link] (4 responses)

Indeed, if you can implement your new synchronization primitives on top of something else (which is what this ntsync work or even the futex system call do, using e.g. waitqueues) it's not that hard. But the futex code in glibc is much harder to write, much more so than the futex implementation in the kernel itself!

Windows NT synchronization primitives for Linux

Posted Feb 17, 2024 9:43 UTC (Sat) by itsmycpu (guest, #139639) [Link] (3 responses)

glibc code, for example for mutexes, is somewhat complex mostly because of the many options that it supports. Futex'es without the userspace part are "just" a mechanism to wait atomically, not a complete synchronization primitive.

Windows NT synchronization primitives for Linux

Posted Feb 18, 2024 15:57 UTC (Sun) by tialaramex (subscriber, #21167) [Link] (2 responses)

Yeah, compare Rust's Mutex† which, on Linux, ultimately boils down to: https://github.com/rust-lang/rust/blob/master/library/std...

... with what they have to do if you only have POSIX threads: https://github.com/rust-lang/rust/blob/master/library/std...

Between "It's very stupid but POSIX technically allows this, so we need to cope" on one hand, and people just straight up not complying with POSIX anyway on the other I'd have thrown all of my toys out of the pram before writing the latter monster.

† Technically unlike the C mutex, a Rust Mutex<T> is a wrapper for a type T, the code I've linked isn't about that part, just the part with the actual mechanics of a mutex which are platform specific.

Windows NT synchronization primitives for Linux

Posted Feb 18, 2024 19:57 UTC (Sun) by intelfx (subscriber, #130118) [Link] (1 responses)

> with what they have to do if you only have POSIX threads: https://github.com/rust-lang/rust/blob/master/library/std...
>
> [...] I'd have thrown all of my toys out of the pram before writing the latter monster [...]

I'm not seeing anything criminal there. Certainly not a monster. WDYM?

Windows NT synchronization primitives for Linux

Posted Feb 19, 2024 10:31 UTC (Mon) by tialaramex (subscriber, #21167) [Link]

For example when we want to lock the mutex, that can't fail in POSIX, it will just deadlock if we're recursively locking our own mutex, which in Rust's model is fine... too bad Sun didn't agree and so it fails instead.

_ = libc::pthread_mutex_lock(raw(self)); // Should be fine, but instead there's a whole mess

Windows NT synchronization primitives for Linux

Posted Feb 18, 2024 15:32 UTC (Sun) by tialaramex (subscriber, #21167) [Link] (1 responses)

I don't think so, lock freedom guarantees global progress. If our threads are executing and we're a lock free algorithm, we will get work done. It may be the least preferred work, it may get done more slowly than preferred, but some of the work we had gets done. I think mutexes can't promise that, you might spend all of your execution resources on the mechanics and get no work done.

And one step harder is wait freedom, a guarantee of local progress - if our threads are executing specific work will get done, if thread A is squawking a goose, that goose gets squawked, it may not get squawked quickly but it definitely gets squawked, whereas a lock free algorithm is allowed to leave thread A starving forever until some day squawking that goose is globally the only work left to do.

Windows NT synchronization primitives for Linux

Posted Feb 21, 2024 1:26 UTC (Wed) by itsmycpu (guest, #139639) [Link]

Maybe that was just meant to say that implementing a mutex requires similar programming techniques (atomic operations, avoiding issues like race conditions) as lock-free programming.

Of course, there can be (and there are already some) higher level abstractions for lock-free programming as well.