epoch_manager.h

Go to the documentation of this file.

// BSD 3-Clause License
// Copyright (c) 2024, 🍀☀🌕🌥 🌊
// See the LICENSE file in the project root for full license information.
 
#pragma once
 
#include <atomic>
#include <array>
#include <vector>
#include <functional>
#include <mutex>
 
namespace kcenon::container
{
    class epoch_manager
    {
    public:
        static constexpr uint64_t INACTIVE = UINT64_MAX;
 
        static constexpr size_t NUM_EPOCHS = 3;
 
        static epoch_manager& instance() {
            static epoch_manager instance;
            return instance;
        }
 
        void enter_critical() noexcept {
            thread_epoch() = global_epoch_.load(std::memory_order_acquire);
        }
 
        void exit_critical() noexcept {
            thread_epoch() = INACTIVE;
        }
 
        [[nodiscard]] bool in_critical_section() const noexcept {
            return thread_epoch() != INACTIVE;
        }
 
        void defer_delete(void* ptr, std::function<void(void*)> deleter) {
            if (ptr == nullptr) {
                return;
            }
 
            uint64_t epoch = global_epoch_.load(std::memory_order_relaxed);
            size_t bucket = epoch % NUM_EPOCHS;
 
            std::lock_guard<std::mutex> lock(retire_mutex_[bucket]);
            retired_[bucket].emplace_back(ptr, std::move(deleter));
        }
 
        template<typename T>
        void defer_delete(T* ptr) {
            defer_delete(static_cast<void*>(ptr), [](void* p) {
                delete static_cast<T*>(p);
            });
        }
 
        size_t try_gc() {
            // Advance epoch
            uint64_t current = global_epoch_.fetch_add(1, std::memory_order_acq_rel);
 
            // Calculate which epoch is safe to collect
            // We need 2 epoch advances before an epoch is safe
            if (current < 2) {
                return 0;
            }
 
            uint64_t safe_epoch = current - 2;
            size_t bucket = safe_epoch % NUM_EPOCHS;
 
            // Check if any thread is still in the safe epoch
            // For simplicity, we just try to collect
            // In production, you'd check all registered threads
 
            std::vector<std::pair<void*, std::function<void(void*)>>> to_delete;
            {
                std::lock_guard<std::mutex> lock(retire_mutex_[bucket]);
                to_delete = std::move(retired_[bucket]);
                retired_[bucket].clear();
            }
 
            // Actually delete the objects
            for (auto& [ptr, deleter] : to_delete) {
                deleter(ptr);
            }
 
            gc_count_.fetch_add(1, std::memory_order_relaxed);
            reclaimed_count_.fetch_add(to_delete.size(), std::memory_order_relaxed);
 
            return to_delete.size();
        }
 
        size_t force_gc() {
            size_t total = 0;
            for (size_t i = 0; i < NUM_EPOCHS; ++i) {
                std::vector<std::pair<void*, std::function<void(void*)>>> to_delete;
                {
                    std::lock_guard<std::mutex> lock(retire_mutex_[i]);
                    to_delete = std::move(retired_[i]);
                    retired_[i].clear();
                }
 
                for (auto& [ptr, deleter] : to_delete) {
                    deleter(ptr);
                }
                total += to_delete.size();
            }
 
            if (total > 0) {
                gc_count_.fetch_add(1, std::memory_order_relaxed);
                reclaimed_count_.fetch_add(total, std::memory_order_relaxed);
            }
 
            return total;
        }
 
        [[nodiscard]] uint64_t current_epoch() const noexcept {
            return global_epoch_.load(std::memory_order_relaxed);
        }
 
        [[nodiscard]] size_t gc_count() const noexcept {
            return gc_count_.load(std::memory_order_relaxed);
        }
 
        [[nodiscard]] size_t reclaimed_count() const noexcept {
            return reclaimed_count_.load(std::memory_order_relaxed);
        }
 
        [[nodiscard]] size_t pending_count() const {
            size_t total = 0;
            for (size_t i = 0; i < NUM_EPOCHS; ++i) {
                std::lock_guard<std::mutex> lock(retire_mutex_[i]);
                total += retired_[i].size();
            }
            return total;
        }
 
        // Delete copy and move operations
        epoch_manager(const epoch_manager&) = delete;
        epoch_manager& operator=(const epoch_manager&) = delete;
        epoch_manager(epoch_manager&&) = delete;
        epoch_manager& operator=(epoch_manager&&) = delete;
 
    private:
        epoch_manager() = default;
 
        ~epoch_manager() {
            force_gc();
        }
 
        static std::atomic<uint64_t>& thread_epoch() {
            thread_local std::atomic<uint64_t> epoch{INACTIVE};
            return epoch;
        }
 
        std::atomic<uint64_t> global_epoch_{0};
        std::atomic<size_t> gc_count_{0};
        std::atomic<size_t> reclaimed_count_{0};
 
        mutable std::array<std::mutex, NUM_EPOCHS> retire_mutex_;
        std::array<std::vector<std::pair<void*, std::function<void(void*)>>>, NUM_EPOCHS> retired_;
    };
 
    class epoch_guard
    {
    public:
        epoch_guard() noexcept {
            epoch_manager::instance().enter_critical();
        }
 
        ~epoch_guard() noexcept {
            epoch_manager::instance().exit_critical();
        }
 
        // Non-copyable, non-movable
        epoch_guard(const epoch_guard&) = delete;
        epoch_guard& operator=(const epoch_guard&) = delete;
        epoch_guard(epoch_guard&&) = delete;
        epoch_guard& operator=(epoch_guard&&) = delete;
    };
 
} // namespace kcenon::container