slab分配器設計的需求

在Linux內核的內存子系統中，伙伴系統無疑處于內存管理的核心地帶，但是如果將內存管理從邏輯上分層，它的位置則處于最底層。Buddy是所有物理內存的管家，不論使用何種接口申請內存都要經由伙伴系統進行分配。但是，伙伴系統管理的物理內存是以頁為單位，以4K頁為例，它也包含了4096個字節。但是無論是內核自己還是用戶程序，在日常的使用中都很少會需要使用四千多字節大小的內存。試想如果我們僅需要為10個字符的字符串分配內存，但是伙伴系統卻給了我們一頁，那這一頁剩余沒有使用的內存就浪費了，而且這個浪費近乎奢侈。除了浪費的問題， 還有一個更需要關心的問題是，在這樣的分配情況下，如果分配非常頻繁，系統可能很快就會面臨嚴重的碎片化問題。因為頻繁使用的數據結構也會頻繁的分配和釋放，加速生產內存碎片。另外，直接調用伙伴系統的操作對系統的數據和指令高速緩存也有很大的影響。所以，基于以上的原因，也源于現實需求，內核需要一種輕量的、快速的、靈活的新型內存分配器，最主要的是，它可以提供小塊內存的分配。為了實現這樣的小內存分配器，Sun公司的J.Bonwick首先在Solaris 2.4中設計并實現了slab分配器，并對其開源。在Linux中也實現了具有相同的基本設計思想的同名分配器slab。

slab、slob和slub關系

slab、slob和slub都是小內存分配器，slab是slob和slub實現的基礎，而slob和slub是針對slab在不同場景下的優化版本。在slab引入Linux的很多年內，其都是Linux內核管理對象緩沖區的主流算法。并且由于slab的實現非常復雜，很長一段時間內都少有對它的改動。隨著多處理器的發展和NUMA架構的廣泛應用，slab的不足也逐漸顯現。slab的緩存隊列管理復雜，其用于管理的數據結構存儲開銷大，對NUMA支持復雜，slab著色機制效果不明顯。這些不足讓slab很難在兩種場景下提供最優的性能：小型嵌入式系統和配備有大量物理內存的大規模并行系統。對于小型嵌入式系統來說，slab分配器的代碼量和復雜性都太高；對于大規模并行系統，slab用于自身管理的數據結構就需要占用很多G字節內存。針對slab的不足，內核開發人員Christoph Lameter在在內核版本2.6開發期間，引入了新的Slub分配器。Slub簡化了slab一些復雜的設計，但保持slab的基本設計思想。同時，一種新的針對小型嵌入式系統的分配器slob也被引入，為了適應嵌入式系統的特點，slob進行了特別的優化，以大幅減少代碼量（slob只有大約600行代碼）。

slab層在內存管理子系統的層次

slab層可以理解為一個通用層，其包含了slab、slob和slub，至于底層具體使用哪種分配器可以通過配置內核選項進行選擇。對于內核的其他模塊，則不需要關注底層使用了哪個分配器。因為為了保證內核的其他模塊都可以無縫遷移到Slub/slob，所有分配器的接口都是相同的，它們都實現了一組特定的接口用于內存分配。下圖為Slab層在內存管理中的層次圖：

邏輯上看，slab層位于伙伴系統之上。因為Buddy是最底層的分配器，Slub需要先向Buddy申請內存，而不能越過Buddy獲取page。從Buddy申請到內存后，Slub才可以對其進行自己的操作。

slub分配器框架

下圖是在讀完宋牧春大俠的《圖解Slub》后，我也總結了一張Slub分配器框架圖，可以大致的看到Slub的框架。Slub的框架如下圖（圖片很大，可以放大）：

這篇文章中用了一個通俗易懂的例子來介紹Slub的工作原理，我覺的這個例子很恰當，所以這里繼續借舉一下。

每個數組元素對應一種大小的內存，可以把一個kmem_cache結構體看做是一個特定大小內存的零售商，整個Slub系統中有很多個這樣的零售商，每個“零售商”只“零售”特定大小的內存，例如：有的“零售商”只"零售"8Byte大小的內存，有的只”零售“16Byte大小的內存?！詌uken.《linux內核內存管理slub算法(一)原理》

Slub的工作原理和日常生產生活的產銷環節很類似，所以為了清晰直觀的看到其工作原理，我把這個過程畫了一幅圖來表示，如下圖：

每個零售商(kmem_cache)有兩個“部門”，一個是“倉庫”：kmem_cache_node，一個“營業廳”：kmem_cache_cpu。“營業廳”里只保留一個slab，只有在營業廳(kmem_cache_cpu)中沒有空閑內存的情況下才會從倉庫中換出其他的slab。所謂slab就是零售商(kmem_cache)批發的連續的整頁內存，零售商把這些整頁的內存分成許多小內存，然后分別“零售”出去，一個slab可能包含多個連續的內存頁。slab的大小和零售商有關?！詌uken.《linux內核內存管理slub算法(一)原理》

總的來說，Slub就相當于零售商，它從伙伴系統“批發”內存，然后再零售出去。

slub的重要數據結構

• kmem_cache

structkmem_cache{
structkmem_cache_cpu__percpu*cpu_slab;
/*Usedforretrivingpartialslabsetc*/
unsignedlongflags;
unsignedlongmin_partial;
/*size=object_size+對象后面下個空閑對象的指針的size*/
intsize;/*Thesizeofanobjectincludingmetadata*/
intobject_size;/*Thesizeofanobjectwithoutmetadata*/
/*object首地址+offset=下一個空閑對象的指針地址*/
intoffset;/*Freepointeroffset.*/
intcpu_partial;/*Numberofpercpupartialobjectstokeeparound*/
/*
*oo表示存放最優slab的order和object的數量
*低16位表示對象數，高16位表示slab的order
*/
structkmem_cache_order_objectsoo;
/*Allocationandfreeingofslabs*/
structkmem_cache_order_objectsmax;
/*
*最小slab只需要足夠存放一個對象。當設備長時間運行以后，內存碎片化嚴重，
*分配連續物理頁很難成功，如果分配最優slab失敗，就分配最小slab。
*/
structkmem_cache_order_objectsmin;
gfp_tallocflags;/*gfpflagstouseoneachalloc*/
intrefcount;/*Refcountforslabcachedestroy*/
void(*ctor)(void*);
intinuse;/*Offsettometadata*/
intalign;/*Alignment*/
//當slab長度不是對象長度的整數倍的時候，尾部有剩余部分，保存在reserved中
intreserved;/*Reservedbytesattheendofslabs*/
constchar*name;/*Name(onlyfordisplay!)*/
structlist_headlist;/*Listofslabcaches*/
intred_left_pad;/*Leftredzonepaddingsize*/
#ifdefCONFIG_SYSFS
structkobjectkobj;/*Forsysfs*/
#endif
#ifdefCONFIG_MEMCG
structmemcg_cache_paramsmemcg_params;
intmax_attr_size;/*forpropagation,maximumsizeofastoredattr*/
#ifdefCONFIG_SYSFS
structkset*memcg_kset;
#endif
#endif
#ifdefCONFIG_NUMA
/*
*Defragmentationbyallocatingfromaremotenode.
*/
intremote_node_defrag_ratio;
#endif
#ifdefCONFIG_SLAB_FREELIST_RANDOM
unsignedint*random_seq;
#endif
#ifdefCONFIG_KASAN
structkasan_cachekasan_info;
#endif
structkmem_cache_node*node[MAX_NUMNODES];/*每個NUMA節點都有一個kmem_cache_node*/
};

根據是否打開Slub Debug，next object指針可以有兩種方式放置，如果打開了Slub Debug，則采用指針外置式；反之，采用指針內置式。兩種指針放置方式如下圖：

• 指針外置式

• 指針內置式

指針內置式的方法實際上是復用了object的前8個字節，因為在object被分配出去之前，這一段內存具體存放什么內容并不重要，所以可以利用這一段內存來保存下一個free object的地址。

• kmem_cache_cpu

structkmem_cache_cpu{
/*指向下一個空閑的object，用于快速找到可用對象*/
void**freelist;/*Pointertonextavailableobject*/
/*
*要保證tid和kmem_cache是由同一個CPU訪問。
*開啟了內核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，
*所以要檢查是否匹配，直到它們是由同一個CPU進行訪問
*/
unsignedlongtid;/*Globallyuniquetransactionid*/
/*指向當前使用的slab*/
structpage*page;/*Theslabfromwhichweareallocating*/
/*指向當前cpu上緩存的部分空閑slab鏈表*/
structpage*partial;/*Partiallyallocatedfrozenslabs*/
#ifdefCONFIG_SLUB_STATS
/*
*記錄對slab操作的狀態變化，這個stat非常重要，
*通過這個stat就大概了解object從申請到釋放經過了哪些步驟
*/
unsignedstat[NR_SLUB_STAT_ITEMS];
#endif
};

• kmem_cache_node

structkmem_cache_node{
spinlock_tlist_lock;
/*此處省略掉SLAB的配置*/
#ifdefCONFIG_SLUB
/*掛入kmem_cache_node中的slab數量*/
unsignedlongnr_partial;
/*指向當前內存節點上的部分空閑slab鏈表*/
structlist_headpartial;
#ifdefCONFIG_SLUB_DEBUG
atomic_long_tnr_slabs;
atomic_long_ttotal_objects;
structlist_headfull;
#endif
#endif
};

page中描述Slub信息的字段：

structpage{
/*如果flag設置成PG_slab,表示頁屬于slub分配器*/
unsignedlongflags;
union{
structaddress_space*mapping;
/*指向當前slab中第一個object*/
void*s_mem;/*slabfirstobject*/
atomic_tcompound_mapcount;/*firsttailpage*/
};
union{
pgoff_tindex;/*Ouroffsetwithinmapping.*/
/*指向當前slab中第一個空閑的object*/
void*freelist;/*sl[aou]bfirstfreeobject*/
};
union{
unsignedcounters;
struct{
union{
atomic_t_mapcount;
unsignedintactive;/*SLAB*/
struct{/*SLUB*/
/*該slab中已經分配使用的object數量*/
unsignedinuse:16;
/*該slab中的所有object數量*/
unsignedobjects:15;
/*
*如果slab在kmem_cache_cpu中，表示處于凍結狀態；
*如果slab在kmem_cache_node的部分空閑slab鏈表中，表示處于解凍狀態
*/
unsignedfrozen:1;
};
intunits;/*SLOB*/
};
atomic_t_refcount;
};
};
union{
/*作為鏈表節點加入到kmem_cache_node的部分空閑slab鏈表中
structlist_headlru;/*Pageoutlist*/
structdev_pagemap*pgmap;
struct{/*slubpercpupartialpages*/
structpage*next;/*Nextpartialslab*/
intpages;/*Nrofpartialslabsleft*/
intpobjects;/*Approximate#ofobjects*/
};
structrcu_headrcu_head;
struct{
unsignedlongcompound_head;/*Ifbitzeroisset*/
unsignedintcompound_dtor;
unsignedintcompound_order;
};
};
union{
unsignedlongprivate;
structkmem_cache*slab_cache;/*SL[AU]B:Pointertoslab*/
};
......
}

Slub的分配過程

Slub的分配流程大致如下：首先從kmem_cache_cpu中分配，如果沒有則從kmem_cache_cpu的partial鏈表分配，如果還沒有則從kmem_cache_node中分配，如果kmem_cache_node中也沒有，則需要向伙伴系統申請內存。

Slub的分配接口是kmem_cache_malloc()。其分配object的流程大概如下：首先在kmem_cache_cpu所使用的slab中查找free object，如果當前slab中有free object，則返回這個object。如果當前slab沒有free object，就要看Slub是否開啟了kmem_cache_cpu的Partial隊列，如果開啟了partial隊列，就在Partial隊列中查看有沒有free object的slab，如果有的話就選定這個slab，并返回其free object。如果kmem_cache_cpu的partial鏈表中也沒有擁有free object的slab，則在kmem_cache_node中查找。如果kmem_cache_node中的slab有free object，則選定這個slab并返回free object。如果kmem_cache_node中也沒有free object，則需要向伙伴系統申請內存，制作新的slab。

創建slab緩存(kmem_cache)的函數分析

斗膽分析一下slab緩存的創建過程，新手小白分析內核代碼，分析的可能不夠深度和完整，如有不對還請各路高手指教，提前謝過。

函數調用流程：

kmem_cache_create()
——>kmem_cache_create_usercopy()
——>create_cache()
——>__kmem_cache_create()
——>kmem_cache_open()

下面是每個函數的主干分析，代碼有精簡。

kmem_cache_create()：

kmem_cache_create()里繼續調用了kmem_cache_create_usercopy()。

kmem_cache_create(){
returnkmem_cache_create_usercopy(name,size,align,flags,0,0,ctor);
}

kmem_cache_create_usercopy()：

kmem_cache_create_usercopy(){
structkmem_cache*s=NULL;
constchar*cache_name;

/*
*Someallocatorswillconstraintthesetofvalidflagstoasubset
*ofallflags.WeexpectthemtodefineCACHE_CREATE_MASKinthis
*case,andwe'lljustprovidethemwithasanitizedversionofthe
*passedflags.
*/
flags&=CACHE_CREATE_MASK;

/*定義這個緩存的名字，用于在/proc/slabinfo中顯示*/
cache_name=kstrdup_const(name,GFP_KERNEL);

/*kmem_cache結構，并返回其地址*/
s=create_cache(cache_name,size,
calculate_alignment(flags,align,size),
flags,useroffset,usersize,ctor,NULL,NULL);

returns;
}

create_cache()：

create_cache(){
structkmem_cache*s;
interr;

/*為kmem_cache結構申請一段內存并清零*/
s=kmem_cache_zalloc(kmem_cache,GFP_KERNEL);

/*初始化kmem_cache結構的部分成員*/
s->name=name;
s->size=s->object_size=object_size;
s->align=align;
s->ctor=ctor;
s->useroffset=useroffset;
s->usersize=usersize;

/*核心函數，slub/slab/slob都實現了這個函數*/
err=__kmem_cache_create(s,flags);

/*將新創建的kmem_cache加入slabcaches鏈表*/
list_add(&s->list,&slab_caches);

returns;
}

__kmem_cache_create()：

__kmem_cache_create(){
interr;

/*在kmem_cache_open中處理剩余的結構成員，如min_partial、cpu_partial等*/
err=kmem_cache_open(s,flags);
}

kmem_cache_open()：

kmem_cache_open(){
/*設置kmem_cache中的min_partial,它表示kmem_cache_node中partial鏈表可掛入的slab數量*/
set_min_partial(s,ilog2(s->size)/2);

/*設置kmem_cache中的cpu_partial,它表示percpupartial上所有slab中freeobject總數*/
set_cpu_partial(s);

/*為每個節點分配kmem_cache_node*/
if(!init_kmem_cache_nodes(s))
gotoerror;

/*為kmem_cache_cpu變量創建每CPU副本*/
if(alloc_kmem_cache_cpus(s))
return0;
}

分配對象(object)的函數分析

函數調用流程：

kmem_cache_alloc()
——>slab_alloc()
——>slab_alloc_node()
——>__slab_alloc()
——>___slab_alloc()

kmem_cache_alloc()：

kmem_cache_alloc(){
/*直接調用slab_alloc*/
void*ret=slab_alloc(s,gfpflags,_RET_IP_);

returnret;
}

slab_alloc()：

slab_alloc(){
returnslab_alloc_node(s,gfpflags,NUMA_NO_NODE,addr);
}

slab_alloc_node()：

slab_alloc_node(){
void*object;
structkmem_cache_cpu*c;
structpage*page;

redo:
/*
*要保證tid和kmem_cache是由同一個CPU訪問。但是如果配置了CONFIG_PREEMPT = y，
*即開啟了內核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，所以要檢查
*是否匹配，直到它們是由同一個CPU進行訪問。
*
*內核態搶占的時機是：
*1.中斷處理函數返回內核空間之前會檢查請求重新調度的標志(TIF_NEED_RESCHED)，
*如果置位則調用preempt_schedule_irq()執行搶占。
* 2. 當內核從non-preemptible(禁止搶占)狀態變成preemptible(允許搶占)的時候。
*/
do{
tid=this_cpu_read(s->cpu_slab->tid);/*訪問當前CPU的perCPU變量的副本的tid*/
c=raw_cpu_ptr(s->cpu_slab);
}while(IS_ENABLED(CONFIG_PREEMPT)&&/*檢查是否開啟了內核搶占*/
unlikely(tid!=READ_ONCE(c->tid)));

barrier();/*內存屏障，消除指令亂序執行的影響*/

object=c->freelist;/*下一個freeobject的地址*/
page=c->page;/*當前使用的slab*/
if(unlikely(!object||!node_match(page,node))){
/*調用核心函數__slab_alloc()*/
object=__slab_alloc(s,gfpflags,node,addr,c);
stat(s,ALLOC_SLOWPATH);
}else{
void*next_object=get_freepointer_safe(s,object);

if(unlikely(!this_cpu_cmpxchg_double(
s->cpu_slab->freelist,s->cpu_slab->tid,
object,tid,
next_object,next_tid(tid)))){

note_cmpxchg_failure("slab_alloc",s,tid);
gotoredo;
}
prefetch_freepointer(s,next_object);
stat(s,ALLOC_FASTPATH);
}

maybe_wipe_obj_freeptr(s,object);

/*如果gfpflags標志需要對object對象的內存清零*/
if(unlikely(slab_want_init_on_alloc(gfpflags,s))&&object)
memset(object,0,s->object_size);

slab_post_alloc_hook(s,gfpflags,1,&object);

returnobject;
}

__slab_alloc()：

__slab_alloc(){
void*p;
unsignedlongflags;

/*
*關中斷。關閉當前處理器上的所有中斷處理
*
*local_irq_save()將當前的中斷狀態(開或關)
*保存在flags中然后再禁用處理器上的中斷。
*
*與local_irq_save不同，local_irq_disable()
*不保存狀態而關閉本地處理器的中斷服務。
*/
local_irq_save(flags);
#ifdefCONFIG_PREEMPT
/*
*在關中斷之前，可能已經被搶占并被調度在不同的CPU上，
*所以需要重新加載CPU區域的指針。
*/
c=this_cpu_ptr(s->cpu_slab);
#endif
/*調用核心函數___slab_alloc()*/
p=___slab_alloc(s,gfpflags,node,addr,c);

/*
*恢復本地處理器的中斷。
*
*local_irq_restore()將local_irq_save()保存的狀態值(flags)恢復，
*注意是恢復之前的中斷狀態，不一定會開啟中斷。如果之前的狀態是
*開中斷，就打開中斷；如果之前的狀態是關中斷，就關閉中斷。
*而local_irq_enable()會無條件開啟中斷，所以可能會破壞之前的中
*斷環境。所以local_irq_restore()比local_irq_enable()更安全。
*/
local_irq_restore(flags);

returnp;
}

slub的frozen（凍結）和unfrozen（解凍）

如果cpu1的kcmem_cache_cpu的slab是frozen, 那么cpu1可以從該slab中取出或放回obj，但是cpu2不能從該slab中取obj, 只能把obj還給該slab。另外，cpu partial上的slab都是frozen狀態。node partial上的slab都是unfrozen。耗盡kmem_cache_cpu的slab的obj后解凍slab。