Linux 核心設計: 記憶體管理

Copyright (慣C) 2019 宅色夫

直播錄影 (一)
直播錄影 (二)
直播錄影 (三)

身處事件視界的企鵝

目標設定

記憶體管理是 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

從科普觀點談起

學習金字塔

改編自 五分鐘徹底搞懂你一直沒明白的 Linux 記憶體管理

對於記憶體的部分需要知道：

• 地址映射
• 記憶體管理的方式
• Page fault

以 process 來看，記憶體分為核心模式和使用者模式兩部分，經典比例如下：

從使用者模式到核心模式可經由系統呼叫和中斷來達成。使用者模式的記憶體被劃分為不同的區域用於不同的目的：

當然核心模式也不會無差別地使用，所以，其劃分如下：

下面來仔細看這些記憶體是如何管理的。

• 定址空間

在 Linux 內部的記憶體地址映射過程為邏輯地址 –> 線性地址–> 實體地址 (PA)，實體地址最簡單：在匯流排中傳輸的數位信號，而線性地址和邏輯地址所表示的意涵則是種轉換規則，線性地址規則如下：

這部分由 MMU 完成，其中在 IA32 架構下，涉及到主要的暫存器有 CR0, CR3。機器指令中出現的是邏輯地址，邏輯地址規則如下：

在 Linux 中的邏輯地址對應於線性地址，也就是說 Intel 為了相容過往架構，把硬體設計搞得很複雜，Linux 核心的實作則予以簡化，並且在支援其他處理器架構時，儘量保持該原則。

記憶體管理的方式

在系統啟動之際會去探測記憶體的大小和情況，在建立複雜的結構前，需要透過簡化的模式來管理這些記憶體，這即是 bootmem，簡單來說就是 bitmap，不過其中也有一些優化的思路。

bootmem 再怎麼優化，效率都不高，在要分配記憶體的時候畢竟是要去走訪全部，buddy system 剛好能解決這個問題：在內部保存一些 2 的 N 次方空間記憶體片段，如果要分配 3 pages，去 4 pages 的列表裡面取一個，分配 3 個之後將剩下的 1 個放回去，記憶體釋放的過程剛好是一個反向過程，如下圖:

可見 0, 4, 5, 6, 7 都是正在使用的，那麼 1, 2 被釋放之際，他們會合併嗎？

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 就要用這些碎片來拼湊出一個大記憶體，相當於收集一些「碎肉渣」，以蛋白黏合成一個成品後「出售」這樣的「組合肉」：

相較之前的記憶體採用直接映射的模式，我們此刻首度感受到分頁管理的存在。另外，對於 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
• SLAB: Solaris type allocator (1999-2008)
  • 依據 Sun Microsystems 任職的 Jeff Bonwick 所撰寫的論文 Extending the Slab Allocator to Many CPUs and Arbitrary Resources，自 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

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原理

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

/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

取自 Donald E. Porter 教授的 CSE 506: Operating Systems 教材

• The Art and Science of Memory Allocation
  
  

• Hoard is a fast, scalable, and memory-efficient memory allocator that can speed up your applications.

  • 論文: Hoard: A Scalable Memory Allocator for Multithreaded Applications

• mimalloc: Microsoft Research 開發的完全 lock-free 記憶體管理器

  • 論文: Mimalloc: Free List Sharding in Action

• The Page Cache
• Page Frame Reclaiming
• 浙江大學教材 Virtual Memory and Linux
• Deterministic Memory Allocation for Mission-Critical Linux

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

• 簡報 / 錄影

設定 overcommit_memory 為 1，可執行：

# 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
• What is Overcommit? And why is it bad?

追蹤機制

• 核心選項
  • CONFIG_FUNCTION_TRACER=y
  • CONFIG_DYNAMIC_FTRACE=y
• Ftrace 資訊: /sys/kernel/debug/tracing/ 目錄
• 核心參數
  • trace_event=kmem:kmalloc,
  • kmem:kmalloc_node,
  • kmem:kfree
• 設定 Ftrace 事件

$ cd /sys/kernel/debug/tracing
$ echo "kmem:kmalloc" > set_event
$ echo "kmem:kmalloc_node" >> set_event
$ echo "kmem:kfree" >> set_event

• 觸發 Ftrace

$ echo "1" > tracing_on

• 抑制 Ftrace

$ 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
• Process Address Space: The way to create virtual address (page table) of userspace application
• Physical Memory Model
• Physical Memory Management
• Memory Compaction
• Slab Allocator
• malloc & vmalloc
• Reverse Mapping (rmap)
• Memory Mapping Implementation (mmap)
• Linux PSI (Pressure Stall Information) 指標的解讀與應用