hazard_ptr.hpp

浏览该文件的文档.

#ifndef NEFORCE_CORE_ASYNC_HAZARD_PTR_HPP__
#define NEFORCE_CORE_ASYNC_HAZARD_PTR_HPP__

 
#include "NeForce/core/algorithm/sort.hpp"
#include "NeForce/core/async/atomic.hpp"
#include "NeForce/core/container/vector.hpp"
#include "NeForce/core/utility/deleter.hpp"
NEFORCE_BEGIN_NAMESPACE__


 
class hazard_pointer_domain;
class hazard_pointer_obj_base;

struct hazard_pointer_record {
    atomic<void*> hazard_ptr{nullptr};            
    atomic<hazard_pointer_record*> next{nullptr}; 
    atomic<bool> active{false};                   
 
    hazard_pointer_record() = default;

    bool try_acquire() {
        bool expected = false;
        return active.compare_exchange_strong(expected, true, memory_order_acquire, memory_order_relaxed);
    }

    void release() {
        hazard_ptr.store(nullptr, memory_order_release);
        active.store(false, memory_order_release);
    }

    void protect(void* ptr) { hazard_ptr.store(ptr, memory_order_release); }

    NEFORCE_NODISCARD void* get_protected() const { return hazard_ptr.load(memory_order_acquire); }
};

class hazard_pointer_obj_base {
public:
    hazard_pointer_obj_base* next{nullptr}; 
 
    virtual ~hazard_pointer_obj_base() = default;
    virtual void destroy() = 0;                          
    NEFORCE_NODISCARD virtual void* get_ptr() const = 0; 
};

template <typename T, typename Deleter = default_deleter<void>>
class hazard_pointer_obj final : public hazard_pointer_obj_base {
    T* ptr;          
    Deleter deleter; 
 
public:
    explicit hazard_pointer_obj(T* p, Deleter d = Deleter()) :
    ptr(p),
    deleter(_NEFORCE move(d)) {}

    void destroy() override { deleter(ptr); }
 
    NEFORCE_NODISCARD void* get_ptr() const override { return static_cast<void*>(ptr); }
};

struct retire_list {
    hazard_pointer_obj_base* head{nullptr}; 
    size_t count{0};                        
 
    retire_list() noexcept = default;

    retire_list(retire_list&& other) noexcept :
    head(other.head),
    count(other.count) {
        other.head = nullptr;
        other.count = 0;
    }

    retire_list& operator=(retire_list&& other) noexcept {
        if (addressof(other) == this) {
            return *this;
        }
        clear();
        head = other.head;
        count = other.count;
        other.head = nullptr;
        other.count = 0;
        return *this;
    }
 
    retire_list(const retire_list&) = delete;
    retire_list& operator=(const retire_list&) = delete;

    ~retire_list() { clear(); }

    void add(hazard_pointer_obj_base* obj) {
        obj->next = head;
        head = obj;
        ++count;
    }

    void clear() {
        while (head != nullptr) {
            auto* next = head->next;
            head->destroy();
            delete head;
            head = next;
        }
        count = 0;
    }
};

class hazard_pointer_domain {
private:
    atomic<hazard_pointer_record*> head_{nullptr}; 
 
    static retire_list& get_thread_retire_list() {
        thread_local retire_list list;
        return list;
    }
 
    static constexpr size_t RETIRE_THRESHOLD = 100; 

    vector<void*> get_hazard_pointers() {
        vector<void*> hazards;
        hazard_pointer_record* current = head_.load(memory_order_acquire);
 
        while (current != nullptr) {
            if (current->active.load(memory_order_acquire)) {
                void* ptr = current->get_protected();
                if (ptr != nullptr) {
                    hazards.push_back(ptr);
                }
            }
            current = current->next.load(memory_order_acquire);
        }
 
        return hazards;
    }

    void scan_and_reclaim() {
        auto hazards = get_hazard_pointers();
        _NEFORCE sort(hazards.begin(), hazards.end(), less<void*>());
 
        auto& thread_list = get_thread_retire_list();
        hazard_pointer_obj_base* current = thread_list.head;
        thread_list.head = nullptr;
        thread_list.count = 0;
 
        hazard_pointer_obj_base* keep_head = nullptr;
        size_t keep_count = 0;
        hazard_pointer_obj_base* destroy_head = nullptr;
 
        while (current != nullptr) {
            auto* next = current->next;
            void* inner_ptr = current->get_ptr();
 
            if (_NEFORCE binary_search(hazards.begin(), hazards.end(), inner_ptr, less<void*>())) {
                current->next = keep_head;
                keep_head = current;
                ++keep_count;
            } else {
                current->next = destroy_head;
                destroy_head = current;
            }
            current = next;
        }
 
        while (destroy_head != nullptr) {
            auto* next = destroy_head->next;
            destroy_head->destroy();
            delete destroy_head;
            destroy_head = next;
        }
 
        thread_list.head = keep_head;
        thread_list.count = keep_count;
    }
 
public:
    hazard_pointer_domain() = default;

    ~hazard_pointer_domain() {
        hazard_pointer_record* current = head_.load();
        while (current != nullptr) {
            auto* next = current->next.load();
            delete current;
            current = next;
        }
    }
 
    hazard_pointer_domain(const hazard_pointer_domain&) = delete;
    hazard_pointer_domain& operator=(const hazard_pointer_domain&) = delete;

    hazard_pointer_record* acquire_record() {
        hazard_pointer_record* current = head_.load(memory_order_acquire);
        while (current != nullptr) {
            if (current->try_acquire()) {
                return current;
            }
            current = current->next.load(memory_order_acquire);
        }
 
        auto* new_record = new hazard_pointer_record();
        new_record->active.store(true, memory_order_relaxed);
 
        hazard_pointer_record* old_head = head_.load(memory_order_relaxed);
        do {
            new_record->next.store(old_head, memory_order_relaxed);
        } while (!head_.compare_exchange_weak(old_head, new_record, memory_order_release, memory_order_relaxed));
 
        return new_record;
    }

    template <typename T, typename Deleter = default_deleter<T>>
    void retire(T* ptr, Deleter deleter = Deleter()) {
        if (!ptr) {
            return;
        }
 
        auto* obj = new hazard_pointer_obj<T, Deleter>(ptr, _NEFORCE move(deleter));
        get_thread_retire_list().add(obj);
 
        if (get_thread_retire_list().count >= RETIRE_THRESHOLD) {
            scan_and_reclaim();
        }
    }

    void reclaim() { scan_and_reclaim(); }

    static hazard_pointer_domain& default_domain() {
        static hazard_pointer_domain domain{};
        return domain;
    }
};
 

class hazard_pointer {
private:
    hazard_pointer_record* record_{nullptr}; 
    hazard_pointer_domain* domain_{nullptr}; 
 
public:
    hazard_pointer() = default;

    explicit hazard_pointer(hazard_pointer_domain& domain) :
    domain_(&domain) {
        record_ = domain_->acquire_record();
    }

    ~hazard_pointer() {
        reset_protection();
        if (record_ != nullptr) {
            record_->release();
        }
    }
 
    hazard_pointer(hazard_pointer&& other) noexcept :
    record_(other.record_),
    domain_(other.domain_) {
        other.record_ = nullptr;
        other.domain_ = nullptr;
    }
 
    hazard_pointer& operator=(hazard_pointer&& other) noexcept {
        if (addressof(other) == this) {
            return *this;
        }
 
        reset_protection();
        if (record_ != nullptr) {
            record_->release();
        }
        record_ = other.record_;
        domain_ = other.domain_;
        other.record_ = nullptr;
        other.domain_ = nullptr;
 
        return *this;
    }
 
    hazard_pointer(const hazard_pointer&) = delete;
    hazard_pointer& operator=(const hazard_pointer&) = delete;

    template <typename T>
    T* protect(const atomic<T*>& src) {
        if (!record_) {
            return nullptr;
        }
 
        T* ptr = src.load(memory_order_relaxed);
        while (true) {
            record_->protect(ptr);
            T* ptr2 = src.load(memory_order_acquire);
            if (ptr == ptr2) {
                return ptr;
            }
            ptr = ptr2;
        }
    }

    template <typename T>
    bool try_protect(T*& ptr, const atomic<T*>& src) {
        if (!record_) {
            return false;
        }
 
        ptr = src.load(memory_order_relaxed);
        record_->protect(ptr);
        T* ptr2 = src.load(memory_order_acquire);
 
        if (ptr == ptr2) {
            return true;
        }
 
        ptr = ptr2;
        return false;
    }

    void reset_protection() noexcept {
        if (record_ != nullptr) {
            record_->protect(nullptr);
        }
    }

    void swap(hazard_pointer& other) noexcept {
        _NEFORCE swap(record_, other.record_);
        _NEFORCE swap(domain_, other.domain_);
    }

    explicit operator bool() const noexcept { return record_ != nullptr; }
};

inline hazard_pointer make_hazard_pointer(hazard_pointer_domain& domain = hazard_pointer_domain::default_domain()) {
    return hazard_pointer(domain);
}
 

template <typename T>
class hazard_pointer_holder {
private:
    hazard_pointer hp_; 
    T* ptr_{nullptr};   
 
public:
    hazard_pointer_holder() = default;

    explicit hazard_pointer_holder(hazard_pointer_domain& domain) :
    hp_(domain) {}

    T* protect(const atomic<T*>& src) {
        ptr_ = hp_.protect(src);
        return ptr_;
    }

    T* get() const noexcept { return ptr_; }

    T& operator*() const noexcept { return *ptr_; }

    T* operator->() const noexcept { return ptr_; }

    explicit operator bool() const noexcept { return ptr_ != nullptr; }

    void reset() noexcept {
        hp_.reset_protection();
        ptr_ = nullptr;
    }
};
 // HazardPointer
 // AsyncComponents
 
NEFORCE_END_NAMESPACE__
#endif // NEFORCE_CORE_ASYNC_HAZARD_PTR_HPP__