c++ - 无锁双链表的原子操作

我根据这些文件编写了一个无锁的双向链接列表:

“基于引用计数的高效可靠的无锁内存回收”
Anders Gidenstam，成员，IEEE，Marina Papatriantafilou，HMar akan Sundell和Philippas Tsigas

“无锁双端队列和双向链表”
菲利普斯·蒂加斯(Philippas Tsigas)，霍坎·桑德尔

对于这个问题，我们可以搁置第一篇论文。

在本文中，他们使用一种聪明的方式在单词中存储删除标志和指针。
(更多信息here)

本文中此部分的伪代码:

union Link
    : word
    (p,d): {pointer to Node, boolean}

structure Node
    value: pointer to word
    prev: union Link
    next: union Link

而我的上述伪代码的代码:

template< typename NodeT >
struct LockFreeLink
{
public:
    typedef NodeT NodeType;

private:

protected:
    std::atomic< NodeT* > mPointer;

public:
    bcLockFreeLink()
    {
        std::atomic_init(&mPointer, nullptr);
    }
    ~bcLockFreeLink() {}

    inline NodeType* getNode() const throw()
    {
        return std::atomic_load(&mPointer, std::memory_order_relaxed);
    }
    inline std::atomic< NodeT* >* getAtomicNode() const throw()
    {
        return &mPointer;
    }
};

struct Node : public LockFreeNode
{
    struct Link : protected LockFreeLink< Node >
    {
        static const int dMask = 1;
        static const int ptrMask = ~dMask;

        Link() { } throw()
        Link(const Node* pPointer, bcBOOL pDel = bcFALSE) throw()
        {
            std::atomic_init(&mPointer, (reinterpret_cast<int>(pPointer) | (int)pDel));
        }

        Node* pointer() const throw()
        {
            return reinterpret_cast<Node*>(
                std::atomic_load(&data, std::memory_order_relaxed) & ptrMask);
        }
        bool del() const throw()
        {
            return std::atomic_load(&data, std::memory_order_relaxed) & dMask;
        }
        bool compareAndSwap(const Link& pExpected, const Link& pNew) throw()
        {
            Node* lExpected = std::atomic_load(&pExpected.mPointer, std::memory_order_relaxed);
            Node* lNew = std::atomic_load(&pNew.mPointer, std::memory_order_relaxed);

            return std::atomic_compare_exchange_strong_explicit(
                &mPointer,
                &lExpected,
                lNew,
                std::memory_order_relaxed,
                std::memory_order_relaxed);
        }

        bool operator==(const Link& pOther) throw()
        {
            return std::atomic_load(data, std::memory_order_relaxed) ==
                std::atomic_load(pOther.data, std::memory_order_relaxed);
        }
        bool operator!=(const Link& pOther) throw()
        {
            return !operator==(pOther);
        }
    };

    Link mPrev;
    Link mNext;
    Type mData;

    Node() {};
    Node(const Type& pValue) : mData(pValue) {};
};

本文提供了用于将链接的删除标记设置为true的功能:

procedure SetMark(link: pointer to pointer to Node)
    while true do
       node = *link;
       if node.d = true or CAS(link, node, (node.p, true)) then break;

而我的函数代码:

void _setMark(Link* pLink)
{
    while (bcTRUE)
    {
        Link lOld = *pLink;
        if(pLink->del() || pLink->compareAndSwap(lOld, Link(pLink->pointer(), bcTRUE)))
            break;
    }
}

但是我的问题是在compareAndSwap函数中，我必须比较并交换三个原子变量。有关问题的信息是here

(实际上，compare and swap函数中的new变量并不重要，因为它是线程本地的)

现在我的问题是:我该如何编写compareAndSwap函数来比较和交换三个原子变量，或者我在哪里出错？

(请问一个长时间的问题)

编辑:

内存管理器文件中也存在类似的问题:

function CompareAndSwapRef(link:pointer to pointer toNode,
old:pointer toNode, new:pointer toNode):boolean
    if CAS(link,old,new) then
        if new=NULL then
            FAA(&new.mmref,1);
            new.mmtrace:=false;
    if old=NULLthen FAA(&old.mmref,-1);
    return true;
return false;

在这里，我必须再次比较并交换三个原子变量。
(请注意，我的参数是Link的类型，我必须比较并交换mPointer的Link)

最佳答案

除非您可以将要比较/交换的三个数据项放到两个指针大小的元素中，否则无法通过比较和交换来做到这一点(肯定不在x86上，而且我还没有听说过任何其他机器架构有这样的事情)。

如果您依赖存储在(至少)与偶数字节地址对齐的地址上的数据，则在删除元素时可能会使用按位或来设置最低位。过去，人们一直在使用地址的上部存储额外的数据，但是至少在x86-64中，这是不可能的，因为地址的上部必须是“规范”的，这意味着任何地址位高于“可用限制”(由处理器体系结构定义，当前为48位)，必须全部与可用限制的最高位相同(因此与第47位相同)。

编辑:这部分代码正是我所描述的:

    static const int dMask = 1;
    static const int ptrMask = ~dMask;

    Link() { } throw()
    Link(const Node* pPointer, bcBOOL pDel = bcFALSE) throw()
    {
        std::atomic_init(&mPointer, (reinterpret_cast<int>(pPointer) | (int)pDel));
    }

    Node* pointer() const throw()
    {
        return reinterpret_cast<Node*>(
            std::atomic_load(&data, std::memory_order_relaxed) & ptrMask);
    }

它使用最低位来存储pDel标志。

通过使用cmpxchg16b形式(在x86上)，您应该能够对双向链接列表执行此操作。在Windows系统中，该名称为 _InterlockedCompareExchange128 。在gcc中(对于Unix类型的OS，例如Linux/MacOS)，您需要首先根据两个指针构造一个int128。如果要编译32位代码，则可能需要为Windows和Unix OS都制作一个64位int。