together/hazptr.tex

% together/hazptr.tex
% mainfile: ../perfbook.tex
% SPDX-License-Identifier: CC-BY-SA-3.0

\section{Hazard-Pointer Helpers}
\label{sec:together:Hazard-Pointer Helpers}
%
\epigraph{It's the little things that count, hundreds of them.}
	 {Cliff Shaw}

This section looks at some issues that can be addressed with the
help of hazard pointers.
In addition, hazard pointers can sometimes be used to address the
issues called out in \cref{sec:together:RCU Rescues}, and vice versa.

\subsection{Scalable Reference Count}
\label{sec:together:Scalable Reference Count}

Suppose a reference count is becoming a performance or scalability
bottleneck.
What can you do?

One approach is to instead use \IXpl{hazard pointer}.

There are some differences, perhaps most notably that with
hazard pointers it is extremely expensive to determine when
the corresponding reference count has reached zero.

One way to work around this problem is to split the load between
reference counters and hazard pointers.
Each data element has a reference counter that tracks the number
of other data elements referencing this element on the one hand,
and readers use hazard pointers on the other.

Making this arrangement work both efficiently and correctly can be
quite challenging, and so interested readers are invited to examine
the UnboundedQueue and ConcurrentHashMap data structures implemented in
Folly open-source library.\footnote{
	\url{https://github.com/facebook/folly}}

\subsection{Long-Duration Accesses}
\label{sec:together:Long-Duration Accesses}

Suppose a reader-writer-locking reader is holding the lock for so
long that updates are excessively delayed.
If that reader can reasonably be converted to use reference counting
instead of reader-writer locking, but if performance and scalability
considerations prevent use of actual reference counters, then hazard
pointers provides a scalable variant of reference counting.

The key point is that where reader-writer locking readers block all
updates for that lock, hazard pointers instead simply hang onto the
data that is actually needed, while still allowing updates to proceed.

If the reader cannot be reasonably be converted to use reference
counting, the tricks in \cref{sec:together:Long-Duration Accesses Two}
might be helpful.

% @@@ papers to maybe cite: OrcGC, ThreadScan, Fast and Robust Memory...

% @@@ Generalized hazard-pointer link counts, if and when.

% @@@ Representative hazard pointer for list, so that nothing
% @@@ in list gets freed until list's hazard pointer is released.
% @@@ Midpoint between hazard pointers and RCU, in fact, you
% @@@ could argue that Tasks Trace RCU with read-side memory
% @@@ barriers is sort of a per-CPU hazard pointers implementing RCU.
% @@@ Except no re-checking because CPUs cannot be freed.