Re: 2.4.7-pre9..

[Matthew Dharm <mdharm-kernel@one-eyed-alien.net>]

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

Hrm... just to be clear, then... this only is a problem with semaphores
that are declared on the local stack?

IIRC, usb-storage only uses semaphores that are allocated via kfree, so I
think we're okay.  Tho, I think the new semantics are probably better, and
will probably switch to them.  Later.

Matt

On Fri, Jul 27, 2001 at 10:46:44AM -0700, Linus Torvalds wrote:
> 
> On Fri, 27 Jul 2001, Matthew Dharm wrote:
> >
> > It looks like I missed an important discussion in the torrent of e-mail
> > that I receive... could someone give me the 30-second executive summary so
> > I can look at what may need to change in usb-storage?
> 
> The basic summary is that we had this (fairly common) way of waiting for
> certain events by having a locked semaphore on the stack of the waiter,
> and then having the waiter do a "down()" which caused it to block until
> the thing it was waiting for did an "up()".
> 
> This works fairly well, _but_ it has a really small (and quite unlikely)
> race on SMP, that is not so much a race of the idea itself, as of the
> implementation of the semaphores. We could have fixed the semaphores, but
> there were a few reasons not to:
> 
>  - the semaphores are optimized (on purpose) for the non-contention case.
>    The "wait for completion" usage has the opposite default case
>  - the semaphores are quite involved and architecture-specific, exactly
>    due to this optimization. Trying to change them is painful as hell.
> 
> So instead, I introduced the notion of "wait for completion":
> 
> 	struct completion event;
> 
> 	init_completion(&event);
> 	.. pass of event pointer to waker ..
> 	wait_for_completion(&event);
> 
> where the thing we're waiting for just does "complete(event)" and we're
> all done.
> 
> This has the advantage of being a bit more obvious just from a syntactic
> angle about what is going on. It also ends up being slightly more
> efficient than semaphores because we can handle the right expected case,
> and it also avoids the implementation issue that made for the race in the
> first place.
> 
> Switching over to the new format is really trivial:
> 
>  struct semaphore	-> struct completion
>  init_MUTEX_LOCKED	-> init_completion
>  DECLARE_MUTEX_LOCKED	-> DECLARE_COMPLETION
>  down()			-> wait_for_completion()
>  up()			-> complete()
> 
> and you can in fact maintain 2.2.x compatibility by just having a 2.2.x
> compatibility file that does the reverse mappings.
> 
> In case anybody cares, the race was that Linux semaphores only protect the
> accesses _inside_ the semaphore, while the accesses by the semaphores
> themselves can "race" in the internal implementation. That helps make an
> efficient implementation, but it means that the race was:
> 
> 	cpu #1				cpu #2
> 
> 	DECLARE_MUTEX_LOCKED(sem);
> 	..
> 	down(&sem);			up(&sem);
> 	return;
> 					wake_up(&sem.wait) /*BOOM*/
> 
> where the waker still touches the semaphore data structure after the
> sleeper has become happy with it no longer being locked - and free'd the
> data structure by virtue of freeing the stack.
> 
> 		Linus

-- 
Matthew Dharm                              Home: mdharm-usb@one-eyed-alien.net 
Maintainer, Linux USB Mass Storage Driver

Hey Chief.  We've figured out how to save the technical department.  We 
need to be committed.
					-- The Techs
User Friendly, 1/22/1998

[-- Attachment #2: Type: application/pgp-signature, Size: 232 bytes --]