ABA problem

ABA problem is a correctness hazard in lock-free code using compare-and-swap (CAS). CAS assumes that matching values mean nothing changed, but another thread can change a location from A to B and back to A between your read and your CAS, and CAS cannot detect this. This manifests concretely in lock-free stacks where a popped and re-pushed node can corrupt the stack structure.

Solutions include tagged pointers (pair pointer with monotonic version counter), epoch-based reclamation (defer freeing until all threads pass a checkpoint), or hazard pointers (track active references).

This example shows the ABA problem in a simplified lock-free scenario.

// compile: gcc -std=c11 -pthread -O2 -o aba aba.c
// run: ./aba
// description: demonstrate ABA problem where CAS cannot detect reuse
 
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdatomic.h>
 
struct node {
    int value;
    struct node* next;
};
 
atomic_intptr_t head = 0;
 
void push(int val) {
    struct node* n = malloc(sizeof(struct node));
    n->value = val;
    struct node* old;
    do {
        old = (struct node*)atomic_load(&head);
        n->next = old;
    } while (!atomic_compare_exchange_weak(&head, (void*)&old, n));
}
 
struct node* pop(void) {
    struct node* n;
    do {
        n = (struct node*)atomic_load(&head);
        if (!n) return NULL;
    } while (!atomic_compare_exchange_weak(&head, &n, n->next));
    return n;
}
 
int main() {
    // Push A
    push(1);
 
    // Pop A (thread 1 reads head=A, preempted)
    struct node* a = pop();
 
    // Pop and push A again (thread 2 pops B, pushes A back)
    push(2);
    struct node* b = pop();
    push(1);  // A is reused
 
    printf("ABA problem: node A was freed and reused\n");
 
    free(a);
    free(b);
    return 0;
}