Автоматическое fuzzy-планирование потоков с помощью relacy для обнаружения ошибок в многопоточном коде

Проблема

Проверка многопоточного кода (особенно lock-free) одной из основных составляющих включает себя постоянное стресс-тестирование, причём не от хорошей жизни. Даже при реализации подобных алгоритмов на Java, так как там есть AtomicReference и нет ABA, никто не отменяет наличия других ошибок || программирования. Текущие проверки обычно сводятся к:

проверить производительность (заданная масштабируемость на 1 и N потоках-работниках по идее должна быть сильно выше lock-based версии, если подобрать верно контейнер)

отсутствие использования примитивов типа mutex и т.п. (и то иногда бывает полезно задействовать spin-lock)

искусственно поостанавливать потоки так, чтобы остальные продолжали выполнять задачи (это уже не просто)

ThreadSanitizer или аналоги

Пути решения

С другой стороны, был очень хороший доклад Димы Вьюкова про Fuzzing Test на конференции C++ Russia. Суть в том, что с помощью специальной инструментации кода fuzzer может строить последовательности входных данных “с нуля” такие, которые максимизируют покрытие кода. За 15 минут простейший fuzzer длиной 5 строк кода нашел более 10 ошибок в boost.regexp (boost 1.63). Максим Хижинский немного поговорил с докладчиком, как приспособить этот подход к тестированию lock-free алгоритмов. Сошлись на том, что здесь в качестве “входной последовательности” должен выступать свой собственный планировщик (за отправную точку можно взять relacy), который мог бы планировать потоки так, чтобы максимизировать покрытие кода. Это как-то перекликается с “искусственно поостанавливать потоки” из п.3, но более разумно, так как такой планировщик может заглянуть в instrumented code и посмотреть, что и где нужно останавливать/ запускать и с какими данными

Ближайшие задачи

Разобраться на тестовых примерах как работать с relacy

Разобраться с LLVM/clang для формирования видения порядка управления потоками во время исполнения

Сделать/взять простую реализацию списка и искусственно внести туда ошибки

Натравить relacy

Продумать шаги, как сделать из relacy что-то типа fuzzer'a