C 中 lockFree 列表的标记指针

Question

我正在尝试使用标记指针来处理列表上的无锁操作，以便在此事务期间如果其他线程在列表上操作时阻止比较和交换 (CAS) 通过。我的节点结构和 CAS 如下所示：

struct node {
    unsigned long key;
    unsigned long val;
    struct node * next;
};

static inline bool CAS(std::atomic<node*> node, struct node* oldNode, struct node* newNode)
{
    node.compare_exchange_strong(oldNode, newNode, std::memory_order_seq_cst);
}

我找到了一些设置和检查这些指针的方法，但我不清楚它们是如何工作的，这些是设置掩码和验证它的方法。

__inline struct node* setTagMask(struct node* p, int MASK_BIT)
{
    return (struct node*) ((uintptr_t)p | MASK_BIT);
}

__inline bool isMaskFlagSet(struct node* p)
{
    return ((uintptr_t)p & MASK_BIT) != 0;
}

所以我不清楚的是，例如在 setTagMask 中，如果我在我的列表中使用它，它会删除所有对其值和下一个元素的引用。

任何人都可以向我解释如何正确设置这些位以使列表的其他元素保持不变吗？

Answer 1

setTagMask 函数 returns 指针的修改版本 p。如果您将这个修改后的指针存储在您的链表中，那么该列表将被破坏，因为修改后的指针不再指向 node。

指针修改如下。指针 p 被转换为一个无符号整数，可以存储一个指针：uintptr_t。然后根据MASK_BIT设置一位或多位。最后将结果转换回指针返回。

函数isMaskFlagSet检查掩码位是否仍然设置。

我能想到的唯一用例是：每次使用指针之前，您都必须调用 isMaskFlagSet。如果设置了掩码位，则禁止实际使用指针。

C 中 lockFree 列表的标记指针

Tagged Pointers for lockFree list in C

c++

pointers

bitmask

lock-free