正在尝试实现cas-linkedlist

Question

#include <iostream>
#include <thread>
class Node
{
public:
int data;
Node* next;
Node(int i)
{
data = i;
next = NULL;
}
};
class List
{
public:
List()
{
headptr = 0L;
}
long long headptr;
long long count = 1;
void push(Node* newnode)
{
while (true)
{
long long tmph = headptr;
long long tmp = (tmph<<12) >> 12; //untag
newnode->next = (Node*)tmp;
long long cnt = (count++) << 52;
long long tagnew = (long long)newnode | cnt;
newnode = (Node*)tagnew;
if (_InterlockedCompareExchange64((volatile long long*)&headptr, tagnew, tmph) == tmph)
{
break;
}
}
}
Node* pop()
{
while (true)
{
long long headp = headptr;
long long untagheadp = (headp << 12) >> 12; //untag;
Node* headnode = (Node*)untagheadp;
long long nextp = (long long)headnode->next;
if (headp == NULL)
return NULL;
long long cnt = (long long)(count++) << 52;
nextp = nextp | cnt;
if (_InterlockedCompareExchange64((volatile long long*)&headptr, nextp, headp))
{ 
return headnode;
}
};
static List* freelist = new List();
static List* headlist = new List();
void threadbody()
{
int count = 0;
while (count < 10000)
{
for (int i = 0; i < 2; i++)
{
if (freelist->headptr != NULL)
{
Node* temp = freelist->pop();
headlist->push(temp);
}
}
for (int j = 0; j < 1; j++)
{
if (headlist->headptr != NULL)
{
Node* temp = headlist->pop();
freelist->push(temp);
}
}
count++;
}
std::cout << "Thread End" << std::endl;
}
int main()
{
for (int i = 0; i < 100000; i++)
{
freelist->push(new Node(i));
}
freelist->showcount();
std::thread t1(&threadbody);
int count = 0;
while (count < 10000)
{
for (int i = 0; i < 2; i++)
{
if (freelist->headptr != NULL)
{
Node* temp = freelist->pop();
headlist->push(temp);
}
}
for (int j = 0; j < 1; j++)
{
if (headlist->headptr != NULL)
{
Node* temp = headlist->pop();
freelist->push(temp);
}
}
count++;
}
std::cout << "Main End" << std::endl;
t1.join();
freelist->showcount();
headlist->showcount();
}

我正在尝试使用cas实现linkedlist。我使用标签实现。第一个12位是标记，52位是地址(x64(当我只运行主线程时，push-and-pop工作得很好。但是，它不适用于2线程。通过代码运行，我发现一个节点->下一个点是它自己的。不知道如何解决这个问题。提出一个想法将是一种乐趣。

Answer 1

从根本上讲，问题是getAddress对它所传递的指针有两次访问。

当您调用getAddress(&headptr);时，会读取headptr(通过getAddress的ptr参数。几条语句之后会写入headptr。在读取和写入之间，另一个线程可以成功地获得_InterlockedCompareExchange64，从而更改headptr的值。当发生这种情况时，*ptr = temp;的写入将更改前一个线程存储的值。

"廉价"的解决方案是让getAddress在写入ptr时也进行互锁交换。但是，为什么getAddress会写回*ptr呢？如果您丢失了存储在那里的标签信息，这似乎是不必要的。

与此无关，pop中对build的调用没有任何作用，因为您忽略了返回的值。

在你的代码中有很多未定义的行为，因为你假设只使用地址的低52位。像reinterpret_cast<Node*>(newptr);这样的东西可能会创建坏指针，因为非指针newptr是一个计算值，而不是指针强制转换的结果。

Answer 2

问题出在counter变量上。您对该变量使用非原子增量来计算新标记，但这是错误的。不能使用单独的变量，但必须使用嵌入headptr中的标记。标记的更新和指向下一项的指针的更新必须在单个原子操作中进行。此外，您应该考虑使用C++11原子。

作为参考，您可以从以下要点来看我对无锁堆栈的实现：https://gist.github.com/mpoeter/926a80eda0c2c2dce8424b1175a24c84