高并发内存池框架设计

// 计算对齐后的大小（向上取整到2的幂次）
static size_t align_to_power_of_two(size_t size) {
    if (size <= 0) return 8;  // 最小对齐粒度为8B（处理0的特殊情况）
    size_t aligned = 1;
    while (aligned < size) {
        aligned <<= 1;  // 左移1位（等价于×2），直到超过或等于原始大小
    }
    return aligned;
}

// 定义最大Size Class（示例为4KB，即2^12）
#define MAX_SIZE_CLASS 9  // 对应4KB（索引从0到9）

// 将对齐后的大小映射到Size Class索引
static int get_size_class_index(size_t aligned_size) {
    static const size_t size_classes[] = {8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096};
    for (int i = 0; i < MAX_SIZE_CLASS; i++) {
        if (aligned_size <= size_classes[i]) {
            return i;  // 找到第一个大于等于aligned_size的分类
        }
    }
    return MAX_SIZE_CLASS - 1;  // 理论上不会执行（因MAX_SIZE_CLASS对应4KB）
}

// 线程本地存储的ThreadCache实例
__thread ThreadCache* tls_thread_cache = NULL;

// 初始化线程本地ThreadCache
void init_thread_cache() {
    if (!tls_thread_cache) {
        tls_thread_cache = (ThreadCache*)malloc(sizeof(ThreadCache));
        // 初始化哈希桶数组、空闲链表等
        for (int i = 0; i < MAX_SIZE_CLASS; i++) {
            tls_thread_cache->buckets[i] = NULL;  // 初始化为空链表
        }
    }
}

// ThreadCache分配函数（无锁，结合哈希桶索引计算）
void* thread_cache_alloc(size_t size) {
    if (!tls_thread_cache || size == 0) return NULL;
    
    // 1. 计算哈希桶索引（关键新增逻辑）
    size_t aligned_size = align_to_power_of_two(size);
    int class_index = get_size_class_index(aligned_size);
    if (class_index < 0 || class_index >= MAX_SIZE_CLASS) {
        class_index = MAX_SIZE_CLASS - 1;  // 保险处理
    }
    void** bucket = &tls_thread_cache->buckets[class_index];
    
    // 2. 从空闲链表头部取对象（O(1)时间）
    if (*bucket) {
        void* obj = *bucket;
        *bucket = *(void**)obj;  // 链表指针前移
        return obj;
    }
    
    // 3. 本地无空闲对象，向CentralCache批量申请（触发全局协作）
    return fetch_from_central_cache(class_index);  // 传递Size Class索引
}

// ThreadCache释放函数（无锁，结合哈希桶索引）
void thread_cache_free(void* ptr, size_t size) {
    if (!tls_thread_cache || !ptr) return;
    
    // 1. 计算哈希桶索引（关键新增逻辑）
    size_t aligned_size = align_to_power_of_two(size);
    int class_index = get_size_class_index(aligned_size);
    if (class_index < 0 || class_index >= MAX_SIZE_CLASS) {
        class_index = MAX_SIZE_CLASS - 1;  // 保险处理
    }
    void** bucket = &tls_thread_cache->buckets[class_index];
    
    // 2. 插入空闲链表头部（O(1)时间）
    *(void**)ptr = *bucket;
    *bucket = ptr;
}

// 页号类型（使用uintptr_t保证跨平台兼容性）
using PageID = uintptr_t;

// 虚拟地址 = 页号 × 页大小
void* page_to_addr(PageID page_id) {
    return (void*)(page_id * PAGE_SIZE);
}

// Span结构体（管理连续页的内存块）
struct Span {
    PageID start_page;    // 起始页号
    size_t page_count;    // 总页数（如1页=4KB，2页=8KB）
    Span* prev;           // 双链表前驱指针
    Span* next;           // 双链表后继指针
    bool is_free;         // 是否空闲
    // 扩展字段（如对象大小分类、引用计数等）
};

// CentralCache结构体
struct CentralCache {
    SpinLock lock;               // 自旋锁（保护全局操作）
    Span* free_spans[MAX_PAGE_COUNT];  // 按页数分类的空闲链表（如1页、2页、4页...）
    size_t total_pages;          // 总管理的页数
    size_t used_pages;           // 已使用的页数
};

// 合并相邻的空闲Span
void merge_adjacent_spans(CentralCache* cache, Span* span) {
    // 检查前驱Span是否空闲
    if (span->prev && span->prev->is_free) {
        span->start_page = span->prev->start_page;
        span->page_count += span->prev->page_count;
        // 从链表中移除前驱Span
        span->prev->prev->next = span;
        span->prev = span->prev->prev;
        cache->free_spans[span->prev->page_count] = span->prev;  // 更新链表头
    }
    
    // 检查后继Span是否空闲（类似逻辑）
    // ...
}

// PageCache结构体
struct PageCache {
    SpinLock lock;               // 自旋锁（保护全局操作）
    Span* free_spans;            // 空闲Span的双链表（按页数排序）
    size_t total_pages;          // 总管理的页数
    size_t free_pages;           // 空闲页数
};

// 从PageCache获取Span（关键逻辑）
Span* page_cache_get_span(PageCache* cache, size_t required_pages) {
    SpinLockAcquire(&cache->lock);
    
    // 1. 查找空闲链表中是否有足够页数的Span
    Span* current = cache->free_spans;
    while (current) {
        if (current->page_count >= required_pages) {
            // 找到足够大的Span，分割为两部分（保留剩余页）
            Span* allocated = current;
            allocated->page_count = required_pages;
            allocated->is_free = false;
            
            // 剩余页形成新的Span（若有余）
            Span* remaining = (Span*)((char*)current + required_pages * PAGE_SIZE);
            remaining->start_page = current->start_page + required_pages;
            remaining->page_count = current->page_count - required_pages;
            remaining->is_free = true;
            
            // 从空闲链表中移除当前Span
            remove_span_from_free_list(cache, current);
            
            // 若剩余页非零，加入空闲链表
            if (remaining->page_count > 0) {
                add_span_to_free_list(cache, remaining);
            }
            
            SpinLockRelease(&cache->lock);
            return allocated;
        }
        current = current->next;
    }
    
    // 2. 本地无足够空闲页，向操作系统申请新内存（原有内容优化）
    size_t new_pages = required_pages * 2;  // 超量申请（减少未来系统调用）
    PageID new_start_page = (PageID)mmap(
        NULL, 
        new_pages * PAGE_SIZE, 
        PROT_READ | PROT_WRITE, 
        MAP_PRIVATE | MAP_ANONYMOUS, 
        -1, 
        0
    );
    
    if (new_start_page == MAP_FAILED) {
        SpinLockRelease(&cache->lock);
        return NULL;  // 申请失败
    }
    
    // 创建新Span并加入空闲链表
    Span* new_span = (Span*)malloc(sizeof(Span));
    new_span->start_page = new_start_page;
    new_span->page_count = new_pages;
    new_span->is_free = true;
    add_span_to_free_list(cache, new_span);
    
    // 重新查找并分配（此时新Span已在空闲链表）
    return page_cache_get_span(cache, required_pages);
}