MQX心得之动态内存分配

对于习惯上位机编程的程序员而言动态内存分配自然是司空见惯、习以为常，但是对于我们这些折腾MCU开发的，本来小小的芯片里内存就那么几K，哪有什么余地搞动态内存。不过幸好cortex m带来了大堆的大容量的MCU，加上外扩SRAM的能力，使得系统可用的内存已经相当的可观了。但是如何使用这些可观的内存又是一件麻烦的事情，定义成静态变量的话太凌乱，定义成临时变量的话设置堆栈指针不让其出界又是一件麻烦事情。因此我们需要一个良好的动态内存分配机制，充分利用我们的片上宝贵的内存。

动态内存分配一直是操作系统的一个难点。我们很难获得一个又快、安全性高、低碎片率、资源占用小的内存分配算法，说能做的就是根据具体的情况在上述方面中不断折中。linux的buddy和slab算法的确是一个不错的算法，可以相对于MCU的并不富于的资源而言是有点门槛过高了。所以通常嵌入式系统都是采用一种相对而言比较简单、资源占用比较小的动态内存分配算法，其中最常用的就是block机制的算法，就本人所知ucos、rt thread和MQX都是采用的这样的机制。下面我就具体介绍MQX的动态内存分配机制。

MQX的动态内存区域是在我之前“地址空间分布”那篇博文中提及到的KERNEL_DATA_STRUCT下面一直到KERNEL_DATA_END这块区域。由于MQX的动态内存机制内容相当多，我就挑几个关键的部分说明。   这是一个典型的基于BLOCK机制的动态内存分配示意图。图中内存池中一共有5个storeblock。stroeblock是一个最小分配的结构，假设我要动态申请一个大小为1K的内存空间，MQX会给这个内存空间加上一个stroeblock的头来控制它的分配到释放的生命周期。因此一个storeblock的大小为（sizeof（storeblock）+申请大小）4字节对齐后的产物。对于stroeblock头，我们可以看见主要有几个结构，TASK_NUMBER是申请进程的ID，也就是块的所有者；MEM_TYPE是申请内存的类型；BLOCKSIZE是整个完整stroreblock的大小；MEM_POOL_PTR指向分配块的内存池；CHECKSUM是块的校验值，是为了防止块被破坏说做的检查。剩下的NEXTBLOCK、PREVBLOCK和USER_AREA就有些意思了，就字面意思NEXTBLOCK是下一个块，PREVBLOCK是上一个块，但实际不是这么简单的。stroeblock一共有两个状态，要么是空闲的，要么被分配出去了。MQX一共用链表结构来管理那些空闲的块和被分配的块。空闲的块被放在了一个全局的链表POOL_FREE_LIST上面，如图NEXTBLOCK指的是下一个空闲的块，而USER_AREA是指的之前的空闲的块。而PREVBLOCK是指向物理地址连续的上一个块的指针。（不要奇怪结构里为什么没有指向物理地址连续的上一个块的指针，因为只需要通过 当前块指针+BLOCKSIZE 就可以轻松算出来。）

  而对于已经分配的块，MQX用的是任务架构来管理那些块的。

每个被分配出去的storeblock都被一个任务所使用，就算是内核申请的storeblock也是有一个System task的任务的。在task的控制结构体TD_STRUCT_PTR中MEMORY_RESOURCE_LIST是这个task的说申请的stroreblock的链表头，之后每个storeblock的NEXTBLOCK指向下一个已分配的块的USER_AREA，就这样构成了一个单向的链表结构。被分配的块由申请的task控制有很多好处，好处之一就是假设task崩溃后，根据MEMORY_RESOURCE_LIST也能找到所有该task申请的动态内存，系统可以将这些内存释放以防止内存泄漏。

 

  大致介绍完块的结构，下面说一下申请块的过程。具体是这样的，根据申请空间的大小计算出要求块空间的大小。通过POOL_FREE_LIST遍历全部的空闲块，找到一个大小足够的空闲块。由于涉及系统的全局变量，在分配动态内存的操作中，MQX是禁止中断的，但是分配内存是一个花时间的过程，特别是对于一个工作了很长时间非常零碎的内存池而言，可能花费的时间是一些实时性任务说不能接受的。因此MQX在遍历每个空闲块的时候会有一个开启中断的步骤，若是有一个更高优先级的任务就将当前任务切换出去了，返回来之后再继续遍历。这里POOL_ALLOC_CURRENT_BLOCK就是为了这个操作所预留，防止竞争的一个变量。当找到一个空闲块且大小比要求的大小大的时候，就选择这个块了进行分配。这个分配会有两种情况。

  第一种情况是空闲块除去要求分配的块之外还有余量能新建一个空闲块。就将此块一分为二，变成两个空闲块，再将前一个空闲块改为被占用。

 

第二种情况是空闲块没有余量能新建一个空闲块。在这样的情况下，就干脆不要那些多余的内存了，将整个块划为被占用。

 

动态内存的释放要稍微复杂一点。因为牵涉到连续内存块的合并，一共会出现三种情况。

最简单的就是要释放的块前后都是已经被分配的块了，说做的操作就是将这个块变为空闲块就行了。

复杂一点的就是要释放的块后面紧跟着一个空闲块，说要做的就是先删除后面的块，再把要释放的块的吞掉这个被删除块的内存部分，最后将这个块改为空闲块。

最复杂的是这个要释放的块前后都是空闲的块。这样将此块和前面的块合并成一个块 ，再将这个块按照上一幅图的操作合并后面的块，最后完成操作。

 

基于块的动态内存分配机制就差不多了，有图自然很好理解，不过还是要对照相应的源码，源码里面东西很多，我只是简单大致的用图描述了一片，具体细节的东西还是要慢慢琢磨的。有一个动态内存分配的功能是MQX的一大优点，不过这个机制也不是太完美的。特别是分配是没有根据实际空闲块的大小择优分配，只是按照链表的顺序找到一个能分配的就分配，长时间工作下去可能会产生许多内存碎片，而导致无法完成大内存的分配。不过如果想要有上述的功能，增加一个择优分配算法，内存分配的速度就大打折扣了。鱼与熊掌不可得兼，对于MQX的内存分配的特点，我们在使用的时候可以采用多级分配的方式，根据实际需求来建立相应的二级或三级内存池，完成又快稳定的动态内存分配。