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_at_ list? Assuming symbol lookup is indeed this simple, then I agree that this algorithm seems sound to me. -- John Baldwin <jhb_at_FreeBSD.org> <>< http://www.FreeBSD.org/~jhb/ "Power Users Use the Power to Serve!" - http://www.FreeBSD.org/Received on Thu May 22 2003 - 08:00:31 UTC
This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:37:08 UTC