KeilC动态内存管理机制分析及改进.doc

2．（ 6068a ）《 Keil C 动态内存管理机制分析及改进 ※ 》P 74
全文如下：
Keil C 动态内存管理机制分析及改进
丁明亮 熊真春
[摘要]通过对C51中init_mempool, malloc, free三个函数源代码的分析，深入分析C51的动态内存管理机制，同时也给出一些使init_mempool函数更完善和除去free函数中的一个错误的建议。
[关键词] C51 动态内存管理 分析
Abstract: based on the analysis to sources of function init_mempool, malloc and free, this article probes the dynamic memory management of C51 Library, and gives out some advices to better function init_mempool and to clear a bug of function free.
Key words: C51 dynamic memory management
5

0.前言
Keil C是常用的嵌入式系统编程工具，它通过init_mempool，mallloc，free等函数，提供了动态存储管理管理等功能。本文希望通过init_mempool，mallloc，free三个Keil C库函数源代码的分析，揭示了其实现的原理和方法，也对其中的不足作了改进，以使Keil C 编程人员更好地应用动态存储管理。
1．相关数据结构、变量及说明
在Keil C安装目录下的 \c51\lib目录下，有实现init_mempool，mallloc，free三个函数的C源文件init_mem.c，malloc.c，free.c，下面针对keil C7.5A版，将其中与动态存储管理相关的数据结构介绍如下：
#define _MALLOC_MEM_ xdata /*该行在stdlib.h文件中*/
struct __mem__
{
struct __mem__ _MALLOC_MEM_ *next; /* 单链表 */
unsigned int len; /*下一块长度 */
};
该结构的next指向堆中的下一空闲内存块，len表示该空闲块除去该块首部的struct __mem__
结构所占的字节数后，该块实际可用的字节数。由于next 是一个指向XDATA区的指针，故在Keil C中应用程序所定义的堆空间应在XDATA段中定义。
在Keil C中，堆中的所有的空闲内存块是用一个单链表来管理的，struct _mem_即为该链表结点的结构，后面定义的宏AVAIL为该链表的首结点，为叙述方便，以下将该链表称为AVAIL链表。

typedef struct__mem__ __memt__;
typedef __memt__ _MALLOC_MEM_ *__memp__;

__memt__ _MALLOC_MEM_ __mem_avail__ [2] =
{
{ NULL, 0 }, /*堆中空闲内存块头结点 */
{ NULL, 0 }, /* 未使用，但对free函数防止丢失堆空间或误将链表头加入到堆空间，却是必须的 */
/*作者注：__mem_avail__ [1]的存在，并不能防止堆丢失，见后面free函数分析*/
};
#define AVAIL (__mem_avail__[0])
全局数组__mem_avail__实际也是struct __mem__类型，__mem_avail__[0]的next指向堆中首块空闲块，如堆中已无空闲内存块，则__mem_avail__[0]的next为NULL（0值）。为使程序代码简洁，定义了宏AVAIL 来代替__mem_avail__[0]。
2． init_mempool函数剖析
函数int init_mempool ( void _MALLOC_MEM_ *pool, unsigned int size)失败时将返回0，成功则返回-1，参数pool 指向应用程序定义的堆空间，参数size为堆空间的字节数。如果应用程序提供的堆空间太小（size的值太小），将失去实际意义，故函数将返回0表示失败。当size参数足够大，则会初如化AVAIL（即__mem_avail__[0]），使其next域指向pool参数所指向的堆空间，len域为pool参数所指向的堆空间的总字节数size。其在Keil C 7.5A库中init_mem.c的源代码如下所示。
#define HLEN (sizeof(__memt__))
#define MIN_POOL_SIZE (HLEN * 10)
int init_mempool (
void _MALLOC_MEM_ *pool,
unsigned int size)
{
if (size < MIN_POOL_SIZE)
return (0); /*失败*/
if (pool == NULL)
{ pool = 1; size--; }
AVAIL.next = pool;
AVAIL.len = size;
(AVAIL.next)->next = NULL;
(AVAIL.next)->len = size - HLEN;
return (-1);/*成功*/
}

堆
NULL
size-HLEN
…

AVAIL
pool
size
图1： init_mempool执行后的AVAIL链表及堆空间

在成功执行init_mempool函数后，将得到如图1所示的一个数据结构。另外，链首结点AVAIL的len域记录了整个堆的字节数。链首AVAIL结点的next域指向的是首块空闲块，当经过多次的malloc函数而堆中没有空闲内存块时，AVAIL结点的next域将为NULL值。
很明显，从上面的if (pool == NULL) { pool = 1; size--; }这部分源代码来看，如果应用程序中pool参数为空指针（pool为0）时，此时显然不能直接将AVAIL的next 域的值赋为空指针的（即赋为0），于是便将pool的值改为1，再将size的值减1，这样，init_mempool函数会在XDATA区中，从地址1开始，取size-1个字节来作为堆来使用，如果源程序有定义在XDATA区的变量，则这些变量所占的存储单元也可能会被当成堆空间的一部分，这无疑是有潜在风险的。
部分程序员在调用init_mempool函数时习惯将pool参数设为一个形如0xAAAA数字表示的绝对地址，如果不加特别防范，也是不妥的，因为Keil C可能会在你以如此方式指定的堆空间中分配临时变量。好的习惯是定义一个字节数组作为堆空间，再将数组名作为pool参数调用init_mempool函数。
在Keil C的联机文档中，指明了init_mempool在应用程序中只能被调用一次，那么，如果多次调用该函数又会有什么后果呢？从该函数的源代码来分析，多次调用init_mempool函数会导致重新初始化首结点AVAIL的next域和len域的值，将使AVAIL链表中的原有的管理信息丢失，从而导致一些很难诊断的问题。
对这个问题，可采用如下的保护措施。当发现AVAIL链表中已有管理信息时，则返回失败标志，函数直接返回。具体的方法是检查AVAIL结点的len域由于其被初始化为零，如果发现其值非零，则表明init_mempool函数已被成功调用过，此时函数直接返回。
3．malloc函数分析
malloc函数的原形是void *malloc (unsigned int size);size参数为需动态申请的内存块的字节数。
malloc函数的算法是查找AVAIL链表中各结点next指针所指向的空闲内存块，如果某块的空闲的字节数>=size参数，则停止查找，并从该块进行内存分配，返回一个指向所分配的内存块的指针给应用程序，如果没有找到合符要求的空闲内存块，则返回空指针给应用程序。
需要注意的是AVAIL链表中除首结点AVAIL外，其余各节点是位于堆中各空闲内存块开始处的一个struct __mem__结构中，其len域为该空闲块总字节数减去sizeof(struct __mem)后的值，即该块实际空闲的字节数；next域指向堆中下一空闲内存块。
设链表节点p指向所找到的空闲内存块，如果在p空闲块分配size个字节后，剩余的字节数不多，则将p块从AVAIL链表中删除，然后返回一个指向p块偏移sizeof(struct __mem)处的指针。如果在p空闲块分配size个字节后，该块仍剩余较多的字节数，则需对该块进行分割，将多出的这一部分保留在AVAIL链表中。下面是在malloc.c中该函数的部分源代码：

#define MIN_BLOCK (HLEN * 4)
void _MALLOC_MEM_ *malloc ( unsigned int size)
{
…//省略
k = p->len - size; /* 计算分配后剩余的字节数 */
if (k < MIN_BLOCK) /* 剩余的字节数太少，*/
{ /*不再分割该块*/
q->next = p->next; /*将p块从AVAIL链表中删除*/
return (&p[1]); /* 成功，参见后面分析*/
}
/*分割该块*/
k -= HLEN;
p->len = k
q = (__memp__ ) (((char _MALLOC_MEM_ *) (&p [1])) + k);
q->len = size; /*填入所分配块的大小*/
return (&q[1]); /* 成功，参见下面分析*/
}
在C语言中，数组名就是一个内存地址，也可把一个指针当作一个数组名；同时C语言数组的下标从0开始，在上面的源代码中，q为struct struct __mem类型的指针，所以&q[1]的值等于q块的起始地址+sizeof(struct struct __mem)的值，也就是说malloc通过return(&q[1])语句返回给应用程序的内存块指针，实际是指向所分配内存块偏移sizeof(struct struct __mem_)处的。
假设我们的应用程序中有一指向某动态分配的内存块的指针x，则可用如下的语句来获知包含开始处struct struct __mem的x块的大小：
struct struct __mem_ *pBlock;
unsigned int blocksize;
pBlock=x;
blocksize=((struct struct __mem_ *)(&pBlock[-1]))->len+sizeof(struct struct __mem);
而这正是free函数进行内存回收时所要采用的技术。
4.free函数分析及改进
free函数的原形是void free (void xdata *memp); 参数memp指向所要释放的内存块。
在AVAIL链表中，各结点是按其所指空闲内存块的开始地址的大小按升序排列。free函数的算法是在AVAIL链表中查一个节点p(其前驱为q)，当p节点所指空存块的地址大于参数memp所指内存块的起始地址时，则将memp块插入到该节点之前，如没有找到这样的节点，则memp块插到链尾。在插入memp块时，还将检查在memp块的前后是否存在地址相邻的空闲内存块，如果有，则将memp块与相邻块合并。free库函数的部分源代码如下：
void free ( void _MALLOC_MEM_ *memp)
{
…//前面省略
p0 = memp;
p0 = &p0 [-1];
/* 参考malloc函数的分析，&p0 [-1]为memp所指内存块首部
的 struct __mem_结构的地址，其中含有该块内存的大小信息，由
调用malloc函数时填入*/
q = &AVAIL;
…//查找p节点的代码省略
…//部分代码省略

/*如果q块与memp块相邻，则合并*/
if ((((char _MALLOC_MEM_ *)q) + q->len + HLEN) == p0)
{
q->len += p0->len + HLEN;
q->next = p0->next;
}
else { q->next = p0; }
}
值得探讨的是最后一段将memp块与前一块（q块）合并的这部分代码。如果在执行此部分代码之前，q指向首结点AVAIL，而此时欲将q块与memp块合并显然是不合理；实际上，此时本应当使q的next指针的值设为memp块的开始地址p0。由于Keil C7.5A中free库函数的源程序中没有考虑这种特殊情况，可能会引发严重后果。
由源代码分析可知，在q指向首结点AVAIL，而此时如果满足memp块与q块合并的判定条件，执行q->len + p0->len + HLEN；q->next = p0->next后，不但不能回收内存，反而导致memp块丢失，同时，AVAIL的len域的值也不再正确；而如果此时p0->next又为NULL，则会导致整个堆内存的丢失！
作者特在Keil C7.5 A版中设计了一个示例，用于引发该错误，有兴趣的可通过电子邮件与作者联系。要防止这种错误，只需将if ((((char _MALLOC_MEM_ *)q) + q->len + HLEN) == p0)判定语句改为if (（q!=&AVAIL）&& (((char _MALLOC_MEM_ *)q) + q->len + HLEN) == p0)即可。