Pooled Allocation(池式分配)范例——Keil 内存管理

引言：说到动态申请（Dynamic Allocation）内存的好处，学过C/C++的人可能都有体会。运行时的灵活申请自然要比编码时的猜测好的多。而在内存受限情况下这种灵活性又有特别的好处——能让我们把有限的内存用的更充分。所以Keil给我们实现了一个简捷的版本，也就是这里所记录的内容。

最近翻看Kei安装目录，无意中发现C51\LIB下的几个.C文件：

CALLOC.C
FREE.C
INIT_MEM.C
MALLOC.C
REALLOC.C

看到 MALLOC.C 和 FREE.C 想到可能和“内存管理”有关。花了半个上午把这个几个文件看完，感觉代码虽然短，确有几个巧妙之处。看的时候也有几处疑问，看完之后豁然开朗。

我首先点开的是calloc.c（因为calloc()平时没怎么用过，最为好奇），看到了这样的代码： 

这个函数很简单，它并没有直接获取内存，而是调用了malloc；看到这样的代码很容易想到——这是一个用来分配动态数组的函数。size是元素大小，len是数组长度。应该是这样用的：

// ...pBase = (int*)calloc(sizeof(int), 10); // 10个整数// ...

  在calloc里看的了 _MALLOC_MEM_ 让人不解，顺着CALLOC.C的#include找上去，看到了：

原来是这个… …（如果有同学不知道xdata是什么，可以简单的理解为“堆”。管它呢！）。

继续点开MALLOC.C（这份代码不短），一看到头部，猜到它可能是个链表：

很明显，这里的next用作链接；但是，len的作用暂时还不能确定(猜测：标识空闲块的长度，注释说的)。它们是这样：

接下来是类型、常量定义定义：

 
由此可知，注释里的free block指的是一个“白色+绿色”。
注意，一旦满足条件（找到一个足够大的空闲块），跳出循环时，p指向这个“够用”的块，q指向p的前驱（与链表方向相反的一块）（如上图p,q）；
往下，k很明确，计算空闲块中剩下的字节数； 
如果剩下的太小（<MIN_BLOCK），直接抛弃之，即将p指向的节点删除，即26行q->next = p->next;并返回空闲内存的地址&p[1]（即绿色的开头处）；
继续往下（够大≥MIN_BLOCK），这四句结合起来才能看得懂：

其中，ret表示返回值，蓝色为调用malloc所返回的内存（称这段“白色+蓝色”的为Allocated block）。 
所以p->len(当前)变成了p->len(初始的)-size-sizeof(__mem__)。
至此，malloc完成，切割后部的一大好处是，对于原来的链表，你只需要修改p->len即可；试想，如果切割前半部分，那么，空闲块内新创建的节点（上图蓝色左边）要插入到原来的空闲链表上，而且被切下的内存块前的节点（上图绿色左边）要从原来的空闲链表上删除，操作相对较麻烦。（嗯，你可以想象从一个挂满腊肉的肉架上切肉，“切下一块直接拿走”总是要比“把大块腊肉拿下，从穿孔的那头切下一块，再将剩下的那块穿上孔挂上架子”要来的简单。）
小结
malloc如此组织内存:用__mem_avail__[0]为链表头结点(因为malloc源码中只用了它的next字段，而没有用到它的len字段)的单链表（称其为free list）连接所有free block，而每个free block的结构如我上图所画，其中包含一个节点struct __mem__，之后是一段长度为len的可用内存。
每次调用malloc(size)时从链表的第一个节点(__mem_avail__[0]->next)开始找，直到找到一个“足够大”（len字段比size大）的free block。如果len比size多出的字节数不多，就直接将这个节点从free list上移除，并直接返回当前的可用内存地址（绿色的开头）；
否则，将该free block切为两段，并将后一段交给malloc返回；实际切下的大小要比size多出一个链表节点的大小，而这多出的一个节点，仅用了len字段，用于记录当前malloc的长度，以便free之时准确将其回收到free list之上。（注：这里有点浪费）
3) FREE.C
有了这一番分析，也能猜得出free是如何做到“内存回收”的。 
前面的类型定义完全一样，这里略去（应该定义到一个.h里，再各自inlcude）。
直接上free的代码，free的注释较为准确：

其中蓝色（memp指向的）为要free的内存，p0所指block与p所指block相邻，所以会发生合并（修改前一个的len值），合并后情形如下： 
 
两个block合并成功！
4) INIT_MEM.C
MALLOC.C和FREE.C中都没有看到数组__mem_avail__的真身（仅用extern做了声明，不会取得内存实体），原来它藏在了INTI_MEM.C里：

然后，在这个内存块（block）内部建立一个节点： 

5) REALLOC.C
有了malloc和free想要实现realloc当然简单，realloc的源码如下：
 
#include <stdlib.h>unsigned char xdata malloc_mempool [0x1000];void tst_init_mempool (void) {  int i;  xdata void *p;  init_mempool (&malloc_mempool, sizeof(malloc_mempool));  p = malloc (100);  for (i = 0; i < 100; i++)    ((char *) p)[i] = i;  free (p);}
开销
Keil提供的此种方案可以让你像标准C程序一样使用malloc和free；这种方式的一大好处是，你可以在此后重复使用一段内存。
想要灵活自然就要付出代价。
空间代价主要在于Allocted block的“头部”，下面就来详细分析： 
在Keil中xdata*和unsigned int都是两个字节，所以一个节点的大小sizeof(__mem__) == 4 
每次malloc(size)的效率就（不考虑free block，即allocated block的利用率）： 
size/(size+4) 
所以你应该尽量多申请一些内存，如果你只申请4个字节，利用率只有50%. 
（据之前malloc分析，其实可以再“抠门”一些，让malloc所得block的头部只记录长度（因为next字段没有使用），每次malloc就少“浪费”两个字节）
时间上，在malloc，free陆续调用多次之后，内存池在也不是当初的一大块了，它将被分为很多个小块，他们被串接在free list之上。 
此时调用malloc就不是那么简单的事了，malloc从free list的头部开始查找，直到找到一个“够大的”free block这个过程是有时间开销的。单链表的查找是O(n)复杂度，但问题是这里的n不能由你直接决定。所以malloc的时间性能也就不那么稳定了。
调用free也是同样，在free list上挂的节点变多时，每次free都要从头开始找，找到能做block的前驱的block（被free源码中的q所指）之后，再将当前的block插入到其后。完成该操作必须修改q所指节点，而你没有指向该block指针，必然要从头查找。所以free通常情况下的时间复杂度是O(n)，这里的n和malloc同样不能确定。
缺陷
要使用malloc，必须先调用init_mempool为malloc，free创建一个“内存池”；通常可以把一个xdata数组的空间交由malloc和free管理。但我们常会纠结：我该给多少字节给Pool？我的MCU可能只有1024个字节可用，也可能更少。如果给多了，我就没有足够的空间存放其他数据了；如果给少了，可能很快malloc就不能从池中取得足够的内存，甚至耗尽整个Pool。而这里的init_mempool只能调用一次；因为如果发生第二次调用，唯一的一个free list的头部（AVIL）会被切断，此前的整个链表都将“失去控制”！
总结
尽管Keil这个方案存在着一些小的缺陷，但是总体来说还是不错的，可以说是——在有限的情况下做到了较好的灵活性。
注： 
1.我所使用的Keil 版本：V4.24.00 for C51 
几个源码文件连接： 
INIT_MEM.C: http://www.oschina.net/action/code/download?code=23770&id=39701 
MALLOC.C: http://www.oschina.net/action/code/download?code=23770&id=39702 
FREE.C: http://www.oschina.net/action/code/download?code=23770&id=39703 
CALLOC.C:http://www.oschina.net/action/code/download?code=23770&id=39704
REALLOC.C:http://www.oschina.net/action/code/download?code=23770&id=39705