，，，，

(許繼電氣，許昌 461000)

引　言

Nucleus為搶先式多任務(wù)操作系統(tǒng)，Nucleus PLUS為其系統(tǒng)內(nèi)核，具有可移植性、易用性、可配置性等特點(diǎn)。Nucleus PLUS提供一系列系統(tǒng)服務(wù)，比如：任務(wù)控制、任務(wù)通信、任務(wù)同步、內(nèi)存管理、可編程的定時(shí)器、標(biāo)準(zhǔn)的輸入/輸出設(shè)備接口等。

Nucleus PLUS內(nèi)存管理沒有使用虛擬內(nèi)存技術(shù)，采用的是實(shí)存儲(chǔ)器管理技術(shù)：對內(nèi)存地址的訪問不需要經(jīng)過MMU，直接送到地址線上輸出，程序中訪問的地址都是實(shí)際的物理地址[1]。這種內(nèi)存管理策略雖然降低了系統(tǒng)的安全性，但是內(nèi)存分配快速、高效，避免了虛存系統(tǒng)中地址轉(zhuǎn)換及非常耗時(shí)的磁盤I/O操作，是許多嵌入式設(shè)備的選擇。

Nucleus PLUS提供兩種內(nèi)存管理方式，一種是分區(qū)內(nèi)存管理(Partition Memory Pools)，另一種是動(dòng)態(tài)內(nèi)存管理(Dynamic Memory Pools)[2]。本文針對某版本Nucleus PLUS，詳細(xì)研究了其動(dòng)態(tài)內(nèi)存管理機(jī)制及實(shí)現(xiàn)細(xì)節(jié)，介紹了其測試思路和測試用例設(shè)計(jì)，最后對Nucleus PLUS動(dòng)態(tài)內(nèi)存管理機(jī)制進(jìn)行評價(jià),并針對該機(jī)制存在的內(nèi)存訪問越界時(shí)保存在內(nèi)存頭的內(nèi)存管理信息被破壞，進(jìn)而導(dǎo)致動(dòng)態(tài)內(nèi)存管理機(jī)制系統(tǒng)性失效的缺點(diǎn),提出了改進(jìn)建議及內(nèi)存越界檢測方法。

1　Nucleus PLUS動(dòng)態(tài)內(nèi)存管理機(jī)制研究

Nucleus PLUS動(dòng)態(tài)內(nèi)存管理組件(DM)負(fù)責(zé)所有的動(dòng)態(tài)內(nèi)存管理。一個(gè)動(dòng)態(tài)內(nèi)存池包括用戶指定數(shù)目的字節(jié),提供了從動(dòng)態(tài)內(nèi)存池中分配或釋放可變長度內(nèi)存塊的服務(wù)。內(nèi)存分配采用first-fit策略(首次適配策略)。

1.1　數(shù)據(jù)結(jié)構(gòu)

1.1.1內(nèi)存池控制塊鏈表

內(nèi)存池通過動(dòng)態(tài)內(nèi)存池控制塊(DM_PCB，見1.1.2節(jié))管理。所有創(chuàng)建的內(nèi)存池的DM_PCB通過一個(gè)雙向循環(huán)鏈表鏈接起來，即內(nèi)存池控制塊鏈表。全局變量DMD_Created_Pools_List為該鏈表的頭指針。動(dòng)態(tài)內(nèi)存池可以動(dòng)態(tài)刪除和創(chuàng)建，每創(chuàng)建一個(gè)動(dòng)態(tài)內(nèi)存池，其DB_PCB加入到鏈表尾端；每刪除一個(gè)動(dòng)態(tài)內(nèi)存池，其在鏈表中對應(yīng)的DB_PCB節(jié)點(diǎn)就會(huì)從鏈表中刪除。內(nèi)存池控制塊鏈表如圖1所示。

圖1　內(nèi)存池控制塊鏈表

1.1.2內(nèi)存池控制塊(DM_PCB)

DM_PCB用于管理內(nèi)存池，它包含了內(nèi)存池的狀態(tài)和控制信息，屬性見表1。

表1　內(nèi)存池控制塊主要屬性

DM_PCB的dm_suspension_list鏈表的每個(gè)節(jié)點(diǎn)為一個(gè)內(nèi)存池阻塞結(jié)構(gòu)，其定義見DM_SUSPEND。它主要包含如下信息：

① dm_memory_pool：內(nèi)存池控制塊指針，指示阻塞哪個(gè)內(nèi)存池上。

② dm_suspended_task：任務(wù)控制塊指針，指示哪個(gè)任務(wù)被阻塞。

③ dm_request_size：任務(wù)請求內(nèi)存的大小。

1.1.3內(nèi)存池內(nèi)存布局

內(nèi)存池的內(nèi)存由內(nèi)存塊組成，分為空閑內(nèi)存塊和已分配內(nèi)存塊。每個(gè)內(nèi)存塊都有一個(gè)內(nèi)存頭數(shù)據(jù)結(jié)構(gòu)(DM_HEADER，見1.1.4節(jié))，用以描述該內(nèi)存塊的基本信息以及用于鏈接其它內(nèi)存塊的指針信息，內(nèi)存頭與用戶數(shù)據(jù)連續(xù)存在一起。內(nèi)存池內(nèi)存中存在兩個(gè)雙向鏈表：①“全部內(nèi)存塊鏈表”：鏈接了全部內(nèi)存塊，包括已分配內(nèi)存塊和空閑內(nèi)存塊。②“空閑內(nèi)存塊鏈表”：只鏈接了空閑內(nèi)存塊。“全部內(nèi)存塊鏈表”的頭指針保存在內(nèi)存池控制塊的dm_start_address中，通過DM_HEADER的dm_next_memory和dm_previous_memory指針將所有內(nèi)存塊雙向鏈接起來。“空閑內(nèi)存塊鏈表”的頭指針保存在內(nèi)存控制塊的dm_memory_list中，通過DM_HEADER的dm_next_free和dm_previous指針將空閑內(nèi)存塊雙向鏈接起來。圖2為內(nèi)存池布局圖。

圖2　內(nèi)存池布局圖

內(nèi)存池剛創(chuàng)建后，只有一個(gè)空閑塊和一個(gè)Trailer塊，隨著該內(nèi)存池中內(nèi)存的不斷申請和釋放，內(nèi)存池便被分割成許多內(nèi)存塊。

1.1.4內(nèi)存頭數(shù)據(jù)結(jié)構(gòu)(DM_HEADER)

內(nèi)存頭存儲(chǔ)了內(nèi)存塊基本信息以及用于鏈接其它內(nèi)存塊的指針信息。主要屬性如表2所列。

表2　DM_HEADER主要屬性

DM_HEADER數(shù)據(jù)類型的大小為24, 但是所占內(nèi)存開銷的大小(見DM_OVERHEAD)卻定義16，少了8個(gè)字節(jié)。原因是：對于已分配內(nèi)存塊，DM_HEADER中不存儲(chǔ)dm_next_free和dm_previous_free這兩個(gè)共占8個(gè)字節(jié)的指針。對于空閑內(nèi)存塊，dm_next_free、dm_previous_free這個(gè)指針只是暫時(shí)存儲(chǔ)在其可用內(nèi)存中，當(dāng)該內(nèi)存塊被分配出去時(shí)，這兩個(gè)指針?biāo)诘膬?nèi)存也在分配范圍內(nèi)。

DM_HEADER中并沒有定義表示內(nèi)存塊內(nèi)存大小的數(shù)據(jù)。但是內(nèi)存塊內(nèi)存的大小是可以推算出來的。對于某個(gè)內(nèi)存塊(pt指針指向該內(nèi)存塊)，計(jì)算方法如下：

(char)pt->dm_next_memory - (char)pt - DM_OVERHEAD。

對于Trailer內(nèi)存塊,只包含了一個(gè)內(nèi)存頭，且dm_memory_free為非空閑狀態(tài)。設(shè)置Trailer內(nèi)存塊的作用是：充當(dāng)一條屏障，防止當(dāng)內(nèi)存池第一塊內(nèi)存塊和最后一塊內(nèi)存塊均空閑時(shí)而發(fā)生的內(nèi)存合并(見1.2.2內(nèi)存釋放)。

1.2　系統(tǒng)函數(shù)功能

本節(jié)主要介紹了內(nèi)存池創(chuàng)建、內(nèi)存分配、內(nèi)存釋放等接口函數(shù)的功能和實(shí)現(xiàn)細(xì)節(jié)。

1.2.1內(nèi)存池創(chuàng)建

NU_Create_Memory_Pool函數(shù)提供內(nèi)存創(chuàng)建功能。內(nèi)存池的內(nèi)存由參數(shù)start_address、pool_size決定。該塊內(nèi)存應(yīng)事先從系統(tǒng)內(nèi)存池(Application_Initialize的mem_pool參數(shù))中分配。內(nèi)存池的創(chuàng)建會(huì)建立一個(gè)屬性由傳入?yún)?shù)決定的DM_PCB，并將其加入到“內(nèi)存控制塊鏈表”中。內(nèi)存池創(chuàng)建后，其內(nèi)存的初始布局為：一個(gè)空閑內(nèi)存塊和一個(gè)Trailer。

1.2.2內(nèi)存分配

內(nèi)存分配采用first-fit策略(首次適配策略)。第一個(gè)滿足需求的可用內(nèi)存塊被分配。如果沒有可用內(nèi)存滿足內(nèi)存分配請求，任務(wù)可能被掛起。系統(tǒng)提供兩種內(nèi)存分配接口：

圖5　內(nèi)存分割

① NU_Allocate_Memory，此方式分配的內(nèi)存首地址不要求對齊。

② NU_Allocate_Aligned_Memory，此方式分配的內(nèi)存首地址要求分配的內(nèi)存首地址按參數(shù)指定的值對齊。

內(nèi)存分配時(shí)，可能出現(xiàn)下列內(nèi)存分割情況：(注：下文的“最小分配空間”記為min_alloc，大小為16)

① 尾部分割(rear split)：當(dāng)內(nèi)存分配后尾部剩余內(nèi)存-DM_OVERHEAD≥min_alloc時(shí)，會(huì)發(fā)生尾部分割，將尾部所剩內(nèi)存新建一個(gè)空閑塊。

圖3中，大小為100字節(jié)的空閑塊中分配出去68字節(jié)后，剩余32字節(jié)。32-DM_OVERHEADE(16)=16，等于“最小分配空間”，于是進(jìn)行尾部分割。

圖3　尾部分割

② 頭部分割(front split)：對于對齊方式分配內(nèi)存，如果頭部用于對齊的字節(jié)數(shù)(記為：split_size)大于0，則會(huì)發(fā)生頭部分割。split_size的含義如圖4所示。

圖4　split_size含義

根據(jù)split_size和min_alloc的關(guān)系，又可分為兩種情況：

(1) split_size≥min_alloc + DM_OVERHEAD

此時(shí)預(yù)期在頭部分割出一個(gè)大小為split_size的空閑塊(包含內(nèi)存頭)。例如：對齊方式請求分配大小(size)為96、對齊字節(jié)數(shù)(align)為48的內(nèi)存。內(nèi)存池的#1空閑內(nèi)存首次滿足分配請求，該內(nèi)存塊的起始地址(start_addr)為N×48，可用內(nèi)存大小為128。則會(huì)按圖5所示發(fā)生頭部分割，且內(nèi)存分配起始地址(ptr)為N×48+48。

(2) split_size < min_alloc + DM_OVERHEAD

此種情況下，會(huì)在min_alloc+ DM_OVERHEAD的基礎(chǔ)上再次對齊，計(jì)算出新的split_size，然后再進(jìn)行頭部分割。

1.2.3內(nèi)存池內(nèi)存釋放

NU_Deallocate_Memory提供內(nèi)存釋放功能。內(nèi)存釋放時(shí)，將判斷與被釋放內(nèi)存塊(記為dealloc_block)物理位置相鄰的內(nèi)存塊是否空閑，如果空閑，則將該內(nèi)存塊與其進(jìn)行合并。另外，內(nèi)存釋放后會(huì)檢查該內(nèi)存池的阻塞鏈表，如果某些任務(wù)的內(nèi)存請求此時(shí)可被滿足，則將它們從阻塞鏈表中刪除，并喚醒這些任務(wù)。圖6為當(dāng)與dealloc_block物理位置緊鄰的上一塊內(nèi)存和下一塊內(nèi)存均空閑時(shí)，發(fā)生的內(nèi)存合并。

圖6　內(nèi)存合并

1.2.4其它

動(dòng)態(tài)內(nèi)存管理模塊還提供其它接口函數(shù)：

NU_Create_Memory_Pool: 創(chuàng)建內(nèi)存池。

NU_Add_Memory: 向內(nèi)存池中增加內(nèi)存。

NU_Reallocate_Aligned_Memory:重新分配內(nèi)存。

NU_Delete_Memory_Pool:刪除內(nèi)存池。

因篇幅所限，這些功能不做詳細(xì)介紹。

2　動(dòng)態(tài)內(nèi)存管理模塊測試

2.1　測試思路

進(jìn)行內(nèi)存池創(chuàng)建、內(nèi)存分配、內(nèi)存釋放、內(nèi)存池刪除等操作后，DM_PCB、內(nèi)存池內(nèi)存塊的布局以及任務(wù)狀態(tài)均可能發(fā)生變化，檢查這些變化是否正確。

DM_PCB的變化主要指的是：可用內(nèi)存大小(dm_availble)和空閑塊鏈表(dm_memory_list)首指針的變化。

內(nèi)存池內(nèi)存塊的布局可通過“全部內(nèi)存塊鏈表”和“空閑控制塊鏈表”(見1.1.3)來表達(dá)。

2.2　用例設(shè)計(jì)

NU_Allocate_Aligned_Memory和NU_Deallocate_Memory兩個(gè)API函數(shù)最重要、使用最頻繁，由于篇幅所限，只針對這兩個(gè)函數(shù)介紹其測試用例設(shè)計(jì)。

(三)2012年至今，中國特色社會(huì)主義進(jìn)入了新時(shí)代，中國共產(chǎn)黨以實(shí)現(xiàn)中華民族偉大復(fù)興為引領(lǐng)，在知識(shí)分子中深入開展“弘揚(yáng)愛國奮斗精神、建功立業(yè)新時(shí)代”活動(dòng)，加強(qiáng)政治吸納，以最大限度凝聚共識(shí)

2.2.1NU_Allocate_Aligned_Memory用例設(shè)計(jì)

用例劃分為以下幾類：

① 空閑內(nèi)存塊鏈表中，首次滿足內(nèi)存請求的內(nèi)存塊在鏈表中的位置：第一塊、中間某塊、最后一塊。

② 各種分割情況。

a. 尾部分割。

b. 頭部分割。又分為split_size≥min_alloc + DM_OVERHEAD的情況和split_size < min_alloc+DM_OVERHEAD的情況。

c. 頭部和尾部均需分割。

d. 頭部和尾部均不需分割。

③ 任務(wù)的阻塞與喚醒。

a. 阻塞原因：內(nèi)存池中不存在可以滿足內(nèi)存分配請求的空閑內(nèi)存塊。

b. 喚醒原因：釋放內(nèi)存、刪除內(nèi)存池、超時(shí)、內(nèi)存池增加內(nèi)存。

c. 喚醒順序：先進(jìn)先出、優(yōu)先級。

④ 各種異常輸入。

2.2.2NU_Deallocate_Memory用例設(shè)計(jì)

① 各種合并情況(下文中的被釋放的內(nèi)存塊記為dealloc_block; 與其物理位置相鄰的前一個(gè)內(nèi)存塊記為prev_block; 與其物理位置相鄰的后一個(gè)內(nèi)存塊記為next_block)：

a. prev_block：不空閑，next_block：空閑。

b. prev_block：空閑，next_block：空閑。

c. prev_block：空閑，next_block：不空閑。

d. prev_block與next_block均不空閑。

e. dealloc_block：(除trailer外)最后一個(gè)內(nèi)存塊; 第一個(gè)內(nèi)存塊：空閑。

② 任務(wù)的阻塞與喚醒。

a. 內(nèi)存釋放后，可滿足阻塞鏈表中某些任務(wù)的內(nèi)存請求。

b. 內(nèi)存釋放后，仍無法滿足阻塞鏈表中任何一個(gè)任務(wù)的內(nèi)存請求。

③ 各種異常輸入。

3　Nucleus PLUS動(dòng)態(tài)內(nèi)存管理機(jī)制評價(jià)及改進(jìn)措施

從內(nèi)存碎片問題和內(nèi)存越界風(fēng)險(xiǎn)兩方面來評價(jià)該動(dòng)態(tài)內(nèi)存管理機(jī)制，針對內(nèi)存越界，提出了改進(jìn)和檢測辦法。

3.1　內(nèi)存碎片問題

內(nèi)存碎片是指內(nèi)存池中有空閑內(nèi)存塊，當(dāng)所有的空閑內(nèi)存塊均小于內(nèi)存請求大小時(shí)，稱之為內(nèi)存碎片[3]。Nucleus PLUS提供了如下措施來應(yīng)對內(nèi)存碎片問題：① 內(nèi)存分割時(shí)使用了“最小分配內(nèi)存”。② 內(nèi)存釋放時(shí)，與物理位置相鄰的空閑塊進(jìn)行合并。但由于其所采用的first-fit算法的固有缺陷，隨著內(nèi)存池內(nèi)存的不斷分配與釋放，內(nèi)存池支離破碎，仍可能存在內(nèi)存碎片問題。

3.2　內(nèi)存越界風(fēng)險(xiǎn)

內(nèi)存塊的管理信息直接放在內(nèi)存池的內(nèi)存中，不需要額外的內(nèi)存用作管理，且內(nèi)存的合并操作非常高效[4]。但這也正是其缺點(diǎn)所在：內(nèi)存池中內(nèi)存塊的管理信息(DM_HEADER)和用戶數(shù)據(jù)連續(xù)存放在一起。如果用戶數(shù)據(jù)寫越界，DM_HEADER的信息可能被破壞，即該內(nèi)存池的內(nèi)存塊的鏈接信息或內(nèi)存塊的空閑標(biāo)志被破壞，從而導(dǎo)致內(nèi)存池模塊功能全面失效。

3.3　改進(jìn)措施

針對內(nèi)存寫越界可能導(dǎo)致的系統(tǒng)崩潰，建議在該動(dòng)態(tài)內(nèi)存管理模塊增加內(nèi)存越界檢查機(jī)制。具體方式：在內(nèi)存頭增加一塊“越界保護(hù)內(nèi)存”[5]，用于防止內(nèi)存的寫越界并提供寫越界檢測。內(nèi)存塊分配時(shí)，向“越界保護(hù)內(nèi)存”填充特殊字符。內(nèi)存塊釋放時(shí)，判斷“越界保護(hù)內(nèi)存”的特殊字符是否被破壞，從而判斷是否發(fā)生內(nèi)存寫越界。“越界保護(hù)內(nèi)存”會(huì)帶來額外的內(nèi)存開銷，并且只有在內(nèi)存釋放時(shí)才能判斷出來。下節(jié)介紹不改動(dòng)系統(tǒng)代碼的情況下，從應(yīng)用/測試角度可實(shí)施的內(nèi)存越界檢測方法。

3.4　內(nèi)存越界檢測方法

Nucleus動(dòng)態(tài)內(nèi)存模塊并沒有提供內(nèi)存池越界檢查手段。但是動(dòng)態(tài)內(nèi)存相關(guān)數(shù)據(jù)結(jié)構(gòu)的一些信息是可以相互驗(yàn)證的；內(nèi)存寫越界發(fā)生時(shí)，內(nèi)存頭信息被破壞進(jìn)而內(nèi)存塊鏈表被破壞?；谝陨蟽牲c(diǎn)，如果信息不能相互驗(yàn)證或者內(nèi)存塊鏈表的雙向循環(huán)特征被破壞，則內(nèi)存寫越界發(fā)生。提出以下三種檢測方法：

① 從start_address_list開始遍歷，遍歷全部內(nèi)存塊鏈表，應(yīng)能再次遍歷到start__address_list節(jié)點(diǎn)。如果在N次(可配置)循環(huán)中，或在一段時(shí)間內(nèi)(可配置)沒有再次遍歷到start_address_list節(jié)點(diǎn)，則有可能內(nèi)存池訪問越界發(fā)生。

② 遍歷全部內(nèi)存塊鏈表。如果內(nèi)存塊A的下一個(gè)內(nèi)存塊(記為內(nèi)存塊B)的dm_previous_memory不為內(nèi)存A，則可能內(nèi)存池訪問越界發(fā)生。

③ 內(nèi)存池控制塊的可用內(nèi)存(DM_PCB的dm_available)與所有空閑塊的內(nèi)存大小之和，應(yīng)該相同。如果不

同，則可能內(nèi)存池訪問越界發(fā)生。

結(jié)　語

[1] 黃斌.嵌入式操作系統(tǒng)的內(nèi)核剖析及基于ARM的移植[D].武漢:武漢理工大學(xué),2004.

[2] Mentor Graphics Corporation.Nucleus Kernel Guide,2016.

[3] 李志軍.面向嵌入式實(shí)時(shí)系統(tǒng)的動(dòng)態(tài)內(nèi)存管理方法研究[D].重慶:重慶大學(xué),2007.

[4] 李云.專業(yè)嵌入式軟件開發(fā)[M].北京:電子工業(yè)出版社,2012.

[5] 顧勝元,楊丹,黃海倫.嵌入式實(shí)時(shí)動(dòng)態(tài)內(nèi)存管理機(jī)制[J].計(jì)算機(jī)工程,2009,35(20):264-266.

姬希娜(工程師)，主要從事繼電保護(hù)及自動(dòng)化產(chǎn)品的測試技術(shù)研究。