1.內(nèi)部碎片和外部碎片

外部碎片
什么是外部碎片呢述呐？我們通過(guò)一個(gè)圖來(lái)解釋：

image.png

2.slab分配機(jī)制

slab分配器是基于對(duì)象進(jìn)行管理的护盈，所謂的對(duì)象就是內(nèi)核中的數(shù)據(jù)結(jié)構(gòu)（例如：task_struct,file_struct 等）挟纱。相同類型的對(duì)象歸為一類，每當(dāng)要申請(qǐng)這樣一個(gè)對(duì)象時(shí)腐宋，slab分配器就從一個(gè)slab列表中分配一個(gè)這樣大小的單元出去紊服，而當(dāng)要釋放時(shí)，將其重新保存在該列表中胸竞，而不是直接返回給伙伴系統(tǒng)欺嗤，從而避免內(nèi)部碎片。slab分配器并不丟棄已經(jīng)分配的對(duì)象卫枝，而是釋放并把它們保存在內(nèi)存中煎饼。slab分配對(duì)象時(shí)，會(huì)使用最近釋放的對(duì)象的內(nèi)存塊剃盾，因此其駐留在cpu高速緩存中的概率會(huì)大大提高腺占。

3.內(nèi)核中slab的主要數(shù)據(jù)結(jié)構(gòu)

image.png

• 首先要查看inode_cachep的slabs_partial鏈表募强，如果slabs_partial非空株灸，就從中選中一個(gè)slab，返回一個(gè)指向已分配但未使用的inode結(jié)構(gòu)的指針擎值。完事之后慌烧，如果這個(gè)slab滿了，就把它從slabs_partial中刪除鸠儿，插入到slabs_full中去屹蚊，結(jié)束；
• 如果slabs_partial為空进每，也就是沒(méi)有半滿的slab汹粤，就會(huì)到slabs_empty中尋找。如果slabs_empty非空田晚，就選中一個(gè)slab玄括，返回一個(gè)指向已分配但未使用的inode結(jié)構(gòu)的指針，然后將這個(gè)slab從slabs_empty中刪除肉瓦，插入到slabs_partial（或者slab_full）中去，結(jié)束胃惜；
• 如果slabs_empty也為空泞莉，那么沒(méi)辦法，cache內(nèi)存已經(jīng)不足船殉，只能新創(chuàng)建一個(gè)slab了鲫趁。
  接下來(lái)我們來(lái)分析下slab在內(nèi)核中數(shù)據(jù)結(jié)構(gòu)的組織，首先要從kmem_cache這個(gè)結(jié)構(gòu)體說(shuō)起了

struct kmem_cache {
    struct array_cache *array[NR_CPUS];//per_cpu數(shù)據(jù)利虫，記錄了本地高速緩存的信息挨厚，也是用于跟蹤最近釋放的對(duì)象，每次分配和釋放都要直接訪問(wèn)它糠惫。
    unsigned int batchcount;//本地高速緩存轉(zhuǎn)入和轉(zhuǎn)出的大批數(shù)據(jù)數(shù)量
    unsigned int limit;//本地高速緩存中空閑對(duì)象的最大數(shù)目
    unsigned int shared;

    unsigned int buffer_size;/*buffer的大小疫剃，就是對(duì)象的大小*/
    u32 reciprocal_buffer_size;

    unsigned int flags;     /* constant flags */
    unsigned int num;       /* # of objs per slab *//*slab中有多少個(gè)對(duì)象*/

    /* order of pgs per slab (2^n) */
    unsigned int gfporder;/*每個(gè)slab中有多少個(gè)頁(yè)*/

    gfp_t gfpflags;       /*與伙伴系統(tǒng)交互時(shí)所提供的分配標(biāo)識(shí)*/  

    size_t colour;          /* cache colouring range *//*slab中的著色*/
    unsigned int colour_off;    /* colour offset */著色的偏移量
    struct kmem_cache *slabp_cache;
    unsigned int slab_size;              //slab管理區(qū)的大小
    unsigned int dflags;        /* dynamic flags */

    /* constructor func */
    void (*ctor)(void *obj);    /*構(gòu)造函數(shù)*/

/* 5) cache creation/removal */
    const char *name;/*slab上的名字*/
    struct list_head next;              //用于將高速緩存連入cache chain

/* 6) statistics */ //一些用于調(diào)試用的變量
#ifdef CONFIG_DEBUG_SLAB
    unsigned long num_active;
    unsigned long num_allocations;
    unsigned long high_mark;
    unsigned long grown;
    unsigned long reaped;
    unsigned long errors;
    unsigned long max_freeable;
    unsigned long node_allocs;
    unsigned long node_frees;
    unsigned long node_overflow;
    atomic_t allochit;
    atomic_t allocmiss;
    atomic_t freehit;
    atomic_t freemiss;

    int obj_offset;
    int obj_size;
#endif /* CONFIG_DEBUG_SLAB */
    //用于組織該高速緩存中的slab
    struct kmem_list3 *nodelists[MAX_NUMNODES];/*最大的內(nèi)存節(jié)點(diǎn)*/

};

/* Size description struct for general caches. */
struct cache_sizes {
    size_t          cs_size;
    struct kmem_cache   *cs_cachep;
#ifdef CONFIG_ZONE_DMA
    struct kmem_cache   *cs_dmacachep;
#endif
};

由上面的總圖可知，一個(gè)核心的數(shù)據(jù)結(jié)構(gòu)就是kmem_list3硼讽，它描述了slab描述符的狀態(tài)巢价。

struct kmem_list3 {
/*三個(gè)鏈表中存的是一個(gè)高速緩存slab*/
/*在這三個(gè)鏈表中存放的是cache*/
    struct list_head slabs_partial; //包含空閑對(duì)象和已經(jīng)分配對(duì)象的slab描述符
    struct list_head slabs_full;//只包含非空閑的slab描述符
    struct list_head slabs_free;//只包含空閑的slab描述符
    unsigned long free_objects;  /*高速緩存中空閑對(duì)象的個(gè)數(shù)*/
    unsigned int free_limit;   //空閑對(duì)象的上限
    unsigned int colour_next;   /* Per-node cache coloring *//*即將要著色的下一個(gè)*/
    spinlock_t list_lock;
    struct array_cache *shared; /* shared per node */
    struct array_cache **alien; /* on other nodes */
    unsigned long next_reap;    /* updated without locking *//**/
    int free_touched;       /* updated without locking */
};

接下來(lái)介紹描述單個(gè)slab的結(jié)構(gòu)struct slab

struct slab {
    struct list_head list;   //用于將slab連入keme_list3的鏈表
    unsigned long colouroff;   //該slab的著色偏移
    void *s_mem;        /* 指向slab中的第一個(gè)對(duì)象*/
    unsigned int inuse; /* num of objs active in slab */已經(jīng)分配出去的對(duì)象
    kmem_bufctl_t free;       //下一個(gè)空閑對(duì)象的下標(biāo)
    unsigned short nodeid;   //節(jié)點(diǎn)標(biāo)識(shí)符
};

在kmem_cache中還有一個(gè)重要的數(shù)據(jù)結(jié)構(gòu)struct array_cache.這是一個(gè)指針數(shù)組，數(shù)組的元素是系統(tǒng)的cpu的個(gè)數(shù)固阁。該結(jié)構(gòu)用來(lái)描述每個(gè)cpu的高速緩存壤躲，它的主要作用是減少smp系統(tǒng)中對(duì)于自旋鎖的競(jìng)爭(zhēng)。

• 實(shí)際上备燃，每次分配內(nèi)存都是直接與本地cpu高速緩存進(jìn)行交互碉克，只有當(dāng)其空閑內(nèi)存不足時(shí)，才會(huì)從keme_list中的slab中引入一部分對(duì)象到本地高速緩存中并齐，而keme_list中的空閑對(duì)象也不足時(shí)漏麦，那么就要從伙伴系統(tǒng)中引入新的頁(yè)來(lái)建立新的slab了客税。

struct array_cache {
    unsigned int avail;/*當(dāng)前cpu上有多少個(gè)可用的對(duì)象*/
    unsigned int limit;/*per_cpu里面最大的對(duì)象的個(gè)數(shù)，當(dāng)超過(guò)這個(gè)值時(shí)唁奢，將對(duì)象返回給伙伴系統(tǒng)*/
    unsigned int batchcount;/*一次轉(zhuǎn)入和轉(zhuǎn)出的對(duì)象數(shù)量*/
    unsigned int touched;/*標(biāo)示本地cpu最近是否被使用*/
    spinlock_t lock;/*自旋鎖*/
    void *entry[];  /*
             * Must have this definition in here for the proper
             * alignment of array_cache. Also simplifies accessing
             * the entries.
             */
};

對(duì)上面提到的各個(gè)數(shù)據(jù)結(jié)構(gòu)做一個(gè)總結(jié)霎挟，用下圖來(lái)描述：

image.png

4.關(guān)于slab分配器的API

下面看一下slab分配器的接口——看看slab緩存是如何創(chuàng)建、撤銷以及如何從緩存中分配一個(gè)對(duì)象的麻掸。一個(gè)新的kmem_cache通過(guò)kmem_cache_create()函數(shù)來(lái)創(chuàng)建：

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

*name是一個(gè)字符串，存放kmem_cache緩存的名字脊奋；size是緩存所存放的對(duì)象的大邪颈薄；align是slab內(nèi)第一個(gè)對(duì)象的偏移诚隙；flag是可選的配置項(xiàng)讶隐，用來(lái)控制緩存的行為。最后一個(gè)參數(shù)ctor是對(duì)象的構(gòu)造函數(shù)久又，一般是不需要的巫延，以NULL來(lái)代替。kmem_cache_create()成功執(zhí)行之后會(huì)返回一個(gè)指向所創(chuàng)建的緩存的指針地消，否則返回NULL炉峰。kmem_cache_create()可能會(huì)引起阻塞（睡眠），因此不能在中斷上下文中使用脉执。

撤銷一個(gè)kmem_cache則是通過(guò)kmem_cache_destroy()函數(shù)：

int kmem_cache_destroy( struct kmem_cache *cachep);

該函數(shù)成功則返回0疼阔，失敗返回非零值。調(diào)用kmem_cache_destroy()之前應(yīng)該滿足下面幾個(gè)條件：首先半夷，cachep所指向的緩存中所有slab都為空閑婆廊，否則的話是不可以撤銷的；其次在調(diào)用kmem_cache_destroy()過(guò)程中以及調(diào)用之后巫橄，調(diào)用者需要確保不會(huì)再訪問(wèn)這個(gè)緩存淘邻；最后，該函數(shù)也可能會(huì)引起阻塞嗦随，因此不能在中斷上下文中使用列荔。
可以通過(guò)下面函數(shù)來(lái)從kmem_cache中分配一個(gè)對(duì)象：

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

這個(gè)函數(shù)從cachep指定的緩存中返回一個(gè)指向?qū)ο蟮闹羔槨Ｈ绻彺嬷兴衧lab都是滿的枚尼，那么slab分配器會(huì)通過(guò)調(diào)用kmem_getpages()創(chuàng)建一個(gè)新的slab贴浙。

釋放一個(gè)對(duì)象的函數(shù)如下：

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

這個(gè)函數(shù)是將被釋放的對(duì)象返還給先前的slab，其實(shí)就是將cachep中的對(duì)象objp標(biāo)記為空閑而已

5.使用以上的API寫(xiě)內(nèi)核模塊署恍，生成自己的slab高速緩存崎溃。

其實(shí)到了這里，應(yīng)該去分析以上函數(shù)的源碼盯质，但是幾次奮起分析袁串，都被打趴在地概而。所以就寫(xiě)個(gè)內(nèi)核模塊，鼓勵(lì)下自己吧囱修。

#include <linux/autoconf.h>
#include <linux/module.h>
#include <linux/slab.h>

MODULE_AUTHOR("wangzhangjun");
MODULE_DESCRIPTION("slab test module");

static struct kmem_cache  *test_cachep = NULL;
struct slab_test
{
    int val;
};
void fun_ctor(struct slab_test *object , struct kmem_cache  *cachep , unsigned long flags )
{
    printk(KERN_INFO "ctor fuction ...\n");
    object->val = 1;
}

static int __init slab_init(void)
{
    struct slab_test *object = NULL;//slab的一個(gè)對(duì)象
    printk(KERN_INFO "slab_init\n");
//注意：這個(gè)函數(shù)的第二個(gè)參數(shù)（對(duì)象的大惺旯濉），是有上限和下限的
//4Byte<=object size <= 4M(即在4字節(jié)到4M之間)破镰，如果不在這個(gè)范圍之內(nèi)餐曼，會(huì)導(dǎo)致內(nèi)核崩潰
    test_cachep = kmem_cache_create("test_cachep",sizeof(struct slab_test)*3,0,SLAB_HWCACHE_ALIGN,fun_ctor);
    if(NULL == test_cachep) 
                return  -ENOMEM ;
    printk(KERN_INFO "Cache name is %s\n",kmem_cache_name(test_cachep));//獲取高速緩存的名稱
    printk(KERN_INFO "Cache object size  is %d\n",kmem_cache_size(test_cachep));//獲取高速緩存的大小
    object = kmem_cache_alloc(test_cachep,GFP_KERNEL);//從高速緩存中分配一個(gè)對(duì)象
    if(object)
    {
        printk(KERN_INFO "alloc one val = %d\n",object->val);
        kmem_cache_free( test_cachep, object );//歸還對(duì)象到高速緩存
        //這句話的意思是雖然對(duì)象歸還到了高速緩存中，但是高速緩存中的值沒(méi)有做修改
        //只是修改了一些它的狀態(tài)鲜漩。
        printk(KERN_INFO "alloc three val = %d\n",object->val);
            object = NULL;
        }else
            return -ENOMEM;
    return 0;
}

static void  __exit slab_clean(void)
{
    printk(KERN_INFO "slab_clean\n");
    if(test_cachep)
                kmem_cache_destroy(test_cachep);//調(diào)用這個(gè)函數(shù)時(shí)test_cachep所指向的緩存中所有的slab都要為空

}

module_init(slab_init);
module_exit(slab_clean);
MODULE_LICENSE("GPL");

我們結(jié)合結(jié)果來(lái)分析下這個(gè)內(nèi)核模塊：

image.png

image.png

image.png

6.總結(jié)

目前只是對(duì)slab機(jī)制的原理有了一個(gè)感性的認(rèn)識(shí)肖粮，對(duì)于這部分相關(guān)的源碼涉及到著色以及內(nèi)存對(duì)齊等細(xì)節(jié)孤页。看的不是很清楚涩馆，后面還需要仔細(xì)研究行施。