啟動期間的記憶體管理之引導分配器bootmem--Linux記憶體管理(十)

在記憶體管理的上下文中, 初始化(initialization)可以有多種含義. 在許多CPU上, 必須顯式設置適用於Linux內核的記憶體模型. 例如在x86_32上需要切換到保護模式, 然後內核才能檢測到可用記憶體和寄存器.

而我們今天要講的bootmem分配器就是系統初始化階段使用的記憶體分配器.

為什麼要使用bootmem分配器，記憶體管理不是有buddy系統和slab分配器嗎？由於在系統初始化的時候需要執行一些記憶體管理，記憶體分配的任務，這個時候buddy系統，slab分配器等並沒有被初始化好，此時就引入了一種記憶體管理器bootmem分配器在系統初始化的時候進行記憶體管理與分配，當buddy系統和slab分配器初始化好後，在mem_init()中對bootmem分配器進行釋放，記憶體管理與分配由buddy系統，slab分配器等進行接管。

bootmem分配器使用一個bitmap來標記物理頁是否被占用，分配的時候按照第一適應的原則，從bitmap中進行查找，如果這位為1，表示已經被占用，否則表示未被占用。為什麼系統運行的時候不使用bootmem分配器呢？bootmem分配器每次在bitmap中進行線性搜索，效率非常低，而且在記憶體的起始端留下許多小的空閑碎片，在需要非常大的記憶體塊的時候，檢查點陣圖這一過程就顯得代價很高。bootmem分配器是用於在啟動階段分配記憶體的，對該分配器的需求集中於簡單性方面，而不是性能和通用性.

2. 引導記憶體分配器bootmem概述

由於硬體配置多種多樣, 所以在編譯時就靜態初始化所有的內核存儲結構是不現實的.

bootmem分配器是系統啟動初期的記憶體分配方式，在耳熟能詳的伙伴系統建立前記憶體都是利用bootmem分配器來分配的，伙伴系統框架建立起來後，bootmem會過度到伙伴系統.

2.1 初始化階段的引導記憶體分配器bootmem

在啟動過程期間, 儘管記憶體管理尚未初始化, 但是內核仍然需要分配記憶體以創建各種數據結構. 因此在系統啟動過程期間, 內核使用了一個額外的簡化形式的記憶體管理模塊引導記憶體分配器(boot memory allocator–bootmem分配器), 用於在啟動階段早期分配記憶體, 而在系統初始化完成後, 該分配器被內核拋棄, 然後初始化了一套新的更加完善的記憶體分配器.

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

引導記憶體分配器(boot memory allocator–bootmem分配器)基於最先適配(first-first)分配器的原理(這兒是很多系統的記憶體分配所使用的原理), 使用一個點陣圖來管理頁, 以點陣圖代替原來的空閑鏈表結構來表示存儲空間, 點陣圖的比特位的數目與系統中物理記憶體頁面數目相同. 若點陣圖中某一位是1, 則標識該頁面已經被分配(已用頁), 否則表示未被占有(未用頁).

在需要分配記憶體時, 分配器逐位的掃描點陣圖, 直至找到一個能提供足夠連續頁的位置, 即所謂的最先最佳(first-best)或最先適配位置.

該分配機制通過記錄上一次分配的頁面幀號(PFN)結束時的偏移量來實現分配大小小於一頁的空間, 連續的小的空閑空間將被合併存儲在一頁上.

2.2 為什麼需要bootmem

2.3 為什麼在系統運行時拋棄bootmem

當系統運行時, 為何不繼續使用bootmem分配機制呢?

• 其中一個關鍵原因在於 : 但它每次分配都必須從頭掃描點陣圖, 每次通過對記憶體域進行線性搜索來實現分配.
• 其次首先適應演算法容易在記憶體的起始斷留下許多小的空閑碎片, 在需要分配較大的空間頁時,　檢查點陣圖的成本將是非常高的.

引導記憶體分配器bootmem分配器簡單卻非常低效,　因此在內核完全初始化之後,　不能將該分配器繼續歐諾個與記憶體管理,　而伙伴系統(連同slab, slub或者slob分配器)是一個好很多的備選方案．

3 引導記憶體分配器數據結構

內核用bootmem_data表示引導記憶體區域

即使是初始化用的最先適配分配器也必須使用一些數據結構存, 內核為系統中每一個結點都提供了一個struct bootmem_data結構的實例, 用於bootmem的記憶體管理. 它含有引導記憶體分配器給結點分配記憶體時所需的信息. 當然, 這時候記憶體管理還沒有初始化, 因而該結構所需的記憶體是無法動態分配的, 必須在編譯時分配給內核.

在UMA系統上該分配的實現與CPU無關, 而NUMA系統記憶體結點與CPU相關聯, 因此採用了特定體繫結構的解決方法.

3.1 bootmem_data描述記憶體引導區

bootmem_data的結構定義在include/linux/bootmem.h?v=4.7, line 28, 其定義如下所示

#ifndef CONFIG_NO_BOOTMEM
/*
* node_bootmem_map is a map pointer - the bits represent all physical 
* memory pages (including holes) on the node.
*/
typedef struct bootmem_data {
       unsigned long node_min_pfn;
       unsigned long node_low_pfn;
       void *node_bootmem_map;
       unsigned long last_end_off;
       unsigned long hint_idx;
       struct list_head list;
} bootmem_data_t;

extern bootmem_data_t bootmem_node_data[];

#endif

bootmem的點陣圖建立在從start_pfn開始的地方, 也就是說, 內核映像終點_end上方的地方. 這個點陣圖用來管理低區（例如小於 896MB), 因為在0到896MB的範圍內, 有些頁面可能保留, 有些頁面可能有空洞, 因此, 建立這個點陣圖的目的就是要搞清楚哪一些物理頁面是可以動態分配的

• node_bootmem_map就是一個指向點陣圖的指針. node_min_pfn表示存放bootmem點陣圖的第一個頁面(即內核映像結束處的第一個頁面)
• node_low_pfn 表示物理記憶體的頂點, 最高不超過896MB

4 初始化引導分配器

系統是從start_kernel開始啟動的, 在啟動過程中通過調用體繫結構相關的setup_arch函數, 來獲取初始化引導記憶體分配器所需的參數信息, 各種體繫結構都有對應的函數來獲取這些信息, 在獲取信息完成後, 內核首先初始化了bootmem自身, 然後接著又用bootmem分配和初始化了記憶體結點和管理域, 因此初始化bootmem的工作主要分成兩步

• 初始化bootmem自身的數據結構
• 用bootmem初始化記憶體結點管理域

bootmem分配器的初始化是一個特定於體繫結構的過程, 此外還取決於系統的記憶體佈局

系統是從start_kernel開始啟動的, 在啟動過程中通過調用體繫結構相關的setup_arch函數, 來獲取初始化引導記憶體分配器所需的參數信息, 各種體繫結構都有對應的函數來獲取這些信息.

4.1 IA-32的初始化

在使用bootmem, 內核在setup_arch函數中通過setup_memory來分析檢測到的記憶體區, 以找到低端記憶體區中最大的頁幀號。由於高端記憶體處理太麻煩，由此對bootmem分配器無用。全局變數max_low_pfn保存了可映射的最高頁的編號。內核會在啟動日誌中報告找到的記憶體的數量。

5 bootmem分配記憶體介面

bootmem提供了各種函數用於在初始化期間分配記憶體.

儘管mm/bootmem.c中提供了一些了的記憶體分配函數，但是這些函數大多數以__下劃線開頭, 這個標識告訴我們儘量不要使用他們, 他們過於底層, 往往是不安全的, 因此特定於某個體系架構的代碼並沒有直接調用它們，而是通過linux/bootmem.h提供的一系列的巨集

5.1 NUMA結構的分配函數

首先我們講解一下子在UMA系統中, 可供使用的函數.

5.1.1 從ZONE_NORMAL區域分配函數

下麵列出的這些函數可以從ZONE_NORMAL記憶體域分配指向大小的記憶體

這些函數的定義在include/linux/bootmem.h

http://lxr.free-electrons.com/source/include/linux/bootmem.h?v=4.7#L122
#define alloc_bootmem(x) \
    __alloc_bootmem(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_align(x, align) \
    __alloc_bootmem(x, align, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_nopanic(x) \
    __alloc_bootmem_nopanic(x, SMP_CACHE_BYTES, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages(x) \
    __alloc_bootmem(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)
#define alloc_bootmem_pages_nopanic(x) \
    __alloc_bootmem_nopanic(x, PAGE_SIZE, BOOTMEM_LOW_LIMIT)

5.1.2 從ZONE_DMA區域分配函數

下麵的函數可以從ZONE_DMA中分配記憶體

這些函數的定義在include/linux/bootmem.h

#define alloc_bootmem_low(x) \
    __alloc_bootmem_low(x, SMP_CACHE_BYTES, 0)
#define alloc_bootmem_low_pages_nopanic(x) \
    __alloc_bootmem_low_nopanic(x, PAGE_SIZE, 0)
#define alloc_bootmem_low_pages(x) \
    __alloc_bootmem_low(x, PAGE_SIZE, 0)

5.1.3 函數實現方式

通過分析我們可以看到alloc_bootmem_nopanic的底層實現函數__alloc_bootmem_nopanic實現了一套最基礎的記憶體分配函數, 而___alloc_bootmem函數則通過_alloc_bootmem_nopanic函數實現, 它首先通過_alloc_bootmem_nopanic函數分配記憶體，但是一旦記憶體分配失敗，系統將通過panic("Out of memory")拋出信息，並停止運行, 其他的記憶體分配函數除了都是基於alloc_bootmem_nopanic族的函數, 都是基於__alloc_bootmem的. 那麼所有的函數都是間接的基於___alloc_bootmem_nopanic實現的

static void * __init ___alloc_bootmem(unsigned long size, unsigned long align,
                    unsigned long goal, unsigned long limit)
{
    void *mem = ___alloc_bootmem_nopanic(size, align, goal, limit);

    if (mem)
        return mem;
    /*
     * Whoops, we cannot satisfy the allocation request.
     */
    pr_alert("bootmem alloc of %lu bytes failed!\n", size);
    panic("Out of memory");
    return NULL;
}

那麼我們現在就進入分配函數的核心___alloc_bootmem_node_nopanic, 它定義在mm/nobootmem.c?v=4.7, line 317

void * __init ___alloc_bootmem_node_nopanic(pg_data_t *pgdat,
                unsigned long size, unsigned long align,
                unsigned long goal, unsigned long limit)
{
    void *ptr;

    if (WARN_ON_ONCE(slab_is_available()))
        return kzalloc(size, GFP_NOWAIT);
again:

    /* do not panic in alloc_bootmem_bdata() */
    if (limit && goal + size > limit)
        limit = 0;

    ptr = alloc_bootmem_bdata(pgdat->bdata, size, align, goal, limit);
    if (ptr)
        return ptr;

    ptr = alloc_bootmem_core(size, align, goal, limit);
    if (ptr)
        return ptr;

    if (goal) {
        goal = 0;
        goto again;
    }

    return NULL;
}

我們可以看到UMA下底層的分配函數_alloc_bootmem_nopanic與NUMA下的函數_alloc_bootmem_node_nopanic實現方式基本類似. 參數也基本相同

5.2 __alloc_memory_core進行記憶體分配

__alloc_memory_core函數的功能相對而言很廣泛(在啟動期間不需要太高的效率), 該函數基於最先適配演算法, 但是該分配器不僅可以分配整個記憶體頁, 還能分配頁的一部分. 它遍歷所有的bootmem list然後找到一個合適的記憶體區域, 然後通過 alloc_bootmem_bdata來完成分配

該函數主要執行如下操作

• list_for_each_entry從goal開始掃描為圖, 查找滿足分配請求的空閑記憶體區

• 然後通過alloc_bootmem_bdata完成記憶體的分配
  1. 如果目標頁緊接著上一次分配的頁即last_end_off, 則內核會判斷所需的記憶體(包括對齊數據所需的記憶體)是否能夠在上一頁分配或者從上一頁開始分配
  2. 新分配的頁在點陣圖中對應位置設置為1,, 如果該頁未完全分配, 則相應的偏移量保存在bootmem_data->last_end_off中; 否則, 該值設為0

6 bootmem釋放記憶體

內核提供了free_bootmem函數來釋放記憶體

它需要兩個參數：需要釋放的記憶體區的起始地址和長度。不出意外，NUMA系統上等價函數的名稱為free_bootmem_node，它需要一個額外的參數來指定結點

//  http://lxr.free-electrons.com/source/mm/bootmem.c?v=4.7#L422
void free_bootmem(unsigned long addr, unsigned long size);
void free_bootmem_node(pg_data_t *pgdat, unsigned long addr, unsigned long size);

7 停用bootmem

在系統初始化進行到伙伴系統分配器能夠承擔記憶體管理的責任後，必須停用bootmem分配器，畢竟不能同時用兩個分配器管理記憶體。在UMA和NUMA系統上，停用是由free_all_bootmem完成。在伙伴系統建立之後，特定於體繫結構的初始化代碼需要調用這個函數

首先掃描bootmem分配器的頁點陣圖，釋放每個未用的頁。到伙伴系統的介面是__free_pages_bootmem函數，該函數對每個空閑頁調用。該函數內部依賴於標準函數__free_page。它使得這些頁併入伙伴系統的數據結構，在其中作為空閑頁管理，可用於分配。

在頁點陣圖已經完全掃描之後，它占據的記憶體空間也必須釋放。此後，只有伙伴系統可用於記憶體分配。