lkml.org 
[lkml]   [1999]   [Jan]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: MM deadlock [was: Re: arca-vm-8...]
Linus Torvalds wrote:
>
> On Mon, 11 Jan 1999, MOLNAR Ingo wrote:
> >
> > ps. not that it counts too much, but my embarrasing email brought me to
> > really closely check all the semaphore code again, and it seems to be
> > all really cool and accurate. I've 'unfolded' the code into pseudocode
> > by hand:
>
> The not cool part about my implementation of recursive semaphores is:
>
> CPU #1 CPU#2
>
> down()
> ..
> up()
>
> "owner" is P#1, count=1
>
> down() down()
> lock ; decl succeeds
>
> lock ; decl fails
> goto slow part
> slow part sees stale owner
> returns success
>
> "owner" is P#2
>
> BOOM! - both CPU's are now inside the critical region.
>
> The problem is that "owner" can be stale, and can be updated outside the
> semaphore spinlock by a successful down() - which means that there are no
> synchronizing primitives there to guarantee that the slow part sees the
> new owner.
>
> Now, setting the new owner is done in the very next instruction after
> getting the semaphore, so CPU#1 has to be really fast, and CPU#2 has to be
> really slow for the above to happen. But it's still possible, and CPU#2
> taking an interrupt could cause that to happen.
>
> And I don't see any way of getting rid of it without another spinlock. I
> _could_ possibly do it with something like
>
> up(sem) {
> if (!sem.count)
> sem.owner = 0;
> old_up();
> }
>
> but I can't convince myself that that always works either.
>
> Linus

I have attached a figure (I prefer postscript over ascii figures; I
appologize if this means any inconveniences) describing a capability
based automatic serializing semaphore mechanism. It involves self
modifying code (even though I think it can be done without self
modifying code on some architectures), so you may not like it, and
because of various cache issues it may not even work on many
architectures at all. I did look up (hopefully all) the relevant
sections in the x86 architecture specifications though and I think it
should work there (I'm not an x86 expert though).

The cycle of operation is something along the following lines:
- semaphore starts in state 1: the contents of the semaphore is the
'atomic modify' instruction
- the first process(or) enters the semaphore, immediatelly modifies it
to a loop (state 2) and continues to execute the protected code
- the second (and other) process(or) enters the semaphore; because the
modification of the semaphore was atomic, it gets a 'jump' instead of
'atomic modify'; it starts spinning in a busy loop
- the first process(or) exits the protected code and modifies the
semaphore back to the original state (when the contents of the semaphore
was the 'atomic modify' instruction)
- the second (or some other) process(or) hits the 'atomic modify'
instruction and drops out of the loop, then immediatelly modifies the
semaphore back to loop so that others don't escape
- etc

I hope this mail is not a shot in the dark since I haven't been
following this thread all the way (so I don't know whether the 'owner'
stuff that you mentioned is relevant and necessary in the semaphore). If
it is, please ignore it.

Andrej

--
Andrej Presern, andrejp@luz.fe.uni-lj.si
[unhandled content-type:application/x-gzip]
\
 
 \ /
  Last update: 2005-03-22 13:49    [from the cache]
©2003-2011 Jasper Spaans