The ABA Problem

The ABA problem is a well-known issue in CAS-based lock-free data structures. C++ supports std::atomic for arbitrary data types, but it is not always lock-free. You can check it with below.

#include <atomic>
#include <iostream>

typedef struct _bigStructure{
    int a;
    int b;
    float c;
    char d;
}bigStructure;

int main(){
    std::atomic<int> atomicInt;
    std::atomic<bigStructure> atomicStructure;

    std::cout << "std::atomic<int> atomicInt                  is it lock free? : " << atomicInt.is_lock_free() << std::endl;
    std::cout << "std::atomic<bigStructure> atomicStructure   is it lock free? : " << atomicStructure.is_lock_free() << std::endl;
    return 0;
}

The output will look like:

std::atomic<int> atomicInt                  is it lock free? : 1
std::atomic<bigStructure> atomicStructure   is it lock free? : 0

In fact, CAS-possible data size is limited to the HW support. However, most of HW supports only memory size CAS operation. If it is 32-bit computing unit, it usually supports 32-bit CAS. If it is 64-bit computing unit, it usually supports 64-bit CAS. Therefore, most of CAS based data structures use a pointer to work. Below lock-free queue uses this.

#include <iostream>
#include <thread>
#include <string>
#include <atomic>
#include <stdio.h>
#include <unistd.h>
#include <mutex>

template<typename T>
int __coutArgs__(T t){
    std::cout << t;
}

template<typename T, typename ... Args>
int __coutArgs__(T t, Args... args){
    std::cout << t;
    __coutArgs__(args...);
}

std::mutex __print_sync_mutex__;

//Synchronous printing for cpp
template<typename ... Args>
int printSync(Args... args){
    __print_sync_mutex__.lock();
    __coutArgs__(args...);
    __print_sync_mutex__.unlock();
}

//List structure to save some profile
class profile_t{
public:
    profile_t(std::string name, std::string phoneNumber, profile_t* next):name(name),phoneNumber(phoneNumber),next(next){}
    std::string name;
    std::string phoneNumber;
    profile_t* next;
};

class profileStack_t{
public:
    std::atomic<profile_t*> top_ptr;
    profileStack_t(){
        top_ptr = nullptr;
    }

    profile_t* pop(){
        while (true) {
            profile_t* ret_ptr = top_ptr;
            if (ret_ptr == nullptr) return nullptr;//Empty stack
            profile_t* next_ptr = ret_ptr->next;
            if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
                return ret_ptr;
            }
        }
    }

    profile_t* slowPop(){
        while (true) {
            profile_t* ret_ptr = top_ptr;
            if (ret_ptr == nullptr) return nullptr;//Empty stack
            profile_t* next_ptr = ret_ptr->next;
            printSync("T2 sleep with top pointer at ", ret_ptr, "\n");
            printSync("This CAS must failed if T1 access\n");
            sleep(2);
            if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
                printSync("T2 Success\n");
                return ret_ptr;
            }
            else{
                printSync("T2 Failed\n");
            }
        }
    }

    void push(profile_t* obj_ptr){
        while (true) {
            profile_t* next_ptr = top_ptr;
            obj_ptr->next = next_ptr;

            if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {
                return;
            }
        }
    }
};

int main(){
    using namespace std;
    profile_t* A    = new profile_t("A", "010-1234-5678", nullptr);
    profile_t* B    = new profile_t("B", "010-1111-1111", nullptr);
    profileStack_t q;

    q.push(B);
    q.push(A);
    
    auto t1 = thread([&](){
        sleep(1);//Let t2 gets pointer first.
        auto popped1 = q.pop();
        if(popped1 != nullptr){
            printSync("T1 : pop ", popped1->name.c_str(), "(", popped1->phoneNumber, ") at ", popped1, "\n");
            delete popped1;
        }
        
        profile_t* newA    = new profile_t("newA", "010-0000-0000", nullptr); //Produce after delete A for using the same address
        
        auto popped2 = q.pop();
        if(popped2 != nullptr){
            printSync("T1 : pop ", popped2->name.c_str(), "(", popped2->phoneNumber, ") at ", popped2, "\n");
            delete popped2;
        }
        q.push(newA);
        printSync("T1 : push ", newA->name.c_str(), "(", newA->phoneNumber, ") at ", newA, "\n");
    });
    
    auto t2 = thread([&](){
        auto popped = q.slowPop();
        if(popped != nullptr){
            printSync("T2 : pop ", popped->name.c_str(), "(", popped->phoneNumber, ") at ", popped, "\n");
            delete popped;
        }
    });

    t1.join();
    t2.join();

    profile_t* popped;
    while(true){
        popped = q.pop();
        if(popped == nullptr)
            break;
        cout << "top : " << popped->name.c_str() << "(" << popped->phoneNumber <<") at " << popped << "\n";
        delete popped;
    }

}

However, this code has a subtle problem (you can reproduce it yourself). Since the CAS checks only the pointer value to determine whether it has changed, it cannot detect when the same address is reallocated for a new object. The following scenario demonstrates the issue.

Assume there is one CAS-based lock-free stack $Q$ and two threads $T_1$ and $T_2$. $Q$ initially contains $A$ at the top and $B$ below it. Thread $T_1$ reads $A$ as the top and $B$ as the next element, then goes to sleep. Thread $T_2$ pops both $A$ and $B$, then allocates a new node that happens to reuse $A$’s address and pushes it. When $T_1$ wakes up, its CAS succeeds because the top pointer still matches $A$’s address. As a result, the new top points to $B$, which has already been freed — a dangling pointer. The data structure is now in a corrupted state.