---
tags: LINUX KERNEL, LKI
---
# [Linux 核心設計](https://beta.hackfoldr.org/linux/): 記憶體管理
Copyright (**慣C**) 2019 [宅色夫](http://wiki.csie.ncku.edu.tw/User/jserv)
==[直播錄影 (一)](https://www.youtube.com/watch?v=kY3g2r03erk&feature=youtu.be)==
==[直播錄影 (二)](https://www.youtube.com/watch?v=0oABzHrZDPY&feature=youtu.be)==
==[直播錄影 (三)](https://youtu.be/9Kj7TBrvP-8)==
> 身處[事件視界](https://pansci.asia/archives/tag/%E4%BA%8B%E4%BB%B6%E8%A6%96%E7%95%8C)的企鵝
## 目標設定
記憶體管理是 Linux 核心裡頭最複雜的部分，涉及到對計算機結構、slob/slab/slub 記憶體配置器、行程和執行檔樣貌、虛擬記憶體對應的例外處理、記憶體映射, UMA vs. NUMA 等等議題。
在本講座中，我們預計探討:
- 虛擬記憶體原理: MMU, TLB, cache, page fault
- Lazy Allocation 的精神和具體表現
- Linux 核心配置記憶體的策略 (考量到不同計算機架構)
- vmalloc, kmalloc, kmem_caches, shared memory 彼此的關聯
- swap 運作機制和現代電腦的使用狀況
- Overcommit
- 觀察 Linux 核心的記憶體管理
- 邁向 huge memory
## 從科普觀點談起
[學習金字塔](http://chiuphysics.cgu.edu.tw/yun-ju/cguweb/scilearn/learning/conelearning/homeconelearning.htm)
> 改編自 [五分鐘徹底搞懂你一直沒明白的 Linux 記憶體管理](https://zhuanlan.zhihu.com/p/32952524)
對於記憶體的部分需要知道：
* 地址映射
* 記憶體管理的方式
* Page fault
以 process 來看，記憶體分為核心模式和使用者模式兩部分，經典比例如下：
從使用者模式到核心模式可經由系統呼叫和中斷來達成。使用者模式的記憶體被劃分為不同的區域用於不同的目的：
當然核心模式也不會無差別地使用，所以，其劃分如下：
下面來仔細看這些記憶體是如何管理的。
- [ ] 定址空間
在 Linux 內部的記憶體地址映射過程為邏輯地址 –> 線性地址–> 實體地址 (PA)，實體地址最簡單：在匯流排中傳輸的數位信號，而線性地址和邏輯地址所表示的意涵則是種轉換規則，線性地址規則如下：
這部分由 MMU 完成，其中在 IA32 架構下，涉及到主要的暫存器有 CR0, CR3。機器指令中出現的是邏輯地址，邏輯地址規則如下：
在 Linux 中的邏輯地址對應於線性地址，也就是說 Intel 為了相容過往架構，把硬體設計搞得很複雜，Linux 核心的實作則予以簡化，並且在支援其他處理器架構時，儘量保持該原則。
記憶體管理的方式
在系統啟動之際會去探測記憶體的大小和情況，在建立複雜的結構前，需要透過簡化的模式來管理這些記憶體，這即是 [bootmem](https://www.kernel.org/doc/gorman/html/understand/understand022.html)，簡單來說就是 bitmap，不過其中也有一些優化的思路。
bootmem 再怎麼優化，效率都不高，在要分配記憶體的時候畢竟是要去走訪全部，[buddy system](https://en.wikipedia.org/wiki/Buddy_memory_allocation) 剛好能解決這個問題：在內部保存一些 2 的 N 次方空間記憶體片段，如果要分配 3 pages，去 4 pages 的列表裡面取一個，分配 3 個之後將剩下的 1 個放回去，記憶體釋放的過程剛好是一個反向過程，如下圖:
可見 0, 4, 5, 6, 7 都是正在使用的，那麼 1, 2 被釋放之際，他們會合併嗎？
```c
static inline unsigned long
__find_buddy_pfn(unsigned long page_pfn, unsigned int order)
{
return page_pfn ^ (1 << order); // 更新最高位元，0～1 互換
}
```
從上面這段程式碼中可見: 0, 1 是 buddy，而 2, 3 是 buddy，雖然1, 2 相鄰，但他們不是。記憶體碎片是系統執行的大敵，buddy system 機制可以在一定程度上防止碎片。另外，我們可使用 `$ cat /proc/buddyinfo` 得知各 order 中的空閒的 pages 數。
在許多處理器架構上，buddy system 每次分配記憶體都以 page (4KB）為單位，但系統執行時絕大部分的資料結構都是很小的，為一個小物件分配 4KB 顯然不划算。Linux 中使用 slab 來解決小物件的分配：
slab 向 buddy system 去「批發」一些記憶體，加工切塊以後「零售」出去。隨著大規模多核處理器和 NUMA 系統的廣泛應用，slab 終於暴露出其不足：
* 複雜的隊列管理
* 管理資料和隊列儲存開銷較大
* 長時間運行 partial 隊列可能會非常長
* 對 NUMA 支持非常複雜
為此，核心開發者引入 slub：改造 page 結構，削減 slab 管理結構的開銷、每個 CPU 都有一個本地活動的 slab (`kmem_cache_cpu`) 等等。對於小型的嵌入式系統存在一個 slab 模擬層 slob，在這種系統中它更有優勢。
小記憶體的問題算是解決了，但還有一個大記憶體的問題：用 buddy system 分配 10 x 4KB 的資料時，會去 16 x 4KB 的空閒列表裡面去找 (確保得到的實體記憶體才會是連續的)，但很可能系統裡面有記憶體，但是 buddy 系統分配不出來，因為他們被分割成小的片段。那麼，`vmalloc` 就要用這些碎片來拼湊出一個大記憶體，相當於收集一些「碎肉渣」，以蛋白黏合成一個成品後「出售」這樣的「[組合肉](https://zh.wikipedia.org/zh-tw/%E7%B5%84%E5%90%88%E8%82%89)」：
相較之前的記憶體採用直接映射的模式，我們此刻首度感受到分頁管理的存在。另外，對於 High Memory Area，提供 `kmap` 為 page 分配一個線性地址。
process 由不同長度的 section 組成：text, 動態函式庫、全域變數/符號和動態產生資料的 stack/heap 等等。在 Linux 中為每個 process 管理了一套虛擬定址空間：
在呼叫 `malloc` 後，系統不會立即佔用宣稱那麼大的實體記憶體空間，而僅是維護上面的虛擬定址空間而已，只有在真正需要的時候才分配實體記憶體，這就是 CoW（Copy-on-Write) 策略，而實體分配的過程就是最複雜的 page fault 處理。
- [ ] Page fault
在實際需要某個虛擬記憶體區域的資料前，和實體記憶體之間的映射關係不會建立。如果 process 存取的虛擬定址空間部分尚未與 page frame 有所關聯，處理器自動引發一個 page fault。在核心處理 page fault 之際，Linux 可取得的資訊如下:
1. `cr2`: 存取到線性地址
2. `err_code`: 異常發生時由控制單元推入 stack 中，表示發生異常的原因
3. `regs`: 發生異常當下的暫存器數值
處理的流程如下：
發生 page fault 時，可能因為不常使用而被 swap 到主記憶體以外的儲存設備中。
如果記憶體是透過 mmap 映射的手段取得，那麼在讀、寫對應記憶體時也會觸發 page fault。
## slub/slab/slob
* SLOB: K&R allocator (1991-1999)
- as compact as possible
- simply manages list of free objects within the space of the free objects
- allocation requires traversing the list to find an object with sufficient size.
* If nothing is found, the page allocator is used to increase the size of the heap.
- rapid fragmentation of memory
- [Linux v6.4 捨棄 slob](https://www.phoronix.com/news/Linux-6.4-Looks-To-Drop-SLOB)
* SLAB: Solaris type allocator (1999-2008)
- 依據 Sun Microsystems 任職的 [Jeff Bonwick](https://en.wikipedia.org/wiki/Jeff_Bonwick) 所撰寫的論文 [Extending the Slab Allocator to Many CPUs and Arbitrary Resources](http://static.usenix.org/event/usenix01/full_papers/bonwick/bonwick.pdf)，自 Linux 核心 2.2 版之後實作
- as cache friendly as possible. benchmark friendly
- queues to track cache hotness
- queues per CPU and per node
- queues for each remote node (alien cache)
- object based memory polices and interleaving
* SLUB: Unqueued allocator (2008-)
- simple and instruction cost counts. superior debugging.
- defragmentation. execution time friendly
- enough for queueing
- slabinfo
[Slab allocators in the Linux Kernel: SLAB, SLOB, SLUB](https://events.static.linuxfound.org/sites/events/files/slides/slaballocators.pdf)
Linux 核心的組態
> config DEBUG_SLAB
> bool "Debug slab memory allocations"
> depends on DEBUG_KERNEL && SLAB && !KMEMCHECK
> help
> Say Y here to have the kernel do limited verification on memory
> allocation as well as poisoning memory on free to catch use of freed memory.
> This can make kmalloc/kfree-intensive workloads much slower.
Poisoning 是個常見分析記憶體的手法，一如「摻毒」到特定的對象，使其行為遲至，從而追蹤行為和劑量。使用範例:
```
[47744.480000] TRACE kmalloc-128 alloc 0x83df8300 inuse=16 fp=0x (null)
[47744.480000] Call Trace:
[47744.480000] [<8027c4b4>] dump_stack+0x8/0x34
[47744.480000] [<8027d5fc>] alloc_debug_processing+0xf8/0x17c
[47744.480000] [<8027decc>] __slab_alloc.constprop.65+0x2e0/0x350
[47744.480000] [<800df2c0>] __kmalloc+0x98/0x148
[47744.480000] [<8308ad74>] amalloc_private+0x38/0x13c [asf]
[47744.480000] [<82aba2a8>] osif_forward_mgmt_to_app+0xa0/0x280 [umac]
[47744.480000] [<82aba478>] osif_forward_mgmt_to_app+0x270/0x280 [umac]
```
* [SLUB DEBUG原理](http://www.wowotech.net/memory_management/427.html)
slub 是目前 Linux 核心預設的 slab allocator
* 所謂的 slab 是從 buddy system 要一個 page 過來，之後依照不同的 kmalloc 所丟入不同的 object size (例如 kmalloc-96, kmalloc-192, kmalloc-8, kmalloc-32 等等)，把 page 內部切成 object size 為單位的格式
* 之後 return freelist 的第一個 free 的 object 給 kmalloc 的呼叫者
* 其中，初始化過後，每個 object 的頭 8 個 bytes 儲存 freepointer 指向下一個可得的 available object size。用 linked list 的方式串起整個 slab(page) 內部所有空的 objects
slob 比 slab 配置器程式碼更精簡，但比 slab 更容易產生記憶體碎片問題，僅用於小型系統，特別是嵌入式系統。
* [slob: introduce the SLOB allocator](https://lwn.net/Articles/157944/)
```
/proc/meminfo:
SLAB SLOB delta
MemTotal: 27964 kB 27980 kB +16 kB
MemFree: 24596 kB 25092 kB +496 kB
```
slob 配置器共只有三條 partial free list，每個 partial free list 都由已被分配給 slob 的 page 單元構成:
* `free_slab_small` 只配置小於 256 位元組的 block;
* `free_slab_medium` 只配置小於 1024 位元組的 block;
* `free_slab_large` 只分配小於 PAGE_SIZE 的 block;
若透過 slob 配置器去配置大於一個 page 的物件，則 slob 直接呼叫 zone mem allocator (alloc_pages) 來配置連續頁 (compound pages) 並返回。並修改相應首 page 結構體的 flags 欄位，private 欄位中儲存該 block 大小。
參照 [Linux Memory Management](https://hackmd.io/@VIRqdo35SvekIiH4p76B7g/rJ-UJ_uWx)
取自 Donald E. Porter 教授的 [CSE 506: Operating Systems](http://www.cs.unc.edu/~porter/courses/cse506/) 教材
- [ ] [The Art and Science of Memory Allocation](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/malloc.pdf)
* [Hoard](http://hoard.org/) is a fast, scalable, and memory-efficient memory allocator that can speed up your applications.
* 論文: [Hoard: A Scalable Memory Allocator for Multithreaded Applications](https://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf)
* [mimalloc](https://github.com/microsoft/mimalloc): Microsoft Research 開發的完全 lock-free 記憶體管理器
* 論文: [Mimalloc: Free List Sharding in Action](https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf)
- [ ] [The Page Cache](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/page-cache.pdf)
- [ ] [Page Frame Reclaiming](http://www.cs.unc.edu/~porter/courses/cse506/s16/slides/pfra.pdf)
- [ ] 浙江大學教材 [Virtual Memory and Linux](http://malgenomeproject.org/os2018fall/10_Linux_virtual_memory.pdf)
- [ ] [Deterministic Memory Allocation for Mission-Critical Linux](https://static.sched.com/hosted_files/ossna2017/cf/Deterministic%20Memory%20Allocation%20for%20Mission-Critical%20Linux.pdf)
## kmalloc vs. vmalloc
* vmalloc()
- Obtains a physically discontiguous block
- Unsuitable for DMA on some platforms
* 一般策略
* chunk < 128 KiB → kmalloc()
* chunk > 128 KiB → vmalloc()
## 20 years of Linux Virtual Memory
* [簡報](https://www.slideshare.net/ennael/kernel-recipes-2017-20-years-of-linux-virtual-memory-andrea-arcangeli) / [錄影](https://www.youtube.com/watch?v=pZghXbeCH5s)
設定 overcommit_memory 為 `1`，可執行：
```shell
# echo 1 > /proc/sys/vm/overcommit_memory
```
有三種可用值：
* `0`: heuristic overcommit (this is the default)
* `1`: always overcommit, never check
* `2`: always check, never overcommit
參照:
* [理解 Linux 的 memory overcommit](http://linuxperf.com/?p=102)
* [What is Overcommit? And why is it bad?](https://www.etalabs.net/overcommit.html)
## 追蹤機制
* 核心選項
* `CONFIG_FUNCTION_TRACER=y`
* `CONFIG_DYNAMIC_FTRACE=y`
* Ftrace 資訊: `/sys/kernel/debug/tracing/` 目錄
* 核心參數
* trace_event=kmem:kmalloc,
* kmem:kmalloc_node,
* kmem:kfree
* 設定 Ftrace 事件
```shell
$ cd /sys/kernel/debug/tracing
$ echo "kmem:kmalloc" > set_event
$ echo "kmem:kmalloc_node" >> set_event
$ echo "kmem:kfree" >> set_event
```
* 觸發 Ftrace
```shell
$ echo "1" > tracing_on
```
* 抑制 Ftrace
```shell
$ echo "0" > tracing_on
```
示範:
```
# TASK-PID CPU# TIMESTAMP FUNCTION
# | | | | |
linuxrc-1 [000] 0.310577: kmalloc: \
# caller address
call_site=c00a1198 \
# obtained pointer
ptr=de239600
# requested and obtained bytes
bytes_req=29 bytes_alloc=64
```
64 - 29 = 35 bytes (被浪費的空間)
## 待整理
* [Hack-The-Virtual-Memory](https://github.com/holbertonschool/Hack-The-Virtual-Memory)
* [Process Address Space: The way to create virtual address (page table) of userspace application](https://www.slideshare.net/AdrianHuang/process-address-space-the-way-to-create-virtual-address-page-table-of-userspace-application-251425396)
* [Physical Memory Model](https://www.slideshare.net/AdrianHuang/physical-memory-modelspdf)
* [Physical Memory Management](https://www.slideshare.net/AdrianHuang/physical-memory-managementpdf)
* [Memory Compaction](https://www.slideshare.net/AdrianHuang/memory-compaction-in-linux-kernelpdf)
* [Slab Allocator](https://www.slideshare.net/AdrianHuang/slab-allocator-in-linux-kernel)
* [malloc & vmalloc](https://www.slideshare.net/AdrianHuang/malloc-vmalloc-in-linuxpdf)
* [Reverse Mapping (rmap)](https://www.slideshare.net/AdrianHuang/reverse-mapping-rmap-in-linux-kernel)
* [Memory Mapping Implementation (mmap)](https://www.slideshare.net/AdrianHuang/memory-mapping-implementation-mmap-in-linux-kernel-251745285)
* [Linux PSI (Pressure Stall Information) 指標的解讀與應用](https://igene.tw/pressure-stall-information-intro)
Sign in with Wallet
Connect another wallet