Условие гонки 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 предоставляет реализации различных схем рекультивации, которые можно использовать именно для этого.