Re: 2.4.7-pre9..

From: Matthew Dharm (
Date: Fri Jul 27 2001 - 14:47:36 EST

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.


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

- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to More majordomo info at Please read the FAQ at

This archive was generated by hypermail 2b29 : Tue Jul 31 2001 - 21:00:35 EST