Попытка реализовать cas связанный список

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. Я реализую с помощью тега. первый 12-битный тег, а 52-битный адрес (x64) pu sh, и pop работает нормально, когда я запускаю только основной поток. Но, это не работает с 2 потоком. Проходя через код, я обнаружил, что узел -> следующий указывает сам по себе. Не могу понять, как решить эту проблему. Давать идею было бы приятно.

Answer 1

Проблема в вашей переменной counter. Вы используете non-atomi c приращения этой переменной для вычисления нового тега, но это неправильно. Вы не можете использовать отдельную переменную, но вы должны использовать тег, встроенный в ваш headptr. Обновление тега и указатель на следующий элемент должны выполняться в операции single atomi c . Кроме того, вам следует рассмотреть возможность использования атомарного кода в C ++ 11.

В качестве справочного материала вы можете взглянуть на мою реализацию стека без блокировки в этой сущности: https://gist.github.com/mpoeter/926a80eda0c2c2dce8424b1175a24c84

Answer 2

По сути, проблема в том, что getAddress имеет два доступа к указателю, который ему передан.

Когда вы вызываете getAddress(&headptr);, происходит чтение headptr (через параметр ptr из getAddress. Несколько операторов позже есть запись в headptr. Между этим чтением и этой записью другой поток может иметь успешный _InterlockedCompareExchange64, который изменяет значение headptr. Когда это происходит, запись *ptr = temp; изменит значение, сохраненное предыдущим потоком.

«Дешевое» исправление - getAddress также выполняет блокированный обмен при записи в ptr. Однако, почему getAddress пишет вернуться к *ptr вообще? Это кажется ненужным, если вы потеряете информацию о тегах, хранящуюся там.

Не связано, вызов build в pop ничего не делает, так как вы игнорируете возвращаемое значение.

И в вашем коде много неопределенного поведения, поскольку вы предполагаете, что используются только младшие 52 бита адреса. Такие вещи, как reinterpret_cast<Node*>(newptr);, могут создавать плохие указатели, так как не указатель newptr является вычислением значение ted, а не результат приведения из указателя.