无锁堆栈 - 这是正确使用c ++ 11放松原子吗？可以证明吗？ [英] Lock-free stack - Is this a correct usage of c++11 relaxed atomics? Can it be proven?

问题描述

我写了一个容器，用于一个非常简单的数据，需要在线程间同步。我想要最好的性能。我不想使用锁。

我想使用轻松原子。

我一直在这方面做了很多，我在这个代码通过我抛出的所有测试的点。这不是很证明，所以我想知道是否有什么我失踪，或任何其他方式，我可以测试这个？

I've been working on this a lot, and I'm at the point where this code passes all tests I throw at it. That's not quite "proof" though, and so I'm wondering if there's anything I'm missing, or any other ways I can test this?

这是我的前提：

Here's my premise:

• 只有正确地推送和弹出节点才是重要的，堆栈不能被无效。


• 我相信操作在内存中的顺序只在一个地方是重要的：
  
  
  
  • 在compare_exchange操作本身之间。
  
  
  • It is only important that a Node be properly pushed and popped, and that the Stack can never be invalidated.
  • I believe that the order of operations in memory is only important in one place:
    • Between the compare_exchange operations themselves. This is guaranteed, even with relaxed atomics.

    这是我的思维。 正常，我们解释我们正在阅读的代码的方式是查看它的写入顺序。内存可以读取或写入无序，但不会以无效程序的正确性的方式。

    Here's what I'm thinking. "Normally", the way we reason about code that we're reading is to look at the order in which it's written. Memory can be read or written to "out of order", but not in a way that invalidates the correctness of the program.

    在多线程环境中更改。这就是内存围栏 - 所以我们仍然可以看看代码，并能够推断如何工作。

    That changes in a multi-threaded environment. That's what memory fences are for - so that we can still look at the code and be able to reason about how it's going to work.

    所以如果一切都可以全部在这里，我用轻松的原子学做什么？是不是有点太远了？

    So if everything can go all out-of-order here, what am I doing with relaxed atomics? Isn't that a bit too far?

    我不这么认为，但这就是为什么我在这里寻求帮助。

    I don't think so, but that's why I'm here asking for help.

    compare_exchange操作本身保证了彼此的顺序恒定性。

    或写入原子是在compare_exchange之前获取头的初始值。它被设置为变量的初始化的一部分。就我所知，这个操作是否会带来一个正确的值是不重要的。

    The only other time there is read or write to an atomic is to get the head's initial value before a compare_exchange. It is set as part of the initialization of a variable. As far as I can tell, it would be irrelevant whether or not this operation brings back a "proper" value.

    当前代码： / p>
    
    

    Current code:

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

    与其他人相比，这个问题有什么不同？轻松原子。他们对问题有很大的不同。

    What's different about this question compared to others? Relaxed atomics. They make a big difference to the question.

    那么，你觉得怎么样？有没有什么我错过了？

    So, what do you think? Is there anything I'm missing?

    推荐答案

    因为在 compareAndSwap 失败后不更新 node-> _next 。你最初存储的节点 node-> setNext 可能被另一个线程从堆栈的顶部弹出，当下一个 compareAndSwap 尝试成功。结果，一些线程认为它已经从堆栈弹出一个节点，但这个线程已经把它放回堆栈。应为：

    push is broken, since you do not update node->_next after a compareAndSwap failure. It's possible that the node you originally stored with node->setNext has been popped from the top of stack by another thread when the next compareAndSwap attempt succeeds. As a result, some thread thinks it has popped a node from the stack but this thread has put it back in the stack. It should be:

    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 ，则当堆栈实际上不为空时，可能无法弹出。

    Also, since next and setNext use memory_order_relaxed, there's no guarantee that _head_.next() here is returning the node most recently pushed. It's possible to leak nodes from the top of the stack. The same problem obviously exists in pop as well: _head.next() may return a node that was previously but is no longer at the top of the stack. If the returned value is nullptr, you may fail to pop when the stack is not actually empty.

    pop 也可以有未定义的行为，如果两个线程同时尝试从堆栈弹出最后一个节点。他们都看到 _head.next（）的同一个值，一个线程成功完成pop。另一个线程进入while循环 - 因为观察到的节点指针不是 nullptr - 但是 compareAndSwap 到 nullptr ，因为堆栈现在是空的。在循环的下一个迭代中，该nullptr被递减以获得其 _next 指针，并且随之而来的是令人欢喜的。

    pop can also have undefined behavior if two threads try to pop the last node from the stack at the same time. They both see the same value for _head.next(), one thread successfully completes pop. The other thread enters the while loop - since the observed node pointer is not nullptr - but the compareAndSwap loop soon updates it to nullptr since the stack is now empty. On the next iteration of the loop, that nullptr is dererenced to get its _next pointer and much hilarity ensues.

    pop 也显然遭受ABA。两个线程可以在堆栈的顶部看到相同的节点。说一个线程到达评估 _next 指针的位置，然后阻塞。其他线程成功弹出该节点，推送5个新节点，然后在其他线程唤醒之前再次推送该原始节点。其他线程的 compareAndSwap 将成功 - 栈顶节点是相同的 - 但是存储旧的 _next 值到 _head 而不是新的。被另一个线程推送的五个节点都被泄漏。 memory_order_seq_cst 也是这种情况。

    pop is also clearly suffering from ABA. Two threads can see the same node at the top of the stack. Say one thread gets to the point of evaluating the _next pointer and then blocks. The other thread successfully pops the node, pushes 5 new nodes, and then pushes that original node again all before the other thread wakes. That other thread's compareAndSwap will succeed - the top-of-stack node is the same - but store the old _next value into _head instead of the new one. The five nodes pushed by the other thread are all leaked. This would be the case with memory_order_seq_cst as well.

    这篇关于无锁堆栈 - 这是正确使用c ++ 11放松原子吗？可以证明吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！