ABA Race Condition

Question

I'm concerned about nested pointers and access, specifically whether there is a way to avoid this ABA problem when dealing with a lock-free node based tree structure.

My concern is the following:

Does the standard make guarantees about this and is funcB equivalent to funcA?

If there as an ABA problem here, is there a solution to nested member access for lock-free programming?

#include <atomic>
#include <iostream>

struct Foo
{
    std::atomic_int value;
};

struct Bar
{
    Foo * foo;
};

void funcB(Bar * bar)
{
    if (not bar->foo->value.fetch_or(1) )
    {
        //Something
    }
}

void funcA(std::atomic_int * bar)
{
    if (not bar->fetch_or(0))
    {
        //Something
    }
}

The assembly output from the above is:

funcB(Bar*):                          # @funcB(Bar*)
        mov     rax, qword ptr [rdi]
        lock            or      dword ptr [rax], 1
        ret
funcA(Foo*):                          # @funcA(Foo*)
        lock            or      dword ptr [rdi], 1
        ret

Answer 1

Your example does not really show an ABA problem. Wikipedia:

[..] the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.

That said, it is your responsibility to ensure that a pointer is still valid (i.e., points to an existing object/memory that has not been freed) at the time it is dereferenced. In case multiple threads are involved, it is also your responsibility to ensure the required happens-before relations (if any) that are necessary to avoid potential data races.

Avoiding the ABA problem in a lock-free algorithm can be quite tricky. It is usually simplest to delegate this to an established memory reclamation scheme. My xenium library provides implementations of various reclamation schemes that can be used for just that.