ABA 문제 회피 — Tagged Pointer·Hazard·Generation Counter

1
struct node { node *next; int v; };
2
std::atomic<node *> top;
3

4
int pop_naive(void) {
5
    node *cur;
6
    do {
7
        cur = top.load();
8
        if (!cur) return -1;
9
        /* 이 순간 다른 thread가 cur 제거, free, 재할당 가능 */
10
    } while (!top.compare_exchange_weak(cur, cur->next));
11
    int v = cur->v;
12
    delete cur;
13
    return v;
14
}

1
struct tagged_node {
2
    node *ptr;
3
    uint64_t tag;
4
};
5

6
std::atomic<tagged_node> top;    /* sizeof == 16, 128-bit CAS 필요 */
7

8
int pop_tagged(void) {
9
    tagged_node cur, neu;
10
    do {
11
        cur = top.load();
12
        if (!cur.ptr) return -1;
13
        neu = { cur.ptr->next, cur.tag + 1 };
14
    } while (!top.compare_exchange_weak(cur, neu));
15
    int v = cur.ptr->v;
16
    delete cur.ptr;
17
    return v;
18
}

1
/* ARM64/x86-64는 보통 상위 16-bit가 사용 가능 */
2
inline uintptr_t pack(node *p, uint16_t tag) {
3
    return (uintptr_t)p | ((uintptr_t)tag << 48);
4
}
5

6
inline node *unpack_ptr(uintptr_t v) {
7
    return (node *)(v & 0x0000FFFFFFFFFFFFull);
8
}
9

10
inline uint16_t unpack_tag(uintptr_t v) {
11
    return (uint16_t)(v >> 48);
12
}
13

14
std::atomic<uintptr_t> top;
15

16
int pop_packed(void) {
17
    uintptr_t cur, neu;
18
    node *p;
19
    do {
20
        cur = top.load();
21
        p = unpack_ptr(cur);
22
        if (!p) return -1;
23
        neu = pack(p->next, unpack_tag(cur) + 1);
24
    } while (!top.compare_exchange_weak(cur, neu));
25
    int v = p->v;
26
    delete p;
27
    return v;
28
}

1
std::atomic<node *> top;
2
std::atomic<uint64_t> version;
3

4
int pop_versioned(void) {
5
    node *cur, *next;
6
    uint64_t ver;
7
    do {
8
        ver = version.load();
9
        cur = top.load();
10
        if (!cur) return -1;
11
        next = cur->next;
12
    } while (!top.compare_exchange_weak(cur, next) ||
13
             version.fetch_add(1) != ver);
14
    /* 별도 atomic 두 개 — 일관성이 깨짐 — 비추천 */
15
}

1
int pop_hp(void) {
2
    node *cur;
3
    while (true) {
4
        cur = top.load();
5
        if (!cur) return -1;
6
        my_hp.store(cur);                    /* publish */
7
        if (top.load() != cur) continue;    /* re-validate */
8
        if (top.compare_exchange_weak(cur, cur->next)) {
9
            int v = cur->v;
10
            my_hp.store(nullptr);
11
            retire(cur);                     /* 즉시 free 안 함 */
12
            return v;
13
        }
14
    }
15
}

1
rcu_read_lock();
2
list_for_each_entry_rcu(e, &head, list) {
3
    process(e);
4
}
5
rcu_read_unlock();
6

7
/* writer */
8
list_del_rcu(&e->list);
9
call_rcu(&e->rcu, free_entry);    /* grace period 후 free */

1
원본 paper Michael & Scott (1996)
2
  CAS 두 번으로 enqueue/dequeue
3
  ABA 회피를 위해 tagged pointer 필수
4
  C++ 구현은 보통 atomic<__int128> 사용

1
ABA 발생률 (8 thread stack, 1M op)
2
대처 없음                   매 100K op 중 ~수십 회 corruption
3
16-bit tag (packed)         양산 환경에서 거의 0 (wraparound risk)
4
64-bit tag (DCAS)           0
5
hazard pointer              0 (memory 약간 증가)
6
RCU                         0 (memory 더 증가)

1
연산 비용
2
naive CAS                   1 CAS
3
tagged CAS (16-bit packed)  1 CAS (같은 비용)
4
tagged CAS (128-bit DCAS)   1 CMPXCHG16B (1.5x cycle)
5
hazard pointer              1 atomic store + 1 load + 1 CAS (3x)
6
RCU                         거의 0 (reader)

1
/* 매우 빠른 cycle에서 65536 update면 wraparound */

1
tag++;
2
if (cur.tag == old.tag) { ... }    /* tag만 비교 — 의미 없음 */

1
/* MTE/PAC 환경에서는 상위 비트가 다른 의미로 사용됨 */

1
my_hp.store(cur);
2
/* 재확인 없이 사용 — race */

1
ptr.compare_exchange(...);
2
version.fetch_add(1);    /* 두 atomic — 일관성 깨짐 */