Lock-free stack - Является ли это правильным использованием С++ 11 расслабленной атомистики? Можно ли это доказать?

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

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

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

Здесь мое предположение:

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

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

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

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

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

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

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

Текущий код:

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_;
};

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

Итак, что вы думаете? Есть ли что-то, что мне не хватает?

Ответы

void push(Node* node) noexcept
{
    Node* n = _head.next();
    do {
        node->setNext(n);
    } while (!_head.compareAndSwap(n, node));
}