Nucleus PLUS的動態內存管理機制研究

，，，，

(許繼電氣，許昌 461000)

引　言

Nucleus為搶先式多任務操作系統，Nucleus PLUS為其系統內核，具有可移植性、易用性、可配置性等特點。Nucleus PLUS提供一系列系統服務，比如：任務控制、任務通信、任務同步、內存管理、可編程的定時器、標準的輸入/輸出設備接口等。

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

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

1　Nucleus PLUS動態內存管理機制研究

Nucleus PLUS動態內存管理組件(DM)負責所有的動態內存管理。一個動態內存池包括用戶指定數目的字節,提供了從動態內存池中分配或釋放可變長度內存塊的服務。內存分配采用first-fit策略(首次適配策略)。

1.1　數據結構

1.1.1內存池控制塊鏈表

內存池通過動態內存池控制塊(DM_PCB，見1.1.2節)管理。所有創建的內存池的DM_PCB通過一個雙向循環鏈表鏈接起來，即內存池控制塊鏈表。全局變量DMD_Created_Pools_List為該鏈表的頭指針。動態內存池可以動態刪除和創建，每創建一個動態內存池，其DB_PCB加入到鏈表尾端；每刪除一個動態內存池，其在鏈表中對應的DB_PCB節點就會從鏈表中刪除。內存池控制塊鏈表如圖1所示。

圖1　內存池控制塊鏈表

1.1.2內存池控制塊(DM_PCB)

DM_PCB用于管理內存池，它包含了內存池的狀態和控制信息，屬性見表1。

表1　內存池控制塊主要屬性

DM_PCB的dm_suspension_list鏈表的每個節點為一個內存池阻塞結構，其定義見DM_SUSPEND。它主要包含如下信息：

① dm_memory_pool：內存池控制塊指針，指示阻塞哪個內存池上。

② dm_suspended_task：任務控制塊指針，指示哪個任務被阻塞。

③ dm_request_size：任務請求內存的大小。

1.1.3內存池內存布局

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

圖2　內存池布局圖

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

1.1.4內存頭數據結構(DM_HEADER)

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

表2　DM_HEADER主要屬性

DM_HEADER數據類型的大小為24, 但是所占內存開銷的大小(見DM_OVERHEAD)卻定義16，少了8個字節。原因是：對于已分配內存塊，DM_HEADER中不存儲dm_next_free和dm_previous_free這兩個共占8個字節的指針。對于空閑內存塊，dm_next_free、dm_previous_free這個指針只是暫時存儲在其可用內存中，當該內存塊被分配出去時，這兩個指針所在的內存也在分配范圍內。

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

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

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

1.2　系統函數功能

本節主要介紹了內存池創建、內存分配、內存釋放等接口函數的功能和實現細節。

1.2.1內存池創建

NU_Create_Memory_Pool函數提供內存創建功能。內存池的內存由參數start_address、pool_size決定。該塊內存應事先從系統內存池(Application_Initialize的mem_pool參數)中分配。內存池的創建會建立一個屬性由傳入參數決定的DM_PCB，并將其加入到“內存控制塊鏈表”中。內存池創建后，其內存的初始布局為：一個空閑內存塊和一個Trailer。

1.2.2內存分配

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

圖5　內存分割

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

② NU_Allocate_Aligned_Memory，此方式分配的內存首地址要求分配的內存首地址按參數指定的值對齊。

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

① 尾部分割(rear split)：當內存分配后尾部剩余內存-DM_OVERHEAD≥min_alloc時，會發生尾部分割，將尾部所剩內存新建一個空閑塊。

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

圖3　尾部分割

② 頭部分割(front split)：對于對齊方式分配內存，如果頭部用于對齊的字節數(記為：split_size)大于0，則會發生頭部分割。split_size的含義如圖4所示。

圖4　split_size含義

根據split_size和min_alloc的關系，又可分為兩種情況：

(1) split_size≥min_alloc + DM_OVERHEAD

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

(2) split_size < min_alloc + DM_OVERHEAD

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

1.2.3內存池內存釋放

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

圖6　內存合并

1.2.4其它

動態內存管理模塊還提供其它接口函數：

NU_Create_Memory_Pool: 創建內存池。

NU_Add_Memory: 向內存池中增加內存。

NU_Reallocate_Aligned_Memory:重新分配內存。

NU_Delete_Memory_Pool:刪除內存池。

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

2　動態內存管理模塊測試

2.1　測試思路

進行內存池創建、內存分配、內存釋放、內存池刪除等操作后，DM_PCB、內存池內存塊的布局以及任務狀態均可能發生變化，檢查這些變化是否正確。

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

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

2.2　用例設計

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

(三)2012年至今，中國特色社會主義進入了新時代，中國共產黨以實現中華民族偉大復興為引領，在知識分子中深入開展“弘揚愛國奮斗精神、建功立業新時代”活動，加強政治吸納，以最大限度凝聚共識

2.2.1NU_Allocate_Aligned_Memory用例設計

用例劃分為以下幾類：

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

② 各種分割情況。

a. 尾部分割。

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

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

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

③ 任務的阻塞與喚醒。

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

b. 喚醒原因：釋放內存、刪除內存池、超時、內存池增加內存。

c. 喚醒順序：先進先出、優先級。

④ 各種異常輸入。

2.2.2NU_Deallocate_Memory用例設計

① 各種合并情況(下文中的被釋放的內存塊記為dealloc_block; 與其物理位置相鄰的前一個內存塊記為prev_block; 與其物理位置相鄰的后一個內存塊記為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外)最后一個內存塊; 第一個內存塊：空閑。

② 任務的阻塞與喚醒。

a. 內存釋放后，可滿足阻塞鏈表中某些任務的內存請求。

b. 內存釋放后，仍無法滿足阻塞鏈表中任何一個任務的內存請求。

③ 各種異常輸入。

3　Nucleus PLUS動態內存管理機制評價及改進措施

從內存碎片問題和內存越界風險兩方面來評價該動態內存管理機制，針對內存越界，提出了改進和檢測辦法。

3.1　內存碎片問題

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

3.2　內存越界風險

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

3.3　改進措施

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

3.4　內存越界檢測方法

Nucleus動態內存模塊并沒有提供內存池越界檢查手段。但是動態內存相關數據結構的一些信息是可以相互驗證的；內存寫越界發生時，內存頭信息被破壞進而內存塊鏈表被破壞。基于以上兩點，如果信息不能相互驗證或者內存塊鏈表的雙向循環特征被破壞，則內存寫越界發生。提出以下三種檢測方法：

① 從start_address_list開始遍歷，遍歷全部內存塊鏈表，應能再次遍歷到start__address_list節點。如果在N次(可配置)循環中，或在一段時間內(可配置)沒有再次遍歷到start_address_list節點，則有可能內存池訪問越界發生。

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

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

同，則可能內存池訪問越界發生。

結　語

[1] 黃斌.嵌入式操作系統的內核剖析及基于ARM的移植[D].武漢:武漢理工大學,2004.

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

[3] 李志軍.面向嵌入式實時系統的動態內存管理方法研究[D].重慶:重慶大學,2007.

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

[5] 顧勝元,楊丹,黃海倫.嵌入式實時動態內存管理機制[J].計算機工程,2009,35(20):264-266.

姬希娜(工程師)，主要從事繼電保護及自動化產品的測試技術研究。