safe_hazard_pointer.h

Go to the documentation of this file.

// BSD 3-Clause License
// Copyright (c) 2021-2025, 🍀☀🌕🌥 🌊
// See the LICENSE file in the project root for full license information.
 
#pragma once
 
#include <algorithm>
#include <array>
#include <atomic>
#include <cassert>
#include <functional>
#include <memory>
#include <mutex>
#include <thread>
#include <unordered_set>
#include <vector>
 
namespace kcenon::thread {
 
class safe_hazard_pointer_record {
public:
    static constexpr size_t MAX_HAZARD_POINTERS = 2;
 
    safe_hazard_pointer_record() {
        for (auto& hp : hazard_pointers_) {
            hp.store(nullptr, std::memory_order_relaxed);
        }
        next.store(nullptr, std::memory_order_relaxed);
        active.store(false, std::memory_order_relaxed);
    }
 
    void protect(void* p, size_t slot = 0) noexcept {
        assert(slot < MAX_HAZARD_POINTERS);
        hazard_pointers_[slot].store(p, std::memory_order_release);
    }
 
    void clear(size_t slot = 0) noexcept {
        assert(slot < MAX_HAZARD_POINTERS);
        hazard_pointers_[slot].store(nullptr, std::memory_order_release);
    }
 
    [[nodiscard]] bool contains(void* p) const noexcept {
        for (const auto& hp : hazard_pointers_) {
            if (hp.load(std::memory_order_acquire) == p) {
                return true;
            }
        }
        return false;
    }
 
    [[nodiscard]] void* get(size_t slot = 0) const noexcept {
        assert(slot < MAX_HAZARD_POINTERS);
        return hazard_pointers_[slot].load(std::memory_order_acquire);
    }
 
    // Linked list for global registry
    std::atomic<safe_hazard_pointer_record*> next{nullptr};
    std::atomic<bool> active{false};
 
private:
    std::array<std::atomic<void*>, MAX_HAZARD_POINTERS> hazard_pointers_;
};
 
class safe_hazard_pointer_domain {
public:
    using retire_callback = std::function<void(void*)>;
 
    static safe_hazard_pointer_domain& instance() {
        static safe_hazard_pointer_domain domain;
        return domain;
    }
 
    safe_hazard_pointer_record* acquire() {
        // 1. Try to reuse an inactive record first
        safe_hazard_pointer_record* p = head_.load(std::memory_order_acquire);
        while (p != nullptr) {
            bool expected = false;
            if (p->active.compare_exchange_strong(
                    expected, true,
                    std::memory_order_acq_rel,
                    std::memory_order_relaxed)) {
                // Clear hazard pointers immediately after acquiring to avoid
                // stale pointers from previous use affecting collect()
                p->clear(0);
                p->clear(1);
                active_count_.fetch_add(1, std::memory_order_relaxed);
                return p;
            }
            p = p->next.load(std::memory_order_acquire);
        }
 
        // 2. Create new record (constructor already clears hazard pointers)
        auto* new_record = new safe_hazard_pointer_record();
        new_record->active.store(true, std::memory_order_relaxed);
 
        // 3. Add to list (lock-free)
        safe_hazard_pointer_record* old_head;
        do {
            old_head = head_.load(std::memory_order_relaxed);
            new_record->next.store(old_head, std::memory_order_relaxed);
        } while (!head_.compare_exchange_weak(
            old_head, new_record,
            std::memory_order_release,
            std::memory_order_relaxed));
 
        active_count_.fetch_add(1, std::memory_order_relaxed);
        return new_record;
    }
 
    void release(safe_hazard_pointer_record* record) noexcept {
        if (record == nullptr) {
            return;
        }
 
        record->clear(0);
        record->clear(1);
        record->active.store(false, std::memory_order_release);
        active_count_.fetch_sub(1, std::memory_order_relaxed);
    }
 
    void retire(void* p, retire_callback deleter) {
        if (p == nullptr) {
            return;
        }
 
        bool should_collect = false;
        {
            std::lock_guard<std::mutex> lock(retire_mutex_);
 
            // Remove any existing entry with the same address to handle memory reuse.
            // This can happen when memory is freed and reallocated to the same address.
            // In this case, the old entry's deleter must NOT be called since the memory
            // is now occupied by a new valid object.
            auto it = std::remove_if(retired_list_.begin(), retired_list_.end(),
                [p](const auto& entry) { return entry.first == p; });
            if (it != retired_list_.end()) {
                size_t removed = std::distance(it, retired_list_.end());
                retired_list_.erase(it, retired_list_.end());
                retired_count_.fetch_sub(removed, std::memory_order_relaxed);
            }
 
            retired_list_.emplace_back(p, std::move(deleter));
            retired_count_.fetch_add(1, std::memory_order_relaxed);
 
            // Check threshold inside lock to avoid race
            size_t threshold = get_adaptive_threshold();
            should_collect = (retired_count_.load(std::memory_order_relaxed) >= threshold);
        }
 
        // Trigger collection after releasing lock to avoid deadlock
        if (should_collect) {
            collect();
        }
    }
 
    void collect() {
        std::lock_guard<std::mutex> lock(retire_mutex_);
        collect_internal();
    }
 
    [[nodiscard]] size_t retired_count() const noexcept {
        return retired_count_.load(std::memory_order_relaxed);
    }
 
    [[nodiscard]] size_t active_count() const noexcept {
        return active_count_.load(std::memory_order_relaxed);
    }
 
private:
    safe_hazard_pointer_domain() = default;
 
    ~safe_hazard_pointer_domain() {
        // Delete all records
        auto* p = head_.load(std::memory_order_relaxed);
        while (p != nullptr) {
            auto* next = p->next.load(std::memory_order_relaxed);
            delete p;
            p = next;
        }
 
        // Force delete remaining retired objects
        for (auto& [ptr, deleter] : retired_list_) {
            if (deleter && ptr) {
                deleter(ptr);
            }
        }
    }
 
    // Prevent copying
    safe_hazard_pointer_domain(const safe_hazard_pointer_domain&) = delete;
    safe_hazard_pointer_domain& operator=(const safe_hazard_pointer_domain&) = delete;
 
    void collect_internal() {
        if (retired_list_.empty()) {
            return;
        }
 
        // Gather all currently protected pointers
        // IMPORTANT: Check ALL records, not just active ones, to avoid race condition
        // where a record is being reused while we're scanning.
        // The hazard pointer value is set before active=true, so we must check
        // the pointer value itself, not the active flag.
        std::unordered_set<void*> hazards;
        hazards.reserve(active_count_.load(std::memory_order_relaxed) *
                        safe_hazard_pointer_record::MAX_HAZARD_POINTERS);
 
        safe_hazard_pointer_record* p = head_.load(std::memory_order_acquire);
        while (p != nullptr) {
            // Check all records regardless of active status to avoid race condition
            for (size_t i = 0; i < safe_hazard_pointer_record::MAX_HAZARD_POINTERS; ++i) {
                void* hp = p->get(i);
                if (hp != nullptr) {
                    hazards.insert(hp);
                }
            }
            p = p->next.load(std::memory_order_acquire);
        }
 
        // Delete objects not in hazard set
        size_t reclaimed = 0;
        auto it = retired_list_.begin();
        while (it != retired_list_.end()) {
            if (hazards.find(it->first) == hazards.end()) {
                // Safe to delete
                if (it->second && it->first) {
                    it->second(it->first);
                }
                it = retired_list_.erase(it);
                ++reclaimed;
            } else {
                ++it;
            }
        }
 
        retired_count_.fetch_sub(reclaimed, std::memory_order_relaxed);
    }
 
    [[nodiscard]] size_t get_adaptive_threshold() const noexcept {
        static constexpr size_t BASE_THRESHOLD = 64;
        static constexpr size_t PER_THREAD_THRESHOLD = 16;
        static constexpr size_t MAX_THRESHOLD = 512;
 
        size_t active = active_count_.load(std::memory_order_relaxed);
        return std::min(MAX_THRESHOLD, BASE_THRESHOLD + active * PER_THREAD_THRESHOLD);
    }
 
    std::atomic<safe_hazard_pointer_record*> head_{nullptr};
    std::atomic<size_t> active_count_{0};
    std::atomic<size_t> retired_count_{0};
    std::mutex retire_mutex_;
    std::vector<std::pair<void*, retire_callback>> retired_list_;
};
 
class safe_hazard_guard {
public:
    explicit safe_hazard_guard(void* p = nullptr, size_t slot = 0)
        : record_(safe_hazard_pointer_domain::instance().acquire())
        , slot_(slot) {
        if (p != nullptr) {
            record_->protect(p, slot_);
        }
    }
 
    ~safe_hazard_guard() {
        if (record_ != nullptr) {
            safe_hazard_pointer_domain::instance().release(record_);
        }
    }
 
    // Non-copyable
    safe_hazard_guard(const safe_hazard_guard&) = delete;
    safe_hazard_guard& operator=(const safe_hazard_guard&) = delete;
 
    // Movable
    safe_hazard_guard(safe_hazard_guard&& other) noexcept
        : record_(other.record_)
        , slot_(other.slot_) {
        other.record_ = nullptr;
    }
 
    safe_hazard_guard& operator=(safe_hazard_guard&& other) noexcept {
        if (this != &other) {
            if (record_ != nullptr) {
                safe_hazard_pointer_domain::instance().release(record_);
            }
            record_ = other.record_;
            slot_ = other.slot_;
            other.record_ = nullptr;
        }
        return *this;
    }
 
    void protect(void* p) noexcept {
        if (record_ != nullptr) {
            record_->protect(p, slot_);
        }
    }
 
    void clear() noexcept {
        if (record_ != nullptr) {
            record_->clear(slot_);
        }
    }
 
    [[nodiscard]] void* get() const noexcept {
        return record_ != nullptr ? record_->get(slot_) : nullptr;
    }
 
    [[nodiscard]] explicit operator bool() const noexcept {
        return record_ != nullptr;
    }
 
private:
    safe_hazard_pointer_record* record_;
    size_t slot_;
};
 
template<typename T>
void safe_retire_hazard(T* p) {
    if (p == nullptr) {
        return;
    }
    safe_hazard_pointer_domain::instance().retire(
        p,
        [](void* ptr) { delete static_cast<T*>(ptr); }
    );
}
 
template<typename T>
class typed_safe_hazard_domain {
public:
    static typed_safe_hazard_domain& instance() {
        static typed_safe_hazard_domain domain;
        return domain;
    }
 
    void retire(T* p) {
        safe_retire_hazard(p);
    }
 
    void collect() {
        safe_hazard_pointer_domain::instance().collect();
    }
 
private:
    typed_safe_hazard_domain() = default;
};
 
}  // namespace kcenon::thread