Try   HackMD

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),實體地址最簡單:在匯流排中傳輸的數位信號,而線性地址和邏輯地址所表示的意涵則是種轉換規則,線性地址規則如下:
image

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

在 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)
  • 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 是目前 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 更容易產生記憶體碎片問題,僅用於小型系統,特別是嵌入式系統。

/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 教材

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

參照:

追蹤機制

  • 核心選項
    • 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 (被浪費的空間)

待整理