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

`std::shared_ptr` to ensure lifetime of your object? – Jarod42 May 27 '20 at 10:20 — Jarod42, May 27 '20 at 10:20

score 1 · Accepted Answer · answered May 27 '20 at 10:35

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.

Thanks! I see what your saying. My case also includes the changing of the foo pointer, so a memory reclamation scheme isn't all I need. But thanks I'll take a look! — David Ledger, May 27 '20 at 10:48
Looks like you used marked pointers with the high/low bits being used as flags. Do you use the bits to stall disposal and such? I'm still mentally trying to understand your code :). That said the paper you linked on your git references a wait-free dequeue (you also seem to have implemented it, but I'll study the paper before studying your repo). — David Ledger, May 27 '20 at 12:48
Marked pointers are used by some data structures (e.g., in harris michael list based set/hash map), but not for the reclamation schemes. The fully understand that it is not easy to grasp the code at a first glance. :) However, this is not the right place - if you have questions about the code, you can raise an issue or contact my via email (you can find the mail address in my github profile) and I will be happy to answer. — mpoeter, May 27 '20 at 12:56

ABA Race Condition

1 Answers1