From owner-freebsd-net Mon Jul 15 10:36:32 2002 Delivered-To: freebsd-net@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id E732137B6F9 for ; Mon, 15 Jul 2002 10:35:56 -0700 (PDT) Received: from kali.avantgo.com (shadow.avantgo.com [64.157.226.66]) by mx1.FreeBSD.org (Postfix) with ESMTP id DF866442A2 for ; Mon, 15 Jul 2002 10:23:20 -0700 (PDT) (envelope-from scott@avantgo.com) Received: from river.avantgo.com ([10.11.30.114]) by kali.avantgo.com with Microsoft SMTPSVC(5.0.2195.3779); Mon, 15 Jul 2002 10:23:11 -0700 Date: Mon, 15 Jul 2002 10:20:06 -0700 (PDT) From: Scott Hess To: Bosko Milekic Cc: Jon Mini , Subject: Re: mbuf external buffer reference counters In-Reply-To: <20020712074507.B75547@unixdaemons.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 15 Jul 2002 17:23:11.0404 (UTC) FILETIME=[4B540EC0:01C22C24] Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org 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. You threw out a logic problem 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 majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message