前言

昨天講過了遠古時代的記憶體管理，跟後續為了解決最古老的記憶體管理所引發的問題而接著有的分段管理與分頁管理，今天要提到的是Linux 中使用到的動態記憶體管理的三個機制，分別是 buddy, slab, slob。

對偶式記憶體管理演算法

這個算法正如其名，是讓記憶體分配的時候一對一對的，這個作法會將記憶體頁面的大小以冪次分組，從 $2^0$ ~ $2^{11}$，將所有未使用的頁面分組成11個空閑記憶體區塊的列表，鏈表裡面依序的空閒記憶體大小分別是 1, 2, 4, 8, 16...... 1024個連續的頁面，因為每頁的大小是4KB，所以最大的連續大小就是4MB，更為了管理方便，會依照記憶體的性質再分為三個不同的鏈表，分別是不可移動、可回收、可移動三種，因為世界上所有的數字都可以由二的冪次組成，所以這個演算法便有所依據。
以下舉出一個例子
在內部保存一些 2 的 N 次方空間記憶體片段，如果要分配 3 pages，去 4 pages 的列表裡面取一個，分配 3 個之後將剩下的 1 個放回去，記憶體釋放的過程剛好是一個反向過程。
在 <mm/page_alloc.c> 裡面可以看到跟Buddy 系統有關係的一些函數。
在 get_page_from_freelist() 就是從Buddy系統的link list中嘗試分配裡的頁面; free_page() 則是釋放實體記憶體，其中有個函數是 __free_one_page() ，負責檢查是否有檢查是否有page 需要合併， 在裡頭會呼叫 page_is_buddy() 函數檢查要釋放的記憶體區塊A 鄰近的記憶體區塊是否是未使用的，如果未使用才會繼續進行合併。
對於某兩個記憶體區塊是否能夠合併需要判斷以下三個條件

1. 記憶體區塊B是否在buddy system中
2. 兩塊的記憶體區塊的冪次要相同
3. 兩塊記憶體區塊要在同一個區域內，也就是如果有0,1,2,3 四個記憶體區塊，1跟二是沒辦法合併的。

Slab 記憶體配置器

buddy system 分配記憶體時，是以頁面為單位，但是在實際系統的應用上，有許多的記憶體需求只有需要字節等級的，此時如果仍用頁面分配，會造成非常大的記憶體空間浪費，為了解決這個問題slab allocator就出現了。
Slab 做的事情是在 buddy system之後，利用那些連續的物理頁面實現了自己的機制。
以下列出幾個與slab相關的函數

//創造一個slab 的descriptor
struct kmem_cache *kmem_cache_create(const char *name, size_t size, size_t align, unsigned long floags, void (*ctor)(void *))

//釋放 slab descriptor
void kmem_cache_destroy(struct kmem_cache *s)

//分配記憶體對象
void *kmem_cache_alloc(struct kmem_cache *, gfp_t flags);

//釋放記憶體對象
void kmem_cache_free(struct kmem_cache *, void *);

slub

slub 是slab的改良版，在多數情況下Slab可以正確地完成任務，但是在這個大規模多處理器系統和NUMA系統的廣泛應用下slab逐漸透露出不足。

1. 緩衝序列的管理複雜
2. 管理數據的空間使用量大
3. 對NUMA的支持較複雜
4. 調整測試困難
   因此引入slub allocator，保留了slab allocator的基本思想，但是簡化了slab相關的數據管理結構，捨棄了 slab allocator裡多序列的概念，並且對多處裡去雨NUMA系統優化，提高性能跟可擴展性，並且為了保證相容性，slub保留了slab的所有API函數。

記憶體管理