[[251667]]

Buddy分配算法

假設這是一段連續的頁框，陰影部分表示已經被使用的頁框，現在需要申請一個連續的5個頁框。這個時候，在這段內存上不能找到連續的5個空閑的頁框，就會去另一段內存上去尋找5個連續的頁框，這樣子，久而久之就形成了頁框的浪費。為了避免出現這種情況，Linux內核中引入了伙伴系統算法(Buddy system)。把所有的空閑頁框分組為11個塊鏈表，每個塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁框塊。最大可以申請1024個連續頁框，對應4MB大小的連續內存。每個頁框塊的第一個頁框的物理地址是該塊大小的整數倍，如圖：

假設要申請一個256個頁框的塊，先從256個頁框的鏈表中查找空閑塊，如果沒有，就去512個頁框的鏈表中找，找到了則將頁框塊分為2個256個頁框的塊，一個分配給應用，另外一個移到256個頁框的鏈表中。如果512個頁框的鏈表中仍沒有空閑塊，繼續向1024個頁框的鏈表查找，如果仍然沒有，則返回錯誤。頁框塊在釋放時，會主動將兩個連續的頁框塊合并為一個較大的頁框塊。

從上面可以知道Buddy算法一直在對頁框做拆開合并拆開合并的動作。Buddy算法牛逼就牛逼在運用了世界上任何正整數都可以由2^n的和組成。這也是Buddy算法管理空閑頁表的本質。

空閑內存的信息我們可以通過以下命令獲取：

也可以通過echo m > /proc/sysrq-trigger來觀察buddy狀態，與/proc/buddyinfo的信息是一致的：

CMA

細心的讀者或許會發現當Buddy算法對內存拆拆合合的過程中會造成碎片化的現象，以至于內存后來沒有了大塊的連續內存，全是小塊內存。當然這對應用程序是不影響的(前面我們講過用頁表可以把不連續的物理地址在虛擬地址上連續起來)，但是內核態就沒有辦法獲取大塊連續的內存(比如DMA, Camera, GPU都需要大塊物理地址連續的內存)。

在嵌入式設備中一般用CMA來解決上述的問題。CMA的全稱是contiguous memory allocator， 其工作原理是：預留一段的內存給驅動使用，但當驅動不用的時候，CMA區域可以分配給用戶進程用作匿名內存或者頁緩存。而當驅動需要使用時，就將進程占用的內存通過回收或者遷移的方式將之前占用的預留內存騰出來，供驅動使用。

Slab

在Linux中，伙伴系統(buddy system)是以頁為單位管理和分配內存。但是現實的需求卻以字節為單位，假如我們需要申請20Bytes，總不能分配一頁吧!那豈不是嚴重浪費內存。那么該如何分配呢?slab分配器就應運而生了，專為小內存分配而生。slab分配器分配內存以Byte為單位。但是slab分配器并沒有脫離伙伴系統，而是基于伙伴系統分配的大內存進一步細分成小內存分配。我們先來看一張圖

kmem_cache是一個cache_chain的鏈表，描述了一個高速緩存，每個高速緩存包含了一個slabs的列表，這通常是一段連續的內存塊。存在3種slab：

• slabs_full(完全分配的slab)
• slabs_partial(部分分配的slab)
• slabs_empty(空slab,或者沒有對象被分配)。

slab是slab分配器的最小單位，在實現上一個slab有一個貨多個連續的物理頁組成(通常只有一頁)。單個slab可以在slab鏈表之間移動，例如如果一個半滿slab被分配了對象后變滿了，就要從slabs_partial中被刪除，同時插入到slabs_full中去。

為了進一步解釋，這里舉個例子來說明，用struct kmem_cache結構描述的一段內存就稱作一個slab緩存池。一個slab緩存池就像是一箱牛奶，一箱牛奶中有很多瓶牛奶，每瓶牛奶就是一個object。分配內存的時候，就相當于從牛奶箱中拿一瓶。總有拿完的一天。當箱子空的時候，你就需要去超市再買一箱回來。超市就相當于partial鏈表，超市存儲著很多箱牛奶。如果超市也賣完了，自然就要從廠家進貨，然后出售給你。廠家就相當于伙伴系統。

可以通過下面命令查看slab緩存的信息：

總結

從內存DDR分為不同的ZONE，到CPU訪問的Page通過頁表來映射ZONE，再到通過Buddy算法和Slab算法對這些Page進行管理，我們應該可以從感官的角度理解了下圖：