3 ms·

That's very interesting history, thanks. I agree with Linux still only supporting 32-bit futexes is a bit baffling. The only reason the width matters is for th

• adrian_b 1y ago
  The futex width matters if you implement your own waiting on multiple events, with one bit per event. The events can be signaled with atomic bit operations.
  • cryptonector 1y ago
    Ideally the value should be two words -- 16 bytes on 64-bit systems.
    • prerok 1y ago
      Emm, what? Why? If you mean two processor words, which I gather from what you are saying, then I think you are already in the space of full memory barriers. In that case, why not just say, ideally it would be 256K words, or whatever?
      • cryptonector 1y ago
        Because there are apps that use two-word pass/return-by-value values internally, so it'd be convenient.
      • mananaysiempre 1y ago
        Because mainstream modern architectures (practically speaking, x86-64-v2+ and ARMv8+) give you[1] a two-word compare-and-swap or LL/SC. [1] https://ibraheem.ca/posts/128-bit-atomics/ https://ibraheem.ca/posts/128-bit-atomics/
        • viega 1y ago
          One thing to add here, I've enjoyed reasonably extensive support for `atomic_compare_exchange_strong()` and the `_explicit` variant for quite a long time (despite the need for the cache line lock on x86). 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? :)
        • adrian_b 1y ago
          However using compare-and-swap as the atomic operation for implementing multiple events can be very inefficient, because it introduces waiting loops where the threads can waste a lot of time when there is high contention. 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.