Re: 5.1-RELEASE TODO

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_at_ 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