Условие гонки ABA

Question

Меня беспокоят вложенные указатели и доступ, в частности, есть ли способ избежать этой проблемы ABA при работе с древовидной структурой на основе узлов без блокировки.

Меня беспокоит следующее:

Предоставляет ли стандарт гарантии по этому поводу и является ли funcB эквивалентом funcA?

Если здесь есть проблема ABA, есть ли решение для вложенного доступа к членам для программирования без блокировки?

#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
    }
}

Результат сборки из приведенного выше:

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

Ваш пример на самом деле не показывает проблему ABA. Википедия:

[..] проблема ABA возникает во время синхронизации, когда местоположение считывается дважды, имеет одинаковое значение для обоих считываний, а "значение одинаково" используется для обозначения "ничего не изменилось". Однако другой поток может выполняться между двумя чтениями и изменять значение, выполнять другую работу, а затем возвращать значение, таким образом обманывая первый поток, заставляя думать, что "ничего не изменилось", даже если второй поток действительно работал, что нарушает это предположение.

Тем не менее, вы несете ответственность за то, чтобы указатель оставался действительным (т.е. указывал на существующий объект / память, который не был освобожден) во время разыменования. В случае, если несколько потоков, то для нее также ваша ответственность, чтобы обеспечить требуемое происходит, прежде, чем отношения (если таковые имеются), которые необходимы, чтобы избежать возможных гонок данных.

Избежать проблемы ABA в алгоритме без блокировки может быть довольно сложно. Обычно проще всего делегировать это установленной схеме восстановления памяти. Моя библиотека xenium предоставляет реализации различных схем утилизации, которые можно использовать именно для этого.