Re: [PATCH] Lightweight userspace semphores...

[Hubertus Franke <frankeh@watson.ibm.com>]

On Wed, Feb 27, 2002 at 06:17:41PM +0100, Martin Wirth wrote:
> Hubertus Franke wrote:
> 
> > Again, the trick is to not
> > sync the state of the kernel and the user level. It comes naturally 
> > if you properly separate the duties.
> > 
> 
> Your code for usema_down is simply:
> 
> int usema_down(ulock_t *ulock)
> {
> 	if (!__ulock_down(ulock)) {
> 		return 0;
> 	}
> 	return ulock_wait(ulock,0);
> }
> 
> This means you do not recheck if the usema is really available after you 
> return form ulock_wait(), but you may have the following situtation:

Not so. First remember the following:

__ulock_down is basically an 
	atomic_dec(&lockword) and returns 0 if lockword after decrement
        is < 0. 

__ulock_up   is basically a
	atomic_inc(&lockword) and returns 0 if lockword after increment
	is >= 0.

After each line I print the value of the lockword after the atomic op.
I assume initial value was "1". Initial value of kernel semaphore is "0".
Let's write this as [ 1, 0 ] state (user,kernel).

> 
> Process 1             Process 2                        Process 3
>   down
    [ 0, 0 ]
> 
>                        down
	                 [ -1, 0 ]
>                          -> call usema_wait
>                          but gets preempted shortly
>                          before it
>                          can enter kernel mode
> 
>   up
    [ 0, 0 ] now signal the kernel but nobody waiting on it yet
    [ 0, 1 ] kernel stores the signal token in its state
>    (kernel sema is free)
    [ 0, 1 ] kernel stores the signal token in its state
> 
>                                                           down -> got it
						(not so........ )
						[-1,1]
						you don't have the lock
						as __ulock_down return !=0
						you are going to call the 							kernel ulock_wait	
	
Two scenarios now:  either P3 get's there first to the kernel or P2.
P3 first.

						[-1,1] (start state from above)
						wait in kernel is through down
						that will succeed and eat 
						the kernel sem token and
						continue out of kernel
						holding the lock
						[-1,0]

			P2 rescheduled..
			down in the kernel
			will block the process
			[ -1, -1 ]

P2 first, assuming that P3 too got preempted before the kernel call 
		("Shit Happens", Forrest Gump)

		
			[-1,1] (start state from above)
			wait in kernel is through down
			that will succeed and eat 
			the kernel sem token and
			continue out of kernel
			holding the lock
			[-1,0]

						P3 rescheduled..
						down in the kernel
						will block the process
			[ -1, -1 ]


Any UP call now will ditch into the kernel and signal the waiting process
to continue, handing the lock over to it.
			[ 0, 0 ]
> 
> 
>                        resume execution,
>                        thinks its also got it
>                        because kernel sema is free!

So, it works and is correct. Hope that clarifies it, if not let me know.
Interestingly enough. This scheme doesn't work for spinning locks.
Goto lib/ulocks.c[91-133], I have integrated this dead code here
to show how not to do it. A similar analysis as above shows
that this approach wouldn't work. You need cmpxchg for these scenarios
(more or less).

> 
> Now you have two owners!!
> 

Not so,  QED.

> 
> Martin Wirth
> 
> 

-- Hubertus Franke 		(frankeh@watson.ibm.com)

>