这是个人编写的第三版内存管理器，主要用在单片机上。这一系列的内存管理器，由于本人对内存碎片的执念，于是前两版的使用非常反人类。举个例子：

第一版

void** malloc(uint32_t _size,uint8 _userid);

分配出来的是指向地址的地址，这对常规程序来说，用起来的感觉是相当酸爽。

第二版

void* malloc(uint32_t _size,uint8_t _userid,void **_address);

这就比较好看点了，但是还要给一个被分配的指针变量的地址。（内存管理第二版）

上面两个版本，用的一种思路是——知道被分配的地址a的地址b，每当碎片整理时，直接将数据移动到上一块被使用的内存后面，更新地址b上的地址a，得到地址c。
碎片整理前

碎片整理后

将内存块 0x40000020 上的数据 “world” 复制到 内存块 0x40000010 上，并将新的地址更新到指针变量地址 0x20003280 上。
像这样做的优点是，当碎片整理完成后，不影响数据的使用。而缺点是，只能自己玩，并不适合一起用。

但是在某一天，翻资料，看到了linux的内存管理机制后，一下顿悟了，于是有了内存管理器的第三版。

原理

（n块内存组成一页，n页内存组成一组，n组内存）
1. 根据设定的内存大小（不超过物理内存）即内存池，分配 x 组（目前x最大值为1024），根据分配策略限定每组内存大小。
2. 按照 $2^i,i \in [0,x]$的规律，对 $i,i \in [0,x]$组进行分页。
3. 内存分配顺序，由小页到大页，游大端到大端。
4. 当要分配的 $i,i \in [0,x)$组的内存用完时，向$i+1,i \in [0,x)$组内存借一页，使用递归模式，直至没有内存可以分配。
5. 内存释放后，若该内存为借用的，则尝试拼回。
6. 一块内存大小为 $2^i,i>0$字节。

举个例子。
有定义一块内存池，大小为 327680 Bytes，定义一块内存块为 32 字节。将其分成10组，则每组大小为 32 KBytes。

• 当变量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 字节 。
采用组大小均衡方法，使其符条件 $({m \over n} > 2^n * 32) \land( {m \over (n+1)} < 2^{n+1} * 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);
    }
}

完整程序

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