# ABA problem

**[ABA problem](https://en.wikipedia.org/wiki/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).

## Example

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

```c
// 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;
}
```