Hazard Pointer 분석 — Lock-Free Memory Reclamation

1
#include <atomic>
2
#include <thread>
3
#include <vector>
4

5
static thread_local std::atomic<void *> my_hp{nullptr};
6

7
template <typename T>
8
T *acquire(std::atomic<T *> *src) {
9
    T *p;
10
    do {
11
        p = src->load(std::memory_order_acquire);
12
        my_hp.store(p, std::memory_order_release);
13
    } while (src->load(std::memory_order_acquire) != p);   /* 재확인 */
14
    return p;
15
}
16

17
void release(void) {
18
    my_hp.store(nullptr, std::memory_order_release);
19
}

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

4
int reader(void) {
5
    node *n = acquire(&head);
6
    if (!n) { release(); return 0; }
7
    int v = n->val;
8
    release();
9
    return v;
10
}

1
std::vector<node *> retired;
2

3
void retire(node *n) {
4
    retired.push_back(n);
5
    if (retired.size() >= 64) scan();
6
}
7

8
void scan(void) {
9
    /* 모든 thread의 hazard pointer 수집 */
10
    std::vector<void *> hps;
11
    for (auto *thread_hp : all_hps())
12
        if (auto *p = thread_hp->load()) hps.push_back(p);
13

14
    std::sort(hps.begin(), hps.end());
15

16
    std::vector<node *> still_retired;
17
    for (auto *n : retired) {
18
        if (std::binary_search(hps.begin(), hps.end(), n))
19
            still_retired.push_back(n);     /* 누군가 보고 있음 */
20
        else
21
            delete n;                        /* 안전하게 free */
22
    }
23
    retired = std::move(still_retired);
24
}

1
static thread_local std::array<std::atomic<void *>, 4> my_hps;
2

3
template <typename T>
4
T *acquire_at(std::atomic<T *> *src, int slot) {
5
    T *p;
6
    do {
7
        p = src->load();
8
        my_hps[slot].store(p);
9
    } while (src->load() != p);
10
    return p;
11
}

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

4
void push(int v) {
5
    snode *n = new snode{nullptr, v};
6
    snode *old;
7
    do {
8
        old = top.load();
9
        n->next = old;
10
    } while (!top.compare_exchange_weak(old, n));
11
}
12

13
int pop(void) {
14
    snode *old;
15
    int v = 0;
16
    while (true) {
17
        old = acquire(&top);
18
        if (!old) { release(); return 0; }
19
        if (top.compare_exchange_weak(old, old->next)) {
20
            v = old->val;
21
            release();
22
            retire(old);    /* 즉시 delete X */
23
            return v;
24
        }
25
        release();
26
    }
27
}

1
#include <hazard_pointer>     /* C++26 (proposal) */
2

3
std::hazard_pointer hp;
4
node *p = hp.protect(head);
5
process(p);
6
hp.reset_protection();
7

8
/* writer */
9
old->retire();    /* 자동 retired list 관리 */

1
패턴                    reader latency      throughput (8 thread)
2
spinlock-protected list 200 ns              100 K ops/s
3
RCU                     10 ns               5 M ops/s
4
hazard pointer          25 ns               4 M ops/s

1
메모리 bound
2
RCU                     grace period 비례 (수 ms 동안 retired 쌓임)
3
hazard pointer          ~thread 수 × retired threshold (bounded)

1
p = src->load();
2
my_hp.store(p);
3
/* 재확인 안 함 — writer가 동시에 retire 가능 */
4
return p;

1
/* main thread만 hp 슬롯 있음 — 새 thread는 없음 */
2
std::thread t([](){ acquire(...); });   /* hp 슬롯 없음 */

1
release();
2
retire(n);
3
my_hp.store(n);    /* 이미 retired된 n을 다시 보호 — UB */

1
retire(n);
2
scan();    /* 매 retire마다 scan — 매우 비쌈 */

1
/* hazard pointer만으로 ABA 해결되지 않음 */