8 ms·
Landing a new syscall, part 1: What is futex?
- __s 5y agohttps://lore.kernel.org/lkml/20200612185122.327860-1-andrealmeid@collabora.com https://lore.kernel.org/lkml/20200612185122.327860-1-andreal... goes over what futex2 introduces
- gpderetta 5y agoWhile futex_waitv is great, I would have also liked a futex_wakev.
- ot 5y agoAs an optimization? Would futex support in io_uring be enough? https://lwn.net/Articles/857835/ https://lwn.net/Articles/857835/
- gpderetta 5y agoPossibly yes! Edit: but I'm having a deja vu. Did we already have this conversation?!?
- ot 5y agoNot that I remember :) I went through that LKML thread and it looks like that particular patch isn't going anywhere, but given the general direction of supporting all syscalls in io_uring, I'm confident it will happen eventually. Support for wait, in particular, would be strictly more powerful than waitv: you could wait for futexes and IO (or any other completions) at the same time!
- gpderetta 5y agoIt would. On the other hand, I never had a need to wait for futexes and IO at the same time. If I need an internal wakeup while blocked on a poll call, I would use an eventfd. YMMV. In any case generalized support for all or most syscalls in io_uring can only be a good thing. Especially if we get eBPF support for chaining. I'm also quite excited for the new intel instruction to send IPIs from userspace. That would be great for non blocking io_uring.
- wbl 5y agoWindows has had this one for a while.
- gpderetta 5y agoThe windows equivalent of futex_wait is WaitOnAddress. I don't think it supports waiting on multiple addresses, but I'm not a WIN32 programmer.
- sumtechguy 5y agoYeah from the 10 mins I spent in the docs I do not think there is one baked in. You would probably have to roll your own. It would not be pretty. https://docs.microsoft.com/en-us/windows/win32/api/synchapi/nf-synchapi-waitonaddress https://docs.microsoft.com/en-us/windows/win32/api/synchapi/...
- wbl 5y agoWaitForMultipleObjects. And it isn't from the Windows heritage but from VMS.
- gpderetta 5y agoWFMO is equivalent to select. This is different.
- __s 5y agoRelevant that Valve is sponsoring this for Wine's benefit
- ww520 5y agoI don't think Windows has the equivalent of futex2, waiting on multiple addresses. WaitOnAddress() in Windows is the equivalent of futex, waiting on a single address. WaitForMultipleObjects() in Windows is for acquiring multiple locks, not for waiting on arbitrary addresses. The parameters to WaitForMultipleObjects() are mutex/semaphore/event/etc handles. When WaitForMultipleObjects() returns, the ownerships of the locks are actually acquired. E.g. for semaphore, the count is decremented by WaitForMultipleObjects(). Futex2 is more generic where it just waits on multiple arbitrary addresses. The locking is done separately.
- im3w1l 5y agoI'm pretty sure the mutex_lock and mutex_unlock are bugged, as they take a mutex int by value. Would be unfortunate if somone copy pasted those.
- More-nitors 5y agocare to explain more?
- smhenderson 5y agoWithout having looked into any details I assume the parent is saying that the integer passed by value is a flag that is checked periodically and used to trigger a next step or to release a lock. If it's passed by value it will never change inside the function and whatever is supposed to happen when it changes will never get executed. The integers should be passed by reference so when they change the function receiving them is aware of the update.
- gpderetta 5y agoMost importantly wake and wait are keyed by address. The waker must provide to futex_wake the same address that the waiter passed to futex_wait to wake it.
- mockery 5y agoNot GP, but the code in the article passes 'unsigned int mutex' by-value, and then operates on its address (which will potentially be at a different stack address on each invocation, and will certainly be different for different threads.) It won't serve its purpose at all. To my eye, the code is fundamentally broken in a way that's surprising for an article trying to teach threading, and it's likely confuse someone unfamiliar with these concepts.
- im3w1l 5y agoThe articles code for mutex_lock is this mutex_lock(unsigned int mutex) { while (!cmpxchg(&mutex, UNLOCKED, LOCKED)) futex(&mutex, FUTEX_WAIT, LOCKED); } Now consider what happens if someone calls it volatile unsigned int my_mutex = UNLOCKED; mutex_lock(my_mutex); ... mutex_unlock(my_mutex); my_mutex is copied into the mutex parameter. The mutex parameter is updated to locked. mutex_lock exits, which destroys the mutex variable. my_mutex still has the variable UNLOCKED.
- gpderetta 5y agoThe article is nice, aside from the buggy and suboptimal implementations of the mutex. But I would like to stress that futexes are not just useful to implement mutexes (nor they are even the most interesting feature). They are a generalized waitqueue abstraction that can be used for all kind of signaling primitives. Also the nice thing about futexes is that they do not consume resources when they are not in use: you could implement a fast pathed mutex on top of, say, an eventfd, but allocating a file descriptor for each mutex can potentially run out of resources quickly.
- mfilion 5y agoThe mutex example was purely for didactic purposes, and definitely not a complete mutex. It was meant to help demonstrate the basics of how a mutex works. Blog post has been updated to clarify this.
- leshow 5y agoI didn't really get the example, futex is itself a syscall, so how does implementing mutex in terms of futex help you create a "fast userspace" mutex? The example presented looks to do almost nothing in userspace. Am I missing something?
- kvhdude 5y agowhen the cas (compare and swap) succeeds in user space, the subsequent futex call to wait will not be made, i suppose.
- aidenn0 5y agomutex_lock makes 0 system calls in the fast case (when cmpxchg succeeds on the first try). mutex_unlock makes 1 system call always, but TFA mentions that it can be optimized by adding some user-space complexity to check if signalling might be required (if you can demonstrate zero waiters, then the FUTEX_WAKE is not needed).
- gpderetta 5y agoYes, usually you keep a (saturating) waiter count, at the limit just one additional bit.
- waynesonfire 5y agoWow so poorly written. Hope author does a proof read for part 2. Mutual exclusion is tricky to follow and the bad grammer doesn't help.
- samatman 5y agoI know that account balances were just a "motivating example" here, but please, I beg you: don't handle accounts this way. Double-entry accounting predates computers by many centuries, and solves a problem which computers still have. Use double-entry accounting internally if you're handling money! This means both the liability and the asset side of the equation are balanced when written, and can be (should be, must be) balanced across both entries as well.
- exdsq 5y agoOne of those great moments where domain knowledge results in a substantially different system to the intuitive approach :)
- PoignardAzur 5y agoNaive question: how does double-entry accounting help computer accouting systems?
- inopinatus 5y agoIt’s the original CRDT.
- OJFord 5y agoEverything is accounted for, you can't accidentally (or 'accidentally') have money come from or go nowhere, since it must balance - account1 going up by a pound is matched to account2 going down a pound.
- kzrdude 5y ago(Serious question) Why don't we see money-out-of-nowhere bugs in banks? How do they ensure they don't happen? Even maliciously, for that reason.
- OJFord 5y agoWell we've done the (more direct) question and answer in reverse here really! Balancing is one part of the answer (I think it would be fair to say it doesn't necessarily have to be - or at least not obviously look like - double-entry). You could argue immutable (append-only) records help too - no amendments only additional corrective records. I've never worked in a bank btw so pinch of salt etc., just have a bit of an interest and fiddle on and off with a related project.
- LoveGracePeace 5y agoThat web site name looked familiar, it's one I used to get tons of recruiter spam from. I added it to my email server's block list some time ago.
- andrewshadura 5y agoThat's grossly untrue. We never send recruiting spam.
- LoveGracePeace 5y agotyingq pointed out my mistake, I was thinking of a very similar web site name.
- andrewshadura 5y agoThanks.
- tyingq 5y agoYou're probably thinking of https://www.collabera.com/ https://www.collabera.com/ Note the 'e' instead of the 'o'..."bera", not "bora".
- LoveGracePeace 5y agoYou're right thank you.
- winrid 5y agoNeat timing, was just running gdb on MongoDB and saw it uses futexes. Was debugging why the instances were hanging... sigh
- ww520 5y agoIt's important to remember that futex is not a lock; it is a conditional sleeping operation. Its name unfortunately looks similar to mutex but it's not a lock. A thread calls futex(&flag, FUTEX_WAIT) to sleep. The kernel wakes up the caller thread when the futex flag's value might have been changed, by another thread calling futex(&flag, FUTEX_WAKE). When futex() returns, you don't get a lock. It just means the value of the flag might have been changed. Since it's not a lock, the value of the flag is not guaranteed to be certain value when futex() returns. The flag can be changed again by another thread between the futex's return and the next instruction of the caller thread. It's important to put the futex() call inside a loop calling compare_and_set() repeatedly to check the expected value of the flag.
- dpratt71 5y agoStupid question: Why isn't such logic incorporated into the call itself?
- ww520 5y agoGood question. It's for performance reason. Calling into kernel is expensive. Lock acquired in the user mode is much faster than lock acquired in kernel. A typical lock acquisition using futex looks like: (a) while !compare_and_swap(&lock, 0, 1) // see if flag is free as 0, lock it as 1 (b) futex(&lock, WAIT, 1) // sleep until flag changes from 1 (a) runs in user mode and it's very fast. It's just one CMPXCHG assembly instruction. If the lock is free, it's acquired in one instruction as 1 (locked). If the lock is not free, then do the expensive call into the kernel to sleep via futex at (b). Futex() helps in detecting the change of the value while putting the thread to sleep, to avoid hogging the CPU.
- chrchang523 5y agoIt is worth noting here that this "one assembly instruction" is not that cheap. The hardware on a multicore system does have to perform some locking under the hood to execute that instruction. But yes, it still has enough of an advantage over calling into the kernel to justify the additional usage complexity.