動態(tài)內(nèi)存管理

內(nèi)存管理的目標(biāo)是提供一種方法，為實(shí)現(xiàn)各種目的而在各個(gè)用戶之間實(shí)現(xiàn)內(nèi)存共享。內(nèi)存管理方法應(yīng)該實(shí)現(xiàn)以下兩個(gè)功能：

最小化管理內(nèi)存所需的時(shí)間?

最大化用于一般應(yīng)用的可用內(nèi)存（最小化管理開銷）?

內(nèi)存管理實(shí)際上是一種關(guān)于權(quán)衡的零和游戲。您可以開發(fā)一種使用少量內(nèi)存進(jìn)行管理的算法，但是要花費(fèi)更多時(shí)間來管理可用內(nèi)存。也可以開發(fā)一個(gè)算法來有效地管理內(nèi)存，但卻要使用更多的內(nèi)存。最終，特定應(yīng)用程序的需求將促使對這種權(quán)衡作出選擇。

每個(gè)內(nèi)存管理器都使用了一種基于堆的分配策略。在這種方法中，大塊內(nèi)存（稱為?堆）用來為用戶定義的目的提供內(nèi)存。當(dāng)用戶需要一塊內(nèi)存時(shí)，就請求給自己分配一定大小的內(nèi)存。堆管理器會查看可用內(nèi)存的情況（使用特定算法）并返回一塊內(nèi)存。搜索過程中使用的一些算法有?first-fit（在堆中搜索到的第一個(gè)滿足請求的內(nèi)存塊）和?best-fit（使用堆中滿足請求的最合適的內(nèi)存塊）。當(dāng)用戶使用完內(nèi)存后，就將內(nèi)存返回給堆。

這種基于堆的分配策略的根本問題是碎片（fragmentation）。當(dāng)內(nèi)存塊被分配后，它們會以不同的順序在不同的時(shí)間返回。這樣會在堆中留下一些洞，需要花一些時(shí)間才能有效地管理空閑內(nèi)存。這種算法通常具有較高的內(nèi)存使用效率（分配需要的內(nèi)存），但是卻需要花費(fèi)更多時(shí)間來對堆進(jìn)行管理。

另外一種方法稱為?buddy memory allocation，是一種更快的內(nèi)存分配技術(shù)，它將內(nèi)存劃分為 2 的冪次方個(gè)分區(qū)，并使用 best-fit 方法來分配內(nèi)存請求。當(dāng)用戶釋放內(nèi)存時(shí)，就會檢查 buddy 塊，查看其相鄰的內(nèi)存塊是否也已經(jīng)被釋放。如果是的話，將合并內(nèi)存塊以最小化內(nèi)存碎片。這個(gè)算法的時(shí)間效率更高，但是由于使用 best-fit 方法的緣故，會產(chǎn)生內(nèi)存浪費(fèi)。

本文將著重介紹 Linux 內(nèi)核的內(nèi)存管理，尤其是?slab 分配提供的機(jī)制。

slab 緩存

Linux 所使用的 slab 分配器的基礎(chǔ)是 Jeff Bonwick 為 SunOS 操作系統(tǒng)首次引入的一種算法。Jeff 的分配器是圍繞對象緩存進(jìn)行的。在內(nèi)核中，會為有限的對象集（例如文件描述符和其他常見結(jié)構(gòu)）分配大量內(nèi)存。Jeff 發(fā)現(xiàn)對內(nèi)核中普通對象進(jìn)行初始化所需的時(shí)間超過了對其進(jìn)行分配和釋放所需的時(shí)間。因此他的結(jié)論是不應(yīng)該將內(nèi)存釋放回一個(gè)全局的內(nèi)存池，而是將內(nèi)存保持為針對特定目而初始化的狀態(tài)。例如，如果內(nèi)存被分配給了一個(gè)互斥鎖，那么只需在為互斥鎖首次分配內(nèi)存時(shí)執(zhí)行一次互斥鎖初始化函數(shù)（mutex_init）即可。后續(xù)的內(nèi)存分配不需要執(zhí)行這個(gè)初始化函數(shù)，因?yàn)閺纳洗吾尫藕驼{(diào)用析構(gòu)之后，它已經(jīng)處于所需的狀態(tài)中了。

Linux slab 分配器使用了這種思想和其他一些思想來構(gòu)建一個(gè)在空間和時(shí)間上都具有高效性的內(nèi)存分配器。

圖 1 給出了 slab 結(jié)構(gòu)的高層組織結(jié)構(gòu)。在最高層是?cache_chain，這是一個(gè) slab 緩存的鏈接列表。這對于 best-fit 算法非常有用，可以用來查找最適合所需要的分配大小的緩存（遍歷列表）。cache_chain?的每個(gè)元素都是一個(gè)?kmem_cache?結(jié)構(gòu)的引用（稱為一個(gè)?cache）。它定義了一個(gè)要管理的給定大小的對象池。

圖 1. slab 分配器的主要結(jié)構(gòu)

每個(gè)緩存都包含了一個(gè)?slabs?列表，這是一段連續(xù)的內(nèi)存塊（通常都是頁面）。存在 3 種 slab：

slabs_full

完全分配的 slab?

slabs_partial

部分分配的 slab?

slabs_empty

空 slab，或者沒有對象被分配?

注意?slabs_empty?列表中的 slab 是進(jìn)行回收（reaping）的主要備選對象。正是通過此過程，slab 所使用的內(nèi)存被返回給操作系統(tǒng)供其他用戶使用。

slab 列表中的每個(gè) slab 都是一個(gè)連續(xù)的內(nèi)存塊（一個(gè)或多個(gè)連續(xù)頁），它們被劃分成一個(gè)個(gè)對象。這些對象是從特定緩存中進(jìn)行分配和釋放的基本元素。注意 slab 是 slab 分配器進(jìn)行操作的最小分配單位，因此如果需要對 slab 進(jìn)行擴(kuò)展，這也就是所擴(kuò)展的最小值。通常來說，每個(gè) slab 被分配為多個(gè)對象。

由于對象是從 slab 中進(jìn)行分配和釋放的，因此單個(gè) slab 可以在 slab 列表之間進(jìn)行移動。例如，當(dāng)一個(gè) slab 中的所有對象都被使用完時(shí)，就從?slabs_partial?列表中移動到?slabs_full?列表中。當(dāng)一個(gè) slab 完全被分配并且有對象被釋放后，就從?slabs_full?列表中移動到?slabs_partial?列表中。當(dāng)所有對象都被釋放之后，就從?slabs_partial?列表移動到?slabs_empty?列表中。

slab 背后的動機(jī)

與傳統(tǒng)的內(nèi)存管理模式相比， slab 緩存分配器提供了很多優(yōu)點(diǎn)。首先，內(nèi)核通常依賴于對小對象的分配，它們會在系統(tǒng)生命周期內(nèi)進(jìn)行無數(shù)次分配。slab 緩存分配器通過對類似大小的對象進(jìn)行緩存而提供這種功能，從而避免了常見的碎片問題。slab 分配器還支持通用對象的初始化，從而避免了為同一目而對一個(gè)對象重復(fù)進(jìn)行初始化。最后，slab 分配器還可以支持硬件緩存對齊和著色，這允許不同緩存中的對象占用相同的緩存行，從而提高緩存的利用率并獲得更好的性能。

API 函數(shù)

現(xiàn)在來看一下能夠創(chuàng)建新 slab 緩存、向緩存中增加內(nèi)存、銷毀緩存的應(yīng)用程序接口（API）以及 slab 中對對象進(jìn)行分配和釋放操作的函數(shù)。

第一個(gè)步驟是創(chuàng)建 slab 緩存結(jié)構(gòu)，您可以將其靜態(tài)創(chuàng)建為：

struct struct kmem_cache *my_cachep;

slab 緩存的 Linux 源代碼?
您可以在 ./linux/mm/slab.c 中找到 slab 緩存的源代碼。?kmem_cache?結(jié)構(gòu)也是在 ./linux/mm/slab.c 中定義的。本文著重討論 2.6.21 Linux 內(nèi)核中的當(dāng)前實(shí)現(xiàn)。?

然后其他 slab 緩存函數(shù)將使用該引用進(jìn)行創(chuàng)建、刪除、分配等操作。kmem_cache?結(jié)構(gòu)包含了每個(gè)中央處理器單元（CPU）的數(shù)據(jù)、一組可調(diào)整的（可以通過 proc 文件系統(tǒng)訪問）參數(shù)、統(tǒng)計(jì)信息和管理 slab 緩存所必須的元素。

kmem_cache_create

內(nèi)核函數(shù)?kmem_cache_create?用來創(chuàng)建一個(gè)新緩存。這通常是在內(nèi)核初始化時(shí)執(zhí)行的，或者在首次加載內(nèi)核模塊時(shí)執(zhí)行。其原型定義如下：

struct kmem_cache *kmem_cache_create( const char *name, size_t size, size_t align, unsigned long flags; void (*ctor)(void*, struct kmem_cache *, unsigned long), void (*dtor)(void*, struct kmem_cache *, unsigned long));

name?參數(shù)定義了緩存名稱，proc 文件系統(tǒng)（在 /proc/slabinfo 中）使用它標(biāo)識這個(gè)緩存。?size?參數(shù)指定了為這個(gè)緩存創(chuàng)建的對象的大小，?align?參數(shù)定義了每個(gè)對象必需的對齊。?flags?參數(shù)指定了為緩存啟用的選項(xiàng)。這些標(biāo)志如表 1 所示。

表 1. kmem_cache_create 的部分選項(xiàng)（在 flags 參數(shù)中指定）

選項(xiàng)

說明

SLAB_RED_ZONE在對象頭、尾插入標(biāo)志，用來支持對緩沖區(qū)溢出的檢查。SLAB_POISON使用一種己知模式填充 slab，允許對緩存中的對象進(jìn)行監(jiān)視（對象屬對象所有，不過可以在外部進(jìn)行修改）。SLAB_HWCACHE_ALIGN指定緩存對象必須與硬件緩存行對齊。

ctor?和?dtor?參數(shù)定義了一個(gè)可選的對象構(gòu)造器和析構(gòu)器。構(gòu)造器和析構(gòu)器是用戶提供的回調(diào)函數(shù)。當(dāng)從緩存中分配新對象時(shí)，可以通過構(gòu)造器進(jìn)行初始化。

在創(chuàng)建緩存之后，?kmem_cache_create?函數(shù)會返回對它的引用。注意這個(gè)函數(shù)并沒有向緩存分配任何內(nèi)存。相反，在試圖從緩存（最初為空）分配對象時(shí)，refill?操作將內(nèi)存分配給它。當(dāng)所有對象都被使用掉時(shí)，也可以通過相同的操作向緩存添加內(nèi)存。

kmem_cache_destroy

內(nèi)核函數(shù)?kmem_cache_destroy?用來銷毀緩存。這個(gè)調(diào)用是由內(nèi)核模塊在被卸載時(shí)執(zhí)行的。在調(diào)用這個(gè)函數(shù)時(shí)，緩存必須為空。

void kmem_cache_destroy( struct kmem_cache *cachep );

kmem_cache_alloc

要從一個(gè)命名的緩存中分配一個(gè)對象，可以使用?kmem_cache_alloc?函數(shù)。調(diào)用者提供了從中分配對象的緩存以及一組標(biāo)志：

void kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags );

這個(gè)函數(shù)從緩存中返回一個(gè)對象。注意如果緩存目前為空，那么這個(gè)函數(shù)就會調(diào)用?cache_alloc_refill?向緩存中增加內(nèi)存。?kmem_cache_alloc?的 flags 選項(xiàng)與?kmalloc?的 flags 選項(xiàng)相同。表 2 給出了標(biāo)志選項(xiàng)的部分列表。

表 2. kmem_cache_alloc 和 kmalloc 內(nèi)核函數(shù)的標(biāo)志選項(xiàng)

標(biāo)志

說明

GFP_USER為用戶分配內(nèi)存（這個(gè)調(diào)用可能會睡眠）。GFP_KERNEL從內(nèi)核 RAM 中分配內(nèi)存（這個(gè)調(diào)用可能會睡眠）。GFP_ATOMIC使該調(diào)用強(qiáng)制處于非睡眠狀態(tài)（對中斷處理程序非常有用）。GFP_HIGHUSER從高端內(nèi)存中分配內(nèi)存。

NUMA 的 slab 分配?
對于 NUMA（Non-Uniform Memory Access）架構(gòu)來說，對某個(gè)特定節(jié)點(diǎn)的分配函數(shù)是?kmem_cache_alloc_node。?

kmem_cache_zalloc

內(nèi)核函數(shù)?kmem_cache_zalloc?與?kmem_cache_alloc?類似，只不過它對對象執(zhí)行?memset?操作，用來在將對象返回調(diào)用者之前對其進(jìn)行清除操作。

NUMA 的 slab 分配?
對于 NUMA（Non-Uniform Memory Access）架構(gòu)來說，對某個(gè)特定節(jié)點(diǎn)的分配函數(shù)是?kmem_cache_alloc_node。

kmem_cache_free

要將一個(gè)對象釋放回 slab，可以使用?kmem_cache_free。調(diào)用者提供了緩存引用和要釋放的對象。

void kmem_cache_free( struct kmem_cache *cachep, void *objp );

kmalloc 和 kfree

內(nèi)核中最常用的內(nèi)存管理函數(shù)是?kmalloc?和?kfree?函數(shù)。這兩個(gè)函數(shù)的原型如下：

void *kmalloc( size_t size, int flags );void kfree( const void *objp );

注意在?kmalloc?中，惟一兩個(gè)參數(shù)是要分配的對象的大小和一組標(biāo)志（請參看?表 2?中的部分列表）。但是?kmalloc?和?kfree?使用了類似于前面定義的函數(shù)的 slab 緩存。kmalloc?沒有為要從中分配對象的某個(gè) slab 緩存命名，而是循環(huán)遍歷可用緩存來查找可以滿足大小限制的緩存。找到之后，就（使用?__kmem_cache_alloc）分配一個(gè)對象。要使用?kfree?釋放對象，從中分配對象的緩存可以通過調(diào)用?virt_to_cache?確定。這個(gè)函數(shù)會返回一個(gè)緩存引用，然后在?__cache_free?調(diào)用中使用該引用釋放對象。

通用對象分配?
在 slab 源代碼中，提供了一個(gè)名為?kmem_find_general_cachep?的函數(shù)，可執(zhí)行緩存搜索，即用來查找最適合所需對象大小的 slab 緩存。

其他函數(shù)

slab 緩存 API 還提供了其他一些非常有用的函數(shù)。?kmem_cache_size?函數(shù)會返回這個(gè)緩存所管理的對象的大小。您也可以通過調(diào)用?kmem_cache_name?來檢索給定緩存的名稱（在創(chuàng)建緩存時(shí)定義）。緩存可以通過釋放其中的空閑 slab 進(jìn)行收縮。這可以通過調(diào)用?kmem_cache_shrink?實(shí)現(xiàn)。注意這個(gè)操作（稱為回收）是由內(nèi)核定期自動執(zhí)行的（通過?kswapd）。

unsigned int kmem_cache_size( struct kmem_cache *cachep );const char *kmem_cache_name( struct kmem_cache *cachep );int kmem_cache_shrink( struct kmem_cache *cachep );

通用對象分配?
在 slab 源代碼中，提供了一個(gè)名為?kmem_find_general_cachep?的函數(shù)，可執(zhí)行緩存搜索，即用來查找最適合所需對象大小的 slab 緩存。

slab 緩存的示例用法

下面的代碼片斷展示了創(chuàng)建新 slab 緩存、從緩存中分配和釋放對象然后銷毀緩存的過程。首先，必須要定義一個(gè)?kmem_cache?對象，然后對其進(jìn)行初始化（請參看清單 1）。這個(gè)特定的緩存包含 32 字節(jié)的對象，并且是硬件緩存對齊的（由標(biāo)志參數(shù)?SLAB_HWCACHE_ALIGN?定義）。

清單 1. 創(chuàng)建新 slab 緩存

static struct kmem_cache *my_cachep;static void init_my_cache( void ){ my_cachep = kmem_cache_create( "my_cache", /* Name */ 32, /* Object Size */ 0, /* Alignment */ SLAB_HWCACHE_ALIGN, /* Flags */ NULL, NULL ); /* Constructor/Deconstructor */ return;}

使用所分配的 slab 緩存，您現(xiàn)在可以從中分配一個(gè)對象了。清單 2 給出了一個(gè)從緩存中分配和釋放對象的例子。它還展示了兩個(gè)其他函數(shù)的用法。

清單 2. 分配和釋放對象

int slab_test( void ){ void *object; printk( "Cache name is %s/n", kmem_cache_name( my_cachep ) ); printk( "Cache object size is %d/n", kmem_cache_size( my_cachep ) ); object = kmem_cache_alloc( my_cachep, GFP_KERNEL ); if (object) { kmem_cache_free( my_cachep, object ); } return 0;}

最后，清單 3 演示了 slab 緩存的銷毀。調(diào)用者必須確保在執(zhí)行銷毀操作過程中，不要從緩存中分配對象。

清單 3. 銷毀 slab 緩存

static void remove_my_cache( void ){ if (my_cachep) kmem_cache_destroy( my_cachep ); return;}

SLOB 分配器

對于小型的嵌入式系統(tǒng)來說，存在一個(gè) slab 模擬層，名為 SLOB。這個(gè) slab 的替代品在小型嵌入式 Linux 系統(tǒng)中具有優(yōu)勢，但是即使它保存了 512KB 內(nèi)存，依然存在碎片和難于擴(kuò)展的問題。在禁用?CONFIG_SLAB?時(shí)，內(nèi)核會回到這個(gè) SLOB 分配器中。

結(jié)束語

slab 緩存分配器的源代碼實(shí)際上是 Linux 內(nèi)核中可讀性較好的一部分。除了函數(shù)調(diào)用的間接性之外，源代碼也非常直觀，總的來說，具有很好的注釋。如果您希望了解更多有關(guān) slab 緩存分配器的內(nèi)容，建議您從源代碼開始，因?yàn)樗怯嘘P(guān)這種機(jī)制的最新文檔。 下面的?參考資料?一節(jié)提供了介紹 slab 緩存分配器的參考資料，但是不幸的是就目前的 2.6 實(shí)現(xiàn)來說，這些文檔都已經(jīng)過時(shí)了。

?