每天十五分鐘，熟讀一個技術點，水滴石穿，一切隻為渴望更優秀的你！
————零聲學院
6.3 記憶體的配置設定和回收
在記憶體初始化完成以後，記憶體中就常駐有核心映像(核心代碼和資料)。以後，随着用
戶程式的執行和結束，就需要不斷地配置設定和釋放實體頁面。核心應該為配置設定一組連續的頁面
而建立一種穩定、高效的配置設定政策。為此，必須解決一個比較重要的記憶體管理問題，即外碎
片問題。頻繁地請求和釋放不同大小的一組連續頁面，必然導緻在已配置設定的記憶體塊中分散許
多小塊的空閑頁面。由此帶來的問題是，即使這些小塊的空閑頁面加起來足以滿足所請求的
頁面，但是要配置設定一個大塊的連續頁面可能就根本無法滿足。Linux 采用著名的夥伴(Buddy)
系統算法來解決外碎片問題。
但是請注意，在 Linux 中，CPU 不能按實體位址來通路存儲空間，而必須使用虛拟位址；
是以，對于記憶體頁面的管理，通常是先在虛存空間中配置設定一個虛存區間，然後才根據需要為
此區間配置設定相應的實體頁面并建立起映射，也就是說，虛存區間的配置設定在前，而實體頁面的
配置設定在後，但是為了承接上一節的内容，我們先介紹記憶體的配置設定和回收，然後再介紹使用者進
程虛存區間的建立。
6.3.1 夥伴算法
1．原理
Linux 的夥伴算法把所有的空閑頁面分為 10 個塊組，每組中塊的大小是 2 的幂次方個頁
面，例如，第 0 組中塊的大小都為 20 (1 個頁面)，第 1 組中塊的大小都為 21 (2 個頁面)，
第 9 組中塊的大小都為 29 (512 個頁面)。也就是說，每一組中塊的大小是相同的，且這同樣
大小的塊形成一個連結清單。
我們通過一個簡單的例子來說明該算法的工作原理。
假設要求配置設定的塊的大小為 128 個頁面(由多個頁面組成的塊我們就叫做頁面塊)。該
算法先在塊大小為 128 個頁面的連結清單中查找，看是否有這樣一個空閑塊。如果有，就直接分
配；如果沒有，該算法會查找下一個更大的塊，具體地說，就是在塊大小 256 個頁面的連結清單
中查找一個空閑塊。如果存在這樣的空閑塊，核心就把這 256 個頁面分為兩等份，一份配置設定
出去，另一份插入到塊大小為 128 個頁面的連結清單中。如果在塊大小為 256 個頁面的連結清單中也
沒有找到空閑頁塊，就繼續找更大的塊，即 512 個頁面的塊。如果存在這樣的塊，核心就從
512 個頁面的塊中分出 128 個頁面滿足請求，然後從 384 個頁面中取出 256 個頁面插入到塊
大小為 256 個頁面的連結清單中。然後把剩餘的 128 個頁面插入到塊大小為 128 個頁面的連結清單中。
如果 512 個頁面的連結清單中還沒有空閑塊，該算法就放棄配置設定，并發出出錯信号。
以上過程的逆過程就是塊的釋放過程，這也是該算法名字的來由。滿足以下條件的兩個
塊稱為夥伴：
(1)兩個塊的大小相同；
(2)兩個塊的實體位址連續。
夥伴算法把滿足以上條件的兩個塊合并為一個塊，該算法是疊代算法，如果合并後的塊
還可以跟相鄰的塊進行合并，那麼該算法就繼續合并。
2．資料結構
在 6.2.6 節中所介紹的管理區資料結構 struct zone_struct 中，涉及到空閑區資料結
構：
free_area_t free_area[MAX_ORDER];
我們再次對 free_area_t 給予較詳細的描述。
#difine MAX_ORDER 10 type struct free_area_struct { struct list_head free_list unsigned int *map } free_area_t
其中 list_head 域是一個通用的雙向連結清單結構，連結清單中元素的類型将為 mem_map_t(即
struct page 結構)。Map 域指向一個位圖，其大小取決于現有的頁面數。free_area 第 k 項
位圖的每一位，描述的就是大小為 2k 個頁面的兩個夥伴塊的狀态。如果位圖的某位為 0，表
示一對兄弟塊中或者兩個都空閑，或者兩個都被配置設定，如果為 1，肯定有一塊已被配置設定。當
兄弟塊都空閑時，核心把它們當作一個大小為 2k+1的單獨快來處理。如圖 6.9 給出該資料結
構的示意圖。
圖 6.9 中，free_aea 數組的元素 0 包含了一個空閑頁(頁面編号為 0)；而元素 2 則包
含了兩個以 4 個頁面為大小的空閑頁面塊，第一個頁面塊的起始編号為 4，而第二個頁面塊
的起始編号為 56。
我們曾提到，當需要配置設定若幹個記憶體頁面時，用于 DMA 的記憶體頁面必須是連續的。其實
為了便于管理，從夥伴算法可以看出，隻要請求配置設定的塊大小不超過 512 個頁面(2KB)，内
核就盡量配置設定連續的頁面。
6.3.2 實體頁面的配置設定和釋放
當一個程序請求配置設定連續的實體頁面時，可以通過調用 alloc_pages()來完成。Linux 2.4
版本中有兩個 alloc_pages()，一個在 mm/numa.c 中，另一個在 mm/page_alloc,c 中，編譯
時根據所定義的條件選項 CONFIG_DISCONTIGMEM 來進行取舍。
1．非一緻存儲結構(NUMA)中頁面的配置設定
CONFIG_DISCONTIGMEM 條件編譯的含義是“不連續的存儲空間”，Linux 把不連續的存儲
空間也歸類為非一緻存儲結構(NUMA)。這是因為，不連續的存儲空間本質上是一種廣義的
NUMA，因為那說明在最低實體位址和最高實體位址之間存在着空洞，而有空洞的空間當然是
“不一緻”的。是以，在位址不連續的實體空間也要像結構不一樣的實體空間那樣劃分出若幹
連續且均勻的“節點”。是以，在存儲結構不連續的系統中，每個子產品都有若幹個節點，因而
都有個 pg_data_t 資料結構隊列。我們先來看 mm/numa.c 中的 alloc_page()函數：
/* * This can be refined. Currently, tries to do round robin, instead * should do concentratic circle search, starting from current node. */struct page * _alloc_pages(unsigned int gfp_mask, unsigned int order){ struct page *ret = 0; pg_data_t *start, *temp;#ifndef CONFIG_NUMA unsigned long flags; static pg_data_t *next = 0;#endif if (order >= MAX_ORDER) return NULL;#ifdef CONFIG_NUMA temp = NODE_DATA(numa_node_id());#else spin_lock_irqsave(&node_lock, flags); if (!next) next = pgdat_list; temp = next; next = next->node_next; spin_unlock_irqrestore(&node_lock, flags);#endif start = temp; while (temp) { if ((ret = alloc_pages_pgdat(temp, gfp_mask, order))) return(ret); temp = temp->node_next; } temp = pgdat_list; while (temp != start) { if ((ret = alloc_pages_pgdat(temp, gfp_mask, order))) return(ret); temp = temp->node_next; } return(0); }
對該函數的說明如下。
該函數有兩個參數。gfp_mask 表示采用哪種配置設定政策。參數 order 表示所需實體塊的大
小，可以是 1、2、3 直到 2MAX_ORDER-1。
如果定義了 CONFIG_NUMA，也就是在 NUMA 結構的系統中，可以通過 NUMA_DATA()宏找
到 CPU 所在節點的 pg_data_t 資料結構隊列，并存放在臨時變量 temp 中。
如果在不連續的 UMA 結構中，則有個 pg_data_t 資料結構的隊列 pgdat_list，pgdat_list
就是該隊列的首部。因為隊列一般都是臨界資源，是以，在對該隊列進行兩個以上的操作時
要加鎖。
配置設定時輪流從各個節點開始，以求各節點負荷的平衡。函數中有兩個循環，其形式基本
相同，也就是，對節點隊列基本進行兩遍掃描，直至在某個節點内配置設定成功，則跳出循環，
否則，則徹底失敗，進而傳回 0。對于每個節點，調用 alloc_pages_pgdat()函數試圖配置設定
所需的頁面。
2．一緻存儲結構(UMA)中頁面的配置設定
連續空間 UMA 結構的 alloc_page()是在 include/linux/mm.h 中定義的：
#ifndef CONFIG_DISCONTIGMEM static inline struct page * alloc_pages(unsigned int gfp_mask, unsigned int order){ /* * Gets optimized away by the compiler. */ if (order >= MAX_ORDER) return NULL; return __alloc_pages(gfp_mask, order, contig_page_data.node_zonelists+(gfp_mask & GFP_ZONEMASK)); } #endif
從這個函數的定義可以看出， alloc_page()是 _alloc_pages()的封裝函數，而
_alloc_pages()才是夥伴算法的核心。這個函數定義于 mm/page_alloc.c 中，我們先對此
函數給予概要描述。
_alloc_pages()在管理區連結清單 zonelist 中依次查找每個區，從中找到滿足要求的區，
然後用夥伴算法從這個區中配置設定給定大小(2 order個)的頁面塊。如果所有的區都沒有足夠的
空閑頁面，則調用 swapper 或 bdflush 核心線程，把髒頁寫到磁盤以釋放一些頁面。
在__alloc_pages()和虛拟記憶體(簡稱 VM)的代碼之間有一些複雜的接口(後面會詳細
描述)。每個區都要對剛剛被映射到某個程序 VM 的頁面進行跟蹤，被映射的頁面也許僅僅做
了标記，而并沒有真正地配置設定出去。因為根據虛拟存儲的配置設定原理，對實體頁面的配置設定要盡
量推遲到不能再推遲為止，也就是說，當程序的代碼或資料必須裝入到記憶體時，才給它真正
配置設定實體頁面。
搞清楚頁面配置設定的基本原則後，我們對其代碼具體分析如下：
/* * This is the 'heart' of the zoned buddy allocator: */struct page * __alloc_pages(unsigned int gfp_mask, unsigned int order, zonelist_t *zonelist){ unsigned long min; zone_t **zone, * classzone; struct page * page;int freed; zone = zonelist->zones; classzone = *zone; min = 1UL << order; for (;;) { zone_t *z = *(zone++); if (!z) break; min += z->pages_low; if (z->free_pages > min) { page = rmqueue(z, order); if (page) return page; } }
這是對一個配置設定政策中所規定的所有頁面管理區的循環。循環中依次考察各個區中空閑
頁面的總量，如果總量尚大于“最低水位線”與所請求頁面數之和，就調用 rmqueue()試
圖從該區中進行配置設定。如果配置設定成功，則傳回一個 page 結構指針，指向頁面塊中第一個頁面
的起始位址。
classzone->need_balance = 1; mb(); if (waitqueue_active(&kswapd_wait)) wake_up_interruptible(&kswapd_wait);
如果發現管理區中的空閑頁面總量已經降到最低點，則把 zone_t 結構中需要重新平衡
的标志(need_balance)置 1，而且如果核心線程 kswapd 在一個等待隊列中睡眠，就喚醒它，
讓它收回一些頁面以備使用(可以看出，need_balance 是和 kswapd 配合使用的)。
zone = zonelist->zones; min = 1UL << order; for (;;) { unsigned long local_min; zone_t *z = *(zone++); if (!z) break; local_min = z->pages_min; if (!(gfp_mask & __GFP_WAIT)) local_min >>= 2; min += local_min; if (z->free_pages > min) { page = rmqueue(z, order); if (page) return page; } }
如果給定配置設定政策中所有的頁面管理區都配置設定失敗，那隻好把原來的“最低水位”再向
下調(除以 4)，然後看是否滿足要求(z->free_pages > min)，如果能滿足要求，則調用 rmqueue
()進行配置設定。
/* here we're in the low on memory slow path */rebalance: if (current->flags & (PF_MEMALLOC | PF_MEMDIE)) { zone = zonelist->zones; for (;;) { zone_t *z = *(zone++); if (!z) break; page = rmqueue(z, order); if (page) return page; } return NULL; }
如果配置設定還不成功，這時候就要看是哪類程序在請求配置設定記憶體頁面。其中 PF_MEMALLOC
和 PF_MEMDIE 是程序的 task_struct 結構中 flags 域的值，對于正在配置設定頁面的程序(如
kswapd 核心線程)，則其 PF_MEMALLOC 的值為 1(一般程序的這個标志為 0)，而對于使記憶體
溢出而被殺死的程序，則其 PF_MEMDIE 為 1。不管哪種情況，都說明必須給該程序配置設定頁面
(想想為什麼)。是以，繼續進行配置設定。
/* Atomic allocations - we can't balance anything */ if (!(gfp_mask & __GFP_WAIT)) return NULL;
如果請求配置設定頁面的程序不能等待，也不能被重新排程，隻好在沒有配置設定到頁面的情況
下“空手”傳回。
page = balance_classzone(classzone, gfp_mask, order, &freed); if (page) return page;
如果經過幾番努力，必須得到頁面的程序(如 kswapd)還沒有配置設定到頁面，就要調用
balance_classzone()函數把目前程序所占有的局部頁面釋放出來。如果釋放成功，則傳回
一個 page 結構指針，指向頁面塊中第一個頁面的起始位址。
zone = zonelist->zones; min = 1UL << order; for (;;) { zone_t *z = *(zone++); if (!z) break; min += z->pages_min; if (z->free_pages > min) { page = rmqueue(z, order); if (page) return page; } }
繼續進行配置設定。
/* Don't let big-order allocations loop * if (order > 3) return NULL; /* Yield for kswapd, and try again */ current->policy |= SCHED_YIELD; __set_current_state(TASK_RUNNING); schedule(); goto rebalance; }
在這個函數中，頻繁調用了 rmqueue()函數，下面我們具體來看一下這個函數内容。
(1)rmqueue()函數
該函數試圖從一個頁面管理區配置設定若幹連續的記憶體頁面。這是最基本的配置設定操作，其具
體代碼如下：
static struct page * rmqueue(zone_t *zone, unsigned int order){free_area_t * area = zone->free_area + order;unsigned int curr_order = order;struct list_head *head, *curr;unsigned long flags;struct page *page;spin_lock_irqsave(&zone->lock, flags);do {head = &area->free_list;curr = memlist_next(head);if (curr != head) {unsigned int index;page = memlist_entry(curr, struct page, list);if (BAD_RANGE(zone,page))BUG();memlist_del(curr);index = page - zone->zone_mem_map;if (curr_order != MAX_ORDER-1)MARK_USED(index, curr_order, area);zone->free_pages -= 1UL << order;page = expand(zone, page, index, order, curr_order, area);spin_unlock_irqrestore(&zone->lock, flags);set_page_count(page, 1);if (BAD_RANGE(zone,page))BUG();if (PageLRU(page))BUG();if (PageActive(page))BUG();return page;} curr_order++; area++; } while (curr_order < MAX_ORDER); spin_unlock_irqrestore(&zone->lock, flags); return NULL; }
對該函數的解釋如下。
參數 zone 指向要配置設定頁面的管理區，order 表示要求配置設定的頁面數為 2 order 。
do 循環從 free_area 數組的第 order 個元素開始，掃描每個元素中由 page 結構組成的
雙向循環空閑隊列。如果找到合适的頁塊，就把它從隊列中删除，删除的過程是不允許其他
程序、其他處理器來打擾的。是以要用 spin_lock_irqsave()将這個循環加上鎖。
首先在恰好滿足大小要求的隊列裡進行配置設定。其中 memlist_entry(curr, struct page,
list)獲得空閑塊的第 1 個頁面的位址，如果這個位址是個無效的位址，就陷入 BUG()。如果
有效，memlist_del(curr)從隊列中摘除配置設定出去的頁面塊。如果某個頁面塊被配置設定出去，就
要在 frea_area 的位圖中進行标記，這是通過調用 MARK_USED()宏來完成的。
如果配置設定出去後還有剩餘塊，就通過 expand()獲得所配置設定的頁塊，而把剩餘塊鍊入适
當的空閑隊列中。
如果目前空閑隊列沒有空閑塊，就從更大的空閑塊隊列中找。
(2)expand()函數
該函數源代碼如下。
static inline struct page * expand (zone_t *zone, struct page *page, unsigned long index, int low, int high, free_area_t * area) { unsigned long size = 1 << high; while (high > low) { if (BAD_RANGE(zone,page)) BUG(); area--; high--; size >>= 1; memlist_add_head(&(page)->list, &(area)->free_list); MARK_USED(index, high, area); index += size; page += size; } if (BAD_RANGE(zone,page)) BUG(); return page; }
對該函數解釋如下。
參數 zone 指向已配置設定頁塊所在的管理區；page 指向已配置設定的頁塊；index 是已配置設定的
頁面在 mem_map 中的下标； low 表示所需頁面塊大小為 2 low，而 high 表示從空閑隊列中實
際進行配置設定的頁面塊大小為 2 high；area 是 free_area_struct 結構，指向實際要配置設定的頁塊。
通過上面介紹可以知道，傳回給請求者的塊大小為 2low 個頁面，并把剩餘的頁面放入合
适的空閑隊列，且對夥伴系統的位圖進行相應的修改。例如，假定我們需要一個 2 頁面的塊，
但是，我們不得不從 order 為 3(8 個頁面)的空閑隊列中進行配置設定，又假定我們碰巧選擇物
理頁面 800 作為該頁面塊的底部。在我們這個例子中，這幾個參數值為：
page == mem_map+800
index == 800
low == 1
high == 3
area == zone->free_area+high ( 也就是 frea_area 數組中下标為 3 的元素)
首先把 size 初始化為配置設定塊的頁面數(例如，size = 1<<3 == 8)
while 循環進行循環查找。每次循環都把 size 減半。如果我們從空閑隊列中配置設定的一個
塊與所要求的大小比對，那麼 low = high，就徹底從循環中跳出，傳回所配置設定的頁塊。
如果配置設定到的實體塊所在的空閑塊大于所需塊的大小(即 2 high>2low)，那就将該空閑塊
分為兩半(即 area--;high--; size >>= 1),然後調用 memlist_add_head()把剛配置設定出去
的頁面塊又加入到低一檔(實體塊減半)的空閑隊列中，準備從剩下的一半空閑塊中重新進
行配置設定，并調用 MARK_USED()設定位圖。
在上面的例子中，第 1 次循環，我們從頁面 800 開始，把頁面大小為 4(即 2high--)的塊
其首位址插入到 frea_area[2]中的空閑隊列；因為 low
面 804 開始，把頁面大小為 2 的塊插入到 frea_area[1]中的空閑隊列，此時，page＝806，
high=low＝1，退出循環，我們給調用者傳回從 806 頁面開始的一個 2 頁面塊。
從這個例子可以看出，這是一種巧妙的配置設定算法。
3．釋放頁面
從上面的介紹可以看出，頁面塊的配置設定必然導緻記憶體的碎片化，而頁面塊的釋放則可以
将頁面塊重新組合成大的頁面塊。頁面的釋放函數為__free_pages(page struct *page,
unsigned long order) ，該函數從給定的頁面開始，釋放的頁面塊大小為 2order。原函數為:
void __free_pages(page struct *page, unsigned long order){ if (!PageReserved(page) && put_page_testzero(page)) __free_pages_ok(page, order);}
其中比較巧妙的部分就是調用 put_page_testzero()宏，該函數把頁面的引用計數減 1，
如果減 1 後引用計數為 0，則該函數傳回 1。是以，如果調用者不是該頁面的最後一個使用者，
那麼，這個頁面實際上就不會被釋放。另外要說明的是不可釋放保留頁 PageReserved，這是
通過 PageReserved()宏進行檢查的。
如果調用者是該頁面的最後一個使用者，則__free_pages() 再調用 __free_pages_ok()。
__free_pages_ok()才是對頁面塊進行釋放的實際函數，該函數把釋放的頁面塊鍊入空閑鍊
表，并對夥伴系統的位圖進行管理，必要時合并夥伴塊。這實際上是 expand()函數的反操作，
我們對此不再進行詳細的讨論。
6.3.3 Slab 配置設定機制
采用夥伴算法配置設定記憶體時，每次至少配置設定一個頁面。但當請求配置設定的記憶體大小為幾十個
位元組或幾百個位元組時應該如何處理？如何在一個頁面中配置設定小的記憶體區，小記憶體區的配置設定所
産生的内碎片又如何解決？
Linux 2.0 采用的解決辦法是建立了 13 個空閑區連結清單，它們的大小從 32 位元組到 132056
位元組。從 Linux 2.2 開始，MM 的開發者采用了一種叫做 Slab 的配置設定模式，該模式早在 1994
年就被開發出來，用于 Sun Microsystem Solaris 2.4 作業系統中。Slab 的提出主要是基于
以下考慮。
核心對記憶體區的配置設定取決于所存放資料的類型。例如，當給使用者态程序配置設定頁面時，内
核調用 get_free_page()函數，并用 0 填充這個頁面。而給核心的資料結構配置設定頁面時，事
情沒有這麼簡單，例如，要對資料結構所在的記憶體進行初始化、在不用時要收回它們所占用
的記憶體。是以，Slab 中引入了對象這個概念，所謂對象就是存放一組資料結構的記憶體區，其
方法就是構造或析構函數，構造函數用于初始化資料結構所在的記憶體區，而析構函數收回相
應的記憶體區。但為了便于了解，你也可以把對象直接看作核心的資料結構。為了避免重複初
始化對象，Slab 配置設定模式并不丢棄已配置設定的對象，而是釋放但把它們依然保留在記憶體中。當
以後又要請求配置設定同一對象時，就可以從記憶體擷取而不用進行初始化，這是在 Solaris 中引
入 Slab 的基本思想。
實際上，Linux 中對 Slab 配置設定模式有所改進，它對記憶體區的處理并不需要進行初始化或
回收。出于效率的考慮，Linux 并不調用對象的構造或析構函數，而是把指向這兩個函數的
指針都置為空。Linux 中引入 Slab 的主要目的是為了減少對夥伴算法的調用次數。
實際上，核心經常反複使用某一記憶體區。例如，隻要核心建立一個新的程序，就要為該
程序相關的資料結構(task_struct、打開檔案對象等)配置設定記憶體區。當程序結束時，收回這
些記憶體區。因為程序的建立和撤銷非常頻繁，是以，Linux 的早期版本把大量的時間花費在
反複配置設定或回收這些記憶體區上。從 Linux 2.2 開始，把那些頻繁使用的頁面儲存在高速緩存
中并重新使用。
可以根據對記憶體區的使用頻率來對它分類。對于預期頻繁使用的記憶體區，可以建立一組
特定大小的專用緩沖區進行處理，以避免内碎片的産生。對于較少使用的記憶體區，可以建立
一組通用緩沖區(如 Linux 2.0 中所使用的 2 的幂次方)來處理，即使這種處理模式産生碎
片，也對整個系統的性能影響不大。
硬體高速緩存的使用，又為盡量減少對夥伴算法的調用提供了另一個理由，因為對夥伴
算法的每次調用都會“弄髒”硬體高速緩存，是以，這就增加了對記憶體的平均通路次數。
Slab 配置設定模式把對象分組放進緩沖區(盡管英文中使用了 Cache 這個詞，但實際上指的
是記憶體中的區域，而不是指硬體高速緩存)。因為緩沖區的組織和管理與硬體高速緩存的命中
率密切相關，是以，Slab 緩沖區并非由各個對象直接構成，而是由一連串的“大塊(Slab)”
構成，而每個大塊中則包含了若幹個同種類型的對象，這些對象或已被配置設定，或空閑，如圖
6.10 所示。一般而言，對象分兩種，一種是大對象，一種是小對象。所謂小對象，是指在一
個頁面中可以容納下好幾個對象的那種。例如，一個 inode 結構大約占 300 多個位元組，是以，
一個頁面中可以容納 8 個以上的 inode 結構，是以，inode 結構就為小對象。Linux 核心中把
小于 512 位元組的對象叫做小對象。
實際上，緩沖區就是主存中的一片區域，把這片區域劃分為多個塊，每塊就是一個 Slab，
每個 Slab 由一個或多個頁面組成，每個 Slab 中存放的就是對象。
因為 Slab 配置設定模式的實作比較複雜，我們不準備對其進行詳細的分析，隻對主要内容
給予描述。
1．Slab 的資料結構
Slab 配置設定模式有兩個主要的資料結構，一個是描述緩沖區的結構 kmem_cache_t，一個
是描述 Slab 的結構 kmem_slab_t，下面對這兩個結構給予簡要讨論。
(1)Slab
Slab 是 Slab 管理模式中最基本的結構。它由一組連續的實體頁面組成，對象就被順序
放在這些頁面中。其資料結構在 mm/slab.c 中定義如下：
/* * slab_t * * Manages the objs in a slab. Placed either at the beginning of mem allocated * for a slab, or allocated from an general cache. * Slabs are chained into three list: fully used, partial, fully free slabs. */ typedef struct slab_s { struct list_head list; unsigned long colouroff; void *s_mem; /* including colour offset */ unsigned int inuse; /* num of objs active in slab */ kmem_bufctl_t free; } slab_t;
這裡的連結清單用來将前一個 Slab 和後一個 Slab 連結起來形成一個雙向連結清單，colouroff
為該 Slab 上着色區的大小，指針 s_mem 指向對象區的起點，inuse 是 Slab 中所配置設定對象的
個數。最後，free 的值指明了空閑對象鍊中的第一個對象，kmem_bufctl_t 其實是一個整數。
Slab 結構的示意圖如圖 6.11 所示。
對于小對象，就把 Slab 的描述結構 slab_t 放在該 Slab 中；對于大對象，則把 Slab 結
構遊離出來，集中存放。關于 Slab 中的着色區再給予具體描述。
每個 Slab 的首部都有一個小小的區域是不用的，稱為“着色區(Coloring Area)”。
着色區的大小使 Slab 中的每個對象的起始位址都按高速緩存中的“緩存行(Cache Line)”
大小進行對齊(80386 的一級高速緩存行大小為 16 位元組，Pentium 為 32 位元組)。因為 Slab
是由 1 個頁面或多個頁面(最多為 32)組成，是以，每個 Slab 都是從一個頁面邊界開始的，
它自然按高速緩存的緩沖行對齊。但是，Slab 中的對象大小不确定，設定着色區的目的就是
将 Slab 中第一個對象的起始位址往後推到與緩沖行對齊的位置。因為一個緩沖區中有多個
Slab，是以，應該把每個緩沖區中的各個 Slab 着色區的大小盡量安排成不同的大小，這樣可
以使得在不同的 Slab 中，處于同一相對位置的對象，讓它們在高速緩存中的起始位址互相錯
開，這樣就可以改善高速緩存的存取效率。
每個 Slab 上最後一個對象以後也有個小小的廢料區是不用的，這是對着色區大小的補
償，其大小取決于着色區的大小，以及 Slab 與其每個對象的相對大小。但該區域與着色區的
總和對于同一種對象的各個 Slab 是個常數。
每個對象的大小基本上是所需資料結構的大小。隻有當資料結構的大小不與高速緩存中
的緩沖行對齊時，才增加若幹位元組使其對齊。是以，一個 Slab 上的所有對象的起始位址都必
然是按高速緩存中的緩沖行對齊的。
(2)緩沖區
每個緩沖區管理着一個 Slab 連結清單，Slab 按序分為 3 組。第 1 組是全滿的 Slab(沒有空
閑的對象)，第 2 組 Slab 中隻有部分對象被配置設定，部分對象還空閑，最後一組 Slab 中的對象
全部空閑。隻是以這樣分組，是為了對 Slab 進行有效的管理。每個緩沖區還有一個輪轉鎖
(Spinlock)，在對連結清單進行修改時用這個輪轉鎖進行同步。類型 kmem_cache_s 在 mm/slab.c
中定義如下：
struct kmem_cache_s {/* 1) each alloc & free */ /* full, partial first, then free */ struct list_head slabs_full; struct list_head slabs_partial; struct list_head slabs_free; unsigned int objsize; unsigned int flags; /* constant flags */ unsigned int num; /* # of objs per slab */ spinlock_t spinlock;#ifdef CONFIG_SMP unsigned int batchcount;#endif/* 2) slab additions /removals */ /* order of pgs per slab (2^n) */ unsigned int gfporder; /* force GFP flags, e.g. GFP_DMA */ unsigned int gfpflags; size_t colour; /* cache colouring range */ unsigned int colour_off; /* colour offset */ unsigned int colour_next; /* cache colouring */ kmem_cache_t *slabp_cache; unsigned int growing; unsigned int dflags; /* dynamic flags */ /* constructor func */ void (*ctor)(void *, kmem_cache_t *, unsigned long); /* de-constructor func */ void (*dtor)(void *, kmem_cache_t *, unsigned long); unsigned long failures;/* 3) cache creation/removal */ char name[CACHE_NAMELEN]; struct list_head next;#ifdef CONFIG_SMP/* 4) per-cpu data */ cpucache_t *cpudata[NR_CPUS];#endif…..};
然後定義了 kmem_cache_t，并給部分域賦予了初值：
static kmem_cache_t cache_cache = { slabs_full: LIST_HEAD_INIT(cache_cache.slabs_full), slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial), slabs_free: LIST_HEAD_INIT(cache_cache.slabs_free),objsize: sizeof(kmem_cache_t), flags: SLAB_NO_REAP, spinlock: SPIN_LOCK_UNLOCKED, colour_off: L1_CACHE_BYTES, name: "kmem_cache",};
對該結構說明如下。
該結構中有 3 個隊列 slabs_full、slabs_partial 以及 slabs_free，分别指向滿 Slab、
半滿 Slab 和空閑 Slab，另一個隊列 next 則把所有的專用緩沖區鍊成一個連結清單。
除了這些隊列和指針外，該結構中還有一些重要的域：objsize 是原始的資料結構的大
小，這裡初始化為 kmem_cache_t 的大小；num 表示每個 Slab 上有幾個緩沖區；gfporder 則
表示每個 Slab 大小的對數，即每個 Slab 由 2 gfporder個頁面構成。
如前所述，着色區的使用是為了使同一緩沖區中不同 Slab 上的對象區的起始位址互相
錯開，這樣有利于改善高速緩存的效率。colour_off 表示顔色的偏移量，colour 表示顔色的
數量；一個緩沖區中顔色的數量取決于 Slab 中對象的個數、剩餘空間以及高速緩存行的大小。
是以，對每個緩沖區都要計算它的顔色數量，這個數量就儲存在 colour 中，而下一個 Slab
将要使用的顔色則儲存在 colour_next 中。當 colour_next 達到最大值時，就又從 0 開始。
着色區的大小可以根據(colour_off×colour)算得。例如，如果 colour 為 5，colour_off
為 8，則第一個 Slab 的顔色将為 0，Slab 中第一個對象區的起始位址(相對)為 0，下一個
Slab 中第一個對象區的起始位址為 8，再下一個為 16，24，32，0……等。
cache_cache 變量實際上就是緩沖區結構的頭指針。
由此可以看出，緩沖區結構 kmem_cache_t 相當于 Slab 的總控結構，緩沖區結構與 Slab
結構之間的關系如圖 6.12 所示。
在圖 6.12 中，深灰色表示全滿的 Slab，淺灰色表示含有空閑對象的 Slab，而無色表示
空的 Slab。緩沖區結構之間形成一個單向連結清單，Slab 結構之間形成一個雙向連結清單。另外，緩
沖區結構還有分别指向滿、半滿、空閑 Slab 結構的指針。
2．專用緩沖區的建立和撤銷
專用緩沖區是通過 kmem_cache_create()函數建立的，函數原型為：
kmem_cache_t *kmem_cache_create(const char *name, size_t size, size_t offset,
unsigned long c_flags,
void (*ctor) (void *objp, kmem_cache_t *cachep, unsigned long flags),
void (*dtor) (void *objp, kmem_cache_t *cachep, unsigned long flags))
對其參數說明如下。
(1)name： 緩沖區名 ( 19 個字元)。
(2)size： 對象大小。
(3)offset ：所請求的着色偏移量。
(4)c_flags ：對緩沖區的設定标志。
• SLAB_HWCACHE_ALIGN：表示與第一個高速緩存中的緩沖行邊界(16 或 32 位元組)對齊。
• SLAB_NO_REAP：不允許系統回收記憶體。
• SLAB_CACHE_DMA：表示 Slab 使用的是 DMA 記憶體。
(5)ctor ：構造函數(一般都為 NULL)。
(6)dtor ：析構函數(一般都為 NULL)。
(7)objp ：指向對象的指針。
(8)cachep ：指向緩沖區。
對專用緩沖區的建立過程簡述如下。
kmem_cache_create()函數要進行一系列的計算，以确定最佳的 Slab 構成。包括：每
個 Slab 由幾個頁面組成，劃分為多少個對象；Slab 的描述結構 slab_t 應該放在 Slab 的外
面還是放在 Slab 的尾部；還有“顔色”的數量等等。并根據調用參數和計算結果設定
kmem_cache_t 結構中的各個域，包括兩個函數指針 ctor 和 dtor。最後，将 kmem_cache_t
結構插入到 cache_cache 的 next 隊列中。
但請注意，函數 kmem_cache_create()所建立的緩沖區中還沒有包含任何 Slab，是以，
也沒有空閑的對象。隻有以下兩個條件都為真時，才給緩沖區配置設定 Slab：
(1)已發出一個配置設定新對象的請求；
(2)緩沖區不包含任何空閑對象。
當這兩個條件都成立時，Slab 配置設定模式就調用 kmem_cache_grow()函數給緩沖區配置設定
一個新的 Slab。其中，該函數調用 kmem_gatepages()從夥伴系統獲得一組頁面；然後又調用
kmem_cache_slabgmt()獲得一個新的 Slab結構；還要調用 kmem_cache_init_objs()為新 Slab
中的所有對象申請構造方法(如果定義的話)；最後，調用 kmem_slab_link_end()把這個 Slab
結構插入到緩沖區中 Slab 連結清單的末尾。
Slab 配置設定模式的最大好處就是給頻繁使用的資料結建構立專用緩沖區。但到目前的版本
為止，Linux 核心中多數專用緩沖區的建立都用 NULL 作為構造函數的指針，例如，為虛存區
間結構 vm_area_struct 建立的專用緩沖區 vm_area_cachep：
vm_area_cachep = kmem_cache_create("vm_area_struct",
sizeof(struct vm_area_struct), 0,
SLAB_HWCACHE_ALIGN, NULL, NULL);
就把構造和析構函數的指針置為 NULL，也就是說，核心并沒有充分利用 Slab 管理機制
所提供的好處。為了說明如何利用專用緩沖區，我們從核心代碼中選取一個構造函數不為空
的簡單例子，這個例子與網絡子系統有關，在 net/core/buff.c 中定義：
void __init skb_init(void){ int i; skbuff_head_cache = kmem_cache_create("skbuff_head_cache", sizeof(struct sk_buff), 0, SLAB_HWCACHE_ALIGN, skb_headerinit, NULL); if (!skbuff_head_cache) panic("cannot create skbuff cache"); for (i=0; i
從代碼中可以看出，skb_init()調用 kmem_cache_create()為網絡子系統建立一個
sk_buff 資料結構的專用緩沖區，其名稱為“skbuff_head_cache”( 你可以通過讀取／
proc/slabinfo/檔案得到所有緩沖區的名字)。調用參數 offset 為 0，表示第一個對象在 Slab
中的位移并無特殊要求。但是參數 flags 為 SLAB_HWCACHE_ALIGN，表示 Slab 中的對象要與
高速緩存中的緩沖行邊界對齊。對象的構造函數為 skb_headerinit()，而析構函數為空，
也就是說，在釋放一個 Slab 時無需對各個緩沖區進行特殊的處理。
當從核心解除安裝一個子產品時，同時應當撤銷為這個子產品中的資料結構所建立的緩沖區，這
是通過調用 kmem_cache_destroy()函數來完成的。從 Linux 2.4.16 核心代碼中進行查找可
知，對這個函數的調用非常少。
3．通用緩沖區
在核心中初始化開銷不大的資料結構可以合用一個通用的緩沖區。通用緩沖區非常類似
于實體頁面配置設定中的大小分區，最小的為 32，然後依次為 64、128、……直至 128KB(即 32
個頁面)，但是，對通用緩沖區的管理又采用的是 Slab 方式。從通用緩沖區中配置設定和釋放緩
沖區的函數為：
void *kmalloc(size_t size, int flags);
Void kree(const void *objp);
是以，當一個資料結構的使用根本不頻繁時，或其大小不足一個頁面時，就沒有必要給
其配置設定專用緩沖區，而應該調用 kmallo()進行配置設定。如果資料結構的大小接近一個頁面，則
幹脆通過 alloc_page()為之配置設定一個頁面。
事實上，在核心中，尤其是驅動程式中，有大量的資料結構僅僅是一次性使用，而且所
占記憶體隻有幾十個位元組，是以，一般情況下調用 kmallo()給核心資料結構配置設定記憶體就足夠了。
另外，因為，在 Linux 2.0 以前的版本一般都調用 kmallo()給核心資料結構配置設定記憶體，是以，
調用該函數的一個優點是(讓你開發的驅動程式)能保持向後相容。
6.3.4 核心空間非連續記憶體區的管理
我們說，任何時候，CPU 通路的都是虛拟記憶體，那麼，在你編寫驅動程式，或者編寫模
塊時，Linux 給你配置設定什麼樣的記憶體？它處于 4GB 空間的什麼位置？這就是我們要讨論的非
連續記憶體。
首先，非連續記憶體處于 3GB 到 4GB 之間，也就是處于核心空間，如圖 6.13 所示。
圖 6.13 中，PAGE_OFFSET 為 3GB，high_memory 為儲存實體位址最高值的變量，
VMALLOC_START 為非連續區的的起始位址，定義于 include／i386/pgtable.h 中：
#define VMALLOC_OFFSET (8*1024*1024)
#define VMALLOC_START (((unsigned long) high_memory + 2*VMALLOC_OFFSET-1) & ~
(VMALLOC_OFFSET-1))
在實體位址的末尾與第一個記憶體區之間插入了一個 8MB(VMALLOC_OFFSET)的區間，這
是一個安全區，目的是為了“捕獲”對非連續區的非法通路。出于同樣的理由，在其他非連
續的記憶體區之間也插入了 4KB 大小的安全區。每個非連續記憶體區的大小都是 4096 的倍數。
1．非連續區的資料結構
描述非連續區的資料結構為 struct vm_struct，定義于 include/linux/vmalloc.h 中：
struct vm_struct { unsigned long flags; void * addr; unsigned long size; struct vm_struct * next;};
struct vm_struct * vmlist;
非連續區組成一個單連結清單，連結清單第一個元素的位址存放在變量 vmlist 中。Addr 域是内
存區的起始位址；size 是記憶體區的大小加 4096(安全區的大小)。
2．建立一個非連續區的結構
函數 get_vm_area()建立一個新的非連續區結構，其代碼在 mm/vmalloc.c 中：
struct vm_struct * get_vm_area(unsigned long size, unsigned long flags) { unsigned long addr; struct vm_struct **p, *tmp, *area; area = (struct vm_struct *) kmalloc(sizeof(*area), GFP_KERNEL); if (!area) return NULL; size += PAGE_SIZE; addr = VMALLOC_START; write_lock(&vmlist_lock); for (p = &vmlist; (tmp = *p) ; p = &tmp->next) { if ((size + addr) < addr) goto out; if (size + addr <= (unsigned long) tmp->addr) break; addr = tmp->size + (unsigned long) tmp->addr; if (addr > VMALLOC_END-size) goto out; } area->flags = flags; area->addr = (void *)addr; area->size = size; area->next = *p; *p = area; write_unlock(&vmlist_lock); return area;out: write_unlock(&vmlist_lock); kfree(area); return NULL; }
這個函數比較簡單，就是在單連結清單中插入一個元素。其中調用了 kmalloc()和 kfree()
函數,分别用來為 vm_struct 結構配置設定記憶體和釋放所配置設定的記憶體。
3．配置設定非連續記憶體區
vmalloc()函數給核心配置設定一個非連續的記憶體區，在/include/linux/vmalloc.h 中定
義如下：
static inline void * vmalloc (unsigned long size) { return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL); }vmalloc()最終調用的是__vmalloc()函數，該函數的代碼在 mm/vmalloc.c 中： void * __vmalloc (unsigned long size, int gfp_mask, pgprot_t prot) { void * addr; struct vm_struct *area; size = PAGE_ALIGN(size); if (!size || (size >> PAGE_SHIFT) > num_physpages) { BUG(); return NULL; } area = get_vm_area(size, VM_ALLOC); if (!area) return NULL; addr = area->addr; if (vmalloc_area_pages(VMALLOC_VMADDR(addr), size, gfp_mask, prot)) { vfree(addr); return NULL; } return addr; }
函數首先把 size 參數取整為頁面大小(4096)的一個倍數，也就是按頁的大小進行對
齊，然後進行有效性檢查，如果有大小合适的可用記憶體，就調用 get_vm_area()獲得一個
記憶體區的結構。但真正的記憶體區還沒有獲得，函數 vmalloc_area_pages()真正進行非連續
記憶體區的配置設定：
inline int vmalloc_area_pages (unsigned long address, unsigned long size, int gfp_mask, pgprot_t prot) { pgd_t * dir; unsigned long end = address + size; int ret; dir = pgd_offset_k(address); spin_lock(&init_mm.page_table_lock); do { pmd_t *pmd; pmd = pmd_alloc(&init_mm, dir, address); ret = -ENOMEM; if (!pmd) break; ret = -ENOMEM; if (alloc_area_pmd(pmd, address, end - address, gfp_mask, prot)) break; address = (address + PGDIR_SIZE) & PGDIR_MASK; dir++; ret = 0; } while (address && (address < end));spin_unlock(&init_mm.page_table_lock); return ret; }
該函數有兩個主要的參數，address 表示記憶體區的起始位址，size 表示記憶體區的大小。
記憶體區的末尾位址賦給了局部變量 end。其中還調用了幾個主要的函數或宏。
(1)pgd_offset_k()宏導出這個記憶體區起始位址在頁目錄中的目錄項。
(2)pmd_alloc()為新的記憶體區建立一個中間頁目錄。
(3)alloc_area_pmd()為新的中間頁目錄配置設定所有相關的頁表，并更新頁的總目錄；
該函數調用 pte_alloc_kernel()函數來配置設定一個新的頁表，之後再調用 alloc_area_pte()
為頁表項配置設定具體的實體頁面。
(4)從 vmalloc_area_pages()函數可以看出，該函數實際建立起了非連續記憶體區到物
理頁面的映射。
4．kmalloc()與 vmalloc()的差別
kmalloc()與 vmalloc() 都是在核心代碼中提供給其他子系統用來配置設定記憶體的函數，但
二者有何差別？
從前面的介紹已經看出，這兩個函數所配置設定的記憶體都處于核心空間，即從 3GB～4GB；但位
置不同，kmalloc()配置設定的記憶體處于 3GB～high_memory 之間，而 vmalloc()配置設定的記憶體在
VMALLOC_START～4GB 之間，也就是非連續記憶體區。一般情況下在驅動程式中都是調用 kmalloc()
來給資料結構配置設定記憶體，而 vmalloc()用在為活動的交換區配置設定資料結構，為某些 I/O 驅動程
序配置設定緩沖區，或為子產品配置設定空間，例如在 include/asm-i386/module.h 中定義了如下語句：
#define module_map(x) vmalloc(x)
其含義就是把子產品映射到非連續的記憶體區。
與 kmalloc()和 vmalloc()相對應，兩個釋放記憶體的函數為 kfree()和 vfree()。