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

slub分配器

概述

        Linux的物理記憶體管理採用了以頁為單位的buddy system(夥伴系統),但是很多情況下,核心僅僅需要一個較小的物件空間,而且這些小塊的空間對於不同物件又是變化的、不可預測的,所以需要一種類似使用者空間堆記憶體的管理機制(malloc/free)。然而核心對物件的管理又有一定的特殊性,有些物件的訪問非常頻繁,需要採用緩衝機制;物件的組織需要考慮硬體cache的影響;需要考慮多處理器以及NUMA架構的影響。90年代初期,在Solaris 2.4作業系統中,採用了一種稱為“slab”(原意是大塊的混凝土)的緩衝區分配和管理方法,在相當程度上滿足了內核的特殊需求。

        多年以來,SLAB成為linux kernel物件緩衝區管理的主流演演算法,甚至長時間沒有人願意去修改,因為它實在是非常複雜,而且在大多數情況下,它的工作完成的相當不錯。但是,隨著大規模多處理器系統和 NUMA系統的廣泛應用,SLAB 分配器逐漸暴露出自身的嚴重不足:

1). 快取佇列管理複雜;

2). 管理資料儲存開銷大;

3). 對NUMA支援複雜;

4). 除錯調優困難;

5). 摒棄了效果不太明顯的slab著色機制;

        針對這些SLAB不足,核心開發人員Christoph Lameter在Linux核心2.6.22版本中引入一種新的解決方案:SLUB分配器。SLUB分配器特點是簡化設計理念,同時保留SLAB分配器的基本思想:每個緩衝區由多個小的slab 組成,每個 slab 包含固定數目的物件。SLUB分配器簡化kmem_cache,slab等相關的管理資料結構,摒棄了SLAB 分配器中眾多的佇列概念,並針對多處理器、NUMA系統進行最佳化,從而提高了效能和可擴充套件性並降低了記憶體的浪費。為了保證核心其它模組能夠無縫遷移到SLUB分配器,SLUB還保留了原有SLAB分配器所有的介面API函式。

(註:本文原始碼分析基於linux-4.1.x)

        整體資料結構關係如下圖所示:

1 SLUB分配器的初始化

        SLUB初始化有兩個重要的工作:第一,建立用於申請struct kmem_cache和struct kmem_cache_node的kmem_cache;第二,建立用於常規kmalloc的kmem_cache。

    1.1 申請kmem_cache的kmem_cache

        第一個工作涉及到一個“先有雞還是先有蛋”的問題,因為建立kmem_cache需要從kmem_cache的緩衝區申請,而這時候還沒有建立kmem_cache的緩衝區。kernel的解決辦法是先用兩個靜態變數boot_kmem_cache和boot_kmem_cache_node來儲存struct kmem_cach和struct kmem_cache_node緩衝區管理資料,以兩個靜態變數為基礎申請大小為struct kmem_cache和struct kmem_cache_node物件大小的slub緩衝區,隨後再從這些緩衝區中分別申請兩個kmem_cache,然後把boot_kmem_cache和boot_kmem_cache_node中的內容複製到新申請的物件中,從而完成了struct kmem_cache和struct kmem_cache_node管理結構的bootstrap(自引導)。

  1. void __init kmem_cache_init(void)
  2. {
  3. //宣告靜態變數,儲存臨時kmem_cache管理結構
  4. static __initdata struct kmem_cache boot_kmem_cache,
  5. boot_kmem_cache_node;
  6. •••
  7. kmem_cache_node =&boot_kmem_cache_node;
  8. kmem_cache =&boot_kmem_cache;
  9.  
  10. //申請slub緩衝區,管理資料放在臨時結構中
  11. create_boot_cache(kmem_cache_node,“kmem_cache_node”,
  12. sizeof(struct kmem_cache_node), SLAB_HWCACHE_ALIGN);
  13. create_boot_cache(kmem_cache,“kmem_cache”,
  14. offsetof(struct kmem_cache, node)+
  15. nr_node_ids *sizeof(struct kmem_cache_node *),
  16. SLAB_HWCACHE_ALIGN);
  17.  
  18. //從剛才掛在臨時結構的緩衝區中申請kmem_cache的kmem_cache,並將管理資料複製到新申請的記憶體中
  19. kmem_cache = bootstrap(&boot_kmem_cache);
  20.  
  21. //從剛才掛在臨時結構的緩衝區中申請kmem_cache_node的kmem_cache,並將管理資料複製到新申請的記憶體中
  22. kmem_cache_node = bootstrap(&boot_kmem_cache_node);
  23. •••
  24. }

    1.2 建立kmalloc常規快取

        原則上系統會為每個2次冪大小的記憶體塊申請一個快取,但是記憶體塊過小時,會產生很多碎片浪費,所以系統為96B和192B也各自建立了一個快取。於是利用了一個size_index陣列來幫助確定小於192B的記憶體塊使用哪個快取

  1. void __init create_kmalloc_caches(unsignedlong flags)
  2. {
  3. •••
  4. /*使用SLUB時KMALLOC_SHIFT_LOW=3,KMALLOC_SHIFT_HIGH=13
  5. 也就是說使用kmalloc能夠申請的最小記憶體是8B,最大記憶體是8KB
  6. 申請記憶體是向上對其2的n次冪,建立對應大小快取儲存在kmalloc_caches [n]*/
  7. for(i = KMALLOC_SHIFT_LOW; i <= KMALLOC_SHIFT_HIGH; i++){
  8. if(!kmalloc_caches[i]){
  9. kmalloc_caches[i]= create_kmalloc_cache(NULL,
  10. 1<< i, flags);
  11. }
  12.  
  13. /*
  14. * Caches that are not of the two-to-the-power-of size.
  15. * These have to be created immediately after the
  16. * earlier power of two caches
  17. */
  18. /*有兩個例外,大小為64~96B和128B~192B,單獨建立了兩個快取
  19. 儲存在kmalloc_caches [1]和kmalloc_caches [2]*/
  20. if(KMALLOC_MIN_SIZE <=32&&!kmalloc_caches[1]&& i ==6)
  21. kmalloc_caches[1]= create_kmalloc_cache(NULL,96, flags);
  22.  
  23. if(KMALLOC_MIN_SIZE <=64&&!kmalloc_caches[2]&& i ==7)
  24. kmalloc_caches[2]= create_kmalloc_cache(NULL,192, flags);
  25. }
  26. •••
  27. }

快取的建立與銷毀

    2.1 快取的建立

        建立快取透過介面kmem_cache_create進行,在建立新的快取以前,嘗試找到可以合併的快取,合併條件包括對物件大小以及快取屬性的判斷,如果可以合併則直接傳回已存在的kmem_cache,並建立一個kobj連結指向同一個節點。

        建立新的快取主要是申請管理結構暫用的空間,並初始化,這些管理結構包括kmem_cache、kmem_cache_nodes、kmem_cache_cpu。同時在sysfs建立kobject節點。最後把kmem_cache加入到全域性cahce連結串列slab_caches中。

    2.2 快取的銷毀

        銷毀過程比建立過程簡單的多,主要工作是釋放partial佇列所有page,釋放kmem_cache_cpu,釋放每個node的kmem_cache_node,最後釋放kmem_cache本身。

申請物件

        物件是SLUB分配器中可分配的記憶體單元,與SLAB相比,SLUB物件的組織非常簡潔,申請過程更加高效。SLUB沒有任何管理區結構來管理物件,而是將物件之間的關聯嵌入在物件本身的記憶體中,因為申請者並不關心物件在分配之前記憶體的內容是什麼。而且各個SLUB之間的關聯,也利用page自身結構進行處理。

        每個CPU都有一個slab作為本地高速快取,只要slab所在的node與申請者要求的node匹配,同時該slab還有空閑物件,則直接在cpu_slab中取出空閑物件,否則就進入慢速路徑。

        每個物件記憶體的offset偏移位置都存放著下一個空閑物件,offset通常為0,也就是復用物件記憶體的第一個字來儲存下一個空閑物件的指標,當滿足條件(flags & (SLAB_DESTROY_BY_RCU | SLAB_POISON)) 或者有物件建構式時,offset不為0,每個物件的結構如下圖。

        cpu_slab的freelist則儲存著當前第一個空閑物件的地址。

        如果本地CPU快取沒有空閑物件,則申請新的slab;如果有空閑物件,但是記憶體node不相符,則deactive當前cpu_slab,再申請新的slab

        deactivate_slab主要進行兩步工作:

        第一步,將cpu_slab的freelist全部釋放回page->freelist;

        第二部,根據page(slab)的狀態進行不同操作,如果該slab有部分空閑物件,則將page移到kmem_cache_node的partial佇列;如果該slab全部空閑,則直接釋放該slab;如果該slab全部佔用,而且開啟了CONFIG_SLUB_DEBUG編譯選項,則將page移到full佇列。

        page的狀態也從frozen改變為unfrozen。(frozen代表slab在cpu_slub,unfroze代表在partial佇列或者full佇列)。

        申請新的slab有兩種情況,如果cpu_slab的partial佇列不為空,則取出佇列中下一個page作為新的cpu_slab,同時再次檢測記憶體node是否相符,還不相符則迴圈處理。

        如果cpu_slab的partial佇列為空,則檢視本node的partial佇列是否為空,如果不空,則取出page;如果為空,則看一定距離範圍內其它node的partial佇列,如果還為空,則需要建立新slab。

        建立新slab其實就是申請對應order的記憶體頁,用來放足夠數量的物件。值得註意的是其中order以及物件數量的確定,這兩者又是相互影響的。order和object數量同時存放在kmem_cache成員kmem_cache_order_objects中,低16位用於存放object數量,高位存放order。order與object數量的關係非常簡單:((PAGE_SIZE << order) – reserved) / size。

        下麵重點看calculate_order這個函式

  1. staticinlineint calculate_order(int size,int reserved)
  2. {
  3. •••
  4. //嘗試找到order與object數量的最佳配合方案
  5. //期望的效果就是剩餘的碎片最小
  6. min_objects = slub_min_objects;
  7. if(!min_objects)
  8. min_objects =4*(fls(nr_cpu_ids)+1);
  9. max_objects = order_objects(slub_max_order, size, reserved);
  10. min_objects = min(min_objects, max_objects);
  11.  
  12. //fraction是碎片因子,需要滿足的條件是碎片部分乘以fraction小於slab大小
  13. // (slab_size – reserved) % size <= slab_size / fraction
  14. while(min_objects >1){
  15. fraction =16;
  16. while(fraction >=4){
  17. order = slab_order(size, min_objects,
  18. slub_max_order, fraction, reserved);
  19. if(order <= slub_max_order)
  20. return order;
  21. //放寬條件,容忍的碎片大小增倍
  22. fraction /=2;
  23. }
  24. min_objects–;
  25. }
  26.  
  27. //嘗試一個slab只包含一個物件
  28. order = slab_order(size,1, slub_max_order,1, reserved);
  29. if(order <= slub_max_order)
  30. return order;
  31.  
  32. //使用MAX_ORDER且一個slab只含一個物件
  33. order = slab_order(size,1, MAX_ORDER,1, reserved);
  34. if(order < MAX_ORDER)
  35. return order;
  36. returnENOSYS;
  37. }

釋放物件

        從上面申請物件的流程也可以看出,釋放的object有幾個去處:

1)cpu本地快取slab,也就是cpu_slab;

2)放回object所在的page(也就是slab)中;另外要處理所在的slab:

    2.1)如果放回之後,slab完全為空,則直接銷毀該slab;

    2.2)如果放回之前,slab為滿,則判斷slab是否已被凍結;如果已凍結,則不需要做其他事;如果未凍結,則將其凍結,放入cpu_slab的partial佇列;如果cpu_slab partial佇列過多,則將佇列中所有slab一次性解凍到各自node的partial佇列中。

        值得註意的是cpu partial佇列的功能是個可選項,依賴於核心選項CONFIG_SLUB_CPU_PARTIAL,如果沒有開啟,則不使用cpu partial佇列,直接使用各個node的partial佇列。

贊(0)

分享創造快樂