Проблема ABA: CAS видит то же значение, а мир уже другой

Если ты знаешь сценарий ABA на стеке Трайбера, почему её нет в языках со сборщиком мусора и как от неё защищают метка версии, LL/SC и hazard pointers, листай до «Теперь сам».

Как думаешь, пройдёт ли CAS

Стек A → B → C. Поток 0 начал «снять»: прочитал вершину t = A и её следующий n = B - и тут его сняли с процессора. Пока он спит, поток 1 снимает A, снимает B и кладёт D, а узел для D аллокатор выдаёт тот, что освободился первым, - бывший A. Поток 0 просыпается и делает cas(вершина, A, B). Пройдёт ли CAS? И что окажется в стеке?

Ответь себе до чтения. В вершине действительно лежит узел A - CAS пройдёт. Вершиной станет B, хотя B уже снят и лежит в пуле свободных, а D из стека пропадёт.

На что это похоже

Ты оставил кружку на столе в переговорной и вышел на минуту. Вернувшись, видишь на том же месте такую же кружку - и пьёшь. А за эту минуту коллега унёс твою, помыл, налил себе кофе и поставил на то же место: та же кружка, то же место, но содержимое и история другие. Проверка «кружка на месте» не говорит, трогали ли её.

Механизм: значение то же, ссылки другие

Поток 0 подготовил изменение по двум прочитанным значениям: t = A и n = B. CAS проверяет только первое. Пока вершина «та же», он считает верным и второе - что следующий за A по-прежнему B. При переиспользовании узла это неправда: узел A теперь хранит D, и его следующий - C. Успешный CAS записывает в вершину устаревший n.

Почему этого нет в Java или Go: сборщик мусора не освободит узел, на который ещё ссылается поток 0, - значит, и не выдаст его снова. ABA возвращается и там, если программа сама держит пул узлов ради скорости, - так Херлихи и Шавит показывают её на очереди с пулами на потоках. В C и C++ к ABA прибавляется худшее: поток 0 читает t.следующий у узла, который уже освобождён, - это обращение к чужой памяти.

Защиты.

• Метка версии. Вершина - пара [указатель, метка]; каждый успешный CAS увеличивает метку. Узел тот же, метка другая - CAS проваливается. Нужен CAS на двойное слово (cmpxchg16b на x86-64) или метка в неиспользуемых битах указателя; в Java - AtomicStampedReference. Метка может обойти круг: 64-битной для этого нужно больше операций, чем случится за жизнь программы, узкая обходит быстро (ниже).
• LL/SC. Пара «загрузить с пометкой» и «записать, если ячейку не трогали» (ARM ldxr/stxr, RISC-V lr/sc): запись проваливается после ЛЮБОЙ записи в ячейку, даже того же значения. ABA ей не страшна, но чтение t.следующий у уже освобождённого узла она не защищает - освобождение памяти нужно и тут.
• Безопасное освобождение. Не выдавать узел снова, пока его может читать другой поток. Hazard pointers (Магед Майкл, 2004): поток публикует «я сейчас работаю с узлом A» и перечитывает вершину: если там всё ещё A, узел защищён, иначе - заново. Защищённый A не освобождается, пока публикация есть. Эпохи и RCU: освобождение откладывается, пока все потоки не пройдут точку, где старых ссылок у них заведомо нет. В C++26 вошли std::hazard_pointer (P2530) и RCU (P2545).

Правило

CAS сравнивает значение, а не историю: ячейка, ставшая A → B → A, проходит проверку. На стеке Трайбера с переиспользованием узлов это ставит вершиной уже освобождённый узел. Защита - метка версии в CAS, LL/SC или безопасное освобождение памяти (hazard pointers, эпохи, RCU); в языках со сборщиком мусора узел, на который есть ссылка, не переиспользуется.

Разбор: перебор находит ABA

Модель стека Трайбера, где снятый узел уходит в пул, а «положить» берёт из пула самый давний. Вершина - пара [узел, метка]; с метками CAS сверяет обе части. Поток 0 снимает один раз, поток 1 - снимает дважды и кладёт D. Последовательно стек может закончиться только как ['D'] или ['C']. Обходим все достижимые состояния и ищем конечные, где стек другой. Проверяем только конечный стек: испорченная выдача при правильном стеке тоже была бы порчей, но для доказательства, что ABA ломает структуру, хватает одного испорченного конца.

# стек Трайбера с переиспользованием узлов: снятый узел уходит в пул,
# «положить» берёт из пула самый давний (или новый, если пул пуст).
# Вершина - [номер узла, метка]; с метками CAS сверяет и метку.

def nachalo(nachalnyj, programmy):
    uzly = []
    for i in range(len(nachalnyj)):
        sled = i + 1
        if i == len(nachalnyj) - 1:
            sled = -1
        uzly.append([nachalnyj[i], sled])
    k = len(programmy)
    return {"verh": [0, 0], "uzly": uzly, "pul": [], "pc": [0] * k,
            "op": [0] * k, "t": [[-1, 0]] * k, "n": [-1] * k,
            "x": [-1] * k, "vyshlo": []}

def kopiya(s):
    uzly = []
    for u in s["uzly"]:
        uzly.append(u[:])
    return {"verh": s["verh"][:], "uzly": uzly, "pul": s["pul"][:],
            "pc": s["pc"][:], "op": s["op"][:], "t": s["t"][:],
            "n": s["n"][:], "x": s["x"][:], "vyshlo": s["vyshlo"][:]}

def cas_verh(s, ozhidali, novyj, s_metkoj):
    v = s["verh"]
    if v[0] != ozhidali[0] or (s_metkoj and v[1] != ozhidali[1]):
        return False
    s["verh"] = [novyj, v[1] + 1]
    return True

def shag(s, p, programmy, s_metkoj):
    op = programmy[p][s["op"][p]]
    pc = s["pc"][p]
    if op == "pop":
        if pc == 0:                              # t = вершина
            s["t"][p] = s["verh"][:]
            s["pc"][p] = 1
        elif pc == 1:                            # n = t.next
            if s["t"][p][0] == -1:
                s["vyshlo"].append("пусто")
                s["op"][p] = s["op"][p] + 1
                s["pc"][p] = 0
            else:
                s["n"][p] = s["uzly"][s["t"][p][0]][1]
                s["pc"][p] = 2
        elif cas_verh(s, s["t"][p], s["n"][p], s_metkoj):
            u = s["t"][p][0]
            s["vyshlo"].append(s["uzly"][u][0])
            s["pul"].append(u)                   # узел - в пул
            s["op"][p] = s["op"][p] + 1
            s["pc"][p] = 0
        else:
            s["pc"][p] = 0
    else:
        if pc == 0:                              # взять узел из пула
            if len(s["pul"]) > 0:
                x = s["pul"].pop(0)
            else:
                s["uzly"].append(["", -1])
                x = len(s["uzly"]) - 1
            s["uzly"][x][0] = op
            s["x"][p] = x
            s["pc"][p] = 1
        elif pc == 1:                            # x.next = вершина
            s["t"][p] = s["verh"][:]
            s["uzly"][s["x"][p]][1] = s["t"][p][0]
            s["pc"][p] = 2
        elif cas_verh(s, s["t"][p], s["x"][p], s_metkoj):
            s["op"][p] = s["op"][p] + 1
            s["pc"][p] = 0
        else:
            s["pc"][p] = 1

def soderzhimoe(s):
    out = []
    v = s["verh"][0]
    while v != -1 and len(out) < 10:
        out.append(s["uzly"][v][0])
        v = s["uzly"][v][1]
    return out

def obojti(s, programmy, s_metkoj, put, vidennye, konechnye):
    # обход состояний: одинаковое состояние разными путями - один раз
    klyuch = str(s)
    if klyuch in vidennye:
        return
    vidennye[klyuch] = True
    hodit = []
    for p in range(len(programmy)):
        if s["op"][p] < len(programmy[p]):
            hodit.append(p)
    if len(hodit) == 0:
        konechnye.append([soderzhimoe(s), put])
        return
    for p in hodit:
        s2 = kopiya(s)
        shag(s2, p, programmy, s_metkoj)
        obojti(s2, programmy, s_metkoj, put + [p], vidennye, konechnye)

nachalnyj = ["A", "B", "C"]
programmy = [["pop"], ["pop", "pop", "D"]]
# по одной операции целиком: стек может закончиться так
vernye = [["D"], ["C"]]
for s_metkoj in [False, True]:
    vidennye = {}
    konechnye = []
    obojti(nachalo(nachalnyj, programmy), programmy, s_metkoj, [],
           vidennye, konechnye)
    plohie = []
    for st, put in konechnye:
        if st not in vernye:
            plohie.append([st, put])
    print("метки:", s_metkoj, "- состояний", len(vidennye),
          "конечных", len(konechnye), "испорченных", len(plohie))
    if len(plohie) > 0:
        put = plohie[0][1]
        print("  потоки по шагам:", put)
        s = nachalo(nachalnyj, programmy)
        for i in range(len(put)):
            shag(s, put[i], programmy, s_metkoj)
            if i == 1 or i == 10 or i == 11:
                print("  после шага", i + 1, "- стек", soderzhimoe(s),
                      "пул", s["pul"], "у потока 0: t =", s["t"][0][0],
                      "n =", s["n"][0])

метки: False - состояний 121 конечных 6 испорченных 1
  потоки по шагам: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
  после шага 2 - стек ['A', 'B', 'C'] пул [] у потока 0: t = 0 n = 1
  после шага 11 - стек ['D', 'C'] пул [1] у потока 0: t = 0 n = 1
  после шага 12 - стек ['B', 'C'] пул [1, 0] у потока 0: t = 0 n = 1
метки: True - состояний 119 конечных 4 испорченных 0

Перебор нашёл ровно сценарий из крючка. После двух шагов поток 0 запомнил t = 0 (узел A) и n = 1 (узел B). Девять шагов потока 1: снял A, снял B, положил D в узел 0 - стек D → C, в пуле узел 1. Шаг 12: CAS потока 0 видит в вершине узел 0 и записывает туда n = 1. Стек стал B → C - узел B одновременно в стеке и в пуле, D потерян, а поток 0 «снял» узел 0 со значением D и вернул его в пул второй раз.

Разбор: метка закрывает дыру

Та же модель с метками: 119 состояний, ни одного испорченного. В том же расписании CAS потока 0 сравнивает [0, 0] - узел 0 с меткой 0 - с вершиной [0, 3]: за время сна было три успешных CAS, метка ушла вперёд, CAS проваливается, поток 0 перечитывает вершину и снимает честно. Граница правила «метка решает ABA»: метка защищает CAS, но не чтение t.следующий. Если узел освобождён в систему, а не в пул, поток 0 читает освобождённую память ещё ДО своего CAS - от этого спасает только безопасное освобождение, метка тут бессильна.

Что ломается без этого

Пул узлов «для скорости». Неблокирующий стек на языке со сборщиком мусора работал годами, потом его ускорили пулом свободных узлов - и под нагрузкой элементы начали пропадать и дублироваться.

delete сразу после успешного «снять». В C++ другой поток в этот момент может читать t.следующий у того же узла - обращение к освобождённой памяти, падение или тихая порча.

Метка на 16 битов. 65 536 успешных CAS при миллионах операций в секунду - это сотые доли секунды; поток, проспавший столько, увидит ту же метку. Ширина метки - часть корректности.

Зачем это в работе

ABA - причина, по которой «просто CAS» почти никогда не пишут на C и C++ без схемы освобождения памяти. Ядро Linux держит RCU для структур, которые читают постоянно, а меняют редко; folly и libcds - hazard pointers; crossbeam в Rust - эпохи. Теперь те же средства в стандарте C++. Если тебе встретилась неблокирующая структура без объяснения, как она освобождает узлы, - первый вопрос к ней про ABA.

Теперь сам

1. Вершина [узел 5, метка 7], поток прочитал её и уснул. Пока он спал, другие сняли и снова положили узел 5 - всего 2 успешных CAS. Пройдёт ли CAS проснувшегося с меткой и без?
2. Почему в Java стек Трайбера без пула узлов не страдает от ABA?
3. Защищает ли метка от чтения освобождённой памяти?