The ABA problem and tagged pointers

Compare-and-swap asks "is the value still what I read?" and cannot ask "was it changed and changed back?". On a lock-free stack that blind spot is the ABA problem: a swap succeeds on a stale idea of the stack and returns a value twice. Of 3,021 schedules of one pop against a churning thread, 21 corrupt the plain stack and none corrupts the tagged one.

A lock-free stack keeps its nodes in the shared dictionary: node i has a value val{i} and a link next{i} to the node below, and head names the top (-1 for empty). To push a node, read the head, point the new node's link at it, and swap the head from the value you read to the new node; if the swap fails, someone changed the head, so start over. To pop, read the head, read the link and the value of the top node, and swap the head from the node you read to its link. The pop that wins logs its value in popped. Each stack operation is a generator, and a thread runs it with yield from, which also hands back the returned value.

def make_stack(values, tagged=False):    top = 0 if values else -1    shared = {"head": (top, 0) if tagged else top, "popped": ()}    for i, value in enumerate(values):        shared["val%d" % i] = value        shared["next%d" % i] = i + 1 if i + 1 < len(values) else -1    return shareddef push(shared, node, value, tagged=False):    shared["val%d" % node] = value    while True:        yield        old = shared["head"]        yield        shared["next%d" % node] = old[0] if tagged else old        yield        new = (node, old[1] + 1) if tagged else node        if compare_and_swap(shared, "head", old, new):            returndef pop(shared, tagged=False):    while True:        yield        old = shared["head"]        idx = old[0] if tagged else old        if idx == -1:            return None        yield        nxt = shared["next%d" % idx]        value = shared["val%d" % idx]        yield        new = (nxt, old[1] + 1) if tagged else nxt        if compare_and_swap(shared, "head", old, new):            shared["popped"] = shared["popped"] + (value,)            return valuedef alone(shared):    def thread():        for _ in range(3):            print("popped", (yield from pop(shared)))    return [thread()]final, alive = run_prefix(alone, [0] * 20, make_stack([10, 20]))print(final["head"], final["popped"])

popped 10
popped 20
popped None
-1 (10, 20)

Alone, the stack is an ordinary stack: the pops return 10, 20 and then None, and the head is back to -1. Everything depends on what happens when another thread works between the three reads of a pop and its swap.

Here is the trap. A victim thread starts a pop: it reads head = 0 (node A) and the link next0 = 1 (node B), and is paused before its swap. A churner thread then pops A, pops B, and pushes node 0 back with a new value 99, so head is 0 again, with nothing below it. The victim wakes up. Its compare-and-swap asks only whether head is still 0, and it is, so the swap succeeds and installs node 1 as the head, a node that is no longer in the stack. We follow the schedule [0, 0], then nine turns of the churner, then the victim, and check the result with conserved: the values popped plus the values left on the stack must be exactly the values that were put in.

def walk(shared, tagged=False):    values = []    idx = shared["head"][0] if tagged else shared["head"]    while idx != -1 and len(values) < 10:        values.append(shared["val%d" % idx])        idx = shared["next%d" % idx]    return valuesdef conserved(shared, expected, tagged=False):    return sorted(list(shared["popped"]) + walk(shared, tagged)) == sorted(expected)def aba_program(tagged=False):    def make_threads(shared):        def victim():            yield from pop(shared, tagged)        def churner():            yield from pop(shared, tagged)            yield from pop(shared, tagged)            yield from push(shared, 0, 99, tagged)        return [victim(), churner()]    return make_threadsprefix = [0, 0] + [1] * 9 + [0]final, alive = run_prefix(aba_program(), prefix, make_stack([10, 20]))print(final)print("still on the stack:", walk(final), "| conserved:", conserved(final, [10, 20, 99]))

{'head': 1, 'popped': (10, 20, 10), 'val0': 99, 'next0': -1, 'val1': 20, 'next1': -1}
still on the stack: [20] | conserved: False

The victim returned 10, which the churner had already popped (popped: (10, 20, 10)), the head is node 1 although value 20 was popped too, so 20 is on the stack and in popped, and the new value 99 is lost. conserved says False. A lost update, a duplicated value and a node that should not exist: all from a swap that was "correct" for the value it compared.

The repair is to make the head carry its own history. In the tagged pointer version head is a pair (node, tag), and every successful push or pop swaps it for (new node, tag + 1). The compare-and-swap now compares both fields, so the head (0, 3) that the churner leaves behind is not the (0, 0) that the victim read. The victim's swap fails, it counts one retry, reads the real stack, and pops 99. The same schedule, with the tag, ends correctly.

final, alive = run_prefix(aba_program(True), prefix, make_stack([10, 20], True))print(final["head"], "victim alive:", alive == [0])final, alive = run_prefix(aba_program(True), prefix + [0] * 6, make_stack([10, 20], True))print(final["popped"], walk(final, True), "| conserved:", conserved(final, [10, 20, 99], True))

(0, 3) victim alive: True
(10, 20, 99) [] | conserved: True

values = [int(round(float(c) * 100)) for c in load_bars()["close"].iloc[:2]]for tagged in (False, True):    outcomes = explore_all(aba_program(tagged), make_stack(values, tagged))    corrupt = sum(n for key, n in outcomes.items() if not conserved(dict(key), values + [99], tagged))    print("tagged" if tagged else "plain ", sum(outcomes.values()), "schedules,", corrupt, "corrupt")

plain  3021 schedules, 21 corrupt
tagged 3021 schedules, 0 corrupt

Twenty-one schedules in 3,021 is less than 1%. A stress test on a real machine could run for days and never hit one, and then fail once in production. The explorer lists them all, and the tag removes all of them.

The lab follows the lecture: the stack in the shared dictionary, push and pop with a compare-and-swap loop (plain and tagged), a walk of the stack, the conservation check, the ABA program of a victim and a churner, and the study of both stacks over every schedule on two SPY closes.

• Function · questionBuilds on
• make_stack(values, tagged)What does the shared stack look like?Plain arithmetic
• push(shared, node, value, tagged)How does a node go on?Plain arithmetic
• pop(shared, tagged)How does a value come off?Plain arithmetic
• walk(shared, tagged)What is on the stack?Plain arithmetic
• conserved(shared, expected, tagged)Was anything lost or duplicated?walk
• aba_program(tagged)What does the ABA trap look like?poppush
• study(bars)How many schedules does the tag save?make_stackaba_programconserved

Next topic: a stack is one head. A queue needs two ends and many threads at each. Multi-producer multi-consumer queues build a bounded queue in which producers and consumers claim a ticket with fetch-and-add and each slot carries a sequence number, and the explorer checks it over every schedule.