with Header for now, the following is
an ABA problem scenario starting with
a list that includes blocks A and B:
a. A thread P reads the value A from
Header in line 1 and B from *A in line 2;
b. Other threads pop blocks A and
B and push blocks C and A, leaving
Header holding the value A again;
c. P performs a CAS operation on
Header with parameters A and B in
line 3, and the CAS succeeds.
Now the list is corrupted. Header
points to B, which is not in the list anymore. What went wrong is that (without
the packed integer) P’s Pop algorithm
cannot differentiate between the case
where Header never changed between
lines 1 and 3 and this scenario where
the list changed but Header returned
to its old value before the CAS in line 3.
The classic LIFO algorithm packs an
integer with the pointer in the Header
variable and is designed such that the
counter will change if the list changes
between lines 1 and 3 of Pop (assuming
that the counter never overflows).
Packing an integer with the main
content of variables vulnerable to the
ABA problem is the classic ABA prevention solution. 2 It remained the
only solution for decades, but it has
its limitations. It requires wide atomic
operations to allow space for a large
enough integer that cannot overflow
(at least cannot overflow in the lifetime of one operation, such as Pop in
the example). Another disadvantage
of this solution is that it requires the
integer subfield to retain its semantics
indefinitely. This can make it very difficult to free the memory of dynamic
blocks that include variables packed
with ABA-prevention counters, thus
meaning memory cannot be coalesced
or reused for different purposes.
Although the ABA problem can
occur in algorithms that do not use
dynamic memory, its solutions are
intertwined with safe memory reclamation solutions. First, as already
mentioned, the classic ABA solution
can hinder memory reclamation.
Second, any memory-safety solution
(GC, RCU, reference counting, hazard pointers) can be adapted to construct an ABA solution, possibly with
an added level of indirection.
An advantage of the RCU type of so-
lution is that traversal operations have
almost no overhead, while reference
counting and hazard pointers have
nontrivial overhead for traversal opera-
tions. On the other hand, unlike RCU,
reference counting and hazard-pointer
methods guarantee bounds on the
number of removed blocks that are not
ready for reuse.
A disadvantage of reference counting that can be significant in some
cases is that it can cause a supposedly
read-only operation (such as the check
operation mentioned earlier) to actually write to shared data ( reference counters) and prevent update operations
from ever completing.
The operations LL (load-linked),
SC (store-conditional), and VL (
validate) are inherently immune to the
ABA problem. LL(location) returns the value in a shared location.
VL(location) returns a Boolean indicator of whether or not the shared
location has not been written by another thread since the last LL to it by
the current thread. SC(location,
value) writes a new value to the location if and only if it has not been
written by another thread since it was
last LL’ed to it by the current thread,
and it returns a Boolean indicator of
the occurrence of such a write. If the
read in line 1 of Pop is replaced with
LL(&Header) and the CAS in line 3 of
Pop is replaced with SC(&Header,n),
then the Pop operation would be immune to the ABA problem, without the
need for using a packed integer.
Actual architectures that support
LL/SC (for example, IBM Power PC) do
not support the full semantics of ideal
LL/SC/VL. None supports the VL op-
eration, and all impose restrictions on
what can be executed between LL/SC
and prohibit the nesting or interleaving
of LL/SC pairs on different locations.
So, while actual LL/SC support can help
the lock-free LIFO algorithm avoid the
ABA problem, it is limited in preventing
the ABA problem in general.
While implementations of ideal LL/
SC/VL present an absolute ABA prevention solution, 18 their strong semantics
disallow many correct scenarios. For
example, all ABA scenarios in the lock-free LIFO-list Push operation are benign. Therefore, it is advisable to consider algorithms expressed in terms of
reads and CAS operations, and address
only the harmful cases of ABA, such as
Pop but not Push in the lock-free LIFO-list algorithm.
It is advisable to consider ABA prevention and safe memory reclamation
solutions together to avoid unnecessary duplication of overhead or solutions that are contradictory or contrary
to the overall system requirements.
Portability of required atomic operations. The range of hardware support for atomic operations needed for
nonblocking algorithms and methods varies significantly. If portability
is an important issue, designers need
to take that into account in selecting data structures, algorithms, and
supporting methods for safe memory
reclamation and management, and
figure 2. Data structure requirements.