News for hackers. Stuff that matters.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by maxfurman on Wednesday April 28, 2021 @09:43AM (#26969250)
Can someone please ELI5 what is a futex? Is it like a mutex?
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by hyperman1 on Wednesday April 28, 2021 @09:50AM (#26969331)
Futex stands for fast userspace mutex. It is a basic building block for implementing a mutex (amongst others).

Afaik, if locking a mutex succeeds, futexes avoid a context switch to and from the kernel. The fast path happens completely in userspace. Only when a mutex lock causes a thread to sleep, the kernel is needed. All of this improves mutex performance.

There are other locking primitives than mutexes, and the current futex interface is not optimal for implementing common windows ones. Hence this proposal.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by xxs on Wednesday April 28, 2021 @02:03PM (#26972226)
>"context switch to and from the kernel"

This is a common misconception, a "context" switch is a lot more expensive than a "mode" switch that goes from user mode to the kernel mode (and back).

Of course, if the futex has to wait, it'd be a context switch for real.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by ece on Wednesday April 28, 2021 @06:55PM (#26975293)
ESYNC is the way this is currently done, it's hit and miss in that it doesn't work unless the number of open files is set high enough for some games. It's also slower than this proposal.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by whoisburbansky on Wednesday April 28, 2021 @09:52AM (#26969355)
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/
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @12:46PM (#26971441)
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...

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by kccqzy on Wednesday April 28, 2021 @01:44PM (#26972043)
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.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Wednesday April 28, 2021 @03:34PM (#26973172)
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.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by catern on Wednesday April 28, 2021 @07:39PM (#26975607)
>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?

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Saturday May 01, 2021 @06:35AM (#27005103)
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.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by catern on Saturday May 01, 2021 @11:18AM (#27006972)
>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.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Sunday May 02, 2021 @05:56AM (#27013788)
You wouldn't want to use an event loop to wait for a mutex as it doesn't really make much sense. It does make sense to use an event loop to wait for empty/non empty events (which on a normal queue you would implement with a cond var).

You have two options: you can use an eventfd to implement the queue full/empty event, or provide a generic notification interface (i.e. a callback). Any non event loop users wiuld simply have the callback signal a futex, but it allows for more complex use case: obviously you can wakeup the event loop from the callback, but you could resume a coroutine, send an async signal or whatever makes sense for the application.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @04:38PM (#26973885)
>'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?

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by tialaramex on Wednesday April 28, 2021 @06:05PM (#26974836)
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.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @07:39PM (#26975611)
Thanks for this insight. A couple quick questions:

>"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.

Did you mean to say "and it's time to release to you" here?

>"None of the conventional semantics are enforced by the operating system"

Ah OK, this is the part that I feel is maybe always left out of the things I've read on futex(). I guess this is just always implied then that some library implements these semantics correctly? And that library is generally going to glibc?

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by jesboat on Wednesday April 28, 2021 @10:59PM (#26976946)
> Ah OK, this is the part that I feel is maybe always left out of the things I've read on futex(). I guess this is just always implied then that some library implements these semantics correctly? And that library is generally going to glibc?

Yup. For example, the pthread_foo functions are futexes under the hood.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by tialaramex on Thursday April 29, 2021 @12:50AM (#26977586)
On Linux.

The POSIX threading API accommodates many possible implementations, and so in Linux many of the bits that look expensive (and might be on other systems) are more or less free thanks to futexes, e.g. setting up the mutex in Linux is just allocating an aligned 32-bit value on the heap and setting it to some initialising value, but on some systems it involves an OS system call to get a mutex handle.

This is the true benefit of the futex. The typical scheme for using it looks almost exactly like a well known trick for speeding up conventional mutual exclusion features that have low contention, which you'd see in say BeOS as the Benaphore, or described in several books about high performance programming. But those tricks all imply the expense of first obtaining a handle from the operating system for every such mutex whereas with a futex that part is free and you only talk to the operating system at all once there is contention for it to help you manage.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Thursday April 29, 2021 @09:45AM (#26981076)
>"The typical scheme for using it looks almost exactly like a well known trick for speeding up conventional mutual exclusion features that have low contention, which you'd see in say BeOS as the Benaphore, or described in several books about high performance programming."

Do you have any links that document this trick in Linux? Is there name for it or search term I could use to find out more?

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by tialaramex on Thursday April 29, 2021 @07:38PM (#26988207)
The phrase you'd have used to describe this when it wasn't just how everything works on a good OS is "Lightweight mutex". Here's Be explaining the "Benaphore" for example:

https://www.haiku-os.org/legacy-docs/benewsletter/Issue1-26....

Note that when I say "typical scheme for using it" I did not mean, that your program should implement such a scheme itself, instead futex is intended for the sort of people who implement the concurrency features in your language or APIs to use - and this is how they'd go about doing that to deliver the features you just use. So, for most of us this is interesting to know about but unlikely to impact our day-to-day practice.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by kccqzy on Wednesday April 28, 2021 @05:20PM (#26974366)
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.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @07:39PM (#26975615)
Thanks this implementation detail is helpful. Cheers.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by corbet on Wednesday April 28, 2021 @09:47AM (#26969307)
See https://lwn.net/Articles/823513/ for a look at both the old and proposed new futex interfaces.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by brandmeyer on Wednesday April 28, 2021 @10:42AM (#26969912)
The best introduction is probably the original presentation paper from 2002.

Fuss, Futexes, and Furwoks: Fast Userlevel Locking in Linux

https://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pd...

Another great paper that came after some additional experience by glibc developers:

Futexes are Tricky, by Ulrich Drepper

https://www.akkadia.org/drepper/futex.pdf

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by MaxBarraclough on Wednesday April 28, 2021 @12:29PM (#26971230)
I see Drepper resisted the urge to pluralise futex to futices.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Wednesday April 28, 2021 @09:50AM (#26969338)
A futex is an ephemeral list of waiting threads or processes keyed on an address. It can be used to implement any synchronization or signaling primitive, like mutexes, condition variables, semaphores, etc.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by tialaramex on Wednesday April 28, 2021 @06:20PM (#26974964)
This is a really nice insight into the kernel's model of what's going on. It's probably not the best way for an absolute beginner to think about why they want this, but it's much better than some of the other explanations if you have trickier technical or performance questions, and it makes it obvious why it's clever and why you need the OS kernel to actually implement it.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by DSingularity on Wednesday April 28, 2021 @10:06AM (#26969503)
Okay, consider a multi-threaded program. These programs have multiple threads running on multiple cores. Sometimes you want to coordinate the execution of multiple threads in such programs. A common example is when a thread is in a "critical section" where it is only safe for one thread to access/modify state. Sometimes threads will have to wait for each other. This is where the futex comes in. Instead of the thread to wait while using the processor it can tell the OS that it needs to wait for this futex to become free. The OS will then suspend the thread and find another one to schedule in its place.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @12:56PM (#26971559)
Ah Interesting. So is the concept of futex() similar to how a process in kernel mode will yield the CPU by putting itself on a wait_queue and call the schedule() function before it issues an I/O request then?

I realize that one is userspace and the other kernel but would the above be the right mental model?

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Wednesday April 28, 2021 @03:37PM (#26973202)
Yes, a futex is basically a waitqueue abstraction coupled with a TOCTOU guard.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by ROARosen on Wednesday April 28, 2021 @10:18AM (#26969642)
Can someone please ELI5 what is a mutex?
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by __init on Wednesday April 28, 2021 @10:42AM (#26969915)
(Edited because I transposed "mutex" and "semaphore" in my mind.)

A mutex is a lock -- if multiple users attempt to access a resource simultaneously, they each attempt to acquire the lock serially, and those not first are excluded (blocked) until the current holder releases the lock.

Mutexes are typically implemented with semaphores:

First a more developer-oriented explanation (because I imagine that's what you really want):

A semaphore locks a shared resource by implementing two operations, "up" and "down". First, the semaphore is initialized to some positive integer, which represents how many concurrent "users" (typically threads) can use that resource. Then, each time a user wants to take advantage of that resource, it "down"s the semaphore , which atomically subtracts one from the current value -- but the key is that the semaphore's value can _never_ be negative, so if the value is currently zero, "down"ing a semaphore implies blocking until it's non-zero again. "Up"ing is just what you'd imagine: atomically increment the semaphore value, and unblock someone waiting, if necessary.

Semaphores are generally seen as a fundamental primitive (one reason being that locks/mutexes can be implemented trivially as a semaphore initialized to one), but they also have broad use as a general synchronization mechanism between threads.

For a true ELI5 of semaphores (I enjoy writing these):

Imagine everyone in class needs to write something, but there are only three pencils available, so you devise a system (a system of mutual exclusion, per se) for everyone to follow while the pencils are used: First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the semaphore) you subtract one from the number in your head and give them a pencil. But if that number is zero, you don't have any pencils left, so you ask the person to wait. When someone returns and is done with their pencil, you hand it off to someone waiting, or, if nobody is waiting, you add one to that number in your head and take the pencil back ("up"ing the semaphore). It's important that you decide to only handle one request at a time (atomicity) -- if you tried to do too many things at once, you might lose track of your pencil count and accidentally promise more pencils than you have.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by MayeulC on Wednesday April 28, 2021 @11:04AM (#26970192)
> First, you note how many pencils are available -- three. Then, each time someone asks you for one, (which we call "down"ing the mutex) you subtract one from the number in your head and give them a pencil

Isn't that a semaphore rather than a mutex?

For ELI5 on semaphores, it's like going at the train station, airport, or Mc Donald's: There is a single queue for multiple counters. Everyone is given a paper with a number, and once a counter is free, the one with the lowest number can walk to it. A semaphore is just the number of free counters, it decreases when someone goes to one, and increases when one leaves. If the semaphore is zero, there is no free spot, and people will have to queue.

It's quite close to another synchronization primitive, barriers: if you have to wait for n tasks to finish, you make one with n spots, and release everyone when all the spots are filled.

To me, mutexes are semaphores, but with only one counter: there is only exactly one or zero resources available. If you take the mutex, others will have to wait for you to be done before they can take it. They can queue in any fashion, depending on the implementation: first come, first served; fastest first; most important first; random; etc.

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by __init on Wednesday April 28, 2021 @11:36AM (#26970585)
Oh no, you're absolutely right. My sleep-deprived brain has confused the names -- thanks for the heads up. I'll edit my post.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by e_proxus on Wednesday April 28, 2021 @03:24PM (#26973067)
But it can’t be turtles all the way down? Isn’t a semaphore counter also shared state that needs to be protected if several threads want to “down” the value? Can it become negative?
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by gpderetta on Wednesday April 28, 2021 @03:41PM (#26973245)
Well at the bottom of the turtle stack you have harware primitives that guarantee atomicity of a bunch of word sized arithmetic operations (at the minimum CAS or LL/SC).
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by ROARosen on Wednesday April 28, 2021 @12:41PM (#26971359)
Thanks, great analogue there, it really helped it 'click'!

Please excuse my ignorance...

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by marcodiego on Wednesday April 28, 2021 @10:23AM (#26969700)
Mutex is named after "mutual exclusion" a primitive that is used to guarantee that some parts of code will run exclusively, never at the same time. This is important for good performance and synchronization on multiple threaded programs.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by hyperman1 on Wednesday April 28, 2021 @01:05PM (#26971655)
A mutex is the software equivalent of the lock on your toilet door. There is a zone in your code where only 1 thread at a time is allowed. So before entering, you lock the mutex. Now either you are allowed in or are added to a set of waiters. When you leave, you unlock the mutex, and 1 other waiter is allowed to enter.

This sounds easy, but is in practice wrought eith peril. You need high performance, not waste too much cpu time on sleepers, some notion of fairness when you have lots of waiters, minimal memory usage, etc...

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by xxs on Wednesday April 28, 2021 @04:12PM (#26973612)
My ELI5 version of that locking mechanism, e.g. mutex, uses a toilet and the disaster if multiple people try taking the dump at the same time.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by bogomipz on Wednesday April 28, 2021 @08:14PM (#26975847)
I just found this article which I think is really helpful as it has some good historical context as well:

"Detailed approach of the futex"

http://www.rkoucha.fr/tech_corner/the_futex.html

Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by achernya on Wednesday April 28, 2021 @09:47AM (#26969314)
futex is a Fast Userspace muTEX. It's the syscall to help implement a mutex when there are two or more threads waiting on the lock to let other processes/threads schedule and do useful work during the wait.
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by hulitu on Wednesday April 28, 2021 @09:46AM (#26969297)
As far as i remember a futex is a fast mutex
Re:Proposed futex2 allows Linux to mimic the NT kernel for b... by Iwan-Zotow on Wednesday April 28, 2021 @10:40AM (#26969892)
it is thing behind/inside mutex. It is making uncontested mutex acquire/release ops pure userspace thingy.