最近翻看Kei安装目录，无意中发现C51\LIB下的几个.C文件：
CALLOC.C
FREE.C
INIT_MEM.C
MALLOC.C
REALLOC.C
看到 MALLOC.C 和 FREE.C 想到可能和“内存管理”有关。花了半个上午把这个几个文件看完，感觉代码虽然短，确有几个巧妙之处。看的时候也有几处疑问，看完之后豁然开朗。
1) CALLOC.C
我首先点开的是calloc.c（因为calloc()平时没怎么用过，最为好奇），看到了这样的代码：
1: void _MALLOC_MEM_ *calloc (
2: unsigned int size,
3: unsigned int len)
4: {
5: void _MALLOC_MEM_ *p;
6:
7: size *= len;
8:
9: if ((p = malloc (size)) == NULL)
10: return (NULL);
11:
12: memset (p, 0, size);
13: return (p);
14: }
这个函数很简单，它并没有直接获取内存，而是调用了malloc；看到这样的代码很容易想到——这是一个用来分配动态数组的函数。size是元素大小，len是数组长度。应该是这样用的：
1: int *pBase;
2: // ...
3: pBase = (int*)calloc(sizeof(int), 10); // 10个整数
4: // ...
在calloc里看的了 _MALLOC_MEM_ 让人不解，顺着CALLOC.C的#include找上去，看到了：
1: #define _MALLOC_MEM_ xdata
原来是这个… …（如果有同学不知道xdata是什么，可以简单的理解为“堆”。管它呢！）。
2) MALLOC.C
继续点开MALLOC.C（这份代码不短），一看到头部，猜到它可能是个链表：
1: struct __mem__
2: {
3: struct __mem__ _MALLOC_MEM_ *next; /* single-linked list */
4: unsigned int len; /* length of following block */
5: };
很明显，这里的next用作链接；但是，len的作用暂时还不能确定(猜测：标识空闲块的长度，注释说的)。它们是这样：
接下来是类型、常量定义定义：
1: typedef struct __mem__ __memt__;
2: typedef __memt__ _MALLOC_MEM_ *__memp__;
3:
4: #define HLEN (sizeof(__memt__))
5:
6: extern __memt__ _MALLOC_MEM_ __mem_avail__ [];
7:
8: #define AVAIL (__mem_avail__[0])
9:
10: #define MIN_BLOCK (HLEN * 4)
看到这些typedef，#define也不能确定各自是做什么用的。但是有个extern声明的数组！应该在别的地方有定义。（关于声明和定义不多说了）
然后就是完整的malloc()了（部分注释已被删除）：
1: void _MALLOC_MEM_ *malloc( unsigned int size)
2: {
3: __memp__ q; /* ptr to free block */
4: __memp__ p; /* q->next */
5: unsigned int k; /* space remaining in the allocated block */
6:
7: q = &AVAIL;
8:
9: while (1)
10: {
11: if ((p = q->next) == NULL)
12: {
13: return (NULL); /* FAILURE */
14: }
15:
16: if (p->len >= size)
17: break;
18:
19: q = p;
20: }
21:
22: k = p->len - size; /* calc. remaining bytes in block */
23:
24: if (k < MIN_BLOCK) /* rem. bytes too small for new block */
25: {
26: q->next = p->next;
27: return (&p[1]); /* SUCCESS */
28: }
29:
30: k -= HLEN;
31: p->len = k;
32:
33: q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p [1])) + k);
34: q->len = size;
35:
36: return (&q[1]); /* SUCCESS */
37: }
稍加分析可知，while(1)是循环遍历链表的（循环内的p=q->next和q=p这两句）。所以q一开始指向的应该是链表的头结点，AVAIL即__mem_avail__[0]里存放着链表的头结点。
由16行 if(p->len > size) break; 可知，len的作用确实是用来标识空闲块的长度；
所以整个链表应该是这样的（绿色部分为空闲内存，白色是链表节点）：
由此可知，注释里的free block指的是一个“白色+绿色”。
注意，一旦满足条件（找到一个足够大的空闲块），跳出循环时，p指向这个“够用”的块，q指向p后面（与链表方向相反）的一块（如上图p,q）；
往下，k很明确，计算空闲块中剩下的字节数；
如果剩下的太小（<MIN_BLOCK），直接抛弃之，即将p指向的节点删除，即26行q->next = p->next;并返回空闲内存的地址&p[1]（即绿色的开头处）；
继续往下（够大≥MIN_BLOCK），这四句结合起来才能看得懂：
1: k-=HLEN; // 空闲块内也要创建一个节点
2: p->len=k; // 此时的可用空间已经少size+sizeof(__mem__)
3: q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p [1])) + k); // 这里用的是切割的空闲块的后部
4: q->len = size; // 这个新的节点仅用来记录分割了多少字节（便于free时回收），
5: // 并没有链接为链表，next字段也就没有赋值
最终情形是这样的：
其中，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，在从其上切下一个（size+HLEN）的block（Allocated block）。
如果len比size多出的字节数不多，就直接将这个节点从free list上移除；
否则，将该free block切为两段，并将后一段交给malloc返回；实际切下的大小要比size多出一个链表节点的大小，而这多出的一个节点，仅用了len字段，用于记录当前malloc的长度，以便free之时准确将其回收到free list之上。
3) FREE.C
有了这一番分析，也能猜得出free是如何做到“内存回收”的。
前面的类型定义完全一样，这里略去（应该定义到一个.h里，再各自inlcude）。
直接上free的代码，free的注释较为准确：
1: void free (
2: void _MALLOC_MEM_ *memp)
3: {
4: /*-----------------------------------------------
5: FREE attempts to organize Q, P0, and P so that
6: Q < P0 < P. Then, P0 is inserted into the free
7: list so that the list is maintained in address
8: order.
9:
10: FREE also attempts to consolidate small blocks
11: into the largest block possible. So, after
12: allocating all memory and freeing all memory,
13: you will have a single block that is the size
14: of the memory pool. The overhead for the merge
15: is very minimal.
16: -----------------------------------------------*/
17: __memp__ q; /* ptr to free block */
18: __memp__ p; /* q->next */
19: __memp__ p0; /* block to free */
20:
21: /*-----------------------------------------------
22: If the user tried to free NULL, get out now.
23: Otherwise, get the address of the header of the
24: memp block (P0). Then, try to locate Q and P
25: such that Q < P0 < P.
26: -----------------------------------------------*/
27: if ((memp == NULL) || (AVAIL.len == 0))
28: return;
29:
30: p0 = memp;
31: p0 = &p0 [-1]; /* get address of header */
32:
33: /*-----------------------------------------------
34: Initialize.
35: Q = Location of first available block.
36: -----------------------------------------------*/
37: q = &AVAIL;
38:
39: /*-----------------------------------------------
40: B2. Advance P.
41: Hop through the list until we find a free block
42: that is located in memory AFTER the block we're
43: trying to free.
44: -----------------------------------------------*/
45: while (1)
46: {
47: p = q->next;
48:
49: if ((p == NULL) || (p > memp))
50: break;
51:
52: q = p;
53: }
54:
55: /*-----------------------------------------------
56: B3. Check upper bound.
57: If P0 and P are contiguous, merge block P into
58: block P0.
59: -----------------------------------------------*/
60: if ((p != NULL) && ((((char _MALLOC_MEM_ *)memp) + p0->len) == p))
61: {
62: p0->len += p->len + HLEN;
63: p0->next = p->next;
64: }
65: else
66: {
67: p0->next = p;
68: }
69:
70: /*-----------------------------------------------
71: B4. Check lower bound.
72: If Q and P0 are contiguous, merge P0 into Q.
73: -----------------------------------------------*/
74: if ((((char _MALLOC_MEM_ *)q) + q->len + HLEN) == p0)
75: {
76: q->len += p0->len + HLEN;
77: q->next = p0->next;
78: }
79: else
80: {
81: q->next = p0;
82: }
83: }
12~13行，求得当前malloc所得block的节点结构。
17~25行的while(1)仍然是遍历链表，但退出条件已经不一样了，
变成了：if ((p == NULL) || (p > memp))，退出时p指向的free block在memp之后，q在memp之前。
如图：
后面的两个if做检查，如果memp所在的block和p,q某一或两个相邻都将被合并为一个free block，否则只将他们所在的free block节点链接起来。如下，memp所在free block和q所指向的free block相邻的情形：
其中蓝色（memp指向的）为要free的内存，p0所指block与p所指block相邻，所以会发生合并（修改前一个的len值），合并后情形如下：
两个block合并成功！
4) INIT_MEM.C
MALLOC.C和FREE.C中都没有看到数组__mem_avail__的真身（仅用extern做了声明，不会取得内存实体），原来它藏在了INTI_MEM.C里：
1: __memt__ _MALLOC_MEM_ __mem_avail__ [2] =
2: {
3: { NULL, 0 }, /* HEAD for the available block list */
4: { NULL, 0 }, /* UNUSED but necessary so free doesn't join HEAD or ROVER with the pool */
5: };
INIT_MEM.C还定义了一个重要的函数：
void init_mempool (
void _MALLOC_MEM_ *pool, // address of the memory pool
unsigned int size); // size of the pool in bytes
其源码如下：
1: void init_mempool (
2: void _MALLOC_MEM_ *pool,
3: unsigned int size)
4: {
5:
6: /*-----------------------------------------------
7: If the pool points to the beginning of a memory
8: area (NULL), change it to point to 1 and decrease
9: the pool size by 1 byte.
10: -----------------------------------------------*/
11: if (pool == NULL) {
12: pool = 1;
13: size--;
14: }
15:
16: /*-----------------------------------------------
17: Set the AVAIL header to point to the beginning
18: of the pool and set the pool size.
19: -----------------------------------------------*/
20: AVAIL.next = pool;
21: AVAIL.len = size;
22:
23: /*-----------------------------------------------
24: Set the link of the block in the pool to NULL
25: (since it's the only block) and initialize the
26: size of its data area.
27: -----------------------------------------------*/
28: (AVAIL.next)->next = NULL;
29: (AVAIL.next)->len = size - HLEN;
30:
31: }
由这段代码印证了malloc源码中AVAIL为头结点的猜想，16~19行的注释可以看到，AVIL.len记录的是内存池的大小，而非一般节点的空闲内存的字节数。
这里的过程是这样的：
首先，将头结点指向内存（block）块的首地址pool，再将len修改为size（内存块的长度）。
然后，在这个内存块（block）内部建立一个节点：
5) REALLOC.C
有了malloc和free想要实现realloc当然简单，realloc的源码如下：
1: void _MALLOC_MEM_ *realloc (
2: void _MALLOC_MEM_ *oldp,
3: unsigned int size)
4: {
5: __memp__ p0;
6: void _MALLOC_MEM_ *newp;
7:
8: if ((oldp == NULL) || (AVAIL.len == 0))
9: return (NULL);
10:
11: p0 = oldp;
12: p0 = &p0 [-1]; /* get address of header */
13:
14: if ((newp = malloc (size)) == NULL)
15: {
16: return (NULL);
17: }
18:
19: if (size > p0->len)
20: size = p0->len;
21:
22: memcpy (newp, oldp, size);
23: free (oldp);
24:
25: return (newp);
26: }
注：realloc可以理解为具有“延长”动态数组能力的一个函数，在你一次malloc的内存不够长时可以调用它；当然，你也可以直接调用它，但那么做事不安全的。
因果
可能你会有疑问：为什么在Keil中会有init_mempool？为什么Keil的malloc，free这么复杂（VC的malloc，free就很简单）？
用过Keil的朋友都知道，Keil是用来开发嵌入式软件的，它编译出来的可执行文件不是windows的PE格式也不是Linux的ELF格式，而是HEX-80。
有必要提一下VC中malloc的实现，VC中malloc调用了HeapAlloc，HeapAlloc是Windows API，实现从堆中申请内存的功能，除此之外，Windows API还提供了功能和realloc相似的HeapReAlloc，以及功能和相似的HeapFree。所以VC中malloc，free的实现要比Keil中简单。
VC的编译的目标程序是在Windows上运行的，而windows系统本身已经提供了一套内存管理的功能（API就是使用这些功能的一种方式），所以其上的应用程序不需要写太多的内存管理的代码（Windows已经为你做好了）。VC编译出来的程序调用malloc，malloc调用HeapAlloc，而HeapAlloc的原型是：
1: LPVOID WINAPI HeapAlloc(
2: _In_ HANDLE hHeap,
3: _In_ DWORD dwFlags,
4: _In_ SIZE_T dwBytes
5: );
传入的hHeap参数必须是一个可用的“堆”（通常用HeapCreate），就和init_mempool一样，HeapAlloc调用前也需要先调用HeapCreate，以及其他环境的初始化操作，只是这些都是运行库（Runtime Library）做的事。Windows程序运行在操作系统之上，操作系统和运行库会为你准备好一切；而这些我们是看不到的，所以看到这里的init_mempool可能会感到有点奇怪。
而Keil是编译的程序往往是在裸机（没有操作系统）上运行的，所以你要想有“内存管理”的功能，就要你自己实现，而Keil的开发商早已想到了这点，所以他们帮你你实现了一个版本（即这里介绍的），你可以直接使用它。
应用
关于这个几个函数如何应用，Keil的帮助文档里给出了一个实例：
1: #include <stdlib.h>
2:
3: unsigned char xdata malloc_mempool [0x1000];
4:
5: void tst_init_mempool (void) {
6: int i;
7: xdata void *p;
8:
9: init_mempool (&malloc_mempool, sizeof(malloc_mempool));
10:
11: p = malloc (100);
12:
13: for (i = 0; i < 100; i++)
14: ((char *) p)[i] = i;
15:
16: free (p);
17: }
开销
Keil提供的此种方案可以让你像PC上的程序一样使用malloc和free；这种方式的一大好处是，你可以在此后重复使用一段内存。
想要灵活自然就要付出代价。
这里的代价主要在于Allocted block的“头部”，下面就来详细分析：
在Keil中xdata*和unsigned int都是两个字节，所以一个节点的大小sizeof(__mem__) == 4
每次malloc(size)的效率就（不考虑free block，即allocated block的利用率）：
size/(size+4)
所以你应该尽量多申请一些内存，如果你只申请4个字节，利用率只有50%.
（据之前malloc分析，其实可以再“抠门”一些，让malloc的头部只有两个字节，每次malloc就少“浪费”两个字节）
除此之外，在malloc，free陆续调用多次之后，内存池在也不是当初的一大块了，它将被分为很多个小块，他们被串接在free list之上。此时再调用malloc就不是那么简单的事了，malloc从free list的头部开始查找，直到找到一个“够大的”free block这个过程是有时间开销的。单链表的查找是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