Hazard Pointers：安全内存回收的优雅方案

typedef struct node {
    void *data;
    struct node *next;
} node_t;

typedef struct queue {
    node_t *head;  // 哨兵节点
    node_t *tail;
} queue_t;

void *dequeue(queue_t *q) {
    node_t *head, *tail, *next;
    void *data;

    while (1) {
        head = q->head;                          // 1. 读 head
        tail = q->tail;                          // 2. 读 tail
        next = head->next;                       // 3. 读 head->next  <-- 危险！

        if (head != q->head)                     // 4. 一致性检查
            continue;

        if (head == tail) {
            if (next == NULL)
                return NULL;                     // 队列为空
            CAS(&q->tail, tail, next);           // 帮助推进 tail
            continue;
        }

        data = next->data;                       // 5. 读数据       <-- 危险！
        if (CAS(&q->head, head, next))           // 6. 推进 head
            break;
    }

    // head 现在是旧的哨兵节点，可以"释放"
    // 但是，其他线程可能还在步骤 1-5 中持有 head 的引用！
    free(head);  // <-- 这行代码是不安全的
    return data;
}

void retire(hp_domain_t *domain, void *ptr) {
    // 加入本线程的退役列表
    add_to_retired_list(ptr);

    // 如果退役列表超过阈值，触发扫描
    if (retired_count >= SCAN_THRESHOLD)
        scan(domain);
}

// 安全地读取一个共享指针
node_t *protect(atomic_ptr *source, hazard_pointer_t *hp) {
    node_t *ptr;
    do {
        ptr = atomic_load(source);            // 1. 读取共享指针
        atomic_store(hp, ptr);                // 2. 发布到 HP 槽
        // 需要 StoreLoad barrier
        atomic_thread_fence(memory_order_seq_cst);
    } while (ptr != atomic_load(source));     // 3. 验证指针未变
    return ptr;
}

/* hazard_pointer.h */
#ifndef HAZARD_POINTER_H
#define HAZARD_POINTER_H

#include <stdatomic.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

/* ========== 配置常量 ========== */

#define HP_MAX_THREADS    64
#define HP_MAX_HPS        2       /* 每个线程的 hazard pointer 数量 */
#define HP_SCAN_THRESHOLD 32      /* retired list 阈值 */

/* ========== 数据结构 ========== */

/* 退役节点链表 */
typedef struct hp_retired_node {
    void *ptr;
    void (*deleter)(void *);
    struct hp_retired_node *next;
} hp_retired_node_t;

/* 每线程记录 */
typedef struct hp_thread_record {
    _Atomic(void *) hp[HP_MAX_HPS];       /* hazard pointer 槽位 */
    _Atomic(bool)   active;               /* 是否被某线程持有 */
    hp_retired_node_t *retired_list;       /* 退役列表（线程本地） */
    int retired_count;                     /* 退役列表长度 */
    struct hp_thread_record *next;         /* 全局链表 */
} hp_thread_record_t;

/* Hazard Pointer 域 */
typedef struct hp_domain {
    _Atomic(hp_thread_record_t *) head;   /* 线程记录链表头 */
    _Atomic(int) thread_count;            /* 活跃线程数 */
} hp_domain_t;

/* ========== 全局域 ========== */

static hp_domain_t g_hp_domain = {
    .head = NULL,
    .thread_count = 0
};

/* 线程局部存储：每个线程的记录 */
static _Thread_local hp_thread_record_t *tl_my_record = NULL;

/* ========== 线程注册与注销 ========== */

/*
 * hp_thread_acquire - 获取一个线程记录
 * 优先复用已注销线程的记录，否则分配新的。
 */
static hp_thread_record_t *hp_thread_acquire(hp_domain_t *domain) {
    hp_thread_record_t *rec;

    /* 尝试复用已有的非活跃记录 */
    rec = atomic_load_explicit(&domain->head, memory_order_acquire);
    while (rec != NULL) {
        bool expected = false;
        if (atomic_compare_exchange_strong_explicit(
                &rec->active, &expected, true,
                memory_order_acq_rel, memory_order_relaxed)) {
            /* 成功获取一个已有记录 */
            return rec;
        }
        rec = rec->next;
    }

    /* 没有可复用的记录，分配新的 */
    rec = (hp_thread_record_t *)calloc(1, sizeof(hp_thread_record_t));
    if (!rec) return NULL;

    atomic_store_explicit(&rec->active, true, memory_order_relaxed);
    for (int i = 0; i < HP_MAX_HPS; i++) {
        atomic_store_explicit(&rec->hp[i], NULL, memory_order_relaxed);
    }
    rec->retired_list = NULL;
    rec->retired_count = 0;

    /* 用 CAS 插入全局链表头部 */
    hp_thread_record_t *old_head;
    do {
        old_head = atomic_load_explicit(&domain->head, memory_order_acquire);
        rec->next = old_head;
    } while (!atomic_compare_exchange_weak_explicit(
                &domain->head, &old_head, rec,
                memory_order_acq_rel, memory_order_relaxed));

    atomic_fetch_add_explicit(&domain->thread_count, 1, memory_order_relaxed);
    return rec;
}

/*
 * hp_thread_release - 注销当前线程的记录
 */
static void hp_thread_release(hp_thread_record_t *rec) {
    for (int i = 0; i < HP_MAX_HPS; i++) {
        atomic_store_explicit(&rec->hp[i], NULL, memory_order_release);
    }
    atomic_store_explicit(&rec->active, false, memory_order_release);
}

/* ========== Hazard Pointer 操作 ========== */

/*
 * hp_protect - "读取-发布-验证"三步协议
 * 安全地获取一个共享指针的快照并发布 hazard pointer。
 */
static void *hp_protect(int hp_index, _Atomic(void *) *source,
                        hp_thread_record_t *rec) {
    void *ptr;
    do {
        ptr = atomic_load_explicit(source, memory_order_acquire);
        atomic_store_explicit(&rec->hp[hp_index], ptr, memory_order_release);
        atomic_thread_fence(memory_order_seq_cst);
    } while (ptr != atomic_load_explicit(source, memory_order_acquire));
    return ptr;
}

/*
 * hp_clear - 清除一个 hazard pointer 槽
 */
static void hp_clear(int hp_index, hp_thread_record_t *rec) {
    atomic_store_explicit(&rec->hp[hp_index], NULL, memory_order_release);
}

/* ========== Scan 算法 ========== */

/*
 * pointer 比较函数，用于 qsort 和 bsearch
 */
static int ptr_compare(const void *a, const void *b) {
    uintptr_t pa = (uintptr_t)(*(void **)a);
    uintptr_t pb = (uintptr_t)(*(void **)b);
    if (pa < pb) return -1;
    if (pa > pb) return 1;
    return 0;
}

/*
 * hp_scan - 扫描并回收安全的退役节点
 */
static void hp_scan(hp_domain_t *domain, hp_thread_record_t *rec) {
    int hp_count = 0;
    int max_hps = HP_MAX_THREADS * HP_MAX_HPS;
    void **plist = (void **)malloc(sizeof(void *) * max_hps);
    if (!plist) return;

    /* 阶段 1：收集所有活跃的 hazard pointers */
    hp_thread_record_t *cur = atomic_load_explicit(
        &domain->head, memory_order_acquire);
    while (cur != NULL) {
        if (atomic_load_explicit(&cur->active, memory_order_acquire)) {
            for (int i = 0; i < HP_MAX_HPS; i++) {
                void *hp = atomic_load_explicit(
                    &cur->hp[i], memory_order_acquire);
                if (hp != NULL) {
                    plist[hp_count++] = hp;
                }
            }
        }
        cur = cur->next;
    }

    /* 阶段 2：排序，用于后续二分查找 */
    qsort(plist, hp_count, sizeof(void *), ptr_compare);

    /* 阶段 3：扫描退役列表 */
    hp_retired_node_t *new_list = NULL;
    int new_count = 0;

    hp_retired_node_t *node = rec->retired_list;
    while (node != NULL) {
        hp_retired_node_t *next = node->next;

        /* 二分查找：该节点是否被任何 HP 保护？ */
        bool is_protected = (hp_count > 0) &&
            bsearch(&node->ptr, plist, hp_count,
                    sizeof(void *), ptr_compare) != NULL;

        if (is_protected) {
            /* 被保护，保留在退役列表 */
            node->next = new_list;
            new_list = node;
            new_count++;
        } else {
            /* 安全，调用 deleter 释放 */
            node->deleter(node->ptr);
            free(node);
        }

        node = next;
    }

    rec->retired_list = new_list;
    rec->retired_count = new_count;

    free(plist);
}

/* ========== Retire 操作 ========== */

/*
 * hp_retire - 将一个节点加入退役列表
 * 当退役列表超过阈值时触发 scan。
 */
static void hp_retire(hp_domain_t *domain, hp_thread_record_t *rec,
                      void *ptr, void (*deleter)(void *)) {
    hp_retired_node_t *rnode =
        (hp_retired_node_t *)malloc(sizeof(hp_retired_node_t));
    if (!rnode) {
        deleter(ptr);
        return;
    }

    rnode->ptr = ptr;
    rnode->deleter = deleter;
    rnode->next = rec->retired_list;
    rec->retired_list = rnode;
    rec->retired_count++;

    int threshold = 2 * atomic_load_explicit(
        &domain->thread_count, memory_order_relaxed) * HP_MAX_HPS;
    if (threshold < HP_SCAN_THRESHOLD)
        threshold = HP_SCAN_THRESHOLD;

    if (rec->retired_count >= threshold) {
        hp_scan(domain, rec);
    }
}

/* ========== 便捷接口 ========== */

/*
 * hp_init - 初始化当前线程
 * 必须在线程开始使用 HP 前调用。
 */
static inline void hp_init(void) {
    if (tl_my_record == NULL) {
        tl_my_record = hp_thread_acquire(&g_hp_domain);
    }
}

/*
 * hp_deinit - 注销当前线程
 * 在线程退出前调用，会尝试回收所有退役节点。
 */
static inline void hp_deinit(void) {
    if (tl_my_record != NULL) {
        /* 尝试最后一次 scan */
        hp_scan(&g_hp_domain, tl_my_record);
        /* 剩余无法释放的节点，交给其他线程处理（简化处理：此处不转移） */
        hp_thread_release(tl_my_record);
        tl_my_record = NULL;
    }
}

#endif /* HAZARD_POINTER_H */

/* lockfree_stack.c */
#include <stdio.h>
#include <pthread.h>
#include <assert.h>
#include "hazard_pointer.h"

/* ========== 无锁栈定义 ========== */

typedef struct stack_node {
    int value;
    struct stack_node *next;
} stack_node_t;

typedef struct lockfree_stack {
    _Atomic(void *) top;
} lockfree_stack_t;

static void stack_init(lockfree_stack_t *s) {
    atomic_store(&s->top, NULL);
}

static void stack_push(lockfree_stack_t *s, int value) {
    stack_node_t *node = (stack_node_t *)malloc(sizeof(stack_node_t));
    node->value = value;

    stack_node_t *old_top;
    do {
        old_top = atomic_load_explicit(&s->top, memory_order_acquire);
        node->next = old_top;
    } while (!atomic_compare_exchange_weak_explicit(
                &s->top, (void **)&old_top, node,
                memory_order_acq_rel, memory_order_relaxed));
}

static bool stack_pop(lockfree_stack_t *s, int *out_value) {
    hp_thread_record_t *rec = tl_my_record;
    stack_node_t *top;

    while (1) {
        /* 用 HP 保护 top 节点 */
        top = (stack_node_t *)hp_protect(0, &s->top, rec);
        if (top == NULL) {
            hp_clear(0, rec);
            return false;  /* 栈为空 */
        }

        stack_node_t *next = top->next;

        if (atomic_compare_exchange_weak_explicit(
                &s->top, (void **)&top, next,
                memory_order_acq_rel, memory_order_relaxed)) {
            /* CAS 成功，摘除了 top 节点 */
            *out_value = top->value;
            hp_clear(0, rec);

            /* 不是 free(top)，而是 retire */
            hp_retire(&g_hp_domain, rec, top, free);
            return true;
        }
        /* CAS 失败，重试（HP 会在下一轮循环中更新） */
    }
}

/* ========== 测试 ========== */

#define NUM_THREADS   8
#define OPS_PER_THREAD 100000

static lockfree_stack_t g_stack;
static _Atomic(long) g_push_sum = 0;
static _Atomic(long) g_pop_sum = 0;

static void *worker(void *arg) {
    int tid = (int)(long)arg;
    hp_init();

    long local_push_sum = 0;
    long local_pop_sum = 0;

    for (int i = 0; i < OPS_PER_THREAD; i++) {
        if (i % 2 == 0) {
            int val = tid * OPS_PER_THREAD + i;
            stack_push(&g_stack, val);
            local_push_sum += val;
        } else {
            int val;
            if (stack_pop(&g_stack, &val)) {
                local_pop_sum += val;
            }
        }
    }

    atomic_fetch_add(&g_push_sum, local_push_sum);
    atomic_fetch_add(&g_pop_sum, local_pop_sum);

    hp_deinit();
    return NULL;
}

int main(void) {
    stack_init(&g_stack);

    pthread_t threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, worker, (void *)(long)i);
    }
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    /* 弹出栈中剩余元素 */
    hp_init();
    long drain_sum = 0;
    int val;
    while (stack_pop(&g_stack, &val)) {
        drain_sum += val;
    }
    hp_deinit();

    long total_push = atomic_load(&g_push_sum);
    long total_pop = atomic_load(&g_pop_sum) + drain_sum;

    printf("push sum = %ld\n", total_push);
    printf("pop  sum = %ld\n", total_pop);
    printf("match: %s\n", total_push == total_pop ? "YES" : "NO");

    return 0;
}

gcc -std=c11 -O2 -pthread lockfree_stack.c -o lockfree_stack
./lockfree_stack

// folly 的使用接口非常简洁
auto holder = folly::makeHazardPointer();
auto *ptr = holder.protect(atomicPtr);
// ptr 在 holder 生命周期内保证有效
// holder 析构时自动清除 HP

// P2530 提案接口（简化版）
namespace std {
    template<typename T>
    class hazard_pointer {
    public:
        hazard_pointer() noexcept;
        hazard_pointer(hazard_pointer&&) noexcept;
        ~hazard_pointer();

        // 保护一个原子指针
        T* protect(const atomic<T*>& source) noexcept;

        // 清除保护
        void reset_protection() noexcept;
    };

    // 退役一个指针
    template<typename T, typename D = default_delete<T>>
    void hazard_pointer_retire(T* ptr, D deleter = {});
}