歡迎光臨
每天分享高質量文章

圖解slub

1.前言

Linux中,伙伴系統(buddy system)是以頁為單位管理和分配記憶體。但是現實的需求卻以位元組為單位,假如我們需要申請20Bytes,總不能分配一頁吧!那豈不是嚴重浪費記憶體。那麼該如何分配呢?slab分配器就應運而生了,專為小記憶體分配而生。slab分配器分配記憶體以Byte為單位。但是slab分配器並沒有脫離伙伴系統,而是基於伙伴系統分配的大記憶體進一步細分成小記憶體分配。

前段時間學習了下slab分配器工作原理。因為自己本身是做手機的,發現現在好像都在使用slub分配器,想想還是再研究一下slub的工作原理。之前看了代碼,感覺挺多資料結構和成員的。成員的意思是什麼?資料結構之間的關係是什麼?不知道你是否感覺雲里霧裡。既然代碼閱讀起來晦澀難懂,如果有精美的配圖,不知是否有助於閣下理解slub的來龍去脈呢?我想表達的意思就是文章圖多,圖多,圖多。我們只說原理,儘量不看代碼。因為所有代碼中包含的內容我都會用圖來說明。你感興趣絕對有助於你看代碼。

說明:slubslab中的一種,slab也是slab中的一種。有時候用slab來統稱slab, slubslobslab, slubslob僅僅是分配記憶體策略不同。本篇文章中說的是slub分配器工作的原理。但是針對分配器管理的記憶體,下文統稱為slab快取池。所以文章中slubslab會混用,表示同一個意思。

註:文章代碼分析基於linux-4.15.0-rc3 圖片有點走形,請單獨點開圖片查看。

2. slub資料結構

slub的資料結構相對於slab來說要簡單很多。並且對外接口和slab兼容。所以說,從slab的系統更換到slub,可以說是易如反掌。

2.1. kmem_cache

現在假如從伙伴系統分配一頁記憶體供slub分配器管理。對於slub分配器來說,就是將這段連續記憶體平均分成若干大小相等的object(物件)進行管理。可是我們總得知道每一個objectsize吧!管理的記憶體頁數也是需要知道的吧!不然怎麼知道如何分配呢!因此需要一個資料結構管理。那就是struct kmem_cachekmem_cache資料結構描述如下:

  1. struct kmem_cache {
  2. struct kmem_cache_cpu __percpu *cpu_slab;
  3. /* Used for retriving partial slabs etc */
  4. slab_flags_t flags;
  5. unsignedlong min_partial;
  6. int size;/* The size of an object including meta data */
  7. int object_size;/* The size of an object without meta data */
  8. int offset;/* Free pointer offset. */
  9. #ifdef CONFIG_SLUB_CPU_PARTIAL
  10. int cpu_partial;/* Number of per cpu partial objects to keep around */
  11. #endif
  12. struct kmem_cache_order_objects oo;
  13. /* Allocation and freeing of slabs */
  14. struct kmem_cache_order_objects max;
  15. struct kmem_cache_order_objects min;
  16. gfp_t allocflags;/* gfp flags to use on each alloc */
  17. int refcount;/* Refcount for slab cache destroy */
  18. void(*ctor)(void*);
  19. int inuse;/* Offset to metadata */
  20. int align;/* Alignment */
  21. int reserved;/* Reserved bytes at the end of slabs */
  22. constchar*name;/* Name (only for display!) */
  23. structlist_head list;/* List of slab caches */
  24. struct kmem_cache_node *node[MAX_NUMNODES];
  25. };

1)     cpu_slab:一個per cpu變數,對於每個cpu來說,相當於一個本地記憶體快取池。當分配記憶體的時候優先從本地cpu分配記憶體以保證cache的命中率。

2)     flagsobject分配掩碼,例如經常使用的SLAB_HWCACHE_ALIGN標誌位,代表創建的kmem_cache管理的object按照硬體cache 對齊,一切都是為了速度。

3)     min_partial:限制struct kmem_cache_node中的partial鏈表slab的數量。雖說是mini_partial,但是代碼的本意告訴我這個變數是kmem_cache_nodepartial鏈表最大slab數量,如果大於這個mini_partial的值,那麼多餘的slab就會被釋放。

4)     size:分配的object size

5)     object_size:實際的object size,就是創建kmem_cache時候傳遞進來的引數。和size的關係就是,size是各種地址對齊之後的大小。因此,size要大於等於object_size

6)     offsetslub分配在管理object的時候採用的方法是:既然每個object在沒有分配之前不在乎每個object中儲存的內容,那麼完全可以在每個object中儲存下一個object記憶體首地址,就形成了一個單鏈表。很巧妙的設計。那麼這個地址資料儲存在object什麼位置呢?offset就是儲存下個object地址資料相對於這個object首地址的偏移。

7)     cpu_partialper cpu partial中所有slabfree object的數量的最大值,超過這個值就會將所有的slab轉移到kmem_cache_nodepartial鏈表。

8)     oo:低16位代表一個slab中所有object的數量(oo & ((1 << 16) – 1)),高16位代表一個slab管理的page數量((2^(oo  16)) pages)。

9)     max:看了代碼好像就是等於oo

10)  min:當按照oo大小分配記憶體的時候出現記憶體不足就會考慮min大小方式分配。min只需要可以容納一個object即可。

11)  allocflags:從伙伴系統分配記憶體掩碼。

12)  inuseobject_size按照word對齊之後的大小。

13)  align:位元組對齊大小。

14)  namesysfs檔案系統顯示使用。

15)  list:系統有一個slab_caches鏈表,所有的slab都會掛入此鏈表。

16)  nodeslab節點。在NUMA系統中,每個node都有一個struct kmem_cache_node資料結構。

2.2. kmem_cache_cpu

struct kmem_cache_cpu是對本地記憶體快取池的描述,每一個cpu對應一個結構體。其資料結構如下:

  1. struct kmem_cache_cpu {
  2. void**freelist;/* Pointer to next available object */
  3. unsignedlong tid;/* Globally unique transaction id */
  4. struct page *page;/* The slab from which we are allocating */
  5. #ifdef CONFIG_SLUB_CPU_PARTIAL
  6. struct page *partial;/* Partially allocated frozen slabs */
  7. #endif
  8. };

1)     freelist:指向下一個可用的object

2)     tid:一個神奇的數字,主要用來同步作用的。

3)     pageslab記憶體的page指標。

4)     partial:本地slab partial鏈表。主要是一些部分使用objectslab

2.3. kmem_cache_node

slab節點使用struct kmem_cache_node結構體描述。對於slub分配器來說,成員很少,遠比slab分配器簡潔。

  1. struct kmem_cache_node {
  2. spinlock_tlist_lock;
  3. unsignedlong nr_partial;
  4. structlist_head partial;
  5. };

1)     list_lock:自旋鎖,保護資料。

2)     nr_partialslab節點中slab的數量。

3)     partialslab節點的slab partial鏈表,和struct kmem_cache_cpupartial鏈表功能類似。

2.4. slub接口

瞭解了基本的資料結構,再來看看slub提供的API。如果你瞭解slub,我想這幾個接口你是再熟悉不過了。

  1. struct kmem_cache *kmem_cache_create(constchar*name,
  2. size_t size,
  3. size_t align,
  4. unsignedlong flags,
  5. void(*ctor)(void*));
  6. void kmem_cache_destroy(struct kmem_cache *);
  7. void*kmem_cache_alloc(struct kmem_cache *cachep,int flags);
  8. void kmem_cache_free(struct kmem_cache *cachep,void*objp);

1) kmem_cache_create是創建kmem_cache資料結構,引數描述如下:

    namekmem_cache的名稱

    size slab管理物件的大小

    alignslab分配器分配記憶體的對齊位元組數(align位元組對齊)

    flags:分配記憶體掩碼

    ctor :分配物件的構造回呼函式

2) kmem_cache_destroy作用和kmem_cache_create相反,就是銷毀創建的kmem_cache

3) kmem_cache_alloc是從cachep引數指定的kmem_cache管理的記憶體快取池中分配一個物件,其中flags是分配掩碼,GFP_KERNEL是不是很熟悉的掩碼?

4) kmem_cache_freekmem_cache_alloc的反操作

slab分配器提供的接口該如何使用呢?其實很簡單,總結分成以下幾個步驟:

1) kmem_cache_create創建一個kmem_cache資料結構。

2) 使用kmem_cache_alloc接口分配記憶體,kmem_cache_free接口釋放記憶體。

3) release第一步創建的kmem_cache資料結構。

再來一段demo示例代碼就更好了。

  1. /*
  2. * This is a demo for how to use kmem_cache_create
  3. */
  4. void slab_demo(void)
  5. {
  6. struct kmem_cache *kmem_cache_16 = kmem_cache_create(“kmem_cache_16”,16,
  7. 8, ARCH_KMALLOC_FLAGS,
  8.            NULL);
  9.  
  10. /* now you can alloc memory, the buf points to 16 bytes of memory*/
  11. char*buf = kmeme_cache_alloc(kmem_cache_16, GFP_KERNEL);
  12.  
  13. /*
  14.     * do something what you what, don’t forget to release the memory after use
  15. */
  16.    kmem_cache_free(kmem_cache_16, buf);
  17.  
  18.    kmem_cache_destroy(kmem_cache_16);

  1. }

1) 首先使用kmem_cache_create創建名稱為kmem_cache_16kmem_cache,該kmem_cache主要是描述如何管理一堆物件,其實就是slab的佈局。每個物件都是16位元組,並且分配的物件地址按照8位元組對齊,也就是說從kmem_cache_16中分配的物件大小全是16位元組。不管你要申請多少,反正就是16Bytes。當然,kmem_cache_create僅僅是創建了一個描述slab快取池佈局的資料結構,並沒有從伙伴系統申請記憶體,具體的申請記憶體操作是在kmeme_cache_alloc中完成的。

2) kmeme_cache_allockmem_cache_16分配一個物件。

3) 記憶體使用結束記得kmem_cache_free釋放。

4) 如果不需要這個kmem_cache的話,就可以呼叫kmem_cache_destroy進行銷毀吧。在釋放kmem_cache之前要保證從該kmem_cache中分配的物件全部釋放了,否則無法釋放kmem_cache

3. slub資料結構之間關係

什麼是slab快取池呢?我的解釋是使用struct kmem_cache結構描述的一段記憶體就稱作一個slab快取池。一個slab快取池就像是一箱牛奶,一箱牛奶中有很多瓶牛奶,每瓶牛奶就是一個object。分配記憶體的時候,就相當於從牛奶箱中拿一瓶。總有拿完的一天。當箱子空的時候,你就需要去超市再買一箱回來。超市就相當於partial鏈表,超市儲存著很多箱牛奶。如果超市也賣完了,自然就要從廠家進貨,然後出售給你。廠家就相當於伙伴系統。

說了這麼多終於要丟擲辛辛苦苦畫的美圖了。

好了,後面說的大部分內容請看這張圖。足以表明資料結構之間的關係了。看懂了這張圖,就可以理清資料結構之間的關係了。

3.1. slub管理object方法

在圖片的左上角就是一個slub快取池中object的分佈以及資料結構和kmem_cache之間的關係。首先一個slab快取池包含的頁數是由oo決定的。oo拆分為兩部分,低16位代表一個slab快取池中object的數量,高16位代表包含的頁數。使用kmem_cache_create()接口創建kmem_cache的時候需要指出objsize和對齊align。也就是傳入的引數。kmem_cache_create()主要是就是填充kmem_cache結構體成員。既然從伙伴系統得到(2^(oo >> 16)) pages大小記憶體,按照size大小進行平分。一般來說都不會整除,因此剩下的就是圖中灰色所示。由於每一個object的大小至少8位元組,當然可以用來儲存下一個object的首地址。就像圖中所示的,形成單鏈表。圖中所示下個obj地址存放的位置位於每個obj首地址處,在內核中稱作指標內置式。同時,下個obj地址存放的位置和obj首地址之間的偏移儲存在kmem_cacheoffset成員。兩外一種方式是指標外置式,即下個obj的首地址儲存的位置位於obj尾部,也就是在obj尾部再分配sizeof(void *)位元組大小的記憶體。對於外置式則offset就等於kmem_cacheinuse成員。

3.2. per cpu freelist

針對每一個cpu都會分配一個struct kmem_cacche_cpu的結構體。可以稱作是本地快取池。當記憶體申請的時候,優先從本地cpu快取池申請。在分配初期,本地快取池為空,自然要從伙伴系統分配一定頁數的記憶體。內核會為每一個物理頁幀創建一個struct page的結構體。kmem_cacche_cpupage就會指向正在使用的slab的頁幀。freelist成員指向第一個可用記憶體obj首地址。處於正在使用的slabstruct page結構體中的freelist會置成NULL,因為沒有其他地方使用。struct page結構體中inuse代表已經使用的obj數量。這地方有個很有意思的地方,在剛從伙伴系統分配的slab inuse在分配初期就置成obj的總數,在分配obj的時候並不會改變。你是不是覺得很奇怪,既然表示已經使用obj的數量,為什麼一直是obj的總數呢?你想想,slab中的物件總有分配完的時候,那個時候就直接脫離kmem_cache_cpu了。此時的inuse不就名副其實了嘛!對於full slab就像圖的右下角,就像無人看管的孩子,沒有任何鏈表來管理。

3.3. per cpu partial

當圖中右下角full slab釋放obj的時候,首先就會將slab掛入per cpu partial鏈表管理。通過struct pagenext成員形成單鏈表。per cpu partial鏈表指向的第一個page中會存放一些特殊的資料。例如:pobjects儲存著per cpu partial鏈表中所有slab可供分配obj的總數,如圖所示。當然還有一個圖中沒有體現的pages成員儲存per cpu partial鏈表中所有slab快取池的個數pobjects到底有什麼用呢?我們從full slab中釋放一個obj就添加到per cpu partial鏈表,總不能無限制的添加吧!因此,每次添加的時候都會判斷當前的pobjects是否大於kmem_cachecpu_partial成員,如果大於,那麼就會將此時per cpu partial鏈表中所有的slab移送到kmem_cache_nodepartial鏈表,然後再將剛剛釋放objslab插入到per cpu partial鏈表。如果不大於,則更新pobjectspages成員,並將slab插入到per cpu partial鏈表。

3.4. per node partial

per node partia鏈表類似per cpu partial,區別是node中的slab是所有cpu共享的,而per cpu是每個cpu獨占的。假如現在的slab佈局如上圖所示。假如現在如紅色箭頭指向的obj將會釋放,那麼就是一個empty slab,此時判斷kmem_cache_nodenr_partial是否大於kmem_cachemin_partial,如果大於則會釋放該slab的記憶體。

4. slub分配記憶體原理

當呼叫kmem_cache_alloc()分配記憶體的時候,我們可以從正在使用slab分配,也可以從per cpu partial分配,同樣還可以從per node partial分配,那麼分配的順序是什麼呢?我們可以用下圖表示。

 

首先從cpu 本地快取池分配,如果freelist不存在,就會轉向per cpu partial分配,如果per cpu partial也沒有可用物件,繼續查看per node partial,如果很不幸也不沒有可用物件的話,就只能從伙伴系統分配一個slab了,並掛入per cpu freelist。我們詳細看一下這幾種情況。

1)     kmem_cache剛剛建立,還沒有任何物件可供分配,此時只能從伙伴系統分配一個slab,如下圖所示。

2)     如果正在使用的slabfree obj,那麼就直接分配即可,這種是最簡單快捷的。如下圖所示。

3)     隨著正在使用的slabobj的一個個分配出去,最終會無obj可分配,此時per cpu partial鏈表中有可用slab用於分配,那麼就會從per cpu partial鏈表中取下一個slab用於分配obj。如下圖所示。

4)     隨著正在使用的slabobj的一個個分配出去,最終會無obj可分配,此時per cpu partial鏈表也為空,此時發現per node partial鏈表中有可用slab用於分配,那麼就會從per node partial鏈表中取下一個slab用於分配obj。如下圖所示。

5. slub釋放記憶體原理

我們可以通過kmem_cache_free()接口釋放申請的obj物件。釋放物件的流程如下圖所示。

如果釋放的obj就是屬於正在使用cpu上的slab,那麼直接釋放即可,非常簡單;如果不是的話,首先判斷所屬slub是不是full狀態,因為full slab是沒媽的孩子,釋放之後就變成partial empty,急需要找個鏈表領養啊!這個媽就是per cpu partial鏈表。如果per cpu partial鏈表管理的所有slabfree object數量超過kmem_cachecpu_partial成員的話,就需要將per cpu partial鏈表管理的所有slab移動到per node partial鏈表管理;如果不是full slab的話,繼續判斷釋放當前obj後的slab是否是empty slab,如果是empty slab,那麼在滿足kmem_cache_nodenr_partial大於kmem_cachemin_partial的情況下,則會釋放該slab的記憶體。其他情況就直接釋放即可。

1)     假設下圖左邊的情況下釋放obj,如果滿足kmem_cache_nodenr_partial大於kmem_cachemin_partial的話,釋放情況如下圖所示。

2)     假設下圖左邊的情況下釋放obj,如果不滿足kmem_cache_nodenr_partial大於kmem_cachemin_partial的話,釋放情況如下圖所示。

3)     假設下圖從full slab釋放obj的話,如果滿足per cpu partial管理的所有slabfree object數量大於kmem_cachecpu_partial成員的話的話,將per cpu partial鏈表管理的所有slab移動到per node partial鏈表管理,釋放情況如下圖所示。

4)     假設下圖從full slab釋放obj的話,如果不滿足per cpu partial管理的所有slabfree object數量大於kmem_cachecpu_partial成員的話的話,釋放情況如下圖所示。

6. kmalloc

好了,說了這麼多,估計你會感覺slab好像跟我們沒什麼關係。如果作為一個驅動開發者,是不是感覺自己寫的driver從來沒有使用過這些接口呢?其實我們經常使用,只不過隱藏在kmalloc的面具之下。

kmalloc的記憶體分配就是基於slab分配器,在系統啟動初期呼叫create_kmalloc_caches ()創建多個管理不同大小物件的kmem_cache,例如:8B16B32B64B64MB等大小。當然預設配置情況下,系統系統啟動之後創建的最大size的kmem_cache是kmalloc-8192。因此,通過slab接口分配的最大記憶體是8192 bytes。那麼通過kmalloc接口申請的記憶體大於8192 bytes該怎麼辦呢?其實kmalloc會判斷申請的記憶體是否大於8192 bytes,如果大於的話就會通過alloc_pages接口申請記憶體。kmem_cache的名稱以及大小使用struct kmalloc_info_struct管理。所有管理不同大小物件的kmem_cache的名稱如下:

  1. conststruct kmalloc_info_struct kmalloc_info[] __initconst ={
  2. {NULL,0},{“kmalloc-96”,96},
  3. {“kmalloc-192”,192},{“kmalloc-8”,8},
  4. {“kmalloc-16”,16},{“kmalloc-32”,32},
  5. {“kmalloc-64”,64},{“kmalloc-128”,128},
  6. {“kmalloc-256”,256},{“kmalloc-512”,512},
  7. {“kmalloc-1024”,1024},{“kmalloc-2048”,2048},
  8. {“kmalloc-4096”,4096},{“kmalloc-8192”,8192},
  9. {“kmalloc-16384”,16384},{“kmalloc-32768”,32768},
  10. {“kmalloc-65536”,65536},{“kmalloc-131072”,131072},
  11. {“kmalloc-262144”,262144},{“kmalloc-524288”,524288},
  12. {“kmalloc-1048576”,1048576},{“kmalloc-2097152”,2097152},
  13. {“kmalloc-4194304”,4194304},{“kmalloc-8388608”,8388608},
  14. {“kmalloc-16777216”,16777216},{“kmalloc-33554432”,33554432},
  15. {“kmalloc-67108864”,67108864}
  16. };

經過create_kmalloc_caches ()函式之後,系統通過create_kmalloc_cache()創建以上不同sizekmem_cache,並將這些kmem_cache儲存在kmalloc_caches全域性變數中以備後續kmalloc分配記憶體。現在假如通過kmalloc(17, GFP_KERNEL)申請記憶體,系統會從名稱“kmalloc-32”管理的slab快取池中分配一個物件。即使浪費了15Byte

我們來看看kmalloc的實現方式。

  1. static __always_inline void*kmalloc(size_t size,gfp_t flags)
  2. {
  3. if(__builtin_constant_p(size)){
  4. if(size > KMALLOC_MAX_CACHE_SIZE)
  5. return kmalloc_large(size, flags);
  6. if(!(flags & GFP_DMA)){
  7. int index = kmalloc_index(size);
  8. if(!index)
  9. return ZERO_SIZE_PTR;
  10. return kmem_cache_alloc_trace(kmalloc_caches[index], flags, size);
  11. }
  12. }
  13. return __kmalloc(size, flags);
  14. }

1)     __builtin_constant_pgcc工具用來判斷引數是否是一個常數,畢竟有些操作對於常數來說是可以優化的。

2)     通過kmalloc_index函式查找符合滿足分配大小的最小kmem_cache

3)     index作為下表從kmalloc_caches陣列中找到符合的kmem_cache,並從slab快取池中分配物件。

我們再看一下kmalloc_index的實現。

  1. static __always_inline int kmalloc_index(size_t size)
  2. {
  3. if(!size)
  4. return0;
  5. if(size <= KMALLOC_MIN_SIZE)
  6. return KMALLOC_SHIFT_LOW;
  7. if(KMALLOC_MIN_SIZE <=32&& size >64&& size <=96)
  8. return1;
  9. if(KMALLOC_MIN_SIZE <=64&& size >128&& size <=192)
  10. return2;
  11. if(size <=8)return3;
  12. if(size <=16)return4;
  13. if(size <=32)return5;
  14. if(size <=64)return6;
  15. if(size <=128)return7;
  16. if(size <=256)return8;
  17. if(size <=512)return9;
  18. if(size <=1024)return10;
  19. if(size <=2*1024)return11;
  20. if(size <=4*1024)return12;
  21. if(size <=8*1024)return13;
  22. if(size <=16*1024)return14;
  23. if(size <=32*1024)return15;
  24. if(size <=64*1024)return16;
  25. if(size <=128*1024)return17;
  26. if(size <=256*1024)return18;
  27. if(size <=512*1024)return19;
  28. if(size <=1024*1024)return20;
  29. if(size <=2*1024*1024)return21;
  30. if(size <=4*1024*1024)return22;
  31. if(size <=8*1024*1024)return23;
  32. if(size <=16*1024*1024)return24;
  33. if(size <=32*1024*1024)return25;
  34. if(size <=64*1024*1024)return26;
  35. /* Will never be reached. Needed because the compiler may complain */
  36. return1;
  37. } 

  1.  

 

    閱讀原文

    赞(0)

    分享創造快樂