4 ms·

It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty go

It's a primitive that lets you build mutexes; you've got an atomic integer in userspace, attached to a wait queue in kernel space. Eli Bendersky has a pretty good rundown: https://eli.thegreenplace.net/2018/basics-of-futexes/ https://eli.thegreenplace.net/2018/basics-of-futexes/

bogomipz 5y ago
This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"Before the introduction of futexes, system calls were required for locking and unlocking shared resources (for example semop)." >"A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true" The first indicates futexes are an improvement because they avoid the overhead of system call but the second states that futex() is a system call. Is this similar to how a vDSO or vsyscall works where a page from kernel address space is mapped into all users processes? In other words is it similar to how gettimeofday works?[1] [1] https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...
- kccqzy 5y ago
  It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
  - gpderetta 5y ago
    IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. Any kernel state is created lazily when needed (i.e on the first wait) and destroyed automatically when not needed (i.e. when the last waiter is woken up). Coupled with the minimal userspace space requirements (just a 32 bit word) it means that futexes can be embedded very cheaply in a lot of places.
    - catern 5y ago
      >The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). >The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. This is an extremely interesting and useful observation, thank you for making it. Futexes are missing a lot of useful functionality - see the OP, and as another example it's very hard to integrate them with an event loop - so I've been dreading building anything with them, but I thought I needed it to get fast synchronization. But for my use cases, I already have setup and teardown calls. Maybe I can do fast userspace synchronization on top of some other kernel object - a pipe, or something, as you suggest. Do you have any more to share about this observation, or pointers to any implementations of fast userspace synchronization on top of something other than futexes?
      - gpderetta 5y ago
        You can use eventfd as a pollable waiting primitive. But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases.
        catern 5y ago
        >But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases. I'm not sure what you mean, can you elaborate? Suppose I had a mutex (synchronization) implemented with a futex, and a shared memory queue (waiting) implemented with a futex; suppose both are being used to coordinate between multiple processes. I guess you're suggesting that one of those two doesn't need to be integrated with an event loop? But why? Both of those seem useful to have as part of an event loop.
        5y ago
  - bogomipz 5y ago
    >'The key phrase is "only when" in the second sentence' Thank you for pointing this out. That makes sense. This is sort of like the idea that the fastest system call is the one that is never made. Can you say how does something in userland know if something "would" block without actually crossing the user/kernel boundary? Does the kernel expose a queue length counter or similar via a read-only page?
    - kccqzy 5y ago
      The most common implementation of mutexes using futex() is that the userland simply spins a while waiting to acquire the mutex (just atomic operations, no system call). After a while the userland gives up spinning and makes the system call.
      - bogomipz 5y ago
        Thanks this implementation detail is helpful. Cheers.
    - tialaramex 5y ago
      The trick is, the memory address futex cares about is how you signal. Normally, in the "uncontended" case, everybody involved uses atomic memory access to manipulate this memory location (for example they set it to 1 as a flag to say somebody is in the mutually excluded code and then back to zero to say now nobody is in there) and they pay no kernel cost at all for this feature. The kernel has no idea the memory is even special. But in the contended case the flag is already set by somebody else, so you leave a sign (maybe you set it to 42) about the contention in the memory address, and you tell the kernel that you're going to sleep and it should wake you back up once whoever is blocking you releases. When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you. None of the conventional semantics are enforced by the operating system. If you write buggy code which just scribbles nonsense on the magic flag location, your program doesn't work properly. Too bad. The kernel does contain some code that helps do some tricks lots of people want to do using futexes, and so for that reason you should stick to the conventions, but nobody will force you to.

bogomipz 5y ago

This is a good post thanks. One thing confuses me is that these two sentences seem to contradict each other: >"Before the introduction of futexes, system calls were required for locking and unlocking shared resources (for example semop)." >"A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true" The first indicates futexes are an improvement because they avoid the overhead of system call but the second states that futex() is a system call. Is this similar to how a vDSO or vsyscall works where a page from kernel address space is mapped into all users processes? In other words is it similar to how gettimeofday works?[1] [1] https://0xax.gitbooks.io/linux-insides/content/SysCall/linux-syscall-3.html https://0xax.gitbooks.io/linux-insides/content/SysCall/linux...

kccqzy 5y ago
It's not a contradiction. The two sentences are perfectly clear to me. Of course futex() is itself a system call, but in case of no contention you don't need to invoke the system call. That's why futex() is an improvement. The key phrase is "only when" in the second sentence.
- gpderetta 5y ago
  IMHO The nice thing about futexes is not that they allow to fast path uncontended sinchronization. The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. Any kernel state is created lazily when needed (i.e on the first wait) and destroyed automatically when not needed (i.e. when the last waiter is woken up). Coupled with the minimal userspace space requirements (just a 32 bit word) it means that futexes can be embedded very cheaply in a lot of places.
  - catern 5y ago
    >The userspace fast path can in principle be implemented on top of any kernel only synchronization primitive (a pipe for example). >The nice thing about futexes is that they do not consume any kernel resource when uncontended, i.e there is no open or close futex syscalls. This is an extremely interesting and useful observation, thank you for making it. Futexes are missing a lot of useful functionality - see the OP, and as another example it's very hard to integrate them with an event loop - so I've been dreading building anything with them, but I thought I needed it to get fast synchronization. But for my use cases, I already have setup and teardown calls. Maybe I can do fast userspace synchronization on top of some other kernel object - a pipe, or something, as you suggest. Do you have any more to share about this observation, or pointers to any implementations of fast userspace synchronization on top of something other than futexes?
    - gpderetta 5y ago
      You can use eventfd as a pollable waiting primitive. But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases.
      - catern 5y ago
        >But there isn't really ever a reason to mix futexes and event loops. Futexes are not a synchronization primitive, just a waiting strategy. Decouple the two and you can integrate your synchronization primitives with an event loop while still using futexes for the non event-loop cases. I'm not sure what you mean, can you elaborate? Suppose I had a mutex (synchronization) implemented with a futex, and a shared memory queue (waiting) implemented with a futex; suppose both are being used to coordinate between multiple processes. I guess you're suggesting that one of those two doesn't need to be integrated with an event loop? But why? Both of those seem useful to have as part of an event loop.
        5y ago
- bogomipz 5y ago
  >'The key phrase is "only when" in the second sentence' Thank you for pointing this out. That makes sense. This is sort of like the idea that the fastest system call is the one that is never made. Can you say how does something in userland know if something "would" block without actually crossing the user/kernel boundary? Does the kernel expose a queue length counter or similar via a read-only page?
  - kccqzy 5y ago
    The most common implementation of mutexes using futex() is that the userland simply spins a while waiting to acquire the mutex (just atomic operations, no system call). After a while the userland gives up spinning and makes the system call.
    - bogomipz 5y ago
      Thanks this implementation detail is helpful. Cheers.
  - tialaramex 5y ago
    The trick is, the memory address futex cares about is how you signal. Normally, in the "uncontended" case, everybody involved uses atomic memory access to manipulate this memory location (for example they set it to 1 as a flag to say somebody is in the mutually excluded code and then back to zero to say now nobody is in there) and they pay no kernel cost at all for this feature. The kernel has no idea the memory is even special. But in the contended case the flag is already set by somebody else, so you leave a sign (maybe you set it to 42) about the contention in the memory address, and you tell the kernel that you're going to sleep and it should wake you back up once whoever is blocking you releases. When whoever was in there is done, they try to put things back to zero, but they discover you've left that sign that you were waiting, so they tell the kernel they're done with the address and it's time to release you. None of the conventional semantics are enforced by the operating system. If you write buggy code which just scribbles nonsense on the magic flag location, your program doesn't work properly. Too bad. The kernel does contain some code that helps do some tricks lots of people want to do using futexes, and so for that reason you should stick to the conventions, but nobody will force you to.