Linux內核內存管理之slab分配器

本文在行文的過程中，會多次提到cache或緩存的概念。如果沒有特殊在前面添加硬件的限定詞，就說明cache指的是slab分配器使用的軟件緩存的意思。如果添加了硬件限定詞，則指的是處理器的硬件緩存，比如L1-DCache、L1-ICache之類的。

本節我們討論memory area，一段具有連續物理地址和任意長度的內存。

buddy算法將頁幀作為最基本的memory area。這對于申請較大內存的請求是非常好的，但是，如果是很小的memory area請求，比如幾十或幾百字節，我們將如何處理呢？

很明顯，申請一個完整頁幀存儲幾十個字節是非常浪費資源的。如果引入新數據結構描述在同一個頁幀內如何分配memory area，會引入一個新問題：內部碎片。這是由于請求的內存大小和分配的memory area大小不匹配造成。

早期Linux內核就是采用這種經典方案是，提供大小成幾何分布的memory area；換句話說，大小是2的冪次方，而不是要存儲數據的實際大小。這樣的好處是，無論請求的內存是多少，我們都能保證內存碎片小于50%?；谶@種方法，內核創建了13個memory area列表，列表元素的大小從32 → 131072字節。這些列表還是用buddy系統申請內存頁幀，或釋放不再包含memory area的頁幀。使用一個動態列表追蹤每個頁幀內的自由memory area數量。

1 slab分配器

在buddy系統之上運行前述的memory area分配算法不是特別有效。在Sun Microsystems Solaris 2.4操作系統中首次引入的slab分配器方案給出了一種更好地算法：

存儲的數據類型影響memory area的分配方式（類似C++語言中的類的概念，也就是面向對象的編程思想）。例如，給用戶態進程申請分配一個頁幀，內核會調用get_zeroed_page()函數，將該頁填充為0。

slab分配器擴展了該思想，將memory area視為對象，該對象由一組數據結構和一對函數組成，這對函數又稱為構造函數和析構函數。前者初始化memory area，而后者負責解除初始化。

為了避免重復初始化對象，slab分配器不會丟棄已經申請但要釋放的對象，而是將其保存在內存中。當申請新對象時，直接從內存中獲取，而無需重新初始化。

內核往往重復地申請相同類型的memory area（建立cache，重復利用）。比如，當內核創建一個新進程時，它會分配一些固定大小的memory area，每組固定大小的memory area組成一張表，用來保存進程描述符、打開的文件對象等等。當進程結束時，這些memory area以及管理它們的表能夠被重復利用。因為進程的創建和銷毀是很頻繁的，如果沒有slab分配器，內核就會浪費時間重復地分配和釋放包含相同大小memory area的頁幀；而slab分配器，將它們保存在緩存中，可以快速的重復利用。

memory area的申請可以按照它們的使用頻率來分類。通過創建一組具有合適大小的專用對象，可以有效處理預期特定大小的內存申請，從而避免內部碎片。同時，對于很少遇見的大小，可以按照幾何分布大?。ɡ?，2的冪次方）的對象進行處理，盡管這種方法仍然會導致內部碎片的產生。

引入大小不是幾何分布的對象還有一個微妙的好處：內核數據結構的首地址往往不是以2的冪次方大小分布的物理地址上。（通俗地講，就是數據結構的首地址不太可能正好落在2的冪次方大小的地址上）。因此，輔以硬件cache，可以產生更好的性能。

硬件cache性能是限制盡可能少地調用伙伴關系分配器的另一個原因（頻繁調用buddy系統，會降低系統性能）。每次調用伙伴關系系統，都會弄臟硬件cache，也就會增加平均內存訪問時間。內核函數對硬件cache的影響被稱為函數占用空間；它被定義為當該函數終止后，覆蓋的cache百分比。很明顯，越大的占用空間比會導致該函數之后的代碼執行越慢，因為此時的硬件cache需要重新讀取內存，填充自己。

slab分配器將對象分組保存到cache中，每個cache保存了相同類型的對象。比如，打開一個文件，為了保存打開的文件這個對象，就會從slab分配器的filp緩存對象中（文件指針的意思），申請memory area。

包含一個cache的memory area被分成很多個slab；每個slab包含一個或多個連續的頁幀，這些頁幀用來保存已經分配的對象和自由空閑的對象。如下圖所示：

內核會周期性地掃描這些cache，釋放掉那些空slab占用的頁幀。

2 cache描述符

描述cache的數據類型是kmem_cache_t（等價于struct kmem_cache_s），各字段如下表所示。其中，忽略了收集統計信息和調試的幾個字段。

表8-8kmem_cache_t的各個字段

類型	名稱	描述
struct array_cache*[]	array	Per-CPU數組，包含指向本地的那些cache
unsigned int	batchcount	與本地cache傳送的對象數量
unsigned int	limit	本地cache中空閑對象的最大數量。這是可調的
struct kmem_list3	lists	見下表
unsigned int	objsize	cache中對象的大小
unsigned int	flags	描述cache永久屬性的一些標志集
unsigned int	num	單個slab中的對象數量（同一cache中slab大小相同）
unsigned int	free_limit	整個slab cache中自由空閑對象的上限
spinlock_t	spinlock	保護cache的自旋鎖
unsigned int	gfporder	單個slab中連續頁幀數量的對數
unsigned int	gfpflags	申請分配頁幀時傳遞給伙伴關系函數的標志組合
size_t	colour	slab顏色數量
unsigned int	colour_off	slab中基本對齊偏移量
unsigned int	colour_next	用于下一個slab的顏色
kmem_cache_t *	slabp_cache	指向通用slab cache的指針，該cache包含slab描述符 （如果其內部的slab描述符已經被使用，則為NULL）
unsigned int	slab_size	單個slab的大小
unsigned int	dflags	描述cache的動態屬性的標志集
void *	ctor	指向與cache相關聯的構造函數方法的指針
void *	dtor	指向與cache相關聯的析構函數方法的指針
const char *	name	保存cache名稱的字符數組
struct list_head	next	cache描述符的雙向鏈表的指針

lists字段參見下表。

表8-9kmem_list3結構體的各個字段

類型	名稱	描述
struct list_head	slabs_partial	slab描述符（包含自由和非自由對象）的雙向循環鏈表
struct list_head	slabs_full	slab描述符（包含非自由對象）的雙向循環鏈表
struct list_head	slabs_free	slab描述符（包含自由對象）的雙向循環鏈表
unsigned long	free_objects	cache中自由對象的數量
int	free_touched	slab分配器的頁回收算法使用
unsigned long	next_reap	slab分配器的頁回收算法使用
struct array_cache *	shared	指向所有CPU共享的本地cache

3 slab描述符

cache中的每一個slab都有自己的描述符，其各字段描述，如下表所示：

類型	名稱	描述
struct list_head	list	指向三個slab描述符的雙向鏈表之一。 也就是cache描述符的kmem_list3中的列表 （slabs_full、slabs_partial、slabs_free）
unsigned long	colouroff	該slab中第一個對象的偏移量（跟染色有關）
void *	s_mem	該slab中第一個對象的地址
unsigned int	inuse	該slab中當前使用的對象數量（非自由）
unsigned int	free	該slab中下一個自由對象的索引， 如果沒有自由對象則等于BUFCTL_END

slab描述符有兩個存儲的地方：

外部slab描述符

存儲在該slab之外，通用緩存之一中（由cache_sizes指向）。

內部slab描述符

存儲在該slab之內內，也就是分配給slab的第一個頁幀的開頭處。

當對象的大小小于512MB時，或者當內部碎片在slab內為slab描述符和對象描述符留出足夠的空間時，slab分配器選擇第二種解決方案。如果slab描述符存儲在slab之外，則cache描述符的flags字段中的CFLGS_OFF_SLAB標志被設置為1；否則它將被設置為0。

下圖展示了cache和slab描述符的主要關系。已經使用的slab，部分使用的slab和未使用的slab，它們使用不同鏈表串聯起來。

4 通用和特殊cache

cache可以分為兩類：通用和特殊。通用cache僅由slab分配器使用，而特殊cache由內核其它部分使用。

通用cache包含：

第一個cache稱為kmem_cache，它的對象都是內核中其余cache的描述符。cache_cache變量保存著這個特殊cache的描述符。

一些包含通用memory area的cache。這些內存區域范圍是13個呈幾何分布的內存大小。內核中有一個表malloc_sizes（一個數組，數據類型是cache_sizes），它指向26個通用cache描述符，這些cache的大小是32、64、128、256、512、1024、2048、4096、8192、16384、32768、65536、131072字節。對于每種大小，都有兩種cache：一種適用于ISA DMA分配，另一種適用于普通內存分配。

系統初始化的時候，調用函數kmem_cache_init()建立通用cache。

特殊cache都是調用kmem_cache_create()函數創建的。依據傳參，該函數首先檢查處理新cache的最佳方式（例如，slab描述符位于slab內部還是外部）。然后從cache_cache通用緩存中分配新的cache描述符，并將其插入到一個cache描述符的鏈表cache_chain中（插入操作使用cache_chain_sem信號量進行保護，避免競態條件發生）。

從cache_chain鏈表中銷毀和移除一個cache，可以調用kmem_cache_destroy()。此函數對于那些在加載時創建cache，卸載時銷毀cache的模塊非常有用。為了避免浪費內存空間，內核必須在銷毀cache本身之前，需要銷毀所有的slab。而kmem_cache_shrink()函數正好可以通過調用slab_destroy()迭代銷毀所有slab。

不管是通用還是特殊cache，都可以讀取/proc/slabinfo獲取其名稱；該文件還指定了每個cache中自由對象、已分配對象的數量。

# name                 : tunables  
#  : slabdata   
isofs_inode_cache     72     72    656   24    4 : tunables    0    0    0 : slabdata      3      3      0
nf_conntrack         175    175    320   25    2 : tunables    0    0    0 : slabdata      7      7      0
au_finfo               0      0    192   21    1 : tunables    0    0    0 : slabdata      0      0      0
au_icntnr              0      0    832   39    8 : tunables    0    0    0 : slabdata      0      0      0
au_dinfo               0      0    192   21    1 : tunables    0    0    0 : slabdata      0      0      0
ovl_inode             69     69    688   23    4 : tunables    0    0    0 : slabdata      3      3      0
kvm_async_pf           0      0    136   30    1 : tunables    0    0    0 : slabdata      0      0      0
kvm_vcpu               0      0  17152    1    8 : tunables    0    0    0 : slabdata      0      0      0
...省略(內核數據對象使用)
pool_workqueue      1393   1568    256   32    2 : tunables    0    0    0 : slabdata     49     49      0
radix_tree_node    13253  14896    584   28    4 : tunables    0    0    0 : slabdata    532    532      0
task_group           275    275    640   25    4 : tunables    0    0    0 : slabdata     11     11      0
vmap_area           3584   3584     64   64    1 : tunables    0    0    0 : slabdata     56     56      0
dma-kmalloc-8k         0      0   8192    4    8 : tunables    0    0    0 : slabdata      0      0      0
...省略
dma-kmalloc-8          0      0      8  512    1 : tunables    0    0    0 : slabdata      0      0      0
dma-kmalloc-192        0      0    192   21    1 : tunables    0    0    0 : slabdata      0      0      0
dma-kmalloc-96         0      0     96   42    1 : tunables    0    0    0 : slabdata      0      0      0
...省略
kmalloc-rcl-16         0      0     16  256    1 : tunables    0    0    0 : slabdata      0      0      0
kmalloc-rcl-8          0      0      8  512    1 : tunables    0    0    0 : slabdata      0      0      0
kmalloc-8k           168    168   8192    4    8 : tunables    0    0    0 : slabdata     42     42      0
kmalloc-4k          3832   3856   4096    8    8 : tunables    0    0    0 : slabdata    482    482      0
...省略
kmalloc-16          9472   9472     16  256    1 : tunables    0    0    0 : slabdata     37     37      0
kmalloc-8          12288  12288      8  512    1 : tunables    0    0    0 : slabdata     24     24      0
kmem_cache_node     2432   2432     64   64    1 : tunables    0    0    0 : slabdata     38     38      0
kmem_cache          2239   2340    448   36    4 : tunables    0    0    0 : slabdata     65     65      0

5 slab分配器和zone分配器的關系

前面我們知道，cache的頁幀分配是在初始化時就完成的。而slab分配器創建新slab時，則需要zone分配器獲取一組空閑且連續的物理內存（不會分配高端內存）。因此，需要調用kmem_getpages()函數，在UMA系統上，實現大概如下所示：

void * kmem_getpages(kmem_cache_t *cachep, int flags)
{
    struct page *page;
    int i;

    flags   |= cachep->gfpflags;
    page    = alloc_pages(flags, cachep->gfporder);
    if (!page)
        return NULL;
    i = (1 << cache->gfporder);
    if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
        atomic_add(i, &slab_reclaim_pages);
    while (i--)
        SetPageSlab(page++);
    return page_address(page);
}

參數說明：

cachep

指向需要額外頁幀的cache描述符的指針（所需頁幀數量由cachep->gfporder字段中的階數決定）。

flags

指定如何請求頁幀（參見Zone分配器）。這個標志與cache描述符中保存的標志組合使用。

內存分配請求的大小由緩存描述符的gfporder字段指定，該字段決定了緩存中slab的大小。如果slab cache設置了SLAB_RECLAIM_ACCOUNT標志，當內核檢查是否有足夠的內存來滿足一些用戶請求時，分配給slab的頁幀將被視為可回收頁。該函數還在分配的頁幀的頁描述符中設置PG_slab標志。

釋放slab頁幀時，調用kmem_freepages()函數：

    void kmem_freepages(kmem_cache_t *cachep, void *addr)
    {
        unsigned long i = (1 << cachep->gfporder);
        struct page *page = virt_to_page(addr);

        if (current->reclaim_state)
            current->reclaim_state->reclaimed_slab += i;
        while (i--)
            ClearPageSlab(page++);
        free_pages((unsigned long) addr, cachep->gfporder);
        if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
            atomic_sub(1<gfporder, &slab_reclaim_pages);
    }

該函數釋放slab頁幀，從線性地址為addr的頁幀開始。如果當前進程正在執行內存回收(current->reclaim_state字段不是NULL)，reclaim_state->reclaimed_slab加上要釋放的頁幀數，由頁幀回收算法計算在內。此外，如果設置了SLAB_RECLAIM_ACCOUNT標志(見上文)，適當的減小slab_reclaim_pages，該變量用來記錄在內存不足時，分配給slab的頁幀有多少是空閑的。

6 分配slab給cache

剛創建的cache不包含slab，因此也就沒有任何空閑的對象。只有在滿足下面兩個條件時才會將slab分配給cache：

有新對象的分配請求時

cache沒有空閑對象時

slab分配器調用cache_grow()分配新的slab。具體的過程如下所示：

首先，調用kmem_getpages()從ZONE頁幀分配器獲取存儲slab所需的頁幀；

然后，調用alloc_slabmgmt()來獲取新的slab描述符。如果設置了cache描述符的CFLGS_OFF_SLAB標志，則從cache描述符的slabp_cache指向的通用緩存中分配slab描述符；否則，將在slab的第1個頁幀中分配slab描述符。

對于給定的頁幀，內核必須能夠確定它是否被slab分配器使用，如果是，則必須能夠快速導出相應cache和slab描述符的地址。因此，cache_grow()掃描分配給新slab的頁幀的所有頁描述符，并分別使用cache和slab描述符的地址加載page描述符中lru字段的next和prev字段。這是正確的，因為lru字段僅在頁幀空閑時由buddy伙伴系統使用，而由slab分配器處理的頁幀設置了PG_slab標志，對buddy伙伴系統而言不是空閑的。相反的問題：對于給定的slab，哪些是實現它的頁幀？可以通過使用slab描述符的s_mem字段（slab第一個頁幀的起始地址）和cache描述符的gfporder字段（slab大?。﹣泶_定。

接下來，cache_init_objs()，對slab所有對象調用構造函數；（也就是初始化所有對象）

最后，調用list_add_tail()將獲取的slab描述符（*slabp）添加到cache描述符（*cachep）中的空閑slab列表中，并更新空閑對象的計數：

    list_add_tail(&slabp->list, &cachep->lists->slabs_free);
    cachep->lists->free_objects += cachep->num;

7 從cache中釋放slab

銷毀slab分為兩種情況：

slab cache中有太多空閑的對象；

定時器函數周期性地檢查是否有完全未使用的slab需要釋放

銷毀過程的實現函數是slab_destroy()，銷毀slab并將對應的頁幀釋放回ZONE頁幀分配器：

    void slab_destroy(kmem_cache_t *cachep, slab_t *slabp)
    {
        /* 檢查cache是否具有析構函數：如果有對所有對象調用析構函數 */
        if (cachep->dtor) {
            int i;
            for (i = 0; i < cachep->num; i++) {
                // objp指向當前正在處理的對象
                void* objp = slabp->s_mem+cachep->objsize*i;
                (cachep->dtor)(objp, cachep, 0);
            }
        }

        /* 將slab使用的所有頁幀返回給buddy系統 */
        kmem_freepages(cachep, slabp->s_mem - slabp->colouroff);

        /* 如果slab描述符存儲在slab之外，需要從slab描述符的緩存中釋放 */
        if (cachep->flags & CFLGS_OFF_SLAB)
            kmem_cache_free(cachep->slabp_cache, slabp);

        /* 如果slab cache被設置了`SLAB_DESTROY_BY_RCU`標志，
         * 意味著使用延遲執行的方法釋放`slab`，使用call_rcu()注冊回調函數
         * 由回調函數調用kmem_freepages()。如果可能，還需要調用kmem_cache_free
         */
        if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU)) {
            struct slab_rcu *slab_rcu;
            slab_rcu = (struct slab_rcu *) slabp;
            slab_rcu->cachep = cachep;
            slab_rcu->addr = addr;
            call_rcu(&slab_rcu->head, kmem_rcu_free);
        } else {
            kmem_freepages(cachep, addr);
            if (OFF_SLAB(cachep))
                kmem_cache_free(cachep->slabp_cache, slabp);
        }
    }

8 對象描述符

每個對象也有描述符，類型是kmem_bufctl_t，這是一個unsigned short類型。對象描述符數組就存放在slab描述符的后邊。所以，對象描述符的存儲位置也分為兩種情況，如下圖所示：

slab外部

存儲在由slabp_cache指向的通用cache中。對象描述符和對象所占用的內存大小，有存儲在slab中的對象數量決定（cache描述符中的num字段）。

slab內部

存儲在slab之內，就在slab描述符后邊。

數組中的第一個對象描述符描述第一個對象，依次對應。對象描述符是一個unsigned short整數，只有當對象是空閑時才有意義。它包含指向下一個空閑對象的索引，因此形成了一個空閑對象的列表。該列表中，最后一個空閑對象的索引標記為BUFCTL_END(0xffff)。

9 對象的內存對齊

slab分配器管理的對象在內存中需要對齊，也就是說，存儲它們的初始物理地址是給定常數倍數的內存單元中，通常是2的冪。這個常數稱為對齊因子。

slab分配器允許的最大對齊因子是4096（頁幀大?。?。這意味著對象可以通過引用它們的物理地址或線性地址來對齊。在這兩種情況下，只有地址的低12位可能會被對齊改變。

通常，如果物理地址按照word(即計算機內部存儲器總線的寬度)對齊，計算機訪問存儲單元的速度會更快。因此，默認情況下，kmem_cache_create()函數根據BYTES_PER_WORD宏指定的字長來對齊對象。

對于×86處理器，宏的值為4，字長為32位。在創建新的slab cache時，可以將對象在硬件L1-cache中對齊。為了實現這一點，內核設置了SLAB_HWCACHE_ALIGNcache描述符標志。kmem_cache_create()會按照如下方式處理請求：

如果對象大于cache line的一半，那么它在內存中的對齊大小就是L1_CACHE_BYTES；換句話說，總是位于cache line的起始處。

否則，對象大小按照obj_size * n = L1_CACHE_BYTES計算出的合理值進行對齊，總之要保證一個對象不能跨越2個cache line。

很顯然，slab分配器在這兒就是采用以空間換取時間的思想；通過人為的增加對象的大小獲得更好地緩存性能，但也會產生內部碎片。

10 slab染色

我們知道，同一條cache line可以映射許多不同的內存塊。在本章中，我們還看到了相同大小的對象最終被存儲在硬件cache中相同的偏移位置。在不同slab中具有相同偏移量的對象將以相對較高的概率最終映射到相同的cache line中。因此，頻繁訪問映射到同一cache line的不同內存位置時，需要來回在硬件cache和內存之間搬運數據，造成訪存性能降低。slab分配器通過一種稱為slab染色的策略避免這種行為：將不同的值（稱為colors）賦給不同的slab。

在分析slab著色之前，我們必須先看一下cache中對象的布局。因為cache在內存中是對齊的，這意味著對象地址必須是給定值（比如aln）的倍數。但即使考慮到對齊約束，也有許多可能的方法將對象存放到slab中。如何選擇取決于對以下變量所做的決定:

num

可以存儲到slab中的對象數量。

osize

對象大小，包含對齊字節。

dsize

描述符大?。ò╯lab和所有對象描述符的大?。?，按照cache line對齊。如果slab和對象描述符存儲在slab之外，它的值等于0。

free

slab中未使用的字節（那些沒有分配給任何對象的字節）。

所以，slab總長可以用下面的公式計算：

slab length = (num × osize) + dsize + free

free總是小于osize，否則就可以在slab中添加一個對象了。但是，free可能大于aln。

slab分配器利用free未使用字節為slab染色。術語color簡單地對slab進行劃分，從而允許內存分配器將對象分散到不同的線性地址中。通過這種方式，內核可以從處理器的硬件cache中獲得最佳性能。

將slab染色可以將slab的第一個對象存儲到不同的內存位置，同時滿足對齊約束?？捎玫腸olor數量是free?aln（該值存儲在cache描述符的colour字段中）。因此，第1個顏色值是0，最后一個為(free?aln)?1。（一種特殊情況是，free < aln，colour設為0，所有的slab使用顏色值0，顏色的數量是一個。）

如果slab被使用顏色值col染色，第一個對象的偏移量（相對于slab初始地址）等于col × aln + dsize個字節。如下圖所示，圖中闡釋了slab內對象的位置如何依賴slab顏色值。本質上，染色就是將slab中未使用的部分字節從結尾處移動到起始處。

染色只有在free足夠大時才起作用。很明顯，如果對象沒有要求對齊，或者如果slab中未使用的字節數小于對齊因子（free < aln），唯一可能的slab染色就一個，顏色值為0，即第一個對象的偏移量賦值為零。

通過將當前顏色存儲在cache描述符中的color_next字段中，cache_grow()函數將color_next指定的顏色分配給新的slab，然后增加該字段的值。到達colour后，它再次繞到“0”。通過這種方式，每個slab都使用與前一個不同的顏色創建，直到最大可用顏色。此外，cache_grow()函數從cache描述符的color_off字段獲取值aln，根據slab內部對象的數量計算dsize，最后將值col × aln + dsize存儲在slab描述符的coloroff字段中。

11 空閑slab對象的本地緩存

在多核處理器系統中，Linux v2.6版本實現的slab分配器，與最初的Solaris 2.4實現不同。為了減少處理器之間的自旋鎖競爭并更好地利用硬件緩存，slab分配器的每個緩存都包含一個CPU核的本地數據結構，該數據結構由指向被釋放對象指針組成的數組，稱為“slab本地緩存”。大多數slab對象的分配和釋放只影響本地緩存；只有當本地緩存下溢或溢出時，才會涉及到slab數據結構。這種技術與前面的“CPU本地頁幀緩存”一節中介紹的技術非常相似。

緩存描述符的array字段是指向該指針數組，而指針指向array_cache數據結構，系統中的每個CPU都有一個這樣的元素。每個array_cache數據結構都是空閑對象的本地緩存的描述符，其字段如表8-11所示。

表8-11array_cache結構的字段

類型	名稱	描述
unsigned int	avail	指向本地緩存中可用對象的指針數。該字段可以作為緩存中的第一個空閑slot。
unsigned int	limit	本地緩存的大小。也就是說，本地緩存中指針的最大數量。
unsigned int	batchcount	本地緩存重填或清空的塊大小。
unsigned int	touched	如果本地緩存最近被使用，則標志設置為1。

注意，本地緩存描述符不包括本地緩存本身的地址；實際上，本地緩存就放在描述符后面，代碼如下所示。當然，本地緩存存儲的是指向被釋放對象的指針，而不是對象本身，對象總是放在緩存的slab中。

struct arraycache_init {
    struct array_cache cache;
    void * entries[BOOT_CPUCACHE_ENTRIES];
};

當創建新的slab緩存時，kmem_cache_create()函數確定本地緩存的大小(將此值存儲在緩存描述符的limit字段中)，分配它們，并將它們的指針存儲在緩存描述符的array字段中。大小取決于存儲在slab緩存中的對象的大小，范圍從1表示非常大的對象到120表示較小的對象。此外，“batchcount”字段的初始值，即在塊中從本地緩存中添加或刪除的對象的數量，最初設置為本地緩存大小的一半。

系統管理員可以為每個cache調節本地緩存的大小，方法是寫batchcount字段值，該值保存在/proc/slabinfo文件中。

在多核系統中，存儲小內存對象的slab緩存還支持一個額外的本地緩存，它的地址存儲在緩存描述符的lists.shared字段中。顧名思義，共享本地緩存是所有CPU共享的，它使空閑對象在本地緩存之間進行遷移變得容易。初始值等于8倍于batchcount的值。

12 分配slab對象

新對象可以通過調用kmem_cache_alloc()函數獲得。參數cachep指向必須從中獲得新的空閑對象的緩存描述符，而參數flag表示要傳遞給ZONE頁幀分配器函數的標志，如果緩存的所有slab都已滿時，使用這些標志創建新的slab。

該函數本質上等價于下面的代碼：

    void * kmem_cache_alloc(kmem_cache_t *cachep, int flags)
    {
        unsigned long       save_flags;
        void                *objp;
        struct array_cache  *ac;

        local_irq_save(save_flags);
        ac = cachep->array[smp_processor_id()];
        if (ac->avail) {
            ac->touched = 1;
            objp = ((void **)(ac+1))[--ac->avail];
        } else
            objp = cache_alloc_refill(cachep, flags);
        local_irq_restore(save_flags);
        return objp;
    }

該函數首先嘗試從本地緩存中檢索一個空閑對象。如果有空閑對象，avail字段包含本地緩存中指向最后一個被釋放對象的索引。因為本地緩存數組存儲在ac描述符之后，((void**)(ac+1))[——ac->avail]獲取該空閑對象的地址并減小ac->avail的值。調用cache_alloc_refill()函數來重新填充本地緩存，并在本地緩存中沒有空閑對象時獲得一個空閑對象。

cache_alloc_fill()函數基本上執行以下步驟:

static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
{
    // ...
    check_irq_off();

    /* 1. 獲取本地緩存描述符 */
    ac = ac_data(cachep);
retry:
    batchcount = ac->batchcount;
    if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {
        /* 如果最近這個緩存很少有活動，執行部分填充。
         * 否則容易產生refill bouncing。
         */
        batchcount = BATCHREFILL_LIMIT;
    }
    l3 = list3_data(cachep);

    /* 2. 申請自旋鎖 */
    spin_lock(&cachep->spinlock);

    /* 3. 如果slab緩存包含本地共享緩存，且其中包含一些空閑對象時。
     * 則將這些空閑對象轉移給本地緩存。
     */
    if (l3->shared) {
        struct array_cache *shared_array = l3->shared;
        if (shared_array->avail) {
            if (batchcount > shared_array->avail)
                batchcount = shared_array->avail;
            shared_array->avail -= batchcount;
            ac->avail = batchcount;
            memcpy(ac_entry(ac), &ac_entry(shared_array)[shared_array->avail],
                    sizeof(void*)*batchcount);
            shared_array->touched = 1;
            goto alloc_done;
        }
    }

    /* 4 使用batchcount個指針填充本地緩存，這些指針是slab中的空閑對象的地址 */
    while (batchcount > 0) {
        struct list_head *entry;
        struct slab *slabp;

        /* 4.a 查看cache描述符中的slabs_partial和slabs_free列表，尋找合適的空閑對象：
         * (1) 如果slabs_partial還有空閑對象，則從其中申請空閑對象
         * (2) 否則從slabs_free申請空閑對象
         * (3) 如果slabs_free沒有空閑對象，則跳轉到must_grow，擴展slab緩存
         */
        entry = l3->slabs_partial.next;
        if (entry == &l3->slabs_partial) {
            l3->free_touched = 1;
            entry = l3->slabs_free.next;
            if (entry == &l3->slabs_free)
                goto must_grow;
        }

        slabp = list_entry(entry, struct slab, list);
        check_slabp(cachep, slabp);
        check_spinlock_acquired(cachep);
        while (slabp->inuse < cachep->num && batchcount--) {
            kmem_bufctl_t next;
            STATS_INC_ALLOCED(cachep);
            STATS_INC_ACTIVE(cachep);
            STATS_SET_HIGH(cachep);

            /* 4.b 獲取空閑對象：
             * （1）獲取slab中空閑對象的指針；
             * （2）slab描述符的inuse字段+1，表明該空閑對象已經被使用
             * （3）slab描述符的free字段+1，指向下一個空閑對象
             */
            ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize;
            slabp->inuse++;
            next = slab_bufctl(slabp)[slabp->free];
            slabp->free = next;
        }
        check_slabp(cachep, slabp);

        /* 4.c 將已經消耗的slab插入到cache描述符的正確列表中
         * (1) slab_fulll列表
         * (2) slab_partial列表
         */
        list_del(&slabp->list);
        if (slabp->free == BUFCTL_END)
            list_add(&slabp->list, &l3->slabs_full);
        else
            list_add(&slabp->list, &l3->slabs_partial);
    }

must_grow:
    /* 5. 此時，要添加到本地緩存的指針數量存儲在`ac->avail`變量中。
     * 將kmem_list3結構體的字段free_objects減去添加到本地緩存中的指針數量，
     * 即是表明這些對象不再是空閑的了。
     */
    l3->free_objects -= ac->avail;

alloc_done:
    /* 6. 釋放自旋鎖 */
    spin_unlock(&cachep->spinlock);

    /* 8. 如果沒有發生緩存重填，則調用cache_grow申請一個新的slab，
     *    并申請分配新的空閑對象
     */
    if (unlikely(!ac->avail)) {
        int x;
        x = cache_grow(cachep, flags, -1);

        /* 9. 沒有申請到新slab緩存，則返回NULL;
         *    否則跳轉到第一步，重新分配對象
         */
        ac = ac_data(cachep);
        if (!x && ac->avail == 0)   // 沒有可用的空閑對象，放棄
            return NULL;

        if (!ac->avail)     // 對象重填被中斷？
            goto retry;
    }

    /* 7 如果ac->avail大于0（說明某些緩存被重填了），設置本地緩存被使用，
     *   并返回插入到本地緩存中的最后一個空閑對象的指針
     */
    ac->touched = 1;
    return ac_entry(ac)[--ac->avail];
}

13 釋放slab對象

kmem_cache_free()函數釋放先前由slab分配器分配給某個內核函數的對象。它的參數是cachep，緩存描述符的地址，objp，要釋放的對象的地址:

    void kmem_cache_free(kmem_cache_t *cachep, void *objp)
    {
        unsigned long flags;
        struct array_cache *ac;

        local_irq_save(flags);
        ac = cachep->array[smp_processor_id()];
        if (ac->avail == ac->limit)
            cache_flusharray(cachep, ac);
        ((void**)(ac+1))[ac->avail++] = objp;
        local_irq_restore(flags);
    }

該函數首先檢查本地緩存是否有空間容納指向空閑對象的額外指針。如果是，指針被添加到本地緩存中，函數返回。否則，它首先調用cache_flusharray()來耗盡本地緩存，然后將指針添加到本地緩存。

cache_flusharray()函數的主要功能如下:

static void cache_flusharray (kmem_cache_t* cachep, struct array_cache *ac)
{
    int batchcount;
    batchcount = ac->batchcount;
    check_irq_off();

    /* 1. 申請自旋鎖 */
    spin_lock(&cachep->spinlock);

    /* 2. 判斷貢獻本地緩存是否還有空間，如果有，
     *    則從CPU本地緩存中拷貝batchcount個指針到共享緩存中；
     *    然后跳轉到第4步。
     */
    if (cachep->lists.shared) {
        struct array_cache *shared_array = cachep->lists.shared;
        int max = shared_array->limit-shared_array->avail;
        if (max) {
            if (batchcount > max)
                batchcount = max;
            memcpy(&ac_entry(shared_array)[shared_array->avail],
                    &ac_entry(ac)[0],
                    sizeof(void*)*batchcount);
            shared_array->avail += batchcount;
            goto free_done;
        }
    }

    /* 3 將當前本地緩存中的batchcount對象返還給`slab`分配器 */
    free_block(cachep, &ac_entry(ac)[0], batchcount);
free_done:
    /* 4. 釋放自旋鎖 */
    spin_unlock(&cachep->spinlock);
    /* 5. 將移動到共享本地緩存或slab分配器中的對象個數從本地緩存描述符中減去 */
    ac->avail -= batchcount;
    /* 6. 將本地緩存中所有合法的指針移動到本地緩存數組的起始處。
     *    因為原起始處的對象指針已經被我們移走了。
     */
    memmove(&ac_entry(ac)[0], &ac_entry(ac)[batchcount],
            sizeof(void*)*ac->avail);
}

free_block()函數的主要功能如下:

static void free_block(kmem_cache_t *cachep, void **objpp, int nr_objects)
{
    int i;

    check_spinlock_acquired(cachep);

    /* NUMA: move add into loop
     * 1. 增加cache描述符的空閑對象計數
     */
    cachep->lists.free_objects += nr_objects;

    for (i = 0; i < nr_objects; i++) {
        void *objp = objpp[i];
        struct slab *slabp;
        unsigned int objnr;

        /* 2. 獲取對象所在slab的描述符地址:
         *    (slab所在頁的描述符的lru字段指向相應的slab描述符)
         */
        slabp = GET_PAGE_SLAB(virt_to_page(objp));
        // 3. 從slab cache列表中移除slab描述符
        // （cachep->lists.slabs_partial或cachep->lists.slabs_full）
        list_del(&slabp->list);
        // 4. 計算對象在slab中的索引
        objnr = (objp - slabp->s_mem) / cachep->objsize;
        check_slabp(cachep, slabp);

        // 5. 將slab中下一個空閑對象的索引存入對象描述符中
        //    下一個空閑對象是`objnr`。
        //    (最后一個釋放的對象，將是第一個待分配的對象)
        slab_bufctl(slabp)[objnr] = slabp->free;
        slabp->free = objnr;
        STATS_DEC_ACTIVE(cachep);
        // 6. 對象已經恢復空閑
        slabp->inuse--;
        check_slabp(cachep, slabp);

        /* */
        if (slabp->inuse == 0) {
            /* 7 如果slab中所有對象都是空閑的（inuse=0），且
             *   整個slab緩存中空閑對象的數量大于cache上限，則
             *   將多余的空閑對象占用的slab頁幀釋放回`ZONE`頁幀分配器>
             *   
             *   cachep->free_limit == cachep->num+ (1+N) × cachep->batchcount
             *   此處的N是系統中CPU核的數量。
             */
            if (cachep->lists.free_objects > cachep->free_limit) {
                cachep->lists.free_objects -= cachep->num;
                slab_destroy(cachep, slabp);
            } else {
                /* 8. 如果slab中所有對象都是空閑的（inuse=0），但整個slab緩存
                 *    中的空閑對線小于等于cachep->free_limit，則將slab描述符
                 *    插入到cachep->lists.slabs_free列表中
                 */
                list_add(&slabp->list,
                &list3_data_ptr(cachep, objp)->slabs_free);
            }
        } else {
            /* 9. 如果inuse大于0，說明slab部分被用，所以將slab描述符插入到
             *    cachep->lists.slabs_partial列表中。
             *    無條件的將一個slab移動到slabs_partial列表的末尾，
             *    這也是釋放其它的最大時間。
             */
            list_add_tail(&slabp->list,
                &list3_data_ptr(cachep, objp)->slabs_partial);
        }
    }
}

14 通用對象

在前面通用和特殊緩存一節中，對內存不頻繁的請求是通過一組通用緩存實現的，這些通用緩存對象的大小是按照幾何大小均勻分布的，從32→131072個字節。

這類對象是通過kmalloc()實現的，約等于下面的代碼：

    void * kmalloc(size_t size, int flags)
    {
        struct cache_sizes  *csizep = malloc_sizes;
        kmem_cache_t        *cachep;

        for (; csizep->cs_size; csizep++) {
            if (size > csizep->cs_size)
                continue;
            if (flags & __GFP_DMA)
                cachep = csizep->cs_dmacachep;
            else
                cachep = csizep->cs_cachep;
            return kmem_cache_alloc(cachep, flags);
        }
        return NULL;
    }

該函數借助malloc_sizes表鎖定最接近請求內存大小的2的冪次方對應的cache描述符表。然后調用kmem_cache_alloc()分配對象，可以傳遞給DMA內存的緩存描述符，也可以是普通內存的緩存描述符，取決于調用者是否傳遞了__GFP_DMA標志。

對應的釋放通用緩存對象的函數是kfree()：

    void kfree(const void *objp)
    {
        kmem_cache_t    *c;
        unsigned long   flags;

        if (!objp)
            return;
        local_irq_save(flags);
        c = (kmem_cache_t *)(virt_to_page(objp)->lru.next);
        kmem_cache_free(c, (void *)objp);
        local_irq_restore(flags);
    }

正確的緩存描述符是通過讀取包含內存區域的第1頁幀的描述符的lru.next字段來確定的。通過調用kmem_cache_free()釋放內存區域。

15 內存池

內存池是Linux v2.6內核的一個新特性?；旧?，內存池允許內核子系統(比如塊設備子系統)分配一些動態內存，僅在內存不足的緊急情況下使用。

首先我們不應該將內存池(memory pool)和預留頁幀池混淆。

實際上，這些預留頁幀只能用于滿足中斷處理程序或關鍵代碼區發出的原子內存分配請求。相反，內存池是動態內存的儲備，只能由特定的內核組件(即內存池的“所有者”)使用。內核組件通常不使用這些預留的動態內存池；但是，如果動態內存變得稀缺時，以至于所有正常的內存分配請求都注定要失敗，內核組件可以調用特殊的內存池函數，作為最后的手段，可以從內存池預留獲得所需的內存。

通常，內存池也是基于slab分配器申請的，也就是說，內存池就是預留了一些slab對象。但是，內存池可以分配任何類型的動態內存，從整個的頁幀到非常小的內存塊都可以。因此，我們一般將內存池處理的內存單元稱為內存元素。

內存池用mempool_t數據結構表示，各個字段如下表所示：

類型	名稱	描述
spinlock_t	lock	保護對象的自旋鎖
int	min_nr	內存池的最大數量
int	curr_nr	內存池的當前數量
void **	elements	指向內存池中內存元素指針的數組的指針
void *	pool_data	內存池所有者的私有數據
mempool_alloc_t *	alloc	分配一個內存池元素的方法
mempool_free_t *	free	釋放一個內存池元素的方法
wait_queue_head_t	wait	內存池為空時使用的等待隊列

min_nr存儲內存池中元素的初始數量。換句話說，存儲在此字段中的值表示內存池的所有者肯定會從內存分配器獲得的內存元素的數量。curr_nr總是小于或等于min_nr，它存儲當前包含在內存池中的內存元素的數量。內存元素本身由一個指針數組引用，其地址存儲在“elements”字段中。

alloc和free方法分別與底層內存分配器交互以獲取和釋放內存元素。這兩種方法都可以是由擁有內存池的內核組件提供的自定義函數。

當內存元素是slab對象時，alloc和free方法通常由mempool_alloc_slab()和mempool_free_slab()函數實現，它們分別調用kmem_cache_alloc()和kmem_cache_free()函數。在這種情況下，mempool_t對象的pool_data字段存儲slab緩存描述符的地址。

當內存元素是自定義數據對象時，alloc和free方法通常由kmalloc和kfree函數實現。分配的通用緩存對象。如下所示：

    static void *pkt_rb_alloc(int gfp_mask, void *data)
    {
        return kmalloc(sizeof(struct pkt_rb_node), gfp_mask);
    }

mempool_create()創建一個新的內存池：它接收的參數是min_nr，alloc和free函數的地址，及pool_data。該函數為mempool_t對象和指向內存元素的指針數組分配內存，然后重復調用alloc方法來獲取min_nr內存元素。相反，mempool_destroy()函數釋放池中的所有內存元素，然后釋放元素數組和mempool_t對象本身。

為了從內存池中分配一個元素，內核調用mempool_alloc()函數，傳遞給它mempool_t對象的地址和內存分配標志。本質上，該函數根據指定的內存分配標志，通過調用alloc方法，嘗試從底層內存分配器分配內存元素。如果分配成功，該函數返回獲得的內存元素，而不觸及內存池。否則，如果分配失敗，則從內存池中取一個內存元素。當然，在內存不足的情況下，太多的內存分配請求會耗盡內存池；在這種情況下，如果沒有設置__GFP_WAIT標志，mempool_alloc()會阻塞當前進程，直到內存元素被釋放到內存池中。

相反，要將元素釋放到內存池中，內核調用mempool_free()函數。如果內存池未滿(curr_min小于min_nr)，則該函數將元素添加到內存池中。否則，mempool_free()調用free方法將元素釋放到底層內存分配器。

審核編輯：湯梓紅