On Fri, 12 Jul 2002, Bosko Milekic wrote:
> On Fri, Jul 12, 2002 at 04:26:53AM -0700, Jon Mini wrote:
> > I'm probably speaking out of turn here (I have no idea what structure
> > you all are talking about), but a monodirectional ring can be safely
> > modified with a compare-and-exchange atomic operation.
>
> The jist of the problem is that when you want to say, remove yourself
> from the list, you have to:
>
> 1) your "next"'s back pointer to your "back" pointer
> 2) your "Prev"'s next pointer to your "next" pointer
>
> So that's two operations but for all you know your "next" or your
> "back" may be doing the same thing to you at the same time. As far as
> I know, you can't (intuitively) figure out a way to do both of these
> atomically. i.e., maybe you'll set your next's back pointer to whatever
> you have in `back' but then your `back' guy will set your back pointer
> to whatever he has in `back' and then your next guy's back pointer will
> be invalid, for example.
<offtopic>You threw out a logic problem</offtopic>
The following came to mind, though I've not quite been able to fully think
through all possibilities, yet (C psuedo-code, because I am not up-to-date
on my assembly. Comments assume a list A<->B<->C<-^, B being deleted):
r1=prev;
// If prev!=r1, A was deleted during the race.
prev=0 iff prev==r1; // atomic test-and-set.
r2=next;
// If next!=r2, C was deleted during the race.
next=0 iff next==r2;
// If r2->prev!=self, then the C is in delete.
r2->prev=r1 iff r2->prev==self;
// At this point, if C attempted a delete, the delete code would
// notice that C->prev->next != C (it is still B).
// If r1->next!=self, then the A is in delete.
r1->next=r2 iff r1->next==self;
Storing the 0's locks against deletes from the neighbors. The failure
cases for the first three exchanges (X=Y iff X==Z) are pretty
straightforward, and I think can be safely unwound.
The fourth failure case is interesting, though, because I _think_ that if
you correctly code the failure cases, you can try to run 'r1->next=r2 iff
r1->next==0;' to salvage it. It's possible that there's a way of coding
things which would always allow one of two conflicting threads to proceed,
so that spinning on failure is sensible. I can't quite see it, though.
I have no idea what the performance implications of this are. AFAICT, you
would require 3 locks to accomplish this correctly (self, next, prev *),
which implies 6 total exchanges. Also, I haven't considered the insert
case, though I'm not sure why it wouldn't simply invert the
ordering of the delete.
(*) Hmm. I thought you could do two (Lock self, lock next,
prev->next=next, next->prev=prev, unlock next, delete self), but then
realized that there was a race between finding next and applying the lock.
So you need all three.
Later,
scott
To Unsubscribe: send mail to [EMAIL PROTECTED]
with "unsubscribe freebsd-net" in the body of the message
