ABA問題とハザードポインタ（ロックフリーのメモリ回収）

なぜロックフリーの「解放」が難しいのか

ロックフリー構造の本当の難所は、ノードの更新ではなく解放にあります。ミューテックスなら「ロック区間で誰も触っていない」が保証されるため、その場でfreeできます。ロックを外した世界には、その保証がありません。あるスレッドが共有ノードへのポインタを読んで握ったまま中断し、その隙に別スレッドが同じノードをデータ構造から外して解放したら——握っていたポインタは**ダングリング（宙ぶらりん）**になり、読み出した瞬間に use-after-free です。

# スレッドR（読み手）            # スレッドW（解放側）
p = atomic_load(head)
                                 unlink(p); free(p)   # p を構造から外し解放
v = p->value                     # ← use-after-free。p は既に解放済み

問題の核心は「いま誰がそのノードを指しているかを、ロックなしでどう知るか」です。CASでポインタを付け替える話はロックフリー・ウェイトフリーとCAS命令で扱いましたが、付け替えに成功しても外したノードをいつ捨てられるかは別問題として残ります。GCのある言語は「到達不能になれば回収」でこれを肩代わりしますが、C/C++/Rust のように手動回収する環境では、専用の**安全メモリ回収（SMR: Safe Memory Reclamation）**機構が要ります。

ABA問題は回収問題の一側面

回収を誤ると、CASが論理的に壊れた状態を「成功」と誤認します。これがABA問題です。値が A → B → A と変化して戻ると、CASは「変わっていない」と判断しますが、実際にはその間に A が解放され、アロケータが同じアドレスを別の意味のノードに再利用しているかもしれません。

top = A
next = A->next           # この時点の next は B
# ← 中断。その間に pop A, pop B が起き、A のアドレスが新ノードに再利用される
CAS(stack.top, A, next)  # アドレスとしては A に一致 → 誤って成功
                         # だが next(=旧B) は解放済み。先頭が壊れる

ハザードポインタ：参照を公示してから触る

ハザードポインタ（Maged Michael, 2004）は「触る前に宣言する」方式です。各スレッドは、参照しようとするノードのアドレスを、自分専用のスロット（グローバルに読める単一ワード）へ書き込んでから、改めてそのポインタが有効かを確認します。

# 読み手：head のノードを安全に掴む
do:
  p = atomic_load(head)
  hazard[myID] = p          # 公示（release ストア）
while atomic_load(head) != p  # 公示後にもう一度検証（再読込）
# ここまで来れば、p は解放されない（公示済みのため）
use(p)
hazard[myID] = null         # 使い終わったら取り下げ

公示後の再検証が肝です。公示する前に他スレッドが p を外して回収判定を済ませてしまう競合を、「公示してからもう一度読み直し、まだ head==p なら安全」と確定させて閉じます。解放側は即freeせず、退役ノードをローカルのretireリストへ溜め、しきい値に達したら全スレッドのhazardスロットを走査します。

# 解放側：p を退役させる
retire(p)                       # ローカルリストに積む
if retired.size >= threshold:
  H = collect_all_hazard_slots()   # 全スレッドの公示を集める
  for n in retired:
    if n not in H: free(n)         # 誰も公示していなければ解放
    else: keep(n)                  # 公示中なら次回へ持ち越し

公示の正しさはメモリモデルとhappens-before関係に依存します。公示は release、走査側の読み取りは acquire でなければ、走査側が古い null を見て解放してしまいます。

エポックベース回収とRCU：読み手をほぼ無料にする

ハザードポインタは読み手にストアと再検証を課します。これすら惜しいホットパス向けに、**エポックベース回収（EBR）とRCU（Read-Copy-Update）**があります。発想は「読み手は何も公示しない。代わりに、いま走っている読み手が全員クリティカルセクションを抜けるまで、解放を一括で遅らせる」です。

EBRはグローバルなエポック番号（世代）を持ちます。読み手はクリティカルセクション入場時に「自分は現エポックで読んでいる」と印を付け、退場時に外すだけです。退役ノードはエポック単位のバケツに入れ、**全スレッドが現エポックに追いついた（=古いエポックの読み手が消えた）**ことを確認できたら、2世代前のバケツをまとめて解放します。RCUはLinuxカーネルの中核機構で、同じ原理を「猶予期間（grace period）——全CPUが少なくとも一度クリティカルセクション外になる期間——が経過したら回収」として実装します。

# RCU 読み手（極めて軽量。多くの実装で実質ノーオペ）
rcu_read_lock()
p = rcu_dereference(head)   # 依存順序つきロード
use(p)
rcu_read_unlock()

# RCU 更新側
new = copy_and_modify(old)
rcu_assign_pointer(head, new)  # release ストアで公開
synchronize_rcu()              # 猶予期間を待つ（全読み手の抜けを待機）
free(old)                      # ここで初めて安全に解放

三方式の比較と使い分け

選択の軸は明快です。メモリ滞留の上限を保証したい・読み手が長く居座り得るならハザードポインタ。読み手が極短命で性能を最優先し、滞留リスクを許容できるならEBR/RCU。参照カウントを各ノードに持たせる手もありますが、共有カウンタへのアトミック更新がキャッシュラインを奪い合い、高競合では失速します（参照カウントの仕組みと循環参照）。SMRはこの「カウンタ集中」を避け、回収判定を読み取りと分離する点に価値があります。

まとめ

ロックフリー構造の本丸は、CASによる更新ではなく安全なメモリ回収です。あるスレッドがノードを握る間は解放してはならず、その「握り」をロックなしで知る手段が安全回収機構です。ハザードポインタは参照を公示し再検証することで滞留を有界に抑え、居座りスレッドに強い。EBR・RCUは読み手をほぼ無料にする代わりに、猶予期間が延びると滞留が無界に膨らむ。両者は「読み手の軽さ」と「滞留の有界性」を交換し合う対照的な設計です。ABA問題はこの回収問題の一断面に過ぎず、タグ付きCASでCASの誤成功を塞いでも、解放時点の決定は別途これらの機構で詰める必要があります。並行設計の全体像はロックフリー・ウェイトフリーとCAS命令と並行性モデル（CSP・アクター・STM）と合わせて押さえると、どこまで踏み込むべきかの判断がつきます。