thread-safe lock-free shared_ptr — приключение на полгода

Есть такой смешной вопрос «Is shared_ptr thread-safe?». Обычно либо человек сразу понимает о чем речь, либо ответа понять сходу невозможно.

Проблема достаточно простая — shared_ptr нельзя модифицировать и читать из нескольких потоков одновременно. Контрольный блок дает thread-safe гарантии, тогда как сам shared_ptr — нет. Копирование shared_ptr состоит из трех операций:
— Скопировать указатель на объект
— Скопировать указатель на контрольный блок
— В контрольном блоке атомарно поднять refcount

Если во время чтения shared_ptr какие-то из этих полей будут обновлены, то мы можем поднять refcount не у того объекта, либо попытаться получить доступ к уничтоженному контрольному блоку. То что нельзя уничтожать объект shared_ptr во время его копирования достаточно очевидно, но то что его нельзя обновлять (за исключением манипуляций на refcount) — уже не так очевидно.

Мне известно о двух основных проблемах, которые можно решить с помощью появления shared_ptr, который можно обновлять во время чтения. Первая проблема — это возможность держать в памяти какой-то ресурс, который можно спокойно обновлять, и при этом из остальных потоков всегда иметь возможность иметь доступ к объекту. Сам объект будет удален ровно после окончания работы с ним последнего из потоков.

Вторая проблема — ABA. В lock-free алгоритмах постоянно используется операция CAS. Кажется логичным, что CAS операция проходит успешно, если объект не изменялся. Но на самом деле операция может успешно завершиться, если объект поменяли, а потом вернули ему обратно то же значение. Подробности на wiki. Проблема достаточно катастрофическая, она дико мешается всем c++ программистам. Java, например, выживает за счет своего garbage collector’а — в систему никогда не вернется блок памяти, который еще используется (не очень точно, но смысл такой).

В С++ проблемы с памятью решаются через shared_ptr, поэтому Herb Sutter предложил имплементировать специализацию std::atomic<std::shared_ptr> (proposal N4058). В своих выступлениях он об этом бодро рассказывал, пытаясь любой ценой не раскрывать детали реализации, просто говоря, что это возможно. lock-free shared_ptr действительно возможен, но только в libcxx-10.0.0 там стоит mutex, предположительно, потому что так быстрее. Тем временем, получается в честных lock-free алгоритмах std::atomic<std::shared_ptr> использовать нельзя.

Я бился об эту задачу порядка полугода (я бы оценил как 50+ часов дебага, 50+ часов имплементации и примерно 100+ часов разборок с теорией). Получилось найти 2 имплементации: одна использовала 128-bit атомарные операции, которые медленные, и не всегда поддерживаются. Вторая от facebook на основе хака с хранением указателя и счетчика в 64-bit одной переменной. В последней я толком не смог разобраться, осилил только комментарий про хак. Потом я решил, что хак — это норм, и начал писать свою версию.

На написание и отладку ушло какое-то адское время, но в итоге у меня есть AtomicSharedPtr, LFStack, LFQueue и LFMap. На последний ушло меньше всего времени, как ни странно. Там используется персистентное декартово дерево. Думал о красно-черном дереве, но в итоге не стал заморачиваться.

Что еще более интересно, я научился дебажить lock-free структуры данных, во время дебага у меня были очень большие проблемы до появления FastLogger. Я использую thread_local кольцевые буферы из событий. При креше тогда можно получить полноценную трассу из событий (скрины и сырые данные есть на гитхабе). До написания подобной системы логирования я был уверен, что писать логи для отладки lock-free невозможно. Один вызов FAST_LOG() стоит 30-50 тактов, что суммарно почти не влияет на общую производительность. Вызов обычной атомарной операции под моим стресс-тестом занимает 700-1500 тактов.

Проблемы в основном проявлялись незаметно, я успел полностью отладить стек, прежде чем узнать, что я потерял lock-free гарантии по дороге. Основную информацию приносили thread/memory/address санитайзеры. Вот когда начались логические проблемы с refcount, и начались креши в произвольных местах, пришлось серьезно повозиться.

Получилось неплохо, хотя мои структуры данных и не слишком быстрые. Но зато с помощью AtomicSharedPtr можно быстро писать уже заточенные варианты под конкретные требования.

Репозиторий с кучей дополнительного описания: https://github.com/vtyulb/AtomicSharedPtr/

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *