memory_pool.cpp

#include "memory_pool.hpp"
#include <cstring>
#include <memory>

/* ============================================================================
 * Memory Pool Implementation — Professional Bilingual Documentation
 * 内存池实现 —— 专业中英文双语文档
 *
 * Overview / 概述
 * - This file implements a high‑performance, mixed‑strategy memory pool that routes
 *   allocation requests to four specialized managers based on size classes:
 *   SmallMemoryManager (slab + bucket), MediumMemoryManager (buddy system),
 *   LargeMemoryManager (tracked large allocations), and HugeMemoryManager (very
 *   large direct allocations). The goal is to minimize fragmentation, reduce
 *   synchronization overhead, and provide predictable allocation latency.
 * - 本文件实现了一个高性能、混合策略的内存池，根据大小类别将分配请求路由至四种
 *   专用管理器：SmallMemoryManager（基于 slab 与桶的设计）、MediumMemoryManager
 *   （伙伴系统）、LargeMemoryManager（可追踪的大块分配）以及 HugeMemoryManager
 *   （超大直接分配）。目标是最小化碎片、降低同步开销，并提供可预测的分配时延。
 *
 * Concurrency Model / 并发模型
 * - SmallMemoryManager uses a thread‑local cache to satisfy most allocations and
 *   a global lock‑free Treiber stack per bucket (or a mutex‑based fallback) for
 *   cross‑thread recycling. A per‑slab bitmap tracks slot state.
 * - SmallMemoryManager 通过线程局部缓存优先满足分配，并在每个桶上使用无锁
 *   Treiber 栈（或基于互斥量的回退）进行跨线程回收；每个 slab 以位图维护槽位状态。
 *
 * - MediumMemoryManager is a classic buddy allocator. It uses compare‑and‑swap
 *   operations to maintain free lists, plus a background merge worker that
 *   processes a circular queue of merge requests to coalesce buddies.
 * - MediumMemoryManager 为经典伙伴分配器。其使用比较并交换（compare and swap，
 *   CAS）维护空闲链表，并通过后台合并线程处理环形队列中的合并请求，实现伙伴块合并。
 *
 * - LargeMemoryManager and HugeMemoryManager forward requests to the operating
 *   system while keeping precise accounting for leak detection and reporting.
 * - LargeMemoryManager 与 HugeMemoryManager 将请求转发给操作系统，同时进行精确
 *   计数，以支持内存泄漏检测与报告。
 *
 * Thread Safety and Memory Ordering / 线程安全与内存序
 * - The code uses acquire/release semantics on critical atomic paths to ensure
 *   that header state and freelist links are observed consistently across threads.
 * - 关键的原子路径采用 acquire/release 语义，确保跨线程一致地观察到头部状态与空闲链。
 *
 * Error Handling / 错误处理
 * - Debug diagnostics print explicit messages on invalid headers or double free.
 * - 在调试模式下，对于无效头部或二次释放会输出明确的诊断信息。
 *
 * Naming and External Interface Policy / 命名与外部接口策略
 * - As required, no external interface or naming is modified. New comments avoid
 *   abbreviations; when technical abbreviations are unavoidable, a full term is
 *   provided on first mention, for example: compare and swap (CAS),
 *   thread‑local storage (TLS).
 * - 根据要求，不修改任何外部接口或命名。新增注释避免使用缩写；若技术缩写不可避免，
 *   首次出现给出全称，例如：比较并交换（CAS）、线程局部存储（TLS）。
 *
 * Invariants / 不变式
 * - All headers carry magic numbers for class‑specific validation.
 * - 所有头部包含用于各自类别校验的 magic 值。
 *
 * Copyright
 * - This documentation block is added without changing logic or symbols.
 * - 本文档块仅新增注释，不改变任何逻辑或符号。
 * ============================================================================ */



// ============================ 静态成员定义 ============================
std::atomic<bool>								  MemoryPool::construction_warning_shown { false };
thread_local SmallMemoryManager::ThreadLocalCache SmallMemoryManager::thread_local_cache;
std::atomic<int>								  MemoryPool::live_pools { 0 };

/* =====================================================================
 *  SmallMemoryManager — slab 支撑，但“桶=SmallMemoryHeader* Treiber 栈 + TLS”保持
 * ===================================================================== */

// ---- slab helpers ----
SmallMemoryManager::SmallSlab* 
/**
 * Create a new slab and initialize slot headers for the specified bucket size.
 * 创建新的 slab，并为指定桶大小初始化槽位头部信息。
 */
SmallMemoryManager::make_new_slab( std::size_t bucket_index, std::size_t bucket_bytes, std::size_t alignment )
{
	const std::size_t block_bytes = sizeof( SmallMemoryHeader ) + bucket_bytes;
	const std::size_t target_bytes = 1ull << 20;  // 目标 1 MiB
	std::size_t		  capacity = target_bytes / block_bytes;
	if ( capacity == 0 )
		capacity = 1;
	if ( capacity > 64 )
		capacity = 64;

	const std::size_t slab_bytes = sizeof( SmallSlab ) + capacity * block_bytes;

	void* raw = os_memory::allocate_tracked( slab_bytes, alignment );
	if ( !raw )
		throw std::bad_alloc();
	{
		std::lock_guard<std::mutex> lk( chunk_mutex );
		allocated_chunks.emplace_back( raw, slab_bytes );
	}

	auto* slab = new ( raw ) SmallSlab();
	slab->bitmap.store( 0, std::memory_order_relaxed );
	slab->used.store( 0, std::memory_order_relaxed );
	slab->capacity = static_cast<std::uint32_t>( capacity );
	slab->bucket_index = static_cast<std::uint32_t>( bucket_index );
	slab->bucket_bytes = bucket_bytes;
	slab->block_bytes = block_bytes;

	// 初始化每个槽的 SmallMemoryHeader
	for ( std::uint32_t i = 0; i < slab->capacity; ++i )
	{
		auto* slab_header = slab->header_at( i );
		slab_header->magic = SmallMemoryHeader::MAGIC;
		slab_header->bucket_index = static_cast<std::uint32_t>( bucket_index );
		slab_header->block_size = static_cast<std::uint32_t>( bucket_bytes );
		slab_header->is_free.store( true, std::memory_order_relaxed );
		slab_header->next = nullptr;
		slab_header->in_tls = 0;
		slab_header->parent_slab = slab;  // 以 void* 形式保存
		slab_header->slot_index = i;
	}
	return slab;
}

inline bool 
/**
 * Attempt to mark a slot as acquired by setting its bit in the slab bitmap.
 * 通过在 slab 位图中设置相应位，尝试将槽位标记为已占用。
 */
SmallMemoryManager::try_mark_slot_acquired( SmallSlab* slab, std::uint32_t idx )
{
	const std::uint64_t bit = ( 1ull << idx );
	for ( ;; )
	{
		std::uint64_t old = slab->bitmap.load( std::memory_order_acquire );
		if ( old & bit )
			return false;  // 已被占
		if ( slab->bitmap.compare_exchange_weak( old, old | bit, std::memory_order_acq_rel, std::memory_order_acquire ) )
		{
			slab->used.fetch_add( 1, std::memory_order_acq_rel );
			return true;
		}
	}
}

inline bool 
/**
 * Attempt to mark a slot as released by clearing its bit in the slab bitmap.
 * 通过清除 slab 位图中的相应位，尝试将槽位标记为已释放。
 */
SmallMemoryManager::try_mark_slot_released( SmallSlab* slab, std::uint32_t idx )
{
	const std::uint64_t bit = ( 1ull << idx );
	for ( ;; )
	{
		std::uint64_t old = slab->bitmap.load( std::memory_order_acquire );
		if ( ( old & bit ) == 0 )
			return false;  // 已是空
		if ( slab->bitmap.compare_exchange_weak( old, old & ~bit, std::memory_order_acq_rel, std::memory_order_acquire ) )
		{
			slab->used.fetch_sub( 1, std::memory_order_acq_rel );
			return true;
		}
	}
}

/* -------- allocate -------- */

/**
 * Allocate a small block via thread‑local cache first, then global bucket, or create a new slab.
 * 优先通过线程局部缓存分配小块；若失败则访问全局桶，必要时创建新的 slab。
 */
void* SmallMemoryManager::allocate( std::size_t bytes, std::size_t alignment )
{
	const std::size_t index = calculate_bucket_index( bytes );
	const std::size_t bucket_bytes = BUCKET_SIZES[ index ];

	// 1) 线程本地缓存
	if ( auto* header = thread_local_cache.buckets[ index ] )
	{
		thread_local_cache.buckets[ index ] = header->next;
		// 位图置位（从 0 -> 1）
		if ( header->parent_slab )
		{
			auto* slab = reinterpret_cast<SmallSlab*>( header->parent_slab );
			( void )try_mark_slot_acquired( slab, header->slot_index );	 // Treiber 已防重，失败也无害
		}
		header->is_free.store( false, std::memory_order_relaxed );
		header->magic = SmallMemoryHeader::MAGIC;
		header->in_tls = 0;
		return header->data();
	}

	// 2) 全局桶
	GlobalBucket& bucket = global_buckets[ index ];
#if SUPPORT_128BIT_CAS
	PointerTag old_head = bucket.head.load( std::memory_order_acquire );
	while ( old_head.pointer )
	{
		SmallMemoryHeader* candidate = old_head.pointer;
		PointerTag		   new_head { candidate->next, old_head.tag + 1 };
		if ( bucket.head.compare_exchange_weak( old_head, new_head, std::memory_order_acq_rel, std::memory_order_acquire ) )
		{
			if ( candidate->parent_slab )
			{
				auto* slab = reinterpret_cast<SmallSlab*>( candidate->parent_slab );
				( void )try_mark_slot_acquired( slab, candidate->slot_index );
			}
			candidate->is_free.store( false, std::memory_order_relaxed );
			candidate->magic = SmallMemoryHeader::MAGIC;
			return candidate->data();
		}
	}
#else
	{
		std::lock_guard<std::mutex> lock( bucket.mutex );
		SmallMemoryHeader*			header = bucket.head.load( std::memory_order_relaxed );
		if ( header )
		{
			bucket.head.store( header->next, std::memory_order_relaxed );
			if ( header->parent_slab )
			{
				auto* slab = reinterpret_cast<SmallSlab*>( header->parent_slab );
				( void )try_mark_slot_acquired( slab, header->slot_index );
			}
			header->is_free.store( false, std::memory_order_relaxed );
			header->magic = SmallMemoryHeader::MAGIC;
			return header->data();
		}
	}
#endif

	// 3) 申请新 slab，并将其槽位（除首个）批量推入全局链
	SmallSlab* slab = make_new_slab( index, bucket_bytes, alignment );

	SmallMemoryHeader* first = nullptr;
	SmallMemoryHeader* previous = nullptr;
	for ( std::uint32_t i = 0; i < slab->capacity; ++i )
	{
		SmallMemoryHeader* slab_header = slab->header_at( i );
		if ( first == nullptr )
			first = slab_header;
		else
			previous->next = slab_header;
		previous = slab_header;
		if (slab_header != nullptr)
		{  
		   slab_header->next = nullptr;
		}
	}

	if(first == nullptr)
	{
		return nullptr;
	}

	// 将 [first->next ... tail] 批量挂到全局桶头
	if ( slab->capacity > 1 )
	{
		SmallMemoryHeader* local_head = first->next;  // 其余所有空块
		SmallMemoryHeader* tail = local_head;
		while ( tail && tail->next )
			tail = tail->next;
#if SUPPORT_128BIT_CAS
		PointerTag head_snapshot = bucket.head.load( std::memory_order_relaxed );
		do
		{
			if (tail != nullptr)  
            {  
               tail->next = head_snapshot.pointer;  
            }
		} while ( !bucket.head.compare_exchange_weak( head_snapshot, { local_head, head_snapshot.tag + 1 }, std::memory_order_release, std::memory_order_relaxed ) );
#else
		{
			std::lock_guard<std::mutex> lock( bucket.mutex );
			if ( tail )
				tail->next = bucket.head.load( std::memory_order_relaxed );
			bucket.head.store( local_head, std::memory_order_relaxed );
		}
#endif
		first->next = nullptr;	// 与批量挂接断开
	}

	// 立刻占用 first 对应槽位
	( void )try_mark_slot_acquired( slab, first->slot_index );
	first->is_free.store( false, std::memory_order_relaxed );
	first->magic = SmallMemoryHeader::MAGIC;
	return first->data();

}

/* -------- deallocate -------- */

/**
 * Recycle a small block into the thread‑local cache and update slab accounting.
 * 将小块回收到线程局部缓存，并更新 slab 统计信息。
 */
void SmallMemoryManager::deallocate( SmallMemoryHeader* header )
{
	bool expected = false;
	if ( !header->is_free.compare_exchange_strong( expected, true, std::memory_order_release, std::memory_order_relaxed ) )
		return;	 // 双重释放

	if ( header->in_tls )
		return;	 // 已经在 TLS 链上

	if ( header->magic != SmallMemoryHeader::MAGIC )
	{
		std::cerr << "[Small] invalid magic during deallocation\n";
		return;
	}
	header->magic = 0;	 // 防复用
	header->in_tls = 1;	 // 进入 TLS

	// 位图清位
	if ( header->parent_slab )
	{
		auto* slab = reinterpret_cast<SmallSlab*>( header->parent_slab );
		( void )try_mark_slot_released( slab, header->slot_index );
	}

	const std::size_t index = header->bucket_index;
	header->next = thread_local_cache.buckets[ index ];
	thread_local_cache.buckets[ index ] = header;

	if ( ++thread_local_cache.deallocation_counter >= 256 )
		flush_thread_local_cache();
}

/* -------- flush TLS（保持旧行为） -------- */

/**
 * Flush thread‑local cache into global buckets; clear the in‑thread flag for all entries.
 * 将线程局部缓存批量刷新到全局桶；同时清除所有条目的线程内标记。
 */
void SmallMemoryManager::flush_thread_local_cache()
{
	for ( std::size_t i = 0; i < BUCKET_COUNT; ++i )
	{
		SmallMemoryHeader* local_head = std::exchange( thread_local_cache.buckets[ i ], nullptr );
		if ( !local_head )
			continue;

		GlobalBucket& bucket = global_buckets[ i ];
		// 找尾
		SmallMemoryHeader* tail = local_head;
		while ( tail->next )
			tail = tail->next;

#if SUPPORT_128BIT_CAS
		using PT = PointerTag;
		PT head_snapshot = bucket.head.load( std::memory_order_relaxed );
		do
		{
			tail->next = head_snapshot.pointer;
		} while ( !bucket.head.compare_exchange_weak( head_snapshot, { local_head, head_snapshot.tag + 1 }, std::memory_order_release, std::memory_order_relaxed ) );
#else
		{
			std::lock_guard<std::mutex> lock( bucket.mutex );
			tail->next = bucket.head.load( std::memory_order_relaxed );
			bucket.head.store( local_head, std::memory_order_relaxed );
		}
#endif
		// 清 in_tls 标记
		for ( SmallMemoryHeader* p = local_head; p; p = p->next )
			p->in_tls = 0;
	}
}

/* -------- release_resources -------- */

/**
 * Release all global buckets and return every slab to the operating system.
 * 清空所有全局桶并将所有 slab 归还给操作系统。
 */
void SmallMemoryManager::release_resources()
{
	// 把全局桶头清零（不必逐个弹出）
	for ( auto& b : global_buckets )
	{
#if SUPPORT_128BIT_CAS
		b.head.store( { nullptr, 0 }, std::memory_order_relaxed );
#else
		b.head.store( nullptr, std::memory_order_relaxed );
#endif
	}

	// 释放所有 slab
	std::lock_guard<std::mutex> lk( chunk_mutex );
	for ( auto& kv : allocated_chunks )
		os_memory::deallocate_tracked( kv.first, kv.second );
	allocated_chunks.clear();
}

/* =====================================================================
 *  MediumMemoryManager — 实现
 * ===================================================================== */

/*──────────────── allocate ────────────────*/

/**
 * Attempt buddy allocation from the requested order upward; lazily split and prepare block.
 * 从所需级别向上尝试伙伴分配；按需拆分并初始化要返回的块。
 */
void* MediumMemoryManager::allocate( std::size_t bytes, std::size_t alignment = sizeof( std::max_align_t ) )
{
	const int want_order = order_from_size( bytes );  // 获取所需的内存块级别 / Get the required block level

	// 边界检查：确保请求的order在有效范围内
	if ( want_order < 0 || want_order >= LEVEL_COUNT )
	{
		throw std::bad_alloc();
	}

	/* 第一阶段：常规分配尝试 */
	for ( int current_order = want_order; current_order < LEVEL_COUNT; ++current_order )
	{
		if ( auto* block = pop_block( current_order ) )
		{
			if ( current_order > want_order )
			{
				block = split_to_order( block, current_order, want_order );
			}
			prepare_block( block, want_order );
			return block->data();
		}
	}

	/* 第二阶段：申请新chunk */
	auto* fresh = request_new_chunk( want_order, alignment );
	if ( !fresh )
		throw std::bad_alloc();

	// 占用检测：统计非空级别数量
	size_t occupied_levels = 0;
	for ( int i = 0; i < LEVEL_COUNT; i++ )
	{
		if ( free_lists[ i ].head.load( std::memory_order_acquire ).pointer )
		{
			occupied_levels++;
		}
	}

	const uint16_t mask = free_list_level_mask.load( std::memory_order_acquire );

	// 策略选择
	if ( mask != 0 )
	{
		/* 情况1：系统中有可用块 - 资源回收优先 */
		push_block( fresh, want_order );  // 将新块加入资源池

		// 重新尝试分配，利用可能的新资源
		for ( int current_order = want_order; current_order < LEVEL_COUNT; ++current_order )
		{
			if ( auto* block = pop_block( current_order ) )
			{
				if ( current_order > want_order )
				{
					block = split_to_order( block, current_order, want_order );
				}
				prepare_block( block, want_order );
				return block->data();
			}
		}
	}
	else
	{
		/* 情况2：系统完全干涸 - 直接使用新资源 */
		if ( want_order < LEVEL_COUNT - 1 )
		{
			// 仅当需要时才分割
			fresh = split_to_order( fresh, want_order, want_order );
		}
		prepare_block( fresh, want_order );
		return fresh->data();
	}

	// 终极保障
	throw std::bad_alloc();
}

/*──────────────── deallocate ────────────────*/

/**
 * Validate header and enqueue a merge request; a background worker coalesces buddies.
 * 校验头部后将合并请求入队；后台线程负责合并伙伴块。
 */
void MediumMemoryManager::deallocate( MediumMemoryHeader* header )
{
	/* 确保不是重复释放 / Ensure no double free */
	bool expected = false;
	if ( !header->is_free.compare_exchange_strong( expected, true, std::memory_order_acq_rel, std::memory_order_relaxed ) )
	{
		return;	 // 如果已经释放过，直接返回 / Return if already freed
	}

	/* 校验魔法 / Validate magic value */
	if ( header->magic != MediumMemoryHeader::MAGIC )
	{
		std::cerr << "[MediumBuddy] invalid magic during deallocation\n";  // 魔法值无效 / Invalid magic value
		return;
	}

	// 创建合并请求 / Create merge request
	const int order = order_from_size( header->block_size );

	// 无锁入队 - 环形缓冲区实现 / Lock-free enqueue - Circular buffer implementation
	std::size_t cycle_queue_tail = merge_queue.tail.load( std::memory_order_relaxed );
	std::size_t cycle_queue_next_tail = ( cycle_queue_tail + 1 ) % MERGE_QUEUE_SIZE;

	// 检查队列是否满 / Check if the queue is full
	if ( cycle_queue_next_tail == merge_queue.head.load( std::memory_order_acquire ) )
	{
		// 队列满时直接尝试合并（安全，因为此时只有当前线程操作）/ If the queue is full, attempt merging directly (safe because only the current thread is operating)
		try_merge_buddy( header, order );
		return;
	}

	// 加入队列 / Add to queue
	merge_queue.requests[ cycle_queue_tail ].store( { header, order }, std::memory_order_relaxed );
	merge_queue.tail.store( cycle_queue_next_tail, std::memory_order_release );

	// 确保合并工作线程运行 / Ensure the merge worker thread runs
	if ( !merge_worker_active.load( std::memory_order_acquire ) && !merge_worker_active.exchange( true, std::memory_order_acq_rel ) )
	{
		std::thread( [ this ] { process_merge_queue(); } ).detach();  // 启动合并线程 / Start the merge thread
	}
}

/*──────────────── 内部工具实现 ────────────────*/
inline void MediumMemoryManager::prepare_block( MediumMemoryHeader* block, int order )
{
	block->is_free.store( false, std::memory_order_relaxed );
	block->magic = MediumMemoryHeader::MAGIC;
	block->block_size = size_from_order( order );
	block->next = nullptr;
}

void MediumMemoryManager::push_block( MediumMemoryHeader* header, int order )
{
	header->next = nullptr;
	header->is_free.store( true, std::memory_order_relaxed );  // 标记为可用 / Mark as free

	auto&	   list = free_lists[ order ];	// 获取空闲链表 / Get free list for the order
	PointerTag head = list.head.load( std::memory_order_relaxed );

	do
	{
		header->next = head.pointer;  // 将当前块链接到链表头 / Link the current block to the list head
		PointerTag new_head { header, head.tag + 1 };
	} while ( !list.head.compare_exchange_weak( head, { header, head.tag + 1 }, std::memory_order_release, std::memory_order_relaxed ) );

	// 原子更新位掩码
	uint16_t current_mask = free_list_level_mask.load( std::memory_order_relaxed );
	uint16_t new_mask;
	do
	{
		new_mask = current_mask | ( 1 << order );  // 设置该级别位
	} while ( !free_list_level_mask.compare_exchange_weak( current_mask, new_mask, std::memory_order_release, std::memory_order_relaxed ) );
}

MediumMemoryHeader* MediumMemoryManager::pop_block( int order )
{
	auto&	   list = free_lists[ order ];	// 获取空闲链表 / Get free list for the order
	PointerTag head = list.head.load( std::memory_order_acquire );

	while ( head.pointer )
	{
		PointerTag next { head.pointer->next, head.tag + 1 };

		//Try CompreAndSwap
		if ( list.head.compare_exchange_weak( head, next, std::memory_order_acq_rel, std::memory_order_acquire ) )
		{
			// 成功取出一个块，检查取出后链表是否为空
			if ( next.pointer == nullptr )
			{
				// 链表变空，清除掩码位
				uint16_t current_mask = free_list_level_mask.load( std::memory_order_relaxed );
				uint16_t new_mask;
				do
				{
					new_mask = current_mask & ~( 1 << order );
				} while ( !free_list_level_mask.compare_exchange_weak( current_mask, new_mask, std::memory_order_release, std::memory_order_relaxed ) );
			}
			return head.pointer;
		}
		// CompreAndSwap Failed, Retry
	}

	// 链表已经为空，确保掩码位被清除
	uint16_t current_mask = free_list_level_mask.load( std::memory_order_relaxed );
	uint16_t new_mask;
	do
	{
		new_mask = current_mask & ~( 1 << order );
	} while ( !free_list_level_mask.compare_exchange_weak( current_mask, new_mask, std::memory_order_release, std::memory_order_relaxed ) );

	return nullptr;
}

/*──────────────── process_merge_queue ────────────────*/

/**
 * Background worker that drains the circular queue and performs buddy merges.
 * 后台工作线程：处理环形队列中的请求并执行伙伴合并。
 */
void MediumMemoryManager::process_merge_queue()
{
	while ( true )
	{
		std::size_t cycle_queue_head = merge_queue.head.load( std::memory_order_relaxed );	// 获取队列头 / Get the queue head
		std::size_t cycle_queue_tail = merge_queue.tail.load( std::memory_order_acquire );	// 获取队列尾 / Get the queue tail

		// 队列为空 / If the queue is empty
		if ( cycle_queue_head == cycle_queue_tail )
		{
			// 设置非活跃状态前做最后检查 / Final check before setting inactive state
			if ( merge_queue.head.load( std::memory_order_acquire ) == merge_queue.tail.load( std::memory_order_acquire ) )
			{
				merge_worker_active.store( false, std::memory_order_release );	// 设置工作线程非活跃 / Set the worker thread inactive
				return;
			}
			continue;  // 继续循环 / Continue looping
		}

		// 取出请求 / Retrieve the request
		MergeRequest request = merge_queue.requests[ cycle_queue_head ].load( std::memory_order_relaxed );

		// 移动头指针 / Move the head pointer
		std::size_t cycle_queue_next_head = ( cycle_queue_head + 1 ) % MERGE_QUEUE_SIZE;
		merge_queue.head.store( cycle_queue_next_head, std::memory_order_release );

		// 处理合并 / Process the merge
		try_merge_buddy( request.block, request.order );
	}
}

/*──────────────── try_merge_buddy ────────────────*/

/**
 * Try to merge the given block with its buddy repeatedly until no larger merge is possible.
 * 尝试将给定块与其伙伴连续合并，直到无法进一步合并为止。
 */
void MediumMemoryManager::try_merge_buddy( MediumMemoryHeader* block, int order )
{
	// 查找chunk的逻辑（与原始merge_buddy相同）/ Logic for finding the chunk (same as original merge_buddy)
	void*		chunk_base = nullptr;
	std::size_t chunk_bytes = 0;
	for ( auto const& chunk : allocated_chunks )
	{
		char* base = static_cast<char*>( chunk.first );
		if ( reinterpret_cast<char*>( block ) >= base && reinterpret_cast<char*>( block ) < base + chunk.second )
		{
			chunk_base = base;
			chunk_bytes = chunk.second;
			break;
		}
	}
	if ( !chunk_base )
		return;

	/* 尝试合并伙伴 / Try to merge buddy */
	while ( order < LEVEL_COUNT - 1 )
	{
		// 计算当前块在chunk中的偏移量 / Calculate block's offset within the chunk
		std::uintptr_t offset = reinterpret_cast<char*>( block ) - static_cast<char*>( chunk_base );

		// 使用XOR计算伙伴块的偏移量 / Calculate buddy's offset using XOR trick
		std::uintptr_t buddy_offset = offset ^ ( size_from_order( order ) );

		// 检查伙伴块是否超出chunk边界 / Check if buddy exceeds chunk boundary
		if ( buddy_offset + size_from_order( order ) > chunk_bytes )
			break;	// buddy 超出 chunk / Buddy exceeds chunk size

		// 获取伙伴块头部指针 / Get buddy block header pointer
		auto* buddy = reinterpret_cast<MediumMemoryHeader*>( static_cast<char*>( chunk_base ) + buddy_offset );

		// 使用原子操作检查buddy状态 / Use atomic operation to check buddy state
		if ( !buddy->is_free.load( std::memory_order_acquire ) || buddy->block_size != size_from_order( order ) )
		{
			break;
		}

		/* 尝试原子性地移除buddy / Try to atomically remove buddy */
		if ( !try_remove_from_freelist( buddy, order ) )
		{
			break;
		}

		/* 再次确认buddy状态 / Recheck buddy state */
		if ( !buddy->is_free.load( std::memory_order_acquire ) || buddy->block_size != size_from_order( order ) )
		{
			// 放回freelist / Put back to freelist
			push_block( buddy, order );
			break;
		}

		/* 合并 - 取较小地址为新块首 / Merge - take the smaller address as the new block's start */
		block = ( offset < buddy_offset ) ? block : buddy;
		block->block_size = size_from_order( order ) << 1;	// 合并后的块大小 / Merged block size
		order++;
	}

	// 将合并后的块放回空闲列表 / Push the merged block back to the free list
	push_block( block, order );
}

/*──────────────── try_remove_from_freelist ────────────────*/

/**
 * Try to atomically remove a block from the free list; uses tag updates to avoid ABA.
 * 尝试以原子方式从空闲链表中移除块；通过更新标签避免 ABA 问题。
 */
bool MediumMemoryManager::try_remove_from_freelist( MediumMemoryHeader* header, int order )
{
	auto&	   list = free_lists[ order ];	// 获取对应级别的空闲链表 / Get the corresponding free list for the order
	PointerTag head = list.head.load( std::memory_order_acquire );

	while ( true )
	{
		if ( head.pointer == header )
		{
			// =====================================================
			// 场景1: 目标块是链表头节点 / Scenario 1: Target is the head
			// =====================================================

			PointerTag next { header->next, head.tag + 1 };

			// 尝试原子性地替换链表头 / Attempt atomic head replacement
			/*
			 * 使用CAS解决ABA问题：
			 * - 比较当前head和之前加载的head
			 * - 如果相同，替换为new_head
			 * - 如果不同，重试
			 * 
			 * CAS solves ABA problem:
			 * - Compare current head with previously loaded head
			 * - If same, replace with new_head
			 * - If different, retry
			 */
			if ( list.head.compare_exchange_weak( head, { header, head.tag + 1 }, std::memory_order_acq_rel, std::memory_order_acquire ) )
			{
				return true;  // 成功移除 / Successfully removed
			}
		}
		else
		{
			// =====================================================
			// 场景2: 目标块在链表中间 / Scenario 2: Target is in list middle
			// =====================================================

			// 遍历链表查找 / Traverse the list to find
			MediumMemoryHeader* current = head.pointer;
			while ( current )
			{
				if ( current == header )
				{
					PointerTag new_head { head.pointer, head.tag + 1 };

					// 尝试原子性地更新链表头 / Attempt atomic head update
					/*
					 * 为什么更新链表头？ 
					 * 在无锁链表中，中间节点移除非常复杂。这里使用简化策略：
					 * 通过修改链表头标签强制其他线程重试，间接使目标块"失效"
					 * 
					 * Why update list head?
					 * Removing middle nodes in lock-free lists is complex.
					 * Simplified strategy: Force other threads to retry by
					 * changing head tag, indirectly "invalidating" target
					 */
					if ( list.head.compare_exchange_weak( head, new_head, std::memory_order_acq_rel, std::memory_order_acquire ) )
					{
						return true;  // 成功移除 / Successfully removed
					}
					break;
				}
				current = current->next;
			}
			return false;  // 没找到 / Not found
		}
	}
}


/**
 * Split a larger block down to the target order; push the right halves to free lists.
 * 将较大块拆分为目标级别；将右侧一半推入相应空闲链表。
 */
MediumMemoryHeader* MediumMemoryManager::split_to_order( MediumMemoryHeader* block, int from_order, int to_order )
{
	// 确保目标order在有效范围内
	if ( to_order < 0 || to_order >= LEVEL_COUNT || to_order > from_order )
	{
		return block;
	}

	for ( int current_order = from_order - 1; current_order >= to_order; --current_order )
	{
		std::size_t half = size_from_order( current_order );				  // 计算每个块的一半 / Calculate half of the block size
		char*		right_pointer = reinterpret_cast<char*>( block ) + half;  // 获取右侧块的位置 / Get the position of the right block

		auto* right_header = reinterpret_cast<MediumMemoryHeader*>( right_pointer );  // 获取右侧块的头部 / Get the header of the right block
		right_header->block_size = half;											  // 设置右侧块的大小 / Set the size of the right block
		right_header->is_free.store( true, std::memory_order_relaxed );				  // 标记为可用 / Mark as free
		right_header->magic = MediumMemoryHeader::MAGIC;							  // 设置魔法值 / Set magic value
		right_header->next = nullptr;												  // 设置下一块为空 / Set next to null

		push_block( right_header, current_order );	// 将右侧块推入空闲链表 / Push the right block into the free list
		block->block_size = half;					// 更新原块的大小 / Update the original block's size
	}
	return block;  // 返回原块 / Return the original block
}


/**
 * Request a fresh chunk from the operating system and return its header.
 * 向操作系统申请新的内存块并返回其头部。
 */
MediumMemoryHeader* MediumMemoryManager::request_new_chunk( int min_order, std::size_t alignment = sizeof( std::max_align_t ) )
{
	std::lock_guard<std::mutex> this_lock_guard( chunk_mutex );	 // 加锁保护 / Lock protection

	// 计算需要的内存块大小 / Calculate the required chunk size
	const std::size_t chunk_bytes = size_from_order( min_order );							 // 使用 min_order 来计算内存块大小 / Use min_order to calculate the chunk size
	void*			  chunk_memory = os_memory::allocate_tracked( chunk_bytes, alignment );	 // 向操作系统请求内存 / Request memory from the OS
	if ( !chunk_memory )
		return nullptr;	 // 申请失败，返回空指针 / Return null if allocation fails

	allocated_chunks.emplace_back( chunk_memory, chunk_bytes );	 // 记录已分配的 chunk / Record the allocated chunk

	// 整个 chunk 作为一个大块先放进最高层，再让 allocate 重新拿 / Place the entire chunk into the highest level first, then let allocate reuse it
	auto* header = static_cast<MediumMemoryHeader*>( chunk_memory );
	header->block_size = chunk_bytes;						   // 设置块大小 / Set the chunk size
	header->is_free.store( true, std::memory_order_relaxed );  // 标记为可用 / Mark as free
	header->magic = MediumMemoryHeader::MAGIC;				   // 设置魔法值 / Set magic value
	header->next = nullptr;									   // 设置下一块为空 / Set next to null

	return header;
}

/*──────────────── release_resources ────────────────*/

/**
 * Clear all free lists and free every recorded chunk.
 * 清空所有空闲链表并释放所有记录的内存块。
 */
void MediumMemoryManager::release_resources()
{
	/* 清空 freelist / Clear the freelist */
	for ( auto& free_list : free_lists )
	{
		free_list.head.store( { nullptr, 0 }, std::memory_order_relaxed );	// 设置空头指针 / Set head pointer to null
	}

	for ( auto& [ pointer, size ] : allocated_chunks )
		os_memory::deallocate_tracked( pointer, size );	 // 释放内存 / Deallocate memory
	allocated_chunks.clear();							 // 清空已分配块 / Clear the allocated chunks
}

/* =====================================================================
 *  LargeMemoryManager — 实现
 * ===================================================================== */


/**
 * Allocate a large block with tracking for leak detection and return the data pointer.
 * 分配一个可追踪的大块以便于泄漏检测，并返回数据指针。
 */
void* LargeMemoryManager::allocate( std::size_t bytes, std::size_t alignment = sizeof( std::max_align_t ) )
{
	const std::size_t total = sizeof( LargeMemoryHeader ) + bytes;				 // 计算总内存大小 / Calculate total memory size
	void*			  memory = os_memory::allocate_tracked( total, alignment );	 // 向操作系统申请内存 / Request memory from the OS
	if ( !memory )
		throw std::bad_alloc();	 // 如果申请失败，抛出异常 / Throw exception if allocation fails

	auto* header = static_cast<LargeMemoryHeader*>( memory );  // 获取内存头部 / Get the memory header
	header->magic = LargeMemoryHeader::MAGIC;				   // 设置魔法值 / Set magic value
	header->block_size = bytes;								   // 设置块大小 / Set block size

	std::lock_guard<std::mutex> this_lock_guard( tracking_mutex );	// 加锁保护 / Lock protection
	active_blocks.push_back( header );								// 记录已分配的块 / Record the allocated block

	return header->data();	// 返回数据指针 / Return data pointer
}


/**
 * Validate and remove a large block from the active set, then free the memory.
 * 校验并从活动集合中移除该大块，随后释放内存。
 */
void LargeMemoryManager::deallocate( LargeMemoryHeader* header )
{
	if ( header->magic != LargeMemoryHeader::MAGIC )
	{
		std::cerr << "[Large] invalid magic during deallocation\n";	 // 魔法值无效 / Invalid magic value
		return;
	}
	header->magic = 0;	// 清除魔法值 / Clear magic value

	{
		std::lock_guard<std::mutex> this_lock_guard( tracking_mutex );										 // 加锁保护 / Lock protection
		auto						iter = std::find( active_blocks.begin(), active_blocks.end(), header );	 // 查找并删除已释放块 / Find and remove the deallocated block
		if ( iter != active_blocks.end() )
			active_blocks.erase( iter );  // 删除已释放块 / Remove the deallocated block
	}

	os_memory::deallocate_tracked( header, sizeof( LargeMemoryHeader ) + header->block_size );	// 释放内存 / Deallocate memory
}


/**
 * Free all active large blocks and clear the internal tracking list.
 * 释放所有活动的大块并清理内部跟踪列表。
 */
void LargeMemoryManager::release_resources()
{
	{
		std::scoped_lock<std::mutex> lock( tracking_mutex );
		for ( auto* header : active_blocks )
			os_memory::deallocate_tracked( header, sizeof( LargeMemoryHeader ) + header->block_size );	// 释放所有已分配的内存 / Deallocate all allocated memory
		active_blocks.clear();																			// 清空已分配块 / Clear the allocated blocks
	}
}

/* =====================================================================
 *  HugeMemoryManager — 实现
 * ===================================================================== */


/**
 * Allocate a very large block directly from the operating system and record it.
 * 直接向操作系统申请超大块并进行记录。
 */
void* HugeMemoryManager::allocate( std::size_t bytes, std::size_t alignment = sizeof( std::max_align_t ) )
{
	const std::size_t total = sizeof( HugeMemoryHeader ) + bytes;				 // 计算总内存大小 / Calculate total memory size
	void*			  memory = os_memory::allocate_tracked( total, alignment );	 // 向操作系统申请内存 / Request memory from the OS
	if ( !memory )
		throw std::bad_alloc();	 // 如果申请失败，抛出异常 / Throw exception if allocation fails

	auto* header = static_cast<HugeMemoryHeader*>( memory );  // 获取内存头部 / Get the memory header
	header->magic = HugeMemoryHeader::MAGIC;				  // 设置魔法值 / Set magic value
	header->block_size = bytes;								  // 设置块大小 / Set block size

	std::lock_guard<std::mutex> this_lock_guard( tracking_mutex );	// 加锁保护 / Lock protection
	active_blocks.emplace_back( memory, total );					// 记录已分配的块 / Record the allocated block

	return header->data();	// 返回数据指针 / Return data pointer
}


/**
 * Validate and free a very large block; remove it from the active list if present.
 * 校验并释放超大块；若存在于活动列表中则将其移除。
 */
void HugeMemoryManager::deallocate( HugeMemoryHeader* header )
{
	if ( header->magic != HugeMemoryHeader::MAGIC )
	{
		std::cerr << "[Huge] invalid magic during deallocation\n";	// 魔法值无效 / Invalid magic value
		return;
	}
	header->magic = 0;	// 清除魔法值 / Clear magic value

	{
		std::lock_guard<std::mutex> this_lock_guard( tracking_mutex );																													   // 加锁保护 / Lock protection
		auto						iter = std::find_if( active_blocks.begin(), active_blocks.end(), [ header ]( auto& reference_object ) { return reference_object.first == header; } );  // 查找并删除已释放块 / Find and remove the deallocated block
		if ( iter != active_blocks.end() )
		{
			os_memory::deallocate_tracked( iter->first, iter->second );	 // 释放内存 / Deallocate memory
			active_blocks.erase( iter );								 // 删除已释放块 / Remove the deallocated block
			return;
		}
	}

	os_memory::deallocate_tracked( header, sizeof( HugeMemoryHeader ) + header->block_size );  // 释放内存 / Deallocate memory
}


/**
 * Free all recorded huge blocks and clear the list.
 * 释放所有记录的超大块并清空列表。
 */
void HugeMemoryManager::release_resources()
{
	{
		std::scoped_lock<std::mutex> lock( tracking_mutex );
		for ( auto& [ pointer, size ] : active_blocks )
			os_memory::deallocate_tracked( pointer, size );	 // 释放所有已分配的内存 / Deallocate all allocated memory
		active_blocks.clear();								 // 清空已分配块 / Clear the allocated blocks
	}
}

/* =====================================================================
 *  MemoryPool 实现
 * ===================================================================== */


/**
 * Initialize global bucket heads and print a one‑time construction warning.
 * 初始化全局桶的栈头，并输出一次性构造警告。
 */
MemoryPool::MemoryPool()
{
	// 初始化 Small: Treiber 栈头
#if SUPPORT_128BIT_CAS
	for ( auto& b : small_manager.global_buckets )
		b.head.store( { nullptr, 0 }, std::memory_order_relaxed );
#else
	for ( auto& b : small_manager.global_buckets )
	{
		b.head.store( nullptr, std::memory_order_relaxed );
	}
#endif

	if ( !construction_warning_shown.exchange( true, std::memory_order_relaxed ) )
	{
		std::cerr << "\033[33m[MemoryPool Warning] 直接使用 MemoryPool 仅适合内部场景，生产代码请封装成 PoolAllocator！\033[0m\n";
	}
}


/**
 * Flush thread caches, release all sub‑managers, and print leak statistics if this is the last pool.
 * 刷新线程缓存，释放所有子管理器；若为最后一个池实例，则输出泄漏统计。
 */
MemoryPool::~MemoryPool()
{
	is_destructing.store( true, std::memory_order_release );
	flush_current_thread_cache();

	huge_manager.release_resources();
	large_manager.release_resources();
	medium_manager.release_resources();
	small_manager.release_resources();

	if ( live_pools.fetch_sub( 1, std::memory_order_acq_rel ) == 1 )
	{
		const auto leaked = os_memory::used_memory_bytes_counter.load( std::memory_order_seq_cst );
		if ( leaked != 0 )
			std::cerr << "[MemoryPool] Memory leak detected: " << leaked << " bytes still allocated.\n";
		const auto operation_imbalance = os_memory::user_operation_counter.load( std::memory_order_seq_cst );
		if ( operation_imbalance != 0 )
			std::cerr << "[MemoryPool] Operation imbalance detected: " << operation_imbalance << " net operations.\n";
	}
}


/**
 * Route the allocation by size class. For non‑default alignment, embed an alignment header.
 * 按大小类别路由分配；对于非常规定的对齐，在返回指针前嵌入对齐头部。
 */
void* MemoryPool::allocate( std::size_t requested_bytes, std::size_t requested_alignment, const char* file, std::uint32_t line, bool nothrow )
{
	/* ── 1. alignment validation ───────────────────────────── */
	if ( ( requested_alignment & 1 ) == 1 || !os_memory::memory_pool::is_power_of_two( requested_alignment ) )
	{
		if ( requested_alignment > MAX_ALLOWED_ALIGNMENT && !nothrow )
			throw std::bad_alloc();	 //!< illegal alignment

		if ( requested_alignment > 0 )
		{
			requested_alignment = DEFAULT_ALIGNMENT;
		}
	}

	/* ── 2. slow path : large alignment ────────────────────── */
	if ( requested_alignment > DEFAULT_ALIGNMENT )
	{
		const std::size_t extra_alignment_padding_bytes = requested_alignment - 1 + ALIGN_HEADER_BYTES;
		const std::size_t total_allocated_bytes = requested_bytes + extra_alignment_padding_bytes;

		void* const raw_block_pointer = os_memory::allocate_tracked( total_allocated_bytes, requested_bytes );
		if ( !raw_block_pointer )
		{
			if ( !nothrow )
				throw std::bad_alloc();
			return nullptr;
		}

		char*		data_region_begin = static_cast<char*>( raw_block_pointer ) + ALIGN_HEADER_BYTES;
		std::size_t remaining_space_bytes = total_allocated_bytes - ALIGN_HEADER_BYTES;
		void*		aligned_user_pointer = data_region_begin;

		if ( !std::align( requested_alignment, requested_bytes, aligned_user_pointer, remaining_space_bytes ) )
		{
			os_memory::deallocate_tracked( raw_block_pointer, total_allocated_bytes );
			if ( !nothrow )
				throw std::bad_alloc();
			return nullptr;
		}

		auto* align_header_pointer = reinterpret_cast<AlignHeader*>( static_cast<char*>( aligned_user_pointer ) - ALIGN_HEADER_BYTES );
		align_header_pointer->tag = ALIGN_SENTINEL;
		align_header_pointer->raw = raw_block_pointer;
		align_header_pointer->size = total_allocated_bytes;
		return aligned_user_pointer;
	}

	/* ── 3. fast path : default alignment ──────────────────── */
	const std::size_t total_bytes_including_header = requested_bytes + NOT_ALIGN_HEADER_BYTES;

	std::size_t	  block_header_size_bytes = 0;
	std::uint32_t block_owner_type_identifier = 0;
	void*		  internal_data_region_pointer = nullptr;  // → points to data()

	if ( total_bytes_including_header <= SMALL_BLOCK_MAX_SIZE )
	{
		block_header_size_bytes = sizeof( SmallMemoryHeader );
		block_owner_type_identifier = 1;
		internal_data_region_pointer = small_manager.allocate( total_bytes_including_header, requested_alignment );
	}
	else if ( total_bytes_including_header <= MEDIUM_BLOCK_MAX_SIZE )
	{
		block_header_size_bytes = sizeof( MediumMemoryHeader );
		block_owner_type_identifier = 2;
		internal_data_region_pointer = medium_manager.allocate( total_bytes_including_header, requested_alignment );
	}
	else if ( total_bytes_including_header <= HUGE_BLOCK_THRESHOLD )
	{
		block_header_size_bytes = sizeof( LargeMemoryHeader );
		block_owner_type_identifier = 3;
		internal_data_region_pointer = large_manager.allocate( total_bytes_including_header, requested_alignment );
	}
	else
	{
		block_header_size_bytes = sizeof( HugeMemoryHeader );
		block_owner_type_identifier = 4;
		internal_data_region_pointer = huge_manager.allocate( total_bytes_including_header, requested_alignment );
	}

	if ( !internal_data_region_pointer )
	{
		if ( !nothrow )
			throw std::bad_alloc();
		return nullptr;
	}

	auto* unaligned_block_header = reinterpret_cast<NotAlignHeader*>( internal_data_region_pointer );
	unaligned_block_header->owner_type = block_owner_type_identifier;
	unaligned_block_header->raw = static_cast<char*>( internal_data_region_pointer ) - block_header_size_bytes;

	return static_cast<char*>( internal_data_region_pointer ) + NOT_ALIGN_HEADER_BYTES;
}

/* -------------------------------------------------------------------------- */


/**
 * Detect the header type (alignment or regular) and forward to the owning manager.
 * 识别头部类型（对齐型或常规型），并将释放请求转发至对应管理器。
 */
void MemoryPool::deallocate( void* user_pointer )
{
	if ( !user_pointer )
		return;

	const std::uintptr_t user_pointer_address = reinterpret_cast<std::uintptr_t>( user_pointer );

	/* ── 1. check large‑alignment header ───────────────────── */
	{
		auto* align_header_pointer = reinterpret_cast<const AlignHeader*>( user_pointer_address - ALIGN_HEADER_BYTES );

		AlignHeader stacked_copy_of_align_header {};
		std::memcpy( &stacked_copy_of_align_header, align_header_pointer, sizeof( stacked_copy_of_align_header ) );

		if ( stacked_copy_of_align_header.tag == ALIGN_SENTINEL )
		{
			os_memory::deallocate_tracked( stacked_copy_of_align_header.raw, stacked_copy_of_align_header.size );
			return;
		}
	}

	/* ── 2. check default‑alignment header ─────────────────── */
	{
		auto* unaligned_header_pointer = reinterpret_cast<const NotAlignHeader*>( user_pointer_address - NOT_ALIGN_HEADER_BYTES );

		NotAlignHeader stacked_copy_of_unaligned_header {};
		std::memcpy( &stacked_copy_of_unaligned_header, unaligned_header_pointer, sizeof( stacked_copy_of_unaligned_header ) );

		switch ( stacked_copy_of_unaligned_header.owner_type )
		{
		case 1:
			small_manager.deallocate( static_cast<SmallMemoryHeader*>( stacked_copy_of_unaligned_header.raw ) );
			return;
		case 2:
			medium_manager.deallocate( static_cast<MediumMemoryHeader*>( stacked_copy_of_unaligned_header.raw ) );
			return;
		case 3:
			large_manager.deallocate( static_cast<LargeMemoryHeader*>( stacked_copy_of_unaligned_header.raw ) );
			return;
		case 4:
			huge_manager.deallocate( static_cast<HugeMemoryHeader*>( stacked_copy_of_unaligned_header.raw ) );
			return;
		default:
#if defined( _DEBUG )
			throw os_memory::bad_dealloc( "deallocate: invalid owner type" );
#endif
		}
	}

#if defined( _DEBUG )
	throw os_memory::bad_dealloc( "deallocate: invalid pointer" );
#endif
}



/**
 * Flush small‑block thread‑local cache to the global buckets.
 * 将小块的线程局部缓存刷新到全局桶中。
 */
void MemoryPool::flush_current_thread_cache()
{
	small_manager.flush_thread_local_cache();  // 刷新线程本地缓存 / Flush thread-local cache
}