Date: Thu, 22 May 2003 22:13:41 -0700 From: Terry Lambert <tlambert2@mindspring.com> To: John Baldwin <jhb@FreeBSD.org> Cc: current@FreeBSD.org Subject: Re: 5.1-RELEASE TODO Message-ID: <3ECDAE05.E5D02A2B@mindspring.com> References: <XFMail.20030522130039.jhb@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
John Baldwin wrote: > On 22-May-2003 Terry Lambert wrote: > > A singly linked list can be maintained in a consistent state > > at all times, so long as pointer updates are atomic to a CPU. > > > > As I said before, this is an order of operation problem, not > > a locking problem. > > For a single linked-list, yes. For doubly-linked lists (which is what > I primarily had in mind since most structures I've worked with use > LIST and TAILQ rather than SLIST or STAILQ) it is a different matter. I never claimed otherwise; though there are certain situations that can be optimized (e.g. multiple writer, single reader, test for existance of any records, etc.), which really depend on the algorith,m that's appropriate to your situation (e.g. co-queueing vs. doubly linked lists, push-rather-than-pull, etc.). > > Change the order of operation. Basic database theory: > > > > o write new record > > o atomically update index to point from old > > record to new record > > o remove old record > > > > No matter how many time you reenter this, you end up with a > > consistent view. > > Have you brought this up on the threads@ list? Assuming symbol > lookup is indeed this simple, then I agree that this algorithm > seems sound to me. It's even simpler, actually. There's no remove involved; all it does is replace a pointer in a jump table; the problem is, it does it before it's ready, instead of afterward, so a reentrancy gets a bad target. Do the pointer set last, and the problem goes away. Yeah, I've brought it up before. If I had the time, I'd just do the implementation myself, but I don't currently have it. -- Terry
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3ECDAE05.E5D02A2B>