From owner-freebsd-current@FreeBSD.ORG Thu May 22 22:14:52 2003 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id A842B37B401; Thu, 22 May 2003 22:14:52 -0700 (PDT) Received: from bluejay.mail.pas.earthlink.net (bluejay.mail.pas.earthlink.net [207.217.120.218]) by mx1.FreeBSD.org (Postfix) with ESMTP id DF68143F93; Thu, 22 May 2003 22:14:51 -0700 (PDT) (envelope-from tlambert2@mindspring.com) Received: from user-38lc10p.dialup.mindspring.com ([209.86.4.25] helo=mindspring.com) by bluejay.mail.pas.earthlink.net with asmtp (SSLv3:RC4-MD5:128) (Exim 3.33 #1) id 19J4tG-0006mm-00; Thu, 22 May 2003 22:14:51 -0700 Message-ID: <3ECDAE05.E5D02A2B@mindspring.com> Date: Thu, 22 May 2003 22:13:41 -0700 From: Terry Lambert X-Mailer: Mozilla 4.79 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: John Baldwin References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-ELNK-Trace: b1a02af9316fbb217a47c185c03b154d40683398e744b8a46c1befd355a0d114fdbe8b49fe58cf4b667c3043c0873f7e350badd9bab72f9c350badd9bab72f9c cc: Robert Watson cc: re@FreeBSD.org cc: current@FreeBSD.org Subject: Re: 5.1-RELEASE TODO X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 23 May 2003 05:14:53 -0000 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