确保使用双比较交换指令，实现无锁栈？

Question

确保使用双比较交换指令，实现无锁栈？

3

（假设使用64位x86-64架构和英特尔第三/四代CPU）

以下是《并发实战》一书第202页中的无锁栈实现：

template<typename T>
class lock_free_stack
{
private:
    struct node;

    struct counted_node_ptr
    {
        int external_count;
        node* ptr;
    };

    struct node
    {
        std::shared_ptr<T> data;
        std::atomic<int> internal_count;
        counted_node_ptr next;

        node(T const& data_):data(std::make_shared<T>(data_)),internal_count(0){}
    };

    std::atomic<counted_node_ptr> head;

public:
    ~lock_free_stack()
    {
        while(pop());
    }

    void push(T const& data)
    {
        counted_node_ptr new_node;
        new_node.ptr=new node(data);
        new_node.external_count=1;
        new_node.ptr->next=head.load();
        while(!head.compare_exchange_weak(new_node.ptr->next,new_node));
    }
};

以下是代码下方的内容：

在支持双字比较和交换操作的平台上，此结构将足够小，以使std::atomic成为无锁状态。

我相信x86-64确实支持双重CAS（我暂时想不起指令的名称）。

如果我检查汇编代码（并且看不到双重CAS指令），那么我需要编写什么内联汇编函数来确保使用双重CAS？

更新 - 我想我在这里找到了我要找的内容：

http://blog.lse.epita.fr/articles/42-implementing-generic-double-word-compare-and-swap-.html

template<typename T>
struct DPointer <T,sizeof (uint64_t)> {
public:
  union {
    uint64_t ui[2];
    struct {
      T* ptr;
      size_t count;
    } __attribute__ (( __aligned__( 16 ) ));
  };

  DPointer() : ptr(NULL), count(0) {}
  DPointer(T* p) : ptr(p), count(0) {}
  DPointer(T* p, size_t c) : ptr(p), count(c) {}

  bool cas(DPointer<T,8> const& nval, DPointer<T,8> const& cmp)
  {
    bool result;
    __asm__ __volatile__ (
        "lock cmpxchg16b %1\n\t"
        "setz %0\n"
        : "=q" ( result )
         ,"+m" ( ui )
        : "a" ( cmp.ptr ), "d" ( cmp.count )
         ,"b" ( nval.ptr ), "c" ( nval.count )
        : "cc"
    );
    return result;
  }

  // We need == to work properly
  bool operator==(DPointer<T,8> const&x)
  {
    return x.ptr == ptr && x.count == count;
  }
};

- user997112

1

你不需要使用内联汇编。现代的gcc（使用-mcx16）在编译像std::atomic<my_struct>这样的16B对象上的compare_exchange_weak时，会使用LOCK CMPXCHG16B。请参见此答案，其中我包含了使用（大部分）可移植的C++11代码实现它的示例。 - Peter Cordes

如果你认为合适的话（请告诉我），我可以将这个问题标记为重复。 - Peter Cordes

2个回答

1

你可以断言。

std::atomic<T>::is_lock_free()

- Petter

1

虽然这段代码可能回答了问题，但最好解释一下它的作用并添加一些参考资料。 - Hamid Pourjam

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marco van de Voort · Accepted Answer

最早版本的x86_64不支持CMPXCHG16B指令，而这个指令是Windows 8.1/64位及以上版本所必需的。据我所知，大部分Athlon64系列（socket 751、939和一些X2，可能还包括第一代Pentium D（8xx））都不支持该指令。

如何强制编译器使用特定指令因情况而异，通常需要使用非完全可移植的内置函数。