https://github.com/ygc129550/HeapMemoryManager

HeapMemoryManager

一个基于 页面族（Page Family） 的固定大小对象内存分配器，专为结构体类型已知、大小固定的场景设计。每个页面仅服务一种结构体类型，通过 Worst-fit 策略管理页内空闲块，支持自动合并与整页回收。

1. 设计逻辑结构

1.1 核心概念

┌─────────────────────────────────────────────────────────┐

│                  vm_page_for_families_t                 │ ← 元数据页：存储多个 family 描述符

│  ┌──────────────────┐ ┌──────────────────┐              │

│  │ vm_page_family_t │ │ vm_page_family_t │  ...         │

│  │ struct_name      │ │ struct_name      │              │

│  │ struct_size      │ │ struct_size      │              │

│  │ first_page ────┐ │ │                  │              │

│  │ priority_head  │ │ │                  │              │

│  └────────────────┼─┘ └──────────────────┘              │

└───────────────────┼─────────────────────────────────────┘

                    │

                    │ vm_page_t*

                    ▼

┌─────────────────────────────────────────────────────────┐

│                     vm_page_t                           │ ← 数据页：4096B，仅存一种结构体

│  prev / next / pg_family                                │

│  ┌────────────────────────────────────────────────────┐ │

│  │ block_meta_data_t (页首初始空闲块)                  │ │

│  │  is_free | block_size | offset | priority_node     │ │

│  │  prev_block | next_block                           │ │

│  ├────────────────────────────────────────────────────┤ │

│  │ page_memory[] (用户数据区 + 嵌入式 metadata)         │ │

│  │  [struct][meta][struct][meta][struct][free...]     │ │

│  └────────────────────────────────────────────────────┘ │

└─────────────────────────────────────────────────────────┘

| 概念 | 说明 |

|------|------|

| vm_page_for_families_t | 元数据页，通过柔性数组存储多个 vm_page_family_t 描述符，以链表形式扩展 |

| vm_page_family_t | 页面族描述符，绑定一种结构体类型（名称 + 大小），维护该类型所有数据页的链表和全局空闲块优先链表 |

| vm_page_t | 数据页，从内核 mmap 获取，页头包含双向链表指针、所属 family 指针和首个 block_meta_data_t |

| block_meta_data_t | 块元数据，嵌入在数据页中每个用户数据块的前方，记录空闲状态、大小、页内偏移、物理链表指针和优先链表节点 |

| glue_node_t | 侵入式双向链表节点，用于构建按 block_size 降序排列的空闲块优先链表（Worst-fit） |

1.2 分配流程（xcalloc）

xcalloc("emp_t", 1)

    │

    ▼

look_up_family_by_name("emp_t")

    │

    ▼

mm_allocate_free_data_block(family, struct_size)

    │

    ├── 优先链表头部有 ≥ req_size 的空闲块？

    │       YES → mm_claim_and_split_block()

    │               ├── glue_node_remove()          // 从优先链表摘除

    │               ├── mm_split_free_block_for_allocation()

    │               │       ├── 标记 is_free = false

    │               │       ├── remainder < sizeof(meta)? → 硬碎片，整块返回

    │               │       └── remainder ≥ sizeof(meta)? → 创建尾部空闲块

    │               │               └── mm_bind_blocks_for_allocation()  // 链入物理链表

    │               └── 新空闲块加入优先链表（若产生）

    │

    └── NO → allocate_vm_page(family)

                ├── mmap 新页

                ├── 挂入 family 页面链表

                ├── MARK_VM_PAGE_EMPTY()

                └── mm_claim_and_split_block(页首块, req_size)

1.3 释放流程（xfree）

xfree(ptr)

    │

    ├── ptr == NULL? → return

    │

    ▼

(block_meta_data_t *)ptr - 1   // 反算 metadata 地址

    │

    ▼

assert(!is_free) → is_free = true

    │

    ▼

MM_GET_PAGE_META_BLOCK() → 定位所属 vm_page_t

    │

    ▼

检查前驱/后继是否空闲

    ├── YES → glue_node_remove(邻居.priority_list_node)  // 先从优先链表摘除

    │         更新 free_block_start / free_block_end

    │

    ▼

mm_union_free_blocks(start, end)  // 合并物理块

    │

    ▼

mm_is_vm_page_empty(vm_page)?

    ├── YES → mm_vm_page_delete_and_free()  // 整页归还内核

    │           ├── 从 family 页面链表摘除

    │           └── munmap()

    │

    └── NO  → mm_add_free_block_metadata_to_free_block_list()

                // 按 block_size 降序插入优先链表（O(n)）

1.4 碎片模型

在本分配器的固定大小 family 模型下，碎片行为具有确定性：

| 碎片类型 | 定义 | 产生位置 | 能否复用 | 处理方式 |

|---------|------|---------|---------|---------|

| 硬碎片 | 分割后剩余空间 < sizeof(block_meta_data_t) | 仅页面顶部最后一次分配边界 | ❌ | 被吞入前一个已分配块的 block_size，随该块释放自动归还 |

| 软碎片 | sizeof(meta) ≤ 剩余 < struct_size | 仅页面顶部最后一次分配边界 | ❌ | 作为独立空闲块存在于优先链表中，但永远无法满足本 family 分配；整页空闲时随页面回收 |

| 外部碎片 | 分散的空闲块总量足够但不连续 | 页面中间 | ✅ | 通过 xfree 时的双向邻居合并及时消除 |

关键性质：由于每个页面只服务一种固定大小的结构体，且所有分配请求均为 struct_size 的整数倍，页面中间的任何空闲块大小必然是 struct_size 的整数倍，不可能产生不可复用的硬/软碎片。碎片仅可能出现在页面顶部，由 (SYSTEM_PAGE_SIZE - offsetof(vm_page_t, block_meta_data)) mod (struct_size + sizeof(block_meta_data_t)) 决定。

2. 代码结构

HeapMemoryManager/

├── mm.h              # 内部数据结构定义、宏、迭代器

├── uapi_mm.h         # 用户 API 声明（xcalloc/xfree/MM_REG_STRUCT 等）

├── mm.c              # 核心实现

├── testapp.c         # 测试用例

├── CMakeLists.txt    # 构建配置（依赖 GLUE_DS 库）

├── build.sh          # 一键构建脚本

└── ../GLUE_DS/       # 侵入式双向链表库（glnode.h）

2.1 文件职责

| 文件 | 职责 |

|------|------|

| uapi_mm.h | 对外接口层。定义 XCALLOC()MM_REG_STRUCT() 等用户宏，屏蔽内部实现细节 |

| mm.h | 内部数据层。定义 vm_page_tblock_meta_data_tvm_page_family_t 等结构体，以及 ITERATE_* 系列遍历宏和 MARK_VM_PAGE_EMPTYmm_bind_blocks_for_allocation 等操作宏 |

| mm.c | 核心逻辑层。分为以下几组函数： |

| | • 初始化mm_init()mm_instantiate_new_page_family() |

| | • 页面管理allocate_vm_page()mm_vm_page_delete_and_free()mm_get_new_vm_page_from_kernel()mm_return_vm_page_to_kernel() |

| | • 分配事务mm_allocate_free_data_block()mm_claim_and_split_block()mm_split_free_block_for_allocation() |

| | • 释放事务xfree()mm_union_free_blocks()mm_assert_free_from_start_to_end() |

| | • 优先链表mm_add_free_block_metadata_to_free_block_list()free_blocks_comparison() |

| | • 查询/调试look_up_family_by_name()mm_is_vm_page_empty()mm_print_*() 系列 |

| glnode.h | 基础设施层。提供侵入式双向链表的 init/add/remove/container_of/isolated 等操作，不依赖任何动态内存分配 |

2.2 关键宏说明

| 宏 | 用途 |

|----|------|

| MM_REG_STRUCT(type) | 注册结构体类型，展开为 mm_instantiate_new_page_family(#type, sizeof(type)) |

| XCALLOC(n, type) | 分配 n 个 type 对象，展开为 xcalloc(#type, n) |

| MM_GET_PAGE_META_BLOCK(meta) | 通过 block_meta_data_t 的 offset 字段反算所属 vm_page_t 地址 |

| MARK_VM_PAGE_EMPTY(page) | 将新页面的首个块标记为空闲、链表指针置空 |

| mm_bind_blocks_for_allocation(alloc, free) | 分割后将新空闲块链入物理双向链表 |

| ITERATE_PAGE_FAMILIES_BEGIN/END | 遍历一个 vm_page_for_families_t 中的所有有效 family |

| ITERATE_VM_PAGE_BEGIN/END | 遍历一个 family 的所有数据页 |

| ITERATE_VM_PAGE_ALL_BLOCKS_BEGIN/END | 遍历一个页面内的所有物理块 |

| ITERATE_NODES_START/END | 安全遍历 glue_node 双向链表 |

3. 优缺点分析

3.1 优点

| 优点 | 说明 |

|------|------|

| 零外部碎片（页内） | 固定大小 family 保证页内空闲块始终可被同类型分配复用，合并机制及时消除分散 |

| 碎片可控且可预测 | 硬/软碎片仅出现在页面顶部，浪费上限由 struct_size 和页头大小决定，与分配频率无关 |

| Worst-fit O(1) 分配 | 优先链表降序排列，最大空闲块始终在头部，分配查找为常数时间 |

| 整页自动回收 | 页面完全空闲时自动 munmap 归还内核，防止页面级内存泄漏 |

| 类型隔离 | 不同结构体类型使用独立页面，避免混合分配导致的交叉碎片和缓存污染 |

| 侵入式数据结构 | 优先链表节点嵌入 block_meta_data_t，无需额外 malloc/free 管理链表本身 |

| 调试友好 | 内置 mm_print_memory_usage()mm_print_block_usage() 等可视化函数，可直接观察每页每块的状态 |

3.2 缺点

| 缺点 | 说明 | 缓解措施 |

|------|------|---------|

| 释放 O(n) | mm_add_free_block_metadata_to_free_block_list 线性遍历优先链表找插入点，空闲块多时性能退化 | 改用分级自由链表（Segregated Fit）可将释放降为 O(1) |

| 跨页不合并 | 相邻两页即使各剩一个空闲块也无法合并，只能等整页空闲才回收 | 架构固有约束，适合对象生命周期相近的场景；可通过监控碎片率评估影响 |

| 仅支持固定大小 | 不支持可变大小分配，每种新类型需预先注册 | 适用于控制面/协议栈等结构体类型有限的场景 |

| 页面顶部浪费 | (4096 - 页头) mod struct_size 字节不可用，小 struct_size 时浪费比例较高 | 可选择 struct_size 使其更接近 4096 的因数 |

| 非线程安全 | 无任何内置同步机制，多线程并发调用 xcalloc/xfree 会导致数据竞争 | 外层加互斥锁，或按 family 粒度加细粒度锁 |

| family 查找 O(n) | look_up_family_by_name 线性扫描所有已注册类型 | 类型数量少时可接受；数量多时可改用哈希表 |

| mmap 系统调用开销 | 每次申请新页都触发 syscall，高频小对象分配时开销显著 | 可引入页面池预分配机制 |

3.3 适用场景

✅ 适合：网络设备控制面、协议栈消息处理、嵌入式系统、游戏 ECS 组件管理等结构体类型有限、大小固定、分配释放模式可预测的场景。

❌ 不适合：通用 malloc/free 替代、字符串/缓冲区等可变大小分配、高并发无锁场景、对延迟极度敏感的实时系统。

4. 快速开始

4.1 构建

./build.sh          # 构建

./build.sh clean    # 清理

4.2 使用示例

#include "uapi_mm.h"

typedef struct emp_ {

    char name[32];

    uint32_t emp_id;

} emp_t;

int main() {

    mm_init();                          // 初始化（获取系统页大小）

    MM_REG_STRUCT(emp_t);               // 注册结构体类型

    emp_t *e = XCALLOC(1, emp_t);       // 分配 1 个 emp_t

    xfree(e);                           // 释放

    mm_print_block_usage();             // 查看内存使用统计

    return 0;

}

4.3 API 参考

| API | 说明 |

|-----|------|

| mm_init() | 初始化分配器，必须在所有其他操作之前调用 |

| MM_REG_STRUCT(type) | 注册结构体类型，创建对应的页面族 |

| XCALLOC(units, type) | 分配 units 个 type 对象，返回清零的指针，失败返回 NULL |

| xfree(ptr) | 释放由 XCALLOC 返回的指针，支持 NULL |

| mm_print_registered_page_families() | 打印所有已注册的结构体类型 |

| mm_print_memory_usage(name) | 打印指定类型的详细页面/块布局（name="" 打印全部） |

| mm_print_block_usage() | 打印所有类型的块使用统计摘要 |