Keil C動(dòng)態(tài)內存管理機制分析及改進(jìn)

　　Keil C是常用的嵌入式系統編程工具，它通過(guò)init_mempool、mallloe、free等函數，提供了動(dòng)態(tài)存儲管理等功能。本文通過(guò)對init_mempool、mallloe和free這3個(gè)KeilC庫函數源代碼的分析，揭示其實(shí)現的原理和方法，并對其中的不足作了改進(jìn)，以使Keil C編程人員更好地應用動(dòng)態(tài)存儲管理。

　　1 相關(guān)數據結構、變量及說(shuō)明

　　在Keil C安裝目錄下的c5llib目錄下，有實(shí)現init_mempool、mallloe和free這3個(gè)函數的C源文件init_mere.c、malloc.e和free.c。下面針對keil C7.5A版，將其中與動(dòng)態(tài)存儲管理相關(guān)的數據結構介紹如下;

　　#define _MALLOC_MEM_xdata /*該行在stdlib.h文件中*/

　　struct __mem__ {

　　struct __mem__ _MALLOC_MEM_ *next; /*單鏈表*/

　　unsigned int len; /*下一塊長(cháng)度*/

　　};

　　該結構的next指向堆中的下一空閑內存塊，len表示該空閑塊除去該塊首部的struct__mem__結構所占的字節數后，該塊實(shí)際可用的字節數。由于next是一個(gè)指向XDATA區的指針，故在Keil C中應用程序所定義的堆空間應在XDATA段中定義。

　　在Keil C中，堆中的所有空閑內存塊是用一個(gè)單鏈表來(lái)管理的，struct_mere_即為該鏈表結點(diǎn)的結構，后面定義的宏AVAIL為該鏈表的首結點(diǎn)，為敘述方便，以下將該鏈表稱(chēng)為AVAIL鏈表。

　　typedef struct __mem__ __memt__;

　　typedef __memt__ _MALLOC_MEM_ *__memp__;

　　__memt__ _MALLOC_MEM_ __mem_avail__ [2] = {

　　{ NULL, 0 }, / * 堆中空閑內存塊頭結點(diǎn)* /

　　{ NULL, 0 }, / * 未使用,但對f ree 函數防止丟失堆空間或誤將鏈表頭加入到堆空間,卻是必須的* /

　　/ * 筆者注:__mem_avail__ [1]的存在,并不能防止堆丟失,見(jiàn)后面free 函數分析* /

　　};

　　#define AVAIL (__mem_avail__[0])

　　全局數組__meM_ avail_實(shí)際也是struct__mem__類(lèi)型，__mem_avail__[O]的next指向堆中首塊空閑塊。如果堆中已無(wú)空閑內存塊，則__mem_avail__[0]的next為NULL(0值)。為使程序代碼簡(jiǎn)潔，定義了宏AVAIL來(lái)代替__mem_avail__[O]。

　　2 init_mempool函數剖析

　　函數int_mempool(void_MALLOC_MEM_*

　　pool，unsigned int size)失敗時(shí)將返回0，成功則返回一1，參數pool指向應用程序定義的堆空間，參數size為堆空間的字節數。如果應用程序提供的堆空間太小(size的值太小)，將失去實(shí)際意義，故函數將返回0表示失敗。當size參數足夠大，則會(huì )初始化AVAIL(即_mem_avail__[O])，使其next域指向pool參數所指向的堆空間，len域為pool參數所指向的堆空間的總字節數size。其在KeilC 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); / * 成功* /

　　}

　　在成功執行init_mempool函數后，將得到如圖1所示的一個(gè)數據結構。另外，鏈首結點(diǎn)AVAIL的len域記錄了整個(gè)堆的字節數。鏈首AVAIL結點(diǎn)的next域指向的是首塊空閑塊，當經(jīng)過(guò)多次的malloe函數而堆中投有空閑內存塊時(shí)，AVAIL結點(diǎn)的next域將為NULL值。

　　很明顯，從上面的if(pool==NULL){pool=1;size--;)這部分源代碼來(lái)看，如果應用程序中pool參數為空指針(pool為0)時(shí)，顯然不能直接將AVAIL，的next域的值賦為空指針的(即賦為O)。將pool的值改為1，再將size的值減l，這樣，init_mempool函數會(huì )在XDATA區中，從地址l開(kāi)始，取size一1個(gè)字節作為堆來(lái)使用。如果源程序有定義在XDATA區的變量，則這些變量所占的存儲單元也可能會(huì )被當成堆空間的一部分，這無(wú)疑是有潛在風(fēng)險的。

　　部分程序員在調用init_mempool函數時(shí)，習慣將pool參數設為一個(gè)形如0xAAAA數字表示的絕對地址，如果不加特別防范，也是不妥的，因為Keil C可能會(huì )在此方式指定的堆空間中分配臨時(shí)變量。好的習慣是定義一個(gè)字節數組作為堆空間，再將數組名作為pool參數調用init_mempool函數。

　　在Keil C的聯(lián)機文檔中，指明了init_mempool在應用程序中只能被調用一次，那么，如果多次調用該函數又會(huì )有什么后果呢?從該函數的源代碼來(lái)分析，多次調用init_mempoo1函數，會(huì )導致重新初始化首結點(diǎn)AVAIL的next域和len域的值，將使AVAIL鏈表中的原有管理信息丟失，從而導致一些很難診斷的問(wèn)題。

　　對此問(wèn)題，可采用如下保護措施。當發(fā)現AVAIL鏈表中已有管理信息時(shí)，則返回失敗標志，函數直接返回。具體的方法是檢查AVAIL結點(diǎn)的len域，由于其被初始化為零，如果發(fā)現其值非零，則表明init_mempool函數已被成功調用過(guò)，此時(shí)函數直接返回。

　　3 malloc函數分析

　　malloc函數的原形是void *malloc(unsigned intsize)，size參數為需動(dòng)態(tài)申請的內存塊的字節數。

　　malloc函數的算法是查找AVAIL鏈表中各結點(diǎn)next指針所指向的空閑內存塊。如果某塊的空閑字節數≥size參數，則停止查找，并從該塊進(jìn)行內存分配，返回一個(gè)指向所分配內存塊的指針給應用程序。如果沒(méi)有找到符合要求的空閑內存塊，則返回空指針給應用程序。

　　需要注意的是，AVAIL鏈表中除首結點(diǎn)AVAIL外，其余各節點(diǎn)位于堆中各空閑內存塊開(kāi)始處的一個(gè)struct__mem__結構中，其len域為該空閑塊總字節數減去sizeof(stiuct__mem)后的值，即該塊實(shí)際空閑的字節數;next域指向堆中下一空閑內存塊。

　　設鏈表節點(diǎn)p指向所找到的空閑內存塊，如果在p空閑塊分配size個(gè)字節后，剩余的字節數不多，則將p塊從AVAIL鏈表中刪除，然后返回一個(gè)指向p塊偏移sizeof(struct__mem)處的指針。如果在p空閑塊分配size個(gè)字節后，該塊仍剩余較多的字節數，則需對該塊進(jìn)行分割，將多出的這一部分保留在A(yíng)VAIL鏈表中。(以下部分有省略，全文請見(jiàn)本刊網(wǎng)站——編者注)

　　4 free函數分析及改進(jìn)

　　free函數的原形是void free(void xdata *memp)，參數memp指向所要釋放的內存塊。

　　在A(yíng)VAIL鏈表中，各結點(diǎn)是按其所指空閑內存塊開(kāi)始地址的大小按升序排列的。free函數的算法是在A(yíng)VAIL鏈表中查一個(gè)節點(diǎn)p(其前驅為q)，當p節點(diǎn)所指空問(wèn)內存塊的地址大于參數memp所指內存塊的起始地址時(shí)，則將memp塊插入到該節點(diǎn)之前，如沒(méi)有找到這樣的節點(diǎn)，則memp塊插到鏈尾。在插入memp塊時(shí)，還將檢查在memp塊的前后是否存在地址相鄰的空閑內存塊，如果有，則將memp塊與相鄰塊合并。(free庫函數的部分源代碼見(jiàn)本刊網(wǎng)站——編者注)

　　值得探討的是最后一段將memp塊與前一塊(q塊)合并的這部分代碼。如果在執行此部分代碼之前，q指向首結點(diǎn)AVAIL，而此時(shí)欲將q塊與memp塊合并，顯然是不合理的。實(shí)際上，此時(shí)應當將q的next指針的值設為memp塊的開(kāi)始地址p0。由于KeilC7.5A中，free庫函數的源程序中沒(méi)有考慮這種特殊情況，因此可能會(huì )引發(fā)嚴重后果。

　　由源代碼分析可知，q指向首結點(diǎn)AVAIL，而此時(shí)如果滿(mǎn)足。memp塊與q塊合并的判定條件，執行q>1en+=p0一>Len+HL，EN和q一>next=pO一>next后，不但不能回收內存，反而導致memp塊丟失;同時(shí)，AVAIL的len域的值也不正確。如果此時(shí)pO一>next又為NULL，則會(huì )導致整個(gè)堆內存的丟失。

　　筆者特在Keil C7.5 A版中設計了一個(gè)示例(見(jiàn)本刊網(wǎng)站)，用于引發(fā)該錯誤。要防止這種錯誤，只需將if((((char_MALLOC_MEM_*)q)+q一>len+HLEN)==pO)判定語(yǔ)句改為if((q!=&AVAIL)&&(((char_MALLOC_MEM_*)q)+q一>len+HLEN)==p0)即可。有興趣的可通過(guò)電子郵件與筆者聯(lián)系(cqdoml@sina.com)。