C语言实现1字节至8KB内存块的内存管理器面试问题咨询

你之前遇到的单级8KB固定内存池浪费高、可变大小分配效率低的问题，可以用**分级固定大小内存池（Segregated Fit）**方案解决，该方案可同时实现O(1)复杂度的分配/释放操作，且内存浪费控制在极低水平，完全符合你的要求。

方案核心原理 #

因为申请的内存大小范围固定为[1B, 8KB]，我们将所有申请大小按2的幂次划分为多个级别，每个级别对应一个独立的固定大小块内存池：

• 级别划分：16B、32B、64B、128B、256B、512B、1KB、2KB、4KB、8KB，共10个级别
• 分配时将申请大小向上对齐到最近的2的幂次，从对应级别的空闲链表中直接取块
• 释放时直接将块插回对应级别空闲链表的头部
  该方案最坏情况下内存浪费率不超过50%（比如申请17B对齐到32B，仅浪费15B），远低于单级8KB池的浪费水平，且所有操作都为O(1)复杂度。

具体实现代码 #

1. 预定义数据结构与全局配置 #

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

// 全局配置参数
#define TOTAL_MEM_LIMIT (1UL << 30)  // 总内存上限1GB
#define MAX_ALLOC_SIZE (8 << 10)     // 单次最大申请8KB
#define MIN_ALIGN 16                 // 内存对齐要求16字节
#define POOL_LEVEL_COUNT 10          // 内存池分级数量

// 每个级别对应的空闲链表头
static void* free_lists[POOL_LEVEL_COUNT];
// init阶段预分配的总内存块基地址
static uint8_t* global_mem_base;
// 预分配内存已使用偏移量
static size_t mem_used_offset;

2. init() 实现 #

仅在该函数中调用一次malloc申请总内存，完成各分级内存池的初始化：

void init() {
    // 一次性申请全部上限内存
    global_mem_base = (uint8_t*)malloc(TOTAL_MEM_LIMIT);
    mem_used_offset = 0;
    memset(free_lists, 0, sizeof(free_lists));
}

3. get() 实现 #

// 工具函数：根据申请大小返回对应内存池级别
static int get_level(size_t size) {
    if (size <= 16) return 0;
    if (size <= 32) return 1;
    if (size <= 64) return 2;
    if (size <= 128) return 3;
    if (size <= 256) return 4;
    if (size <= 512) return 5;
    if (size <= 1024) return 6;
    if (size <= 2048) return 7;
    if (size <= 4096) return 8;
    return 9;
}

void* get(int numOfBytes) {
    // 非法参数校验
    if (numOfBytes < 1 || numOfBytes > MAX_ALLOC_SIZE) {
        return NULL;
    }

    int level = get_level(numOfBytes);
    size_t block_size = 16 << level;
    // 块首8字节存储块大小，返回给用户的指针偏移8字节保证对齐
    size_t real_block_size = block_size + 8;

    // 当前级别无空闲块，从全局预分配内存中切新块
    if (free_lists[level] == NULL) {
        if (mem_used_offset + real_block_size > TOTAL_MEM_LIMIT) {
            return NULL;
        }
        uint8_t* block = global_mem_base + mem_used_offset;
        *(size_t*)block = block_size; // 存储块大小用于free时识别级别
        mem_used_offset += real_block_size;
        return block + 8;
    }

    // 从空闲链表头取可用块
    uint8_t* block = (uint8_t*)free_lists[level];
    free_lists[level] = *(void**)block;
    return block + 8;
}

4. free() 实现 #

void free(void* ptr) {
    if (ptr == NULL) {
        return;
    }
    // 拿到块的真实首地址，读取块大小获取对应级别
    uint8_t* real_block = (uint8_t*)ptr - 8;
    size_t block_size = *(size_t*)real_block;
    int level = get_level(block_size);

    // 将块插到空闲链表头部
    *(void**)real_block = free_lists[level];
    free_lists[level] = real_block;
}

方案符合规则校验 #

1. 仅在init()函数中调用了1次malloc，符合要求
2. get和free操作均为O(1)复杂度，无额外遍历逻辑，效率极高
3. 总内存占用固定不超过1GB上限，无额外内存开销
4. 内存浪费最高为块大小的50%，远低于单级固定池的浪费水平

内容的提问来源于stack exchange，提问作者John