Lock-free, продолжение
Когда-то я рассказывал про lock-free Не прошло и года Прошло 1.5 года и ошибку в предложенном тогда коде нашли. Хорошо, но медленно. Предлагаю попробовать повторить. На этот раз предлагается lock free FIFO очередь, сделанная по тому же принципу. Ищем ошибку (ABA/race/leak) и способ ее исправить. Для ускорения поисков объявляется приз! Первому нашедшему предлагаю бутылку коньяка. Непьющим - эквивалент в березовом соке :)

А вообще, скорость lock-free алгоритмов прямо пропорциональна количеству использованных atomic-ов, поэтому при наличии cmpxch16b лучше пользоваться им - быстрее будет работать.
Update Первым ошибку нашел наш внимательный читатель из города Бердск
evgeny_baskakov. Евгений решил перечислить свой приз на благотвоорительность, так что приз ушел сюда, с чем всех и поздравляю!
А вообще, скорость lock-free алгоритмов прямо пропорциональна количеству использованных atomic-ов, поэтому при наличии cmpxch16b лучше пользоваться им - быстрее будет работать.
Update Первым ошибку нашел наш внимательный читатель из города Бердск
Впрочем я конечно слабо верю в безбажный lock free код на 4 экрана почти без комментариев...
а какие комментарии тебе нужны? Очередь реализована как 2 стека. В один добавляем (PushQueue), из второго достаем (PopQueue). Когда стек PopQueue кончается мы в него инвертируем PushQueue стек это ListInvertor. Против ABA защищаемся тем, что пока есть больше одного активного треда (FreememCounter > 1) мы не зовем delete. Начало/конец работы с рутом - AsyncRef()/AsyncUnref()
Для ускорения инвертирования в условиях contention при неудачном инвертировании (добавили новый элемент, пока мы инвертировали) мы не выбрасываем инвертированный список, а просто добавляем в него вновь добавленные элементы. Для этого запоминаем какой был первый элемент в ListInvertor::PrevFirst и саму копию ListInvertor::Copy-ListInvertor::Tail.
Ты не веришь в реализацию любого lock-free алгоритма? Или только для стека.
Т.е. найти ошибку она может, а доказать, что ее нет - походу не может
Memory leak
Допустим, первый тред попадает на строку 65 (cas в функции AsyncDel), второй - на строку 40 (cas в функции TryToFreeAsyncMemory). Пусть выигрывает компетицию первый, т.е. после выхода обоих тредов из их операций в очереди остаётся непустой FreePtr со своими кишками.
Затем очередь убивают. Случается вызов деструктора, и там TryToFreeAsyncMemory().
К сожалению, FreePtr и его замыкание не будут удалены, поскольку в деструкторе FreememCounter == 0.
Имеем memory leak.
Re: Memory leak
Re: Memory leak
Re: Memory leak
Ещё немного посмотрел
Но смущают строки 167-168.
Допустим, компилятор решил сделать такую совершенно валидную в контексте одного треда трансформацию (ну, регаллок тупанул, а instruction scheduler / щелевик поменяли местами загрузку локалов):
167. TRootNode *curRoot = JobQueue;
168. TListNode *tail = curRoot->PopQueue;
-->
167. TListNode *tail = JobQueue->PopQueue;
168. TRootNode *curRoot = JobQueue;
Пусть есть два треда, одновременно выполняющих Dequeue.
Один заснул между 167 и 168, а другой в это время, пройдя через обе эти строки, далее сделал
179. tail->Next = 0;
В такой ситуации первый тред, проснувшись, на строке 175 запишет 0 в newRoot->PopQueue.
Да, в теории это выглядит натянуто, но важен самый факт того, что ты опираешься на последовательность загрузки локалов из шаренной переменной. В случае неудачного выбора компилятора и/или целевого камня вся эта красота может сломаться.
В принципе, слово volatile на локалах curRoot и tail должно снять (до конца ли?) потенциальную проблему.
Re: Ещё немного посмотрел
Например,
151. TRootNode *curRoot = JobQueue;
152. newRoot->PushQueue = newNode;
153. newNode->Next = curRoot->PushQueue;
вполне может быть заменено компилятором на
151'. TLinkNode *_t1 = JobQueue->PushQueue;
151. TRootNode *curRoot = JobQueue;
152. newRoot->PushQueue = newNode;
153. newNode->Next = _t1;