何 森，遲萬慶

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

1 引言

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

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

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結(jié)點中的4個內(nèi)存區(qū)域的起始地址、連續(xù)長度和所屬的NUMA結(jié)點。內(nèi)核在讀取設(shè)備樹信息的同時，會根據(jù)連續(xù)內(nèi)存區(qū)域的起始地址、大小以及相互之間的相交性進行一定的調(diào)整和規(guī)劃，確保每個NUMA結(jié)點中的連續(xù)內(nèi)存區(qū)域按照起始地址從小到大的順序排列，確保彼此之間不存在相交的區(qū)域。

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

Figure 1 Functional zones of memory space 圖1 內(nèi)存空間功能分區(qū)

此時，以設(shè)備樹文件規(guī)劃的內(nèi)存布局為例的一個NUMA結(jié)點內(nèi)存空間布局的示意圖如圖2所示。

Figure 2 Layout of system memory space 圖2 系統(tǒng)內(nèi)存空間分布示意圖

內(nèi)核對NUMA結(jié)點內(nèi)存的初始化過程可以概括為：順序處理每個結(jié)點，并為每個NUMA結(jié)點內(nèi)的物理內(nèi)存頁面建立內(nèi)核數(shù)據(jù)結(jié)構(gòu)，完成內(nèi)存的初始化工作。

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

2 問題與研究

2.1 問題的產(chǎn)生

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

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

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

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

2.2 問題的研究

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

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

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

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

2.3 解決方案

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

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

3 NUMA結(jié)點內(nèi)存初始化優(yōu)化算法

為了確保優(yōu)化算法對Linux內(nèi)核的影響最小，本文選擇直接在內(nèi)核源代碼的相關(guān)初始化函數(shù)中進行函數(shù)邏輯和功能上的調(diào)整，來實現(xiàn)所需要的“空洞跳過”功能。

3.1 優(yōu)化思路

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

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

(1)設(shè)備樹中規(guī)劃的每個內(nèi)存區(qū)域都是連續(xù)的，并且是一個左閉右開區(qū)間，描述的是一段有效物理內(nèi)存區(qū)域，并且注明了所屬的NUMA結(jié)點ID號；

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

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

3.2 算法描述

根據(jù)上述原理和依據(jù)，優(yōu)化算法流程圖如圖3所示。

Figure 3 Flow chart of improved algorithm 圖3 優(yōu)化算法流程圖

算法步驟如下所示：

(1)內(nèi)核讀取設(shè)備樹信息，并建立相關(guān)數(shù)據(jù)結(jié)構(gòu)，包括NUMA結(jié)點、連續(xù)內(nèi)存區(qū)域等對象。

(2)內(nèi)核針對每個內(nèi)存結(jié)點，對比其內(nèi)存空間范圍與內(nèi)存實地址空間內(nèi)所有功能分區(qū)的相交性，記錄所有產(chǎn)生的相交區(qū)域Zone，保存在內(nèi)核結(jié)點的數(shù)據(jù)結(jié)構(gòu)中。

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

① 順序遍歷設(shè)備樹中記錄的、屬于該NUMA結(jié)點所有連續(xù)內(nèi)存區(qū)域；

② 對每個連續(xù)內(nèi)存區(qū)域求取與當(dāng)前處理的Zone的交集A；

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

(4)繼續(xù)處理后續(xù)結(jié)點。

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

3.3 算法核心實現(xiàn)

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

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 實驗結(jié)果

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

實驗設(shè)置如下幾組內(nèi)存布局：

(1)1個NUMA結(jié)點，1個8 GB的連續(xù)內(nèi)存區(qū)域，無空洞；

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

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

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

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

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

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

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

實驗結(jié)果分析如下：

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

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

5 結(jié)束語

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

需要指出的是，文中所研究的系統(tǒng)物理內(nèi)存空洞是由于CPU基于數(shù)據(jù)親和性模型建立的NUMA體系結(jié)構(gòu)引起的，實際情況中可能存在因其他原因?qū)е碌奈锢韮?nèi)存空洞現(xiàn)象。但是，本文所提算法并不區(qū)分引起內(nèi)存空洞的原因，而是直接針對初始化過程中的內(nèi)存空洞這一現(xiàn)象進行優(yōu)化。