Is ABA relevant for push/insertion operations when using the CAS idiom?

Question

The following pseudo-code is taken from http://15418.courses.cs.cmu.edu/spring2013/article/46

while (1) {
  n->next = p->next;
  Node *old_next = p->next;
  if (compare_and_swap(&p->next, old_next, n) == old_next)
    return;
}

This is the push operation for a lock-free stack that uses the compare and swap idiom, but does it atomically. It does not seem an ABA issue is relevant here, and I am wondering if that's generally the case for push and insertion operations?

Answer 1

You are right that this function does not suffer from the ABA problem, because there is nothing that depends on the old_next value before the call to compare_and_swap.

Consider the (simplified) pop operation:

  while (1) {
    Node *top = s->top;
    if (top == NULL)
      return NULL;
    Node *new_top = top->next;
    if (compare_and_swap(&s->top, top, new_top);
      return top;
  }
}

Here we load s->top into top and later perform a CAS on s->top with top as expected value. But before the CAS, we read top->next, so we perform an operation that depends on top! This is what causes the ABA problem.

It is not possible to generally state that all push/insert operations are free of the ABA problem, since it depends on more details. As a somewhat contrived example, consider a push operation that conditionally pushes the value only if it is greater.

while (1) {
  n->next = p->next;
  Node *old_next = p->next;
  if (n->value < old_next->value)
    return;
  if (compare_and_swap(&p->next, old_next, n) == old_next)
    return;
}

This also suffers from the ABA problem, because it might break our invariant that the values are strictly ordered.

Answer 2

There is no ABA issue with this code, but that's really because it doesn't do very much.

The problem is fundamentally that you use compare_and_swap(&p->next, old_next, n) to make sure that the stack hasn't changed since you last looked at it, but it does not reliably do that.

Between the time you read n->next and the time you do the compare_and_swap, other threads could have:

1. Popped n->next
2. Pushed a bunch of other stuff
3. Re-pushed the old n->next

Then your compare_and_swap would succeed even though the stack has changed.

This is not a problem for you, because you never look at any of the fields of n->next. It doesn't matter that the stack has changed, because all you care about is the n->next pointer.

If you did have to look inside that object, though, then your code would be broken. For instance, if you added a stack_size field to atomically keep track of the stack size, then you'd set n->stack_size = old_next->stack_size+1, and this would be wrong if the stack had changed as above.

So it is not true in general that insert operations are ABA-proof.