---
title: Virtual Memory (虛擬記憶體) - 從零開始的開源地下城
tags: Linux, Linux讀書會, Kernel, 從零開始的開源地下城, COMBO-tw
description: 介紹與Linux Kernel相關基本知識
lang: zh-Hant
GA: G-2QY5YFX2BV
---
# Virtual Memory (虛擬記憶體)
###### tags: `Linux`
## 目錄
[TOC]

## Topic
了解 Linux 記憶體管理機制
了解 Linux 分配機制
了解 Linux 記憶體階層

## Linux User/Kernel Memory Split
### 圖解 Memory 分配

---

### 可愛的小企鵝幫我們將 Memory 分成兩個部分
* Kernel Mode Space - Linux Kernel 運行所使用的記憶體區塊
* User Mode Space - User Space 程式所需要使用的記憶體區塊

### 一般在 32位元的 Kernel 有幾種 Memory Split 方案：
* 3G/1G (User/Kernel) - CONFIG_VMSPLIT_3G (最常見)
* 2G/2G (User/Kernel) - CONFIG_VMSPLIT_2G
* 1G/3G (User/Kernel) - CONFIG_VMSPLIT_1G

### User Mode Momory 又區分為以下的部分：
* Stack
* 堆疊區段（stack segment）用於儲存函數的區域變數，以及各種函數呼叫時需要儲存的資訊（例如函數返回的記憶體位址還有呼叫者函數的狀態等），每一次的函數呼叫就會在堆疊區段建立一個 stack frame，儲存該次呼叫的所有變數與狀態，這樣一來同一個函數重複被呼叫時就會有不同的 stack frame，不會互相干擾，遞迴函數就是透過這樣的機制來執行的。
* Heap
* heap 區段的記憶體空間用於儲存動態配置的變數，例如 C 語言的 malloc 以及 C++ 的 new 所建立的變數都是儲存於此。
* 堆疊區段一般的狀況會從高記憶體位址往低記憶體位址成長，而 heap 剛好從對面以相反的方向成長。
* bss Segment
* 未初始化資料區段（uninitialized data segment）又稱為 bss 區段（這個名稱的起源來自於古老的組譯器，代表 block started by symbol）是儲存尚未被初始化的靜態變數，而這些變數在程式執行之前會被系統初始化為 0 或是 null。
* data Segment
* 初始化資料區段（initialized data segment）儲存的是一些已經初始化的靜態變數，例如有經過初始化的 C 語言的全域變數（global variables）以及靜態變數（static variables）都是儲存於此處。
* 這個區段的變數又可分為唯讀區域（read-only area）以及可讀寫區域（read-write area），可讀寫區域用於存放一般變數，其資料會隨著程式的執行而改變，而唯讀區域則是存放固定的常數。
* text Segment
* 文字區段（text segment）也稱為程式碼區段（code segment），這裡存放的是可執行的 CPU 指令（instructions）。
* 這個區段通常位於 heap 或 stack 之後，避免因 heap 或 stack 溢位而覆寫 CPU 指令。
* Memory Mapping Segment
* 通常會在"尚未使用區域"內找一塊連續記憶體空間來使用，其存放的為該程式所引用的函式庫（Library），ex. `/lib/libc.so`，以便該程式在執行的過程中可以使用。
* system
* system 區段用於儲存一些命令列參數與環境變數，這部分會跟系統有關。

### Kernel Mode Momory 又區分為以下的部分：
* Vector - vector : 如果 CPU 支援向量重新指向，則 CPU 中斷向量將會被映射到這個區間
* FixMap - fixmap : 固定的映射區域，用於分配大的 Page
* DMA - <font color='red'>**x86 架構下才會有**</font>
* Persistent Mapping – pkmap : <font color='red'>**ARM 架構下才有**</font>
* Vmalloc - vmalloc : 虛擬記憶體分配申請的地址區域範圍
* Low Memory – lowmem : 記憶體低水位，不夠時會觸發記憶體回收
* Kernel Image -
* .text Segment
* .init Segment
* .data Segment
* .bss Segment
* Modules – Put on the User Space

## Device Tree Reserved-memory 說明
在 Device Tree 中，有一個區塊在宣告 Reserved-memory，用於保留某個記憶體區段供裝置使用，其基本格式範例如下：

/ {
    ...
	reserved-memory {
		#address-cells = <1>;
		#size-cells = <1>;
		ranges;

		/* global autoconfigured region for contiguous allocations */
		linux,cma {
			compatible = "shared-dma-pool";
			reusable;
			size = <0x4000000>;
			alignment = <0x2000>;
			linux,cma-default;
		};

		display_reserved: framebuffer@78000000 {
			reg = <0x78000000 0x800000>;
		};

		multimedia_reserved: multimedia@77000000 {
			compatible = "acme,multimedia-memory";
			reg = <0x77000000 0x4000000>;
		};
	};
    ...
};

/reserved-memory 節點資訊：
* `#address-cells`, `#size-cells` (必要的) : 標準定義，且必須要有值。
* `ranges` (必要的) : 標準定義，且必須要為空值。

/reserved-memory/ 子節點，每個子節點可指定保留一個至多個特定範圍的記憶體空間，可透過 `reg` 屬性來進行指定範圍的保留，也可透過 `size` 屬性進行動態分配的區域保留，名稱的宣告通常依據其用途來命名，如`framebuffer` or `dma-pool`，若節點為靜態分配，則應將該節點之 Address 置於名稱後，如`<nodename>@<address>`，其包含資訊有資訊：
* 配置的特性：
* 靜態配置，如：`reg`
* 動態配置，如：
* `size` : 必要，長度格式基於父節點之 `#size-cells`，以 Bytes 為單位去宣告保留的記憶體大小。
* `alignment` : 選用，長度格式基於父節點之 `#size-cells`，分配需對其的 Address 的邊界。
* `alloc-ranges` : 選用，屬性編碼陣列，其為 `Address` 與 `length` 的配對 (Pair)，可從中指定分配的記憶體區域。
:::danger
若 `reg` 與 `size` 同時使用，則將以 `reg` 為優先，忽略 `size`。
:::

## Budding System
夥伴系統，為 Linux 針對小的記憶體需求而設計的機制，因應而生的衍伸機制為 Slub, Slab, Slob，其概念為如組合肉一般，將許多細小的使用需求黏成同一塊來使用，因此該機制會向 Kernel 註冊一塊固定大小的 Pages Area，在將該 Area 分割後供系統小塊小塊的去配置 (Alloc)。
### 為了解決分配 (Alloc) 記憶體時，需要全部走訪一次，而 Buddy System 剛好能夠解決此問題：
* 內部保存一些 2 的 N 次方空間的記憶體片段(如上圖一)，已供分配時使用
* 舉個例子：
* 如果要分配一塊 3 Pages 的空間，則去找 4 Pages (Order 2) 來用
* 此時會發現我們多要了 1 Page，而該 Page 會被還回去
* 而被還回去的 Page 之後可以給 Order 0 使用
### Slub/Slab/Slob 簡介
在此說明目前為止的 Linux Kernel 所發展出來的 Allocator (分配器)，目前也有許多研究對於 Allocator 進行設計，但沒有所謂可以完全取代的最佳 Allocator，因本讀書會面相對象為較為初階的學習者，故在此沒有預計讓學習者進行此功能之修改。
* SLOB : K&R Allocator
* 最簡單的 Allocator
* 盡可能緊湊
* 效能要點：
* 全部的配置都可以 Reclamable (可回收)
* 效能部分因為 Global Locking (全域鎖定，會有資源競爭之問題)，故在多核時會整個崩壞
* SLAB : Solaris Type Allocator
* 較為複雜的資料結構
* 透過類似組合肉的方式把一小塊 Free 黏起來使用
* Cache Friendly & Benchmark Friendly
* 效能要點：
* 因為資料結構的關係，開始有一些 Unreclamable 的部分
* 因為此時有考慮到多核，效能上沒 SLOB 那麼嚴重
* SLUB : Unqueued Allocator
* 更易於 Debug
* 較佳的碎片整理能力
* Execution Time Friendly
* 目前為 Linux 預設的 Slab Allocator
* 效能要點：
* 為了解決更多問題， 所以可調整的設定多很多，故效能面比 SLAB 好得多

## Page Fault (分頁錯誤)
Page Fault 字面上看起來為 "分頁錯誤"，實際上其用途為 Page 使用時的 Handler 處理機制。
在實際使用某個記憶體區域的資料之前，實體記憶體空間是沒有建立起映射的關係的。故要使用時會去取得以下資訊：
* 在哪個地址發生的
* 發生該異常的原因
* 發生時的暫存器值

**常見的 Kernel Panic 發生時，其 Call Trace 也是在 Page fault Handler 中被記錄。**

Page Fault 分為以下幾類：
* Minor (又稱軟性分頁錯誤)：相關的 Page 已經被載入進記憶體，但是沒有向 MMU 註冊的情況。所以作業系統只需要在 MMU 中註冊相關 Page 對應的實體位址即可處理完成。
* Major (又稱硬性分頁錯誤)：與 Minor Page Fault 不同，Major Page Fault 是指相關的 Page 在 Page Fault 發生時未被載入進記憶體的情況。其 Overhead 非常大，因為需要頻繁的使用到磁碟等慢速裝置。
這時若發生 Major Page Fault 作業系統將需要做以下的事情：
1. 尋找到一個空閒的 Page。或者把另外一個使用中的 Page 寫回到磁碟上（如果其在最後一次寫入後發生了變化的話），並註銷在 MMU 內的記錄。
3. 將資料讀入被選定的 Page 中。
4. 向 MMU 註冊該 Page。
* Invalid (無效分頁錯誤)：當程式存取的虛擬位址是不存在於虛擬位址空間內的時候，則會發生無效分頁錯誤。一般來說這是個軟體問題，但是也不排除硬體可能，比如因為記憶體故障而損壞了一個正確的指標。

## 記憶體階層
### 四層頁表結構設計
　　在 Linux 當中使用了四層頁表的結構作為虛擬記憶體轉換的階層管理 (在 4.11 之後引入了五層的頁表結構，也就是 PGD、P4D、PUD、PMD、PTE)，目的是為了能夠表達 64 位元的實體記憶體位址映射，使用最低的 12-Bits 作為 Page 的 Offset，換句話說這也是每個 Page 的大小，也就是 4KB。剩下的 36-Bits 會分成四個階層，每個階層 9-Bits，所有的虛擬位址都能透過該多層頁表進行查詢，透過查詢可得到其對應的實體位址。因此不管實體記憶體多大，虛擬記憶體位址長度不變，另外若是將 Offset 調小，將可能會導致四層頁表結構變成五層，這還會導致記憶體訪問有額外的開銷，還會增加每個程式中頁表項目所佔用的記憶體大小。
　　此時會發現 12-Bits + 36-Bits 也才 48-Bits，不是應該是 64-Bits 嗎? 實際上在不同架構上的記憶體定址能力會因為 CPU 設計有所不同，例如在 ARM Cortex-R82 雖然是 64 位元處理器，但其記憶體定址的能力卻只有 40-Bits；就 Armv8-A 而言，雖然是 64 位元架構，但並不是全部採用這架構的處理器的記憶體定址都是 64 位元，以實體記憶體定址而言，Arm Cortex-A 系列處理器是 40 位元或 44 位元（最大是 48 位元，Armv8.2-A 可延伸到 52 位元），虛擬記憶體定址則是 48 位元（可選用 52 位元），而若具備 52 位元的記憶體定址，可支援到 4PB 記憶體容量；即使是伺服器等級的產品，在實作上，也大多是支援 40 位元到 52 位元之間的記憶體定址。

## 本章節練習與反思
* 請筆記出 Kernel 在那些時候下會觸發 Page Fault。
* 請筆記出各記憶體頁表階層轉換函式與其原理說明。

## 參考資料
* https://www.jianshu.com/p/f2de1a1a51a7
* https://learnlinuxconcepts.blogspot.com/2014/03/memory-layout-of-userspace-c-program.html
* https://books.google.com.tw/books?id=yRogEAAAQBAJ&pg=PA346&lpg=PA346&dq=get+vectors_base+variable&source=bl&ots=HgrjahypJN&sig=ACfU3U0euApTbjWggxoD9B5WIx5PUt5quQ&hl=zh-TW&sa=X&ved=2ahUKEwjvtK69sbTvAhWPHKYKHZILCrYQ6AEwAHoECAUQAw#v=onepage&q=get%20vectors_base%20variable&f=false
* https://hackmd.io/@sysprog/linux-memory?type=view
* https://www.jollen.org/blog/2007/01/no-zero-initialized-in-bss.html
* https://blog.gtwang.org/programming/memory-layout-of-c-program/
* https://events.static.linuxfound.org/sites/events/files/slides/slaballocators.pdf
* https://www.youtube.com/watch?v=MTfROZ3cTFQ
* https://loda.hala01.com/2017/06/androidlinux-kernel.html
* https://zh.wikipedia.org/wiki/%E9%A1%B5%E7%BC%BA%E5%A4%B1
* https://www.twblogs.net/a/5b7c4ca12b71770a43da5338
* https://www.kernel.org/doc/Documentation/devicetree/bindings/reserved-memory/reserved-memory.txt
* https://iter01.com/510311.html
* https://iter01.com/510310.html
* https://www.ithome.com.tw/tech/140240