《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對象內(nèi)存管理在操作系統(tǒng)營造的虛擬社會中，除了被時鐘管理部分管理的時間之外，另一個重要的基石就是空間。對空間的管理是操作系統(tǒng)的另一項核心工作。

操作系統(tǒng)所管理的空間可大致分為內(nèi)存空間和外存空間，其中內(nèi)存空間可被處理器直接訪問的，是最基礎(chǔ)的空間。內(nèi)存空間是計算機(jī)系統(tǒng)中的重要資源，操作系統(tǒng)中的進(jìn)程運(yùn)行在內(nèi)存空間中，操作系統(tǒng)本身也運(yùn)行在內(nèi)存空間中，離開了內(nèi)存空間，計算機(jī)系統(tǒng)將無法運(yùn)行。另一方面，內(nèi)存空間又是計算機(jī)系統(tǒng)中的緊缺資源，操作系統(tǒng)及其管理的所有進(jìn)程共享同一塊物理內(nèi)存空間，其容量似乎永遠(yuǎn)都無法滿足進(jìn)程對它的需求。因而有必要對內(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)長期的發(fā)展過程中，內(nèi)存管理部分由簡到繁，不斷演變，正逐步走向成熟。

為解決復(fù)雜的內(nèi)存管理問題，Linux采用了分而治之的設(shè)計方法，將內(nèi)存管理工作交給幾個既相互獨(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)存)。如果按申請的規(guī)模劃分，內(nèi)核對物理內(nèi)存的需求大致可分為中規(guī)模(幾個物理上連續(xù)的頁)、小規(guī)模(若干字節(jié))和大規(guī)模(多個邏輯上連續(xù)的頁)等幾類。為了滿足內(nèi)核對物理內(nèi)存的不同需求，Linux將物理內(nèi)存管理子系統(tǒng)進(jìn)一步劃分成三個管理器，即伙伴內(nèi)存管理器、對象內(nèi)存管理器和邏輯內(nèi)存管理器?；锇閮?nèi)存管理器是物理內(nèi)存的真正管理者，是物理內(nèi)存管理的基礎(chǔ)?；锇閮?nèi)存管理器以頁塊(若干個連續(xù)的物理頁)為單位分配、釋放、回收物理內(nèi)存，雖比較粗放，但極為快速、高效，且不會產(chǎn)生外部碎片。

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

在系統(tǒng)初始化期間，Linux還提供了一個初始內(nèi)存管理器Bootmem，用于向內(nèi)核提供物理內(nèi)存服務(wù)。但在伙伴內(nèi)存管理器啟動之后，Bootmem已讓出管理權(quán)，被停止了工作。除內(nèi)核之外，內(nèi)存管理的主要服務(wù)對象是進(jìn)程。與內(nèi)核不同，每個進(jìn)程都需要一塊容量足夠大的獨(dú)立的虛擬內(nèi)存，用于暫存它的程序、數(shù)據(jù)、堆棧等。因而內(nèi)存管理的另一個核心工作是利用有限的物理內(nèi)存和外存設(shè)備為系統(tǒng)中的每個進(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)存(在堆中)的動態(tài)分配、釋放與回收(如庫函數(shù)malloc()、free()等)。用戶內(nèi)存管理器一般在函數(shù)庫(如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ī)系統(tǒng)中實(shí)際配置的內(nèi)存。根據(jù)處理器與物理內(nèi)存的組織關(guān)系可將計算機(jī)系統(tǒng)分成兩大類。在UMA(UniformMemoryAccess)系統(tǒng)中，每個處理器都可以訪問到所有的物理內(nèi)存，且訪問速度都相同。在NUMA(Non-UniformMemoryAccess)系統(tǒng)中，處理器雖可訪問到所有的物理內(nèi)存，但訪問速度略有差異。6.2伙伴內(nèi)存管理事實(shí)上，一個NUMA系統(tǒng)由多個節(jié)點(diǎn)組成，每個節(jié)點(diǎn)都有自己的處理器和物理內(nèi)存，處理器對節(jié)點(diǎn)內(nèi)部內(nèi)存的訪問速度較快，對其它節(jié)點(diǎn)的內(nèi)存訪問速度較慢。UMA是NUMA的特例，只有一個節(jié)點(diǎn)的NUMA就是UMA。

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

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

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

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

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

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

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

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

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

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

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

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

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

}pg_data_t;

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

structpglist_data*node_data[MAX_NUMNODES]_read_mostly;

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

即使屬于同一個節(jié)點(diǎn)，物理頁的特性也可能不同，如有些物理頁有永久性的內(nèi)核線性地址而另一些物理頁沒有，有些物理頁可用作ISADMA而另一些物理頁不能等。不同特性的物理頁有著不同的用處，應(yīng)采用不同的管理方法，或者說應(yīng)區(qū)別對待一個節(jié)點(diǎn)內(nèi)部的物理內(nèi)存?；锇閮?nèi)存管理器將一個節(jié)點(diǎn)內(nèi)部的物理內(nèi)存進(jìn)一步劃分成管理區(qū)。每個節(jié)點(diǎn)都可以定義2到4個管理區(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)存來自其它幾個區(qū)，都是可動態(tài)遷移的物理頁，用于內(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)容包括如下幾個：

(1)開始頁號zone_start_pfn表示管理區(qū)的開始位置。

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

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

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

structfree_area{

tructlist_head free_list[MIGRATE_TYPES]; //

5個空閑頁塊隊列

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

};

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

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

在系統(tǒng)初始化期間，已經(jīng)進(jìn)行了大量的內(nèi)存初始化工作，如檢測出了物理內(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)，并已將所有的空閑頁塊都轉(zhuǎn)移到了free_area數(shù)組的MOVABLE隊列中。下面幾件是伙伴內(nèi)存管理器專有的初始化工作。

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

伙伴內(nèi)存管理器管理著一到多個節(jié)點(diǎn)，每個節(jié)點(diǎn)中又包含著多個管理區(qū)。通常情況下，物理內(nèi)存的申請者應(yīng)告訴管理器自己想從哪個節(jié)點(diǎn)的哪個管理區(qū)中申請內(nèi)存?；锇閮?nèi)存管理器應(yīng)盡量按照申請者的要求為其分配內(nèi)存。當(dāng)指定的管理區(qū)無法滿足請求時，伙伴內(nèi)存管理器可以返回失敗信息，也可以嘗試其它的管理區(qū)。如果允許嘗試其它管理區(qū)，則應(yīng)預(yù)先確定一個管理區(qū)的嘗試順序，或者說管理區(qū)的分配優(yōu)先級。管理區(qū)排序的基本原則是先“便宜”后“貴重”。DMA區(qū)容量有限且有特定用途，其它區(qū)中的內(nèi)存無法替代，因而最為貴重。NORMAL區(qū)的容量有限，而且內(nèi)核僅能使用NORMAL和DMA區(qū)中的內(nèi)存(只有這兩個區(qū)中的內(nèi)存有內(nèi)核線性地址)，因而比較貴重。內(nèi)核不直接訪問HIGHMEM區(qū)中的內(nèi)存，該區(qū)對內(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ū)的嘗試順序也可能會有所變化。結(jié)構(gòu)pglist_data的域node_zonelists中包含一個數(shù)組_zonerefs，其中記錄著管理區(qū)的嘗試序列。單節(jié)點(diǎn)上的管理區(qū)嘗試序列如圖6.7所示。

如申請者申請DMA內(nèi)存，那么僅能從DMA區(qū)中為其分配，但如果申請者申請高端內(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)行時，物理內(nèi)存資源將無法被回收，系統(tǒng)有可能不穩(wěn)定甚至崩潰。因而，在任何情況下，都應(yīng)該預(yù)留一部分空閑的物理內(nèi)存以備急需。

需要預(yù)留的空閑物理內(nèi)存量記錄在變量min_free_kbytes中，其大小取決于低端物理內(nèi)存的總量，但不得小于128KB，也不應(yīng)大于64MB。Linux用以下公式計算預(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)按比例分布在各個低端管理區(qū)內(nèi)。為安全起見，高端管理區(qū)中也應(yīng)適當(dāng)預(yù)留一部分內(nèi)存。為各管理區(qū)設(shè)定的預(yù)留物理內(nèi)存量會影響到伙伴內(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)存頁數(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)存頁數(shù)，lowmen_pages是可用低端物理內(nèi)存總頁數(shù)。當(dāng)管理區(qū)中的空閑內(nèi)存量小于LOW時，表示該區(qū)的內(nèi)存已比較緊張，應(yīng)立刻開始為其回收物理內(nèi)存。在確定預(yù)留頁數(shù)之后，應(yīng)將預(yù)留的空閑頁塊從free_area的MOVABLE隊列遷移到RESERVE隊列，并將它們的遷移類型改為MIGRATE_RESERVE。由于遷移類型是按頁組標(biāo)記的，因而應(yīng)以頁組為單位(1024頁)遷移預(yù)留頁，遷移的頁組數(shù)為(MIN+1023)/1024，遷移的內(nèi)存量可能會超過應(yīng)預(yù)留的物理頁數(shù)(MIN頁)。

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

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

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

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

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

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

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

4.建立熱頁管理隊列

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

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

structper_cpu_pages{

int count; //隊列中的頁數(shù)

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

int batch; //批的大小

structlist_head lists[3]; //前三種遷移類型各有一個熱頁隊列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

intpkmap_count[LAST_PKMAP]; //LAST_PKMAP=1024

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

structpage_address_map{

structpage *page; //內(nèi)存頁的管理結(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)隊列

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

}_cacheline_aligned_in_smp page_address_htable[1<<PA_HASH_ORDER];

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟的后兩步比較容易實(shí)現(xiàn)，困難的是線性地址區(qū)間的分配。雖然可以用伙伴算法管理這塊線性地址空間，但邏輯內(nèi)存管理器選用了更為簡單的動態(tài)分區(qū)法，即根據(jù)請求者的需要動態(tài)地從預(yù)留的內(nèi)核線性地址空間中劃出小區(qū)間。為了實(shí)現(xiàn)區(qū)間的動態(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)存頁塊的物理內(nèi)存頁

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

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

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

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

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

圖6.11vmlist隊列與邏輯頁塊兩個相鄰邏輯頁塊之間的空隙是隔離帶。在早期的實(shí)現(xiàn)中，邏輯內(nèi)存管理器采用最先適應(yīng)算法分配邏輯頁塊，即順序搜索vmlist隊列(或者說順序搜索空閑頁塊隊列)，從第一個滿足要求的空閑頁塊中劃出需要的頁數(shù)，組成新的邏輯頁塊并將其分配給請求者。在新版本中，為了加快查找和分配的速度，Linux另外定義了一個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)存管理器要為物理頁重新指派內(nèi)核線性地址，因而應(yīng)盡可能從高端內(nèi)存中為邏輯頁塊分配物理頁。當(dāng)然可以從低端內(nèi)存中分配物理頁，但從低端內(nèi)存中分配的物理頁會有兩個內(nèi)核線性地址，顯然是一種浪費(fèi)。邏輯內(nèi)存管理器所管理的線性地址空間(VMALLOC_START到VMALLOC_END)還有另外一個用處，即為板卡上的I/O內(nèi)存分配臨時的內(nèi)核線性地址，以便在內(nèi)核中能直接訪問它們。

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

函數(shù)vmalloc()用于分配邏輯頁塊，vfree()用于釋放邏輯頁塊。函數(shù)vmap()用于將一組物理頁映射到一塊內(nèi)核線性地址區(qū)間，從而將它們組織成一個邏輯頁塊；函數(shù)vunmap()用于釋放一個邏輯頁塊所占用的內(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頁)，如建立數(shù)據(jù)結(jié)構(gòu)、緩沖區(qū)等。內(nèi)核對小內(nèi)存的使用極為頻繁且種類繁多，使用它們的時機(jī)和數(shù)量難以預(yù)估，無法預(yù)先分配，只能動態(tài)地創(chuàng)建和撤銷。由于伙伴內(nèi)存管理器與邏輯內(nèi)存管理器的分配粒度都較大，由它們直接提供小內(nèi)存服務(wù)會造成較大的浪費(fèi)。6.4對象內(nèi)存管理為了滿足內(nèi)核對小內(nèi)存的需求，提高物理內(nèi)存的利用率，Linux引入了對象內(nèi)存管理器。早期的Linux中僅有一種對象內(nèi)存管理器，稱為Slab。新版本的Linux又引入了其它兩種對象內(nèi)存管理器，分別稱為Slub和Slob。三種對象管理器具有相同的接口。

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

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

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

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

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

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

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

structslab{

structlist_head list;

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

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

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

kmem_bufctl_t free; //空閑對象隊列的隊頭

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

};

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

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

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

結(jié)構(gòu)slab與序號數(shù)組捆綁在一起，可以位于Slab內(nèi)部(如在頁塊的首部或尾部)，也可以位于Slab外部(單獨(dú)建立)。Slab管理器會選用碎片最小的實(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)需要創(chuàng)建新的Slab時，Slab管理器向伙伴內(nèi)存管理器申請大小為2gfporder頁、滿足gfpflags要求的頁塊，該頁塊被劃分成num個內(nèi)存對象，對象大小(規(guī)約后)為buffer_size字節(jié)，剩余的著色區(qū)由colour個色塊組成，色塊大小為colour_off字節(jié)，下一個Slab的首部色塊數(shù)為colour_next。在一個Slab中，管理結(jié)構(gòu)(包括slab結(jié)構(gòu)和序號數(shù)組)占用slab_size字節(jié)。如果需將slab結(jié)構(gòu)建立在頁塊之外，可從專用的Cache中申請管理結(jié)構(gòu)，指針slabp_cache指向該Cache。在分配內(nèi)存對象之前，可以使用構(gòu)造函數(shù)ctor對其初始化。

(3)

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

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

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

structarray_cache{

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

unsignedint limit; //上限

unsignedint batchcount; //對象批的大小

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

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

void *entry[]; //熱對象棧

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

2.?Cache創(chuàng)建

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

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

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

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

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

PAGE_SIZE<<gfporder=head+num

×

buffer_size+colour

×

colour_off

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

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

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

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

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

×

batchcount。

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

×

batchcount+num。

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

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

新建的Cache僅有一個管理結(jié)構(gòu)，其中沒有任何Slab。Cache的Slab是在使用過程中動態(tài)創(chuàng)建的。當(dāng)Slab管理器發(fā)現(xiàn)Cache中已沒有空閑的內(nèi)存對象時，即為其創(chuàng)建一個新的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)存管理器申請2gfporder頁連續(xù)的物理內(nèi)存，用于建立Slab。

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

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

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

(4)在頁塊的page結(jié)構(gòu)上增加管理信息。Slab頁塊由2gfporder頁組成，其中每一頁都有一個page結(jié)構(gòu)，對所有這些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)存對象及管理結(jié)構(gòu)，包括：

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

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

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

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

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

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

(1)如果當(dāng)前處理器的熱對象棧不空，則棧頂?shù)臒釋ο笞钣锌赡荞v留在L1Cache中，應(yīng)該將該對象分配出去。

(2)如果當(dāng)前處理器的熱對象棧為空，但Cache的共享熱對象棧不空，則先從共享熱對象棧中轉(zhuǎn)移一批對象到熱對象棧中，而后再將棧頂?shù)膶ο蠓峙涑鋈ァ?/p>

(3)如果Cache的共享對象棧也為空，則先從Cache的Slab中轉(zhuǎn)移一批對象到熱對象棧中，而后再將棧頂?shù)膶ο蠓峙涑鋈ァ?/p>

(4)如果Cache中已沒有空閑對象，則先為其創(chuàng)建一個新的Slab，并將其中的一批對象轉(zhuǎn)移到熱對象棧中，而后再將棧頂?shù)膶ο蠓峙涑鋈ァ?/p>

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

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

s_mem+buffer_size

×

free

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

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