ABA проблема Допустим у нас есть lock-free стек на go и мы вызываем метод pop func (s Stack) Pop() (interface{}, bool) { for { oldHead := (Node)(atomic.LoadPointer(&s.head)) if oldHead == nil { return nil, false } if atomic.CompareAndSwapPointer(&s.head, unsafe.Pointer(oldHead), oldHead.next) { return oldHead.value, true } // retry } } В момент времени 1 поток A (выполняющий Pop()) читает текущее значение головы стека: head = X. Он запоминает этот указатель и готовится выполнить атомарное обновление - заменить head на X.next. Но пока поток A готовится к CAS, в работает поток B В момент времени 2 поток B тоже вызывает Pop() — и успешно удаляет узел X из стека. Теперь X больше не в структуре. Далее поток B возвращает этот узел обратно в пул памяти — например, в sync.Pool. В этот момент объект по адресу X считается свободным: он больше не участвует в логике стека, и GC (если не держат другие ссылки) может его забыть В момент времени 3 поток B решает вставить новый элемент - Push(Y). Он запрашивает новый узел из того же пула. И вот ключевой момент: аллокатор, стремясь снизить число аллокаций, выдаёт ему тот же самый адрес X. Теперь по адресу X лежит совершенно другой объект: value = Y, next = Z, и вообще все изменилось. Но физически - это всё ещё X В момент времени 4 поток A, ничего не подозревая, выполняет свой CAS: CompareAndSwapPointer(&head, X, X.next) Адрес head действительно снова равен X - потому что поток B только что туда вставил новый узел -> CAS проходит успешно Но что происходит дальше? Поток A возвращает oldHead.value - то есть значение из узла, который он считал исходным X. На самом деле - это Y. Формулировка - состояние прошло путь A -> B -> A, и атомарная операция, проверяющая только значение указателя, не в состоянии отличить оригинал от подмены Решение ABA Tagged pointers (указатели с тегом) Идея: расширить указатель дополнительным счётчиком (tag) - например, 48 бит под адрес + 16 бит под версию. При каждом изменении объекта (удалении/вставке) тег инкрементируется CAS теперь проверяет не только адрес, но и тег: даже если адрес X вернулся - тег будет N+1, и CAS провалится Hazard pointers (опасные указатели) Идея: поток публикует указатель на объект, с которым он работает - это опасный указатель, использующтй:«не удаляйте/не переиспользуйте этот адрес - я ещё читаю. Освобождение объектов откладывается до тех пор, пока никто не держит его в hazard-списке -> объект не может быть переиспользован, пока кто-то на него ссылается -> ABA невозможна В коментариях оставил пдф интересной книжки на эту тему