一文讀懂 Linux 內存分配全過程
在《你真的理解內存分配》一文中，我們介紹了 malloc 申請內存的原理，但其在內核怎么實現的呢？所以，本文主要分析在 Linux 內核中對堆內存分配的實現過程。
本文使用 Linux 2.6.32 版本代碼
內存分區(qū)對象
在《你真的理解內存分配》一文中介紹過，Linux 會把進程虛擬內存空間劃分為多個分區(qū)，在 Linux 內核中使用 vm_area_struct 對象來表示，其定義如下：
1struct vm_area_struct {
2 struct mm_struct *vm_mm; // 分區(qū)所屬的內存管理對象
3
4 unsigned long vm_start; // 分區(qū)的開始地址
5 unsigned long vm_end; // 分區(qū)的結束地址
6
7 struct vm_area_struct *vm_next; // 通過這個指針把進程所有的內存分區(qū)連接成一個鏈表
8 ...
9 struct rb_node vm_rb; // 紅黑樹的節(jié)點, 用于保存到內存分區(qū)紅黑樹中
10 ...
11};
我們對 vm_area_struct 對象進行了簡化，只保留了本文需要的字段。
內核就是使用 vm_area_struct 對象來記錄一個內存分區(qū)（如 代碼段、數據段 和 堆空間 等），下面介紹一下 vm_area_struct 對象各個字段的作用：
vm_mm：指定了當前內存分區(qū)所屬的內存管理對象。vm_start：內存分區(qū)的開始地址。vm_end：內存分區(qū)的結束地址。vm_next：通過這個指針把進程中所有的內存分區(qū)連接成一個鏈表。vm_rb：另外，為了快速查找內存分區(qū)，內核還把進程的所有內存分區(qū)保存到一棵紅黑樹中。vm_rb就是紅黑樹的節(jié)點，用于把內存分區(qū)保存到紅黑樹中。
假如進程 A 現在有 4 個內存分區(qū)，它們的范圍如下：
代碼段：00400000 ~ 00401000數據段：00600000 ~ 00601000堆空間：00983000 ~ 009a4000棧空間：7f37ce866000 ~ 7f3fce867000
那么這 4 個內存分區(qū)在內核中的結構如 圖1 所示：
在 圖1 中，我們可以看到有個 mm_struct 的對象，此對象每個進程都持有一個，是進程虛擬內存空間和物理內存空間的管理對象。我們簡單介紹一下這個對象，其定義如下：
1struct mm_struct {
2 struct vm_area_struct *mmap; // 指向由進程內存分區(qū)連接成的鏈表
3 struct rb_root mm_rb; // 內核使用紅黑樹保存進程的所有內存分區(qū), 這個是紅黑樹的根節(jié)點
4 unsigned long start_brk, brk; // 堆空間的開始地址和結束地址
5 ...
6};
我們來介紹下 mm_struct 對象各個字段的作用：
mmap：指向由進程所有內存分區(qū)連接成的鏈表。mm_rb：內核為了加快查找內存分區(qū)的速度，使用了紅黑樹保存所有內存分區(qū)，這個就是紅黑樹的根節(jié)點。start_brk：堆空間的開始內存地址。brk：堆空間的頂部內存地址。
我們來回顧一下進程虛擬內存空間的布局圖，如 圖2 所示：
start_brk 和 brk 字段用來記錄堆空間的范圍， 如 圖2 所示。一般來說，start_brk 是不會變的，而 brk 會隨著分配內存和釋放內存而變化。
虛擬內存分配
在《你真的理解內存分配》一文中說過，調用 malloc 申請內存時，最終會調用 brk 系統(tǒng)調用來從堆空間中分配內存。我們來分析一下 brk 系統(tǒng)調用的實現：
1unsigned long sys_brk(unsigned long brk)
2{
3 unsigned long rlim, retval;
4 unsigned long newbrk, oldbrk;
5 struct mm_struct *mm = current->mm;
6 ...
7 down_write(&mm->mmap_sem); // 對內存管理對象進行上鎖
8 ...
9 // 判斷堆空間的大小是否超出限制, 如果超出限制, 就不進行處理
10 rlim = current->signal->rlim[RLIMIT_DATA].rlim_cur;
11 if (rlim < RLIM_INFINITY
12 && (brk - mm->start_brk) + (mm->end_data - mm->start_data) > rlim)
13 goto out;
14
15 newbrk = PAGE_ALIGN(brk); // 新的brk值
16 oldbrk = PAGE_ALIGN(mm->brk); // 舊的brk值
17 if (oldbrk == newbrk) // 如果新舊的位置都一樣, 就不需要進行處理
18 goto set_brk;
19 ...
20 // 調用 do_brk 函數進行下一步處理
21 if (do_brk(oldbrk, newbrk-oldbrk) != oldbrk)
22 goto out;
23
24set_brk:
25 mm->brk = brk; // 設置堆空間的頂部位置（brk指針）
26out:
27 retval = mm->brk;
28 up_write(&mm->mmap_sem);
29 return retval;
30}
總結上面的代碼，主要有以下幾個步驟：
1、判斷堆空間的大小是否超出限制，如果超出限制，就不作任何處理，直接返回舊的
brk值。2、如果新的
brk值跟舊的brk值一致，那么也不用作任何處理。3、如果新的
brk值發(fā)生變化，那么就調用do_brk函數進行下一步處理。4、設置進程的
brk指針（堆空間頂部）為新的brk的值。
我們看到第 3 步調用了 do_brk 函數來處理，do_brk 函數的實現有點小復雜，所以這里介紹一下大概處理流程：
通過堆空間的起始地址
start_brk從進程內存分區(qū)紅黑樹中找到其對應的內存分區(qū)對象（也就是vm_area_struct）。把堆空間的內存分區(qū)對象的
vm_end字段設置為新的brk值。
至此，brk 系統(tǒng)調用的工作就完成了（上面沒有分析釋放內存的情況），總結來說，brk 系統(tǒng)調用的工作主要有兩部分：
把進程的
brk指針設置為新的brk值。把堆空間的內存分區(qū)對象的
vm_end字段設置為新的brk值。
物理內存分配
從上面的分析知道，brk 系統(tǒng)調用申請的是 虛擬內存，但存儲數據只能使用 物理內存。所以，虛擬內存必須映射到物理內存才能被使用。
那么什么時候才進行內存映射呢？
在《你真的理解內存分配》一文中介紹過，當對沒有映射的虛擬內存地址進行讀寫操作時，CPU 將會觸發(fā) 缺頁異常。內核接收到 缺頁異常 后， 會調用 do_page_fault 函數進行修復。
我們來分析一下 do_page_fault 函數的實現（精簡后）：
1void do_page_fault(struct pt_regs *regs, unsigned long error_code)
2{
3 struct vm_area_struct *vma;
4 struct task_struct *tsk;
5 unsigned long address;
6 struct mm_struct *mm;
7 int write;
8 int fault;
9
10 tsk = current;
11 mm = tsk->mm;
12
13 address = read_cr2(); // 獲取導致頁缺失異常的虛擬內存地址
14 ...
15 vma = find_vma(mm, address); // 通過虛擬內存地址從進程內存分區(qū)中查找對應的內存分區(qū)對象
16 ...
17 if (likely(vma->vm_start <= address)) // 如果找到內存分區(qū)對象
18 goto good_area;
19 ...
20
21good_area:
22 write = error_code & PF_WRITE;
23 ...
24 // 調用 handle_mm_fault 函數對虛擬內存地址進行映射操作
25 fault = handle_mm_fault(mm, vma, address, write ? FAULT_FLAG_WRITE : 0);
26 ...
27}
do_page_fault 函數主要完成以下操作：
獲取導致頁缺失異常的虛擬內存地址，保存到
address變量中。調用
find_vma函數從進程內存分區(qū)中查找異常的虛擬內存地址對應的內存分區(qū)對象。如果找到內存分區(qū)對象，那么調用
handle_mm_fault函數對虛擬內存地址進行映射操作。
從上面的分析可知，對虛擬內存進行映射操作是通過 handle_mm_fault 函數完成的，而 handle_mm_fault 函數的主要工作就是完成對進程 頁表 的填充。
我們通過 圖3 來理解內存映射的原理，可以參考文章《一文讀懂 HugePages的原理》：
下面我們來分析一下 handle_mm_fault 的實現，代碼如下：
1int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct *vma,
2 unsigned long address, unsigned int flags)
3{
4 pgd_t *pgd; // 頁全局目錄項
5 pud_t *pud; // 頁上級目錄項
6 pmd_t *pmd; // 頁中間目錄項
7 pte_t *pte; // 頁表項
8 ...
9 pgd = pgd_offset(mm, address); // 獲取虛擬內存地址對應的頁全局目錄項
10 pud = pud_alloc(mm, pgd, address); // 獲取虛擬內存地址對應的頁上級目錄項
11 ...
12 pmd = pmd_alloc(mm, pud, address); // 獲取虛擬內存地址對應的頁中間目錄項
13 ...
14 pte = pte_alloc_map(mm, pmd, address); // 獲取虛擬內存地址對應的頁表項
15 ...
16 // 對頁表項進行映射
17 return handle_pte_fault(mm, vma, address, pte, pmd, flags);
18}
handle_mm_fault 函數主要對每一級的頁表進行映射（對照 圖3 就容易理解），最終調用 handle_pte_fault 函數對 頁表項 進行映射。
我們繼續(xù)來分析 handle_pte_fault 函數的實現，代碼如下：
1static inline int
2handle_pte_fault(struct mm_struct *mm, struct vm_area_struct *vma,
3 unsigned long address, pte_t *pte, pmd_t *pmd,
4 unsigned int flags)
5{
6 pte_t entry;
7
8 entry = *pte;
9
10 if (!pte_present(entry)) { // 還沒有映射到物理內存
11 if (pte_none(entry)) {
12 ...
13 // 調用 do_anonymous_page 函數進行匿名頁映射（堆空間就是使用匿名頁）
14 return do_anonymous_page(mm, vma, address, pte, pmd, flags);
15 }
16 ...
17 }
18 ...
19}
上面代碼簡化了很多與本文無關的邏輯。從上面代碼可以看出，handle_pte_fault 函數最終會調用 do_anonymous_page 來完成內存映射操作，我們接著來分析下 do_anonymous_page 函數的實現：
1static int
2do_anonymous_page(struct mm_struct *mm, struct vm_area_struct *vma,
3 unsigned long address, pte_t *page_table, pmd_t *pmd,
4 unsigned int flags)
5{
6 struct page *page;
7 spinlock_t *ptl;
8 pte_t entry;
9
10 if (!(flags & FAULT_FLAG_WRITE)) { // 如果是讀操作導致的異常
11 // 使用 `零頁` 進行映射
12 entry = pte_mkspecial(pfn_pte(my_zero_pfn(address), vma->vm_page_prot));
13 ...
14 goto setpte;
15 }
16 ...
17 // 如果是寫操作導致的異常
18 // 申請一塊新的物理內存頁
19 page = alloc_zeroed_user_highpage_movable(vma, address);
20 ...
21 // 根據物理內存頁的地址生成映射關系
22 entry = mk_pte(page, vma->vm_page_prot);
23 if (vma->vm_flags & VM_WRITE)
24 entry = pte_mkwrite(pte_mkdirty(entry));
25 ...
26setpte:
27 set_pte_at(mm, address, page_table, entry); // 設置頁表項為新的映射關系
28 ...
29 return 0;
30}
do_anonymous_page 函數的實現比較有趣，它會根據 缺頁異常 是由讀操作還是寫操作導致的，分為兩個不同的處理邏輯，如下：
如果是讀操作導致的，那么將會使用
零頁進行映射（零頁是 Linux 內核中一個比較特殊的內存頁，所有讀操作引起的缺頁異常都會指向此頁，從而可以減少物理內存的消耗），并且設置其為只讀（因為零頁是不能進行寫操作）。如果下次對此頁進行寫操作，將會觸發(fā)寫操作的缺頁異常，從而進入下面步驟。如果是寫操作導致的，就申請一塊新的物理內存頁，然后根據物理內存頁的地址生成映射關系，再對頁表項進行填充（映射）。
總結
本文主要介紹了 Linux 內存分配的整個過程，當然只是介紹從堆空間分配的內存的過程。Linux 分配內存的方式還有很多，比如 mmap、HugePages 等，有興趣的可以查閱相關的資料和書籍。
