《Linux原理與結(jié)構(gòu)》課件第6章

第六章物理內(nèi)存管理6.1內(nèi)存管理系統(tǒng)組成結(jié)構(gòu) 6.2伙伴內(nèi)存管理6.3邏輯內(nèi)存管理6.4對(duì)象內(nèi)存管理在操作系統(tǒng)營(yíng)造的虛擬社會(huì)中，除了被時(shí)鐘管理部分管理的時(shí)間之外，另一個(gè)重要的基石就是空間。對(duì)空間的管理是操作系統(tǒng)的另一項(xiàng)核心工作。

操作系統(tǒng)所管理的空間可大致分為內(nèi)存空間和外存空間，其中內(nèi)存空間可被處理器直接訪問的，是最基礎(chǔ)的空間。內(nèi)存空間是計(jì)算機(jī)系統(tǒng)中的重要資源，操作系統(tǒng)中的進(jìn)程運(yùn)行在內(nèi)存空間中，操作系統(tǒng)本身也運(yùn)行在內(nèi)存空間中，離開了內(nèi)存空間，計(jì)算機(jī)系統(tǒng)將無法運(yùn)行。另一方面，內(nèi)存空間又是計(jì)算機(jī)系統(tǒng)中的緊缺資源，操作系統(tǒng)及其管理的所有進(jìn)程共享同一塊物理內(nèi)存空間，其容量似乎永遠(yuǎn)都無法滿足進(jìn)程對(duì)它的需求。因而有必要對(duì)內(nèi)存空間實(shí)施嚴(yán)格的、精細(xì)的管理。

內(nèi)存管理的工作艱巨而繁瑣，可大致分成兩大部分：物理內(nèi)存管理部分管理系統(tǒng)中的物理內(nèi)存空間，負(fù)責(zé)物理內(nèi)存的分配、釋放、回收等；虛擬內(nèi)存管理部分管理進(jìn)程的虛擬內(nèi)存空間，負(fù)責(zé)虛擬內(nèi)存的創(chuàng)建、撤銷、換入、換出及虛擬地址到物理地址的轉(zhuǎn)換等。物理內(nèi)存管理的主要任務(wù)是快速、合理、高效地分配與回收物理內(nèi)存資源以盡力提高其利用率；虛擬內(nèi)存管理的主要任務(wù)是為進(jìn)程模擬出盡可能大的內(nèi)存空間并實(shí)現(xiàn)它們間的隔離與保護(hù)。在操作系統(tǒng)長(zhǎng)期的發(fā)展過程中，內(nèi)存管理部分由簡(jiǎn)到繁，不斷演變，正逐步走向成熟。

為解決復(fù)雜的內(nèi)存管理問題，Linux采用了分而治之的設(shè)計(jì)方法，將內(nèi)存管理工作交給幾個(gè)既相互獨(dú)立又相互關(guān)聯(lián)的管理器分別負(fù)責(zé)。這些內(nèi)存管理器各司其職，互相配合，共同管理系統(tǒng)中的內(nèi)存空間，如圖6.1所示。6.1內(nèi)存管理系統(tǒng)組成結(jié)構(gòu)圖6.1內(nèi)存管理系統(tǒng)的組成結(jié)構(gòu)

Linux的物理內(nèi)存管理子系統(tǒng)運(yùn)行在內(nèi)核空間，僅為內(nèi)核提供服務(wù)。內(nèi)核需要的物理內(nèi)存通常是連續(xù)的，而且應(yīng)該有內(nèi)核線性地址(內(nèi)核用線性地址訪問物理內(nèi)存)。如果按申請(qǐng)的規(guī)模劃分，內(nèi)核對(duì)物理內(nèi)存的需求大致可分為中規(guī)模(幾個(gè)物理上連續(xù)的頁(yè))、小規(guī)模(若干字節(jié))和大規(guī)模(多個(gè)邏輯上連續(xù)的頁(yè))等幾類。為了滿足內(nèi)核對(duì)物理內(nèi)存的不同需求，Linux將物理內(nèi)存管理子系統(tǒng)進(jìn)一步劃分成三個(gè)管理器，即伙伴內(nèi)存管理器、對(duì)象內(nèi)存管理器和邏輯內(nèi)存管理器?；锇閮?nèi)存管理器是物理內(nèi)存的真正管理者，是物理內(nèi)存管理的基礎(chǔ)?；锇閮?nèi)存管理器以頁(yè)塊(若干個(gè)連續(xù)的物理頁(yè))為單位分配、釋放、回收物理內(nèi)存，雖比較粗放，但極為快速、高效，且不會(huì)產(chǎn)生外部碎片。

對(duì)象內(nèi)存管理器建立在伙伴內(nèi)存管理器之上，是一種細(xì)粒度的物理內(nèi)存管理器。對(duì)象內(nèi)存管理器將來自伙伴內(nèi)存管理器的內(nèi)存頁(yè)塊劃分成小內(nèi)存對(duì)象，以滿足內(nèi)核對(duì)小內(nèi)存的需求，并負(fù)責(zé)將回收到的小內(nèi)存對(duì)象組合成內(nèi)存頁(yè)塊后還給伙伴內(nèi)存管理器。由于伙伴內(nèi)存管理器只能提供物理上連續(xù)的內(nèi)存，常常無法滿足內(nèi)核對(duì)大內(nèi)存的需求，因而Linux實(shí)現(xiàn)了邏輯內(nèi)存管理器，專門為內(nèi)核提供邏輯上連續(xù)、物理上可不連續(xù)的大內(nèi)存服務(wù)。

在系統(tǒng)初始化期間，Linux還提供了一個(gè)初始內(nèi)存管理器Bootmem，用于向內(nèi)核提供物理內(nèi)存服務(wù)。但在伙伴內(nèi)存管理器啟動(dòng)之后，Bootmem已讓出管理權(quán)，被停止了工作。除內(nèi)核之外，內(nèi)存管理的主要服務(wù)對(duì)象是進(jìn)程。與內(nèi)核不同，每個(gè)進(jìn)程都需要一塊容量足夠大的獨(dú)立的虛擬內(nèi)存，用于暫存它的程序、數(shù)據(jù)、堆棧等。因而內(nèi)存管理的另一個(gè)核心工作是利用有限的物理內(nèi)存和外存設(shè)備為系統(tǒng)中的每個(gè)進(jìn)程都模擬出一塊連續(xù)的虛擬內(nèi)存，并實(shí)現(xiàn)各虛擬內(nèi)存之間的隔離與保護(hù)。Linux中負(fù)責(zé)進(jìn)程內(nèi)存管理工作的是虛擬內(nèi)存管理器和用戶內(nèi)存管理器。用戶內(nèi)存管理器運(yùn)行在用戶空間中，負(fù)責(zé)進(jìn)程虛擬內(nèi)存(在堆中)的動(dòng)態(tài)分配、釋放與回收(如庫(kù)函數(shù)malloc()、free()等)。用戶內(nèi)存管理器一般在函數(shù)庫(kù)(如Libc)中實(shí)現(xiàn)，不屬于內(nèi)核的組成部分，但需要內(nèi)核中的虛擬內(nèi)存管理器為其提供幫助。

本章主要分析Linux的物理內(nèi)存管理部分，虛擬內(nèi)存管理部分將在第8章中討論。

伙伴內(nèi)存管理器管理系統(tǒng)中的物理內(nèi)存，因采用伙伴算法而得名。所謂物理內(nèi)存就是計(jì)算機(jī)系統(tǒng)中實(shí)際配置的內(nèi)存。根據(jù)處理器與物理內(nèi)存的組織關(guān)系可將計(jì)算機(jī)系統(tǒng)分成兩大類。在UMA(UniformMemoryAccess)系統(tǒng)中，每個(gè)處理器都可以訪問到所有的物理內(nèi)存，且訪問速度都相同。在NUMA(Non-UniformMemoryAccess)系統(tǒng)中，處理器雖可訪問到所有的物理內(nèi)存，但訪問速度略有差異。6.2伙伴內(nèi)存管理事實(shí)上，一個(gè)NUMA系統(tǒng)由多個(gè)節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)都有自己的處理器和物理內(nèi)存，處理器對(duì)節(jié)點(diǎn)內(nèi)部?jī)?nèi)存的訪問速度較快，對(duì)其它節(jié)點(diǎn)的內(nèi)存訪問速度較慢。UMA是NUMA的特例，只有一個(gè)節(jié)點(diǎn)的NUMA就是UMA。

計(jì)算機(jī)系統(tǒng)中的物理內(nèi)存被統(tǒng)一編址，其中的每個(gè)字節(jié)都有一個(gè)物理地址，只有通過物理地址才能訪問到物理內(nèi)存單元。在一個(gè)計(jì)算機(jī)系統(tǒng)中，可以使用的所有物理地址的集合稱為物理地址空間。物理地址空間的大小取決于地址線的位數(shù)。物理地址空間中的地址除可用于訪問物理內(nèi)存之外，還可用于訪問固件中的ROM(如BIOS)及設(shè)備中的寄存器(如APIC中的寄存器等)。不能訪問任何實(shí)體的物理地址區(qū)間稱為空洞，空洞中的物理地址是無效的。在初始化時(shí)，系統(tǒng)已經(jīng)通過BIOSint15h的e820服務(wù)獲得了物理地址空間的布局信息，并已利用該信息完成了伙伴內(nèi)存管理器的初始化。6.2.1伙伴內(nèi)存管理結(jié)構(gòu)

物理內(nèi)存的管理方法很多，如靜態(tài)分區(qū)法、動(dòng)態(tài)分區(qū)法、伙伴算法等，衡量算法好壞的標(biāo)準(zhǔn)主要是效率和利用率，影響的因素主要是管理粒度。細(xì)粒度的管理具有較高的利用率，但算法比較復(fù)雜；粗粒度的管理具有較高的效率，但利用率不高?；锇閮?nèi)存管理器采用伙伴算法管理它的物理內(nèi)存，管理的最小粒度是1頁(yè)(4KB)。

為了實(shí)現(xiàn)頁(yè)粒度的內(nèi)存管理，需要一種數(shù)據(jù)結(jié)構(gòu)來描述每一個(gè)物理頁(yè)的使用情況?；锇閮?nèi)存管理器為每個(gè)物理頁(yè)準(zhǔn)備了一個(gè)32字節(jié)的page結(jié)構(gòu)，其格式如圖6.2所示。圖6.2page結(jié)構(gòu)在Linux的發(fā)展過程中，page結(jié)構(gòu)在不斷演變，最重要的是其中的三項(xiàng)：

(1)標(biāo)志flags是一個(gè)4字節(jié)的位圖，用于描述物理頁(yè)的屬性或狀態(tài)。常用的屬性如表6.1所示。flags的前端還記錄著頁(yè)所屬的節(jié)點(diǎn)和管理區(qū)的編號(hào)。

(2)引用計(jì)數(shù)_count用于記錄物理頁(yè)的當(dāng)前用戶數(shù)，_count為0的頁(yè)是空閑的。

(3)通用鏈表節(jié)點(diǎn)lru用于將page結(jié)構(gòu)鏈入到需要的隊(duì)列中。

另外，page結(jié)構(gòu)中還包含幾個(gè)復(fù)用域，如index、freelist和free共用同一個(gè)域，它們的意義隨應(yīng)用場(chǎng)合的不同而變化。復(fù)用域的使用使page結(jié)構(gòu)既可滿足不同的應(yīng)用需求，又不至于變得太大。

表6.1物理頁(yè)的屬性續(xù)表毫無疑問，系統(tǒng)中存在很多page結(jié)構(gòu)，必須另外建立一種結(jié)構(gòu)來組織、管理它們。最簡(jiǎn)單的管理方法是定義一個(gè)page結(jié)構(gòu)數(shù)組。由于計(jì)算機(jī)系統(tǒng)中的物理內(nèi)存頁(yè)數(shù)不是固定的，因而只能在檢測(cè)到物理內(nèi)存大小之后動(dòng)態(tài)地建立該數(shù)組。page結(jié)構(gòu)數(shù)組可能很大，為節(jié)約物理內(nèi)存，應(yīng)盡量壓縮page結(jié)構(gòu)的大小。早期的Linux僅在系統(tǒng)初始化時(shí)建立了一個(gè)page結(jié)構(gòu)數(shù)組，稱為mem_map[]。由于需要支持NUMA系統(tǒng)，新版本的Linux將物理內(nèi)存劃分成多個(gè)節(jié)點(diǎn)，并為每個(gè)節(jié)點(diǎn)建立了一個(gè)page結(jié)構(gòu)數(shù)組。Linux的節(jié)點(diǎn)由一個(gè)名字古怪的結(jié)構(gòu)描述，其主要內(nèi)容如下：

typedefstructpglist_data{

structzone node_zones[MAX_NR_ZONES]; //所有管理區(qū)

structzonelist node_zonelists[MAX_ZONELISTS]; //嘗試序列

int nr_zones; //節(jié)點(diǎn)中的管理區(qū)數(shù)

structpage *node_mem_map; //page結(jié)構(gòu)數(shù)組

unsignedlong node_start_pfn; //開始頁(yè)號(hào)

unsignedlong node_present_pages; //總頁(yè)數(shù)，不含空洞

unsignedlong node_spanned_pages; //總頁(yè)數(shù)，含空洞

wait_queue_head_t kswapd_wait; //回收進(jìn)程等待隊(duì)列

structtask_struct *kswapd; //物理內(nèi)存回收進(jìn)程

int kswapd_max_order; //上次回收的尺寸

}pg_data_t;

一個(gè)pglist_data結(jié)構(gòu)描述一個(gè)節(jié)點(diǎn)內(nèi)部的物理內(nèi)存，對(duì)應(yīng)物理地址空間中的一塊連續(xù)的地址區(qū)間，其開始頁(yè)號(hào)是node_start_pfn，大小是node_spanned_pages頁(yè)。由于空洞的存在，節(jié)點(diǎn)中的實(shí)際物理頁(yè)數(shù)node_present_pages可能小于node_spanned_pages。節(jié)點(diǎn)內(nèi)部的page結(jié)構(gòu)數(shù)組是node_mem_map，其中的每個(gè)page結(jié)構(gòu)描述節(jié)點(diǎn)內(nèi)的一個(gè)物理頁(yè)，包括空洞頁(yè)。系統(tǒng)中所有的節(jié)點(diǎn)結(jié)構(gòu)被組織在數(shù)組node_data中。

structpglist_data*node_data[MAX_NUMNODES]_read_mostly;

在基于X86的個(gè)人計(jì)算機(jī)或服務(wù)器上，盡管可能配置有多個(gè)處理器，但其內(nèi)存訪問模型通常是UMA，因而系統(tǒng)中僅有一個(gè)節(jié)點(diǎn)，稱為contig_page_data。

即使屬于同一個(gè)節(jié)點(diǎn)，物理頁(yè)的特性也可能不同，如有些物理頁(yè)有永久性的內(nèi)核線性地址而另一些物理頁(yè)沒有，有些物理頁(yè)可用作ISADMA而另一些物理頁(yè)不能等。不同特性的物理頁(yè)有著不同的用處，應(yīng)采用不同的管理方法，或者說應(yīng)區(qū)別對(duì)待一個(gè)節(jié)點(diǎn)內(nèi)部的物理內(nèi)存?；锇閮?nèi)存管理器將一個(gè)節(jié)點(diǎn)內(nèi)部的物理內(nèi)存進(jìn)一步劃分成管理區(qū)。每個(gè)節(jié)點(diǎn)都可以定義2到4個(gè)管理區(qū)，其中ZONE_DMA區(qū)管理的是16MB以下的物理內(nèi)存，可供老式DMA使用；ZONE_DMA32區(qū)管理的是可供32位設(shè)備做DMA使用的物理內(nèi)存(4GB以下)，僅用于64位系統(tǒng)；ZONE_NORMAL區(qū)管理的是除ZONE_DMA之外的低端物理內(nèi)存，可供常規(guī)使用；ZONE_HIGHMEM區(qū)管理的是沒有內(nèi)核線性地址的高端物理內(nèi)存，可供特殊使用；ZONE_MOVABLE區(qū)是虛擬的，它管理的內(nèi)存來自其它幾個(gè)區(qū)，都是可動(dòng)態(tài)遷移的物理頁(yè)，用于內(nèi)存的熱插拔(MemoryHotplug)和緊縮，其大小由命令行參數(shù)指定，缺省情況下為空。32位系統(tǒng)中沒有ZONE_DMA32區(qū)，64位系統(tǒng)中沒有ZONE_HIGHMEM區(qū)。內(nèi)存管理區(qū)由結(jié)構(gòu)zone描述，其主要內(nèi)容包括如下幾個(gè)：

(1)開始頁(yè)號(hào)zone_start_pfn表示管理區(qū)的開始位置。

(2)總頁(yè)數(shù)spanned_pages表示管理區(qū)的大小，含空洞。

(3)可分配頁(yè)數(shù)present_pages表示管理區(qū)中的可用物理內(nèi)存總頁(yè)數(shù)，不含空洞。

(4)基準(zhǔn)線watermark[]描述管理區(qū)中空閑內(nèi)存的三個(gè)基準(zhǔn)指標(biāo)。

(5)空閑頁(yè)塊隊(duì)列free_area[]用于組織不同大小的空閑頁(yè)塊。

(6)

LRU隊(duì)列l(wèi)ru[]用于描述區(qū)內(nèi)各類物理頁(yè)的最近使用情況。

(7)熱頁(yè)隊(duì)列pageset用于暫存剛被釋放的單個(gè)物理頁(yè)。

(8)遷移類型位圖pageblock_flags用于描述各頁(yè)組的遷移類型。

(9)預(yù)留空間總量lowmem_reserve[]用于記錄應(yīng)為其它管理區(qū)預(yù)留的內(nèi)存頁(yè)數(shù)。

一個(gè)管理區(qū)管理一塊連續(xù)的物理地址空間，其中可能包含空洞。圖6.3是物理內(nèi)存的一種劃分方式。

圖6.3物理內(nèi)存空間的劃分圖6.3中的物理內(nèi)存空間由2個(gè)節(jié)點(diǎn)構(gòu)成，其中節(jié)點(diǎn)1被劃分成3個(gè)管理區(qū)，節(jié)點(diǎn)2被劃分成2個(gè)管理區(qū)。兩個(gè)節(jié)點(diǎn)間有一塊空洞，節(jié)點(diǎn)1的第3個(gè)管理區(qū)中也有一塊空洞。由于page結(jié)構(gòu)數(shù)組所占空間無法再做它用，因而也被算做空洞。

伙伴內(nèi)存管理器以管理區(qū)為單位管理物理內(nèi)存，包括單個(gè)物理頁(yè)及多個(gè)連續(xù)物理頁(yè)的分配、釋放、回收等。雖然利用page結(jié)構(gòu)數(shù)組能夠?qū)崿F(xiàn)單個(gè)物理頁(yè)的管理，但卻難以進(jìn)行多個(gè)連續(xù)物理頁(yè)的分配。為解決連續(xù)物理頁(yè)的管理問題，Linux引入了頁(yè)塊的概念。一個(gè)頁(yè)塊(pageblock)就是一組連續(xù)的物理頁(yè)。為規(guī)范起見，Linux規(guī)定頁(yè)塊的大小必須是2i(i=0,1,…,10)頁(yè)，頁(yè)塊中起始頁(yè)的編號(hào)必須是頁(yè)塊大小的倍數(shù)。頁(yè)塊是一個(gè)動(dòng)態(tài)管理單元，相鄰的小頁(yè)塊可以組合成大頁(yè)塊，大頁(yè)塊也可拆分成小頁(yè)塊。頁(yè)塊以起始頁(yè)為代表，起始頁(yè)的編號(hào)就是整個(gè)頁(yè)塊的編號(hào)，起始頁(yè)的page結(jié)構(gòu)中記錄著整個(gè)頁(yè)塊的管理信息。

伙伴內(nèi)存管理器以頁(yè)塊為單位管理各區(qū)中的物理內(nèi)存，因而需要為每一種大小的空閑頁(yè)塊準(zhǔn)備一個(gè)隊(duì)列。Linux為每個(gè)管理區(qū)都定義了一個(gè)free_area[]數(shù)組，用于組織區(qū)內(nèi)的空閑頁(yè)塊。大小為2i頁(yè)的空閑頁(yè)塊被組織在free_area的第i隊(duì)列中。第i隊(duì)列中的1個(gè)大小為2i頁(yè)的頁(yè)塊可以被劃分成2個(gè)大小為2i-1頁(yè)的小頁(yè)塊(伙伴)并掛在第i-1隊(duì)列中；第i-1隊(duì)列中的2個(gè)小伙伴可以被合并成大小為2i頁(yè)的頁(yè)塊并掛在第i隊(duì)列中。

在早期的版本中，伙伴內(nèi)存管理器為每一種大小的空閑頁(yè)塊準(zhǔn)備了一個(gè)隊(duì)列。然而，新版本的伙伴內(nèi)存管理器需要面對(duì)內(nèi)存遷移問題，為每一種大小的空閑頁(yè)塊準(zhǔn)備一個(gè)隊(duì)列已無法滿足需要。所謂內(nèi)存遷移就是將頁(yè)塊從一個(gè)物理位置移動(dòng)到另一個(gè)物理位置，也就是將一個(gè)頁(yè)塊的內(nèi)容拷貝到另一個(gè)頁(yè)塊中，并保持移動(dòng)前后的虛擬或線性地址不變。內(nèi)存遷移的需求主要來自兩個(gè)方面：為了加快NUMA內(nèi)存的訪問速度，需要將處理器經(jīng)常訪問的內(nèi)存遷移到離它最近的節(jié)點(diǎn)中；為了解決內(nèi)存碎化問題，需要進(jìn)行物理內(nèi)存緊縮，將分散的小空閑頁(yè)塊合并成大頁(yè)塊。

為了實(shí)現(xiàn)內(nèi)存遷移，需要進(jìn)一步區(qū)分頁(yè)塊的遷移屬性。事實(shí)上，可將物理內(nèi)存頁(yè)塊大致分成五種類型，不可遷移型(MIGRATE_UNMOVABLE)頁(yè)塊只能駐留在物理內(nèi)存的固定位置(如內(nèi)核頁(yè))，不能移動(dòng)；可回收型(MIGRATE_RECLAIMABLE)頁(yè)塊中的內(nèi)容可先被釋放而后再在新的位置上重新生成(如來自映像文件的頁(yè))；可遷移型(MIGRATE_MOVABLE)頁(yè)塊中的內(nèi)容可被拷貝到新的位置而不改變其虛擬或線性地址(如用戶進(jìn)程中的虛擬頁(yè))；預(yù)留型(MIGRATE_RESERVE)頁(yè)塊是留給內(nèi)存不足時(shí)應(yīng)急使用的；孤立型(MIGRATE_ISOLATE)頁(yè)塊用于在NUMA的節(jié)點(diǎn)間遷移，不可分配。顯然，同一類型的頁(yè)塊應(yīng)集中在一起，不同類型的頁(yè)塊不應(yīng)相互交叉。不加限制的頁(yè)塊分配會(huì)影響頁(yè)塊的合并，如圖6.4所示，由于第13頁(yè)不可遷移，前16個(gè)空閑頁(yè)就不能合并成大頁(yè)塊。

圖6.4不可遷移頁(yè)影響頁(yè)塊合并的情況如果可遷移型頁(yè)塊內(nèi)部不存在不可遷移的頁(yè)，那么將其中的非空閑頁(yè)遷移出去之后即可合并成大的空閑頁(yè)塊。為了聚合同一類型的頁(yè)塊，伙伴內(nèi)存管理器預(yù)先將區(qū)中的物理內(nèi)存劃分成了大小為1024頁(yè)的頁(yè)組，并為每個(gè)頁(yè)組指定了一個(gè)遷移類型。頁(yè)塊的分配按照遷移類型進(jìn)行。如此以來，在可遷移型頁(yè)組中就不太可能再出現(xiàn)其它類型的頁(yè)塊。管理區(qū)中的位圖pageblock_flags(3位一組)用于標(biāo)識(shí)各頁(yè)組的遷移類型，如圖6.5所示。

圖6.5頁(yè)塊的遷移類型每個(gè)物理頁(yè)都屬于一個(gè)頁(yè)組，都有一個(gè)確定的遷移類型，不管它是空閑的還是正在被使用的。當(dāng)然，頁(yè)組的遷移類型是可以改變的。

區(qū)分頁(yè)組的遷移類型與定義ZONE_MOVABLE區(qū)的作用一樣，但更加精細(xì)。

劃分了遷移類型之后，就應(yīng)為每一種類型的空閑頁(yè)塊準(zhǔn)備一個(gè)隊(duì)列。新版本的伙伴內(nèi)存管理器為每一種大小的空閑頁(yè)塊準(zhǔn)備了5個(gè)隊(duì)列，分別用于組織5種不同遷移類型的空閑頁(yè)塊。結(jié)構(gòu)free_area的定義如下：

structfree_area{

tructlist_head free_list[MIGRATE_TYPES]; //

5個(gè)空閑頁(yè)塊隊(duì)列

unsignedlong nr_free; //空閑頁(yè)塊數(shù)

};

圖6.6是一個(gè)管理區(qū)中的空閑頁(yè)塊隊(duì)列示意圖。左邊是早期的free_area[]，每種大小的空閑頁(yè)塊1個(gè)隊(duì)列。右邊是新的free_area[]，每種大小的空閑頁(yè)塊5個(gè)隊(duì)列。

圖6.6free_area數(shù)組與空閑頁(yè)塊隊(duì)列6.2.2伙伴內(nèi)存初始化

在系統(tǒng)初始化期間，已經(jīng)進(jìn)行了大量的內(nèi)存初始化工作，如檢測(cè)出了物理內(nèi)存的布局結(jié)構(gòu)，確定了系統(tǒng)中的節(jié)點(diǎn)數(shù)及各節(jié)點(diǎn)的管理區(qū)數(shù)，設(shè)置了伙伴內(nèi)存管理器所需的節(jié)點(diǎn)結(jié)構(gòu)、管理區(qū)結(jié)構(gòu)及所有的page結(jié)構(gòu)，并已將所有的空閑頁(yè)塊都轉(zhuǎn)移到了free_area數(shù)組的MOVABLE隊(duì)列中。下面幾件是伙伴內(nèi)存管理器專有的初始化工作。

1.確定管理區(qū)嘗試序列

伙伴內(nèi)存管理器管理著一到多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)中又包含著多個(gè)管理區(qū)。通常情況下，物理內(nèi)存的申請(qǐng)者應(yīng)告訴管理器自己想從哪個(gè)節(jié)點(diǎn)的哪個(gè)管理區(qū)中申請(qǐng)內(nèi)存?；锇閮?nèi)存管理器應(yīng)盡量按照申請(qǐng)者的要求為其分配內(nèi)存。當(dāng)指定的管理區(qū)無法滿足請(qǐng)求時(shí)，伙伴內(nèi)存管理器可以返回失敗信息，也可以嘗試其它的管理區(qū)。如果允許嘗試其它管理區(qū)，則應(yīng)預(yù)先確定一個(gè)管理區(qū)的嘗試順序，或者說管理區(qū)的分配優(yōu)先級(jí)。管理區(qū)排序的基本原則是先“便宜”后“貴重”。DMA區(qū)容量有限且有特定用途，其它區(qū)中的內(nèi)存無法替代，因而最為貴重。NORMAL區(qū)的容量有限，而且內(nèi)核僅能使用NORMAL和DMA區(qū)中的內(nèi)存(只有這兩個(gè)區(qū)中的內(nèi)存有內(nèi)核線性地址)，因而比較貴重。內(nèi)核不直接訪問HIGHMEM區(qū)中的內(nèi)存，該區(qū)對(duì)內(nèi)核的影響不大，最為便宜。一般情況下，節(jié)點(diǎn)間管理區(qū)的嘗試順序應(yīng)該是先本地后外地，節(jié)點(diǎn)內(nèi)管理區(qū)的嘗試順序應(yīng)該是MOVABLE>HIGHMEM>

NORMAL>DMA32>DMA。當(dāng)然，由于節(jié)點(diǎn)性質(zhì)的不同，其管理區(qū)的嘗試順序也可能會(huì)有所變化。結(jié)構(gòu)pglist_data的域node_zonelists中包含一個(gè)數(shù)組_zonerefs，其中記錄著管理區(qū)的嘗試序列。單節(jié)點(diǎn)上的管理區(qū)嘗試序列如圖6.7所示。

如申請(qǐng)者申請(qǐng)DMA內(nèi)存，那么僅能從DMA區(qū)中為其分配，但如果申請(qǐng)者申請(qǐng)高端內(nèi)存，那么可以從HIGHMEM、NORMAL或DMA區(qū)中為其分配。

圖6.7管理區(qū)嘗試序列

2.預(yù)留空閑內(nèi)存

物理內(nèi)存，尤其是低端物理內(nèi)存，是十分緊缺的資源，如果不加控制的話，很容易全部耗盡。一旦物理內(nèi)存被耗盡，很多緊急工作將無法正常開展。當(dāng)物理內(nèi)存回收程序也無法正常運(yùn)行時(shí)，物理內(nèi)存資源將無法被回收，系統(tǒng)有可能不穩(wěn)定甚至崩潰。因而，在任何情況下，都應(yīng)該預(yù)留一部分空閑的物理內(nèi)存以備急需。

需要預(yù)留的空閑物理內(nèi)存量記錄在變量min_free_kbytes中，其大小取決于低端物理內(nèi)存的總量，但不得小于128KB，也不應(yīng)大于64MB。Linux用以下公式計(jì)算預(yù)留的最小物理內(nèi)存量：

min_free_kbytes=sqrt(lowmem_kbytes*16)

其中l(wèi)owmem_kbytes是低端物理內(nèi)存(包括DMA和NORMAL區(qū))總量。預(yù)留的物理內(nèi)存應(yīng)按比例分布在各個(gè)低端管理區(qū)內(nèi)。為安全起見，高端管理區(qū)中也應(yīng)適當(dāng)預(yù)留一部分內(nèi)存。為各管理區(qū)設(shè)定的預(yù)留物理內(nèi)存量會(huì)影響到伙伴內(nèi)存管理器的分配行為。一旦管理區(qū)中的空閑內(nèi)存出現(xiàn)緊張(接近預(yù)留量)跡象，就應(yīng)設(shè)法為其回收物理內(nèi)存。緊張的標(biāo)志是根據(jù)min_free_kbytes算出的基準(zhǔn)線，記錄在zone的watermark數(shù)組中。基準(zhǔn)線包括三條，MIN<LOW<HIGH，其中的MIN就是為管理區(qū)設(shè)定的預(yù)留物理內(nèi)存頁(yè)數(shù)。三條基準(zhǔn)線的大致設(shè)定如下：

(1)低端管理區(qū)的MIN=((min_free_kbytes/4)

×

present_pages)/lowmem_pages。

(2)高端管理區(qū)的MIN=present_pages/1024，需在32和128之間。

(3)

LOW=MIN+MIN/4。

(4)

HIGH=MIN+MIN/2。

其中的present_pages是管理區(qū)中的可用物理內(nèi)存頁(yè)數(shù)，lowmen_pages是可用低端物理內(nèi)存總頁(yè)數(shù)。當(dāng)管理區(qū)中的空閑內(nèi)存量小于LOW時(shí)，表示該區(qū)的內(nèi)存已比較緊張，應(yīng)立刻開始為其回收物理內(nèi)存。在確定預(yù)留頁(yè)數(shù)之后，應(yīng)將預(yù)留的空閑頁(yè)塊從free_area的MOVABLE隊(duì)列遷移到RESERVE隊(duì)列，并將它們的遷移類型改為MIGRATE_RESERVE。由于遷移類型是按頁(yè)組標(biāo)記的，因而應(yīng)以頁(yè)組為單位(1024頁(yè))遷移預(yù)留頁(yè)，遷移的頁(yè)組數(shù)為(MIN+1023)/1024，遷移的內(nèi)存量可能會(huì)超過應(yīng)預(yù)留的物理頁(yè)數(shù)(MIN頁(yè))。

即使為每個(gè)管理區(qū)都預(yù)留了物理內(nèi)存空間，仍然有可能耗盡低端物理內(nèi)存，原因是管理區(qū)的嘗試序列。當(dāng)高端內(nèi)存緊缺時(shí)，伙伴內(nèi)存管理器會(huì)自動(dòng)用低端內(nèi)存代替高端內(nèi)存，其結(jié)果會(huì)導(dǎo)致低端內(nèi)存消耗過快。解決這一問題的方法是讓低優(yōu)先級(jí)的管理區(qū)為高優(yōu)先級(jí)的管理區(qū)也預(yù)留一些內(nèi)存空間，或者說將高優(yōu)先級(jí)管理區(qū)的預(yù)留內(nèi)存拿出一部分放在低優(yōu)先級(jí)管理區(qū)中。在zone結(jié)構(gòu)的lowmem_reserve數(shù)組中記錄著一個(gè)管理區(qū)應(yīng)為其它管理區(qū)預(yù)留的內(nèi)存頁(yè)數(shù)。數(shù)組lowmem_reserve的值是可調(diào)的。

3.確定遷移類型嘗試序列

定義了遷移類型之后，物理內(nèi)存的申請(qǐng)者還需指定所需頁(yè)塊的遷移類型。當(dāng)特定類型的空閑頁(yè)無法滿足請(qǐng)求時(shí)，Linux允許嘗試其它的遷移類型，當(dāng)然需要預(yù)先確定遷移類型的嘗試序列。數(shù)組fallbacks[]中記錄著遷移類型的嘗試序列，如下：

不可遷移型：UNMOVABLE>RECLAIMABLE>MOVABLE>RESERVE。

可回收型：RECLAIMABLE>UNMOVABLE>MOVABLE>RESERVE。

可遷移型：MOVABLE>RECLAIMABLE>UNMOVABLE>RESERVE。

預(yù)留型：RESERVE>RESERVE>RESERVE>RESERVE，即只許分配預(yù)留頁(yè)。

4.建立熱頁(yè)管理隊(duì)列

伙伴內(nèi)存管理器采用伙伴算法管理內(nèi)存頁(yè)塊的分配和釋放。分配時(shí)可能拆分頁(yè)塊，釋放時(shí)會(huì)盡力合并頁(yè)塊。經(jīng)典伙伴算法的問題是過于頻繁的拆分與合并降低了管理器的性能。在新版本的管理區(qū)結(jié)構(gòu)中，為每個(gè)處理器都增加了一個(gè)熱頁(yè)隊(duì)列(或者說熱頁(yè)緩存)，用于暫存各處理器新釋放的單個(gè)物理頁(yè)，試圖通過延遲熱頁(yè)的合并時(shí)機(jī)來提高伙伴內(nèi)存管理器的性能。熱頁(yè)(hotpage)是位于處理器Cache中的頁(yè)，冷頁(yè)(coldpage)是不在處理器Cache中的頁(yè)。處理器對(duì)熱頁(yè)的訪問速度要快于冷頁(yè)。管理區(qū)結(jié)構(gòu)zone中的pageset是熱頁(yè)隊(duì)列，每個(gè)處理器一個(gè)。一個(gè)熱頁(yè)隊(duì)列由一個(gè)per_cpu_pageset結(jié)構(gòu)描述，其定義如下：

structper_cpu_pageset{

structper_cpu_pages pcp;

s8 stat_threshold;

s8 vm_stat_diff[NR_VM_ZONE_STAT_ITEMS];

}_cacheline_aligned_in_smp;

真正的隊(duì)列在結(jié)構(gòu)per_cpu_pages中，其定義如下：

structper_cpu_pages{

int count; //隊(duì)列中的頁(yè)數(shù)

int high; //基準(zhǔn)線

int batch; //批的大小

structlist_head lists[3]; //前三種遷移類型各有一個(gè)熱頁(yè)隊(duì)列

};如果新釋放的單個(gè)空閑頁(yè)(散頁(yè))不是MIGRATE_ISOLATE類型，伙伴內(nèi)存管理器會(huì)先將其加入到熱頁(yè)隊(duì)列(預(yù)留頁(yè)與可遷移頁(yè)共用一個(gè)隊(duì)列)而不是free_area數(shù)組中，因而暫時(shí)不會(huì)被合并。當(dāng)熱頁(yè)數(shù)量(count)超過基準(zhǔn)線high時(shí)，再一次性地將其中batch個(gè)空閑頁(yè)轉(zhuǎn)給free_area(可能被合并)。batch大致是區(qū)中內(nèi)存頁(yè)數(shù)的1/4096，但必須在1到32之間，high的初值是6倍的batch。熱頁(yè)隊(duì)列的平均長(zhǎng)度是4*batch，大約是管理區(qū)大小的千分之一，基本與處理器的L2cache的大小相當(dāng)。伙伴內(nèi)存管理器總是試圖從熱頁(yè)隊(duì)列中分配單個(gè)物理頁(yè)。當(dāng)熱頁(yè)隊(duì)列為空或缺少指定類型的頁(yè)時(shí)，伙伴內(nèi)存管理器會(huì)從free_area中一次性批發(fā)過來batch個(gè)指定類型的頁(yè)。6.2.3物理頁(yè)塊分配

伙伴內(nèi)存管理器采用伙伴算法，以頁(yè)塊(2order頁(yè))為單位從free_area中分配物理內(nèi)存。滿足下列條件的兩個(gè)頁(yè)塊互稱為伙伴：

(1)大小相等，都是2order頁(yè)；

(2)位置相鄰，起始頁(yè)編號(hào)分別是B1、B2，且|B1-B2|=2order；

(3)編號(hào)的第order位相反，B2=B1^(1<<order)，B1=B2^(1<<order)。如圖6.8所示，大小為2頁(yè)(order=1)、起始頁(yè)號(hào)為4的頁(yè)塊(由4、5兩頁(yè)組成)有兩個(gè)相鄰頁(yè)塊，分別是2、3頁(yè)塊和6、7頁(yè)塊，但只有6、7頁(yè)塊是它的伙伴。同樣地，大小為4頁(yè)(order=2)起始頁(yè)號(hào)為12的頁(yè)塊的伙伴是8、9、10、11頁(yè)塊，而不是16、17、18、19頁(yè)塊，也不是16、17頁(yè)塊。

圖6.8伙伴頁(yè)塊一個(gè)大的頁(yè)塊可以被平分成兩個(gè)小伙伴，如4、5、6、7頁(yè)塊可以被平分成兩個(gè)大小為2頁(yè)的伙伴，即4、5和6、7頁(yè)塊。兩個(gè)小伙伴可以被合并成一個(gè)大頁(yè)塊，如伙伴4、5與6、7可合并成頁(yè)塊4、5、6、7，當(dāng)然，4、5、6、7與其伙伴0、1、2、3可進(jìn)一步合并成大小為8頁(yè)的頁(yè)塊。

伙伴算法的分配思路是：根據(jù)請(qǐng)求的大小(2order頁(yè))和遷移類型查free_area[order]中的空閑頁(yè)塊隊(duì)列，找滿足要求的空閑頁(yè)塊。如找到，則將其直接分配給請(qǐng)求者；如找不到，則向上搜索free_area數(shù)組。如在free_area[order+i]中找到滿足要求的空閑頁(yè)塊，則將其平分成伙伴，將其中的一個(gè)掛在free_area[order+i-1]的隊(duì)列中，將另一個(gè)再平分成伙伴。平分過程一直持續(xù)，直到得到大小為2order頁(yè)的兩個(gè)小伙伴。而后將其中的一個(gè)小伙伴掛在free_area[order]的隊(duì)列中，將另一個(gè)分配給請(qǐng)求者。

伙伴內(nèi)存管理器的請(qǐng)求者至少需要提供三類參數(shù)：管理區(qū)編號(hào)、頁(yè)塊大小和對(duì)頁(yè)塊的特殊需求。管理區(qū)編號(hào)給出了一個(gè)請(qǐng)求者建議的管理區(qū)，伙伴管理器將優(yōu)先從該管理區(qū)中分配內(nèi)存。如建議的管理區(qū)無法滿足請(qǐng)求，伙伴管理器將按管理區(qū)嘗試序列搜索優(yōu)先級(jí)更低的管理區(qū)。對(duì)頁(yè)塊的特殊需求很多，如建議的頁(yè)塊遷移類型、是否特別緊急(可動(dòng)用預(yù)留內(nèi)存)、是否允許暫停(在內(nèi)存緊缺時(shí)先回收內(nèi)存)、是否允許I/O操作、是否允許文件操作、是否需要對(duì)頁(yè)塊進(jìn)行特殊處理(如清0)等。

伙伴內(nèi)存管理器按如下流程從管理區(qū)中分配物理內(nèi)存頁(yè)塊：

(1)根據(jù)請(qǐng)求參數(shù)，確定請(qǐng)求者建議的管理區(qū)號(hào)zone_idx和遷移類型號(hào)，進(jìn)而確定一個(gè)管理區(qū)嘗試序列和一個(gè)遷移類型嘗試序列。

(2)按嘗試序列順序搜索各管理區(qū)，找一個(gè)能滿足請(qǐng)求者要求的管理區(qū)。符合下列條件的管理區(qū)能滿足要求：

①系統(tǒng)允許在該管理區(qū)中為請(qǐng)求者分配內(nèi)存。

②在做完此次內(nèi)存分配之后，該管理區(qū)中還有足夠的空閑內(nèi)存。管理區(qū)中的空閑物理內(nèi)存頁(yè)數(shù)減去為其余管理區(qū)預(yù)留的物理內(nèi)存頁(yè)數(shù)(即lowmem_reserve[zone_idx])不應(yīng)少于它的LOW基準(zhǔn)線。

③在做完此次內(nèi)存分配之后，該管理區(qū)中的空閑內(nèi)存塊仍然具有合理的分布，意思是管理區(qū)中尺寸大于或等于2order頁(yè)的空閑內(nèi)存頁(yè)數(shù)不小于LOW/2order頁(yè)。

(3)從找到的管理區(qū)中選擇大小為2order頁(yè)的頁(yè)塊。

①如果order為0(申請(qǐng)1頁(yè))，則從當(dāng)前處理器的熱頁(yè)隊(duì)列中選擇物理頁(yè)。如果熱頁(yè)隊(duì)列中有要求類型的頁(yè)，則選擇其一并將其從隊(duì)列中摘下；如果熱頁(yè)隊(duì)列中沒有要求類型的頁(yè)，則從free_area中一次性申請(qǐng)batch個(gè)該種類型的頁(yè)，將它們插入熱頁(yè)隊(duì)列，并從其中選擇一個(gè)頁(yè)。

②如果order大于0，則直接從free_area[i](i>=order)中選擇頁(yè)塊。如果i>order，需要將所選的大頁(yè)塊拆分成小伙伴。在大頁(yè)塊拆分出來的兩個(gè)小伙伴中，大序號(hào)的伙伴被插入到free_area的隊(duì)列中，被選中的總是序號(hào)最小的伙伴。

③如果整個(gè)管理區(qū)中都沒有與請(qǐng)求者要求類型一致的頁(yè)塊，則從其它類型中遷移1個(gè)盡可能大的頁(yè)塊到要求類型的隊(duì)列中，而后再次選擇頁(yè)塊。這里的“其它類型”由遷移類型嘗試序列決定，但不含RESERVE類型。如果遷移過來的頁(yè)塊足夠大(超過半個(gè)頁(yè)組)，則將整個(gè)頁(yè)組改成要求類型，相當(dāng)于從其它類型中遷移過來一個(gè)頁(yè)組；否則保持頁(yè)組的類型不變，相當(dāng)于在一種類型的頁(yè)組中強(qiáng)行分配一個(gè)其它類型的小頁(yè)塊。

④如果無法從其它類型中遷移頁(yè)塊，則嘗試從RESERVE類型中選擇頁(yè)塊。

(4)設(shè)置頁(yè)塊的管理結(jié)構(gòu)，將其分配給請(qǐng)求者。

①找到所選頁(yè)塊中起始頁(yè)的page結(jié)構(gòu)，將它的private清0，_count置1。

②如果需要，將頁(yè)塊的內(nèi)容全部清0。

③如果所選頁(yè)塊超過1頁(yè)且請(qǐng)求者提出了要求，則將其組織成復(fù)合頁(yè)。復(fù)合頁(yè)(compound)的起始頁(yè)稱為頭頁(yè)，其余頁(yè)稱為尾頁(yè)。在復(fù)合頁(yè)中，所有頁(yè)的first_page都指向起始頁(yè)的page結(jié)構(gòu)，第一個(gè)尾頁(yè)的lru.prev中記錄頁(yè)塊的大小、lru.next中記錄頁(yè)塊的解構(gòu)函數(shù)。

(5)如果分配過程失敗，說明系統(tǒng)中的物理內(nèi)存出現(xiàn)了緊缺現(xiàn)象。

①喚醒在節(jié)點(diǎn)上等待的守護(hù)進(jìn)程kswapd，讓它去回收物理內(nèi)存。這些守護(hù)進(jìn)程在后臺(tái)運(yùn)行。

②放松檢查條件，如僅檢查MIN基準(zhǔn)線或根本不再檢查基準(zhǔn)線，而后再次嘗試分配內(nèi)存。

③如果仍然失敗，則直接回收物理內(nèi)存，并回收當(dāng)前處理器的熱頁(yè)，而后再次嘗試分配內(nèi)存。④如果仍然失敗，說明內(nèi)存真的耗盡了(OutofMemory)，則啟動(dòng)進(jìn)程殺手(killer)嘗試停止一些進(jìn)程來回收物理內(nèi)存，而后再次嘗試分配內(nèi)存。

⑤如果仍然失敗，則顯示信息，通報(bào)內(nèi)存分配失敗。

Linux的伙伴內(nèi)存管理器提供了多個(gè)物理內(nèi)存分配函數(shù)，其中alloc_pages()類的函數(shù)得到的是起始頁(yè)的page結(jié)構(gòu)，而_

_get_free_pages()類的函數(shù)得到的是起始頁(yè)的內(nèi)核線性地址。6.2.4內(nèi)核線性地址分配

頁(yè)塊分配操作所分配的物理內(nèi)存頁(yè)塊可能屬于低端內(nèi)存，也可能屬于高端內(nèi)存。內(nèi)核可能需要訪問這些內(nèi)存頁(yè)塊，也可能不需要訪問它們(僅給用戶進(jìn)程使用)。由于系統(tǒng)未為高端內(nèi)存預(yù)分配內(nèi)核線性地址，因而當(dāng)內(nèi)核需要訪問來自高端的內(nèi)存頁(yè)塊時(shí)，伙伴內(nèi)存管理器必須臨時(shí)為它們分配內(nèi)核線性地址。

Linux在內(nèi)核線性地址空間(3GB～4GB)中為高端內(nèi)存預(yù)留了1024頁(yè)的kmap區(qū)間(起始線性地址是PKMAP_BASE)，專門用于為高端內(nèi)存臨時(shí)指派內(nèi)核線性地址。在系統(tǒng)初始化時(shí)，Linux已為kmap區(qū)間建立了1個(gè)頁(yè)表pkmap_page_table。所謂為一個(gè)內(nèi)存頁(yè)分配臨時(shí)的內(nèi)核線性地址實(shí)際就是在頁(yè)表pkmap_page_table中找一個(gè)空的頁(yè)表項(xiàng)，將其中的頁(yè)基地址(PageBaseAddress)改為內(nèi)存頁(yè)的物理地址。內(nèi)核線性地址的分配以頁(yè)為單位，一次一頁(yè)。由多個(gè)頁(yè)組成的頁(yè)塊可能會(huì)分配到不連續(xù)的內(nèi)核線性地址。為了管理臨時(shí)線性地址的分配，Linux定義了數(shù)組pkmap_count來記錄kmap區(qū)間中各頁(yè)的使用情況，如下：

intpkmap_count[LAST_PKMAP]; //LAST_PKMAP=1024

數(shù)組pkmap_count的某元素為0表示與之對(duì)應(yīng)的內(nèi)核線性地址當(dāng)前是空閑的，可以將其分配給新的內(nèi)存頁(yè)。為內(nèi)存頁(yè)分配內(nèi)核線性地址之后，通過頁(yè)表pkmap_page_table可以方便地將線性地址轉(zhuǎn)換成物理地址，但卻難以將物理地址轉(zhuǎn)換成線性地址。為了方便查找物理頁(yè)的內(nèi)核線性地址，Linux又定義了結(jié)構(gòu)page_address_map來記錄物理頁(yè)與內(nèi)核線性地址的對(duì)應(yīng)關(guān)系，并定義了Hash表page_address_htable，如圖6.9所示。

structpage_address_map{

structpage *page; //內(nèi)存頁(yè)的管理結(jié)構(gòu)

void *virtual; //內(nèi)核線性地址

structlist_head list;

};

structpage_address_map page_address_maps[LAST_PKMAP];

staticstructpage_address_slot{

structlist_head lh; //page_address_map結(jié)構(gòu)隊(duì)列

spinlock_t lock; //隊(duì)列保護(hù)鎖

}_cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];

圖6.9高端內(nèi)存頁(yè)的內(nèi)核線性地址當(dāng)需要為某高端內(nèi)存頁(yè)分配內(nèi)核線性地址時(shí)，Linux首先從數(shù)組pkmap_count中找一個(gè)空閑的頁(yè)表項(xiàng)，得到一個(gè)空閑的內(nèi)核線性地址，而后修改頁(yè)表pkmap_page_table，將其映射到指定的內(nèi)存頁(yè)，同時(shí)填寫一個(gè)page_address_map結(jié)構(gòu)，并將該結(jié)構(gòu)插入到Hash表page_address_htable中。此后，用頁(yè)的物理地址查Hash表page_address_htable即可得到它的內(nèi)核線性地址。在圖6.9中，為內(nèi)存頁(yè)j分配的內(nèi)核線性地址是：PKMAP_BASE+i*PAGE_SIZE。

當(dāng)內(nèi)核不再使用高端頁(yè)時(shí)，應(yīng)該釋放它占用的線性地址，包括清除它的頁(yè)表項(xiàng)、刪除它在Hash表page_address_htable中的page_address_map結(jié)構(gòu)等。

如果在分配過程中發(fā)現(xiàn)已沒有空閑的頁(yè)表項(xiàng)，則請(qǐng)求者必須等待。為了滿足無法等待的請(qǐng)求者的需要，Linux在“FixedVirtualAddress”區(qū)間為每個(gè)處理器預(yù)留了8頁(yè)的內(nèi)核線性地址，用于應(yīng)急。

Linux提供了一組函數(shù)，用于管理高端內(nèi)存頁(yè)的線性地址，其中kmap()為高端內(nèi)存頁(yè)分配內(nèi)核線性地址，kunmap()釋放高端內(nèi)存頁(yè)的內(nèi)核線性地址，kmap_atomic()將一個(gè)高端內(nèi)存頁(yè)映射到“FixedVirtualAddress”區(qū)間的一個(gè)固定位置，kunmap_atomic()清除高端內(nèi)存頁(yè)到“FixedVirtualAddress”的映射。6.2.5物理頁(yè)塊釋放

如果正在使用的物理頁(yè)塊又變成空閑的，那么應(yīng)該將其還給伙伴內(nèi)存管理器，這一過程稱為物理頁(yè)塊的釋放。釋放是分配的逆過程。

一般情況下，被釋放的頁(yè)塊應(yīng)該插入到free_area數(shù)組的某個(gè)空閑頁(yè)塊隊(duì)列中，隊(duì)列位置由頁(yè)塊的大小和遷移類型決定。與分配過程相反，在釋放過程中應(yīng)該盡可能地將小頁(yè)塊合并成大頁(yè)塊。如果被釋放頁(yè)塊的伙伴也是空閑的，就應(yīng)該將它們合并，而后插入到free_area的更高階隊(duì)列中。合并的過程可能是遞歸的，一個(gè)小頁(yè)塊的釋放可能會(huì)引起一連串的合并。頁(yè)塊釋放過程中需要解決的問題主要有兩個(gè)，一是確定伙伴的編號(hào)，二是確定伙伴是否在指定的隊(duì)列中。根據(jù)頁(yè)塊的大小和編號(hào)，可以比較容易地算出其伙伴的編號(hào)。確定伙伴是否在指定隊(duì)列的方法要稍微麻煩一點(diǎn)。在早期的版本中，Linux為free_area的每個(gè)隊(duì)列準(zhǔn)備了一個(gè)位圖，兩個(gè)伙伴合用其中的一位，0表示伙伴不在隊(duì)列中，1表示伙伴在隊(duì)列中。隨著內(nèi)存的增大、隊(duì)列的增多，位圖的開銷變得難以承受，因而在新版本中，Linux取消了隊(duì)列位圖，改用page結(jié)構(gòu)來判斷伙伴的位置。為此Linux做了如下約定：當(dāng)將空閑頁(yè)塊插入free_area時(shí)，要在其起始頁(yè)的flags上設(shè)置PG_buddy標(biāo)志，并在private中記錄頁(yè)塊的大小(即order)。除起始頁(yè)之外，空閑頁(yè)塊的其余頁(yè)上均不能設(shè)置PG_buddy標(biāo)志，其private也應(yīng)被清0。確定伙伴是否在指定隊(duì)列的方法如下：

(1)根據(jù)頁(yè)塊的編號(hào)B1和大小2order，算出其伙伴的編號(hào)B2=B1^(1<<order)。

(2)如果B2在空洞中，那么B1的伙伴不在指定隊(duì)列中。

(3)如果B2和B1不在一個(gè)管理區(qū)中，那么B1的伙伴不在指定隊(duì)列中。

(4)如果B2的flags上有PG_buddy標(biāo)志且其private等于order，則B1的伙伴在指定隊(duì)列中。

假如要釋放頁(yè)塊屬于zone管理區(qū)，其大小是2order頁(yè)，遷移類型是migratetype，那么頁(yè)塊應(yīng)被插入到zone的free_area[order].free_list[migratetype]隊(duì)列中。如果頁(yè)塊的伙伴不在該隊(duì)列中，則應(yīng)先設(shè)置起始頁(yè)上的標(biāo)志，而后再將其直接插入隊(duì)列。如果頁(yè)塊的伙伴在該隊(duì)列中，則應(yīng)將它的伙伴從隊(duì)列中摘下，清除伙伴起始頁(yè)上的標(biāo)志，將它們合并成大小為2order+1頁(yè)的頁(yè)塊，而后再將其插入到free_area[order+1].free_list[migratetype]中。當(dāng)然，此次插入仍需要判斷其伙伴是否在隊(duì)列中，并在可能的情況下進(jìn)行頁(yè)塊合并。如果頁(yè)塊的大小達(dá)到了最大(如210頁(yè))，則不需要再合并。

上述釋放算法的好處是總能得到大的空閑頁(yè)塊，大頁(yè)塊可以滿足未來更多的需要，問題是合并過于積極。過于積極的合并會(huì)導(dǎo)致未來不必要的拆分，帶來額外的系統(tǒng)開銷。新版本的Linux增加了熱頁(yè)隊(duì)列，試圖將合并工作向后推遲。如果要釋放的是單個(gè)物理頁(yè)，直接將其加入到當(dāng)前處理器的熱頁(yè)隊(duì)列的隊(duì)頭即可，不需要將其與伙伴合并。當(dāng)然，合并推遲不是無限制的，如果熱頁(yè)隊(duì)列的長(zhǎng)度超過了預(yù)設(shè)的基準(zhǔn)(high)線，則要一次性地將其中batch個(gè)空閑頁(yè)歸還給free_area。歸還的物理頁(yè)全部位于熱頁(yè)隊(duì)列的隊(duì)尾，基本已屬于冷頁(yè)。緩存而后批量處理是Linux經(jīng)常采用的Lazy策略，基于Lazy策略的分配與釋放算法可有效地減少拆分與合并的次數(shù)，提高伙伴內(nèi)存管理的性能。

Linux的伙伴內(nèi)存管理器提供了多個(gè)物理內(nèi)存釋放函數(shù)，其中free_pages()類函數(shù)的參數(shù)是起始頁(yè)的page結(jié)構(gòu)，而_

_free_pages()類函數(shù)的參數(shù)是起始頁(yè)的內(nèi)核線性地址。

伙伴內(nèi)存管理器十分有效，但它只能分配物理上連續(xù)的內(nèi)存頁(yè)塊。雖然伙伴內(nèi)存管理器會(huì)盡力合并小頁(yè)塊，但隨著系統(tǒng)的運(yùn)行，內(nèi)存頁(yè)塊仍然有碎化的趨勢(shì)。當(dāng)碎化嚴(yán)重時(shí)，伙伴內(nèi)存管理器雖能回收到足夠的空閑內(nèi)存，卻無法將它們合并成大的頁(yè)塊，無法滿足請(qǐng)求者的需求。為解決這一問題，Linux在伙伴內(nèi)存管理器的基礎(chǔ)上又提供了邏輯內(nèi)存管理器，試圖向它的用戶提供僅在邏輯上連續(xù)的大塊內(nèi)存。6.3邏輯內(nèi)存管理事實(shí)上，在啟動(dòng)分頁(yè)機(jī)制之后，不管是操作系統(tǒng)內(nèi)核還是應(yīng)用程序，在訪問內(nèi)存時(shí)使用的都是邏輯或線性地址，因而只要邏輯上連續(xù)就已足夠，并不需要真正的物理連續(xù)。邏輯內(nèi)存管理器就建立在這一事實(shí)之上，它利用內(nèi)核中一塊連續(xù)的線性地址空間為其用戶模擬出邏輯上連續(xù)的大內(nèi)存塊。由多個(gè)邏輯上連續(xù)的內(nèi)存頁(yè)構(gòu)成的頁(yè)塊稱為邏輯頁(yè)塊，邏輯頁(yè)塊的大小不用遵循2的指數(shù)次方的約定，可以由任意多個(gè)頁(yè)構(gòu)成。為實(shí)現(xiàn)邏輯內(nèi)存管理，Linux已在初始化時(shí)專門預(yù)留了128MB的內(nèi)核線性地址空間，其開始地址為VMALLOC_START，終止地址為VMALLOC_END(見圖3.4)。利用這塊內(nèi)核線性地址空間可實(shí)現(xiàn)邏輯頁(yè)塊的分配，其步驟大致如下：

(1)在VMALLOC_START和VMALLOC_END之間找一塊足夠大的線性地址區(qū)間。

(2)向伙伴內(nèi)存管理器申請(qǐng)一組物理頁(yè)，每次1頁(yè)，不要求物理上連續(xù)。

(3)修改第0號(hào)進(jìn)程的頁(yè)目錄、頁(yè)表，建立內(nèi)核線性地址到物理地址的映射。

步驟的后兩步比較容易實(shí)現(xiàn)，困難的是線性地址區(qū)間的分配。雖然可以用伙伴算法管理這塊線性地址空間，但邏輯內(nèi)存管理器選用了更為簡(jiǎn)單的動(dòng)態(tài)分區(qū)法，即根據(jù)請(qǐng)求者的需要?jiǎng)討B(tài)地從預(yù)留的內(nèi)核線性地址空間中劃出小區(qū)間。為了實(shí)現(xiàn)區(qū)間的動(dòng)態(tài)劃分，避免交叉重疊，邏輯內(nèi)存管理器需要知道預(yù)留空間的使用情況，如哪些部分是空閑的、哪些部分已分配出去等。Linux用結(jié)構(gòu)vm_struct描述已分配的線性地址區(qū)間，如下：

structvm_struct{

structvm_struct *next;

void *addr; //區(qū)間開始線性地址

unsignedlong size; //區(qū)間大小

unsignedlong flags; //標(biāo)志

structpage **pages; //組成邏輯內(nèi)存頁(yè)塊的物理內(nèi)存頁(yè)

unsignedint nr_pages; //區(qū)間的頁(yè)數(shù)

unsignedlong phys_addr; //映射的I/O物理地址

};一個(gè)vm_struct結(jié)構(gòu)描述預(yù)留線性地址空間中的一段連續(xù)的區(qū)間，它由若干個(gè)邏輯頁(yè)組成，其中的每個(gè)邏輯頁(yè)又被映射到一個(gè)物理頁(yè)，形成了一個(gè)邏輯上連續(xù)的內(nèi)存頁(yè)塊，即邏輯頁(yè)塊，如圖6.10所示。

系統(tǒng)中所有的vm_struct結(jié)構(gòu)組成一個(gè)單向的有序隊(duì)列，vmlist是隊(duì)頭，如圖6.11所示。隊(duì)列中的vm_struct結(jié)構(gòu)按addr排列，從小到大，邏輯頁(yè)塊間至少有1頁(yè)的隔離帶。

圖6.10結(jié)構(gòu)vm_struct描述的邏輯內(nèi)存塊

圖6.11vmlist隊(duì)列與邏輯頁(yè)塊兩個(gè)相鄰邏輯頁(yè)塊之間的空隙是隔離帶。在早期的實(shí)現(xiàn)中，邏輯內(nèi)存管理器采用最先適應(yīng)算法分配邏輯頁(yè)塊，即順序搜索vmlist隊(duì)列(或者說順序搜索空閑頁(yè)塊隊(duì)列)，從第一個(gè)滿足要求的空閑頁(yè)塊中劃出需要的頁(yè)數(shù)，組成新的邏輯頁(yè)塊并將其分配給請(qǐng)求者。在新版本中，為了加快查找和分配的速度，Linux另外定義了一個(gè)vmap_area結(jié)構(gòu)。與vm_struct一樣，vmap_area描述的也是已分配的線性地址區(qū)間，但與vm_struct不同，系統(tǒng)中的vmap_area結(jié)構(gòu)被組織成一棵紅黑樹。結(jié)構(gòu)vm_struct與vmap_area關(guān)聯(lián)在一起，通過搜索紅黑樹可以快速找到vm_struct結(jié)構(gòu)。從左到右順序搜索紅黑樹，可以找到所有的空閑區(qū)間，從而實(shí)現(xiàn)空閑區(qū)間的分配。

如果找不到足夠大的空閑區(qū)間，則分配失敗。

由于邏輯內(nèi)存管理器要為物理頁(yè)重新指派內(nèi)核線性地址，因而應(yīng)盡可能從高端內(nèi)存中為邏輯頁(yè)塊分配物理頁(yè)。當(dāng)然可以從低端內(nèi)存中分配物理頁(yè)，但從低端內(nèi)存中分配的物理頁(yè)會(huì)有兩個(gè)內(nèi)核線性地址，顯然是一種浪費(fèi)。邏輯內(nèi)存管理器所管理的線性地址空間(VMALLOC_START到VMALLOC_END)還有另外一個(gè)用處，即為板卡上的I/O內(nèi)存分配臨時(shí)的內(nèi)核線性地址，以便在內(nèi)核中能直接訪問它們。

邏輯內(nèi)存管理器所管理的內(nèi)核線性地址空間是有限的、緊缺的，因而在用完之后，應(yīng)該盡快釋放。釋放操作與分配操作相反，它將一個(gè)邏輯頁(yè)塊中的所有物理頁(yè)逐個(gè)還給伙伴內(nèi)存管理器并清除各邏輯頁(yè)在第0號(hào)進(jìn)程中的頁(yè)表項(xiàng)，而后將vm_struct結(jié)構(gòu)從隊(duì)列中摘下并釋放掉。由于邏輯內(nèi)存管理器僅修改第0號(hào)進(jìn)程的頁(yè)表，因而其它進(jìn)程(包括申請(qǐng)者)訪問邏輯頁(yè)塊時(shí)可能會(huì)引起頁(yè)故障異常。頁(yè)故障異常處理程序會(huì)修正這一錯(cuò)誤，見8.4.4。

函數(shù)vmalloc()用于分配邏輯頁(yè)塊，vfree()用于釋放邏輯頁(yè)塊。函數(shù)vmap()用于將一組物理頁(yè)映射到一塊內(nèi)核線性地址區(qū)間，從而將它們組織成一個(gè)邏輯頁(yè)塊；函數(shù)vunmap()用于釋放一個(gè)邏輯頁(yè)塊所占用的內(nèi)核線性地址區(qū)間。函數(shù)ioremap()用于為I/O內(nèi)存分配內(nèi)核線性地址，函數(shù)iounmap()用于釋放I/O內(nèi)存所占用的內(nèi)核線性地址。

伙伴內(nèi)存管理器與邏輯內(nèi)存管理器合作，可以為內(nèi)核提供大內(nèi)存服務(wù)。然而，內(nèi)核在運(yùn)行過程中最經(jīng)常使用的還是小內(nèi)存(小于1頁(yè))，如建立數(shù)據(jù)結(jié)構(gòu)、緩沖區(qū)等。內(nèi)核對(duì)小內(nèi)存的使用極為頻繁且種類繁多，使用它們的時(shí)機(jī)和數(shù)量難以預(yù)估，無法預(yù)先分配，只能動(dòng)態(tài)地創(chuàng)建和撤銷。由于伙伴內(nèi)存管理器與邏輯內(nèi)存管理器的分配粒度都較大，由它們直接提供小內(nèi)存服務(wù)會(huì)造成較大的浪費(fèi)。6.4對(duì)象內(nèi)存管理為了滿足內(nèi)核對(duì)小內(nèi)存的需求，提高物理內(nèi)存的利用率，Linux引入了對(duì)象內(nèi)存管理器。早期的Linux中僅有一種對(duì)象內(nèi)存管理器，稱為Slab。新版本的Linux又引入了其它兩種對(duì)象內(nèi)存管理器，分別稱為Slub和Slob。三種對(duì)象管理器具有相同的接口。

對(duì)象內(nèi)存管理器建立在伙伴內(nèi)存管理器之上，它將來自伙伴內(nèi)存管理器的大塊內(nèi)存劃分成小對(duì)象分配給請(qǐng)求者，并將回收到的小對(duì)象組合成大塊內(nèi)存后還給伙伴內(nèi)存管理器。如果將伙伴內(nèi)存管理器看成批發(fā)商的話，那么對(duì)象內(nèi)存管理器就是零售商，或者說是內(nèi)存對(duì)象的緩存。6.4.1Slab管理器

一個(gè)Slab就是從伙伴內(nèi)存管理器申請(qǐng)到的一個(gè)物理內(nèi)存頁(yè)塊，該頁(yè)塊被劃分成了一組大小相等的小塊，稱為內(nèi)存對(duì)象。每個(gè)對(duì)象都可滿足內(nèi)核的一種特殊需求。具有相同屬性的一到多個(gè)Slab構(gòu)成一個(gè)Cache(緩存)，一個(gè)Cache管理一種類型的內(nèi)存對(duì)象。當(dāng)需要小內(nèi)存時(shí)，內(nèi)核從預(yù)建的Cache中申請(qǐng)內(nèi)存對(duì)象，用完之后再將其還給Cache。當(dāng)一個(gè)Cache中的內(nèi)存對(duì)象被用完后，Slab管理器會(huì)為其追加新的Slab。當(dāng)物理內(nèi)存緊缺時(shí)，伙伴內(nèi)存管理器會(huì)從Cache中回收完全空閑的Slab。由此可見，Slab管理器定義了一個(gè)層次型的管理結(jié)構(gòu)，Slab管理器管理一組Cache，每個(gè)Cache管理一組Slab，每個(gè)Slab管理一組內(nèi)存對(duì)象，如圖6.12所示。

圖6.12Slab管理器的層次結(jié)構(gòu)

Slab管理器對(duì)內(nèi)存對(duì)象的大小基本沒有限制，對(duì)一個(gè)Cache中的Slab數(shù)也基本未作限制。一個(gè)Cache中可以沒有Slab，也可以有多個(gè)Slab。一個(gè)Slab中可能沒有空閑內(nèi)存對(duì)象(已用滿)，可能有空閑內(nèi)存對(duì)象，也可能全是空閑內(nèi)存對(duì)象(空閑)。

1.管理結(jié)構(gòu)

雖然可以讓Cache直接管理內(nèi)存對(duì)象，但以頁(yè)塊(Slab)為單位的內(nèi)存對(duì)象管理更便于空閑頁(yè)塊的回收，因而至少應(yīng)該為Slab管理器定義兩種管理結(jié)構(gòu)，一個(gè)是Cache管理結(jié)構(gòu)，另一個(gè)是Slab管理結(jié)構(gòu)。

Slab結(jié)構(gòu)管理由同一塊物理內(nèi)存劃分出來的內(nèi)存對(duì)象，其定義如下：

structslab{

structlist_head list;

unsignedlong colouroff; //首部著色區(qū)的大小

void *s_mem; //第一個(gè)內(nèi)存對(duì)象的開始地址

unsignedint inuse; //已分配出去的對(duì)象數(shù)

kmem_bufctl_t free; //空閑對(duì)象隊(duì)列的隊(duì)頭

unsignedshort nodeid; //所屬節(jié)點(diǎn)的編號(hào)

};

為了對(duì)內(nèi)存對(duì)象實(shí)施管理，Slab的首要任務(wù)是描述各個(gè)內(nèi)存對(duì)象的使用情況?？梢杂梦粓D標(biāo)識(shí)空閑的內(nèi)存對(duì)象，但比較方便的方法是將一個(gè)Slab中的空閑內(nèi)存對(duì)象組織成一個(gè)隊(duì)列，并在slab結(jié)構(gòu)中記錄隊(duì)列的隊(duì)頭。早期的Linux在每個(gè)內(nèi)存對(duì)象的尾部都加入一個(gè)指針用于將空閑的內(nèi)存對(duì)象串聯(lián)成一個(gè)真正的隊(duì)列，如圖6.13所示。然而這一額外的指針不僅增加了對(duì)象的長(zhǎng)度，而且容易使本來規(guī)整的對(duì)象尺寸變得不規(guī)整，會(huì)造成較大的空間浪費(fèi)。新版本的Linux去掉了內(nèi)存對(duì)象尾部的指針，將它們集中在一個(gè)數(shù)組中，用數(shù)組中的指針模擬內(nèi)存對(duì)象，用數(shù)組內(nèi)部的鏈表模擬內(nèi)存對(duì)象隊(duì)列。進(jìn)一步地，Linux將數(shù)組中的指針換成了對(duì)象序號(hào)，利用序號(hào)將空閑的內(nèi)存對(duì)象串成隊(duì)列。由于不同Slab中的對(duì)象數(shù)有較大的差別，不宜將序號(hào)數(shù)組直接定義在slab結(jié)構(gòu)中。事實(shí)上，序號(hào)數(shù)組是與slab結(jié)構(gòu)一起動(dòng)態(tài)建立的，其大小取決于Slab中的對(duì)象數(shù)，其位置緊接在slab結(jié)構(gòu)之后，如圖6.13所示。域free中記錄的是空閑內(nèi)存對(duì)象隊(duì)列的隊(duì)頭，也就是第一個(gè)空閑內(nèi)存對(duì)象的序號(hào)。

圖6.13Slab管理結(jié)構(gòu)

Slab管理器不限制內(nèi)存對(duì)象的尺寸，但為了提高內(nèi)存訪問的性能，應(yīng)該對(duì)對(duì)象尺寸進(jìn)行適當(dāng)?shù)匾?guī)范，如將對(duì)象尺寸規(guī)約成處理器一級(jí)緩存(L1cache)中緩存行(CacheLine)大小(64或32字節(jié))的倍數(shù)，即讓對(duì)象的開始位置都位于緩存行的邊界處。即使經(jīng)過了規(guī)約，在將頁(yè)塊劃分成內(nèi)存對(duì)象的過程中，通常還是會(huì)剩余一小部分空間(在所有內(nèi)存對(duì)象之外，稱為外部碎片，有別于對(duì)象尾部的內(nèi)部碎片)。剩余的小空間可以集中在頁(yè)塊的首部或尾部，但也可以分散在首尾兩處。通過調(diào)整剩余空間在頁(yè)塊首尾的分布，可以調(diào)整各內(nèi)存對(duì)象的起始位置(偏移量)，從而調(diào)整對(duì)象在高速緩存中的位置，減少一級(jí)緩存沖突，提高內(nèi)存訪問速度。Slab管理器將剩余的小空間稱為著色區(qū)，如圖6.13所示。著色區(qū)被分成色塊，色塊大小是緩存行的長(zhǎng)度。Slab首部的色塊數(shù)記錄在colouroff域中。同一Cache中的不同Slab應(yīng)有不同的colouroff。

結(jié)構(gòu)slab與序號(hào)數(shù)組捆綁在一起，可以位于Slab內(nèi)部(如在頁(yè)塊的首部或尾部)，也可以位于Slab外部(單獨(dú)建立)。Slab管理器會(huì)選用碎片最小的實(shí)現(xiàn)方案。

Cache的管理信息記錄在結(jié)構(gòu)kmem_cache中，其內(nèi)容可大致可分成如下幾部分：

(1)

Cache描述信息。Cache的名稱為name、屬性為flags、活躍狀況為free_touched，所有的Cache結(jié)構(gòu)被其中的next鏈接成雙向循環(huán)鏈表，表頭是cache_chain。

(2)

Slab描述信息，用于新Slab的創(chuàng)建。當(dāng)需要?jiǎng)?chuàng)建新的Slab時(shí)，Slab管理器向伙伴內(nèi)存管理器申請(qǐng)大小為2gfporder頁(yè)、滿足gfpflags要求的頁(yè)塊，該頁(yè)塊被劃分成num個(gè)內(nèi)存對(duì)象，對(duì)象大小(規(guī)約后)為buffer_size字節(jié)，剩余的著色區(qū)由colour個(gè)色塊組成，色塊大小為colour_off字節(jié)，下一個(gè)Slab的首部色塊數(shù)為colour_next。在一個(gè)Slab中，管理結(jié)構(gòu)(包括slab結(jié)構(gòu)和序號(hào)數(shù)組)占用slab_size字節(jié)。如果需將slab結(jié)構(gòu)建立在頁(yè)塊之外，可從專用的Cache中申請(qǐng)管理結(jié)構(gòu)，指針slabp_cache指向該Cache。在分配內(nèi)存對(duì)象之前，可以使用構(gòu)造函數(shù)ctor對(duì)其初始化。

(3)

Slab隊(duì)列nodelists，用于組織同一Cache中的所有slab結(jié)構(gòu)。Slab隊(duì)列由結(jié)構(gòu)kmem_list3定義，每個(gè)內(nèi)存節(jié)點(diǎn)一個(gè)，其中還包含一些統(tǒng)計(jì)信息，如Cache中屬于各內(nèi)存節(jié)點(diǎn)的空閑對(duì)象數(shù)free_objects、在各節(jié)點(diǎn)中最多允許擁有的空閑對(duì)象數(shù)free_limit、下次回收各節(jié)點(diǎn)內(nèi)存對(duì)象的時(shí)間next_reap等。

(4)熱對(duì)象(hotobject)棧管理信息。每個(gè)Cache中都包含一個(gè)熱對(duì)象棧array，用于緩存Cache中的熱對(duì)象。

在早期的版本中，Linux為每個(gè)Cache僅準(zhǔn)備了一個(gè)slab結(jié)構(gòu)隊(duì)列，但做了簡(jiǎn)單的排序，前部是已用滿的Slab，尾部是完全空閑的Slab。為了維護(hù)隊(duì)列的順序，每次對(duì)象分配、釋放后都需要調(diào)整Slab的位置，額外的開銷較大。新版本的Linux在每個(gè)Cache中為每個(gè)內(nèi)存節(jié)點(diǎn)都準(zhǔn)備了三個(gè)slab結(jié)構(gòu)隊(duì)列，分別用于組織部分滿的、完全滿的和完全空閑的slab結(jié)構(gòu)。與“熱頁(yè)隊(duì)列”相似，Slab管理器為每個(gè)處理器建立了一個(gè)“熱對(duì)象”棧，用于記錄該處理器新釋放的、可能還在L1Cache中的內(nèi)存對(duì)象。熱對(duì)象棧由結(jié)構(gòu)array_cache定義，每個(gè)處理器一個(gè)，如下：

structarray_cache{

unsignedint avail; //當(dāng)前可用的熱對(duì)象數(shù)

unsignedint limit; //上限

unsignedint batchcount; //對(duì)象批的大小

unsignedint touched; //最近是否被用過

spinlock_t lock; //保護(hù)鎖，基本可以不用

void *entry[]; //熱對(duì)象棧

};新釋放的內(nèi)存對(duì)象被壓入堆棧entry中緩存，avail是棧頂位置。當(dāng)緩存中的熱對(duì)象數(shù)超過limit時(shí)，再將其中batchcount個(gè)熱對(duì)象還給Slab。Slab管理器總是試圖從熱對(duì)象棧中分配內(nèi)存對(duì)象。當(dāng)熱對(duì)象棧為空時(shí)，Slab管理器會(huì)一次性向其中轉(zhuǎn)移batchcount個(gè)內(nèi)存對(duì)象?？梢哉J(rèn)為，熱對(duì)象棧是Cache中內(nèi)存對(duì)象的一個(gè)緩存。圖6.14是一個(gè)Cache的管理結(jié)構(gòu)。圖6.14Cache管理結(jié)構(gòu)

2.?Cache創(chuàng)建

Linux允許為經(jīng)常使用的每種數(shù)據(jù)結(jié)構(gòu)創(chuàng)建一個(gè)獨(dú)立的Cache。從這類Cache中申請(qǐng)到的內(nèi)存不僅大小恰能滿足建立一個(gè)數(shù)據(jù)結(jié)構(gòu)的需要，而且可認(rèn)為其內(nèi)容已經(jīng)過了適當(dāng)?shù)某跏蓟?。Slab管理器的這一特性可簡(jiǎn)化數(shù)據(jù)結(jié)構(gòu)的管理。

創(chuàng)建一個(gè)Cache其實(shí)就是創(chuàng)建一個(gè)kmem_cache結(jié)構(gòu)，當(dāng)然，創(chuàng)建者需要提供一些參數(shù)，如名稱、對(duì)象尺寸、對(duì)齊方式、構(gòu)造函數(shù)、特殊要求等。Cache的創(chuàng)建過程如下：

(1)從cache_cache中申請(qǐng)一個(gè)對(duì)象，用于建立kmem_cache結(jié)構(gòu)。

(2)根據(jù)創(chuàng)建者的特殊要求和對(duì)齊方式，調(diào)整對(duì)象尺寸。如果對(duì)象尺寸大于512字節(jié)，應(yīng)將管理結(jié)構(gòu)建立在Slab之外，否則應(yīng)將管理結(jié)構(gòu)建立在Slab內(nèi)部。當(dāng)然創(chuàng)建者可以不管對(duì)象的尺寸，強(qiáng)行要求將管理結(jié)構(gòu)建立在Slab之外。

(3)根據(jù)對(duì)象尺寸、對(duì)齊方式、Slab管理結(jié)構(gòu)位置等信息，確定Slab頁(yè)塊的大小，并據(jù)此算出Slab管理結(jié)構(gòu)的大小、一個(gè)頁(yè)塊可劃分出的對(duì)象數(shù)及剩余空間(碎片)的大小等。早期的Linux會(huì)選擇較大的頁(yè)塊以使碎片最小化，新版本的Linux選擇能滿足要求的最小頁(yè)塊，以減少大頁(yè)塊的消耗。

PAGE_SIZE<<gfporder=head+num

×

buffer_size+colour

×

colour_off

其中head是管理結(jié)構(gòu)大小。如果管理結(jié)構(gòu)在Slab外，head=0。

碎片大小不應(yīng)超過頁(yè)塊的1/8。如果碎片大小可容下Slab的管理結(jié)構(gòu)，則應(yīng)將管理結(jié)構(gòu)建在Slab內(nèi)。

(4)如果需要將管理結(jié)構(gòu)建立在Slab之外，還要為其找一個(gè)合適的通用Cache。

(5)根據(jù)對(duì)象大小算出可在Cache中緩存的熱對(duì)象數(shù)(如表6.2所示)，為每個(gè)在線處理器創(chuàng)建一個(gè)熱對(duì)象管理結(jié)構(gòu)，包括結(jié)構(gòu)array_cache和其后的entry數(shù)組。

(6)如果對(duì)象尺寸不超過1頁(yè)，則為Cache建立一個(gè)共享的熱對(duì)象管理結(jié)構(gòu)，用于管理在處理器間共享的熱對(duì)象。共享熱對(duì)象棧的大小是8

×

batchcount。

(7)為每一個(gè)在線的節(jié)點(diǎn)(Node)創(chuàng)建一個(gè)kmem_list3結(jié)構(gòu)，用于組織其上的Slab，其中的域free_limit=(1+節(jié)點(diǎn)中的處理器數(shù))

×

batchcount+num。

(8)將填寫號(hào)的kmem_cache結(jié)構(gòu)插入到鏈表cache_chain中。

表6.2內(nèi)存對(duì)象大小與熱對(duì)象數(shù)的關(guān)系3.?Slab創(chuàng)建

新建的Cache僅有一個(gè)管理結(jié)構(gòu)，其中沒有任何Slab。Cache的Slab是在使用過程中動(dòng)態(tài)創(chuàng)建的。當(dāng)Slab管理器發(fā)現(xiàn)Cache中已沒有空閑的內(nèi)存對(duì)象時(shí)，即為其創(chuàng)建一個(gè)新的Slab。Slab的創(chuàng)建過程如下：

(1)找到當(dāng)前節(jié)點(diǎn)的kmem_list3結(jié)構(gòu)，根據(jù)其中的colour_next折算出新Slab的首部著色區(qū)大小offset，并將colour_next加1(循環(huán)加)。

(2)向伙伴內(nèi)存管理器申請(qǐng)2gfporder頁(yè)連續(xù)的物理內(nèi)存，用于建立Slab。

(3)建立Slab管理結(jié)構(gòu)。

①如果管理結(jié)構(gòu)位于Slab之外，則從slabp_cache中再申請(qǐng)一塊內(nèi)存，用于建立slab結(jié)構(gòu)和序號(hào)數(shù)組。

②如果管理結(jié)構(gòu)位于Slab內(nèi)部，則從所申請(qǐng)頁(yè)塊的首部(加上著色區(qū)offset)劃出slab_size字節(jié)的內(nèi)存，用于建立slab結(jié)構(gòu)和序號(hào)數(shù)組。

(4)在頁(yè)塊的page結(jié)構(gòu)上增加管理信息。Slab頁(yè)塊由2gfporder頁(yè)組成，其中每一頁(yè)都有一個(gè)page結(jié)構(gòu)，對(duì)所有這些page結(jié)構(gòu)做如下設(shè)置，以備后用：

①在flags域中加入PG_Slab標(biāo)志，表示它們正被用做Slab。②讓lru.prev指向slab結(jié)構(gòu)。

③讓lru.next指向kmem_cache結(jié)構(gòu)。

(5)初始化Slab中的內(nèi)存對(duì)象及管理結(jié)構(gòu)，包括：

①如果Cache有構(gòu)造函數(shù)ctor，則用該構(gòu)造函數(shù)初始化每個(gè)內(nèi)存對(duì)象。

②將序號(hào)數(shù)組中的所有元素串成一個(gè)隊(duì)列，表示所有對(duì)象都處于空閑狀態(tài)。序號(hào)數(shù)組的最后一個(gè)元素設(shè)為BUFCTL_END(0xFFFFFFFF)，表示隊(duì)尾。

③設(shè)置slab結(jié)構(gòu)，將free設(shè)為序號(hào)隊(duì)列的隊(duì)頭，將inuse清0，將s_mem設(shè)為第一個(gè)對(duì)象的開始地址，將colouroff設(shè)為第一個(gè)對(duì)象的偏移量。

(6)將結(jié)構(gòu)kmem_list3的free_objects加num，將新建的slab結(jié)構(gòu)插入到它的free隊(duì)列中，表示新增加了num個(gè)空閑內(nèi)存對(duì)象。4.對(duì)象分配

從對(duì)象內(nèi)存管理器申請(qǐng)對(duì)象時(shí)需要指出對(duì)象所屬的Cache和對(duì)對(duì)象的特殊要求，不需要指出對(duì)象的大小，因?yàn)镃ache中的對(duì)象尺寸已經(jīng)預(yù)先確定。

從Cache中分配對(duì)象的工作按從易到難的順序進(jìn)行，大致如下：

(1)如果當(dāng)前處理器的熱對(duì)象棧不空，則棧頂?shù)臒釋?duì)象最有可能駐留在L1Cache中，應(yīng)該將該對(duì)象分配出去。

(2)如果當(dāng)前處理器的熱對(duì)象棧為空，但Cache的共享熱對(duì)象棧不空，則先從共享熱對(duì)象棧中轉(zhuǎn)移一批對(duì)象到熱對(duì)象棧中，而后再將棧頂?shù)膶?duì)象分配出去。

(3)如果Cache的共享對(duì)象棧也為空，則先從Cache的Slab中轉(zhuǎn)移一批對(duì)象到熱對(duì)象棧中，而后再將棧頂?shù)膶?duì)象分配出去。

(4)如果Cache中已沒有空閑對(duì)象，則先為其創(chuàng)建一個(gè)新的Slab，并將其中的一批對(duì)象轉(zhuǎn)移到熱對(duì)象棧中，而后再將棧頂?shù)膶?duì)象分配出去。

批的大小不超過batchcount。從Slab中轉(zhuǎn)移對(duì)象的工作實(shí)際就是從Slab中逐個(gè)分配對(duì)象的工作。分配的順序是先部分空閑的Slab(在partial隊(duì)列中)再完全空閑的Slab(在free隊(duì)列中)。從Slab中分配一個(gè)對(duì)象的過程如下：

(1)確定要分配的對(duì)象。要分配對(duì)象的序號(hào)是free，它的開始地址是：

s_mem+buffer_size

×

free

(2)調(diào)整空閑對(duì)象隊(duì)列。在Slab的序號(hào)數(shù)組中，序號(hào)為free的元素的內(nèi)容是下一個(gè)空閑對(duì)象的序號(hào)，將該序號(hào)存入slab結(jié)構(gòu)的free域中(刪除原隊(duì)頭)。

(3)將slab結(jié)構(gòu)中的inuse加1，表示又分配出去1個(gè)對(duì)象。