Какой порядок памяти использовать в реализации 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);

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 и в своем коде решаю ее (*) с помощью помеченных указателей)
*solve = значительно снижает вероятность возникновения
После мысли (подробности см. в комментариях к ответу Питера):

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

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

  relaxed+acquire

[*]на x86 вы можете просто использовать seq_cst Compare_exchange_strong() (особенно, поскольку cppreference.com рекомендует это) и использовать всю страницу (попирая неатомарный node::next); просто добавьте соответствующие комментарии



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