深入理解Linux內核——記憶體管理（3）

提要：本系列文章主要參考MIT 6.828課程以及兩本書籍《深入理解Linux內核》 《深入Linux內核架構》對Linux內核內容進行總結。
記憶體管理的實現覆蓋了多個領域：

1. 記憶體中的物理記憶體頁的管理
2. 分配大塊記憶體的伙伴系統
3. 分配較小記憶體的slab、slub、slob分配器
4. 分配非連續記憶體塊的vmalloc分配器
5. 進程的地址空間

上一節介紹了記憶體管理相關的主要數據結構以及它們之間的關係，本節主要介紹這些數據結構的初始化，方便在介紹記憶體分配時讀者思路更加清晰（這部分內容主要參考《深入Linux內核架構》）。

函數start_kernel()負責完成Linux內核的初始化工作，記憶體管理相關數據結構的初始化也是從這裡進行的。下圖給出 start_kernel的代碼流程圖，其中只包括記憶體管理相關的系統初始化函數。

各個函數的作用簡述如下：

為了簡化記憶，筆者做瞭如下的總結：

1. 由於記憶體管理是對物理記憶體的管理，因此必須瞭解整體體繫結構相關信息，因此先需要通過BIOS等提供的API獲取這些信息併進行配置。
2. 在記憶體管理初期，需要對記憶體管理本身使用的空間進行分配，因此需要初始化一個自舉分配器完成這項工作
3. 通過已經存在的自舉分配器就可以創建3層數據結構，即下圖結構：
   
4. 記憶體管理的基本數據結構已經初始化，剩下的記憶體管理功能可以交給伙伴系統了，就需要將自舉分配器占用的記憶體釋放掉或者交由伙伴系統管理
5. 為slab分配器進行一些簡單的配置

那我們依序開始。

setup_arch

由於記憶體管理管理的是真實的物理記憶體，因此，需要和體繫結構強相關，setup_arch函數主要負責這一部分內容。下圖給出了setup_arch中與記憶體管理相關的代碼流程圖：

各個函數職責如下：

本部分主要介紹兩個內容：

1. 因為Linux極大程度使用頁式管理，為了保證完成性，這裡簡單介紹paging_init函數（可以跳過）
2. 為了加速訪問頁，Linux實現了一個冷熱分配器（hot-n-cold allocator），這裡介紹冷熱緩存的初始化（引出free_area_init_nodes，這個函數很重要）

paging_init

paging_init負責按照指定方式（通常是3：1）劃分虛擬地址空間，代碼流程圖如下：

1. pagetable_init首先初始化系統的頁表，以swapper_pg_dir為基礎（該變數此前用於保存臨時數據）。接下來啟用在所有現代IA-32系統上可用的兩個擴展：
   • 對超大記憶體頁的支持。這些特別標記的頁，其長度為4 MiB，而不是普通的4 KiB。該選項用於不會換出的內核頁
   • 如有可能，內核頁會設置另一個屬性（_PAGE_GLOBAL）。在上下文切換期間，設置了_PAGE_GLOBAL位的頁，對應的TLB緩存項不從TLB刷出。由於內核總是出現於虛擬地址空間中同樣的位置，這提高了系統性能
2. 藉助於kernel_physical_mapping_init，將物理記憶體頁（或前896 MiB，正如上一節的討論）映射到虛擬地址空間中從PAGE_OFFSET開始的位置。
3. 接下來建立固定映射項和持久內核映射對應的記憶體區。同樣是用適當的值填充頁表。
4. 在用pagetable_init完成頁表初始化之後，則將cr3寄存器設置為指向全局頁目錄（swapper_pg_dir）的指針。此時必須激活新的頁表
5. 由於TLB緩存項仍然包含了啟動時分配的一些記憶體地址數據，此時也必須刷出。__flush_all_tlb可完成所需的工作。與上下文切換期間相反，設置了_PAGE_GLOBAL位的頁也要刷出。
6. kmap_init初始化全局變數kmap_pte。在從高端記憶體域將頁映射到內核地址空間時，會使用該變數存入相應記憶體區的頁表項。此外，用於高端記憶體內核映射的第一個固定映射記憶體區的地址保存在全局變數kmem_vstart中。

冷熱緩存的初始化

struct zone的pageset成員用於實現冷熱分配器（hot-n-cold allocator）。

1. 頁是熱的，意味著頁已經載入到CPU高速緩存，與在記憶體中的頁相比，其數據能夠更快地訪問。
2. 頁是冷的，則不在高速緩存中。

struct zone {
    ...
    struct per_cpu_pageset pageset[NR_CPUS];
    ...
};

在多處理器系統上每個CPU都有一個或多個高速緩存，各個CPU的管理必須是獨立的（從struct 名字也可以看出來per_cpu_pageset）。這裡的NR_CPUS是一個可以在編譯時間配置的巨集常，表示內核支持的CPU的最大數目。struct per_cpu_pageset代碼如下：

struct per_cpu_pageset {
    struct per_cpu_pages pcp[2]; /* 索引0對應熱頁，索引1對應冷頁 */
} ____cacheline_aligned_in_smp;

由註釋可以看到，對於每個cpu都包含了一個struct per_cpu_pages數組，長度為2，pcp[0]存儲熱頁，pcp[1]存儲冷頁。struct per_cpu_pages結構體代碼如下：

struct per_cpu_pages {
    int count; /* 列表中頁數 */
    int high; /* 頁數上限stake，在需要的情況下清空列表 */
    int batch; /* 添加/刪除多頁塊的時候，塊的大小 */
    struct list_head list; /* 頁的鏈表 */
};

多處理器下，pageset結構形如下圖：

而pageset屬性的初始化，就由setup_arch()完成，具體來說是free_area_init_nodes()函數，伙伴系統的數據結構初始化也是由這個方法完成的，因此會看setup_arch處介紹該函數時，描述是體繫結構無關的函數free_area_init_nodes接下來使用該信息建立完備的內核數據結構。

free_area_init_nodes()調用zone_pcp_init初始化冷熱緩存。可以看到struct per_cpu_pages主要包括兩個屬性：

1. high：頁數上限stake，在需要的情況下清空列表
2. batch: 添加/刪除多頁塊的時候，塊的大小

static __devinit void zone_pcp_init(struct zone *zone)
{
    int cpu;
    unsigned long batch = zone_batchsize(zone);
    for (cpu = 0; cpu < NR_CPUS; cpu++) {
        setup_pageset(zone_pcp(zone,cpu), batch);
    }
    if (zone->present_pages)
        printk(KERN_DEBUG " %s zone: %lu pages, LIFO batch:%lu\n",zone->name, zone->present_pages, batch);
}

zone_pcp_init通過調用zone_batchsize計算batch的具體值，然後再通過setup_pageset以batch為參考初始化每個struct per_cpu_pages：

inline void setup_pageset(struct per_cpu_pageset *p, unsigned long batch)
{
    struct per_cpu_pages *pcp;
    memset(p, 0, sizeof(*p));
    pcp = &p->pcp[0]; /* 熱 */
    pcp->count = 0;
    pcp->high = 6 * batch;
    pcp->batch = max(1UL, 1 * batch);
    INIT_LIST_HEAD(&pcp->list);
    pcp = &p->pcp[1]; /* 冷 */
    pcp->count = 0;
    pcp->high = 2 * batch;
    pcp->batch = max(1UL, batch/2);
    INIT_LIST_HEAD(&pcp->list);
}

可以看到:

1. 對於熱頁，high=6*batch，batch=max(1UL, 1 * batch)
2. 對於冷頁，high=2*batch，batch=max(1UL, batch/2)

冷頁列表的stake稍低一些，因為冷頁並不放置到緩存中，只用於一些關註性能的操作（當然，在內核中這樣的操作屬於少數）。最後給出batch的計算方法即zone_batchsize:

static int __devinit zone_batchsize(struct zone *zone)
{
    int batch;
    batch = zone->present_pages / 1024;
    if (batch * PAGE_SIZE > 512 * 1024)
        batch = (512 * 1024) / PAGE_SIZE;
    batch /= 4;
    if (batch < 1)
        batch = 1;
    batch = (1 << (fls(batch + batch/2)-1)) -1;
    return batch;
}

公式比較複雜（用的時候找得到出處就好），但上述代碼計算得到的batch，大約相當於記憶體域中頁數的0.25‰。

結點和記憶體域初始化

註意：初始化系統中所有結點的pgdat_t實例是在setup_arch中的zone_sizes_init完成的。

build_all_zonelists負責建立管理結點和其記憶體域所需的數據結構，這裡我們主要關註的是zonelist的組織順序。在UMA系統中，只有一個結點需要管理，為了方便通過node id獲取具體的pg_data_t（後面稱作結點描述符）實例信息，linux提供瞭如下的巨集：

#define NODE_DATA(nid)

但對於UMA來說，這個巨集的實現就是如下代碼：

#define NODE_DATA(nid) (&contig_page_data)

我們在上一節介紹Node時，註意中提到了contig_page_data就是UMA中唯一的結點。

但是整個Node中有3個管理區，三個管理區的分配次序如何呢？

我們在Node的數據結構中找到了一個名為node_zonelists的屬性，該屬性主要用於指定備用結點及其記憶體域的列表，以便在當前結點沒有可用空間時，在備用結點分配記憶體，例如如果ZONE_HIGHMEM記憶體域記憶體不夠分配時，可以嘗試向ZONE_NORMAL請求分配記憶體。

typedef struct pglist_data {
    ...
    struct zonelist node_zonelists[MAX_ZONELISTS];
    ...
} pg_data_t;

#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
struct zonelist {
    ...
    struct zone *zones[MAX_ZONES_PER_ZONELIST + 1]; // NULL分隔
};

在介紹Zone時，我們介紹了3類Zone：

這三類記憶體中ZONE_DMA部分，ISA可以對其進行直接定址，ZONE_NORMAL也是直接映射到內核空間的，而ZONE_HIGHMEM就需要選擇性的映射到內核空間中。在這3類記憶體中：

1. ZONE_DMA是最昂貴的，它用於外設和系統之間的數據傳輸
2. ZONE_NORMAL其次，許多內核數據結構必須保存在該記憶體域
3. ZONE_HIGHMEM最廉價，因為內核沒有任何部分依賴於從該記憶體域分配的記憶體。

針對這個情況，內核針對當前記憶體結點的備選結點，定義了一個等級次序，確定這一等級次序的函數就是build_zonelists函數。

內核在調用了build_all_zonelists後，會將工作委托給__build_all_zonelists，該函數只是簡單的對每個結點都調用build_zonelists:

static int __build_all_zonelists(void *dummy)
{
    int nid;
        for_each_online_node(nid) {
            pg_data_t *pgdat = NODE_DATA(nid);
            build_zonelists(pgdat);
            ...
        }
    return 0;
}

結構體zonelist的定義如下：

#define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES)
struct zonelist {
    ...
    struct zone *zones[MAX_ZONES_PER_ZONELIST + 1]; // NULL分隔
};

其長度為Node數*Zone數+1，最後一個結點是NULL負責標記列表結尾。在pg_data_t中，node_zonelists的長度為MAX_ZONELISTS

typedef struct pglist_data {
    ...
    struct zonelist node_zonelists[MAX_ZONELISTS];
    ...
} pg_data_t;

這個長度是多少呢？build_zonelists()函數給出了這個答案：

static void __init build_zonelists(pg_data_t *pgdat)
{
  int node, local_node;
  enum zone_type i,j;
  local_node = pgdat->node_id;
  for (i = 0; i < MAX_NR_ZONES; i++) {
      struct zonelist *zonelist;
      zonelist = pgdat->node_zonelists + i;
      j = build_zonelists_node(pgdat, zonelist, 0, i);
  ...
}

build_zonelists()函數為每個ZONE創建了一個zonelist用於表示其備用記憶體域列表，填充該列表的工作主要交給build_zonelists_node()方法：

static int __init build_zonelists_node(pg_data_t *pgdat, struct zonelist *zonelist,
    int nr_zones, enum zone_type zone_type)
{
    struct zone *zone;
    do {
        // 通過指針獲取zone_type類型的zone
        zone = pgdat->node_zones + zone_type;
        // 如果有空閑空間，則將zone添加到zonelists中
        if (populated_zone(zone)) {
            zonelist->zones[nr_zones++] = zone;
        }
        // 選取更為昂貴的zone判斷是否加入到備用列表中
        zone_type--;
    } while (zone_type >= 0);
    return nr_zones;
}

這裡有一個小細節，在內核中zone_type使用如下enum來保存：

enum zone_type {
#ifdef CONFIG_ZONE_DMA
    ZONE_DMA,
#endif
#ifdef CONFIG_ZONE_DMA32
    ZONE_DMA32,
#endif
    ZONE_NORMAL,
#ifdef CONFIG_HIGHMEM
    ZONE_HIGHMEM,
#endif
    ZONE_MOVABLE,
    MAX_NR_ZONES
};

因此，每次zone_type --就是選取了更為昂貴的記憶體區域。因此，內核在build_zonelists中按分配代價從昂貴到低廉的次序，迭代了結點中所有的記憶體域。而在build_zonelists_node中，則按照分配代價從低廉到昂貴的次序，迭代了分配代價不低於當前記憶體域的記憶體域。

舉一個例子，對於一個系統擁有4個結點，其結點2的高端記憶體即ZONE_HIGHMEM的備用列表創建過程大致如下：

因為zonelist還會引用其它結點的記憶體域，因此需要確定結點之間的次序，相關代碼如下：

static void __init build_zonelists(pg_data_t *pgdat)
{
  ...
  for (node = local_node + 1; node < MAX_NUMNODES; node++) {
      j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
  }
  for (node = 0; node < local_node; node++) {
      j = build_zonelists_node(NODE_DATA(node), zonelist, j, i);
  }
  zonelist->zones[j] = NULL;
  }
}

實際上就是先引用大於當前結點的結點，再引用小於當結點結點。對總數N個結點中的結點m來說，內核生成備用列表時，選擇備用結點的順序總是：m 、m+1、m+2、…、 N-1、0、1、…、 m-1。這確保了不過度使用任何結點。最終結點2即第三個結點上的每個Zone的備用列表如下：

自舉分配器

在啟動過程期間，儘管記憶體管理尚未初始化，但內核仍然需要分配記憶體以創建各種數據結構。bootmem分配器用於在啟動階段早期分配記憶體。

顯然，對該分配器的需求集中於簡單性方面，而不是性能和通用性。因此內核開發者決定實現一個 最先適配（first-fit）分配器用於在啟動階段管理記憶體，這是可能想到的最簡單方式。

傳統操作系統課本會介紹4種動態分區分配方法：

這裡選用的是首次適應演算法（通常效果最好）：

該分配器使用一個點陣圖來管理頁，點陣圖比特位的數目與系統中物理記憶體頁的數目相同。比特位為1，表示已用頁；比特位為0，表示空閑頁。因為該過程不是很高效，因為每次分配都必須從頭掃描比特鏈。因此在內核完全初始化之後，不能將該分配器用於記憶體管理。

為了實現該自舉分配器，內核使用瞭如下結構：

typedef struct bootmem_data {
    // 保存了系統中第一個頁的編號，大多數體繫結構下都是零
    unsigned long node_boot_start;
    // 是可以直接管理的物理地址空間中最後一頁的編號。換句話說，即ZONE_NORMAL的結束頁
    unsigned long node_low_pfn;
    // 是指向存儲分配點陣圖的記憶體區的指針。
    void *node_bootmem_map;
    // last_pos是上一次分配的頁的編號。如果沒有請求分配整個頁，則last_offset用作該頁內部的偏移量。這使得bootmem分配器可以分配小於一整頁的記憶體區
    unsigned long last_offset;
    unsigned long last_pos;
    // last_success指定點陣圖中上一次成功分配記憶體的位置，新的分配將由此開始。儘管這使得最先適配演算法稍快了一點，但仍然無法真正代替更複雜的技術。
    unsigned long last_success;
    // 記憶體不連續的系統可能需要多個bootmem分配器。
    struct list_head list;
} bootmem_data_t;

初始化

bootmem分配器的初始化是一個特定於體繫結構的過程，此外還取決於所述電腦的記憶體佈局。IA-32使用setup_memory，setup_bootmem_allocator來初始化bootmem分配器，而AMD64則使用contig_initmem_init。

對內核的介面

bootmem對於分配記憶體提供瞭如下介面：

1. alloc_bootmem(size)和alloc_bootmem_pages(size)按指定大小在ZONE_NORMAL記憶體域分配記憶體。數據是對齊的，這使得記憶體或者從可適用於L1高速緩存的理想位置開始，或者從頁邊界開始
2. alloc_bootmem_low和alloc_bootmem_low_pages的工作方式類似於上述函數，只是從ZONE_DMA記憶體域分配記憶體

這些函數都是__alloc_bootmem的前端，後者將實際工作委托給__alloc_bootmem_nopanic。由於可以註冊多個bootmem分配器,__alloc_bootmem_core會遍歷所有的分配器，直至分配成功為止。

在NUMA系統上，__alloc_bootmem_node則用於實現該API函數。首先，工作傳遞到__alloc_bootmem_core，嘗試在該結點的bootmem分配器進行分配。如果失敗，則後退到__alloc_bootmem，並將嘗試所有的結點。

void * __init __alloc_bootmem(unsigned long size, unsigned long align,unsigned long goal)

__alloc_bootmem需要3個參數來᧿述記憶體分配請求：size是所需記憶體區的長度，align表示數據的對齊方式，而goal指定了開始搜索適當空閑記憶體區的起始地址。在進行記憶體分配時，大致執行如下操作（和課本上講述的首次適應演算法步驟基本類似）：

1. 從goal開始，掃᧿點陣圖，查找滿足分配請求的空閑記憶體區。
2. 如果目標頁緊接著上一次分配的頁，即bootmem_data-> last_pos，內核會檢查bootmem_data->last_offset，判斷所需的記憶體（包括對齊數據所需的空間）是否能夠在上一頁分配或從上一頁開始分配。
3. 新分配的頁在點陣圖對應的比特位設置為1。最後一頁的數目也保存在bootmem_data->last_pos。如果該頁未完全分配，則相應的偏移量保存在bootmem_data->last_offset;否則，該值設置為0。

bootmem提供了free_bootmem和free_bootmem_node（NUMA）來釋放記憶體，但這兩個方法都將具體邏輯委托給__free_bootmem_core。

停用bootmem分配器和釋放初始化數據

在系統初始化進行到伙伴系統分配器能夠承擔記憶體管理的責任後，必須停用bootmem分配器，停用過程調用free_bootmem和free_bootmem_node（NUMA）函數來完成：

1. 首先掃᧿bootmem分配器的頁點陣圖，釋放每個未用的頁。到伙伴系統的介面是__free_pages_bootmem函數，該函數對每個空閑頁調用。該函數內部依賴於標準函數__free_page。它使得這些頁併入伙伴系統的數據結構，在其中作為空閑頁管理，可用於分配。
2. 在頁點陣圖已經完全掃᧿之後，它占據的記憶體空間也必須釋放。此後，只有伙伴系統可用於記憶體分配。

許多內核代碼塊和數據表只在系統初始化階段需要，因此不必要在內核記憶體中保持其數據結構的初始化常式。

內核提供了兩個屬性（__init和__initcall）用於標記初始化函數和數據，釋放記憶體時，只需要刪除這部分數據就可以了。使用樣例如下：

int __init hyper_hopper_probe(struct net_device *dev)

static char stilllooking_msg[] __initdata = "still searching...";

初始化函數實現的背後，其一般性的思想在於，將數據保持在內核映像的一個特定部分，在啟動結束時可以完全從記憶體刪除。可以從上面兩個label的巨集定義看到：

#define __init __attribute__ ((__section__ (".init.text"))) __cold
#define __initdata __attribute__ ((__section__ (".init.data")))

__attribute__是一個特殊的GNU C關鍵字，屬性即通過該關鍵字使用。__section__屬性用於通知編譯器將隨後的數據或函數分別寫入二進位文件（ELF文件）的.init.data和.init.text段。首碼__cold還通知編譯器，通向該函數的代碼路徑可能性較低，即該函數不會經常調用，對初始化函數通常是這樣。

因此只需要瞭解這兩個段的起始和終止地址，對應釋放這部分就可以了。內核定義了一對變數__init_begin和__init_end，負責完成該工作。

總結

本部分主要介紹了內核管理主要數據結構的初始化內容，下一節我們會開始介紹伙伴系統。