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

Question

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

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

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

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

• Важно только, чтобы узел был правильно выдвинут и вытолкнут, а стек никогда не может быть признан недействительным.
• Я считаю, что порядок операций в памяти важен только в одном месте:
  • Между самими операциями 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_;
};

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

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

Answer 1

push сломан, так как вы не обновляете node->_next после compareAndSwap отказ. Возможно, что узел, с которым вы изначально сохранили node->setNext был вытолкнут из вершины стека другим потоком, когда следующий compareAndSwap попытка удалась В результате некоторый поток думает, что он вытолкнул узел из стека, но этот поток вернул его обратно в стек. Так должно быть:

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

Кроме того, так как next а также setNext использование memory_order_relaxedнет никаких гарантий, что _head_.next() здесь возвращается узел, который был добавлен последним. Возможна утечка узлов с вершины стека. Такая же проблема, очевидно, существует в pop также: _head.next() может вернуть узел, который был ранее, но больше не находится на вершине стека. Если возвращаемое значение nullptr, вы можете потерпеть неудачу, когда стек фактически не пуст.

pop может также иметь неопределенное поведение, если два потока пытаются извлечь последний узел из стека одновременно. Они оба видят одно и то же значение для _head.next(), один поток успешно завершает поп. Другой поток входит в цикл while - поскольку наблюдаемый указатель узла не является nullptr - но compareAndSwap цикл скоро обновит его nullptr поскольку стек сейчас пуст. На следующей итерации цикла этот nullptr разыменовывается, чтобы получить его _next указатель и много веселья наступает.

pop также явно страдает от АБА. Два потока могут видеть один и тот же узел в верхней части стека. Скажем, один поток доходит до оценки _next указатель, а затем блоки. Другой поток успешно извлекает узел, выдвигает 5 новых узлов, а затем снова подталкивает этот исходный узел, прежде чем другой поток проснется. Это другой поток compareAndSwap будет успешным - узел вершины стека тот же - но сохранить старый _next значение в _head вместо нового. Пять узлов, выдвинутых другим потоком, все просочились. Это было бы в случае с memory_order_seq_cst также.

Answer 2

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

Answer 3

Этот код полностью сломан.

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

Первая проблема заключается в том, что без синхронизации нет гарантии, что клиент этой структуры данных даже увидит поля объекта узла, которые будут инициализированы. Следующая проблема заключается в том, что без синхронизации операция push может считывать произвольно старые значения тега заголовка.

Мы разработали инструмент CDSChecker, который имитирует большинство типов поведения, которые допускает модель памяти. Это с открытым исходным кодом и бесплатно. Запустите его на вашей структуре данных, чтобы увидеть некоторые интересные исполнения.

Доказать что-либо о коде, который использует расслабленную атомизацию, является большой проблемой на данный момент. Большинство методов доказательства ломаются, потому что они, как правило, носят индуктивный характер, и у вас нет приказа индуктировать. Таким образом, вы выходите из воздуха, читая вопросы...