From: John Baldwin (
Date: 05/22/03

  • Next message: Sid Carter: "Buildworld failure - at libufs.a"
    Date: Thu, 22 May 2003 13:00:39 -0400 (EDT)
    To: Terry Lambert <>

    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 <>  <><
    "Power Users Use the Power to Serve!"  -
    _______________________________________________ mailing list
    To unsubscribe, send any mail to ""

  • Next message: Sid Carter: "Buildworld failure - at libufs.a"