ABA Problem

ABA problem

The use of CAS has one problem called ABA. The problem arises from the C of CAS, where the comparison 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:

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":

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

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

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:

_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.

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, 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.