上一篇实现的是固定大小内存池先将一块大内存划分成多个相同大小的小块再通过空闲链表完成申请和释放。这种方式适合大量相同大小的对象但如果程序申请的内存大小不同例如依次申请 32 字节、64 字节和 100 字节就需要准备多个不同规格的固定块内存池。另一种实现方式是预先申请一块连续内存使用一个指针记录当前分配位置。每次申请时直接向后移动指针当当前内存块空间不足时再申请一个新的内存块。这种方式不需要为每种大小维护空闲链表适合生命周期相近、需要统一释放的大量小块内存。一、可变大小内存池的基本思路假设内存池中有一块 4096 字节的连续内存内存块起始地址 ↓ ----------------------------------------- | 管理信息 | 可以分配的空间 | ----------------------------------------- ↑ ↑ last end其中last指向当前还没有被使用的内存位置end指向当前内存块的结束位置。申请 32 字节后只需要让last向后移动 32 字节申请前 -------------------------------------------- | 管理信息 | 空闲空间 | -------------------------------------------- ↑ ↑ last end 申请32字节后 ------------------------------------------- | 管理信息 | 已分配32B | 剩余空间 | ------------------------------------------- ↑ ↑ last end再次申请 64 字节时继续从last指向的位置分配------------------------------------------ | 管理信息 | 已分配32B | 已分配64B | 剩余空间 | ------------------------------------------ ↑ ↑ last end这种分配方式只需要完成指针计算和移动不需要遍历空闲链表也不需要每次调用malloc()。小块内存的申请过程可以概括为取得当前分配位置last ↓ 按照指定字节进行地址对齐 ↓ 检查end - last是否足够 ↓ 返回当前地址 ↓ last向后移动size字节二、内存池中的核心结构首先定义内存对齐值和单页大小#include stdio.h #include stdlib.h #include string.h #define MP_ALIGNMENT 32 #define MP_PAGE_SIZE 4096 /* * 小于该值的申请由内存池的小块内存区域处理 * 大于该值的申请交给malloc单独处理。 */ #define MP_MAX_ALLOC_FROM_POOL (MP_PAGE_SIZE - 1)每一块内存区域都使用一个mp_node_s进行管理typedef struct mp_node_s { unsigned char *last; // 当前未使用空间的起始位置 unsigned char *end; // 当前内存块的结束位置 struct mp_node_s *next; // 指向下一块内存节点 size_t failed; // 在当前节点中分配失败的次数 } mp_node_t;它描述的是一块连续内存的使用情况mp_node_t ------------------------------------------------ | last | end | next | failed | 可分配内存区域 | ------------------------------------------------ ↑ ↑ last end内存池整体结构如下typedef struct mp_large_s { struct mp_large_s *next; // 指向下一个大块内存记录 void *alloc; // 单独通过malloc申请的地址 } mp_large_t; typedef struct mp_pool_s { size_t max; // 小块内存的最大申请值 mp_node_t *current; // 当前优先进行分配的节点 mp_large_t *large; // 大块内存记录链表 /* * 零长度数组表示首个内存节点紧跟在内存池结构之后。 * 这是部分编译器支持的扩展写法。 */ mp_node_t head[0]; } mp_pool_t;各成员之间的关系可以表示为mp_pool_t ├── max区分小块申请和大块申请 ├── current当前优先使用的内存节点 ├── large大块内存记录链表 └── head第一个小块内存节点 │ ├── node1 ├── node2 └── node3其中current不一定始终指向第一个节点。当某个节点多次出现空间不足时可以将current移动到后面的节点避免每次申请都重复检查已经接近用满的内存块。三、创建内存池并初始化首个节点为了让内存地址满足指定的对齐要求可以使用posix_memalign()申请内存int posix_memalign( void **memptr, size_t alignment, size_t size );与普通malloc()相比它可以保证返回地址是alignment的整数倍。创建内存池的代码如下mp_pool_t *mp_create_pool(size_t size) { mp_pool_t *pool NULL; /* * 实际申请的空间包括 * * 1. 内存池管理结构mp_pool_t * 2. 首个节点管理结构mp_node_t * 3. 用户指定的小块内存区域size。 */ size_t total_size sizeof(mp_pool_t) sizeof(mp_node_t) size; /* * 申请一块32字节对齐的连续内存。 * * 成功返回0 * 失败返回非0。 */ int ret posix_memalign( (void **)pool, MP_ALIGNMENT, total_size ); if (ret ! 0) { return NULL; } /* * max用于判断一次申请是否属于小块内存。 * * 如果用户指定的池大小超过上限 * 小块内存最大申请值仍限制为4095字节。 */ pool-max size MP_MAX_ALLOC_FROM_POOL ? size : MP_MAX_ALLOC_FROM_POOL; // 首次创建时从第一个节点开始分配 pool-current pool-head; // 当前还没有单独申请的大块内存 pool-large NULL; /* * 首个节点位于mp_pool_t结构后面。 * * 可以分配的用户空间位于 * mp_pool_t和mp_node_t之后。 */ pool-head-last (unsigned char *)pool sizeof(mp_pool_t) sizeof(mp_node_t); // end指向当前节点可用内存的结束位置 pool-head-end pool-head-last size; // 当前只有一个节点 pool-head-next NULL; // 初始化分配失败次数 pool-head-failed 0; return pool; }创建一个 4096 字节的内存池mp_pool_t *pool mp_create_pool(4096); if (pool NULL) { printf(内存池创建失败\n); return -1; }创建完成后的内存布局为pool ↓ ------------------------------------------------------ | mp_pool_t结构 | mp_node_t结构 | 4096字节可分配空间 | ------------------------------------------------------ ↑ ↑ last end这里将管理结构和第一块可分配空间放在同一次内存申请中具有两个优点创建内存池时只需要进行一次系统内存申请管理结构和用户空间地址连续访问时具有较好的局部性。需要注意代码中的mp_node_t head[0];属于零长度数组写法在 GCC 等编译器中较常见。标准 C99 中也可以使用柔性数组mp_node_t head[];四、小块内存如何完成对齐和分配计算机访问某些类型的数据时通常希望数据地址满足一定的对齐要求。例如采用 32 字节对齐时下面这些地址是符合要求的0x1000 0x1020 0x1040 0x1060因为它们都能够被 32 整除。可以使用下面的宏将数值和指针向上对齐/* * 将整数n向上调整为alignment的整数倍。 * * 例如 * mp_align(17, 32) 32 * mp_align(32, 32) 32 * mp_align(33, 32) 64 */ #define mp_align(n, alignment) \ (((n) ((alignment) - 1)) ~((alignment) - 1)) /* * 将指针p向上调整到指定的对齐地址。 */ #define mp_align_ptr(p, alignment) \ (void *)((((size_t)(p)) ((alignment) - 1)) \ ~((alignment) - 1))小块内存申请函数如下void *mp_alloc(mp_pool_t *pool, size_t size) { unsigned char *mem; mp_node_t *node; if (pool NULL || size 0) { return NULL; } /* * 小于等于max的申请尝试从内存池节点中分配。 */ if (size pool-max) { node pool-current; do { /* * 将当前last地址向上进行32字节对齐。 * * 注意对齐后的地址可能比原last稍大 * 中间跳过的几个字节属于对齐填充。 */ mem (unsigned char *)mp_align_ptr( node-last, MP_ALIGNMENT ); /* * 检查对齐后的剩余空间是否足够。 */ if ((size_t)(node-end - mem) size) { // 更新当前节点的分配位置 node-last mem size; // 返回本次申请到的内存地址 return mem; } // 当前节点空间不足检查下一个节点 node node-next; } while (node ! NULL); /* * 所有已有节点都没有足够空间 * 需要创建一个新的内存节点。 */ return mp_alloc_block(pool, size); } /* * 超过max的申请不再使用小块内存区域 * 后续通过大块内存分配函数处理。 */ return mp_alloc_large(pool, size); }假设当前last地址不是 32 的整数倍原last地址0x1013 对齐后地址0x1020那么0x1013到0x101F之间的空间会被跳过------------------------------------------ | 已用空间 | 对齐填充区域 | 本次申请的内存 | ------------------------------------------ ↑ ↑ 原last 对齐后地址这些填充字节虽然没有直接分配给用户但能够保证返回地址满足对齐要求。对齐通常可以带来以下好处满足基本数据类型或特殊指令的地址要求降低某些平台上的非对齐访问成本便于存放结构体、数组和 SIMD 数据避免部分处理器发生非对齐访问异常。如果某些内存不需要强制对齐也可以提供一个不进行地址对齐的接口void *mp_nalloc(mp_pool_t *pool, size_t size) { unsigned char *mem; mp_node_t *node; if (pool NULL || size 0) { return NULL; } if (size pool-max) { node pool-current; do { // 不进行对齐直接从last开始分配 mem node-last; if ((size_t)(node-end - mem) size) { node-last mem size; return mem; } node node-next; } while (node ! NULL); return mp_alloc_block(pool, size); } return mp_alloc_large(pool, size); }二者的主要区别是mp_alloc 先对last进行地址对齐再完成分配。 mp_nalloc 直接从last开始分配不额外处理地址对齐。一般情况下优先使用mp_alloc()。只有能够确定数据没有特殊对齐要求时才考虑使用mp_nalloc()。五、当前节点空间不足时如何扩容当所有已有节点都没有足够空间时需要再申请一块新的内存并将其添加到节点链表尾部。扩容函数如下static void *mp_alloc_block(mp_pool_t *pool, size_t size) { unsigned char *mem; /* * 使用首个节点的总大小作为后续节点大小。 * * 这里的大小包含 * 1. mp_node_t节点管理信息 * 2. 后续可以分配的用户空间。 */ mp_node_t *head pool-head; size_t block_size (size_t)(head-end - (unsigned char *)head); // 申请一块新的对齐内存 int ret posix_memalign( (void **)mem, MP_ALIGNMENT, block_size ); if (ret ! 0) { return NULL; } // 新内存块开头用于存放节点管理信息 mp_node_t *new_node (mp_node_t *)mem; new_node-end mem block_size; new_node-next NULL; new_node-failed 0; /* * 跳过节点管理结构 * 然后对用户内存起始地址进行对齐。 */ mem sizeof(mp_node_t); mem (unsigned char *)mp_align_ptr( mem, MP_ALIGNMENT ); /* * 本次申请直接使用新节点中的第一块空间 * 因此last移动到本次申请之后。 */ new_node-last mem size; mp_node_t *node; mp_node_t *current pool-current; /* * 找到节点链表尾部。 * * 遍历过程中如果某个节点多次分配失败 * 说明它的剩余空间已经很少 * 可以让current跳过该节点。 */ for (node current; node-next ! NULL; node node-next) { node-failed; if (node-failed 4) { current node-next; } } // 将新节点添加到链表尾部 node-next new_node; /* * 更新下一次分配的起始节点。 * * 如果前面的节点已经多次失败 * 后续申请可以直接从更靠后的节点开始检查。 */ pool-current current ! NULL ? current : new_node; return mem; }假设当前已经有两个节点current | v node1 → node2 → NULL当两个节点都没有足够空间时会创建node3current | v node1 → node2 → node3 → NULL新节点中的第一块空间会直接返回给本次申请node3 ------------------------------------------------ | 节点管理信息 | 本次申请的内存 | 剩余空间 | ------------------------------------------------ ↑ ↑ last endfailed和current是一种简单的查找优化。如果每次申请都从第一个节点开始检查随着节点数量增加前面已经接近用满的节点会被反复访问检查node1失败 检查node2失败 检查node3成功下一次申请时又会重复同样的过程。记录失败次数后可以逐渐让current向后移动原来 current | v node1 → node2 → node3 node1多次失败后 current | v node1 → node2 → node3后续申请可以直接从node2或更靠后的节点开始检查减少无效遍历。下面给出一个简单的使用示例int main(void) { // 创建4096字节的小块内存池 mp_pool_t *pool mp_create_pool(4096); if (pool NULL) { printf(内存池创建失败\n); return -1; } // 申请32字节 void *p1 mp_alloc(pool, 32); // 申请64字节 void *p2 mp_alloc(pool, 64); // 申请100字节 void *p3 mp_alloc(pool, 100); printf(p1 %p\n, p1); printf(p2 %p\n, p2); printf(p3 %p\n, p3); /* * 连续申请多块512字节内存。 * 当第一个节点空间不足时 * 内存池会自动创建新的节点。 */ for (int i 0; i 20; i) { void *ptr mp_alloc(pool, 512); if (ptr NULL) { printf(第%d次申请失败\n, i 1); break; } printf(第%d块内存地址%p\n, i 1, ptr); } /* * 小块内存通常不进行单独释放 * 最后统一销毁整个内存池。 */ mp_destory_pool(pool); return 0; }这一类小块内存池采用的是顺序分配思想创建一块连续内存 ↓ last记录当前分配位置 ↓ 申请时移动last ↓ 当前节点空间不足 ↓ 创建新节点并加入链表 ↓ 销毁时统一释放所有节点它与上一篇固定大小内存池的主要区别是固定大小内存池 将内存预先划分成大小相同的块可以单独回收并重复利用。 顺序分配内存池 每次可以申请不同大小的小块内存通常不单独释放 而是在一批任务完成后统一重置或销毁。0voice · GitHub