--- 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://hackmd.io/_uploads/HyAfwjw4h.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://hackmd.io/_uploads/S1dmDiPN2.png) 從使用者模式到核心模式可經由系統呼叫和中斷來達成。使用者模式的記憶體被劃分為不同的區域用於不同的目的： ![](https://hackmd.io/_uploads/ByJEvsvN3.png) 當然核心模式也不會無差別地使用，所以，其劃分如下： ![](https://hackmd.io/_uploads/Sy5EwiwN3.png) 下面來仔細看這些記憶體是如何管理的。 - [ ] 定址空間 在 Linux 內部的記憶體地址映射過程為邏輯地址 –> 線性地址–> 實體地址 (PA)，實體地址最簡單：在匯流排中傳輸的數位信號，而線性地址和邏輯地址所表示的意涵則是種轉換規則，線性地址規則如下： ![image](https://hackmd.io/_uploads/S16QclmLa.png) 這部分由 MMU 完成，其中在 IA32 架構下，涉及到主要的暫存器有 CR0, CR3。機器指令中出現的是邏輯地址，邏輯地址規則如下： ![image](https://hackmd.io/_uploads/S1MGclXIa.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://hackmd.io/_uploads/S1WwvjPNh.png) 可見 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 來解決小物件的分配： ![](https://hackmd.io/_uploads/r1HOwow42.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://hackmd.io/_uploads/H1WKvoDEh.png) 相較之前的記憶體採用直接映射的模式，我們此刻首度感受到分頁管理的存在。另外，對於 High Memory Area，提供 `kmap` 為 page 分配一個線性地址。 process 由不同長度的 section 組成：text, 動態函式庫、全域變數/符號和動態產生資料的 stack/heap 等等。在 Linux 中為每個 process 管理了一套虛擬定址空間： ![](https://hackmd.io/_uploads/BJ-9Dow42.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://hackmd.io/_uploads/Sk25Div4n.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 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) ![](https://hackmd.io/_uploads/rkriPoDNh.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 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 大小。 ![](https://hackmd.io/_uploads/S1y3vjDNn.png) 參照 [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) ![](https://hackmd.io/_uploads/B1dquiP43.png) ![](https://hackmd.io/_uploads/Hyxo_oPN3.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://hackmd.io/_uploads/rkVb_iDV3.png) 設定 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) ![](https://hackmd.io/_uploads/SJXZwiwV3.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) * [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)