5.1-RELEASE TODO

[John Baldwin]

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 at FreeBSD.org>  <><  http://www.FreeBSD.org/~jhb/
"Power Users Use the Power to Serve!"  -  http://www.FreeBSD.org/