Date: Thu, 22 May 2003 13:00:39 -0400 (EDT) From: John Baldwin <jhb@FreeBSD.org> To: Terry Lambert <tlambert2@mindspring.com> Cc: current@FreeBSD.org Subject: Re: 5.1-RELEASE TODO Message-ID: <XFMail.20030522130039.jhb@FreeBSD.org> In-Reply-To: <3ECCFFD8.74A284C7@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 22-May-2003 Terry Lambert wrote: > John Baldwin wrote: >> On 22-May-2003 Terry Lambert wrote: >> > You don't care if another CPU re-does the work, so long as it >> > re-does it atomically. That makes it thread safe without the >> > introduction of locks. >> >> We aren't talking about re-doing the work, we're talking about one >> CPU trying to walk the list while it's an inconsistent state and >> walking off into the weeds through a stale pointer. I.e, CPU 0 >> removes an item from the list while CPU 1 is walking over that item. >> Duh. > > 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. >> > Just because your friend jumped off a cliff... >> >> So what is your magic solution for making rtld thread-safe when >> looking up unresolved symbols on first reference? > > 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. -- John Baldwin <jhb@FreeBSD.org> <>< http://www.FreeBSD.org/~jhb/ "Power Users Use the Power to Serve!" - http://www.FreeBSD.org/
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?XFMail.20030522130039.jhb>