Copyright (慣C) 2019 宅色夫
身處事件視界的企鵝
記憶體管理是 Linux 核心裡頭最複雜的部分,涉及到對計算機結構、slob/slab/slub 記憶體配置器、行程和執行檔樣貌、虛擬記憶體對應的例外處理、記憶體映射, UMA vs. NUMA 等等議題。
在本講座中,我們預計探討:
對於記憶體的部分需要知道:
以 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 終於暴露出其不足:
為此,核心開發者引入 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 處理。
在實際需要某個虛擬記憶體區域的資料前,和實體記憶體之間的映射關係不會建立。如果 process 存取的虛擬定址空間部分尚未與 page frame 有所關聯,處理器自動引發一個 page fault。在核心處理 page fault 之際,Linux 可取得的資訊如下:
cr2
: 存取到線性地址err_code
: 異常發生時由控制單元推入 stack 中,表示發生異常的原因regs
: 發生異常當下的暫存器數值處理的流程如下:
發生 page fault 時,可能因為不常使用而被 swap 到主記憶體以外的儲存設備中。
如果記憶體是透過 mmap 映射的手段取得,那麼在讀、寫對應記憶體時也會觸發 page fault。
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
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 大小。
取自 Donald E. Porter 教授的 CSE 506: Operating Systems 教材
Hoard is a fast, scalable, and memory-efficient memory allocator that can speed up your applications.
mimalloc: Microsoft Research 開發的完全 lock-free 記憶體管理器
設定 overcommit_memory 為 1
,可執行:
# echo 1 > /proc/sys/vm/overcommit_memory
有三種可用值:
0
: heuristic overcommit (this is the default)1
: always overcommit, never check2
: always check, never overcommit參照:
CONFIG_FUNCTION_TRACER=y
CONFIG_DYNAMIC_FTRACE=y
/sys/kernel/debug/tracing/
目錄$ cd /sys/kernel/debug/tracing
$ echo "kmem:kmalloc" > set_event
$ echo "kmem:kmalloc_node" >> set_event
$ echo "kmem:kfree" >> set_event
$ echo "1" > tracing_on
$ 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 (被浪費的空間)