《Java 并发编程·JUC 源码与容器》10.2 ABA 与内存回收

static final class AbaStack {
    volatile Node top;

    Node snapshot() { return top; }                    // 读快照

    boolean commit(Node expected, Node update) {       // 按旧快照提交
        return TOP.compareAndSet(this, expected, update);
    }

    int pop() {                                        // 正常的一次性 pop
        for (;;) {
            Node t = top;
            if (t == null) return Integer.MIN_VALUE;
            if (TOP.compareAndSet(this, t, t.next)) return t.value;
        }
    }

    void pushNode(Node n) {                            // 压入指定节点（可复用）
        for (;;) {
            Node t = top;
            NEXT.set(n, t);
            if (TOP.compareAndSet(this, t, n)) return;
        }
    }
}

AbaStack s = new AbaStack();
Node n3 = new Node(3, null), n2 = new Node(2, n3), n1 = new Node(1, n2);
s.pushNode(n3); s.pushNode(n2); s.pushNode(n1);   // [1 -> 2 -> 3]

Node observed = s.snapshot();
Node observedNext = observed.next;                 // 记下 N1 -> N2

s.pop();                                           // T2: 弹出 1
s.pop();                                           // T2: 弹出 2
s.pushNode(n1);                                    // T2: 把 N1 原对象压回

boolean ok = s.commit(observed, observedNext);     // T1 提交旧快照

## A. 朴素 Treiber 栈
初始栈            [1 -> 2 -> 3]
T1 读到 top=N1 next=N2（准备 CAS 成 N2）
T2 pop()=1        [2 -> 3]
T2 pop()=2        [3]
T2 push(N1) 复用原节点  [1 -> 3]
T1 commit(N1->N2)=true  [2 -> 3]
T1 pop()=1（它交付的 N1）
最终栈 [2 -> 3]，交付序列 [1, 2, 1]
证据 1：T2 刚压入的 N1 被 T1 的 CAS 覆盖，这次 push 丢失
证据 2：N2 在第二次 pop 时已交付，现在又回到栈顶，会被再交付一次
账本：push 4 次，交付 3 次，栈内应剩 1 个，实际剩 2 个

// JDK 25 源码摘录，已删减
public class AtomicStampedReference<V> {

    private static class Pair<T> {
        final T reference;
        final int stamp;
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
            return new Pair<T>(reference, stamp);
        }
    }

    private volatile Pair<V> pair;

    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

    private static final VarHandle PAIR = MhUtil.findVarHandle(
            MethodHandles.lookup(), "pair", Pair.class);

    private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return PAIR.compareAndSet(this, cmp, val);
    }
}

public class java.util.concurrent.atomic.AtomicStampedReference<V> {
  private volatile java.util.concurrent.atomic.AtomicStampedReference$Pair<V> pair;
  private static final java.lang.invoke.VarHandle PAIR;
  public boolean compareAndSet(V, V, int, int);
  public boolean attemptStamp(V, int);
  private boolean casPair(java.util.concurrent.atomic.AtomicStampedReference$Pair<V>,
                          java.util.concurrent.atomic.AtomicStampedReference$Pair<V>);
}

static final class StampedStack {
    record Snapshot(Node ref, int stamp) {}

    private final AtomicStampedReference<Node> pair = new AtomicStampedReference<>(null, 0);

    Snapshot snapshot() {
        int[] stamp = new int[1];
        Node ref = pair.get(stamp);
        return new Snapshot(ref, stamp[0]);
    }

    boolean commit(Snapshot snap, Node update) {
        return pair.compareAndSet(snap.ref(), update, snap.stamp(), snap.stamp() + 1);
    }
}

## B. 带版本戳的栈
初始栈            [1 -> 2 -> 3] stamp=3
T1 读到 top=N1 stamp=3
T2 pop()=1        [2 -> 3] stamp=4
T2 pop()=2        [3] stamp=5
T2 push(N1) 复用原节点  [1 -> 3] stamp=6
T1 commit(旧戳)=false → 重新读栈
T1 重读 top=N1 stamp=6 再 commit=true  [3]
最终栈 [3]，交付序列 [1, 2, 1]
账本：push 4 次，交付 3 次，栈内剩 1 个，合计 4，账对上

// JDK 25 源码摘录，已删减
public boolean compareAndSet(V       expectedReference,
                             V       newReference,
                             boolean expectedMark,
                             boolean newMark) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedMark == current.mark &&
        ((newReference == current.reference &&
          newMark == current.mark) ||
         casPair(current, Pair.of(newReference, newMark)));
}

package com.plume.conc.core;

import java.util.concurrent.atomic.AtomicStampedReference;

/** 库存快照的发布点：版本号必须和引用一起原子更新。 */
public final class StockPublisher {
    public record Snapshot(String isbn, int stock) {}

    private final AtomicStampedReference<Snapshot> current =
            new AtomicStampedReference<>(null, 0);

    /** 试算：读当前快照和版本。 */
    public Snapshot read(int[] stampHolder) {
        return current.get(stampHolder);
    }

    /**
     * 提交：只有当当前快照仍是我读到的那个版本时才写入。
     * 返回 false 表示期间有人改过，调用方必须重读重算。
     */
    public boolean publish(Snapshot expected, int expectedStamp, Snapshot next) {
        return current.compareAndSet(expected, next, expectedStamp, expectedStamp + 1);
    }

    public int stamp() {
        return current.getStamp();
    }
}