Hazard pointers

Hazard pointers (англ. «указатели опасности») — это механизм управления памятью, используемый в многопоточном программировании для безопасного освобождения объектов, на которые могут ссылаться другие потоки. Hazard pointers относятся к классу безблокировочных (lock-free) алгоритмов и применяются в системах с интенсивным конкурентным доступом к данным, где традиционные блокировки (мьютексы) приводят к снижению производительности или рискам взаимоблокировок.

История

Концепция hazard pointers была предложена в 2002 году исследователем Миклошем Варга (Miklos Varga) в работе «Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects». Позднее, в 2004 году, алгоритм был формализован и популяризирован Андреем Александреску (Andrei Alexandrescu) и Миклошем Варга в статье «Lock-Free Data Structures with Hazard Pointers» в журнале «Dr. Dobb’s Journal». В 2000-х годах метод получил широкое распространение в библиотеках и фреймворках, таких как Intel Threading Building Blocks (TBB), Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) Folly, а также в реализации стандартной библиотеки C++ (libstdc++). К началу 2020-х годов hazard pointers остаются одним из основных механизмов безопасного освобождения памяти в безблокировочных структурах данных, хотя в отдельных случаях вытесняются более современными подходами, например, epoch-based reclamation (EBR).

Принцип работы

Hazard pointers решают проблему «опасных указателей» (hazardous pointers), когда один поток может удалить объект, на который в данный момент ссылается другой поток. В безблокировочных алгоритмах потоки не ждут друг друга, поэтому необходимо гарантировать, что объект не будет освобождён, пока хотя бы один поток держит на него ссылку.

Основные элементы

• Hazard pointer (HP) — переменная, доступная для чтения всем потокам, в которую поток записывает адрес объекта, к которому он обращается. Каждый поток имеет фиксированный набор HP (обычно от 1 до 4).
• Глобальный список hazard pointers — массив или список, содержащий все HP всех потоков. Доступен для чтения любым потоком.
• Retire list — локальный или глобальный список объектов, помеченных для удаления, но ещё не освобождённых.
• Атомарные операции — все операции записи и чтения HP, а также обновления указателей на объекты, выполняются атомарно (например, с помощью std::atomic в C++).

Алгоритм

1. Захват hazard pointer: Поток, собирающийся прочитать или изменить объект, записывает его адрес в свой HP с помощью атомарной операции.
2. Проверка актуальности: После записи HP поток повторно проверяет, что объект ещё не был удалён (например, сравнивает указатель на объект с ожидаемым значением). Если объект удалён, поток перезапускает операцию.
3. Освобождение объекта: Когда поток решает удалить объект (например, после вытеснения из очереди), он помещает его в свой retire list. Периодически поток проверяет, можно ли безопасно освободить объекты из retire list: для каждого объекта он сканирует все HP всех потоков. Если ни один HP не указывает на данный объект, объект освобождается (вызывается delete или аналогичная функция).
4. Снятие hazard pointer: После завершения работы с объектом поток обнуляет свой HP (записывает nullptr).

Пример на C++ (упрощённый)

```cpp

include <atomic>

include <array>

struct Node { int value; Node* next; };

class HazardPointer { public: void protect(Node ptr) { hp_.store(ptr, std::memory_order_release); } void unprotect() { hp_.store(nullptr, std::memory_order_relaxed); } Node get() const { return hp_.load(std::memory_order_acquire); } private: std::atomic<Node*> hp_{nullptr}; };

// Глобальный массив HP для каждого потока thread_local std::array<HazardPointer, 2> hazard_pointers;

// Функция проверки, можно ли удалить объект bool is_safe_to_delete(Node* node) { for (auto& hp : hazard_pointers) { if (hp.get() == node) return false; } return true; } ```

Классификация

Hazard pointers относятся к категории безблокировочных механизмов управления памятью (lock-free memory reclamation). В этой категории выделяют несколько подходов:

• Hazard pointers — основаны на явной регистрации адресов.
• Epoch-based reclamation (EBR) — использует эпохи (глобальные счётчики) для отслеживания активных потоков.
• Reference counting — подсчёт ссылок, но требует атомарных операций и может быть дорогим.
• Drop-in replacement — методы, встраиваемые в существующие структуры данных (например, RCU в Linux).

Hazard pointers отличаются от EBR тем, что не требуют глобальных барьеров памяти и могут быть реализованы с меньшими накладными расходами на запись, но требуют большего объёма памяти для хранения HP.

Применение

Hazard pointers используются в безблокировочных структурах данных, таких как:

• Очереди (queues) — безблокировочные очереди Майкла-Скотта (Michael-Scott queue) и её варианты.
• Стеки (stacks) — безблокировочные стеки Тре́бера (Treiber stack).
• Односвязные списки (linked lists) — безблокировочные списки с операциями вставки и удаления.
• Хеш-таблицы (hash tables) — безблокировочные хеш-таблицы, например, в библиотеке Intel TBB.
• Счётчики и счётчики ссылок — в системах с интенсивным конкурентным доступом.

В промышленности hazard pointers применяются в:

• C++ стандартная библиотека — в реализации std::shared_ptr (через std::atomic и внутренние механизмы).
• Facebook Folly — библиотека folly::HazardPointer.
• Intel Threading Building Blocks (TBB) — используется в контейнерах tbb::concurrent_queue и tbb::concurrent_hash_map.
• Ядро Linux — в некоторых безблокировочных структурах (например, в реализации RCU для пользовательского пространства).

Преимущества и недостатки

Преимущества

• Безблокировочность — потоки не блокируют друг друга, что повышает производительность на многоядерных системах.
• Низкие накладные расходы на запись — запись hazard pointer — это одна атомарная операция.
• Простота реализации — алгоритм не требует сложных барьеров памяти (кроме атомарных операций).
• Предсказуемость — время освобождения памяти ограничено (обычно не более нескольких циклов проверки).

Недостатки

• Дополнительная память — каждый поток резервирует несколько hazard pointers, что может быть проблемой при большом количестве потоков (тысячи).
• Задержка освобождения — объекты могут оставаться неосвобождёнными, пока какой-либо поток держит на них указатель. В худшем случае это может привести к исчерпанию памяти.
• Сложность отладки — ошибки в управлении hazard pointers (например, забытая защита) могут привести к повреждению данных или утечкам памяти.
• Не подходит для всех структур — hazard pointers эффективны только для структур с фиксированным числом одновременно используемых указателей (например, для очередей и стеков, но не для деревьев с большим количеством ссылок).

Критика и альтернативы

Критики hazard pointers отмечают, что алгоритм требует от разработчика явного управления защитой указателей, что увеличивает риск ошибок. Кроме того, при большом числе потоков (например, более 100) накладные расходы на сканирование глобального списка HP становятся значительными. В таких случаях предпочтительнее использовать epoch-based reclamation (EBR) или hybrid approaches, сочетающие оба метода.

Альтернативные механизмы:

• Epoch-based reclamation (EBR) — использует глобальные эпохи и локальные счётчики, что снижает накладные расходы на сканирование.
• Reference counting with lock-free — атомарный подсчёт ссылок, но требует дорогих операций fetch_add.
• RCU (Read-Copy-Update) — механизм, широко применяемый в ядре Linux, но требующий поддержки со стороны операционной системы.
• Drop-in replacement — например, std::shared_ptr с атомарным подсчётом ссылок, но с дополнительными накладными расходами.

Интересные факты

• Термин «hazard pointer» происходит от английского «hazard» — опасность, риск. В ранних работах использовался термин «dangerous pointer».
• В 2015 году стандарт C++17 ввёл поддержку hazard pointers в виде экспериментального API в библиотеке <experimental/hazard_pointer>.
• Алгоритм hazard pointers лежит в основе реализации безблокировочной очереди Майкла-Скотта, которая используется в некоторых высоконагруженных системах, например, в Apache Kafka (внутренние очереди сообщений).
• В 2020 году исследователи из Microsoft предложили улучшенную версию hazard pointers — «Hazard Eras» — которая снижает задержки освобождения памяти за счёт комбинирования с EBR.

Источники

• Varga, M. (2002). «Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects». Technical Report.
• Alexandrescu, A.; Varga, M. (2004). «Lock-Free Data Structures with Hazard Pointers». Dr. Dobb’s Journal.
• Herlihy, M.; Shavit, N. (2008). «The Art of Multiprocessor Programming». Morgan Kaufmann.
• McKenney, P. E. (2010). «Is Parallel Programming Hard, And, If So, What Can You Do About It?». Kernel.org.
• C++ Standard Committee. (2017). «Working Draft, Standard for Programming Language C++» (N4659). Раздел «Hazard Pointers».
• Facebook Folly Documentation. (2023). «folly::HazardPointer». GitHub.
• Intel Corporation. (2020). «Intel Threading Building Blocks Developer Guide». Раздел «Concurrent Containers».