Стирание без блокировки - PullRequest
Новая
       41

Стирание без блокировки

0 голосов
/ 20 июня 2019

Я пытался реализовать операцию удаления слайдов без блокировки, но у меня явно возникали проблемы с ней.К сожалению, мне действительно это нужно.

Для решения обычных проблем, связанных с ABA cmpxchg, я написал tagged_ptr <> класс «smart pointer», который встраивает счетчик в указатель, хранящийся в std :: atomic <>.Значение тега увеличивается каждый раз, когда указатель обновляется с помощью CAS в списке: head.compare_exchange_weak(old, old(newptr)) сохраняет newptr с увеличенным тегом от old.Это допускает транзакции с несколькими записями, но не решает проблемы обновления двух указателей одновременно.(например, реализовать стек легко с tagged_ptr <>)

См. код здесь .В строке 256 находится функция erase (): 

bool erase(list_node * node) {
    std::atomic<tagged_ptr<list_node>>* before;
    tagged_ptr<list_node> itr, after;
    for(;;) {
        // Find previous (or head) before-node-ptr
        before = &head;
        itr = before->load(std::memory_order_acquire);
        while(itr) {
            if(itr.get() == node) {
                break;
            } else if(itr.is_void()) {
                // Thread interfered iteration.
                before = &head;
                itr = before->load(std::memory_order_acquire);
            } else {
                // Access next ptr
                before = &itr->next;
                itr = before->load(std::memory_order_acquire);
            }
        }

        after = node->next.load(std::memory_order_acquire);
        if(after.is_void() || !itr) {
            return false;
        }

        // Point before-ptr to after. (set head or previous node's next ptr)
        if(before->compare_exchange_strong(itr, itr(after))) {
            // Set node->next to invalid ptr.
            // list iterators will see it and restart their operation.
            while(!node->next.compare_exchange_weak(after, after().set_void()))
                ;
            return true;
        }
        // If *before changed while trying to update it to after, retry search.
    }
}

В тестовом коде два потока одновременно помещают узлы в список, а два потока ищут случайный узел по данным и пытаются стереть их.У меня есть ошибка:

  • список становится циклическим (список заканчивается каким-либо образом), и поэтому потоки застревают навсегда, повторяя список, не находя конца списка.

1 Ответ

1 голос
/ 20 июня 2019

У меня есть некоторые сомнения относительно вашей tagged_ptr реализации.Кроме того, у меня есть некоторые сомнения относительно этой части кода: 

         } else if(itr.is_void()) {
                // Thread interfered iteration.
                before = &head;
                itr = before->load(std::memory_order_acquire);

Допустим, поток удалил последний узел (у вас был 1 узел в списке, и оба потока вызвали стирание).Оставшаяся нить будет запрашивать указатель на голову, это void.Вы войдете в бесконечный цикл с этой частью кода, поскольку она находится в цикле while(itr).

Эта часть также не является атомарной: 

            // Point before-ptr to after. (set head or previous node's next ptr)
            if(before->compare_exchange_strong(itr, itr(after))) {
                // Set node->next to invalid ptr.
                // list iterators will see it and restart their operation.
                while(!node->next.compare_exchange_weak(after, after().set_void()))
                    ;
                return true;
}

Если before измененопо первому CAS ваш node является указателем без привязки, все еще указывающим на список.Еще один поток может установить before на этот node, изменить его и вернуть.Честно говоря, если ваш список циклический, его не так сложно отладить, просто пройдите под отладчиком и следуйте списку.Вы увидите, когда он зациклится, и вы сможете выяснить, как он это сделал.Для этого вы также можете использовать valgrind.

Класс tagged_ptr трудно понять, с помощью метода "set_void ()", который устанавливает для внутреннего ptr значение 0xFF..F, но в то же время используется логический тест while (itr) вернет true, если это "void".Я предполагаю, что имя должно быть неверно , а не void , и оно должно возвращать false в операторе bool, если оно (не соответствует действительности).Если itr становится void (это возможно в приведенном выше коде, насколько я понимаю), while(itr) будет зацикливаться бесконечно.

Например, допустим, у вас было: 

Head:A -> B -> C

Затем, после удаления некоторого потока, вы получаете 

Thread 2 removing C : Head:A, before = &B on first iteration, exiting the while(itr) loop since itr == C (scheduled here)
Thread 1 removing B : Head:A->C and B->C (scheduled just before line 286 of your example)
Thread 2 resume, and will modify B to B->null (line 283)
and then C->null to C->yourVoid (line 286, then it's scheduled)

Then, thread 1 update B->next to B->yourVoid (useless here for understanding the issue)
You now have A->C->yourVoid

Всякий раз, повторяя здесь, вы получите бесконечный циклтак как, когда поиск itr прибывает на C, следующий шаг должен быть «пустым», а перезапуск итерации с head здесь ничего не решает, это даст тот же результат, список не работает.

...