khizmax
[WIP] Speculative Pairing Queue (LETI 2304)
Работали: Ефремов, Климук, Лихачев, ЛЭТИ, 2304.
Был реализован соответсвующий контейнер, но в статье очень скудно описано, как убирать память при помощи HP. Как следствие из тестов убран scan().
Как убирать память при помощи HP, описано в алгоритме HP и в куче реализаций в libcds, основанных на HP. Есть алгоритмы структур данных, к которым HP неприменим. Но в этом случае нужно: a) Объяснить, почему HP неприменим к данной структуре данных; b) Предложить метод очищения памяти для этой структуры данных; Без управления памятью реализация структуры данных бесполезна.
Технические проблемы Стресс-тесты проходятся очень по разному на разных машинах. Информация по моему ноутбуку: OS: Arch Linux Kernel: x86_64 Linux 4.14.11-1-ARCH CPU: Intel Core i7-2670QM @ 8x 3.1GHz [27.8°C] RAM: 2790MiB / 7873MiB
- На моем ноутбуке ВСЕ стресс тесты с нашим контейнером валятся с SegFault-ом, при этом все юнит тесты проходятся успешно. На 2х других машинах stress-queue-pop проходит "всегда"(ну по крайней мере почти), а остальные по разному завершаются, скорее всего из-за кривого удаления памяти на данный момент. Об этом подробнее чуть дальше, сперва все по ноутам.
- На 2-м ноутбуке, использующем WSL для тестирования и компиляции, вообще падает KERNEL_SECURITY_CHECK_FAILURE с некоторой вероятностью на тестах, но это проблема окружения скорее всего. В другом окружении работать не могу в связи с очевидными проблемами ноутбука(Краш экрана и зависание при различных условиях). В итоге у нас из 3 ноутбуков два просто не способны запускать стресс тесты по разным причинам, остается один, который с трудом выживает из-за своей древности. Крик о помощи Был вариант как-то настроить travis для тестов, но это явно не кратковременное и быстрое действие, да и непонятно вообще возможно ли это.
Об удаление памяти В алгоритме есть два способа удаления памяти, они же описаны в статье.
- Удаление самой очереди. В общем-то оно в некотором смысле реализовано, но все равно непонятно откуда проявляются такие вещи как double free, invalid pointer и прочее.
Логика удаления: каждый поток защищает при помощи HP текущий указатель на очередь. Если очередь становится invalid, то поток ее удаляет. В итоге, когда не останется потоков, которые используют текущую очередь, то она удаляется физически и удаляется все ее содержимое.
Как реализовано: protect при помощи Guard указателя на очередь в начале функций добавления\удаления. Когда очередь становится invalid, то вызывается retire<disposer_queue>(Queue). Внутри disposer удаляются все ноды, которые присутствуют в "старой" очереди. Поскольку потоки не используют этот указатель и очередь, а используют новую очередь, то удаляться должно без проблем.
Проблема: периодически проскальзывает либо free() invalid pointer, либо double free или munmap_chunk() invalid pointer. При этом отследить причины сего так и не удалось
- Удаление "Устаревших" нод. Логика: ищутся устаревшие ноды, которые являются удаленными. Последняя устаревшая становится head. Все это срабатывает в потоке удаления с некоторой вероятностью
Как реализовано: метод dispose_stale_nodes, который с некоторой вероятностью(probStale) запускает поиск нод и и удаляет их с помощью dispose_node. Особо не тестировалось и не проверялось, поскольку есть проблемы с верхним способом удаления.
Собственно, необходима помощь по удалению очереди, потому что непонятно что происходит внутри либы, в какой точно момент действительно вызывается удаление и как именно происходит повторное удаление например.
Некоторые стресс тесты иногда проходятся, но лишь иногда. Подтверждение того, что происходит у нас на стрессах:
Ну что ж, добро пожаловать в параллельный мир ;-) Проблемы с double free и все прочие - это одна сторона одной и той же медали. Думаю, причина только одна: двойное удаление, о ней же честно пишет glibc при крахе. Сценарий: один поток удаляет блок M, второй поток удаляет блок M. Как правило, это означает, что где-то в алгоритме контейнера есть дыра: например, поток 1 исключает ноду из контейнера и делает для неё retire, а поток 2 работает с этой нодой без защиты HP'ом. Вторая возможная причина - обращение к освобожденной памяти (не похоже). Как фиксить подобного рода ошибки: a) asan (AddressSanitizer) - он может помочь понять, что проблема действительно с памятью. Но это и так тут понятно. Так как HP использует по сути отложенное удаление, то источник ошибки (место, когда один и тот же блок памяти дважды освобождается) часто может быть невидим для asan. b) Анализ алгоритма мозгом.
После беглого просмотра вот что мне бросилось в глаза:
- Для atomic ops везде используется memory_order_relaxed. Это неправильно. Может ли это быть источником проблемы?.. В принципе, да, так как memory_order влияет в том числе и на поведение оптимизатора компилятора (memory_order - это [полу]барьеры компиляции). Но маловероятно. Для тестовых целей лучше всего использовать memory_order_seq_cst.
-
pQueue->m_Invalidдолжен быть атомарным, так как к этому флагу идет обращение из разных потоков. Чтение/запись данного флага: load( acquire ), store( release ). Может ли это быть причиной падений?.. В принципе, может, но маловероятно. - А вот настоящая причина (ошибка), мне кажется:
value_type* dequeue()
{
typename gc::template Guard queue_guard;
typename gc::template GuardArray<3> guards;
Queue* pQueue = guards.protect(0, m_Queue);
должно быть Queue* pQueue = queue_guard.protect(m_Queue);
Изменения ввели, стресс тесты стали ввести себя постабильней, но все еще выкидывают те же ошибки. Собственно, вопрос в чем. Система GC в libcds учитывает вхождения одного и того же указателя в список удаленных или вызовет disposer на каждый вызов retire? В данный момент просто retire вызывается, когда invalid становится true, из-за чего несколько deq могут одновременно вызвать retire для одной очереди. При переносе вызова retire после создания новой очереди стресс-тест pop проходится стабильно и всегда, отчего и возник этот вопрос.
Какие способы отладки самого контейнера можно использовать, потому что поиск источника проблемы очень затруднителен сам по себе? И как точно использовать эту библиотеку для создания нашего контейнера в отдельное приложение? Это касается линковки(использовать исходный код libcds или shared libs, проблема 1-го способа что компилятор не может разрешить все include, а проблема 2-го что его непонятно как слинковать, а во-вторых как использовать дебаггером)
P.S.> В зависимости от модели памяти, разнится количество консумеров (stress-push-pop):
4/6 Test #4: stress-queue-push-pop ............***Failed 1.42 sec
Using test config file: ./test-debug.conf
Hardware concurrency: 8
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from intrusive_queue_push_pop
[ RUN ] intrusive_queue_push_pop.SPQueue_HP
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:353: Failure
Expected: nBadConsumerCount
Which is: 500000
To be equal to: 0u
Which is: 0
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:273: Failure
Expected: nTotalPops + nPostTestPops
Which is: 0
To be equal to: nQueueSize
Which is: 500000
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:305: Failure
Expected: arrData[arrData.size() - 1]
Which is: 1003522
To be equal to: s_nThreadPushCount - 1
Which is: 124999
Writer 0
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:305: Failure
Expected: arrData[arrData.size() - 1]
Which is: 1000017
To be equal to: s_nThreadPushCount - 1
Which is: 124999
Writer 1
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:304: Failure
Expected: arrData[0]
Which is: 140278639344384
To be equal to: 0u
Which is: 0
Writer 2
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:305: Failure
Expected: arrData[arrData.size() - 1]
Which is: 1000017
To be equal to: s_nThreadPushCount - 1
Which is: 124999
Writer 2
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:304: Failure
Expected: arrData[0]
Which is: 140278639344384
To be equal to: 0u
Which is: 0
Writer 3
/home/jakutenshi/study/3rd Sem/parallel programming/idp/libcds/test/stress/queue/intrusive_push_pop.cpp:305: Failure
Expected: arrData[arrData.size() - 1]
Which is: 1000017
To be equal to: s_nThreadPushCount - 1
Which is: 124999
Writer 3
[ FAILED ] intrusive_queue_push_pop.SPQueue_HP (1402 ms)
[----------] 1 test from intrusive_queue_push_pop (1402 ms total)
[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (1402 ms total)
[ PASSED ] 0 tests.
[ FAILED ] 1 test, listed below:
[ FAILED ] intrusive_queue_push_pop.SPQueue_HP
1 FAILED TEST
Стресс-тест на pop проходит успешно всегда теперь.
Собственно, вопрос в чем. Система GC в libcds учитывает вхождения одного и того же указателя в список удаленных или вызовет disposer на каждый вызов retire? В данный момент просто retire вызывается, когда invalid становится true, из-за чего несколько deq могут одновременно вызвать retire для одной очереди. При переносе вызова retire после создания новой очереди стресс-тест pop проходится стабильно и всегда, отчего и возник этот вопрос.
"Система GC" в libcds - тупая как пробка и не предоставляет никаких бонусов: вызов retire - это по сути отложенный вызов delete/free() и ничего более. Соответственно, если один и тот же указатель освобождать дважды через вызов retire, получим memory double free.
Какие способы отладки самого контейнера можно использовать, потому что поиск источника проблемы очень затруднителен сам по себе?
Надежных способов отладки конкурентных контейнеров (и вообще параллельных программ) на сегодняшний день в мире не существует. Дебаггер здесь не поможет, так как самые трудные ошибки возникают при взаимодействии потоков на оптимизированном (не дебажном) коде. Некоторые инструменты, вроде ThreadSanitizer (tsan), могут дать некоторую подсказку, но основным инструментом является мозг и анализ алгоритма. Часто ошибки возникают тогда, когда в алгоритме есть какая-то маленькая дыра между анализом некоторого состояния контейнера/ноды и сменой этого состояния. Например, в вашем случае эта дыра может быть здесь (не уверен, привожу просто как иллюстрацию): "retire вызывается, когда invalid становится true".
Как я отлаживаю: при возникновении ошибки я смотрю на алгоритм контейнера и стараюсь в голове промоделировать поведение двух/трех потоков: "если поток 1 выполняет строку N метода push(), а в это время поток 2 выполняет строку K метода pop(), то..." При этом надо учитывать memory_order, так как при оптимизации код, который вы написали, и код, который выполняется, могут сильно отличаться. Memory_order как раз и задает в том числе и [полу]барьеры компилятора.
И как точно использовать эту библиотеку для создания нашего контейнера в отдельное приложение? Это касается линковки(использовать исходный код libcds или shared libs, проблема 1-го способа что компилятор не может разрешить все include, а проблема 2-го что его непонятно как слинковать, а во-вторых как использовать дебаггером)
Честно говоря, я вообще здесь не понял, в чем трудность. Использовать так же, как и любую другую: собрать shared lib. "Проблема 1-го способа что компилятор не может разрешить все include" - это значит, что либо пути не заданы (ключ -I для gcc), либо что-то забыли включить. "а проблема 2-го что его непонятно как слинковать" - ??? Так же как все остальные программы.
Итак. Краткий фидбек по статье. Судя по всему в ней есть логическая ошибка в enqueue. Обьясняю: Если один поток по какой-то причине не изменил при помощи CAS head текущего слота, то по статье он должен увеличить при помощи CAS tail на 1, если получится(При условии что не ПИКЕТ). Но, если ему удается его изменить, то head никогда не получит свое значение, потому что tail всегда будет больше Size. В итоге enqueue упадет с Segfault, поскольку другой поток дойдет до новой вставки в этот слот и будет пытаться действовать с расчетом на то, что head не nullptr, на что явно рассчитывали авторы в статье(Есть конкретная фраза про это). Убрав CAS на tail внутри обработки первых элементов проблему можно обойти и тесты более или менее успешно проходятся. С очень редкой вероятностью падает pop тест, потому что почему-то вытаскивает не всю очередь. И падает push-pop, поскольку имеет почти 70к nBadConsumer.
P.S. unit тесты не переделаны под чистку очереди в Push, а потому не проходятся.
Здравствуйте,
Итого, мы сегодня пытались разобраться в проблеме почему оказывается pHead == nullptr. В итоге оказалось, что CAS в 463 строке, который заменяет nullptr (DUMMY) на новый элемент pNewNode работает очень выборочно: перед CAS появляются все потоки (tail на это указывают), а окончательно срабатывает CAS не на всех, появляются потоки, которые по-идее имели pHead == nullptr, но не прошли CAS, и причина этому не понятна. Пример вывода (можете проверить, запустив, я добавил отладочный вывод в коммит):
Using test config file: ./test.conf
Hardware concurrency: 8
[==========] Running 4 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 4 tests from queue_push
[ RUN ] queue_push.SPQueue_HP
______tail_before = 0 Head = 0 tail_after_1 = 0______
tail_before = 0 Head = 0 tail_after_2 = 0
tail_before = 0 Head = 0x7f9344001d70 tail_after_2 = 0
tail_before = 0 Head = 0 tail_after_2 = 0
tail_before = 0 Head = 0 tail_after_2 = 0
tail_before = 0 Head = 0x7f9344001d70 tail_after_2 = 0
tail_before = 0 Head = 0x7f9344001d70 tail_after_2 = 0
=======tail_before = 1 Head = 0 tail_after_2 = 1=======
tail_before = 0 Head = 0 tail_after_2 = 0
=======tail_before = 1 Head = 0 tail_after_2 = 1=======
=======tail_before = 1 Head = 0 tail_after_2 = 1=======
______tail_before = 2 Head = 0 tail_after_1 = 2______
tail_before = 2 Head = 0x7f9348001d70 tail_after_2 = 2
tail_before = 2 Head = 0x7f9348001d70 tail_after_2 = 2
tail_before = 3 Head = 0 tail_after_2 = 3
tail_before = 3 Head = 0x7f9348001e40 tail_after_2 = 3
tail_before = 4 Head = 0 tail_after_2 = 4
tail_before = 4 Head = 0 tail_after_2 = 4
tail_before = 4 Head = 0 tail_after_2 = 4
tail_before = 4 Head = 0 tail_after_2 = 4
______tail_before = 4 Head = 0 tail_after_1 = 4______
tail_before = 5 Head = 0x7f9340001d70 tail_after_2 = 5
tail_before = 5 Head = 0x7f9340001d70 tail_after_2 = 5
tail_before = 5 Head = 0x7f9340001d70 tail_after_2 = 5
______tail_before = 3 Head = 0 tail_after_1 = 3______
tail_before = 5 Head = 0x7f9340001d70 tail_after_2 = 5
______tail_before = 5 Head = 0 tail_after_1 = 5______
tail_before = 6 Head = 0 tail_after_2 = 6
______tail_before = 6 Head = 0 tail_after_1 = 6______
tail_before = 6 Head = 0 tail_after_2 = 6
tail_before = 6 Head = 0x7f9348001e60 tail_after_2 = 6
tail_before = 6 Head = 0 tail_after_2 = 6
tail_before = 7 Head = 0x7f9348001e80 tail_after_2 = 7
tail_before = 6 Head = 0 tail_after_2 = 6
tail_before = 7 Head = 0x7f9348001e80 tail_after_2 = 7
tail_before = 6 Head = 0x7f9348001e60 tail_after_2 = 6
______tail_before = 7 Head = 0 tail_after_1 = 7______
=======tail_before = 8 Head = 0 tail_after_2 = 8=======
tail_before = 7 Head = 0x7f9348001e80 tail_after_2 = 7
______tail_before = 9 Head = 0 tail_after_1 = 9______
tail_before = 9 Head = 0 tail_after_2 = 9
tail_before = 7 Head = 0x7f9348001e80 tail_after_2 = 7
=======tail_before = 8 Head = 0 tail_after_2 = 8=======
=======tail_before = 8 Head = 0 tail_after_2 = 8=======
tail_before = 7 Head = 0x7f9348001e80 tail_after_2 = 7
Выделены строки, когда CAS прошел (выделены ______). Можно увидеть, что при tail = 1 и 8 CAS не был пройден, но поток до него доходил (выделены =======) и при этом pHead = 0.
Кроме того, стот отметить, что этот результат был получен на машине Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz с ArchLinux, на машине с Windows 10, Intel Pentium CPU B960 тесты на push проходятся, а push-pop валятся тесты, но с другой ошибкой (недостающие элементы). Т.е. имеется проблема, судя по-всему в разнице аппаратной. Просьба проверить результаты со стороны (было еще предложение про предоставление ssh для тестов, но я не уверен, что вообще с этим есть какая-то проблема, в основном тесты делаются на Arch).
Вопросы следующие: в чем может быть проблема, может ли это быть проблема процессора конкретного с CAS операцией (вряд ли но все же)? Потому что у меня (Arch i7) проблемы валятся гораздо чаще. Ставились везде sequential_consistent, для строгости выполнения операций на CAS, может ли это как-то влиять в негативную сторону (производительность сейчас в расчет не берется)? Возможно, по такой информации, Вы сможете подсказать в чем может быть проблема?
По своему опыту могу сказать, что
может ли это быть проблема процессора конкретного с CAS операцией (вряд ли но все же)?
можно отбросить сразу, хотя иногда и очень хочется свалить все на процессор.
Ставились везде sequential_consistent, для строгости выполнения операций на CAS, может ли это как-то влиять в негативную сторону
Здесь вы все сделали правильно, seq_cst - наиболее сильный memory order, если и на нем что-то не так, - значит, есть проблема.
Т.е. имеется проблема, судя по-всему в разнице аппаратной.
Думаю, проблема не в аппаратной части, а в разных компиляторах. На Linux - gcc, на Win - MSVC++, да? К сожалению, у MSVS сейчас компилятор - дерьмо, они уже 7 лет догоняют стандарт C++11, все догнать не могут.
Конкретного чего-нибудь сейчас сказать не могу, - надо разбираться с алгоритмом и реализацией. Это не просто для lock-free структур, - некоторые ошибки я искал месяцами, инструментов для поиска, кроме TSan (выхлоп которого тоже иногда трудно понять), в мире нет. Бывает, что сам алгоритм содержит в себе непреодолимый косяк, надо только это понять.
В итоге оказалось, что CAS в 463 строке, который заменяет nullptr (DUMMY) на новый элемент pNewNode работает очень выборочно: перед CAS появляются все потоки (tail на это указывают), а окончательно срабатывает CAS не на всех, появляются потоки, которые по-идее имели pHead == nullptr, но не прошли CAS, и причина этому не понятна.
Я, честно говоря, этого не понял: CAS на то и CAS, чтобы для всех потоков CAS срабатывал только в одном. Atomic compare and swap. Победитель всегда только один.
Я, честно говоря, этого не понял: CAS на то и CAS, чтобы для всех потоков CAS срабатывал только в одном. Atomic compare and swap. Победитель всегда только один.
@khizmax Да, это так. Суть в том, что другие потоки, не пройдя CAS возвращаются и снова пытаются его применить. Т.е. на каждый tail должно было быть срабатывание tail_after_1 ветки. В примере выше для 1 и 8 - это не так. Причем tail=1 и tail=8 имеются с pHead = 0 , но, почему-то, ни один из них не заходит в условие с выполненым CAS. Это и не понятно.
Update: Инициализация DUMMY непосредственно перед CAS внезапно делает push тест проходным. Причина пока непонятна, т.к. DUMMY как бы и не должен меняться: нету операций, которые его меняли бы.
Здравствуйте, @khizmax
Предыдущая проблема решилась в связи с описанным в Update: объявление и инициализация локального DUMMY = nullptr непосредственно перед CAS решила проблему. БОЛЬШОЙ ВОПРОС: каким образом изменялся DUMMY, если он не присваивается нигде больше и все взаимодействие с ним происходит только в CAS, т.е. реально каким образом (и может ли, но тут практика показывает - МОЖЕТ) CAS меняет значение той переменной, по которой он сравнивает значение??
Далее, итого, решены все проблемы с SEGFAULT, работа с памятью сделана (по очищению всей очереди). Далее, что по тестам: в 80% случаев оно проходится. Далее, идет объяснение что с остальными 20%, но на этом месте я кастую @eugenyk чтобы зафиксировать уровень выполненности задания и оценить проблему уже решенную (с DUMMY и непониманием как так работает CAS) и проявившуюся.
Итак, в 20% случаев (1-2 срабатывание из 10 запусков pop с push-pop) в этих тестах каким-то образом недосчитывалось одного элемента. В ходе анализа было локализовано, что проблема строго в pop (не в push, потому что падает в тесте на pop в котором push происходит последовательно, а то, что последовательный push работает корректно на 5М элементах было проверено дополнительным исправлением в юнит тесте на item_counter). Тот факт, что все остальные элементы у нас отлично фигурируют (т.е. постоянно происходит недочет только одного элемента) и то, что ошибка в тесте показывает сдвиг ожидаемого значения строго на единицу, говорит о том, что pop провального элемента либо выдает nullptr в самом конце dequeue, либо пропускается сам элемент. Первое, исходя из того, что ошибка появляется один раз, а все остальные элементы нормально достаются, исключается. Значит, остается только то, что пропускается элемент.
Далее, вопрос где эта ошибка может быть: соответсвенно, только в месте, где происходить FAI Cntdeq, потому что это единственный момент, где элемент можно "пропустить", ибо все идет через этот счетчик. Для анализа проблемы после получения ticket-а от FAI выводится сам ticket. Результаты тестирования писались в файл (были шокирующими). Спустя приличное время тестирования (опять же, ошибка достаточно редко проходила, а тесты с записью в 465Мб идет долго), было получено 2 ошибки на pop, в которых ясно видно (см. скриншот), что после 5М элемента идет странный 4998610 элемент. Проверяем: перезодим вверх на его позицию (читайте в vim 4998631gg) получаем следующий скриншот и видим следующее:
- нашего 4998610 элемента просто нет!
- выше элементы есть, но они переставлены местами. Это может быть, в теории, проблемой вывода, но предыдущий пункт - нет (как минимум потому что ошибка указывает конкретно на него - раз, два - этот кейс повторился дважды на 10 тестах).
Скриншоты
Итого, пока что предположение, что, по-аналогии со странной работой CAS, FAI делает что-то не очевидное и очень редкое. Кроме того, есть мнение, что один поток застревает на FAI (как раз тот, который должен был вернуть 4998610 элемент) по непонятной причине (планировщик?), а после того, как он приходит к работе - этот момент, когда все остальные потоки закончили свою работу (поэтому он и появляется в конце) - тогда наша очередь инвалидируется и на том месте, где бедный отсталый поток пытается найти свое значение, но находит лишь PICKET, вследствие чего все так же грустно возвращает nullptr, в соответствии с алгоритмом. Тем самым, разумеется, заваливая тест на этом самом элементе.
Это только гипотеза, т.к. проверить что именно не так с FAI мы не видим возможности, как следствие - не понятно как проверять это.
Собственно, т.к. у нас 22 будет последний экзамен и к нему нам надо готовиться, большая просьба ответить на этот комментарий (понять и простить?), объсянив как так и что случилось с CAS (потому что вот, конкретно проблема была обнаружена и решена, конкретным образом) и что делать с FAI. (и возможно, убрать угрозу дедлайна и ведомости..? Поскольку с каждым шагом проблемы от очень странных переходят в разряд мистики)
Спасибо.
Предыдущая проблема решилась в связи с описанным в Update: объявление и инициализация локального DUMMY = nullptr непосредственно перед CAS решила проблему. БОЛЬШОЙ ВОПРОС: каким образом изменялся DUMMY, если он не присваивается нигде больше и все взаимодействие с ним происходит только в CAS, т.е. реально каким образом (и может ли, но тут практика показывает - МОЖЕТ) CAS меняет значение той переменной, по которой он сравнивает значение??
См. аргументы compare_exchange (CAS): первый аргумент передается по ссылке: на входе он содержит ожидаемое значение атомарной переменной, на выходе - текущее значение до exchange. Когда вы объявляете DUMMY без инициализации, DUMMY содержит мусор. Как только вы инициализировали DUMMY, все стало хорошо. Так что дело не в том, что DUMMY изменялся, а в том, что он содержал мусор и иногда этот мусор был равен nullptr.
Итак, в 20% случаев (1-2 срабатывание из 10 запусков pop с push-pop) в этих тестах каким-то образом недосчитывалось одного элемента. В ходе анализа было локализовано, что проблема строго в pop (не в push, потому что падает в тесте на pop в котором push происходит последовательно, а то, что последовательный push работает корректно на 5М элементах было проверено дополнительным исправлением в юнит тесте на item_counter).
Эта ситуация мне очень хорошо знакома. Причина может быть и в push, и в pop.
Надо анализировать, что происходит, когда push и pop встречаются на каком-то элементе. Ищите проблему в алгоритме; CAS и FAI работают правильно, если их правильно применять.
Возможные сценарии:
- Из-за дырки в алгоритме push считает, что он положил в очередь, тогда как на самом деле не положил ("не доложил"). Например, ему помешал pop (или другой push). Получаем утечку памяти.
- Опять-таки из-за дырки pop удаляет очередной элемент из очереди, но считает, что удаление неудачно. Причина - помешал параллельный push/pop.
Собственно, т.к. у нас 22 будет последний экзамен и к нему нам надо готовиться, большая просьба ответить на этот комментарий (понять и простить?), объсянив как так и что случилось с CAS (потому что вот, конкретно проблема была обнаружена и решена, конкретным образом) и что делать с FAI. (и возможно, убрать угрозу дедлайна и ведомости..? Поскольку с каждым шагом проблемы от очень странных переходят в разряд мистики)
:-) Добро пожаловать в волшебную вселенную. Оценивать работу будет @eugenyk, я лишь могу констатировать, что вы напоролись на половину подводных камней волшебного мира конкурентных контейнеров, и это нормально, так как тема довольно сложная и требует предельной аккуратности как в мыслях, так и в коде. Надеюсь, спустя несколько лет эти проблемы будут казаться вам элементарными.
Спасибо за ответ, @khizmax , есть пару но:
Когда вы объявляете DUMMY без инициализации, DUMMY содержит мусор. Как только вы инициализировали DUMMY, все стало хорошо. Так что дело не в том, что DUMMY изменялся, а в том, что он содержал мусор и иногда этот мусор был равен nullptr.
В том-то и дело! В самом начале enqueue DUMMY объявлялся и инициализировался как nullptr (414 строка)! Он там так и остался сейчас. Это и сбивает с толку, откуда мусор. Поэтому Ваш ответ не помогает понять что произошло точно, если честно. Т.е., если взять последний коммит и убрать оттуда объявления и инициализацию DUMMY перед CAS - полезут ошибки. А DUMMY в начале таким nullptr и будет инициализироваться.
Из-за дырки в алгоритме push считает, что он положил в очередь, тогда как на самом деле не положил ("не доложил"). Например, ему помешал pop (или другой push). Получаем утечку памяти.
Так этот вариант и исключили проверкой последовательным push, что нету ситуации, когда он не докладывает в очередь.
Насчёт второго надо подумать, я пишу с телефона сейчас и надо смотреть причины false в деке: это, вроде, только нахождение узла PICKET, т.е. ещё один плюс к описанной гипотезе в предыдущем комментарии.
При анализе кода бросилось в глаза следующее:
if (std::atomic_compare_exchange_strong(&pQueue.load(memory_order_relaxed)->
m_pair[idx].m_pHead.load(memory_order_relaxed), nullptr, pNewNode)) {
pQueue.load(memory_order_relaxed)->m_pair[idx].m_Last = pNewNode;
break;
}
Смотрим atomic_compare_exchange_strong:
Atomically compares the object representation of the object pointed to by obj with the object representation of the object pointed to by expected, as if by std::memcmp, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value pointed to by obj into *expected (performs load operation).
В качестве expected у вас здесь стоит nullptr. упс...
Вообще, я не понимаю, зачем использовать свободные функции std::atomic_XXX, когда у класса std::atomic они уже есть. И учтите, что у std::atomic::compare_exchange первый аргумент передается по ссылке!!!
UPD: это, думаю, и ответ на ваш вопрос:
В том-то и дело! В самом начале enqueue DUMMY объявлялся и инициализировался как nullptr (414 строка)! Он там так и остался сейчас. Это и сбивает с толку, откуда мусор.
Первый аргумент CAS передается по ссылке и изменяется на выходе!
Мне кажется вы просматривается старые коммиты, потому что уже давно поменяли на обычные атомики, обернули nullptr в DUMMY и т.п. Std::atomic_XXX использовался полтора месяца где-то что ли.
в Push проблемы нет, ибо проблема с FAI воспроизводится и в тесте Pop, в котором все Push выполняются последовательно до выполнения параллельных Pop. Ну по крайней мере, это явно не проблема параллельного взаимодействия push и pop.
У меня появилась одна идея как это можно исправить, но к вечеру смогу только попробовать. Если не прокатит, то делаю рефакторинг и оставляю последнюю версию как она есть
Я смотрю master-ветку
Перейдите на ветку efremov, там все коммиты должны быть. Но вопросы по репозиторию лучше перешлю @JAkutenshi. он его контролирует :)
Этот пул-реквест основан на ветке efremov, да. Почему так: потому что предполагалось, что каждый будет работать в своей ветке, но из-за различиях в машинах удобнее было работать на моей и, соответсвенно, в этой же ветке. Ну и потом был сделан пулреквест и этой ветки, а не из мастер, скорее-всего, потому что была спешка. Но, думаю, с этим не должно быть проблем
Итог
- Push решен путем инициализации DUMMY перед CAS
- Pop решен(?) путем добавления прохода по слоту, если последний удаленный - PICKET. В этом же и недочет алгоритма, не описанный в статье. Подробнее дальше.
- Push-pop, SPSC и оооочень редко random не проходятся и все с одной ошибкой - очередь теряет элементы. Поскольку даже SPSC падает, т.е. один читатель и один писатель, то подразумеваю что проблема в неочевидном взаимодействии потоков. Быстро причину не назову, да и искать ее не имею не малейшего понятия как.
Немного про POP В алгоритме не учитывается одна дыра. Обьясню на примере: Допустим что есть два потока pop. Первый решил удалить последний элемент в слоте, а второй элемент nullptr после этого элемента. (Для понимания, второй поток просто доставит PICKET вместо это элемента и сделает очередь невалидной) Так вот, если первый элемент взял билетик(ticket), но еще не загрузил в локальную переменную m_pRemoved("последний" удаленный элемент), а второй поток в этот момент закончил свой алгоритм и сделал m_pRemoved равным PICKET, то первый поток после получения m_pRemoved получит PICKET и посчитает что очередь нужно инвалидировать, вместо того чтобы получать свой элемент. Для решения этого можно добавить условие, что если pNode == PICKET то брать голову списка и проходить по полному алгоритму. После добавления этого условия pop стал проходить стабильно.
К сожалению, это никак не повлияло на push-pop, но в нем проблема в параллельном использовании push и pop и их взаимодействии судя по всему. Да и сложно оценить правильность такого решения, хотя и выглядит оно вполне логичным на мой взгляд.
@khizmax , пока что у меня лично сессия в процессе сдачи, но работа будет продолжена через несколько дней. Перевел статус в WIP.
