--- 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://i.imgur.com/qEIJObQ.png) > 身處[事件視界](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 來看,記憶體分為核心模式和使用者模式兩部分,經典比例如下: ![](https://i.imgur.com/ysvEhtv.png) 從使用者模式到核心模式可經由系統呼叫和中斷來達成。使用者模式的記憶體被劃分為不同的區域用於不同的目的: ![](https://i.imgur.com/F2otWjA.png) 當然核心模式也不會無差別地使用,所以,其劃分如下: ![](https://i.imgur.com/k6jsQmo.png) 下面來仔細看這些記憶體是如何管理的。 - [ ] 定址空間 在 Linux 內部的記憶體地址映射過程為邏輯地址 –> 線性地址–> 實體地址 (PA),實體地址最簡單:在匯流排中傳輸的數位信號,而線性地址和邏輯地址所表示的意涵則是種轉換規則,線性地址規則如下: ![](https://i.imgur.com/5aCYmqA.png) 這部分由 MMU 完成,其中在 IA32 架構下,涉及到主要的暫存器有 CR0, CR3。機器指令中出現的是邏輯地址,邏輯地址規則如下: ![](https://i.imgur.com/DsgNlzI.png) 在 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 個放回去,記憶體釋放的過程剛好是一個反向過程。用一個圖來表示: ![](https://i.imgur.com/IpXwnWx.png) 可見 0, 4, 5, 6, 7 都是正在使用的,那麼 1, 2 被釋放之際,他們會合併嗎? ```clike 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 來解決小物件的分配: ![](https://i.imgur.com/KHVkfij.png) 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)」: ![](https://i.imgur.com/DRgHo7v.png) 相較之前的記憶體採用直接映射的模式,我們此刻首度感受到分頁管理的存在。另外,對於 High Memory Area,提供 `kmap` 為 page 分配一個線性地址。 process 由不同長度的 section 組成:text, 動態函式庫、全域變數/符號和動態產生資料的 stack/heap 等等。在 Linux 中為每個 process 管理了一套虛擬定址空間: ![](https://i.imgur.com/QeeQZnr.png) 在呼叫 `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`: 發生異常當下的暫存器數值 處理的流程如下: ![](https://i.imgur.com/ljg7lNL.png) 發生 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 wuthin the space of the free objects - allocation requires traversing the list to find an object with sufficient sze. * If nothing is found, the page allocator is used to increase the size of the heap. - rapid fragmentation of memory * 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) ![](https://i.imgur.com/gCBAKWC.png) 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 sysytem 要一個 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 大小。 ![](https://i.imgur.com/J3I7kMY.png) 參照 [Linux Memory Management](https://hackmd.io/s/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) ![](https://i.imgur.com/q6njBHt.png) ![](https://i.imgur.com/nrP4PIY.png) * [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) ![](https://i.imgur.com/0IWcp4Z.png) 設定 overcommit_memory 為 `1`,可執行: ```shell # echo 1 > /proc/sys/vm/overcommit_memory ``` 有三種可用值: * `0` — 預設值。核心會進行探索式的記憶體過度寫入處理,方法是預測記憶體的可用量、並讓公然違規的需求失敗。不過,因記憶體採取探索式、而非精準的演算法則來分配,因此這設定有時會過度使用系統上的可用記憶體; * `1` — 核心不進行記憶體過度寫入處理。在此設定下,過度使用記憶體的機會會增加,但對於頻繁存取記憶體的任務來說,效能也會增加。 * `2` — 核心拒絕相等或大於總可用置換空間與實體記憶體比例(於 `overcommit_ratio` 指定)的記憶體需求。如果您想要降低記憶體過度寫入的風險,這是最佳設定。 [微調處理能力](https://access.redhat.com/documentation/zh-tw/red_hat_enterprise_linux/6/html/performance_tuning_guide/s-memory-captun) > redhat 的中英說明會讓人有點混淆, 附上 linux manual page 的說明 > [name=Julian Chu] > [time=Sun, May 2, 2021 4:28 PM] `man 5 proc` >/proc/sys/vm/overcommit_memory This file contains the kernel virtual memory accounting mode. Values are: > >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) ![](https://i.imgur.com/KUyY94e.png) ## 追蹤機制 * 核心選項 * `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)