Стек без блокировок — это правильное использование c ++ 11 расслабленной атомики? Можно ли это доказать?

Я написал контейнер для очень простого фрагмента данных, который нужно синхронизировать между потоками. Я хочу максимальной производительности. Я не хочу использовать замки.

Я хочу использовать «расслабленную» атомику. Частично для этого немного лишнего шума, и частично, чтобы действительно понять их.

Я много работал над этим, и я нахожусь на том этапе, когда этот код проходит все тесты, которые я к нему добавляю. Это не совсем «доказательство», и поэтому мне интересно, есть ли что-то, что я пропускаю, или какие-то другие способы, которыми я могу это проверить?

Вот моя предпосылка:

• Важно только, чтобы узел был правильно выдвинут и вытолкнут, а стек никогда не может быть признан недействительным.
• Я считаю, что порядок операций в памяти важен только в одном месте:
  • Между самими операциями compare_exchange. Это гарантировано даже при расслабленной атомике.
• Проблема «ABA» решается путем добавления идентификационных номеров к указателям. В 32-битных системах это требует двойного слова compare_exchange, а в 64-битных системах неиспользуемые 16-битные указатели заполняются номерами идентификаторов.
• Следовательно: стек всегда будет в допустимом состоянии. (право?)

Вот что я думаю. «Обычно», то, как мы рассуждаем о коде, который читаем, — это смотреть в том порядке, в котором он написан. Память может быть прочитана или записана «не по порядку», но не таким образом, который нарушает правильность программы.

Это меняется в многопоточной среде. Вот для чего нужны ограждения памяти, чтобы мы могли еще посмотреть на код и рассуждать о том, как он будет работать.

Так что, если здесь все может выйти из строя, что я делаю с расслабленной атомикой? Разве это не слишком далеко?

Я так не думаю, но именно поэтому я здесь и прошу помощи.

Сами операции сравнения_обмена дают гарантию последовательного постоянства друг с другом.

Единственный другой раз, когда есть чтение или запись в атомарный элемент, — это получить начальное значение заголовка перед началом сравнения. Он устанавливается как часть инициализации переменной. Насколько я могу судить, было бы неважно, возвращает ли эта операция «правильное» значение.

Текущий код:

struct node
{
node *n_;
#if PROCESSOR_BITS == 64
inline constexpr node() : n_{ nullptr }                 { }
inline constexpr node(node* n) : n_{ n }                { }
inline void tag(const stack_tag_t t)                    { reinterpret_cast<stack_tag_t*>(this)[3] = t; }
inline stack_tag_t read_tag()                           { return reinterpret_cast<stack_tag_t*>(this)[3]; }
inline void clear_pointer()                             { tag(0); }
#elif PROCESSOR_BITS == 32
stack_tag_t t_;
inline constexpr node() : n_{ nullptr }, t_{ 0 }        { }
inline constexpr node(node* n) : n_{ n }, t_{ 0 }       { }
inline void tag(const stack_tag_t t)                    { t_ = t; }
inline stack_tag_t read_tag()                           { return t_; }
inline void clear_pointer()                             { }
#endif
inline void set(node* n, const stack_tag_t t)           { n_ = n; tag(t); }
};

using std::memory_order_relaxed;
class stack
{
public:
constexpr stack() : head_{}{}
void push(node* n)
{
node next{n}, head{head_.load(memory_order_relaxed)};
do
{
n->n_ = head.n_;
next.tag(head.read_tag() + 1);
} while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));
}

bool pop(node*& n)
{
node clean, next, head{head_.load(memory_order_relaxed)};
do
{
clean.set(head.n_, 0);

if (!clean.n_)
return false;

next.set(clean.n_->n_, head.read_tag() + 1);
} while (!head_.compare_exchange_weak(head, next, memory_order_relaxed, memory_order_relaxed));

n = clean.n_;
return true;
}
protected:
std::atomic<node> head_;
};

Чем отличается этот вопрос от других? Расслабленная атомика. Они имеют большое значение для вопроса.

Так что ты думаешь? Я что-то пропустил?