Краткий ответ

Проблема ABA возникает, когда поток видит значение A, временно уступает выполнение, а затем обнаруживает снова A и ошибочно считает, что значение не менялось. Для compare-exchange это может привести к успешному обновлению указателя по устаревшему состоянию и повреждению структуры данных.

Обычно проблему устраняют версионированием значения, hazard pointers или схемами отложенного освобождения памяти. Одного выбора memory_order недостаточно: он упорядочивает доступы, но не сообщает операции CAS, что значение успело измениться и вернуться обратно.

Исторический контекст

Lock-free алгоритмы используют атомарные операции, прежде всего compare-and-exchange, чтобы изменять общую структуру без блокировки. Такой подход решает проблему блокировок: поток не удерживает мьютекс, а повторяет попытку при конфликте.

Однако CAS обычно сравнивает только текущее значение, а не историю его изменений. Поэтому последовательность A → B → A может выглядеть для CAS так же, как отсутствие изменений, что и породило отдельный класс ошибок ABA.

Постановка проблемы

Представим вершину lock-free стека, содержащую указатель на узел A. Поток T1 считывает A и готовит заменить вершину на следующий узел. До CAS поток T1 приостанавливается.

Поток T2 снимает A, освобождает его, а затем размещает новый узел по тому же адресу. Вершина снова содержит адрес A, но это уже другой объект или другое логическое состояние. Когда T1 продолжает работу, его CAS может успешно заменить вершину, хотя прочитанные им данные устарели.

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

Подробное решение

Классический способ — хранить вместе с указателем счётчик изменений. После каждого успешного изменения увеличивается версия, поэтому состояние представляется не просто как A, а как пара «адрес A, версия N». После последовательности A → B → A версия будет другой, и CAS обнаружит изменение.

#include <atomic>
#include <cstdint>

struct Node { Node* next; int value; };
struct Head { Node* ptr; std::uint64_t version; };
std::atomic<Head> top(Head{nullptr, 0});

bool try_pop(Node*& result) {
    Head old = top.load(std::memory_order_acquire);
    for (;;) {
        if (!old.ptr) return false;
        Head next{old.ptr->next, old.version + 1};
        if (top.compare_exchange_weak(old, next,
                std::memory_order_acq_rel,
                std::memory_order_acquire)) {
            result = old.ptr; return true;
        }
    }
}

В примере версия защищает от возврата к прежнему состоянию вершины. Это только иллюстрация обнаружения ABA: безопасное освобождение снятого узла требует отдельного механизма. Кроме того, широкое атомарное значение может быть реализовано не lock-free, а счётчик ограниченной разрядности теоретически может переполниться и снова создать совпадение.

Другой вариант — hazard pointers. Поток объявляет, какой узел собирается разыменовать, а освобождение узла откладывается, пока ни один поток не защищает его. Это хорошо решает проблему преждевременного освобождения, но требует инфраструктуры регистрации потоков и периодической очистки.

Схемы epoch-based reclamation и RCU-подобное отложенное освобождение также не позволяют переиспользовать память, пока потенциально работающие потоки не завершат критическую фазу. Они часто производительнее hazard pointers для подходящих нагрузок, но требуют контроля эпох и могут задерживать возврат памяти.

Порядки памяти нужно выбирать отдельно от защиты от ABA. acquire и release могут обеспечить видимость содержимого узлов, а acq_rel — нужное упорядочивание для операции обновления, но ни один порядок памяти сам по себе не различает два одинаковых значения указателя, появившихся в разное время.

Ситуация из практики

В высокопроизводительной очереди разработчики использовали стек с CAS над указателем вершины и сразу освобождали снятые узлы. На нагрузочном тесте редко возникала потеря элементов: поток иногда продолжал CAS после того, как другой поток снял и переиспользовал узел по тому же адресу.

Рассматривались три решения. Версионированный указатель быстро обнаруживал большинство повторных изменений, но требовал атомарного хранения указателя и счётчика, а переполнение счётчика нужно было учитывать. Hazard pointers давали строгую защиту разыменования, но добавляли публикацию защитных указателей и стоимость сканирования. Немедленное освобождение памяти было самым дешёвым вариантом, но оставалось некорректным.

Для структуры с редкими снятиями и ограниченным числом рабочих потоков выбрали hazard pointers, потому что безопасность освобождения была важнее минимальной задержки одной операции. Версионирование добавили как дополнительную защиту логического состояния, а результаты проверили стресс-тестами с санитайзерами и длительным повторением конкурентных сценариев.

Что кандидаты часто упускают

1. Достаточно ли добавить счётчик версии, чтобы полностью решить проблему ABA?

Нет. Счётчик должен изменяться атомарно вместе с указателем, а его переполнение может вернуть прежнюю пару значений. Кроме того, версия не заменяет безопасное управление временем жизни: поток всё ещё может разыменовать освобождённый узел до выполнения CAS. Поэтому версионирование часто сочетают с механизмом reclamation.

2. Может ли memory_order_seq_cst устранить ABA?

Нет. seq_cst задаёт более строгий порядок наблюдения атомарных операций, но CAS по-прежнему сравнивает текущее значение с ожидаемым. Если значение прошло через B и вернулось к A, для сравнения оно снова равно A. Проблема требует изменения представления состояния или запрета опасного переиспользования памяти, а не только усиления порядка памяти.

3. Чем ABA отличается от ложного пробуждения compare_exchange_weak?

compare_exchange_weak может вернуть неуспех без изменения ожидаемого значения, поэтому его обычно помещают в цикл повторных попыток. ABA — это другой сценарий: CAS может вернуть успех, поскольку значение действительно совпало с ожидаемым, но между чтением и сравнением оно уже менялось и вернулось обратно. Цикл устраняет ложный отказ weak-CAS, но не устраняет успешный CAS на устаревшем состоянии.