剖析Linux核心slab原理機制與Buddy演算法（含程式碼~）
一、整體關係圖
注：SLAB，SLOB，SLUB都是核心提供的分配器，其前端介面都是一致的，其中SLAB是通用的分配器，SLOB針對微小的嵌入式系統，其演算法較為簡單（最先適配演算法），SLUB是面向配備大量物理記憶體的大規模並行系統，透過也描述符中未使用的欄位來管理頁組，降低SLUB本身資料結構的記憶體開銷。
二、相關資料結構
2。1 快取kmem_cache （/mm/slab。c）
struct kmem_cache {struct array_cache *array［NR_CPUS］；unsigned int batchcount；//從本地快取記憶體交換的物件的數量unsigned int limit；//本地快取記憶體中空閒物件的數量unsigned int shared；//是否存在共享CPU快取記憶體unsigned int buffer_size；//物件長度+填充位元組u32 reciprocal_buffer_size；//倒數，加快計算unsigned int flags；/*快取記憶體永久性的標誌，當前只CFLGS_OFF_SLAB*/unsigned int num；/*封裝在一個單獨的slab中的物件數目*/unsigned int gfporder；/*每個slab包含的頁框數取2為底的對數*/gfp_t gfpflags；/* e。g。 GFP_DMA分配頁框是傳遞給夥伴系統的標誌*/size_t colour； /* cache colouring range快取的顏色個數free/aln*/unsigned int colour_off；/*slab的基本對齊偏移，為aln的整數倍，用來計算left_over*/struct kmem_cache *slabp_cache；//slab描述符放在外部時使用，其指向的快取記憶體來儲存描述符unsigned int slab_size；//單個slab頭的大小，包括SLAB和物件描述符unsigned int dflags； /*描述快取記憶體動態屬性，目前沒用*//*建構函式*/void（*ctor）（struct kmem_cache *， void *）；const char *name；struct list_head next；//快取記憶體描述符雙向連結串列指標/*統計量*/#if STATSunsigned long num_active；unsigned long num_allocations；unsigned long high_mark；unsigned long grown；unsigned long reaped；unsigned long errors；unsigned long max_freeable；unsignedlong node_allocs；unsigned long node_frees；unsigned long node_overflow；atomic_t allochit；atomic_t allocmiss；atomic_t freehit；atomic_t freemiss；#endif#if DEBUGinto bj_offset；//物件間的偏移int obj_size；//物件本身的大小，#endif//存放的是所有節點對應的相關資料。每個節點擁有各自的資料；struc tkmem_list3 *nodelists［MAX_NUMNODES］；/}
更多linux核心影片教程文件資料免費領取後臺私信
【核心】
自行獲取。
Linux核心原始碼/記憶體調優/檔案系統/程序管理/裝置驅動/網路協議棧-學習影片教程-騰訊課堂
2。2 array_cache本地快取記憶體，每個CPU對應一個該結構
/** struct array_cache**Purpose：* - LIFO ordering， to hand out cache-warm objectsfrom _alloc* - reduce the number of linked list operations* - reduce spinlock operations** The limit is stored in the per-cpu structure toreduce the data cache* footprint。**/struct array_cache {unsigned int avail；//可用物件數目unsigned int limit；//可擁有的最大物件數目，和kmem_cache中一樣unsigned int batchcount；//同kmem_cacheunsigned int touched；//是否在收縮後被訪問過spinlock_t lock；void *entry［］； /*偽陣列，沒有任何資料項，其後為釋放的物件指標陣列*/}；
2。3 kmem_list3管理slab連結串列的資料結構
/** The slab lists for all objects。*/struct kmem_list3 {struct list_head slabs_partial； /* partial listfirst， better asm code */struct list_head slabs_full；struct list_head slabs_free；unsigned long free_objects；//半空和全空連結串列中物件的個數unsigned int free_limit；//所有slab上允許未使用的物件最大數目unsigned int colour_next； /* 下一個slab的顏色*/spinlock_t list_lock；struct array_cache *shared； /* shared per node */struct array_cache **alien； /* on other nodes */unsigned long next_reap； /* 兩次快取收縮時的間隔，降低次數，提高效能*/int free_touched； /* 0收縮1獲取一個物件*/}；
2。4 slab物件
struct slab {struct list_head list；//SLAB所在的連結串列unsigned long colouroff；//SLAB中第一個物件的偏移void *s_mem； /* including colour offset 第一個物件的地址*/unsigned int inuse； /* num of objs active in slab被使用的物件數目*/kmem_bufctl_t free；//下一個空閒物件的下標unsigned short nodeid；//用於定址在快取記憶體中kmem_list3的下標}；
三、相關函式
3。1 kmem_cache_create （mm/slab。c）
/*** kmem_cache_create - Create a cache。* @name： A string which is used in /proc/slabinfo toidentify this cache。* @size： The size of objects to be created in thiscache。* @align： The required alignment for the objects。* @flags： SLAB flags* @ctor： A constructor for the objects。** Returns a ptr to the cache on success， NULL onfailure。* Cannot be calledwithin a int， but can be interrupted。* The @ctor is run when new pages are allocated bythe cache。struct kmem_cache *kmem_cache_create （const char *name， size_t size，size_t align，unsigned long flags，void （*ctor）（struct kmem_cache *， void *））{size_t left_over， slab_size， ralign；struct kmem_cache *cachep = NULL， *pc；/*引數有效性檢查，名字有效性，物件長度比處理器字長還短，或者超過了允許分配的最大值，不能處在中斷上下文，可能導致睡眠*/if （！name || in_interrupt（） || （size
3。2 物件分配函式kmem_cache_alloc（kmem_cache_t* cachep， gfp_t flags）
static inline void *____cache_alloc（struct kmem_cache *cachep，gfp_t flags）{void *objp；struct array_cache *ac；check_irq_off（）；ac = cpu_cache_get（cachep）；//獲得快取記憶體中CPU快取if （likely（ac->avail）） {//如果CPU快取中還有空間，則從中分配STATS_INC_ALLOCHIT（cachep）；ac->touched = 1；objp = ac->entry［——ac->avail］；} else {//否則要填充CPU快取記憶體了STATS_INC_ALLOCMISS（cachep）；objp = cache_alloc_refill（cachep，flags）；}return objp；}//填充CPU快取記憶體static void *cache_alloc_refill（structkmem_cache *cachep， gfp_t flags）{int batchcount；struct kmem_list3 *l3；struct array_cache *ac；int node；ac = cpu_cache_get（cachep）；//獲得高所快取所在本地CPU快取retry：batchcount = ac->batchcount；if （！ac->touched && batchcount > BATCHREFILL_LIMIT）{/*如果不經常活動，則部分填充*/batchcount = BATCHREFILL_LIMIT；//16}l3 = cachep->nodelists［node］；//獲得相應的kmem_list3結構體。。。/* 先考慮從共享本地CPU快取記憶體*/if （l3->shared && transfer_objects（ac， l3->shared，batchcount））goto alloc_done；while （batchcount > 0） {//老老實實的從本快取記憶體分配struct list_head *entry；struct slab *slabp；/* Get slab alloc is to come from。 */entry = l3->slabs_partial。next；//半滿的連結串列if （entry == &l3->slabs_partial） {//如果半空的都沒了，找全空的l3->free_touched = 1；entry = l3->slabs_free。next；if （entry == &l3->slabs_free）//全空的也沒了，必須擴充了cache_grow（cachep， flags | GFP_THISNODE， node， NULL）；}//此時，已經找到了一個連結串列（半空或者全空）slabp = list_entry（entry， struct slab， list）；//找到一個slabcheck_slabp（cachep， slabp）；check_spinlock_acquired（cachep）；while （slabp->inuse < cachep->num &&batchcount——）{//迴圈從slab中分配物件ac->entry［ac->avail++］ =slab_get_obj（cachep， slabp，node）；}check_slabp（cachep， slabp）；/*將slab放到合適的鏈中：*/list_del（&slabp->list）；if （slabp->free == BUFCTL_END）//如果已經沒有空閒物件了，則放到滿連結串列中list_add（&slabp->list， &l3->slabs_full）；else//否則放在半滿連結串列list_add（&slabp->list， &l3->slabs_partial）；}。。。ac->touched = 1；return ac->entry［——ac->avail］；}//按次序從SLAB中起初物件static void *slab_get_obj（struct kmem_cache *cachep， struct slab*slabp，int nodeid）{void *objp =index_to_obj（cachep， slabp， slabp->free）；//找到要找的物件kmem_bufctl_t next；slabp->inuse++；//增加計數器next =slab_bufctl（slabp）［slabp->free］；//獲得slab_bufctl［slab->free］的值，為下一次鎖定的空閒下標slabp->free =next；//將鎖定下標放到free中return objp；}
3。3 cache_grow
//增加新的SLABstatic int cache_grow（structkmem_cache *cachep， gfp_t flags， int nodeid， void *objp）{struct slab *slabp；size_t offset；gfp_t local_flags；struct kmem_list3 *l3；。。。l3 = cachep->nodelists［nodeid］；。。。/* 計算偏移量和下一個顏色。*/offset = l3->colour_next；//計算下一個顏色l3->colour_next++；//如果到了最大值則回0if （l3->colour_next >= cachep->colour）l3->colour_next = 0；offset *= cachep->colour_off；//計算此SLAB的偏移//從夥伴系統獲得物理頁objp = kmem_getpages（cachep， local_flags， nodeid）；。。。/* 如果slab頭放在外部，則呼叫此函式分配函式*/slabp = alloc_slabmgmt（cachep， objp， offset，local_flags & ~GFP_CONSTRAINT_MASK， nodeid）；slabp->nodeid = nodeid；//在kmem_cache中陣列的下標//依次對每個物理頁的lru。next=cache，lru。prev=slabslab_map_pages（cachep， slabp， objp）；//呼叫各個物件的構造器函式，初始化新SLAB中的物件cache_init_objs（cachep， slabp）；/* 將新的SLAB加入到全空連結串列中*/list_add_tail（&slabp->list， &（l3->slabs_free））；STATS_INC_GROWN（cachep）；l3->free_objects += cachep->num；//更新空閒物件的數目。。。return 0；}
3。4 釋放物件kmem_cache_free
//真正的處理函式static inline void __cache_free（struct kmem_cache *cachep， void*objp）{struct array_cache *ac = cpu_cache_get（cachep）；。。。if （likely（ac->avail < ac->limit））{//如果CPU快取記憶體還有位子，則直接釋放ac->entry［ac->avail++］ = objp；return；} else {//否則需要將部分物件FLUSH到SLAB中了STATS_INC_FREEMISS（cachep）；cache_flusharray（cachep， ac）；ac->entry［ac->avail++］ = objp；}}//將部分CPU快取記憶體FLUSH到SLAB中static void cache_flusharray（struct kmem_cache *cachep， structarray_cache *ac）{int batchcount；struct kmem_list3 *l3；int node = numa_node_id（）；batchcount = ac->batchcount；//指定數量l3 = cachep->nodelists［node］；if （l3->shared） {//如果共享CPU快取存在，則將共享快取填滿，然後返回struct array_cache *shared_array = l3->shared；int max = shared_array->limit - shared_array->avail；if （max） {//if （batchcount > max）batchcount = max；//這裡只是複製，並沒有移除memcpy（&（shared_array->entry［shared_array->avail］），ac->entry， sizeof（void *） * batchcount）；shared_array->avail += batchcount；goto free_done；}}//否則需要釋放到SLAB中了free_block（cachep，ac->entry， batchcount， node）；free_done：//對CPU快取記憶體進行移除操作spin_unlock（&l3->list_lock）；ac->avail -= batchcount；memmove（ac->entry， &（ac->entry［batchcount］），sizeof（void *）*ac->avail）；}//將nr_objects個物件釋放到SLAB中，objpp指CPU快取陣列static void free_block（struct kmem_cache *cachep， void **objpp，int nr_objects， int node）{int i；struct kmem_list3 *l3；for （i = 0； i < nr_objects； i++） {//對每一個物件處理，先從頭部處理，LIFOvoid *objp = objpp［i］；struct slab *slabp；slabp = virt_to_slab（objp）；//獲得SLAB描述符l3 = cachep->nodelists［node］；list_del（&slabp->list）；//將SLAB從原來的連結串列中刪除check_spinlock_acquired_node（cachep， node）；check_slabp（cachep， slabp）；slab_put_obj（cachep， slabp， objp，node）；//將objp放到slab中，和slab_get_obj相反STATS_DEC_ACTIVE（cachep）；l3->free_objects++；//增加快取記憶體的可用物件數目check_slabp（cachep， slabp）；/*將SLAB重新插入連結串列*/if （slabp->inuse == 0） {//如果SLAB是全空的if （l3->free_objects > l3->free_limit）{//並且快取記憶體空閒物件已經超出限制，則需要將SLAB返回給底層頁框管理器l3->free_objects -= cachep->num；slab_destroy（cachep， slabp）；} else {//直接插入空閒連結串列list_add（&slabp->list， &l3->slabs_free）；}} else {//直接插入部分空閒連結串列list_add_tail（&slabp->list， &l3->slabs_partial）；}}}
3。5 快取記憶體的銷燬kmem_cache_destroy，此函式用在模組解除安裝時使用，釋放以前分配的空間
四、通用快取
即kmalloc和kfree使用的，放在malloc_size表中，從32-33554432共21個成員。成員的結構如
/* Size description struct for general caches。 */struct cache_sizes {size_t cs_size；//物件大小struct kmem_cache *cs_cachep；//對應的快取記憶體struct kmem_cache *cs_dmacachep；//對應的DMA訪問快取}；//通用快取記憶體在/kmalloc_sizes。hstruct cache_sizes malloc_sizes［］ = {#define CACHE（x） { 。cs_size = （x） }，#include
Kmalloc_sizes。h
#if （PAGE_SIZE == 4096）CACHE（32）#endifCACHE（64）#if L1_CACHE_BYTES < 64CACHE（96）#endifCACHE（128）#if L1_CACHE_BYTES < 128CACHE（192）#endifCACHE（256）CACHE（512）CACHE（1024）CACHE（2048）CACHE（4096）CACHE（8192）CACHE（16384）CACHE（32768）CACHE（65536）CACHE（131072）#if KMALLOC_MAX_SIZE >= 262144CACHE（262144）#endif#if KMALLOC_MAX_SIZE >= 524288CACHE（524288）#endif#if KMALLOC_MAX_SIZE >= 1048576CACHE（1048576）#endif#if KMALLOC_MAX_SIZE >= 2097152CACHE（2097152）#endif#if KMALLOC_MAX_SIZE >= 4194304CACHE（4194304）#endif#if KMALLOC_MAX_SIZE >= 8388608CACHE（8388608）#endif#if KMALLOC_MAX_SIZE >= 16777216CACHE（16777216）#endif#if KMALLOC_MAX_SIZE >= 33554432CACHE（33554432）#endif
4。1 kalloc函式
//分配函式static inline void *kmalloc（size_t size， gfp_t flags）{if （__builtin_constant_p（size））{//是否用常數指定所需的記憶體長度int i = 0；//找到合適大小的i值。。。//按型別進行分配#ifdef CONFIG_ZONE_DMAif （flags & GFP_DMA）return kmem_cache_alloc（malloc_sizes［i］。cs_dmacachep，flags）；#endifreturn kmem_cache_alloc（malloc_sizes［i］。cs_cachep， flags）；}//不使用常數指定return __kmalloc（size， flags）；}//大小不用指定的分配static __always_inline void *__do_kmalloc（size_t size， gfp_tflags， void *caller）{struct kmem_cache *cachep；cachep = __find_general_cachep（size， flags）；//找一個合適大小的快取記憶體if （unlikely（ZERO_OR_NULL_PTR（cachep）））return cachep；return __cache_alloc（cachep， flags， caller）；//分配函式}
4。2 釋放函式kfree
//kmalloc對應的釋放函式void kfree（const void *objp）{struct kmem_cache *c；unsigned long flags；。。。c =virt_to_cache（objp）；//獲得快取記憶體debug_check_no_locks_freed（objp， obj_size（c））；__cache_free（c， （void*）objp）；//呼叫此函式完成實質性的分配local_irq_restore（flags）；}
五、夥伴系統
2、夥伴系統分析
今天去面試，一位面試官提到了
記憶體管理的夥伴系統
，當時就懵了，因為根本就沒有聽說過。晚上回來在實驗室查了一些資料，現總結如下：
a、夥伴系統概念
夥伴系統是一種經典的記憶體管理方法。Linux夥伴系統的引入為核心提供了一種用於
分配一組連續的頁
而建立的一種高效的分配策略，並有效的解決了外碎片問題。 b、
夥伴系統的組織結構
Linux中的記憶體管理的“頁”大小為4KB。把所有的空閒頁分組為11個塊連結串列，每個塊連結串列分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個連續頁框的頁塊。最大可以申請1024個連續頁，對應4MB大小的連續記憶體。每個頁塊的第一個頁的物理地址是該塊大小的整數倍。 結構如圖所示：第i個塊連結串列中，num表示大小為（2^i）頁塊的數目，address表示大小為（2^i）頁塊的首地址。
c、夥伴系統的記憶體分配及釋放
當向核心
請求分配(2^(i-1)，2^i]
數目的頁塊時，按照2^i頁塊請求處理。如果對應的塊連結串列中沒有空閒頁塊，則在更大的頁塊連結串列中找。當分配的頁塊中有多餘的頁時，夥伴系統根據多餘的頁框大小插入到對應的空閒頁塊連結串列中。
當
釋放單頁
的記憶體時，核心將其置於CPU快取記憶體中，對很可能出現在cache的頁，則放到“快表”的列表中。在此過程中，核心先判斷CPU快取記憶體中的頁數是否超過一定“閾值”，如果是，則將一批記憶體頁還給夥伴系統，然後將該頁新增到CPU快取記憶體中。
當
釋放多頁
的塊時，核心首先計算出該記憶體塊的夥伴的地址。
核心將滿足以下條件的三個塊稱為夥伴
：（1）兩個塊具有相同的大小，記作b。（2）它們的物理地址是
連續
的。（3）第一塊的第一個頁的
物理地址
是2*（2^b）的倍數。如果找到了該記憶體塊的夥伴，確保該夥伴的所有頁都是空閒的，以便進行合併。記憶體繼續檢查合併後頁塊的“夥伴”並檢查是否可以合併，依次類推。
d、夥伴系統的反碎片機制
核心將已分配頁分為以下三種不同的型別：
（1）
不可移動頁
：這些頁在記憶體中有固定的位置，不能夠移動。
（2）
可回收頁
：這些頁不能移動，但可以刪除。核心在回收頁佔據了太多的記憶體時或者記憶體短缺時進行頁面回收。
（3）
可移動頁
：這些頁可以任意移動，使用者空間應用程式使用的頁都屬於該類別。它們是透過頁表對映的。當它們移動到新的位置，頁表項也會相應的更新。
在記憶體子系統初始化期間，所有的頁都被標記為可移動的。在啟動期間，核心核心分配的記憶體是不可移動的。此時核心的策略是分配一個
儘可能大的連續記憶體塊，將其從可移動列表轉換到不可移動列表
。分配一個儘可能大的連續記憶體塊而不是選擇更小的滿足要求的記憶體塊的原因如下：
例如：現有一塊可移動的具有16頁的連續空閒記憶體塊。當核心需要分配1頁不可移動記憶體頁時。分配器選擇後8頁（而不是一頁）轉移到不可移動列表，然後從不可移動列表中選擇1頁用於分配。如果核心又需要分配1頁不可移動記憶體頁則從不可移動列表中選擇一頁用於分配，下圖顯示了進行4次分配後記憶體的分佈。
但如果核心只選擇1頁用於分配將其加入到不可移動列表，當下次需要分配時又選擇一頁加入到不可移動列表，下圖顯示了按照這種方式進行4次分配後記憶體的分佈。
因此，當沒有滿足可用於分配的不可移動空閒塊時，分配器會在可移動列表中遷移一個儘可能大的連續記憶體塊給不可移動列表。這樣
避免
了啟動期間核心分配的記憶體雜湊到物理記憶體各處，從而使其他型別的記憶體分配免受碎片的干擾。
2、夥伴系統
Linux核心中採用了一種同時適用於32位和64位系統的記憶體分頁模型，對於32位系統來說，兩級頁表足夠用了，而在x86_64系統中，用到了四級頁表。四級頁表分別為：
頁全域性目錄（Page Global Directory）
頁上級目錄（Page Upper Directory）
頁中間目錄（Page Middle Directory）
頁表（Page Table）
頁全域性目錄包含若干頁上級目錄的地址，頁上級目錄又依次包含若干頁中間目錄的地址，而頁中間目錄又包含若干頁表的地址，每一個頁表項指向一個頁框。Linux中採用4KB大小的頁框作為標準的記憶體分配單元。
在實際應用中，經常需要分配一組連續的頁框，而頻繁地申請和釋放不同大小的連續頁框，必然導致在已分配頁框的記憶體塊中分散了許多小塊的空閒頁框。這樣，即使這些頁框是空閒的，其他需要分配連續頁框的應用也很難得到滿足。
為了避免出現這種情況，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個頁框的連結串列查詢，如果仍然沒有，則返回錯誤。
頁框塊在釋放時，會主動將兩個連續的頁框塊合併為一個較大的頁框塊。
1、Buddy演算法的優缺點：
1）儘管夥伴記憶體演算法在記憶體碎片問題上已經做的相當出色，但是該演算法中，一個很小的塊往往會阻礙一個大塊的合併，一個系統中，對記憶體塊的分配，大小是隨機的，一片記憶體中僅一個小的記憶體塊沒有釋放，旁邊兩個大的就不能合併。
2）演算法中有一定的浪費現象，夥伴演算法是按2的冪次方大小進行分配記憶體塊，當然這樣做是有原因的，即為了避免把大的記憶體塊拆的太碎，更重要的是使分配和釋放過程迅速。但是他也帶來了不利的一面，如果所需記憶體大小不是2的冪次方，就會有部分頁面浪費。有時還很嚴重。比如原來是1024個塊，申請了16個塊，再申請600個塊就申請不到了，因為已經被分割了。
3）另外拆分和合並涉及到 較多的連結串列和點陣圖操作，開銷還是比較大的。
Buddy（夥伴的定義）：
這裡給出夥伴的概念，滿足以下三個條件的稱為夥伴：
1）兩個塊大小相同；
2）兩個塊地址連續；
3）兩個塊必須是同一個大塊中分離出來的；
2、Buddy演算法的分配原理：
假如系統需要4（2
2）個頁面大小的記憶體塊，該演算法就到free_area［2］中查詢，如果連結串列中有空閒塊，就直接從中摘下並分配出去。如果沒有，演算法將順著陣列向上查詢free_area［3］，如果free_area［3］中有空閒塊，則將其從連結串列中摘下，分成等大小的兩部分，前四個頁面作為一個塊插入free_area［2］，後4個頁面分配出去，free_area［3］中也沒有，就再向上查詢，如果free_area［4］中有，就將這16（2
2
2
2）個頁面等分成兩份，前一半掛如free_area［3］的連結串列頭部，後一半的8個頁等分成兩等分，前一半掛free_area［2］的連結串列中，後一半分配出去。假如free_area［4］也沒有，則重複上面的過程，知道到達free_area陣列的最後，如果還沒有則放棄分配。
3、Buddy演算法的釋放原理：
記憶體的釋放是分配的逆過程，也可以看作是夥伴的合併過程。當釋放一個塊時，先在其對應的連結串列中考查是否有夥伴存在，如果沒有夥伴塊，就直接把要釋放的塊掛入連結串列頭；如果有，則從連結串列中摘下夥伴，合併成一個大塊，然後繼續考察合併後的塊在更大一級連結串列中是否有夥伴存在，直到不能合併或者已經合併到了最大的塊（2
2
2
2
2
2
2
2
2個頁面）。
