并发中的内存回收

Hazard Pointers（危险指针）

✅ 作用：保护正在访问的指针，防止它被其他线程释放。

每个线程维护一组“hazard slots”，用于声明当前正在使用的节点。

在释放节点前，必须检查是否有线程将其标记为 hazard。如果有，就延迟释放。

📌 优点：精细控制：每个指针都可以独立保护。

快速释放：一旦没有线程标记该节点，就可以立即释放。

⚠️ 缺点：每个线程需要维护额外的指针集合。

实现复杂度较高，尤其在高并发场景下。

Epoch-Based Reclamation（基于世代的回收）

✅ 作用：将所有线程的操作划分到一个“epoch”（时间段）中。

每个线程在进入临界区时记录当前 epoch，退出时清除。

被删除的节点会挂到当前 epoch 的垃圾列表中，只有当所有线程都离开该 epoch，才安全释放这些节点。

📌 优点：实现简单，性能好，适合高吞吐量场景。

不需要每个指针都单独保护。

⚠️ 缺点：回收延迟：必须等待所有线程退出当前 epoch。

对长时间运行的线程敏感，可能阻止垃圾回收。

🧠 为什么需要它们？

在 lock-free 数据结构中，节点可能被多个线程同时访问或修改。没有互斥锁保护时，直接释放内存可能导致：

• 悬挂指针：其他线程还在访问被释放的节点。
• ABA 问题：节点被释放后地址复用，导致逻辑错误。

ebr.cppview raw

// EBR: Epoch-Based Reclamation
#include <atomic>
#include <iostream>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <vector>

constexpr int MAX_THREADS = 4;

std::atomic<int> global_epoch{0};
std::atomic<bool> active[MAX_THREADS];
std::atomic<int> local_epoch[MAX_THREADS];

std::mutex retire_mutex;
std::unordered_map<int, std::vector<int*>> retire_list[3];  // 每个 epoch 的垃圾列表

void enter_critical(int tid) {
    active[tid].store(true, std::memory_order_relaxed);
    local_epoch[tid].store(global_epoch.load(std::memory_order_relaxed),
                           std::memory_order_relaxed);
}

void exit_critical(int tid) {
    active[tid].store(false, std::memory_order_relaxed);
}

void retire_node(int tid, int* node) {
    std::lock_guard<std::mutex> lock(retire_mutex);
    int epoch = global_epoch.load(std::memory_order_relaxed);
    retire_list[epoch][tid].push_back(node);
}

void try_advance_epoch() {
    int current = global_epoch.load(std::memory_order_relaxed);
    for (int i = 0; i < MAX_THREADS; ++i) {
        if (active[i].load(std::memory_order_relaxed) &&
            local_epoch[i].load(std::memory_order_relaxed) != current) {
            return;  // 有线程还在旧 epoch，不能推进
        }
    }

    int next_epoch = (current + 1) % 3;
    global_epoch.store(next_epoch, std::memory_order_relaxed);

    // 回收两代前的垃圾
    int reclaim_epoch = (next_epoch + 1) % 3;
    std::lock_guard<std::mutex> lock(retire_mutex);
    for (auto& [tid, nodes] : retire_list[reclaim_epoch]) {
        for (auto node : nodes) {
            delete node;
        }
        nodes.clear();
    }
}