使用RT-Thread小内存分配算法，为单片机编写简易动态内存管理库

零、目录

目录

零、目录

一、注意事项

二、算法核心

三、_alloc() / _free() 与其他函数

四、内存使用报告

五、实战

一、注意事项

1. 本动态内存管理库参考了 rt thread 的小内存管理算法。但是请注意，本库在部分函数的实现，以及部分功能的实现效果上，可能会有的区别。
2. 实现基本的内存管理函数，包括 alloc/realloc/calloc/free 等。
3. 本库主要为单片机裸机而编写，同时也是为学习动态内存分配知识做了一个小的总结。
4. 本库是所有函数/结构体/重要的宏均以 dmem 开头，即 dynamic memory 动态内存。
5. 开源地址：https://github.com/SouthernSandbox/dmem

二、算法核心

由于小内存算法的讲解文章有很多，这里主要为这次自己复刻实现的库的实现做简要的说明。

2.1. 内存管理器与内存块信息结构体

2.1.1. 内存管理器（struct dmem_mgr）

        用于管理全局信息，存储包括首/尾/空闲节点指针成员变量（这里的节点指的是内存块信息结构体）、内存池指针、内存池大小等成员变量。

/**
 * @brief 内存块管理器
 */
struct dmem_mgr
{
    char* pool;                     /** 内存池 **/
    unsigned int size;              /** 内存池大小 **/
    unsigned int free;              /** 当前空闲的内存大小 **/
    unsigned int max_usage;         /** 记录内存消耗的最大值 @note 记录所有的非空闲内存的占用，包括内存块消息结构体 **/
    unsigned int inited_free;       /** 记录初始化时，空闲内存块的大小 **/
    dmem_block_t bhead;             /** 首内存块且始终指向首内存块 **/
    dmem_block_t btail;             /** 尾内存块且始终指向尾内存块 **/
    dmem_block_t bfree;             /** 始终指向第一个空闲内存块 **/
};
static struct dmem_mgr mgr = {0};


/**
 * @brief 初始化动态内存分配管理
 * @param pool 
 * @param size 
 * @return int 
 */
int dmem_init(void* pool, unsigned int size)
{
    if(pool == NULL)
        return -1;
    if(size == 0)
        return -2;
    mgr.pool = (char*) pool;
    mgr.size = size;

    mgr.bhead = (dmem_block_t) dmem_pool_at(0);
    mgr.bhead->magic = dmem_block_magic();
    mgr.bhead->prev = dmem_block_offset(dmem_head_block());
    mgr.bhead->used = false;

    mgr.btail = (dmem_block_t) dmem_pool_at(dmem_pool_size() - dmem_block_size());
    mgr.btail->magic = dmem_block_magic();
    mgr.btail->prev = dmem_block_offset(dmem_head_block());
    mgr.btail->used = true;

    mgr.bhead->next = dmem_block_offset(dmem_tail_block());
    mgr.btail->next = dmem_block_offset(dmem_tail_block());

    mgr.bfree = dmem_head_block();

    mgr.free = dmem_block_mem_size(dmem_head_block());
    mgr.max_usage = dmem_pool_size() - mgr.free;
    mgr.inited_free = mgr.free;

    return 0;
}

2.1.2. 内存块信息结构体（struct dmem_block）

        一个内存块信息结构体管理一块内存，并记录其使用情况。每个内存块信息结构体通过前后索引（利用整形变量了，通过偏移量来记录前后结构体的位置，而非用指针）相互连接，构成一个链表。

        内存块信息结构体是存放于内存池中的，也就是说，内存块信息结构体会占用一定量的内存池空间。例如，对于一篇 1024 字节大小的内存池，用户实际能分配到的内存块的大小一定小于 1024 字节。

        内存块信息结构体的大小为 12 字节。

        每个内存块信息结构体都有一个特殊的幻数（magic，本库使用 0xf00d 作为幻数），这个幻数既可以作为内存块信息结构体的标识，又可以作为一个检查点，如果幻数被修改，则说明出现了内存泄漏/越界等问题。

        一个空闲的内存块的大小不够再划分新的空闲内存块时，将直接令这个空闲内存块变为已分配内存块；如果一个空闲内存块足够大，则会依据用户请求的大小，划分出已分配的内存块作为返回，并用剩余的内存新建一个空闲的内存块。

/**
 * @brief 内存块信息结构体
 */
struct dmem_block
{
    unsigned short magic;
    bool used;
    unsigned int prev, next;
};

2.1.3. 辅助宏

        为使得代码更加易懂，编写了一些列宏用于提高代码的可读性

#define dmem_pool_at(offset)            (mgr.pool + (offset))
#define dmem_pool_size()                (mgr.size)
#define dmem_block_magic()              (0xf00d)
#define dmem_block_size()               (sizeof(struct dmem_block))
#define dmem_head_block()               (mgr.bhead)
#define dmem_tail_block()               (mgr.btail)
#define dmem_free_block()               (mgr.bfree)
#define dmem_block_offset(block)        (unsigned int)((char*)(block) - (char*)(dmem_head_block()))
#define dmem_min_alloc_size()           (dmem_block_size())
#define dmem_block_mem_size(block)      ((block)->next - dmem_block_offset(block) - dmem_block_size())
#define dmem_block_mem_addr(block)      (((char*)(block)) + dmem_block_size())
#define dmem_block_prev(block)          ((dmem_block_t) dmem_pool_at((block)->prev))
#define dmem_block_next(block)          ((dmem_block_t) dmem_pool_at((block)->next))
#define dmem_block_entry(mem)           ((dmem_block_t)(((char*)mem) - dmem_block_size()))
#define dmem_block_is_valid(block)      ((block)->magic == dmem_block_magic())
#define dmem_block_is_unused(block)     ((!(block)->used) && dmem_block_is_valid(block))

2.2. 首节点、尾节点与空闲节点指针

        在前面提到内存管理器的时候，提到了首/尾/空闲节点指针成员变量，他们的功能如下：

1. 首节点指针（mgr.bhead）：永远指向首节点。首节点在初始化时，会将除尾节点以外的所有内存区域都作为空闲内存，首次分配内存时一定是从首节点开始进行分配。首节点的 prev 永远指向自己
2. 尾节点指针（mgr.btail）：永远指向尾节点。尾节点实际并不管理任何内存，且永远处于已使用状态。尾节点位于内存池的最后 12 字节处，且尾节点的 next 永远指向自己。
3. 空闲节点指针（mgr.bfree）：永远指向第一个空闲内存块。这个指针的作用就是进行快速内存分配，因为它一定指向一个空闲的内存块（如果没有可用内存，它将指向 NULL），即便是它指向的内存块不够分配，遍历内存块信息结构体链表时，也无需从头开始遍历，从空闲节点指针指向的节点处遍历即可，也可提高搜索效率。

2.3. 偏移量

        本库的偏移量的使用主要用于以下情况：

1. 已知一个 struct dmem_block 对象，获取其管理的内存 mem；
2. 已知一个被管理的内存 mem，获取其对应的 struct dmem_block 对象；
3. 已知一个 struct dmem_block 对象，获取其前一个/后一个 struct dmem_block 对象；
4. 已知一个 struct dmem_block 对象，获取其相较于 mgr.bhead 的偏移量。

        以上这些需求都以在辅助宏中定义，便于使用。

2.4. 减少内存碎片的产生

        小内存管理算法通过合并相邻的空闲内存块来达到减少空闲内存的目的。

        在本库中，参考了 rt thread，每个内存块的最小分配内存大小为 12 字节，例如，用户申请 4 字节大小的内存，实际在内存池中，将会分配 12 字节的内存（此处未被使用到的内存虽然也是一种内存碎片，但最小可分配内存的设计可能是一种权衡的结果）。

三、_alloc() / _free() 与其他函数

        在本库中，最重要的两个函数为 _alloc() 和 _free() 两个静态函数，这两个函数主管了内存的分配与释放逻辑。 

        _alloc() 的实现如下：

/**
 * @brief 依据指定的大小分配内存
 * @note 该函数不具备线程安全
 * @param size 
 * @return void* 
 */
static void* _alloc(unsigned int size)
{
    if(size <= 0)
        return NULL;
    if(size < dmem_min_alloc_size())
        size = dmem_min_alloc_size();
    if(dmem_free_block() == NULL)
        return NULL;

    /** 遍历，搜寻可用的内存块 **/
    dmem_block_t pos = dmem_free_block();
    for( ; pos != dmem_tail_block(); pos = dmem_block_next(pos))
    {
        if(!dmem_block_is_unused(pos))
            continue;
        if(dmem_block_mem_size(pos) < size)
            continue;
        
        /**
         * 匹配成功，剩余空间是否还可以创建新的空闲内存块，
         * 如果无法创建新的内存块，则将剩余的空闲内存全部分配，
         * 避免出现无法被管理的内存碎片
         */
        int free = dmem_block_mem_size(pos) - size;
        if(free < (dmem_min_alloc_size() + dmem_block_size()))
        {

        }
        else 
        {
            /** 创建新的空闲内存块 **/
            dmem_block_t next = (dmem_block_t)(((char*)pos) + dmem_block_size() + size);
            dmem_block_t nn = dmem_block_next(pos);
            next->magic = dmem_block_magic();
            next->used = false;
            next->prev = dmem_block_offset(pos);
            next->next = dmem_block_offset(nn);
            pos->next = dmem_block_offset(next);
            nn->prev = dmem_block_offset(next);

            mgr.free -= dmem_block_size();
        }
        pos->used = true;

        /** 更新 bfree **/
        dmem_free_block() = _search_free_block_for_alloc(pos);

        /** 更新管理器记录 **/
        mgr.free -= dmem_block_mem_size(pos);
        _update_max_usage();

        return dmem_block_mem_addr(pos);
    }
    return NULL;
}

        _free() 的实现如下： 

/**
 * @brief 释放被分配的内存
 * @note 该函数不具备线程安全
 * @param mem 
 */
static void _free(void* mem)
{
    dmem_block_t block = dmem_block_entry(mem);
    /** 检查内存块合法性 **/
    if(!dmem_block_is_valid(block))
        return;
    /** 检查内存释放被占用 **/
    if(!block->used)
        return;
    /** 重置标志位 **/
    block->used = false;
    /** 更新管理器记录 **/
    mgr.free += (dmem_block_mem_size(block));

    // 检查上一个节点，如果空闲，则进行合并
    if(dmem_head_block() != block)   // 忽略当前内存块是首节点的情况
    {
        dmem_block_t prev = dmem_block_prev(block);
        if(dmem_block_is_unused(prev))
        {
            dmem_block_t bn = dmem_block_next(block);
            block->prev = prev->prev;
            *prev = *block;
            block = prev;
            bn->prev = dmem_block_offset(block);
            /** 更新管理器记录 **/
            mgr.free += dmem_block_size();
        }
    }

    // 检查下一个节点，如果空闲，则进行合并
    {
        dmem_block_t next = dmem_block_next(block);
        // 忽略下一个节点是尾节点的情况
        if(dmem_block_is_unused(next))   
        {
            dmem_block_t nn = dmem_block_next(next);
            block->next = next->next;
            nn->prev = dmem_block_offset(block);
            /** 更新管理器记录 **/
            mgr.free += dmem_block_size();
        }
    }

    /** 重置 bfree **/
    if(dmem_free_block() - block > 0 )
        dmem_free_block() = block;

    /** 更新管理器记录 **/
    _update_max_usage();
}

        _search_free_block_for_alloc() 仅在 _alloc() 中使用，用于重新为 mgr.bfree 查找新的 “第一块空闲内存块”。

        _search_free_block_for_alloc() 的实现逻辑如下：

1. 如果当前 mgr.bfree 指向的 “第一个空闲内存块” 没有被分配，则直接返回当前的  “第一个空闲内存块”。
2. 如果当前 mgr.bfree 指向的 “第一个空闲内存块” 已分配，则说明，其下一个内存块 next 要么是空闲的，要么是已分配的；如果是空闲的，则 next 一定是新的 “第一个空闲内存块”（因为在 _alloc() 中不会存在新的内存释放的情况，而新诞生的空闲内存也只会出现在本内存块之后）；如果 next 不是空闲的，则从当前内存块开始遍历，直到找到新的 “第一个空闲内存块”。

        如果查找失败，则返回 NULL。

/**
 * @brief 查找第一个空闲内存块
 * @note 该函数仅在 _alloc() 中调用
 * @param start 
 * @return dmem_block_t 
 */
static dmem_block_t _search_free_block_for_alloc(dmem_block_t start)
{
    if(dmem_block_is_unused(dmem_free_block()))
        return dmem_free_block();
    else
    {
        dmem_block_t pos = dmem_block_next(start);
        if(dmem_block_is_unused(pos))
            return pos;
        else 
        {
            for( ; pos != dmem_tail_block(); pos = dmem_block_next(pos))
                if(dmem_block_is_unused(pos))
                    return pos;
            return NULL;
        }
    }
}

        _update_max_usage() 用于更新最大内存消耗情况（这里的内存消耗包含了内存块信息结构体）。 

/**
 * @brief 更新最大内存消耗
 */
static void _update_max_usage(void)
{
    int usage = dmem_pool_size() - mgr.free;
    if(usage > mgr.max_usage)
        mgr.max_usage = usage;
}

         dmem_alloc() / dmem_realloc() / dmem_calloc() / dmem_free() 为 _alloc() 和 _free() 的进一步封装，但是加入了线程锁接口，具备线程安全的功能。

/**
 * @brief 依据指定的大小安全地分配连续的空间
 * @param size 
 * @return void* 
 */
void* dmem_alloc(unsigned int size)
{
    dmem_get_lock();
    void* p = _alloc(size);
    dmem_rel_lock();
    return p;
}

/**
 * @brief 依据指定的大小重新分配新的连续的空间，并释放旧的已分配内存
 * @param old_mem 旧的被分配的内存
 * @param new_size 新的被指定的内存大小
 * @return void* 
 */
void* dmem_realloc(void* old_mem, unsigned int new_size)
{
    /** 如果当前的内存块的实际可用内存大小符合新指定的内存大小，则直接返回 **/
    dmem_block_t block = dmem_block_entry(old_mem);
    if(dmem_block_mem_size(block) >= new_size)
        return old_mem;
    /** 尝试分配新的内存 **/
    dmem_get_lock();
    void* p = _alloc(new_size);
    if(p)
        _free(old_mem);
    dmem_rel_lock();
    return p;
}

/**
 * @brief 分配指定大小和数量的连续空间，并自动将已分配的内存初始化为 0
 * @param count 对象的数量
 * @param size 对象的大小
 * @return void* 
 */
void* dmem_calloc(unsigned int count, unsigned int size)
{
    dmem_get_lock();
    int total = count * size;
    void* p = _alloc(total);
    if(p)
        memset(p, 0, total);
    dmem_rel_lock();
    return p;
}

/**
 * @brief 安全地释放被分配的内存
 * @param mem 
 */
void dmem_free(void* mem)
{
    dmem_get_lock();
    _free(mem);
    dmem_rel_lock();
}

         线程锁在 dmem_porting.c 中定义，便于用户进行移植。

#include "dmem.h"

/**
 * @brief 获取线程锁
 * @return int 
 */
int dmem_get_lock(void)
{
    return 0;
}

/**
 * @brief 释放线程锁
 * @return int 
 */
int dmem_rel_lock(void)
{
    return 0;
}

四、内存使用报告

        struct dmem_use_report 结构体和 dmem_get_use_report() 提供一个方便用户更好地了解当前内存的使用情况的接口，可以便于用户优化程序内存的使用。

/**
 * @brief 内存使用报告结构体
 */
struct dmem_use_report
{
    unsigned int free;              /** 当前空闲内存大小 **/
    unsigned int max_usage;         /** 该函数记录了所有的内存消耗（包括但不限于用户申请的内存大小） **/
    unsigned int initf;             /** 初始化时，空闲内存的大小 **/
    unsigned int used_count;        /** 当前尚未释放的内存块数量 **/
};

/**
 * @brief 获取内存使用报告
 * @return struct dmem_use_report* 
 */
struct dmem_use_report* dmem_get_use_report(void)
{
    dmem_get_lock();
    static struct dmem_use_report report = {0};
    report.free = mgr.free;
    report.max_usage = mgr.max_usage;
    report.initf = mgr.inited_free;
    report.used_count = 0;
    dmem_block_t pos = NULL;
    for(pos = dmem_head_block(); pos != dmem_tail_block(); pos = dmem_block_next(pos))
        if(!dmem_block_is_unused(pos))
            report.used_count++;
    dmem_rel_lock();
    return &report;
}

五、实战

        本次实战使用沁恒的 MCU 作为主控，通过仿照 rt thread 的做法，将 MCU 剩余未使用到的内存全部作为堆区。步骤如下：

1. 将 dmem 库的文件移植到项目中，共涉及以下文件：
   

   dmem_conf.h	配置头文件
   dmem.h	dmem 库头文件
   dmem.c	dmem 源文件
   dmem_porting.c	dmem 移植接口

2. 修改 link.ld，修改栈区的大小，添加堆区的信息。因为 link.ld 默认将剩余未使用的内存作为栈区，且仅指定了栈结束的位置，因此此处重新设置栈结束的位置，并设置栈大小为 2048，之后新建堆区，并获取堆区的起始地址，变量 __dmem_start 将传递到 C 文件中使用。

       /** 栈区：官方仅提供了栈尾的位置（默认为 RAM 尾，即 RAM 剩余没有使用的部分均为栈），
   	 * 因此栈的大小需要用户自己设置。
   	 */
   	.stack :
   	{
   		. = ALIGN(4);
   		PROVIDE(_susrstack = . );		
   		. = . + __stack_size;		/** 定位计数器偏移，其中的空间将用作栈区 **/
   		. = ALIGN(4);
   		PROVIDE(_eusrstack = . );	/** 栈尾，该变量将用于 startup_CH583.s 中，指定栈的尾部 **/
   	} >RAM  
   
   	/** 将剩余的 RAM 空间用于 dmem 的堆区 **/
   	.dmem_heap :
   	{
   		. = ALIGN(4);
   		PROVIDE(__dmem_start = .);
   	} >RAM  

3. 创建宏，得出 RAM 的大小 / 堆区大小 / 堆区起始地址 等重要信息，并传递给 dmem_init() 进行堆区的初始化。

   extern int __dmem_start;
   
   #define RAM_START_ADDR      (0x20000000)
   #define RAM_SIZE            (32 * 1024)
   #define HEAP_END_ADDR       (RAM_START_ADDR + RAM_SIZE)
   #define HEAP_BEGIN          ((void*)&__dmem_start)
   #define HEAP_SIZE           (int)(HEAP_END_ADDR - (int)HEAP_BEGIN)
   
   static void _hw_system_heap_init(void)
   {
       dmem_init(HEAP_BEGIN, HEAP_SIZE);
   }

4. 使用 dmem_alloc() 分配内存。此处新建 3 个自定义 mysh 控制台指令，如果分配成功，则单片机运行后，可以在串口控制台查看到注册好的自定义指令，并可执行。

   static void _ld_cmd_exec(int argc, char* argv[])
   {
       extern int __stack_size;
       extern int _susrstack;
       extern int _eusrstack;
       extern int __dmem_start;
   
       log_i("ram   {range: %x ~ %x, size: %x}", RAM_START_ADDR, RAM_START_ADDR + RAM_SIZE, RAM_SIZE);
       log_i("stack {range: %x ~ %x, size: %x}", (int)&_susrstack, (int)&_eusrstack, (int)&__stack_size);
       log_i("heap  {range: %x ~ %x, size: %x}", (int)&__dmem_start, RAM_START_ADDR + RAM_SIZE, RAM_START_ADDR + RAM_SIZE - (int)&__dmem_start);
   }
   
   
   static void _hv_cmd_exec(int argc, char* argv[])
   {
       if(argc == 3)
       {
           char* end_ptr = NULL;
           void* start = (void*) strtoul(argv[1], &end_ptr, 16);
           unsigned int len = (unsigned int) strtoul(argv[2], &end_ptr, 10);
   
           struct hexview* hv = mdw_hexview_get_act();
           hv_print(hv, start, len);
       }
       else
       {
           log_e("%s argument error", __func__);
       }
   }
   
   static void _free_cmd_exec(int argc, char* argv[])
   {
       struct dmem_use_report* report = dmem_get_use_report();
       log_i("free: %d", report->free);
       log_i("max usage: %d", report->max_usage);
       log_i("leak: %d", report->used_count);
   }
   
   
   int main(void)
   {
       // ... 已忽略的代码
   
       struct mysh_cmd_dsc* cmd = NULL;
   
       cmd = dmem_alloc(sizeof(struct mysh_cmd_dsc));
       cmd->name   = "ld";
       cmd->man    = "print link script information";
       cmd->exec   = _ld_cmd_exec;
       mysh_add_cmd(cmd);
   
       cmd = dmem_alloc(sizeof(struct mysh_cmd_dsc));
       cmd->name   = "hv";
       cmd->man    = "hv <start (0x...) > <len>, print hex data table of selected address";
       cmd->exec   = _hv_cmd_exec;
       mysh_add_cmd(cmd);
   
       cmd = dmem_alloc(sizeof(struct mysh_cmd_dsc));
       cmd->name   = "free";
       cmd->man    = "print memory usage";
       cmd->exec   = _free_cmd_exec;
       mysh_add_cmd(cmd);
   
       // ... 已忽略的代码
   }
   

5. 效果：分别输入 ld / free / hv 三个自定义指令，查看内存池地址/当前内存使用情况，并打印当前内存池前 128 字节的实际数据情况。在最下面的十六进制视图中可以看到红色标记的 0xf00d 幻数以及绿色标记的 used 成员变量。                                                                                  

六、总结

1. 小内存管理算法还是比较易懂的，自己实现一遍可以更加有助于加深对小内存管理算法的理解。
2. 目前 dmem 库虽然提供了线程锁的功能，但并没有在多线程环境下实战过，目前的测试仍然是基于裸机，对于多线程测试之后有时间再试试。
3. 这次不仅了解到小内存算法的运行机制，还为了能实现 rt thread 系统内存堆的初始化，特意简单学习了一下链接脚本的语法并成功将沁恒芯片的剩余内存转化为了堆区。

作者：SouthSandbox