[patch 0/5] lightweight robust futexes: -V1

[patch 0/5] lightweight robust futexes: -V1

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

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Andi Kleen]

Ingo Molnar <mingo@elte.hu> writes:


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


> 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);

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Ulrich Drepper]

[-- Attachment #1: Type: text/plain, Size: 1837 bytes --]

Andi Kleen wrote:
> 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.


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


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

-- 
➧ Ulrich Drepper ➧ Red Hat, Inc. ➧ 444 Castro St ➧ Mountain View, CA ❖


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 251 bytes --]

Re: [patch 0/5] lightweight robust futexes: -V1

[Andi Kleen]

On Wednesday 15 February 2006 18:50, Ulrich Drepper wrote:
> Andi Kleen wrote:
> > 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.

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

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

> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Daniel Walker]

On Wed, 15 Feb 2006, Ingo Molnar wrote:

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Arjan van de Ven]

> > 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 ;)

Re: [patch 0/5] lightweight robust futexes: -V1

[Daniel Walker]

On Wed, 15 Feb 2006, Arjan van de Ven wrote:

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Christopher Friesen]

Andi Kleen wrote:
> On Wednesday 15 February 2006 18:50, Ulrich Drepper wrote:
>>Andi Kleen wrote:
>>
>>>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

Re: [patch 0/5] lightweight robust futexes: -V1

[Andi Kleen]

On Wednesday 15 February 2006 20:49, Christopher Friesen wrote:

> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Antonio Vargas]

On 2/15/06, Andi Kleen <ak@suse.de> wrote:
> On Wednesday 15 February 2006 20:49, Christopher Friesen wrote:
>
> > 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/
windNOenSPAMntw@gmail.com
thesameasabove@amigascne.org

Every day, every year
you have to work
you have to study
you have to scene.

Re: [patch 0/5] lightweight robust futexes: -V1

[Andi Kleen]

On Wednesday 15 February 2006 21:13, Antonio Vargas wrote:
> On 2/15/06, Andi Kleen <ak@suse.de> wrote:
> > On Wednesday 15 February 2006 20:49, Christopher Friesen wrote:
> >
> > > 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?

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Andi Kleen <ak@suse.de> wrote:

> On Wednesday 15 February 2006 18:50, Ulrich Drepper wrote:
> > Andi Kleen wrote:
> > > 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.

> 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
:-|

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

> > > 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:

> > > > 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:

> > > > 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 :-(

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Andi Kleen <ak@suse.de> wrote:

> On Wednesday 15 February 2006 20:49, Christopher Friesen wrote:
> 
> > 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Daniel Walker <dwalker@mvista.com> wrote:

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Andrew Morton]

Ingo Molnar <mingo@elte.hu> wrote:
>
> ...
>
> 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.

hm.   What happened if the futex was in anonymous memory (vm_file==NULL)?

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

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

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

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)?

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Andrew Morton <akpm@osdl.org> wrote:

> Ingo Molnar <mingo@elte.hu> wrote:
> >
> > ...
> >
> > 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.
> 
> 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.

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

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

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

> I think the patch breaks the build if CONFIG_FUTEX=n?

ok, i'll fix this.

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

> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Darren Hart]

Ingo Molnar wrote:
> 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?

-- 
Darren Hart

Re: [patch 0/5] lightweight robust futexes: -V1

[Johannes Stezenbach]

On Wed, Feb 15, 2006, Ingo Molnar wrote:
> "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.
...
> 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?
...
> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Daniel Walker]

On Wed, 2006-02-15 at 22:31 +0100, Ingo Molnar wrote:
> * Daniel Walker <dwalker@mvista.com> wrote:
> 
> > >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.

	I was more interested in knowing if you considered it in the design.

Daniel 

Re: [patch 0/5] lightweight robust futexes: -V1

[Ingo Molnar]

* Johannes Stezenbach <js@linuxtv.org> wrote:

> 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

Re: [patch 0/5] lightweight robust futexes: -V1

[Daniel Walker]

On Thu, 16 Feb 2006, Ingo Molnar wrote:

>
> * Johannes Stezenbach <js@linuxtv.org> wrote:
>
>> 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.

 	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

Re: [patch 0/5] lightweight robust futexes: -V1

[Avi Kivity]

Daniel Walker wrote:

> On Thu, 16 Feb 2006, Ingo Molnar wrote:
>
>>
>> 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.


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.

-- 
Do not meddle in the internals of kernels, for they are subtle and quick to panic.

Re: [patch 0/5] lightweight robust futexes: -V1

[Johannes Stezenbach]

On Thu, Feb 16, 2006, Ingo Molnar wrote:
> 
> * Johannes Stezenbach <js@linuxtv.org> wrote:
> 
> > 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.

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

Re: [patch 0/5] lightweight robust futexes: -V1

[Arjan van de Ven]

> However, this leaves the question: Is there a slower, but 100% robust
> alternative on Linux for applications which need it?


sysv semaphores probably count

Re: [patch 0/5] lightweight robust futexes: -V1

[Daniel Jacobowitz]

On Wed, Feb 15, 2006 at 11:14:34PM +0100, Ingo Molnar wrote:
> > 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 :-)

-- 
Daniel Jacobowitz
CodeSourcery