Linux內(nèi)存管理中的slab緩存怎么實(shí)現(xiàn)

本文小編為大家詳細(xì)介紹“Linux內(nèi)存管理中的slab緩存怎么實(shí)現(xiàn)”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“Linux內(nèi)存管理中的slab緩存怎么實(shí)現(xiàn)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

Linux內(nèi)核使用了源自于 Solaris 的一種方法，但是這種方法在嵌入式系統(tǒng)中已經(jīng)使用了很長時間了，它是將內(nèi)存作為對象按照大小進(jìn)行分配，被稱為slab高速緩存。

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

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

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

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

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

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

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

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)行初始化所需的時間超過了對其進(jìn)行分配和釋放所需的時間。因此他的結(jié)論是不應(yīng)該將內(nèi)存釋放回一個全局的內(nèi)存池，而是將內(nèi)存保持為針對特定目而初始化的狀態(tài)。例如，如果內(nèi)存被分配給了一個互斥鎖，那么只需在為互斥鎖***分配內(nèi)存時執(zhí)行一次互斥鎖初始化函數(shù)（mutex_init）即可。后續(xù)的內(nèi)存分配不需要執(zhí)行這個初始化函數(shù)，因?yàn)閺纳洗吾尫藕驼{(diào)用析構(gòu)之后，它已經(jīng)處于所需的狀態(tài)中了。

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

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

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

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

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

一、slab相關(guān)數(shù)據(jù)結(jié)構(gòu)

1）slab高速緩存描述符

struct kmem_cache {       struct array_cache   *array[NR_CPUS];//為了提高效率，每個cpu都有一個slab空閑對象緩存   /* 2) Cache tunables. Protected by cache_chain_mutex */       unsigned int batchcount;//從本地高速緩存批量移入或移出對象的數(shù)目       unsigned int limit;//本地高速緩存空閑對象的***數(shù)目       unsigned int shared;       unsigned int buffer_size;       struct kmem_list3 *nodelists[MAX_NUMNODES];//slab高速緩存空閑，部分空閑，無空閑slab的三個鏈表          unsigned int flags;     /* constant flags */       unsigned int num;//每個slab obj的個數(shù)       unsigned int gfporder;//每個slab中連續(xù)頁框的數(shù)目       gfp_t gfpflags;//分配頁框時，傳遞給伙伴系統(tǒng)的標(biāo)志       size_t colour;//slab使用的顏色個數(shù)       unsigned int colour_off; //slab的顏色偏移       struct kmem_cache *slabp_cache;  //指向存放slab描述符的chache，內(nèi)部slab此字段為null       unsigned int slab_size;//單個slab的大小       unsigned int dflags;        /* dynamic flags */       //對象創(chuàng)建的構(gòu)建函數(shù)       void (*ctor) (void *, struct kmem_cache *, unsigned long);       //對象的析構(gòu)函數(shù)       void (*dtor) (void *, struct kmem_cache *, unsigned long);       const char *name;//slab高速緩存的名稱       struct list_head next;//通過該字段，將該cachep鏈接到cachep鏈表上   }

2）slab描述符

struct slab {       struct list_head list;  //將slab鏈接到各個slab鏈表上面，slabs_full, slabs_paril, slabs_free       unsigned long colouroff;//slab中***個對象的偏移       void *s_mem; //slab中***個對象的地址               unsigned int inuse; //有多少對象正在被使用       kmem_bufctl_t free; //表明接下來使用哪個空閑對象       unsigned short nodeid;//該slab屬于哪個內(nèi)存節(jié)點(diǎn)   }

slab描述符可能會被存放在兩個地方：

外部slab描述符：存放在slab外部，位于cache_size指向的一個普通高速緩存中。

內(nèi)部slab描述符：存放在slab的內(nèi)部，位于分配給slab的內(nèi)存的***個頁框的起始位置。

3）slab隊列描述符

struct kmem_list3 {       struct list_head slabs_partial; //對象被使用了一部分的slab描述符的鏈表       struct list_head slabs_full;//對象都被占用了的slab描述符的鏈表       struct list_head slabs_free;//只包含空閑對象的slab描述符的鏈表       unsigned long free_objects;//高速緩存中空閑對象的個數(shù)       unsigned int free_limit;       unsigned int colour_next;   /* Per-node cache coloring */       spinlock_t list_lock;       struct array_cache *shared; //指向所有cpu所共享的一個本地高速緩存       struct array_cache **alien; /* on other nodes */       unsigned long next_reap;    //由slab的頁回收算法使用       int free_touched;       //由slab的頁回收算法使用   }

4）slab對象描述符

typedef unsigned int kmem_bufctl_t;

每個對象都有一個類型為kmem_bufctl_t的對象描述符，每個slab描述符都有一個kmem_bufctl_t類型的數(shù)組來描述slab中的各個對象。其實(shí)該描述符記錄的是下一個可用的空閑對象，使用了數(shù)組的索引來形成一個對象鏈表而已。對象描述符也分為內(nèi)部對象描述符和外部對象描述符兩種：

1. 內(nèi)部對象描述符：存放在slab的內(nèi)部，位于描述符所描述的對象的前面。

2. 外部對象描述符：存放在slab的外部，位于高速緩存描述符slabp_cache字段指向的一個普通高速緩存中，

slab描述符和slab對象之間的組織圖如下圖所示：

二、slab的本地對象緩存

Linux2.6為了更好的支持多處理器，減少自旋鎖的競爭并更好的利用硬件高速緩存，slab分配器的每個高速緩存都包含一個被稱為slab本地高速緩存的每cpu數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)由一個指向被釋放對象的指針數(shù)組組成。這樣的話，slab對象的釋放和分配就只影響到本地的指針數(shù)組，減少了并發(fā)性。只有本地數(shù)組上溢或者下溢時才會去涉及slab結(jié)構(gòu)。相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：

struct array_cache {       unsigned int avail;//本地高速緩存中可用對象的個數(shù)，也是空閑數(shù)組位置的索引       unsigned int limit;//本地高速緩存的大小       unsigned int batchcount;//本地高速緩存填充或者清空時使用到的對象個數(shù)       unsigned int touched;//如果本地高速緩存最近被使用過，置成1       spinlock_t lock;       void *entry[0];    }

同時在多cpu的環(huán)境下，還存在著一個共享高速緩存，它的地址被存放在高速緩存描述符的lists.shared字段中，本地共享高速緩存被所有cpu所共享，使得對象從一個本地高速緩存移至另一個高速緩存變的簡單。

三、slab內(nèi)存著色

比如cache line 32 字節(jié)，字節(jié)0-31一次從內(nèi)存寫入/讀取，字節(jié)32-63一次從內(nèi)存寫入/讀取…..

另外cache對應(yīng)到內(nèi)存位置不是任意的

Cache 地址0 對應(yīng)到 內(nèi)存地址0 , 32 ,64 ….

Cache 地址1 對應(yīng)到 內(nèi)存地址1 , 33 ,65 ….

…

一個slab大小肯定是整數(shù)頁，所以起始地址末12位為零， 即都于cache0 對應(yīng)。然后2個slab的每一個obj大小一樣， 所以2個slab每個obj都對應(yīng)相同的cache line.這樣2個位置相同的obj都要頻繁訪問，比較容易使cache來回刷新，效率降低。

著色就是在第二個slab的起始位置空一個cache line出來，這樣2個slab每個obj對應(yīng)的cache錯開一個，這樣2個位置相同的obj即使頻繁訪問，也不會用一個相同cache line。

但是這種方法也是有限的，2個slab里面的obj對象的訪問比較隨即，不能保證哪兩個在一個cache line 里。

四、slab內(nèi)存的申請

內(nèi)核代碼中通過slab分配對象的函數(shù)時kmem_cachep_alloc()，實(shí)質(zhì)上***調(diào)用的函數(shù)是____cache_alloc()，其相應(yīng)源碼解析如下：

static inline void *____cache_alloc(struct kmem_cache *cachep, gfp_t flags)   {       void *objp;       struct array_cache *ac;          check_irq_off();       //通過進(jìn)程所在的cpu的id獲取slab的本地高速緩存       ac = cpu_cache_get(cachep);       //本地高速緩存中是否有空閑的slab對象       if (likely(ac->avail)) {           //有空閑對象的話，從本地高速緩存數(shù)組上取一個空閑的對象來使用           STATS_INC_ALLOCHIT(cachep);           //標(biāo)記一下該本地高速緩存最近被使用過           ac->touched = 1;           //從數(shù)組的***面先取一個未使用的對象，HOHO           objp = ac->entry[--ac->avail];       } else {           STATS_INC_ALLOCMISS(cachep);           //本地高速緩存中已經(jīng)沒有空閑對象，需要填充本地高速緩存           objp = cache_alloc_refill(cachep, flags);       }       return objp;   }          cache_alloc_refill()用來填充本地高速緩存，也是slab分配精華的地方，代碼解析如下：   static void *cache_alloc_refill(struct kmem_cache *cachep, gfp_t flags)   {       int batchcount;       struct kmem_list3 *l3;       struct array_cache *ac;          check_irq_off();       //根據(jù)cpu id得到slab本地高速緩存的數(shù)據(jù)結(jié)構(gòu)       ac = cpu_cache_get(cachep);   retry:       //batchcount記錄了此次需要填充多少個空閑對象       batchcount = ac->batchcount;       if (!ac->touched && batchcount > BATCHREFILL_LIMIT) {           batchcount = BATCHREFILL_LIMIT;       }       //獲取到相對應(yīng)的內(nèi)存節(jié)點(diǎn)上的slab鏈表kmem_list3,每個內(nèi)存節(jié)點(diǎn)都有自己的一套空閑，部分空閑，非空閑slab鏈表       //因?yàn)橄鄳?yīng)cpu訪問自己所屬的內(nèi)存節(jié)點(diǎn)的速度是最快的       l3 = cachep->nodelists[numa_node_id()];          BUG_ON(ac->avail > 0 || !l3);       spin_lock(&l3->list_lock);          //從本地共享高速緩存中往本地高速緩存中填充空閑對象，要注意對于numa       //系統(tǒng)來說，往本地高速緩存上填充的空閑對象也都是該內(nèi)存節(jié)點(diǎn)上的空閑對象       if (l3->shared && transfer_objects(ac, l3->shared, batchcount))           goto alloc_done;          while (batchcount > 0) {           struct list_head *entry;           struct slab *slabp;           //先從部分空閑的slab里面分配空閑對象，保留完全空閑的slab，因?yàn)榭臻e的           //slab在內(nèi)存不足時是可以回收的           entry = l3->slabs_partial.next;           //如果沒有了部分空閑的slab，就只能去完全空閑的slab中分配了           if (entry == &l3->slabs_partial) {               l3->free_touched = 1;               entry = l3->slabs_free.next;               //如果完全空閑的slab也沒有了，就必須要為slab高速緩存分配新的slab了               if (entry == &l3->slabs_free)                   goto must_grow;           }              slabp = list_entry(entry, struct slab, list);           check_slabp(cachep, slabp);           check_spinlock_acquired(cachep);           //從slab中分配空閑對象，直到slab中空閑對象不存在了，或者已經(jīng)分配           //了足夠的空閑對象了           while (slabp->inuse < cachep->num && batchcount--) {               STATS_INC_ALLOCED(cachep);               STATS_INC_ACTIVE(cachep);               STATS_SET_HIGH(cachep);               //此處獲取空閑對象               ac->entry[ac->avail++] = slab_get_obj(cachep, slabp,                                   numa_node_id());           }           check_slabp(cachep, slabp);              /* move slabp to correct slabp list: */           list_del(&slabp->list);           //若相應(yīng)slab的空閑內(nèi)存分配完畢，將其掛入slabs_full的slab鏈表中           if (slabp->free == BUFCTL_END)               list_add(&slabp->list, &l3->slabs_full);           else               list_add(&slabp->list, &l3->slabs_partial);       }      must_grow:       l3->free_objects -= ac->avail;   alloc_done:       spin_unlock(&l3->list_lock);       //沒有分配到任何的對象       if (unlikely(!ac->avail)) {           int x;           //為高速緩存申請新的slab           x = cache_grow(cachep, flags, numa_node_id());              /* cache_grow can reenable interrupts, then ac could change. */           ac = cpu_cache_get(cachep);           if (!x && ac->avail == 0)    /* no objects in sight? abort */               return NULL;           //重新從頭填充本地高速緩存           if (!ac->avail)      /* objects refilled by interrupt? */               goto retry;       }       ac->touched = 1;       //返回本地高速緩存***一個空閑對象的地址       return ac->entry[--ac->avail];   }

五、slab內(nèi)存的釋放

slab內(nèi)存的釋放在函數(shù)kmem_cache_free()中，主要處理部分在__cache_free()函數(shù)中，其代碼解析如下：

static inline void __cache_free(struct kmem_cache *cachep, void *objp)   {       struct array_cache *ac = cpu_cache_get(cachep);       check_irq_off();       objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));       if (cache_free_alien(cachep, objp))           return;       //本地高速緩存可用的空閑對象尚未達(dá)到限制，將空閑對象放入本地高速緩存       if (likely(ac->avail < ac->limit)) {           STATS_INC_FREEHIT(cachep);           ac->entry[ac->avail++] = objp;           return;       } else {           //cache_flusharray()會將本地高速緩存的一些空閑對象放入到slab中           cache_flusharray(cachep, ac);           ac->entry[ac->avail++] = objp;       }   }      static void cache_flusharray(struct kmem_cache *cachep, struct array_cache *ac)   {       int batchcount;       struct kmem_list3 *l3;       int node = numa_node_id();       //一次應(yīng)該將batchcount個空閑對象歸還到slab中       batchcount = ac->batchcount;       check_irq_off();       //得到對應(yīng)內(nèi)存節(jié)點(diǎn)的slab list3,上面記錄著該節(jié)點(diǎn)的slab鏈表       l3 = cachep->nodelists[node];       spin_lock(&l3->list_lock);       //優(yōu)先先歸還到本地共享高速緩存中，注意本地共享高速緩存中的       //空閑對象是僅供該內(nèi)存節(jié)點(diǎn)上的各個cpu分配使用的，這樣可以使內(nèi)存訪問的效率***。       if (l3->shared) {           struct array_cache *shared_array = l3->shared;           int max = shared_array->limit - shared_array->avail;           if (max) {               if (batchcount > max)                   batchcount = max;               //將batchcount個數(shù)組元素copy到本地高速緩存中               memcpy(&(shared_array->entry[shared_array->avail]),                      ac->entry, sizeof(void *) * batchcount);               shared_array->avail += batchcount;               goto free_done;           }       }       //在沒有本地高速緩存的情況下，釋放回slab中       free_block(cachep, ac->entry, batchcount, node);   free_done:       spin_unlock(&l3->list_lock);       ac->avail -= batchcount;       //將刪除后剩下的空閑對象往前移動一下，hoho,可能還剩下些空閑對象       memmove(ac->entry, &(ac->entry[batchcount]), sizeof(void *)*ac->avail);   }      static void free_block(struct kmem_cache *cachep, void **objpp, int nr_objects,                  int node)   {       int i;       struct kmem_list3 *l3;          for (i = 0; i < nr_objects; i++) {           void *objp = objpp[i];           struct slab *slabp;           //先從對象獲取到其所在的page，再從page得到其所屬的slab           //page->lru.prev中記錄了page所屬的slab           slabp = virt_to_slab(objp);           l3 = cachep->nodelists[node];           list_del(&slabp->list);           check_spinlock_acquired_node(cachep, node);           check_slabp(cachep, slabp);           //放入對應(yīng)的slab           slab_put_obj(cachep, slabp, objp, node);           STATS_DEC_ACTIVE(cachep);           l3->free_objects++;           check_slabp(cachep, slabp);              /* fixup slab chains */           //slab所有的對象都已經(jīng)被歸還           if (slabp->inuse == 0) {               //slab高速緩存的空閑對象數(shù)超過了限制，可以釋放掉該slab，以               //釋放其所占有的內(nèi)存               if (l3->free_objects > l3->free_limit) {                   l3->free_objects -= cachep->num;                   slab_destroy(cachep, slabp);               } else {                   //加入到完全空閑slab鏈表中                   list_add(&slabp->list, &l3->slabs_free);               }           } else {               //加入到部分空閑的slab鏈表中               list_add_tail(&slabp->list, &l3->slabs_partial);           }       }   }

讀到這里，這篇“Linux內(nèi)存管理中的slab緩存怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點(diǎn)還需要大家自己動手實(shí)踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。