Какой порядок памяти использовать в реализации pop() стека связанных списков без блокировки? ⇐ C++

[Anonymous]

Я столкнулся с интересной проблемой: когда дело доходит до назойливых стеков без блокировки (односвязных списков), похоже, существует консенсус относительно того, как должен выглядеть метод push(). Все поисковые запросы в Интернете/ИИ (и cppreference.com) всегда создают код, написанный следующим образом:

Код: Выделить всё

struct stack
{
struct node { node* next; };

std::atomic head;

void push(node* new_node)
{
new_node->next = head.load(std::memory_order_relaxed);

// simplified: real code has an ABA counter in the low 12 bits of head
while (!head.compare_exchange_weak(new_node->next, new_node,
std::memory_order_release,
std::memory_order_relaxed)) {}
}
};

но когда дело доходит до pop(), результаты поиска несовместимы с порядком памяти, например:

Код: Выделить всё

    node* pop()
{
node* p = head_.load(std::memory_order_**acquire**);

while (p && !head_.compare_exchange_weak(p, p->next,
std::memory_order_**acq_rel**,
std::memory_order_**relaxed**));
return p;
}

Я видел различные варианты выделенных параметров (например, расслабление + acq_rel + приобретение или расслабление + приобретение + расслабление). Я понимаю, что на x86 это не имеет значения, но приятно все делать правильно...
Каковы правильные значения трех выделенных параметров?
Примечание: я знаю о проблеме ABA и в своем коде решаю(*) ее с помощью помеченных указателей, при этом младшие 12 бит заголовка являются счетчиком. Это распределитель страниц.
*solve = значительно уменьшает вероятность возникновения событий
После мысли (подробности см. в комментариях к ответу Питера):

• Похоже, что единственный способ иметь формально правильный список в C++26 — это:
  
  (предотвратить данные Race UB) сделать node::next атомарным
• (предотвратить строгое псевдонимирование UB) не выполнять неатомарный доступ к узлу; т. е. если вы используете список для пула страниц - часть страницы, содержащая узел, не может использоваться для других целей
• используйте версию pop() Питера; то есть приобрести+

  Код: Выделить всё

  relaxed+acquire

[*]На реальных ISA с обычными компиляторами вы можете использовать предложенный pop() и использовать всю страницу (попирая неатомарный node::next); просто добавьте соответствующие комментарии seq_cst для CAS будет компилироваться в тот же asm на x86, что и Acquire/etc, но seq_cst не делает его более безопасным на других ISA, где он компилируется по-другому, поэтому нет причин предпочитать его здесь, кроме использования значения по умолчанию, чтобы исходный код был более компактным.



Подробнее здесь: https://stackoverflow.com/questions/797 ... ementation