Handling large numbers of hazard pointers

["Paul E. McKenney" <paulmck@kernel.org>]

Hello!

I didn't do a good job of answering the "what about large numbers of
hazard pointers" at Boqun's and my hazard-pointers talk at Linux Plumbers
Conference yesterday, so please allow me to at least start on the path
towards fixing that problem.

Also, there were a couple of people participating whose email addresses
I don't know, so please feel free to CC them.

The trick is that in real workloads to date, although there might be
millions of hazard pointers, there will typically only be a few active
per CPU at a given time.  This of course suggests a per-CPU data structure
tracking the active ones.  Allocating a hazard pointer grabs an unused one
from this array, or, if all entries are in use, takes memory provided by
the caller and links it into an overflow list.  Either way, it returns a
pointer to the hazard pointer that is now visible to updaters.  When done,
the caller calls a function that marks the array-entry as unused or
removes the element from the list, as the case may be.  Because hazard
pointers can migrate among CPUs, full synchronization is required when
operating on the array and the overflow list.

And either way, the caller is responsible for allocating and freeing the
backup hazard-pointer structure that will be used in case of overflow.
And also either way, the updater need only deal with hazard pointers
that are currently in use.

Cue Mark telling me that his use case can have millions of active hazard
pointers?  ;-)

							Thanx, Paul