Re: furwocks: Fast Userspace Read/Write Locks

["H. Peter Anvin" <hpa@zytor.com>]

Rusty Russell wrote:

> On 7 Mar 2002 12:17:52 -0800
> "H. Peter Anvin" <hpa@zytor.com> wrote:
> 
> 
>>Followup to:  <20020307191043.9C5F33FE15@smtp.linux.ibm.com>
>>By author:    Hubertus Franke <frankeh@watson.ibm.com>
>>In newsgroup: linux.dev.kernel
>>
>>>Take a look at Rusty's futex-1.2, the code is not that different, however
>>>if its all inlined it creates additional code on the critical path 
>>>and why do it if not necessary.
>>>
>>>In this case the futexes are the well tested path, the rest is a cludge on
>>>top of it.
>>>
>>>
>>Perhaps someone could give a high-level description of how these
>>"futexes" work?
>>
> 
> Certainly!  This is how Futexes IV (and Futexes V, ignoring the fairness
> stuff that adds) works:
> 
> One or more userspace processes share address space, so they can both do
> simple atomic operations on the same memory (hence the new PROT_SEM flag to
> mmap/mprotect for architectures which need to know).  They agree that "this
> address contains an integer which we use as a mutex" (aka. struct futex).
> 
> The futex starts at 1 (available).  down() looks like:
> 	if (atomic_dec_and_test(futex)) return 0; /* We got it! */
> 	else sys_futex(futex, DOWN); /* Go to kernel, wait. */
> 
> up() looks like:
> 	if (atomic_inc_positive(futex)) return 0; /* Noone waiting */
> 	else sys_futex(futex, UP); /* go to kernel, wake people */
> 
> Inside the kernel, we do what you'd expect.  For sys_futex(futex, DOWN):
> 	Pin the page containing the futex, for convenience.
> 	Hash the kernel address of the futex to get a waitqueue.
> 	Add ourselves to the waitqueue.
> 	While !atomic_dec_and_test() (ie. futex still unavailable):
> 		sleep
> 		if signal pending, break;
> 	Unhash from waitqueue
> 	unpin page.
> 	return success or -EINTR.
> 
> For sys_futex(futex, UP):
> 	Pin page for convenience.
> 	Hash kernel address of futex to get the waitqueue.
> 	set futex to 1 (ie. available).
> 	Wake up the first one on the waitqueue waiting for this futex.
> 	unpin page
> 
> The only two twists to add are that we don't keep atomic_dec_and_test'ing
> in the loop forever (if it's already negative we don't bother), so counter
> doesn't wrap, and we don't use actual waitqueues because we share them, but
> we want to know which futex each waiter is waiting on.
> 


Okay, dumb question...

What can this do that shared memory + existing semaphores can't do?

	-hpa