标记指针的lockFree列表中C [英] Tagged Pointers for lockFree list in C

问题描述

我试图使用带标记的指针来处理列表上的无锁操作，以便阻止比较和交换（CAS），如果在此事务期间在列表上操作的其他线程。我的节点结构和CAS看起来像这样：

I am trying to use tagged pointers for handling the lock free operations on a list, in order to block the compare-and-swap (CAS) from going through if some other thread operated on the list during this transaction. My node struct and CAS look like this:

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

我找到一些方法来设置和检查这些指针，但它不清楚我

I found some methods for setting and checking these pointers but it is unclear to me how they work, these are the methods for setting the mask and verifying it.

__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中，如果我使用它在我的列表中，它会删除它的所有引用其值和下一个元素。

So what is unclear to me is for example in the setTagMask, if I use it on my list than it will delete all its references to its value and next element as well.

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

Can anyone explain to me how can I properly set these bits so the other elements of the list remain the same?

推荐答案

setTagMask 函数返回指针的修改版本 p 。如果你在链表中存储这个修改的指针，那么列表会被破坏，因为修改的指针不再指向节点。

The setTagMask function returns a modified version of the pointer p. If you store this modified pointer in your linked-list, then the list gets broken because the modified pointer does not point to a node anymore.

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

The pointer is modified as follows. The pointer p is converted to an unsigned integer which is capable to store a pointer: uintptr_t. Then one or more bits are set according to MASK_BIT. Finally, the result is converted back to a pointer and returned.

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

The function isMaskFlagSet checks whether the mask bits are still set.

唯一的用例，我可以形象是：你必须每次都调用 isMaskFlagSet 你使用指针。如果屏蔽位置位，则禁止实际使用指针。

The only use case, I can image is: you have to call isMaskFlagSet every time, before you use the pointer. If the mask bits are set, then it is prohibited to actually use the pointer.

这篇关于标记指针的lockFree列表中C的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！