This post documents my understanding on ABA problem in lockfree programming.

The wikipedia entry presents a concrete example on how ABA could occur in naive usage of CAS for lockfree programming. The step-by-step reproduce of erroneous situation is easy to follow even for those who have no prior C++ knowledge.

The intended logic for pop is to swing top from A to B:

1
2
3
top → A → B → C
    ↘
      B → C

However, right before the swing happens, the state of the stack is subject to change, which pop fails to capture, resulting into that B is pointed by the new top.

1
2
3
top → A → C
    ↘
      B → C

The illegal access to collected memory could be avoided if a GC is used instead of manual memory management, but the implementation is still problematic, for the CAS would put B in the stack again, even though it has been popped by thread 2.

It’s a common misconception that all ABA problems go away after using GC, and the example in the wiki page is a counter example.

On the other hand, it’s always possible to write lockfree code without ABA problem with GC, using one level of redirection. See more at https://www.research.ibm.com/people/m/michael/RC23089.pdf

The following is a lockfree stack implementation in C assuming a proper GC. It is ABA immune because for each element inserted into the stack, we create a wrapping node around it, and assumed GC wouldn’t reuse a node unless it’s unreachable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#define _atomic_cas(ptr, expected, desired) \
    __atomic_compare_exchange_n(ptr, expected, desired, \
            false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)

#define _atomic_load(ptr) \
    __atomic_load_n(ptr, __ATOMIC_SEQ_CST);

typedef struct node {
    void *data;
    struct node *next;
} node;

typedef struct stack {
    node *top;
} stack;

void* stack_pop(stack *s, void *d)
{
    void *data;
    do {
        node *t = _atomic_load(&s->top);
        if (!t) {
            return NULL;
        }
        node *next = t->next;
        if (_atomic_cas(&s->top, &t, next)) {
            data = t->data;
            // assuming GC takes care of t
            return data;
        }
    } while (true);
}

void stack_push(stack *s, void *d)
{
    node *new = malloc(sizeof *new);
    new->data = d;
    do {
        node *t = _atomic_load(&s->top);
        new->next = t;
        if (_atomic_cas(&s->top, &t, new)) {
            break;
        }
    } while (true);
}

From the same author, http://dl.acm.org/citation.cfm?id=987595 presents a alternative way to GC, so that ABA problems eliminated by GC would not appear using Hazard pointers as well.