# ABA Problem

## ABA problem

The use of CAS has one problem called ABA. The problem arises from the **C** of **C**AS, where the **c**omparison is value-based. That is, as long as the value in the comparison appears the same, the swap can proceed. However, there are still cases that can fool around the CAS. Let's see an example where three threads concurrently access the lock-free stack we presented:

<figure><img src="/files/-Lp-5n1ac2J8DisZiL4C" alt=""><figcaption></figcaption></figure>

**PS**: In our case, it is not necessary for the newly allocated node's content is the same as the original node, they just need to use the same memory block.

## Solution to ABA problem

The solution to ABA problem is that we should defer reclamation while other threads are holding the node; or we should have a way to identify the difference between the old node and the new node.

There are several solutions to the ABA problem, for the details, you can see this link:

> <https://en.wikipedia.org/wiki/ABA_problem>

A common workaround is to add an extra "tag" or "stamp" word to the value being modified. For example, an algorithm using compare-and-swap on a pointer might use a "tag" to indicate how many times the pointer has been successfully modified. Because of this, the next compare-and-swap will fail when the addresses are the same, because the tag will not match. This is sometimes called **ABA'** since the second A is made slightly different from the first.

We solve the ABA problem by using the above solution. We reconstruct the stack by adding a "tag":

```c
typedef struct _lfstack_t
{
    int tag;
    Node *head;
}
```

Every time when we use the pointer, we will increase the "tag" by 1.

```c
void lfstack_push(_Atomic lfstack_t *lfstack, int value) {
    lfstack_t next, orig = atomic_load(lfstack);
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = value;
    do {
        node->next = orig.head;
        next.head = node;
        next.tag = orig.tag + 1; // increase the "tag"
    } while (!atomic_compare_exchange_weak(lfstack, &orig, next));
}

int lfstack_pop(_Atomic lfstack_t *lfstack) {
    lfstack_t next, orig = atomic_load(lfstack);
    do {
        if (orig.head == NULL) {
            return -1;
        }
        next.head = orig.head->next;
        next.tag = orig.tag + 1; // increase the "tag"
    } while (!atomic_compare_exchange_weak(lfstack, &orig, next));
    printf("poping value %d\n", orig.head->data);
    free(orig.head);
    return 0;
}
```

Don't forget to change the initialization of the stack:

```c
_Atomic lfstack_t top = {0,NULL};
```

You may meet the error "undefined reference to `__atomic_compare_exchange_16`" when you compile the code. If so, compile your code with `-latomic`.

```bash
gcc -std=c11 -lpthread -latomic -o my_new_stack my_new_stack.c
```

Now, when we run the program again, it will not print any error information. There is a C library called [`liblfds`](https://www.liblfds.org/), a lock-free data structure library written in C. If you don't like writing the lock-free data structure by yourself, you could use this C library.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://eric-lo.gitbook.io/lock-free-programming/aba-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.