5.1-RELEASE TODO

[Terry Lambert]

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.

> > Introducing locks introduces "expensive atomic operations and memory
> > barriers"; redoing it introduces an extra function call of overhead
> > that doesn't matter and is less expensive.
> 
> Since the locks are only used on shared lists, they aren't present on
> lists that don't need protecting, whereas doing them in the queue macros
> itself would pessimize all lists, unless you want to have a runtime
> check and function call.  Also, one thing you clearly have not noticed
> is that locks that cover lists usually also cover several other members of
> a related data structure, so you often need the lock anyways while you
> manipulate several data members of a structure.

These aren't list locks, these are locks on data structures
containing lists.  That's a very different thing.

Are you trying to claim here that I can't get atomic pointer
updates?

> > 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.

You don't have to worry about multiple updates in this case,
because all updates are identical; it's not like you are
contending to point a symbol one place, and some other CPU
is contending to point it another; you are *both* trying to
point it to the *same* place.  So if you start pointing for
you and someone else starts pointing for them, as long as
the pointer points to *either* the "repoint thunk" *OR*
"the right place", atomically, you don't really give a damn
if you update it out from under somone, or they update it
out from under you: it gets the same *right* value before it
is used.

-- Terry