这是个人编写的第三版内存管理器，主要用在单片机上。这一系列的内存管理器，由于本人对内存碎片的执念，于是前两版的使用非常反人类。举个例子： 第一版 void** malloc(uint32_t _size,uint8 _userid); 分配出来的是指向地址的地址，这对常规程序来说，用起来的感觉是相当酸爽。 第二版 void* malloc(uint32_t _size,uint8_t _userid,void **_address); 这就比较好看点了，但是还要给一个被分配的指针变量的地址。（内存管理第二版） 上面两个版本，用的一种思路是——知道被分配的地址a的地址b，每当碎片整理时，直接将数据移动到上一块被使用的内存后面，更新地址b上的地址a，得到地址c。
碎片整理前 类型 内存块1 内存块2 内存块3 内存块4 内存块5 内存块6 数据 hello world !!! 内存池地址 0x40000000 0x40000010 0x40000020 0x40000030 0x40000040 0x40000050 被分配的地址 0x20001024 0x20003280 0x20007238 碎片整理后 类型 内存块1 内存块2 内存块3 内存块4 内存块5 内存块6 数据 hello world !!! 内存池地址 0x40000000 0x40000010 0x40000020 0x40000030 0x40000040 0x40000050 被分配的地址 0x20001024 0x20003280 0x20007238 将内存块 0x40000020 上的数据 “world” 复制到 内存块 0x40000010 上，并将新的地址更新到指针变量地址 0x20003280 上。
像这样做的优点是，当碎片整理完成后，不影响数据的使用。而缺点是，只能自己玩，并不适合一起用。 但是在某一天，翻资料，看到了linux的内存管理机制后，一下顿悟了，于是有了内存管理器的第三版。

---

原理

（n块内存组成一页，n页内存组成一组，n组内存）
1. 根据设定的内存大小（不超过物理内存）即内存池，分配 x 组（目前x最大值为1024），根据分配策略限定每组内存大小。
2. 按照 2i,i∈[0,x]" role="presentation" style="position: relative;">2i,i∈[0,x]$2^i,i\in [0,x]$ 的规律，对 i,i∈[0,x]" role="presentation" style="position: relative;">i,i∈[0,x]$i,i\in [0,x]$ 组进行分页。
3. 内存分配顺序，由小页到大页，游大端到大端。
4. 当要分配的 i,i∈[0,x)" role="presentation" style="position: relative;">i,i∈[0,x)$i,i\in [0,x)$ 组的内存用完时，向i+1,i∈[0,x)" role="presentation" style="position: relative;">i+1,i∈[0,x)$i+1,i\in [0,x)$ 组内存借一页，使用递归模式，直至没有内存可以分配。
5. 内存释放后，若该内存为借用的，则尝试拼回。
6. 一块内存大小为 2i,i>0" role="presentation" style="position: relative;">2i,i>0$2^i,i>0$ 字节。 举个例子。
有定义一块内存池，大小为 327680 Bytes，定义一块内存块为 32 字节。将其分成10组，则每组大小为 32 KBytes。 组数 1组 2组 3组 4组 5组 6组 7组 8组 9组 10组 内存页大小 1 2 4 8 16 32 64 128 216 512 内存块数量 1024 1024 1024 1024 1024 1024 1024 1024 1024 1024 内存页数量 1024 512 216 128 64 32 16 8 4 2

• 当变量a需要分配的内存大小为 10 字节时，根据内存分配顺序，为该变量 a 分配页大小为 1 的内存，即变量 a 实际分配了 32 个字节。
• 当变量b需要分配的内存大小为 550 字节时，同理，为该变量分配页大小为页大小为 32 的内存，即变量b实际分配了 1024 个字节。
• 当变量c需要分配的内存大小为 100 字节，且大小为 4 的内存页分配完时，若第 4 组有剩余内存，将第 4 组的一块内存页分配给第 3 组，第三组内存页将其拆成 2 页，其中一页分配给变量 c，即变量 c 最终分配了 128 个字节。

---

方案

内存分配策略

假设内存大小为 m ，分组数量为n，其中最大分配组 11 组，即最大页为 1024，内存块大小为 32 字节 。
采用组大小均衡方法，使其符条件 (mn>2n∗32)∧(m(n+1)<2n+1∗32)" role="presentation" style="position: relative;">(mn>2n∗32)∧(m(n+1)<2n+1∗32)$(\frac{m}{n}>2^n\ast 32)\wedge (\frac{m}{(n+1)}<2^{n+1}\ast 32)$ 。

模型

将一大块内存分为两部分，一部分为内存管理器，一部分为内存池。
内存管理器分两部分——总管理器和各分页管理器。
页管理器中，空闲内存页以单向链表的形式链接起来，每页内存并包含一字节内存页信息。
使用时，根据申请的内存页大小，由相应的页管理器从页链表中取出一块内存页进行分配；当该级内存没有可分配内存页，该级管理向更大的页管理器申请一块内存，添加到该级链表中，再对外分配内存；释放内存时，根据内存页信息直接插入到相应页管理器中。

优缺点

缺点：内存使用率不高；由于每页内存包含一字节内存页信息，实际每页内存少一个字节。
优点：无碎片内存；内存分配释放方式较前面两个版本更快更简单；可根据应用调整内分配策略。

---

Code

//页管理 typedef struct { struct { uint8_t MemLeve : 4; //当前级别 uint8_t MemFather : 4; //父页级别 }MemoryState; //内存状态器 void *NextAddress; //下一页内存位置 }MemoryPageLevelOfNum_t; //内存管理控制器 typedef struct { memlevel_t LevelNum; //分组数量 uint16_t InitFlag; //初始化标志 MemoryPageLevelOfNum_t *MemoryPageLevelOf[MEM_PAGE_LEVEL_MAX]; //页管理器集合 void *MemoryPageBaseAddressOf[MEM_PAGE_LEVEL_MAX]; //各级页起始地址 uint32_t PageNumOfLevel[MEM_PAGE_LEVEL_MAX]; //剩余分级页数量 }MemoryDev_t; 这里包含了，内存管理器的主要定义。 uint8_t MemOneBase[MEM_MAX_SIZE]; //占据一大块内存，用来作为我们内存管理的堆 其中，MEM_BLOCK_SIZE 定义了对齐大小，这里是32字节，也就是自定义的一块内存大小；MEM_MAX_SIZE 定义了需要的内存大小，即用来内存分配的大小。 /** 名 称 ： mallocInit 功 能 ： 内存管理器初始化 输 入 ： _mgs - 分页策略 _coefficient - 分页系数 输 出 ： 说 明 ： */ void mallocInit(MemoryGroupingStrategy_t _mgs,uint8_t _coefficient) { uint32_t membufsize,memgroupsize, i_page,surplusblock; memlevel_t memgrouplevel, i_mem; MemoryPageLevelOfNum_t *mempagelevelbuf; memgrouplevel = MEM_PAGE_LEVEL_MAX; //最大分页等级 membufsize = MEM_MAX_SIZE - sizeof(MemoryDev_t); //内存池大小 membufsize /= MEM_BLOCK_SIZE; //内存池块数 _coefficient = _coefficient ? _coefficient : 1; //系数最小为1 MemoryDev = (MemoryDev_t*)MemOneBase; //将内存起始部分作为内存控制器 MemoryDev->MemoryPageLevelOf[0] = (MemoryPageLevelOfNum_t*)(MemOneBase + sizeof(MemoryDev_t)); switch (_mgs) { case Memory_Strategy_BlockBalanced: { }break; default: { while (membufsize / memgrouplevel < ((1 << memgrouplevel-1)*_coefficient)) { memgrouplevel--; } MemoryDev->LevelNum = memgrouplevel; memgroupsize = membufsize / memgrouplevel; //组内存大小 for (i_mem = 0; i_mem < memgrouplevel; i_mem++) { MemoryDev->PageNumOfLevel[i_mem] = memgroupsize >> i_mem; //每组内存页数量 } for (i_mem = memgrouplevel; i_mem < MEM_PAGE_LEVEL_MAX; i_mem++) { MemoryDev->PageNumOfLevel[i_mem] = 0; } surplusblock = membufsize - memgroupsize * memgrouplevel; } } MemoryDev->PageNumOfLevel[0] += surplusblock; for (i_mem = 1; i_mem < memgrouplevel; i_mem++) { MemoryDev->MemoryPageLevelOf[i_mem] = (MemoryPageLevelOfNum_t*)((uint32_t)MemoryDev->MemoryPageLevelOf[i_mem - 1] + MemoryDev->PageNumOfLevel[i_mem-1] * (1 << (i_mem-1)) * MEM_BLOCK_SIZE); //将内存池按组分割 } for (i_mem = memgrouplevel; i_mem < MEM_PAGE_LEVEL_MAX; i_mem++) { MemoryDev->MemoryPageLevelOf[i_mem] = 0; } for (i_mem = 0; i_mem < memgrouplevel; i_mem++) { mempagelevelbuf = MemoryDev->MemoryPageLevelOf[i_mem]; i_page = MemoryDev->PageNumOfLevel[i_mem]; while(i_page--) { //标记当前内存页等级 mempagelevelbuf->MemoryState.MemLeve = i_mem+1; //标记所属内存页等级 mempagelevelbuf->MemoryState.MemFather = i_mem+1; //链接下一个内存页地址 mempagelevelbuf->NextAddress = (MemoryPageLevelOfNum_t*)((uint32_t)mempagelevelbuf + (1 << i_mem)*MEM_BLOCK_SIZE); mempagelevelbuf = mempagelevelbuf->NextAddress; } } MemoryDev->InitFlag = MEM_INIT_SET; } 初始化的过程，除了按照上面的规则外，还把内存页一页页划分出来，再通过链表的形式把每级的串起来。需要用的时候从链表上将内存页取下；释放的时候再将其放回到相应的链上。 /** 名 称 ：memoryCheckAndAdjust 功 能 ：检测内存页数量是否足够分配，不够向上一级递归借内存页并拆分 输 入 ：_level - 当前内存分组级 _flag - 参数为0时表示第一次调用该函数，不为0时表示该函数正在递归调用 输 出 ：内存足够分配返回0，不够返回其他 说 明 ： */ uint8_t memoryCheckAndAdjust(const memlevel_t _level,uint8_t _flag) { uint8_t result = 0; MemoryPageLevelOfNum_t *mpl_1,*mpl_2; #if 0 //递归 if (0 == MemoryDev->PageNumOfLevel[_level]) { if (0 != memoryCheckAndAdjust(_level + 1,1)) { result = 1; goto error; } } if (0 != _flag) { mpl_1 = memoryPop(&MemoryDev->MemoryPageLevelOf[_level]); MemoryDev->PageNumOfLevel[_level]--; mpl_1->MemoryState.MemLeve = _level; memoryPush(&MemoryDev->MemoryPageLevelOf[_level - 1], mpl_1); mpl_2 = (MemoryPageLevelOfNum_t*)((uint32_t)mpl_1 + (1 << (_level - 1))*MEM_BLOCK_SIZE); mpl_2->MemoryState.MemLeve = mpl_1->MemoryState.MemLeve; mpl_2->MemoryState.MemFather = mpl_1->MemoryState.MemFather; memoryPush(&MemoryDev->MemoryPageLevelOf[_level - 1], mpl_2); MemoryDev->PageNumOfLevel[_level - 1] += 2; } #else //迭代 memlevel_t i_level; for (i_level = _level; MemoryDev->LevelNum > i_level; i_level++) { if (0 != MemoryDev->PageNumOfLevel[i_level]) { break; } } if (_level != i_level) { if (MemoryDev->LevelNum > i_level) { mpl_1 = memoryPop(&MemoryDev->MemoryPageLevelOf[i_level]); MemoryDev->PageNumOfLevel[i_level]--; for (; _level < i_level; i_level--) { mpl_1->MemoryState.MemLeve = i_level; memoryPush(&MemoryDev->MemoryPageLevelOf[i_level - 1], mpl_1); MemoryDev->PageNumOfLevel[i_level - 1]++; mpl_2 = (MemoryPageLevelOfNum_t*)((uint32_t)mpl_1 + (1 << (i_level - 1))*MEM_BLOCK_SIZE); mpl_2->MemoryState.MemLeve = mpl_1->MemoryState.MemLeve; mpl_2->MemoryState.MemFather = mpl_1->MemoryState.MemFather; mpl_1 = mpl_2; } memoryPush(&MemoryDev->MemoryPageLevelOf[i_level], mpl_1); MemoryDev->PageNumOfLevel[i_level]++; } else { result = 1; } } #endif error: return result; } /** 名 称 ：memoryGet 功 能 ：获得相应大小的内存地址 输 入 ：_size - 请求的内存大小 输 出 ：需要的内存地址 说 明 ： */ void* memoryGet(uint32_t _size) { uint8_t count, i; memlevel_t memgrouplevel; void *addr=0; uint32_t block; memgrouplevel = MEM_PAGE_LEVEL_MAX; while (_size < ((1 << memgrouplevel)*MEM_BLOCK_SIZE - 1)) { memgrouplevel--; } memgrouplevel += 1; //内存页拆分调用策略 if (0 != memoryCheckAndAdjust(memgrouplevel,0)) { goto error; } addr = (void*)((uint32_t)memoryPop(&MemoryDev->MemoryPageLevelOf[memgrouplevel])+1); *(uint32_t*)addr = 0; MemoryDev->PageNumOfLevel[memgrouplevel]--; error: return addr; } /** 名 称 ：malloc 功 能 ：申请一块大小为_size的内存 输 入 ：_size - 要申请的内存大小 输 出 ：成功，申请的内存地址；失败，返回0 说 明 ：实际申请的内存可能比需求大 */ void* malloc(size_t _size) { if (MEM_INIT_SET != MemoryDev->InitFlag) { mallocInit(Memory_Strategy_CapacityBalanced,2); } return memoryGet(_size); } 申请内存时，若当前内存页不够，则向上级申请，函数 memoryCheckAndAdjust(const memlevel_t _level,uint8_t _flag) 则是实现该功能的重要环节。 /** 名 称 ：memory Put 功 能 ：将内存放回到内存管理器中 输 入 ：_address - 需要收回的内存地址 输 出 ： 说 明 ： */ void memoryPut(void *_address) { MemoryPageLevelOfNum_t *mpl; memlevel_t level; mpl = (MemoryPageLevelOfNum_t*)((uint32_t)_address - 1); level = mpl->MemoryState.MemLeve; memoryPush(&MemoryDev->MemoryPageLevelOf[level -1], mpl); MemoryDev->PageNumOfLevel[level - 1] ++; error: return; } /** 名 称 ：free 功 能 ：释放申请到的内存 输 入 ：_address - 要释放的内存地址 输 出 ： 说 明 ： */ void free(void *_address) { if (MEM_INIT_SET != MemoryDev->InitFlag) { mallocInit(Memory_Strategy_CapacityBalanced, 2); } else { memoryPut(_address); } } 完整程序

---

（本文仅供参考，转载请标明出处；若有大佬发现错误，请指出。）