Keil C的應(yīng)用動(dòng)態(tài)存儲(chǔ)管理的原理和實(shí)現(xiàn)方法分析

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

1 相關(guān)數(shù)據(jù)結(jié)構(gòu)、變量及說(shuō)明

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

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

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

#define AVAIL（__meM_avaiL_［O］）

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

2 init_mempool函數(shù)剖析

函數(shù)int_mempool（void_MALLOC_MEM_*pool，unsigned int size）失敗時(shí)將返回0，成功則返回一1，參數(shù)pool指向應(yīng)用程序定義的堆空間，參數(shù)size為堆空間的字節(jié)數(shù)。如果應(yīng)用程序提供的堆空間太小（size的值太?。瑢⑹?shí)際意義，故函數(shù)將返回0表示失敗。當(dāng)size參數(shù)足夠大，則會(huì)初始化AVAIL（即_mem_avail__［O］），使其next域指向pool參數(shù)所指向的堆空間，len域?yàn)閜ool參數(shù)所指向的堆空間的總字節(jié)數(shù)size。其在KeilC 7．5A庫(kù)中init_mem．C的源代碼如下：

在成功執(zhí)行init_mempool函數(shù)后，將得到如圖1所示的一個(gè)數(shù)據(jù)結(jié)構(gòu)。另外，鏈?zhǔn)捉Y(jié)點(diǎn)AVAIL的len域記錄了整個(gè)堆的字節(jié)數(shù)。鏈?zhǔn)譇VAIL結(jié)點(diǎn)的next域指向的是首塊空閑塊，當(dāng)經(jīng)過(guò)多次的malloe函數(shù)而堆中投有空閑內(nèi)存塊時(shí)，AVAIL結(jié)點(diǎn)的next域?qū)镹ULL值。

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

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

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

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

3 malloc函數(shù)分析

malloc函數(shù)的原形是void *malloc（unsigned intsize），size參數(shù)為需動(dòng)態(tài)申請(qǐng)的內(nèi)存塊的字節(jié)數(shù)。

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

需要注意的是，AVAIL鏈表中除首結(jié)點(diǎn)AVAIL外，其余各節(jié)點(diǎn)位于堆中各空閑內(nèi)存塊開(kāi)始處的一個(gè)struct__mem__結(jié)構(gòu)中，其len域?yàn)樵摽臻e塊總字節(jié)數(shù)減去sizeof（stiuct__mem）后的值，即該塊實(shí)際空閑的字節(jié)數(shù)；next域指向堆中下一空閑內(nèi)存塊。

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

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

free函數(shù)的原形是void free（void xdata *memp），參數(shù)memp指向所要釋放的內(nèi)存塊。

在AVAIL鏈表中，各結(jié)點(diǎn)是按其所指空閑內(nèi)存塊開(kāi)始地址的大小按升序排列的。free函數(shù)的算法是在AVAIL鏈表中查一個(gè)節(jié)點(diǎn)p（其前驅(qū)為q），當(dāng)p節(jié)點(diǎn)所指空問(wèn)內(nèi)存塊的地址大于參數(shù)memp所指內(nèi)存塊的起始地址時(shí)，則將memp塊插入到該節(jié)點(diǎn)之前，如沒(méi)有找到這樣的節(jié)點(diǎn)，則memp塊插到鏈尾。在插入memp塊時(shí)，還將檢查在memp塊的前后是否存在地址相鄰的空閑內(nèi)存塊，如果有，則將memp塊與相鄰塊合并。

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

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

筆者特在Keil C7．5 A版中設(shè)計(jì)了一個(gè)示例（見(jiàn)本刊網(wǎng)站），用于引發(fā)該錯(cuò)誤。要防止這種錯(cuò)誤，只需將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）。

責(zé)任編輯：gt