一種操作系統內存初始化優化算法

何 森，遲萬慶

(國防科技大學計算機學院，湖南 長沙 410073)

1 引言

在高性能處理器芯片的研發和仿真驗證過程中，為了滿足處理器對訪存高帶寬、低延遲的要求，通常采用一種基于數據親和性的多核處理器體系結構。吳俊杰[1]對所謂“數據親和性”進行了相關定義，可以認為若CPU對某個數據單元更具有“親和性”，則CPU訪問這個數據單元所需要的時間周期更短。在這種體系結構下，需要對CPU進行專門設計。本文所驗證的CPU就是將其中的多個核劃分為若干分組(panel)，每個panel又分為若干簇(cluster)。根據每個panel與整個存儲空間中各個物理存儲設備的親和性(如物理鏈路距離)不同，將存儲空間分成若干大空間，每個大空間對應一個panel，組成這個大空間的這些存儲設備與對應的panel中的CPU具有最高親和性。進一步地，又根據一個panel中各個cluster對這個大空間內各個存儲設備的親和性不同，將這個大空間劃分為若干子空間，每個子空間對應一個cluster。根據CPU對存儲單元“數據親和性”的不同而將存儲設備和CPU進行分組，就形成了一種NUMA結構[2,3]。當多核處理器中的CPU訪問所在cluster或者panel對應的具有“親和性”的存儲設備空間時，將具有高帶寬、低延遲的特點。

操作系統作為硬件資源的管理者，必須為用戶提供高效的支持方式以充分利用NUMA特性。一般而言，操作系統內核與系統固件通過約定方式，如ACPI、設備樹等方式獲取CPU的NUMA信息。本文開展的工作是通過讀取Boot-Loader傳入的設備樹文件，從中獲取每個NUMA結點包含的CPU和物理內存等資源信息。其中，物理內存信息是通過連續物理內存地址區域和物理內存大小來描述的。設備樹文件中一個典型的內存區域信息描述如下所示：

memory00{

device_type="memory";

reg=〈0x0 0x0 0x2 0x0〉;

numa-node-id=〈0x0〉

};

memory01{

device_type="memory";

reg=〈0x80 0x0 0x2 0x0〉;

numa-node-id=〈0x0〉

};

memory02{

device_type="memory";

reg=〈0x100 0x0 0x2 0x0〉;

numa-node-id=〈0x0〉

};

memory03{

device_type="memory";

reg=〈0x180 0x0 0x2 0x0〉;

numa-node-id=〈0x0〉

};

此代碼段指定了一個NUMA結點中的4個內存區域的起始地址、連續長度和所屬的NUMA結點。內核在讀取設備樹信息的同時，會根據連續內存區域的起始地址、大小以及相互之間的相交性進行一定的調整和規劃，確保每個NUMA結點中的連續內存區域按照起始地址從小到大的順序排列，確保彼此之間不存在相交的區域。

內核對內存的初始化過程是依據設備樹文件中對NUMA結點的劃分進行的。而一個結點的內存空間范圍，就是從所含的第一個內存區域的起始地址開始，到最后一個內存區域的結束地址結束(包括內存區域之間存在的空洞)。同時，如李慧娟等[4]所指出的，內核對整個內存空間按照功能又進行了一次分區，如圖1所示，內核將8 192 GB內存地址空間劃分為DMA區和NORMAL區。

Figure 1 Functional zones of memory space 圖1 內存空間功能分區

此時，以設備樹文件規劃的內存布局為例的一個NUMA結點內存空間布局的示意圖如圖2所示。

Figure 2 Layout of system memory space 圖2 系統內存空間分布示意圖

內核對NUMA結點內存的初始化過程可以概括為：順序處理每個結點，并為每個NUMA結點內的物理內存頁面建立內核數據結構，完成內存的初始化工作。

本文第2節揭示了操作系統內核在初始化NUMA結點內存，尤其是在虛擬仿真平臺上進行驗證時存在的問題，并提出可行的解決方案。第3節將給出該解決方案的算法描述，并輔以流程圖加以說明。 第4節則通過實驗對所提出的解決方案進行了驗證。

2 問題與研究

2.1 問題的產生

高性能計算機系統通常需要大量物理內存空間來支持高性能計算。為了滿足這種需求，并且兼顧未來繼續擴充物理內存的可能性，在采用上述“基于數據親和性”的NUMA架構的處理器中，通常為每個CPU核或panel劃分巨大的“親和性”地址空間。

如本文所研究的CPU硬件設計[5]，將整個CPU 64位地址空間劃分到多個本地目錄控制部件DCU(Directory Control Unit)上，每個DCU管理一段連續的CPU地址空間,并且將每4個CPU和2個DCU組成一個panel，通過一個訪存控制器MCU(Memory Control Unit)訪問存儲設備。而一個panel中所有DCU管理的地址空間就是這個panel的“親和性”地址空間，即構成了panel中各個CPU所屬的NUMA結點內存地址空間。這樣，在實際訪存時根據目標地址的相關位域將訪存的最終目的分配到各個DCU管理空間中。具體如何劃分CPU地址空間給各個DCU，則取決于不同的策略。如Diener等[6]提出的一種根據目標地址劃分的常規策略，即依據訪存目標虛擬地址的一些關鍵位域(如64位地址中的[42:39]位)，將CPU地址空間劃分為相同大小的連續地址塊(512 GB)，每個DCU管理一塊，然后將相鄰的幾個DCU組成一個panel，即構成一個NUMA結點的內存地址空間。

由于目前分配到NUMA結點的實際物理內存容量不足以填滿整個NUMA結點中多個DCU管理的CPU地址空間，這種CPU空間劃分方式導致了在位于相同NUMA結點中、不同DCU管理空間的物理內存設備在CPU地址空間中的范圍彼此之間不連續并且存在巨大空洞。例如，按上述DCU劃分以及panel組織方式，假設第1個16 GB的物理存儲設備位于NUMA結點0的第1個DCU管理內存空間分區(512 GB)中，則在設備樹中配置其地址空間為[0x0,0x400000000)，第2個16 GB存儲設備位于NUMA結點0的第2個DCU管理內存空間分區(512 GB)中，則配置其地址空間為：[0x8000000000,0x8400000000)。這2個存儲設備的地址空間之間就出現了多達496 GB的地址空洞，即NUMA結點0中出現了496 GB的地址空洞。此外，文獻[7]也指出，由于物理實現上的原因，使用NUMA結構的CPU體系在NUMA結點中通常存在內存空洞。

上述NUMA結點中出現的巨型空洞，會導致現行Linux內核在NUMA結點內存初始化過程中花費大量的時間，造成系統啟動緩慢。這種現象在虛擬仿真平臺(如Vinay 等[8]使用的Synopsis公司的ZEBU仿真平臺)上進行芯片驗證時帶來的負面影響更為嚴重。這是由于虛擬處理器芯片工作頻率(如1 MHz)比實際芯片的頻率(如1 GHz)低，因NUMA結點內存空洞引起的啟動時間過長問題更加突出，給CPU的研發帶來巨大的時間損耗。

2.2 問題的研究

現行Linux內核針對內存連續性情況采取了3種不同的內存管理模型，分別是平坦內存模型(FLAT Memory Mode)、非連續內存模型(Discontiguous Memory Mode)和稀疏內存模型(SPARSE Memory Mode)。其中，平坦內存模型通常用于UMA架構的處理器，所有CPU共享一段連續的公共物理內存空間。非連續內存模型針對整個內存地址空間中存在空洞，導致物理內存呈現多個大段連續區域、區域之間不連續的情形，常見于一般性NUMA架構的處理器內存模型。稀疏性內存模型則是針對熱插拔內存(hotplug memory)或者內存地址空間中有效物理內存區域過于稀疏、大面積存在空洞的情況。

針對CPU研發驗證過程中出現的NUMA結點內存巨大空洞所造成的Linux內核啟動緩慢問題，本文首先采用了SPARSE內存模型來試圖解決該問題。但是，經過實驗發現，通過Linux內核配置開啟SPARSE模型功能模塊，對于含有巨大內存空洞的NUMA結點初始化并沒有優化加速效果，在虛擬仿真平臺上Linux內核啟動仍然極為緩慢。

通過研究現行Linux內核發現，開啟SPARSE模型功能模塊后，在內核初始化過程中僅會為實際物理內存空間按1 GB大小建立映射表，便于后續初始化后內核管理物理頁幀。而對于實際物理頁面的初始化仍然按照非連續內存模型的情況進行處理，即按照NUMA結點的順序，對每個NUMA結點內的所有物理頁面(第一個有效物理內存區域的起始地址，到最后一個有效物理內存區域的結束地址之間)進行遍歷式初始化。這個過程對有效物理頁面進行初始化，建立相關的內核數據結構，對于無效的內存空洞則進行識別并跳過。

內核的非連續或稀疏型內存模型在初始化過程中采取了“窮舉”遍歷式方法初始化每個NUMA結點的內存，當遇到含有巨大內存空洞的NUMA結點時，內核在海量的空洞頁面上進行了無意義的處理。即使這些“處理”只是識別后跳過，但因空洞頁面數量巨大，以上述496 GB大小的空洞為例，會有130 023 424個4 KB大小的物理頁面需要遍歷處理，帶來了巨大的時間損耗。

2.3 解決方案

根據前述的研究可知，目前Linux內核中非連續內存模型以及稀疏內存模型都無法解決NUMA結點內存巨型空洞導致的NUMA結點內存初始化緩慢問題，因此要解決該問題只能從Linux內核的內存初始化算法入手。Linux內核是一個完整且復雜的源碼體系，一般的內核開發是基于內核提供的接口進行驅動開發、模塊開發等二次開發，要實現NUMA結點初始化算法的優化，就必須直接對內核本身進行修改，并且避免影響內核的接口以及相關數據結構。

本文提出了一種針對Linux內核NUMA結點內存初始化的改進優化算法。該算法基于常規的NUMA結點內存初始化算法，在保證原有的初始化行為正常實施的情況下，分析識別并跳過內存空洞，僅針對性地處理有效的內存區域，從而避免了對空洞進行無意義的識別和處理，最終節省了大量的初始化時間，加快了內核的啟動過程。

3 NUMA結點內存初始化優化算法

為了確保優化算法對Linux內核的影響最小，本文選擇直接在內核源代碼的相關初始化函數中進行函數邏輯和功能上的調整，來實現所需要的“空洞跳過”功能。

3.1 優化思路

在現有Linux內核中，NUMA結點內存初始化過程發生在內存區域記錄完畢之后。內核遍歷所有NUMA結點、并按照內核對內存實地址空間的功能分區順序初始化每個結點。在處理每個結點內存的過程中，將該結點內存空間中與每個內存功能分區相交的空間區域進行遍歷初始化，即逐一初始化每個有效/空洞物理內存頁。通過這個過程分析可以看到，現有內核對結點內存的初始化，實際上是對結點中所有有效物理內存頁以及空洞所在內存頁進行逐一遍歷并進行相關初始化工作。

本文對上述流程進行優化，避免內核對NUMA結點內存中的空洞做出無意義的識別和處理。優化的原則是在不修改Linux內核實質性操作的基礎上，對結點內存初始化過程加以優化和提速。優化算法的基本原理和依據如下所示：

(1)設備樹中規劃的每個內存區域都是連續的，并且是一個左閉右開區間，描述的是一段有效物理內存區域，并且注明了所屬的NUMA結點ID號；

(2)經過內核讀取、處理后，不論是在整體上或是在所屬的NUMA結點中，保存在內核中的各個內存區域之間具有邏輯順序，即第i號內存區域的起始地址必然小于第i+1號內存區域起始地址，且第i號內存區域的空間范圍必然與第i+1號內存區域空間范圍不相交；

(3)依照上述內存區域的排列順序，對每個結點內的所有內存區域進行針對性處理，即可處理完結點中的所有有效物理內存頁面。

3.2 算法描述

根據上述原理和依據，優化算法流程圖如圖3所示。

Figure 3 Flow chart of improved algorithm 圖3 優化算法流程圖

算法步驟如下所示：

(1)內核讀取設備樹信息，并建立相關數據結構，包括NUMA結點、連續內存區域等對象。

(2)內核針對每個內存結點，對比其內存空間范圍與內存實地址空間內所有功能分區的相交性，記錄所有產生的相交區域Zone，保存在內核結點的數據結構中。

(3)針對步驟(2)中記錄的、屬于該結點的每個相交區域(Zone)的內存進行有效化處理：

① 順序遍歷設備樹中記錄的、屬于該NUMA結點所有連續內存區域；

② 對每個連續內存區域求取與當前處理的Zone的交集A；

③ 若A存在且不為空，則集合A所記錄的內存空間都是有效物理內存，直接進行初始化處理。

(4)繼續處理后續結點。

這里以圖1和圖2所示的內存空間為例說明上述算法流程。圖2中第0個NUMA結點與圖1所示的系統內存空間功能分區相交，得到Zone DMA32和Zone Normal 2個相交區域。當按上述算法步驟(2)初始化結點0時，會先后處理這2個相交區域。當按上述算法的步驟(3)處理相交區域Zone DMA32時，只會找到連續內存區域Memory00，并且只初始化Memory00的[0,0x1000 0000)范圍。然后按算法步驟(3)處理相交區域Zone Normal時，則會先后找到連續內存區域Memory00～Memory03，并逐個初始化它們位于相交區域Zone Normal中的物理頁面。

3.3 算法核心實現

按照算法原理和流程圖，本文在Linux內核NUMA結點內存初始化等部分中實現了所提算法，其中算法核心部分如下所示：

void_meminit memmap_init_zone(unsigned longsize,intnid, unsigned longzone, unsigned longstart_pfn, enum memmap_contextcontext, struct vmem_altmap*altmap)

{

unsigned longend_pfn=start_pfn+size;

unsigned longregion_start,region_end;

unsigned longreal_start,real_end;

inti;

pg_data_t*pgdat=NODE_DATA(nid);

unsigned longpfn;

unsigned longnr_initialised=0;

struct page*page;

#ifdefCONFIG_HAVE_MEMBLOCK_NODE_MAP struct memblock_region*r=NULL,*tmp;

#endif

real_start=start_pfn,real_end=end_pfn;

if(highest_memmap_pfn

highest_memmap_pfn=end_pfn-1;

if(altmap&&start_pfn==altmap→base_pfn)

start_pfn+=altmap→reserve;

#ifdefCONFIG_SKIP_NUMA_HOLES

for_each_mem_pfn_range(i,nid,®ion_start,®ion_end,NULL)

{

if(real_start==end_pfn)

break;

if(region_end<=real_start)

continue;

real_start=max(real_start,region_start);

real_end=min(end_pfn,region_end);

#else

real_start=start_pfn;

real_end=end_pfn;

#endif

for(pfn=real_start,pfn

{

?

}

#ifdefCONFIG_SKIP_NUMA_HOLES

real_start=real_end;

}

#endif

}

4 實驗結果

為驗證本文所提出的優化算法，在如下環境中進行實驗：將按上述解決方案修改好的內核源代碼進行編譯后，在ZEBU虛擬仿真平臺上搭建的16核CPU、主頻1 446 KHz的虛擬機器上運行該內核。通過修改設備樹文件，測試在不同內存空間布局下對NUMA結點初始化的速度。通常情況下，操作系統是要初始化多個NUMA結點(以本實驗為例，結點數目為1～8個)的內存，但實際上根據本文第2節描述的目標CPU的特性，本實驗每個NUMA結點的內存大小、布局特性相同，結點內部空洞也類似，因此，在實際的驗證工作中針對一個NUMA結點內存的初始化過程進行測試對比，即可驗證本文優化算法對所有NUMA結點初始化效率的增益影響。

實驗設置如下幾組內存布局：

(1)1個NUMA結點，1個8 GB的連續內存區域，無空洞；

(2)1個NUMA結點，2個8 GB連續內存區域，如圖2中由Memory00+Memory01組成的內存布局，存在504 GB大小的空洞；

(3)1個NUMA結點，3個8 GB連續內存區域，如圖2中由Memory00+Memory01+Memory02組成的內存布局，存在1 008 GB大小的空洞；

(4)1個NUMA結點，4個8 GB連續內存區域，如圖2中由Memory00+Memory01+Memory02+Memory03組成的內存布局，存在1 512 GB大小的空洞；

(5)1個NUMA結點，2個8 GB連續內存區域，如圖2中由Memory00+Memory02組成的內存布局，存在1 016 GB大小的空洞；

(6)1個NUMA結點，2個8 GB連續內存區域，如圖2中由Memory00+Memory03組成的內存布局，存在1 528 GB大小的空洞。

在上述實驗組中，組(2)、組(5)和組(6)用于測試在相同有效內存情況下，隨著空洞大小的增加，優化算法和現有Linux內核初始化算法的效率差異情況。組(3)和組(5)、組(4)和組(6)測試在內存空洞基本相同的情況下，有效內存的增加對優化算法和現有Linux內核初始化算法的耗時影響情況。實驗結果如表1所示。

Table 1 Analysis of time of NUMA node initialization 表1 NUMA結點初始化用時分析

實驗結果分析如下：

(1)在相同有效內存的情況下，隨著空洞的不斷增大，現有Linux內核的初始化算法耗時顯著增加，而本文優化算法對結點初始化的耗時則不受內存空洞大小的影響；

(2)在空洞大小基本相等的情況下，有效內存的增加對現有Linux內核初始化和本文優化算法初始化的耗時影響基本相同，即本文優化算法對于有效內存的初始化效率與現有Linux內核保持一致，不會對原有的初始化算法帶來負面影響。

5 結束語

本文討論了Linux內核由于可能存在的物理內存巨大空洞而導致的內核啟動緩慢問題。這種內存空洞可能是由于硬件設計如CPU的“數據親和性”模型帶來的，也可能是由其他因素引起的。本文針對該問題提出了一種解決方案，該方案對現有Linux內核中NUMA結點初始化算法進行優化，在不影響對有效物理內存正確初始化的前提下，能夠有效識別并跳過內存空間中的空洞，避免了對空洞內物理頁面的無意義遍歷，實現了快速高效的結點初始化，加快了內核啟動過程，尤其是在此類CPU的仿真驗證階段，可以帶來明顯的效率提升。

需要指出的是，文中所研究的系統物理內存空洞是由于CPU基于數據親和性模型建立的NUMA體系結構引起的，實際情況中可能存在因其他原因導致的物理內存空洞現象。但是，本文所提算法并不區分引起內存空洞的原因，而是直接針對初始化過程中的內存空洞這一現象進行優化。