lightweight robust futexes: -V1
cover lightweight robust futexes: -V1
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Background
----------
what are robust futexes? To answer that, we first need to understand what futexes are: normal futexes are special types of locks that in the noncontended case can be acquired/released from userspace without having to enter the kernel.
A futex is in essence a user-space address, e.g. a 32-bit lock variable field. If userspace notices contention (the lock is already owned and someone else wants to grab it too) then the lock is marked with a value that says "there's a waiter pending", and the sys_futex(FUTEX_WAIT) syscall is used to wait for the other guy to release it. The kernel creates a 'futex queue' internally, so that it can later on match up the waiter with the waker - without them having to know about each other. When the owner thread releases the futex, it notices (via the variable value) that there were waiter(s) pending, and does the sys_futex(FUTEX_WAKE) syscall to wake them up. Once all waiters have taken and released the lock, the futex is again back to 'uncontended' state, and there's no in-kernel state associated with it. The kernel completely forgets that there ever was a futex at that address. This method makes futexes very lightweight and scalable.
"Robustness" is about dealing with crashes while holding a lock: if a process exits prematurely while holding a pthread_mutex_t lock that is also shared with some other process (e.g. yum segfaults while holding a pthread_mutex_t, or yum is kill -9-ed), then waiters for that lock need to be notified that the last owner of the lock exited in some irregular way.
To solve such types of problems, "robust mutex" userspace APIs were
created: pthread_mutex_lock() returns an error value if the owner exits prematurely - and the new owner can decide whether the data protected by the lock can be recovered safely.
There is a big conceptual problem with futex based mutexes though: it is the kernel that destroys the owner task (e.g. due to a SEGFAULT), but the kernel cannot help with the cleanup: if there is no 'futex queue' (and in most cases there is none, futexes being fast lightweight locks) then the kernel has no information to clean up after the held lock! Userspace has no chance to clean up after the lock either - userspace is the one that crashes, so it has no opportunity to clean up. Catch-22.
In practice, when e.g. yum is kill -9-ed (or segfaults), a system reboot is needed to release that futex based lock. This is one of the leading bugreports against yum.
To solve this problem, 'Robust Futex' patches were created and presented on lkml: the one written by Todd Kneisel and David Singleton is the most advanced at the moment. These patches all tried to extend the futex abstraction by registering futex-based locks in the kernel - and thus give the kernel a chance to clean up.
E.g. in David Singleton's robust-futex-6.patch, there are 3 new syscall variants to sys_futex(): FUTEX_REGISTER, FUTEX_DEREGISTER and FUTEX_RECOVER. The kernel attaches such robust futexes to vmas (via vma->vm_file->f_mapping->robust_head), and at do_exit() time, all vmas are searched to see whether they have a robust_head set.
Lots of work went into the vma-based robust-futex patch, and recently it has improved significantly, but unfortunately it still has two fundamental problems left:
- they have quite complex locking and race scenarios. The vma-based patches had been pending for years, but they are still not completely reliable.
- they have to scan _every_ vma at sys_exit() time, per thread!
The second disadvantage is a real killer: pthread_exit() takes around 1 microsecond on Linux, but with thousands (or tens of thousands) of vmas every pthread_exit() takes a millisecond or more, also totally destroying the CPU's L1 and L2 caches!
This is very much noticeable even for normal process sys_exit_group()
calls: the kernel has to do the vma scanning unconditionally! (this is because the kernel has no knowledge about how many robust futexes there are to be cleaned up, because a robust futex might have been registered in another task, and the futex variable might have been simply mmap()-ed into this process's address space).
This huge overhead forced the creation of CONFIG_FUTEX_ROBUST, but worse than that: the overhead makes robust futexes impractical for any type of generic Linux distribution.
So it became clear to us, something had to be done. Last week, when Thomas Gleixner tried to fix up the vma-based robust futex patch in the -rt tree, he found a handful of new races and we were talking about it and were analyzing the situation. At that point a fundamentally different solution occured to me. This patchset (written in the past couple of days) implements that new solution. Be warned though - the patchset does things we normally dont do in Linux, so some might find the approach disturbing. Parental advice recommended ;-)
New approach to robust futexes
------------------------------
At the heart of this new approach there is a per-thread private list of robust locks that userspace is holding (maintained by glibc) - which userspace list is registered with the kernel via a new syscall [this registration happens at most once per thread lifetime]. At do_exit() time, the kernel checks this user-space list: are there any robust futex locks to be cleaned up?
In the common case, at do_exit() time, there is no list registered, so the cost of robust futexes is just a simple current->robust_list != NULL comparison. If the thread has registered a list, then normally the list is empty. If the thread/process crashed or terminated in some incorrect way then the list might be non-empty: in this case the kernel carefully walks the list [not trusting it], and marks all locks that are owned by this thread with the FUTEX_OWNER_DEAD bit, and wakes up one waiter (if any).
The list is guaranteed to be private and per-thread, so it's lockless. There is one race possible though: since adding to and removing from the list is done after the futex is acquired by glibc, there is a few instructions window for the thread (or process) to die there, leaving the futex hung. To protect against this possibility, userspace (glibc) also maintains a simple per-thread 'list_op_pending' field, to allow the kernel to clean up if the thread dies after acquiring the lock, but just before it could have added itself to the list. Glibc sets this list_op_pending field before it tries to acquire the futex, and clears it after the list-add (or list-remove) has finished.
That's all that is needed - all the rest of robust-futex cleanup is done in userspace [just like with the previous patches].
Ulrich Drepper has implemented the necessary glibc support for this new mechanism, which fully enables robust mutexes. (Ulrich plans to commit these changes to glibc-HEAD later today.)
Key differences of this userspace-list based approach, compared to the vma based method:
- it's much, much faster: at thread exit time, there's no need to loop over every vma (!), which the VM-based method has to do. Only a very simple 'is the list empty' op is done.
- no VM changes are needed - 'struct address_space' is left alone.
- no registration of individual locks is needed: robust mutexes dont need any extra per-lock syscalls. Robust mutexes thus become a very lightweight primitive - so they dont force the application designer to do a hard choice between performance and robustness - robust mutexes are just as fast.
- no per-lock kernel allocation happens.
- no resource limits are needed.
- no kernel-space recovery call (FUTEX_RECOVER) is needed.
- the implementation and the locking is "obvious", and there are no interactions with the VM.
Performance
-----------
I have benchmarked the time needed for the kernel to process a list of 1 million (!) held locks, using the new method [on a 2GHz CPU]:
- with FUTEX_WAIT set [contended mutex]: 130 msecs
- without FUTEX_WAIT set [uncontended mutex]: 30 msecs
I have also measured an approach where glibc does the lock notification [which it currently does for !pshared robust mutexes], and that took 256 msecs - clearly slower, due to the 1 million FUTEX_WAKE syscalls userspace had to do.
(1 million held locks are unheard of - we expect at most a handful of locks to be held at a time. Nevertheless it's nice to know that this approach scales nicely.)
Implementation details
----------------------
The patch adds two new syscalls: one to register the userspace list, and one to query the registered list pointer:
asmlinkage long
sys_set_robust_list(struct robust_list_head __user *head,
size_t len);
asmlinkage long
sys_get_robust_list(int pid, struct robust_list_head __user **head_ptr,
size_t __user *len_ptr);
List registration is very fast: the pointer is simply stored in current->robust_list. [Note that in the future, if robust futexes become widespread, we could extend sys_clone() to register a robust-list head for new threads, without the need of another syscall.]
So there is virtually zero overhead for tasks not using robust futexes, and even for robust futex users, there is only one extra syscall per thread lifetime, and the cleanup operation, if it happens, is fast and straightforward. The kernel doesnt have any internal distinction between robust and normal futexes.
If a futex is found to be held at exit time, the kernel sets the highest bit of the futex word:
#define FUTEX_OWNER_DIED 0x40000000
and wakes up the next futex waiter (if any). User-space does the rest of the cleanup.
Otherwise, robust futexes are acquired by glibc by putting the TID into the futex field atomically. Waiters set the FUTEX_WAITERS bit:
#define FUTEX_WAITERS 0x80000000
and the remaining bits are for the TID.
Testing, architecture support
-----------------------------
i've tested the new syscalls on x86 and x86_64, and have made sure the parsing of the userspace list is robust [ ;-) ] even if the list is deliberately corrupted.
i386 and x86_64 syscalls are wired up at the moment, and Ulrich has tested the new glibc code (on x86_64 and i386), and it works for his robust-mutex testcases.
All other architectures should build just fine too - but they wont have the new syscalls yet.
Architectures need to implement the new futex_atomic_cmpxchg_inuser() inline function before writing up the syscalls (that function returns -ENOSYS right now).
Ingo
Quoted 5 lines · Ingo Molnar
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
the patchset can also be downloaded from:
http://redhat.com/~mingo/lightweight-robust-futexes/
Ingo
Quoted 3 lines · Ingo Molnar
In practice, when e.g. yum is kill -9-ed (or segfaults), a system reboot is needed to release that futex based lock. This is one of the leading bugreports against yum.
Reboot? That object is stored somewhere in user space, isn't it? And wherever it is that object can be removed, can't it?
e.g. if you have it in a shared memory object you could just add some code to always kill everybody who has the shared memory mapped.
I wrote code like this some time ago when I was experimenting with a new machine check handler. It looked for all processes mapping some memory when the CPU reported it corrupted and killed them.
e.g. you could add a new VMA flag that says "when one user of this dies unexpectedly by a signal kill all"
That would solve the problem too, wouldn't it?
It might not be highly available, but people who want that can just use the plain old sysv in kernel locks. In theory you could make it in fact highly available by catching the signal in the other process and then doing the lock cleanup from there.
Of course it won't help if the lock is stored on disk, but that's not in any way different from any other existing disk based lock file.
Quoted 3 lines
Ulrich Drepper has implemented the necessary glibc support for this new mechanism, which fully enables robust mutexes. (Ulrich plans to commit these changes to glibc-HEAD later today.)
And what happens if the patch is rejected? I don't really think you can force patches in this way ("do it or I break glibc")
I think it really needs proper discussion first before it's merged anywhere. And glibc should be the slave of the kernel on this, not the other way round.
Quoted 10 lines
The patch adds two new syscalls: one to register the userspace list, and one to query the registered list pointer:
asmlinkage long
sys_set_robust_list(structrobust_list_head__user*head,size_t len);asmlinkage long
sys_get_robust_list(int pid, structrobust_list_head__user**head_ptr,size_t __user *len_ptr);
What happens when the list gets corrupted? Does the kernel go into an endless loop? Kernel going through arbitary user structures like this seems very risky to me. There are ways to do list walking with cycle detection, but they still have quite bad worst case detection times.
Or when parts of these mappings are remote on NFS and the server is down etc - then the kernel could potentially block a long time in exit.
-Andi
Quoted 2 lines · Andi Kleen
e.g. you could add a new VMA flag that says "when one user of this dies unexpectedly by a signal kill all"
"kill all"? That is so completely different from the intended behavior.
Robust mutexes are no concept which has been invented here. It is
clearly specified. The reaction to a terminating thread/process is notification of other interested parties.
None of your proposals makes any sense in this context.
Quoted 2 lines
And what happens if the patch is rejected? I don't really think you can force patches in this way ("do it or I break glibc")
Nothing which relies on the syscalls goes into cvs unless the kernel side is first committed. I never do this. What is in cvs now is an implementation of the intra-thread robust mutexes based on the same mechanisms. I.e., using the new syscall is a trivial thing since the infrastructure is already in place. And the method is proven to work.
Quoted 5 lines
What happens when the list gets corrupted? Does the kernel go into an endless loop? Kernel going through arbitary user structures like this seems very risky to me. There are ways to do list walking with cycle detection, but they still have quite bad worst case detection times.
The list being corrupted means that the mutexes are corrupted. In which case the application would crash anyway.
As for the "endless loop". You didn't read the code, it seems. There are two mechanisms to prevent this: the list is destroyed when the individual elements are handled and there is an upper limit on the number of robust mutexes which can be registered. The limit is ridiculously high so it'll no problem for correct programs and it also will eliminate run-away list following code.
Signature · 1 line
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖
Quoted 5 lines · Ulrich Drepper
Quoted 2 lines · Andi Kleen
e.g. you could add a new VMA flag that says "when one user of this dies unexpectedly by a signal kill all"
"kill all"?
It would solve the problem statement given by Ingo in the rationale for this kernel patch - cleaning up after a hanging yum.
If there are any other problems this is intended to solve then they should be stated in the rationale.
Quoted 5 lines
Quoted 2 lines
And what happens if the patch is rejected? I don't really think you can force patches in this way ("do it or I break glibc")
Nothing which relies on the syscalls goes into cvs unless the kernel side is first committed. I never do this.
Great we agree on that then.
Quoted 2 lines
The list being corrupted means that the mutexes are corrupted. In which case the application would crash anyway.
I'm not concerned about the application, just about the kernel.
Quoted 6 lines
As for the "endless loop". You didn't read the code, it seems. There are two mechanisms to prevent this: the list is destroyed when the individual elements are handled and there is an upper limit on the number of robust mutexes which can be registered. The limit is ridiculously high so it'll no problem for correct programs and it also will eliminate run-away list following code.
Ok good that's handled. How about long blocking on swapped out pages in exit?
You would need a SO_LINGER I guess, but implementing that would be fairly nasty.
I think the "kill all" approach would be much simpler.
-Andi
Quoted 11 lines · Andi Kleen
Quoted 6 lines · Ulrich Drepper
Quoted 2 lines · Andi Kleen
e.g. you could add a new VMA flag that says "when one user of this dies unexpectedly by a signal kill all"
"kill all"?
It would solve the problem statement given by Ingo in the rationale for this kernel patch - cleaning up after a hanging yum.
If there are any other problems this is intended to solve then they should be stated in the rationale.
"robust" mutexes isn't a new thing, so I assume Ingo didn't think he needed to post the whole rationale.
Consider a group of tasks that want to use a mutex to control access to data. If one of them dies while holding the mutex, the state of the data is unknown and the mutex is left locked.
The goal is for the kernel to unlock the mutex, but the next task to aquire it gets some special notification that the status is unknown. At that point the task can either validate/clean up the data and reset the mutex to clean (if it can) or it can give up the mutex and pass it on to some other task that does know how to validate/clean up.
You want the speed of futexes if possible. You want to keep running. You just want to know that the data protected by the mutex may not be self-consistent.
Chris
Quoted 5 lines · Christopher Friesen
The goal is for the kernel to unlock the mutex, but the next task to aquire it gets some special notification that the status is unknown. At that point the task can either validate/clean up the data and reset the mutex to clean (if it can) or it can give up the mutex and pass it on to some other task that does know how to validate/clean up.
The "send signal when any mapper dies" proposal would do that. The other process could catch the signal and do something with it.
-Andi
Quoted 11 lines · Andi Kleen
Quoted 5 lines · Christopher Friesen
The goal is for the kernel to unlock the mutex, but the next task to aquire it gets some special notification that the status is unknown. At that point the task can either validate/clean up the data and reset the mutex to clean (if it can) or it can give up the mutex and pass it on to some other task that does know how to validate/clean up.
The "send signal when any mapper dies" proposal would do that. The other process could catch the signal and do something with it.
That would be a new signal such as SIG_FUTEXDIED, would it?
--
Greetz, Antonio Vargas aka winden of network
http://wind.codepixel.com/
[email protected]
[email protected]
Every day, every year
you have to work
you have to study
you have to scene.
Quoted 9 lines · Antonio Vargas
Quoted 8 lines · Andi Kleen
Quoted 5 lines · Christopher Friesen
The goal is for the kernel to unlock the mutex, but the next task to aquire it gets some special notification that the status is unknown. At that point the task can either validate/clean up the data and reset the mutex to clean (if it can) or it can give up the mutex and pass it on to some other task that does know how to validate/clean up.
Quoted 5 lines
Quoted 3 lines
The "send signal when any mapper dies" proposal would do that. The other process could catch the signal and do something with it.
That would be a new signal such as
SIG_FUTEXDIED, would it?
It could be probably made configurable, possibly even in fancy ways (RT signal with payload giving the process that got killed and other information)
However that would require a new field to the VMA which is a bit memory critical. Hardcoding the signal is probably better, then only a new bit would be needed. Or maybe two bits, one for SIGKILL and another for fixed real time signal with payload.
With that the list walking Ingo put into the kernel could be all done in user space.
Ok it might be tricky to ensure the VMA bit is set on all mappings that need it. I had some vague memories that SUS had a mmap flag for that, but I can't find it right now.
An alternative would be to make it not a VMA attribute, but a mm_struct attribute - then it would need to be enabled only once, not on each mmap.
-Andi
Quoted 10 lines · Andi Kleen
Quoted 5 lines · Christopher Friesen
The goal is for the kernel to unlock the mutex, but the next task to aquire it gets some special notification that the status is unknown. At that point the task can either validate/clean up the data and reset the mutex to clean (if it can) or it can give up the mutex and pass it on to some other task that does know how to validate/clean up.
The "send signal when any mapper dies" proposal would do that. The other process could catch the signal and do something with it.
the last time we had special signals for glibc-internal purpose it was called 'LinuxThreads'. The concept sucked big big time. Using internal signals means playing with the signal mask - this could conflict with the application, etc. etc. It's simply out of question to play signal games. Not to mention the problem of multiple mappers dying. Should thus queued signals be used? How about if the signal queue overflows.
Signals are really not for stuff like this. Signals are an old, semantics-laden and thus fragile concept that are not suited for abstractions like that.
Another flaw with your suggestion is that the mapper _might not know_ at the time of mmap() that this memory includes a robust futex. So that brings us back to the per-lock registration syscall approach (and overhead) that our patch avoids. Furthermore, glibc would have to track whether a thread used a robust mutex for the first time - which means external object to pthread_mutex_t - additional complications, overhead and design weaknesses.
If you take a look at the list-based robust futex code and the concept, you'll see that a lightweight userspace list of futexes, optionally parsed by the kernel, mixes very well with the existing futex philosophy and methodology. It doesnt have any of these complications and cornercases, precisely because its design aligns naturally with the futex philosophy: futexes are primarily memory based objects. They are not signals. They are not in-kernel structures. They are primarily a piece of userspace memory.
Ingo
Quoted 9 lines · Andi Kleen
Quoted 5 lines · Ulrich Drepper
Quoted 2 lines · Andi Kleen
e.g. you could add a new VMA flag that says "when one user of this dies unexpectedly by a signal kill all"
"kill all"?
It would solve the problem statement given by Ingo in the rationale for this kernel patch - cleaning up after a hanging yum.
no, it wouldnt solve it. How do you know in userspace that the futex got orphan? Say the futex value is stuck at '2'. How do you know it's hung due to the premature exit of its owner?
Premature exit while holding locks is a fundamental property of the locking abstraction - which, in the case of futex based locks, cannot be implemented without kernel help. It's a tough problem that we struggled with for years to solve properly.
Quoted 2 lines
If there are any other problems this is intended to solve then they should be stated in the rationale.
i really only wrote that quick and light preamble to introduce the topic
- not to start any discussion whether the topic exists. The topic obviously exists, check out pthread_mutex_t robustness APIs in other OSs:
http://docs.sun.com/app/docs/doc/816-5137/6mba5vpjf?a=view#sync-103
http://docs.sun.com/app/docs/doc/816-5137/6mba5vpjg?a=view#sync-116
the vma-based robust-futex patches have been circulating on lkml for quite some time, they were even in -mm for some time. Check out:
http://developer.osdl.org/dev/robustmutexes/
for a background. To make sure: our patch handles the 'robust' portion, not the PI portion - just like the previous vma-based patches previously sent to lkml. I.e. robustness comes first - it's a feature orthogonal to priority inheritance.
just in case you were wondering: this is not an ad-hoc topic we made up :-|
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines
And what happens if the patch is rejected? I don't really think you can force patches in this way ("do it or I break glibc")
Nothing which relies on the syscalls goes into cvs unless the kernel side is first committed. I never do this.
Andi, what were you thinking by suggesting that we want to "force patches"? Really, have we ever done that? Ulrich is known to be very strict about ABI issues, and he probably wont even trust Linus himself saying that a syscall will go in - he'll only trust the commit log.
Frankly, i thought we are offering a cool new feature as a solution to a hard problem, and i'm really startled (and saddened) to see such a default assumption of malice from you :-( I dont think we deserved that.
Quoted 10 lines
Quoted 8 lines
Quoted 5 lines
What happens when the list gets corrupted? Does the kernel go into an endless loop? Kernel going through arbitary user structures like this seems very risky to me. There are ways to do list walking with cycle detection, but they still have quite bad worst case detection times.
The list being corrupted means that the mutexes are corrupted. In which case the application would crash anyway.
I'm not concerned about the application, just about the kernel.
i said it multiple times in the announcement:
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
If the thread/process crashed or terminated in some incorrect way then the list might be non-empty: in this case the kernel carefully walks the list [not trusting it],
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
and:
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
i've tested the new syscalls on x86 and
x86_64, and have made sure the parsing of the userspace list is robust [ ;-) ] even if the list is deliberately corrupted.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
You could even have read the code - the function is called exit_robust_list(), and is commented quite extensively:
+/*
+ * Walk curr->robust_list (very carefully, it's a userspace list!)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+ * and mark any locks found there dead, and notify any waiters.
+ *
+ * We silently return on any sign of list-walking problem.
+ */
+void exit_robust_list(struct task_struct *curr)
again, i'm startled at your clearly baseless negative reaction :-(
Quoted 9 lines
Quoted 6 lines
As for the "endless loop". You didn't read the code, it seems. There are two mechanisms to prevent this: the list is destroyed when the individual elements are handled and there is an upper limit on the number of robust mutexes which can be registered. The limit is ridiculously high so it'll no problem for correct programs and it also will eliminate run-away list following code.
Ok good that's handled. How about long blocking on swapped out pages in exit?
We already touch userspace pages in do_exit() (and had been for years), so we may already 'block' on a swapped out page - which will become swapped in and then the kernel continues. The maximum amount of delay depends on how many pages are touched. You can think of the list-walking as a 'preamble' to the thread exiting - it could have been triggered by userspace, straight before the do_exit() was executed.
Furthermore, there is a limit on the maximum number of list entries walked (ROBUST_LIST_LIMIT) - i set it to a quite high number [to be able to test performance], but we could reduce it significantly. Realistically there wont be more than say a dozen locks held at exit time.
Ingo
Quoted 6 lines · Ingo Molnar
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Next point of discussion must be PI . Considering that this
implementation is lacking it. Maybe it wouldn't be "lightweight" if it was included.
If PI is to be added to Linux it will need to encompass both
mutex implementations . Was this a consideration in the design of these lightweight futexes?
Daniel
Quoted 8 lines
Quoted 6 lines
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Next point of discussion must be PI .
Yes. lets discus PI. Lets discuss it forever so that we'll never get it ;)
Quoted 11 lines · Arjan van de Ven
Quoted 8 lines
Quoted 6 lines
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Next point of discussion must be PI .
Yes. lets discus PI. Lets discuss it forever so that we'll never get it ;)
You can always turn it off..
Daniel
Quoted 7 lines · Daniel Walker
Quoted 5 lines
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Next point of discussion must be PI. [...]
robustness is an orthogonal feature to Priority Inheritance. In fact it was requested before on lkml to separate robustness support from PI support, and the vma-based robust futex patches now do precisely that - they dont offer PI. So no, PI does not play here, it's a separate thing.
Ingo
Quoted 8 lines · Ingo Molnar
Quoted 6 lines · Daniel Walker
Quoted 5 lines
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Quoted 6 lines
Quoted 1 line
Next point of discussion must be PI. [...]
robustness is an orthogonal feature to Priority Inheritance. In fact it was requested before on lkml to separate robustness support from PI support, and the vma-based robust futex patches now do precisely that - they dont offer PI. So no, PI does not play here, it's a separate thing.
I was more interested in knowing if you considered it in the design.
Daniel
Quoted 8 lines · Ingo Molnar
...
E.g. in David Singleton's robust-futex-6.patch, there are 3 new syscall variants to
sys_futex():FUTEX_REGISTER,FUTEX_DEREGISTERandFUTEX_RECOVER. The kernel attaches such robust futexes to vmas (viavma->vm_file->f_mapping->robust_head), and atdo_exit()time, all vmas are searched to see whether they have arobust_headset.
hm. What happened if the futex was in anonymous memory (vm_file==NULL)?
Quoted 9 lines
New approach to robust futexes
------------------------------At the heart of this new approach there is a per-thread private list of robust locks that userspace is holding (maintained by glibc) - which userspace list is registered with the kernel via a new syscall [this registration happens at most once per thread lifetime]. At
do_exit()time, the kernel checks this user-space list: are there any robust futex locks to be cleaned up?
Neat.
Quoted 4 lines
...
The list is guaranteed to be private and per-thread, so it's lockless.
Why is that guaranteed?? Another thread could be scribbling on it while the kernel is walking it?
Why use a list and not just a sparse array? (realloc() works..)
Quoted 10 lines
There is one race possible though: since adding to and removing from the list is done after the futex is acquired by glibc, there is a few instructions window for the thread (or process) to die there, leaving the futex hung. To protect against this possibility, userspace (glibc) also maintains a simple per-thread '
list_op_pending' field, to allow the kernel to clean up if the thread dies after acquiring the lock, but just before it could have added itself to the list. Glibc sets thislist_op_pendingfield before it tries to acquire the futex, and clears it after the list-add (or list-remove) has finished.
Oh. I'm surprised that glibc cannot just add the futex to the list prior to acquiring it, then the exit-time code can work out whether the futex was really taken-and-contended. Even if the kernel makes a mistake it either won't find a futex there or it won't wake anyone up.
I think the patch breaks the build if CONFIG_FUTEX=n?
The patches are misordered - with only the first patch applied, the kernel won't build. That's a nasty little landmine for git-bisect users.
Why do we need sys_get_robust_list(other task)?
Quoted 4 lines · Andrew Morton
Quoted 3 lines · Ingo Molnar
...
Quoted 8 lines
Quoted 5 lines
E.g. in David Singleton's robust-futex-6.patch, there are 3 new syscall variants to
sys_futex():FUTEX_REGISTER,FUTEX_DEREGISTERandFUTEX_RECOVER. The kernel attaches such robust futexes to vmas (viavma->vm_file->f_mapping->robust_head), and atdo_exit()time, all vmas are searched to see whether they have arobust_headset.hm. What happened if the futex was in anonymous memory (vm_file==NULL)?
The primary focus of that patch AFAICT was to handle the inter-process robustness case - i.e. the named mapping case. Process-internal robustness was already offered by glibc. But there were also add-on patches IIRC that enabled "on-heap" robust futexes - which would be anonymous memory. I think the vma/address-space-based robust futex support patch was mainly limited by VM constraints: a new field in the vma was opposed, which reduced the utility of the patch.
This i think further underlines that the entire vma/address-space-based approach is faulty: IMO robustness should not be offered that deeply within the kernel - it should be attached to the real futex object itself - i.e. to the userspace lock.
Our patch unifies the two methods (intra-process and inter-process robust mutexes) in a natural way, and further improves process-internal robustness too: premature thread exits that happen without going though glibc [e.g. doing an explicit sys_exit syscall] are detected too.
Quoted 5 lines
Quoted 2 lines
The list is guaranteed to be private and per-thread, so it's lockless.
Why is that guaranteed?? Another thread could be scribbling on it while the kernel is walking it?
Yeah, glibc guarantees that the list is private. But the kernel does not trust the list in any case. If the list is corrupted (accidentally or deliberately) then there's no harm besides the app not working: the kernel will abort the list walk silently [or will wake up the wrong futexes - which userspace could have done too] and glibc wont get the proper futex wakeups, apps will hang, users will moan, userspace will get fixed eventually.
The kernel's list walking assumptions are not affected by whatever userspace activity - the kernel assumes the worst case: that Kevin Mitnick is sitting in another thread and trying to prod the kernel into allow him to do long-distance calls for free.
Quoted 1 line
Why use a list and not just a sparse array? (
realloc()works..)
this list is deep, deep within glibc. Glibc might even use robustness for some of its internal locks in the future, so i'd hate to make it dependent on a higher-level construct like realloc(). Nor is a sparse array necessary: a linked list within pthread_mutex_t is the fastest possible way to do this - we touch the pthread_mutex_t anyway, and the list head is in the Thread Control Block (TCB) - which is always cache-hot in these cases. All the necessary structure addresses are in registers already.
another problem is that the glibc-internal space at the TCB (which would be the primary place for such a lock-stack) is limited - so the lock stack would have to be allocated separately, adding extra indirection cost and complexity.
also, a sparse array is pretty much the same thing as a linked list - there's no fundamental difference between them, except that for lists it's easier to do circularity (which the kernel avoids too). [a sparse array can be circular too in theory: e.g. 32-bit userspace could map 4GB and the sparse index could overflow.] Pretty much the only fundamental difference is that such a sparse array would be in thread-local storage
- but that would also be a disadvantage.
also, there is no guarantee that unlocking happens in the same order as locking, so we'd force userspace into a O(N) unlocking design. The list based method OTOH still allows userspace to use a double-linked list.
so both are unsafe user-space constructs the kernel must not trust: a sparse array might point into (or iterate into) la-la land just as much as a list. The fastest and most lightweight solution, considering the existing internals of pthread_mutex_t, is a list.
Quoted 10 lines
Quoted 9 lines
There is one race possible though: since adding to and removing from the list is done after the futex is acquired by glibc, there is a few instructions window for the thread (or process) to die there, leaving the futex hung. To protect against this possibility, userspace (glibc) also maintains a simple per-thread '
list_op_pending' field, to allow the kernel to clean up if the thread dies after acquiring the lock, but just before it could have added itself to the list. Glibc sets thislist_op_pendingfield before it tries to acquire the futex, and clears it after the list-add (or list-remove) has finished.
Quoted 4 lines
Oh. I'm surprised that glibc cannot just add the futex to the list prior to acquiring it, then the exit-time code can work out whether the futex was really taken-and-contended. Even if the kernel makes a mistake it either won't find a futex there or it won't wake anyone up.
careful: while the 'held locks list' is per-thread and private, the pthread_mutex_t object is very much shared between threads and between processes! So the list op cannot be done prior acquiring the mutex.
after the mutex has been acquired, the list entry can be used in the private list - this thread is owning the lock exclusively. Similarly, at pthread_mutex_unlock() time, we must first remove ourselves from the private list, only then can we release the lock. (otherwise another thread could grab the lock and could corrupt the list)
but your suggestion would work with the sparse array based method: but having a list_op_pending field is really a non-issue - it's akin to having to fetch the current index of the sparse array [and having to search the array whether we have the right entry]. Arrays have other problems like size, and they are also a detached cacheline from the synchronization object - a list entry is more natural here.
Quoted 1 line
I think the patch breaks the build if
CONFIG_FUTEX=n?
ok, i'll fix this.
Quoted 3 lines
The patches are misordered - with only the first patch applied, the kernel won't build. That's a nasty little landmine for git-bisect users.
ok, i'll fix this too.
Quoted 1 line
Why do we need
sys_get_robust_list(other task)?
just for completeness for debuggers - when i added the TLS syscalls debugging people complained that there was no easy way to query the TLS settings of a thread. I didnt want to add yet another ptrace op - but maybe that's the right solution? ptrace is a bit clumsy for things like this - the task might not be ptrace-able, while querying the list head is such an easy thing.
Ingo
Quoted 8 lines · Ingo Molnar
Quoted 1 line
Why do we need
sys_get_robust_list(other task)?just for completeness for debuggers - when i added the TLS syscalls debugging people complained that there was no easy way to query the TLS settings of a thread. I didnt want to add yet another ptrace op - but maybe that's the right solution? ptrace is a bit clumsy for things like this - the task might not be ptrace-able, while querying the list head is such an easy thing.
If it isn't ptraceable, then why should we need to ask the kernel for a pointer into its memory? Except maybe for attacking it :-)
Signature · 2 lines
Daniel Jacobowitz CodeSourcery
Quoted 1 line · Ingo Molnar
This patchset provides a new (written from scratch) implementation of robust futexes, called "lightweight robust futexes". We believe this new implementation is faster and simpler than the vma-based robust futex solutions presented before, and we'd like this patchset to be adopted in the upstream kernel. This is version 1 of the patchset.
Thanks for such a detailed writeup and clean solution. Clearly a lot of time and effort. The code was nicely commented and easy to read.
There was a reference in the thread about Ulrich having some robust mutex tests, are those (or can they be made) publicly available?
Signature · 1 line
Darren Hart
Quoted 6 lines · Ingo Molnar
"Robustness" is about dealing with crashes while holding a lock: if a process exits prematurely while holding a
pthread_mutex_tlock that is also shared with some other process (e.g. yum segfaults while holding apthread_mutex_t, or yum is kill -9-ed), then waiters for that lock need to be notified that the last owner of the lock exited in some irregular way.
...
Quoted 6 lines
At the heart of this new approach there is a per-thread private list of robust locks that userspace is holding (maintained by glibc) - which userspace list is registered with the kernel via a new syscall [this registration happens at most once per thread lifetime]. At
do_exit()time, the kernel checks this user-space list: are there any robust futex locks to be cleaned up?
...
Quoted 3 lines
i've tested the new syscalls on x86 and
x86_64, and have made sure the parsing of the userspace list is robust [ ;-) ] even if the list is deliberately corrupted.
I've no knowledge about all this, and maybe I didn't get your description, so forgive me if I'm talking garbage.
Anyway: If a process can trash its robust futext list and then die with a segfault, why are the futexes still robust? In this case the kernel has no way to wake up waiters with FUTEX_OWNER_DEAD, or does it?
Johannes
Quoted 4 lines · Johannes Stezenbach
Anyway: If a process can trash its robust futext list and then die with a segfault, why are the futexes still robust? In this case the kernel has no way to wake up waiters with
FUTEX_OWNER_DEAD, or does it?
that's memory corruption - which robust futexes do not (and cannot) solve. Robustness is mostly about handling sudden death (e.g. which is due to oom, or is due to a user killing the task, or due to the application crashing in some non-memory-corrupting way), but it cannot handle all possible failure modes.
Ingo
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Johannes Stezenbach
Anyway: If a process can trash its robust futext list and then die with a segfault, why are the futexes still robust? In this case the kernel has no way to wake up waiters with
FUTEX_OWNER_DEAD, or does it?
Quoted 5 lines
that's memory corruption - which robust futexes do not (and cannot) solve. Robustness is mostly about handling sudden death (e.g. which is due to oom, or is due to a user killing the task, or due to the application crashing in some non-memory-corrupting way), but it cannot handle all possible failure modes.
I don't think this is a weakness in Dave or Inaky's versions. Dave
at least maintained the bulk of the information in kernel space. The uaddr was used for the fast locking in userspace, but not for maintaining the robustness .
Correct me if I'm wrong Dave.
Daniel
Quoted 10 lines · Daniel Walker
Quoted 6 lines · Ingo Molnar
that's memory corruption - which robust futexes do not (and cannot) solve. Robustness is mostly about handling sudden death (e.g. which is due to oom, or is due to a user killing the task, or due to the application crashing in some non-memory-corrupting way), but it cannot handle all possible failure modes.
Quoted 4 lines
I don't think this is a weakness in Dave or Inaky's versions. Dave
at least maintained the bulk of the information in kernel space. The uaddr was used for the fast locking in userspace, but not for maintaining the robustness .Correct me if I'm wrong Dave.
In the general case of memory corruption, the data protected by the robust futex might be corrupted, and no robust futex implementation can protect against that, In fact it's a lot more likely since the application code has pointers to the data but not to the robust list.
Signature · 1 line
Do not meddle in the internals of kernels, for they are subtle and quick to panic.
Quoted 8 lines · Ingo Molnar
Quoted 4 lines · Johannes Stezenbach
Anyway: If a process can trash its robust futext list and then die with a segfault, why are the futexes still robust? In this case the kernel has no way to wake up waiters with
FUTEX_OWNER_DEAD, or does it?
Quoted 5 lines
that's memory corruption - which robust futexes do not (and cannot) solve. Robustness is mostly about handling sudden death (e.g. which is due to oom, or is due to a user killing the task, or due to the application crashing in some non-memory-corrupting way), but it cannot handle all possible failure modes.
Hm, OK, from reading this and the other threads on this topic I get:
- there is a tradeoff between speed and robustness
- the focus for "robust futexes" is on speed (else they wouldn't deserve to be called futexes)
- thus it is acceptable if they are just 99% robust
That's OK, but IMHO it wouldn't hurt to clearly spell it out in the documentation.
However, this leaves the question: Is there a slower, but 100% robust alternative on Linux for applications which need it?
Johannes
Quoted 3 lines
However, this leaves the question: Is there a slower, but 100% robust alternative on Linux for applications which need it?
sysv semaphores probably count