如何在c中使用'cmpxchg8b'汇编指令实现原子比较和交换？

Question

我正在尝试实现一个无锁链表。为此，我需要在 C 语言中使用内联汇编来实现原子比较和交换指令。我知道我需要对 x86 使用 cmpxchg8b 指令，但我做不到。

我的节点结构如下：

typedef struct node
{
    int data;
    struct node * next;
    struct node * backlink;
}node_lf;

struct node * next 指针还在最后 2 位（标记位和标志位）中保存附加信息

我需要实现的比较和交换是这样的：

node_lf *cs (cs_arg * address, cs_arg *old_val, cs_arg *new_val )
{
    node_lf *value = (address->node)->next;
    if ((address->node->next) == old_val->node)
    {
        (address->node)->next = new_val->node;
    }
    return value;
}

cs_arg结构如下：

typedef struct csArg
{
    node_lf * node;
}cs_arg;

我的实现：

static inline node_lf* cs(cs_arg * address, cs_arg *old_val, cs_arg *new_val)
{
    node_lf * value;
    __asm__ __volatile__("lock cmpxchg8b %0; "
                :"=q"(value)
                :"a"(address->node->next), "b"(old_val->node), "c"(new_val->node)
                :"memory");
    return value;
}

这给出了一条错误消息： ../list.c:86: Error: operand type mismatch for 'cmpxchg8b' make: *** [list.o] Error 1

请帮我解决这个问题。

Answer 1

让我们一步一个脚印。首先，让我们尝试在一个简单的例子中使用 __sync_val_compare_and_swap：

#include <stdio.h>

typedef struct node
 {
    int data;
    struct node * next;
    struct node * backlink;
 }node_lf;

int cs1(node_lf *address, int old_val, int new_val)
{
    int *p2 = &address->data;
    int p3 = __sync_val_compare_and_swap(p2, old_val, new_val);  

    return p3;
}

int main()
{
   node_lf n;

   n.data = 17;

   int res = cs1(&n, 1, 2);
   printf("Old Value: %d  Cur Value: %d\n", res, n.data);

   res = cs1(&n, 17, 2);
   printf("Old Value: %d  Cur Value: %d\n", res, n.data);
}

所以，这里的代码非常简单。我们正在操纵 node.data。我们首先将其初始化为 17。然后我们尝试执行 cas 将其更改为 2。但是，在第一次调用中，我们为 oldval (1 vs 17) 提供了错误的值。结果，__sync_val_compare_and_swap（正确！）不执行交换，但 return 当前值。第二次调用确实给出了正确的旧值，确实执行了交换并且 returns 旧值。

所以，当运行我们得到：

Old Value: 17  Cur Value: 17 <- Didn't change the value
Old Value: 17  Cur Value: 2  <- Did change the value

足够简单，但不是您想要的。让我们把它拉近一点：

#include <stdio.h>

typedef struct node
 {
    int data;
    struct node * next;
    struct node * backlink;
 }node_lf;

typedef struct csArg
{
    node_lf * node;
}cs_arg;

node_lf *cs2(node_lf *address, const cs_arg *old_val, const cs_arg *new_val)
{
    unsigned long long *p2 = (unsigned long long *)&address->next;
    unsigned long long p3 = __sync_val_compare_and_swap (p2, (unsigned long long)old_val->node, (unsigned long long)new_val->node);  

    return (node *)p3;
}

int main()
{
   node_lf n;
   cs_arg oldval, newval;

   n.next = (node *)18;
   oldval.node = (node *)1;
   newval.node = (node *)2;

   node *res2 = cs2(&n, &oldval, &newval);
   printf("Old Value: %p  Cur Value: %p\n", res2, n.next);

   oldval.node = (node *)18;
   res2 = cs2(&n, &oldval, &newval);
   printf("Old Value: %p  Cur Value: %p\n", res2, n.next);
}

在这种情况下，我们尝试使用 2 cs_args 中的节点更新 node.next。这里要注意的主要事情是，由于 __sync_val_compare_and_swap 适用于整数类型，我们需要将指针转换为适当大小的 int。这里假设我们使用的是 64 位编译器，因此指针是 8 个字节（与 unsigned long long 相同）。

这里真的没有必要使用 cs_arg 结构。使用 node* 应该可以正常工作。不过你用过了，估计是有什么长远打算吧。

运行这个我们看到了：

Old Value: 0000000000000012  Cur Value: 0000000000000012  <- Didn't change the value
Old Value: 0000000000000012  Cur Value: 0000000000000002  <- Did change the value

请注意，如果您使用的是运行ning x64，则可以将其增加到 16 个字节（使用 __int128 和 cmpxchg16b）。但是，有一些技巧需要注意。例如，数据必须是 16 字节对齐的（node.next 不是）。

现在，完成所有这些后，您对 "need the old value of address->node->next as a return value" 的要求似乎值得怀疑。看看上面的代码，你怎么知道cas是否失败了？如果有效，则 returns 18，如果失败，则 returns 18。既然这就是你所说的，那就是我试图提供的。

但我假设您确实想知道它是否有效（可能是为了重试）。既然如此，也许更像是这样：

#include <stdio.h>

typedef struct node
 {
    int data;
    struct node * next;
    struct node * backlink;
 }node_lf;

bool cs2(node_lf *address, const node *old_val, const node *new_val)
{
    unsigned long long *p2 = (unsigned long long *)&address->next;
    return __sync_bool_compare_and_swap (p2, (unsigned long long)old_val, (unsigned long long)new_val);
}

int main()
{
   node_lf n;
   node *oldval, *newval;

   n.next = (node *)18;
   oldval = (node *)1;
   newval = (node *)2;

   bool res2;

   do {

      printf("Trying to change %p from %p to %p: ", n.next, oldval, newval);
      res2 = cs2(&n, oldval, newval);
      printf("Worked: %d  Cur Value: %p\n", res2, n.next);
      if (res2)
         break;

      oldval = n.next;
   } while (1);
}

当您退出循环时，oldval 将是之前存在的内容（必须是，否则 cas 将失败），newval 将是实际写入的内容。请注意，如果这确实是多线程的，则无法保证 newval 与 n.next 相同，因为另一个线程可能已经出现并再次更改它。

虽然使用汇编程序可能会为您节省一两条指令，但在可读性、可维护性、可移植性等方面的胜利几乎肯定是值得的。

除非这是一个 class 项目，老师需要内联汇编。在那种情况下，请查看 .

如何在c中使用'cmpxchg8b'汇编指令实现原子比较和交换？

How to implement atomic compare and swap using 'cmpxchg8b' assembly instruction in c?

c

atomic

inline-assembly

compare-and-swap