slab分配器設(shè)計的需求

在linux內(nèi)核的內(nèi)存子系統(tǒng)中，伙伴系統(tǒng)無疑處于內(nèi)存管理的核心地帶，但是如果將內(nèi)存管理從邏輯上分層，它的位置則處于最底層。Buddy是所有物理內(nèi)存的管家，不論使用何種接口申請內(nèi)存都要經(jīng)由伙伴系統(tǒng)進行分配。但是，伙伴系統(tǒng)管理的物理內(nèi)存是以頁為單位，以4K頁為例，它也包含了4096個字節(jié)。但是無論是內(nèi)核自己還是用戶程序，在日常的使用中都很少會需要使用四千多字節(jié)大小的內(nèi)存。試想如果我們僅需要為10個字符的字符串分配內(nèi)存，但是伙伴系統(tǒng)卻給了我們一頁，那這一頁剩余沒有使用的內(nèi)存就浪費了，而且這個浪費近乎奢侈。除了浪費的問題， 還有一個更需要關(guān)心的問題是，在這樣的分配情況下，如果分配非常頻繁，系統(tǒng)可能很快就會面臨嚴(yán)重的碎片化問題。因為頻繁使用的數(shù)據(jù)結(jié)構(gòu)也會頻繁的分配和釋放，加速生產(chǎn)內(nèi)存碎片。另外，直接調(diào)用伙伴系統(tǒng)的操作對系統(tǒng)的數(shù)據(jù)和指令高速緩存也有很大的影響。所以，基于以上的原因，也源于現(xiàn)實需求，內(nèi)核需要一種輕量的、快速的、靈活的新型內(nèi)存分配器，最主要的是，它可以提供小塊內(nèi)存的分配。為了實現(xiàn)這樣的小內(nèi)存分配器，Sun公司的J.Bonwick首先在Solaris 2.4中設(shè)計并實現(xiàn)了slab分配器，并對其開源。在Linux中也實現(xiàn)了具有相同的基本設(shè)計思想的同名分配器slab。

slab、slob和slub關(guān)系

slab、slob和slub都是小內(nèi)存分配器，slab是slob和slub實現(xiàn)的基礎(chǔ)，而slob和slub是針對slab在不同場景下的優(yōu)化版本。在slab引入Linux的很多年內(nèi)，其都是Linux內(nèi)核管理對象緩沖區(qū)的主流算法。并且由于slab的實現(xiàn)非常復(fù)雜，很長一段時間內(nèi)都少有對它的改動。隨著多處理器的發(fā)展和NUMA架構(gòu)的廣泛應(yīng)用，slab的不足也逐漸顯現(xiàn)。slab的緩存隊列管理復(fù)雜，其用于管理的數(shù)據(jù)結(jié)構(gòu)存儲開銷大，對NUMA支持復(fù)雜，slab著色機制效果不明顯。這些不足讓slab很難在兩種場景下提供最優(yōu)的性能：小型嵌入式系統(tǒng)和配備有大量物理內(nèi)存的大規(guī)模并行系統(tǒng)。對于小型嵌入式系統(tǒng)來說，slab分配器的代碼量和復(fù)雜性都太高；對于大規(guī)模并行系統(tǒng)，slab用于自身管理的數(shù)據(jù)結(jié)構(gòu)就需要占用很多G字節(jié)內(nèi)存。針對slab的不足，內(nèi)核開發(fā)人員Christoph Lameter在在內(nèi)核版本2.6開發(fā)期間，引入了新的Slub分配器。Slub簡化了slab一些復(fù)雜的設(shè)計，但保持slab的基本設(shè)計思想。同時，一種新的針對小型嵌入式系統(tǒng)的分配器slob也被引入，為了適應(yīng)嵌入式系統(tǒng)的特點，slob進行了特別的優(yōu)化，以大幅減少代碼量（slob只有大約600行代碼）。

slab層在內(nèi)存管理子系統(tǒng)的層次

slab層可以理解為一個通用層，其包含了slab、slob和slub，至于底層具體使用哪種分配器可以通過配置內(nèi)核選項進行選擇。對于內(nèi)核的其他模塊，則不需要關(guān)注底層使用了哪個分配器。因為為了保證內(nèi)核的其他模塊都可以無縫遷移到Slub/slob，所有分配器的接口都是相同的，它們都實現(xiàn)了一組特定的接口用于內(nèi)存分配。下圖為Slab層在內(nèi)存管理中的層次圖：

 

邏輯上看，slab層位于伙伴系統(tǒng)之上。因為Buddy是最底層的分配器，Slub需要先向Buddy申請內(nèi)存，而不能越過Buddy獲取page。從Buddy申請到內(nèi)存后，Slub才可以對其進行自己的操作。

 

、slab分配器設(shè)計的需求

在Linux內(nèi)核的內(nèi)存子系統(tǒng)中，伙伴系統(tǒng)無疑處于內(nèi)存管理的核心地帶，但是如果將內(nèi)存管理從邏輯上分層，它的位置則處于最底層。Buddy是所有物理內(nèi)存的管家，不論使用何種接口申請內(nèi)存都要經(jīng)由伙伴系統(tǒng)進行分配。但是，伙伴系統(tǒng)管理的物理內(nèi)存是以頁為單位，以4K頁為例，它也包含了4096個字節(jié)。但是無論是內(nèi)核自己還是用戶程序，在日常的使用中都很少會需要使用四千多字節(jié)大小的內(nèi)存。試想如果我們僅需要為10個字符的字符串分配內(nèi)存，但是伙伴系統(tǒng)卻給了我們一頁，那這一頁剩余沒有使用的內(nèi)存就浪費了，而且這個浪費近乎奢侈。除了浪費的問題， 還有一個更需要關(guān)心的問題是，在這樣的分配情況下，如果分配非常頻繁，系統(tǒng)可能很快就會面臨嚴(yán)重的碎片化問題。因為頻繁使用的數(shù)據(jù)結(jié)構(gòu)也會頻繁的分配和釋放，加速生產(chǎn)內(nèi)存碎片。另外，直接調(diào)用伙伴系統(tǒng)的操作對系統(tǒng)的數(shù)據(jù)和指令高速緩存也有很大的影響。所以，基于以上的原因，也源于現(xiàn)實需求，內(nèi)核需要一種輕量的、快速的、靈活的新型內(nèi)存分配器，最主要的是，它可以提供小塊內(nèi)存的分配。為了實現(xiàn)這樣的小內(nèi)存分配器，Sun公司的J.Bonwick首先在Solaris 2.4中設(shè)計并實現(xiàn)了slab分配器，并對其開源。在Linux中也實現(xiàn)了具有相同的基本設(shè)計思想的同名分配器slab。

slab、slob和slub關(guān)系

slab、slob和slub都是小內(nèi)存分配器，slab是slob和slub實現(xiàn)的基礎(chǔ)，而slob和slub是針對slab在不同場景下的優(yōu)化版本。在slab引入Linux的很多年內(nèi)，其都是Linux內(nèi)核管理對象緩沖區(qū)的主流算法。并且由于slab的實現(xiàn)非常復(fù)雜，很長一段時間內(nèi)都少有對它的改動。隨著多處理器的發(fā)展和NUMA架構(gòu)的廣泛應(yīng)用，slab的不足也逐漸顯現(xiàn)。slab的緩存隊列管理復(fù)雜，其用于管理的數(shù)據(jù)結(jié)構(gòu)存儲開銷大，對NUMA支持復(fù)雜，slab著色機制效果不明顯。這些不足讓slab很難在兩種場景下提供最優(yōu)的性能：小型嵌入式系統(tǒng)和配備有大量物理內(nèi)存的大規(guī)模并行系統(tǒng)。對于小型嵌入式系統(tǒng)來說，slab分配器的代碼量和復(fù)雜性都太高；對于大規(guī)模并行系統(tǒng)，slab用于自身管理的數(shù)據(jù)結(jié)構(gòu)就需要占用很多G字節(jié)內(nèi)存。針對slab的不足，內(nèi)核開發(fā)人員Christoph Lameter在在內(nèi)核版本2.6開發(fā)期間，引入了新的Slub分配器。Slub簡化了slab一些復(fù)雜的設(shè)計，但保持slab的基本設(shè)計思想。同時，一種新的針對小型嵌入式系統(tǒng)的分配器slob也被引入，為了適應(yīng)嵌入式系統(tǒng)的特點，slob進行了特別的優(yōu)化，以大幅減少代碼量（slob只有大約600行代碼）。

slab層在內(nèi)存管理子系統(tǒng)的層次

slab層可以理解為一個通用層，其包含了slab、slob和slub，至于底層具體使用哪種分配器可以通過配置內(nèi)核選項進行選擇。對于內(nèi)核的其他模塊，則不需要關(guān)注底層使用了哪個分配器。因為為了保證內(nèi)核的其他模塊都可以無縫遷移到Slub/slob，所有分配器的接口都是相同的，它們都實現(xiàn)了一組特定的接口用于內(nèi)存分配。下圖為Slab層在內(nèi)存管理中的層次圖：

 

邏輯上看，slab層位于伙伴系統(tǒng)之上。因為Buddy是最底層的分配器，Slub需要先向Buddy申請內(nèi)存，而不能越過Buddy獲取page。從Buddy申請到內(nèi)存后，Slub才可以對其進行自己的操作。

slub分配器框架

下圖是在讀完宋牧春大俠的《圖解Slub》后，我也總結(jié)了一張Slub分配器框架圖，可以大致的看到Slub的框架。Slub的框架如下圖（圖片很大，可以放大）：

 

這篇文章（原文鏈接以置文末）中用了一個通俗易懂的例子來介紹Slub的工作原理，我覺的這個例子很恰當(dāng)，所以這里繼續(xù)借舉一下。

每個數(shù)組元素對應(yīng)一種大小的內(nèi)存，可以把一個kmem_cache結(jié)構(gòu)體看做是一個特定大小內(nèi)存的零售商，整個Slub系統(tǒng)中有很多個這樣的零售商，每個“零售商”只“零售”特定大小的內(nèi)存，例如：有的“零售商”只"零售"8Byte大小的內(nèi)存，有的只”零售“16Byte大小的內(nèi)存。——引自luken.《linux內(nèi)核內(nèi)存管理slub算法(一)原理》

Slub的工作原理和日常生產(chǎn)生活的產(chǎn)銷環(huán)節(jié)很類似，所以為了清晰直觀的看到其工作原理，我把這個過程畫了一幅圖來表示，如下圖：

 

每個零售商(kmem_cache)有兩個“部門”，一個是“倉庫”：kmem_cache_node，一個“營業(yè)廳”：kmem_cache_cpu。“營業(yè)廳”里只保留一個slab，只有在營業(yè)廳(kmem_cache_cpu)中沒有空閑內(nèi)存的情況下才會從倉庫中換出其他的slab。所謂slab就是零售商(kmem_cache)批發(fā)的連續(xù)的整頁內(nèi)存，零售商把這些整頁的內(nèi)存分成許多小內(nèi)存，然后分別“零售”出去，一個slab可能包含多個連續(xù)的內(nèi)存頁。slab的大小和零售商有關(guān)。——引自luken.《linux內(nèi)核內(nèi)存管理slub算法(一)原理》

總的來說，Slub就相當(dāng)于零售商，它從伙伴系統(tǒng)“批發(fā)”內(nèi)存，然后再零售出去。

slub的重要數(shù)據(jù)結(jié)構(gòu)

• kmem_cache

struct kmem_cache {
    struct kmem_cache_cpu __percpu *cpu_slab;
    /* Used for retriving partial slabs etc */
    unsigned long flags;
    unsigned long min_partial;
    /* size = object_size + 對象后面下個空閑對象的指針的size */
    int size;           /* The size of an object including meta data */
    int object_size;    /* The size of an object without meta data */
    /* object首地址 + offset = 下一個空閑對象的指針地址 */
    int offset;         /* Free pointer offset. */
    int cpu_partial;    /* Number of per cpu partial objects to keep around */
    /* 
     * oo表示存放最優(yōu)slab的order和object的數(shù)量
     * 低16位表示對象數(shù)，高16位表示slab的order
     */
    struct kmem_cache_order_objects oo;
    /* Allocation and freeing of slabs */
    struct kmem_cache_order_objects max;
    /* 
     * 最小slab只需要足夠存放一個對象。當(dāng)設(shè)備長時間運行以后，內(nèi)存碎片化嚴(yán)重，
     * 分配連續(xù)物理頁很難成功，如果分配最優(yōu)slab失敗，就分配最小slab。
     */
    struct kmem_cache_order_objects min;
    gfp_t allocflags;   /* gfp flags to use on each alloc */
    int refcount;       /* Refcount for slab cache destroy */
    void (*ctor)(void *);
    int inuse;          /* Offset to metadata */
    int align;          /* Alignment */
    // 當(dāng)slab長度不是對象長度的整數(shù)倍的時候，尾部有剩余部分，保存在reserved中
    int reserved;       /* Reserved bytes at the end of slabs */
    const char *name;   /* Name (only for display!) */
    struct list_head list;  /* List of slab caches */
    int red_left_pad;   /* Left redzone padding size */
#ifdef CONFIG_SYSFS
    struct kobject kobj;    /* For sysfs */
#endif
#ifdef CONFIG_MEMCG
    struct memcg_cache_params memcg_params;
    int max_attr_size; /* for propagation, maximum size of a stored attr */
#ifdef CONFIG_SYSFS
    struct kset *memcg_kset;
#endif
#endif
#ifdef CONFIG_NUMA
    /*
     * Defragmentation by allocating from a remote node.
     */
    int remote_node_defrag_ratio;
#endif
#ifdef CONFIG_SLAB_FREELIST_RANDOM
    unsigned int *random_seq;
#endif
#ifdef CONFIG_KASAN
    struct kasan_cache kasan_info;
#endif
    struct kmem_cache_node *node[MAX_NUMNODES]; /* 每個NUMA節(jié)點都有一個kmem_cache_node */
};

根據(jù)是否打開Slub Debug，next object指針可以有兩種方式放置，如果打開了Slub Debug，則采用指針外置式；反之，采用指針內(nèi)置式。兩種指針放置方式如下圖：

• 指針外置式

 

• 指針內(nèi)置式

 

指針內(nèi)置式的方法實際上是復(fù)用了object的前8個字節(jié)，因為在object被分配出去之前，這一段內(nèi)存具體存放什么內(nèi)容并不重要，所以可以利用這一段內(nèi)存來保存下一個free object的地址。

• kmem_cache_cpu

struct kmem_cache_cpu {
    /* 指向下一個空閑的object，用于快速找到可用對象 */
    void **freelist;    /* Pointer to next available object */
    /*
     * 要保證tid和kmem_cache是由同一個CPU訪問。
     * 開啟了內(nèi)核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，
     * 所以要檢查是否匹配，直到它們是由同一個CPU進行訪問 
     */
    unsigned long tid;  /* Globally unique transaction id */
    /* 指向當(dāng)前使用的slab */
    struct page *page;  /* The slab from which we are allocating */
    /* 指向當(dāng)前cpu上緩存的部分空閑slab鏈表 */
    struct page *partial;   /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
    /* 
     * 記錄對slab操作的狀態(tài)變化，這個stat非常重要，
     * 通過這個stat就大概了解object從申請到釋放經(jīng)過了哪些步驟 
     */
    unsigned stat[NR_SLUB_STAT_ITEMS]; 
#endif
};

• kmem_cache_node

struct kmem_cache_node {
        spinlock_t list_lock;
        /* 此處省略掉SLAB的配置 */  
#ifdef CONFIG_SLUB
        /* 掛入kmem_cache_node中的slab數(shù)量 */
        unsigned long nr_partial;
        /* 指向當(dāng)前內(nèi)存節(jié)點上的部分空閑slab鏈表 */
        struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
        atomic_long_t nr_slabs;
        atomic_long_t total_objects;
        struct list_head full;
#endif
#endif
};

page中描述Slub信息的字段：

struct page {
     /* 如果flag設(shè)置成PG_slab,表示頁屬于slub分配器 */
      unsigned long flags;
      union {
        struct address_space *mApping;  
        /* 指向當(dāng)前slab中第一個object */
        void *s_mem;      /* slab first object */
        atomic_t compound_mapcount;  /* first tail page */
      };
      union {
        pgoff_t index;    /* Our offset within mapping. */
        /* 指向當(dāng)前slab中第一個空閑的object */
        void *freelist;    /* sl[aou]b first free object */
      };
      union {
        unsigned counters;
        struct {
          union {
            atomic_t _mapcount;
            unsigned int active;    /* SLAB */
            struct {      /* SLUB */
              /* 該slab中已經(jīng)分配使用的object數(shù)量 */
              unsigned inuse:16;
              /* 該slab中的所有object數(shù)量 */
              unsigned objects:15;
              /* 
               * 如果slab在kmem_cache_cpu中，表示處于凍結(jié)狀態(tài)；
               * 如果slab在kmem_cache_node的部分空閑slab鏈表中，表示處于解凍狀態(tài)
        */
              unsigned frozen:1;
            };
            int units;      /* SLOB */
          };
          atomic_t _refcount;
        };
      };
      union {
        /* 作為鏈表節(jié)點加入到kmem_cache_node的部分空閑slab鏈表中
        struct list_head lru;  /* Pageout list   */
        struct dev_pagemap *pgmap; 
        struct {    /* slub per cpu partial pages */
          struct page *next;  /* Next partial slab */
          int pages;  /* Nr of partial slabs left */
          int pobjects;  /* Approximate # of objects */
        };
        struct rcu_head rcu_head;
        struct {
          unsigned long compound_head; /* If bit zero is set */
          unsigned int compound_dtor;
          unsigned int compound_order;
        };
      };
      union {
        unsigned long private;
        struct kmem_cache *slab_cache;  /* SL[AU]B: Pointer to slab */
      };
    ......
    }

Slub的分配過程

Slub的分配流程大致如下：首先從kmem_cache_cpu中分配，如果沒有則從kmem_cache_cpu的partial鏈表分配，如果還沒有則從kmem_cache_node中分配，如果kmem_cache_node中也沒有，則需要向伙伴系統(tǒng)申請內(nèi)存。

 

Slub的分配接口是kmem_cache_malloc()。其分配object的流程大概如下：首先在kmem_cache_cpu所使用的slab中查找free object，如果當(dāng)前slab中有free object，則返回這個object。如果當(dāng)前slab沒有free object，就要看Slub是否開啟了kmem_cache_cpu的Partial隊列，如果開啟了partial隊列，就在Partial隊列中查看有沒有free object的slab，如果有的話就選定這個slab，并返回其free object。如果kmem_cache_cpu的partial鏈表中也沒有擁有free object的slab，則在kmem_cache_node中查找。如果kmem_cache_node中的slab有free object，則選定這個slab并返回free object。如果kmem_cache_node中也沒有free object，則需要向伙伴系統(tǒng)申請內(nèi)存，制作新的slab。

創(chuàng)建slab緩存(kmem_cache)的函數(shù)分析

斗膽分析一下slab緩存的創(chuàng)建過程，新手小白分析內(nèi)核代碼，分析的可能不夠深度和完整，如有不對還請各路高手指教，提前謝過。

函數(shù)調(diào)用流程：

kmem_cache_create()
    ——> kmem_cache_create_usercopy()
        ——> create_cache()
            ——> __kmem_cache_create()
                ——> kmem_cache_open()

下面是每個函數(shù)的主干分析，代碼有精簡。

kmem_cache_create()：

kmem_cache_create()里繼續(xù)調(diào)用了
kmem_cache_create_usercopy()。

kmem_cache_create() {
 return kmem_cache_create_usercopy(name, size, align, flags, 0, 0, ctor);
}

kmem_cache_create_usercopy()：

kmem_cache_create_usercopy() {
 struct kmem_cache *s = NULL;
 const char *cache_name;
 
 /*
  * Some allocators will constraint the set of valid flags to a subset
  * of all flags. We expect them to define CACHE_CREATE_MASK in this
  * case, and we'll just provide them with a sanitized version of the
  * passed flags.
  */
 flags &= CACHE_CREATE_MASK;
 
 /* 定義這個緩存的名字，用于在/proc/slabinfo中顯示 */
 cache_name = kstrdup_const(name, GFP_KERNEL);
 
 /* kmem_cache結(jié)構(gòu)，并返回其地址 */
 s = create_cache(cache_name, size,
    calculate_alignment(flags, align, size),
    flags, useroffset, usersize, ctor, NULL, NULL);
 
 return s;
}

create_cache()：

create_cache() {
 struct kmem_cache *s;
 int err;

 /* 為kmem_cache結(jié)構(gòu)申請一段內(nèi)存并清零 */
 s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);

 /* 初始化kmem_cache結(jié)構(gòu)的部分成員 */
 s->name = name;
 s->size = s->object_size = object_size;
 s->align = align;
 s->ctor = ctor;
 s->useroffset = useroffset;
 s->usersize = usersize;

 /* 核心函數(shù)，slub/slab/slob都實現(xiàn)了這個函數(shù) */
 err = __kmem_cache_create(s, flags);
 
 /* 將新創(chuàng)建的kmem_cache加入slab caches鏈表 */
 list_add(&s->list, &slab_caches);
 
 return s;
    }

__kmem_cache_create()：

__kmem_cache_create() {
  int err;

  /* 在kmem_cache_open中處理剩余的結(jié)構(gòu)成員，如min_partial、cpu_partial等 */
  err = kmem_cache_open(s, flags);
 }

kmem_cache_open()：

kmem_cache_open() {
 /* 設(shè)置kmem_cache中的min_partial,它表示kmem_cache_node中partial鏈表可掛入的slab數(shù)量 */
 set_min_partial(s, ilog2(s->size) / 2);
 
 /* 設(shè)置kmem_cache中的cpu_partial,它表示per cpu partial上所有slab中free object總數(shù) */
 set_cpu_partial(s);
 
 /* 為每個節(jié)點分配kmem_cache_node */
 if (!init_kmem_cache_nodes(s))
  goto error;

 /* 為kmem_cache_cpu變量創(chuàng)建每CPU副本 */
 if (alloc_kmem_cache_cpus(s))
  return 0;
}

分配對象(object)的函數(shù)分析

函數(shù)調(diào)用流程：

kmem_cache_alloc()
    ——> slab_alloc()
        ——> slab_alloc_node()
           ——> __slab_alloc()
              ——> ___slab_alloc()

kmem_cache_alloc()：

kmem_cache_alloc() {
 /* 直接調(diào)用slab_alloc */
 void *ret = slab_alloc(s, gfpflags, _RET_IP_);

 return ret;
}

slab_alloc()：

slab_alloc() {
 return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
}

slab_alloc_node()：

slab_alloc_node() {
 void *object;  
 struct kmem_cache_cpu *c;
 struct page *page;

redo:
 /*
  * 要保證tid和kmem_cache是由同一個CPU訪問。但是如果配置了CONFIG_PREEMPT = y，
  * 即開啟了內(nèi)核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，所以要檢查
  * 是否匹配，直到它們是由同一個CPU進行訪問。
  * 
  * 內(nèi)核態(tài)搶占的時機是：
  * 1.中斷處理函數(shù)返回內(nèi)核空間之前會檢查請求重新調(diào)度的標(biāo)志(TIF_NEED_RESCHED)，
  * 如果置位則調(diào)用preempt_schedule_irq()執(zhí)行搶占。
  * 2. 當(dāng)內(nèi)核從non-preemptible(禁止搶占)狀態(tài)變成preemptible(允許搶占)的時候。
  */
 do {
  tid = this_cpu_read(s->cpu_slab->tid); /* 訪問當(dāng)前CPU的per CPU變量的副本的tid */
  c = raw_cpu_ptr(s->cpu_slab);
 } while (IS_ENABLED(CONFIG_PREEMPT) &&  /* 檢查是否開啟了內(nèi)核搶占 */
   unlikely(tid != READ_ONCE(c->tid)));

 barrier(); /* 內(nèi)存屏障，消除指令亂序執(zhí)行的影響 */

 object = c->freelist;  /* 下一個free object的地址 */
 page = c->page;   /* 當(dāng)前使用的slab */
 if (unlikely(!object || !node_match(page, node))) {
  /* 調(diào)用核心函數(shù)__slab_alloc() */
  object = __slab_alloc(s, gfpflags, node, addr, c);
  stat(s, ALLOC_SLOWPATH);
 } else {
  void *next_object = get_freepointer_safe(s, object);

  if (unlikely(!this_cpu_cmpxchg_double(
    s->cpu_slab->freelist, s->cpu_slab->tid,
    object, tid,
    next_object, next_tid(tid)))) {

   note_cmpxchg_failure("slab_alloc", s, tid);
   goto redo;
  }
  prefetch_freepointer(s, next_object);
  stat(s, ALLOC_FASTPATH);
 }

 maybe_wipe_obj_freeptr(s, object);

 /* 如果gfpflags標(biāo)志需要對object對象的內(nèi)存清零 */
 if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
  memset(object, 0, s->object_size);

 slab_post_alloc_hook(s, gfpflags, 1, &object);

 return object;
    }

__slab_alloc()：

__slab_alloc() {
 void *p;
 unsigned long flags;
 
 /* 
  * 關(guān)中斷。關(guān)閉當(dāng)前處理器上的所有中斷處理
  *
  * local_irq_save()將當(dāng)前的中斷狀態(tài)(開或關(guān))
  * 保存在flags中然后再禁用處理器上的中斷。
  * 
  * 與local_irq_save不同，local_irq_disable()
  * 不保存狀態(tài)而關(guān)閉本地處理器的中斷服務(wù)。 
  */
 local_irq_save(flags);  
#ifdef CONFIG_PREEMPT
 /*
  * 在關(guān)中斷之前，可能已經(jīng)被搶占并被調(diào)度在不同的CPU上，
  * 所以需要重新加載CPU區(qū)域的指針。
  */
 c = this_cpu_ptr(s->cpu_slab);
#endif
 /* 調(diào)用核心函數(shù)___slab_alloc() */
 p = ___slab_alloc(s, gfpflags, node, addr, c);
 
 /*
  * 恢復(fù)本地處理器的中斷。
  *
  * local_irq_restore()將local_irq_save()保存的狀態(tài)值(flags)恢復(fù)，
  * 注意是恢復(fù)之前的中斷狀態(tài)，不一定會開啟中斷。如果之前的狀態(tài)是
  * 開中斷，就打開中斷；如果之前的狀態(tài)是關(guān)中斷，就關(guān)閉中斷。
  * 而local_irq_enable()會無條件開啟中斷，所以可能會破壞之前的中
  * 斷環(huán)境。所以local_irq_restore()比local_irq_enable()更安全。
  */
 local_irq_restore(flags); 
 
        return p;
}

slub的frozen（凍結(jié)）和unfrozen（解凍）

如果cpu1的kcmem_cache_cpu的slab是frozen, 那么cpu1可以從該slab中取出或放回obj，但是cpu2不能從該slab中取obj, 只能把obj還給該slab。另外，cpu partial上的slab都是frozen狀態(tài)。node partial上的slab都是unfrozen。耗盡kmem_cache_cpu的slab的obj后解凍slab。

嵌入式物聯(lián)網(wǎng)需要學(xué)的東西真的非常多，千萬不要學(xué)錯了路線和內(nèi)容，導(dǎo)致工資要不上去！

無償分享大家一個資料包，差不多150多G。里面學(xué)習(xí)內(nèi)容、面經(jīng)、項目都比較新也比較全！某魚上買估計至少要好幾十。

點擊這里找小助理0元領(lǐng)取：嵌入式物聯(lián)網(wǎng)學(xué)習(xí)資料（頭條）

 

 

slub分配器框架

下圖是在讀完宋牧春大俠的《圖解Slub》后，我也總結(jié)了一張Slub分配器框架圖，可以大致的看到Slub的框架。Slub的框架如下圖（圖片很大，可以放大）：

 

這篇文章（原文鏈接以置文末）中用了一個通俗易懂的例子來介紹Slub的工作原理，我覺的這個例子很恰當(dāng)，所以這里繼續(xù)借舉一下。

每個數(shù)組元素對應(yīng)一種大小的內(nèi)存，可以把一個kmem_cache結(jié)構(gòu)體看做是一個特定大小內(nèi)存的零售商，整個Slub系統(tǒng)中有很多個這樣的零售商，每個“零售商”只“零售”特定大小的內(nèi)存，例如：有的“零售商”只"零售"8Byte大小的內(nèi)存，有的只”零售“16Byte大小的內(nèi)存。——引自luken.《linux內(nèi)核內(nèi)存管理slub算法(一)原理》

Slub的工作原理和日常生產(chǎn)生活的產(chǎn)銷環(huán)節(jié)很類似，所以為了清晰直觀的看到其工作原理，我把這個過程畫了一幅圖來表示，如下圖：

 

每個零售商(kmem_cache)有兩個“部門”，一個是“倉庫”：kmem_cache_node，一個“營業(yè)廳”：kmem_cache_cpu。“營業(yè)廳”里只保留一個slab，只有在營業(yè)廳(kmem_cache_cpu)中沒有空閑內(nèi)存的情況下才會從倉庫中換出其他的slab。所謂slab就是零售商(kmem_cache)批發(fā)的連續(xù)的整頁內(nèi)存，零售商把這些整頁的內(nèi)存分成許多小內(nèi)存，然后分別“零售”出去，一個slab可能包含多個連續(xù)的內(nèi)存頁。slab的大小和零售商有關(guān)。——引自luken.《linux內(nèi)核內(nèi)存管理slub算法(一)原理》

總的來說，Slub就相當(dāng)于零售商，它從伙伴系統(tǒng)“批發(fā)”內(nèi)存，然后再零售出去。

slub的重要數(shù)據(jù)結(jié)構(gòu)

• kmem_cache

struct kmem_cache {
    struct kmem_cache_cpu __percpu *cpu_slab;
    /* Used for retriving partial slabs etc */
    unsigned long flags;
    unsigned long min_partial;
    /* size = object_size + 對象后面下個空閑對象的指針的size */
    int size;           /* The size of an object including meta data */
    int object_size;    /* The size of an object without meta data */
    /* object首地址 + offset = 下一個空閑對象的指針地址 */
    int offset;         /* Free pointer offset. */
    int cpu_partial;    /* Number of per cpu partial objects to keep around */
    /* 
     * oo表示存放最優(yōu)slab的order和object的數(shù)量
     * 低16位表示對象數(shù)，高16位表示slab的order
     */
    struct kmem_cache_order_objects oo;
    /* Allocation and freeing of slabs */
    struct kmem_cache_order_objects max;
    /* 
     * 最小slab只需要足夠存放一個對象。當(dāng)設(shè)備長時間運行以后，內(nèi)存碎片化嚴(yán)重，
     * 分配連續(xù)物理頁很難成功，如果分配最優(yōu)slab失敗，就分配最小slab。
     */
    struct kmem_cache_order_objects min;
    gfp_t allocflags;   /* gfp flags to use on each alloc */
    int refcount;       /* Refcount for slab cache destroy */
    void (*ctor)(void *);
    int inuse;          /* Offset to metadata */
    int align;          /* Alignment */
    // 當(dāng)slab長度不是對象長度的整數(shù)倍的時候，尾部有剩余部分，保存在reserved中
    int reserved;       /* Reserved bytes at the end of slabs */
    const char *name;   /* Name (only for display!) */
    struct list_head list;  /* List of slab caches */
    int red_left_pad;   /* Left redzone padding size */
#ifdef CONFIG_SYSFS
    struct kobject kobj;    /* For sysfs */
#endif
#ifdef CONFIG_MEMCG
    struct memcg_cache_params memcg_params;
    int max_attr_size; /* for propagation, maximum size of a stored attr */
#ifdef CONFIG_SYSFS
    struct kset *memcg_kset;
#endif
#endif
#ifdef CONFIG_NUMA
    /*
     * Defragmentation by allocating from a remote node.
     */
    int remote_node_defrag_ratio;
#endif
#ifdef CONFIG_SLAB_FREELIST_RANDOM
    unsigned int *random_seq;
#endif
#ifdef CONFIG_KASAN
    struct kasan_cache kasan_info;
#endif
    struct kmem_cache_node *node[MAX_NUMNODES]; /* 每個NUMA節(jié)點都有一個kmem_cache_node */
};

根據(jù)是否打開Slub Debug，next object指針可以有兩種方式放置，如果打開了Slub Debug，則采用指針外置式；反之，采用指針內(nèi)置式。兩種指針放置方式如下圖：

• 指針外置式

 

• 指針內(nèi)置式

 

指針內(nèi)置式的方法實際上是復(fù)用了object的前8個字節(jié)，因為在object被分配出去之前，這一段內(nèi)存具體存放什么內(nèi)容并不重要，所以可以利用這一段內(nèi)存來保存下一個free object的地址。

• kmem_cache_cpu

struct kmem_cache_cpu {
    /* 指向下一個空閑的object，用于快速找到可用對象 */
    void **freelist;    /* Pointer to next available object */
    /*
     * 要保證tid和kmem_cache是由同一個CPU訪問。
     * 開啟了內(nèi)核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，
     * 所以要檢查是否匹配，直到它們是由同一個CPU進行訪問 
     */
    unsigned long tid;  /* Globally unique transaction id */
    /* 指向當(dāng)前使用的slab */
    struct page *page;  /* The slab from which we are allocating */
    /* 指向當(dāng)前cpu上緩存的部分空閑slab鏈表 */
    struct page *partial;   /* Partially allocated frozen slabs */
#ifdef CONFIG_SLUB_STATS
    /* 
     * 記錄對slab操作的狀態(tài)變化，這個stat非常重要，
     * 通過這個stat就大概了解object從申請到釋放經(jīng)過了哪些步驟 
     */
    unsigned stat[NR_SLUB_STAT_ITEMS]; 
#endif
};

• kmem_cache_node

struct kmem_cache_node {
        spinlock_t list_lock;
        /* 此處省略掉SLAB的配置 */  
#ifdef CONFIG_SLUB
        /* 掛入kmem_cache_node中的slab數(shù)量 */
        unsigned long nr_partial;
        /* 指向當(dāng)前內(nèi)存節(jié)點上的部分空閑slab鏈表 */
        struct list_head partial;
#ifdef CONFIG_SLUB_DEBUG
        atomic_long_t nr_slabs;
        atomic_long_t total_objects;
        struct list_head full;
#endif
#endif
};

page中描述Slub信息的字段：

struct page {
     /* 如果flag設(shè)置成PG_slab,表示頁屬于slub分配器 */
      unsigned long flags;
      union {
        struct address_space *mapping;  
        /* 指向當(dāng)前slab中第一個object */
        void *s_mem;      /* slab first object */
        atomic_t compound_mapcount;  /* first tail page */
      };
      union {
        pgoff_t index;    /* Our offset within mapping. */
        /* 指向當(dāng)前slab中第一個空閑的object */
        void *freelist;    /* sl[aou]b first free object */
      };
      union {
        unsigned counters;
        struct {
          union {
            atomic_t _mapcount;
            unsigned int active;    /* SLAB */
            struct {      /* SLUB */
              /* 該slab中已經(jīng)分配使用的object數(shù)量 */
              unsigned inuse:16;
              /* 該slab中的所有object數(shù)量 */
              unsigned objects:15;
              /* 
               * 如果slab在kmem_cache_cpu中，表示處于凍結(jié)狀態(tài)；
               * 如果slab在kmem_cache_node的部分空閑slab鏈表中，表示處于解凍狀態(tài)
        */
              unsigned frozen:1;
            };
            int units;      /* SLOB */
          };
          atomic_t _refcount;
        };
      };
      union {
        /* 作為鏈表節(jié)點加入到kmem_cache_node的部分空閑slab鏈表中
        struct list_head lru;  /* Pageout list   */
        struct dev_pagemap *pgmap; 
        struct {    /* slub per cpu partial pages */
          struct page *next;  /* Next partial slab */
          int pages;  /* Nr of partial slabs left */
          int pobjects;  /* Approximate # of objects */
        };
        struct rcu_head rcu_head;
        struct {
          unsigned long compound_head; /* If bit zero is set */
          unsigned int compound_dtor;
          unsigned int compound_order;
        };
      };
      union {
        unsigned long private;
        struct kmem_cache *slab_cache;  /* SL[AU]B: Pointer to slab */
      };
    ......
    }

Slub的分配過程

Slub的分配流程大致如下：首先從kmem_cache_cpu中分配，如果沒有則從kmem_cache_cpu的partial鏈表分配，如果還沒有則從kmem_cache_node中分配，如果kmem_cache_node中也沒有，則需要向伙伴系統(tǒng)申請內(nèi)存。

 

Slub的分配接口是kmem_cache_malloc()。其分配object的流程大概如下：首先在kmem_cache_cpu所使用的slab中查找free object，如果當(dāng)前slab中有free object，則返回這個object。如果當(dāng)前slab沒有free object，就要看Slub是否開啟了kmem_cache_cpu的Partial隊列，如果開啟了partial隊列，就在Partial隊列中查看有沒有free object的slab，如果有的話就選定這個slab，并返回其free object。如果kmem_cache_cpu的partial鏈表中也沒有擁有free object的slab，則在kmem_cache_node中查找。如果kmem_cache_node中的slab有free object，則選定這個slab并返回free object。如果kmem_cache_node中也沒有free object，則需要向伙伴系統(tǒng)申請內(nèi)存，制作新的slab。

創(chuàng)建slab緩存(kmem_cache)的函數(shù)分析

斗膽分析一下slab緩存的創(chuàng)建過程，新手小白分析內(nèi)核代碼，分析的可能不夠深度和完整，如有不對還請各路高手指教，提前謝過。

函數(shù)調(diào)用流程：

kmem_cache_create()
    ——> kmem_cache_create_usercopy()
        ——> create_cache()
            ——> __kmem_cache_create()
                ——> kmem_cache_open()

下面是每個函數(shù)的主干分析，代碼有精簡。

kmem_cache_create()：

kmem_cache_create()里繼續(xù)調(diào)用了
kmem_cache_create_usercopy()。

kmem_cache_create() {
 return kmem_cache_create_usercopy(name, size, align, flags, 0, 0, ctor);
}

kmem_cache_create_usercopy()：

kmem_cache_create_usercopy() {
 struct kmem_cache *s = NULL;
 const char *cache_name;
 
 /*
  * Some allocators will constraint the set of valid flags to a subset
  * of all flags. We expect them to define CACHE_CREATE_MASK in this
  * case, and we'll just provide them with a sanitized version of the
  * passed flags.
  */
 flags &= CACHE_CREATE_MASK;
 
 /* 定義這個緩存的名字，用于在/proc/slabinfo中顯示 */
 cache_name = kstrdup_const(name, GFP_KERNEL);
 
 /* kmem_cache結(jié)構(gòu)，并返回其地址 */
 s = create_cache(cache_name, size,
    calculate_alignment(flags, align, size),
    flags, useroffset, usersize, ctor, NULL, NULL);
 
 return s;
}

create_cache()：

create_cache() {
 struct kmem_cache *s;
 int err;

 /* 為kmem_cache結(jié)構(gòu)申請一段內(nèi)存并清零 */
 s = kmem_cache_zalloc(kmem_cache, GFP_KERNEL);

 /* 初始化kmem_cache結(jié)構(gòu)的部分成員 */
 s->name = name;
 s->size = s->object_size = object_size;
 s->align = align;
 s->ctor = ctor;
 s->useroffset = useroffset;
 s->usersize = usersize;

 /* 核心函數(shù)，slub/slab/slob都實現(xiàn)了這個函數(shù) */
 err = __kmem_cache_create(s, flags);
 
 /* 將新創(chuàng)建的kmem_cache加入slab caches鏈表 */
 list_add(&s->list, &slab_caches);
 
 return s;
    }

__kmem_cache_create()：

__kmem_cache_create() {
  int err;

  /* 在kmem_cache_open中處理剩余的結(jié)構(gòu)成員，如min_partial、cpu_partial等 */
  err = kmem_cache_open(s, flags);
 }

kmem_cache_open()：

kmem_cache_open() {
 /* 設(shè)置kmem_cache中的min_partial,它表示kmem_cache_node中partial鏈表可掛入的slab數(shù)量 */
 set_min_partial(s, ilog2(s->size) / 2);
 
 /* 設(shè)置kmem_cache中的cpu_partial,它表示per cpu partial上所有slab中free object總數(shù) */
 set_cpu_partial(s);
 
 /* 為每個節(jié)點分配kmem_cache_node */
 if (!init_kmem_cache_nodes(s))
  goto error;

 /* 為kmem_cache_cpu變量創(chuàng)建每CPU副本 */
 if (alloc_kmem_cache_cpus(s))
  return 0;
}

分配對象(object)的函數(shù)分析

函數(shù)調(diào)用流程：

kmem_cache_alloc()
    ——> slab_alloc()
        ——> slab_alloc_node()
           ——> __slab_alloc()
              ——> ___slab_alloc()

kmem_cache_alloc()：

kmem_cache_alloc() {
 /* 直接調(diào)用slab_alloc */
 void *ret = slab_alloc(s, gfpflags, _RET_IP_);

 return ret;
}

slab_alloc()：

slab_alloc() {
 return slab_alloc_node(s, gfpflags, NUMA_NO_NODE, addr);
}

slab_alloc_node()：

slab_alloc_node() {
 void *object;  
 struct kmem_cache_cpu *c;
 struct page *page;

redo:
 /*
  * 要保證tid和kmem_cache是由同一個CPU訪問。但是如果配置了CONFIG_PREEMPT = y，
  * 即開啟了內(nèi)核搶占后，訪問tid和kmem_cache的CPU可能不是同一個CPU，所以要檢查
  * 是否匹配，直到它們是由同一個CPU進行訪問。
  * 
  * 內(nèi)核態(tài)搶占的時機是：
  * 1.中斷處理函數(shù)返回內(nèi)核空間之前會檢查請求重新調(diào)度的標(biāo)志(TIF_NEED_RESCHED)，
  * 如果置位則調(diào)用preempt_schedule_irq()執(zhí)行搶占。
  * 2. 當(dāng)內(nèi)核從non-preemptible(禁止搶占)狀態(tài)變成preemptible(允許搶占)的時候。
  */
 do {
  tid = this_cpu_read(s->cpu_slab->tid); /* 訪問當(dāng)前CPU的per CPU變量的副本的tid */
  c = raw_cpu_ptr(s->cpu_slab);
 } while (IS_ENABLED(CONFIG_PREEMPT) &&  /* 檢查是否開啟了內(nèi)核搶占 */
   unlikely(tid != READ_ONCE(c->tid)));

 barrier(); /* 內(nèi)存屏障，消除指令亂序執(zhí)行的影響 */

 object = c->freelist;  /* 下一個free object的地址 */
 page = c->page;   /* 當(dāng)前使用的slab */
 if (unlikely(!object || !node_match(page, node))) {
  /* 調(diào)用核心函數(shù)__slab_alloc() */
  object = __slab_alloc(s, gfpflags, node, addr, c);
  stat(s, ALLOC_SLOWPATH);
 } else {
  void *next_object = get_freepointer_safe(s, object);

  if (unlikely(!this_cpu_cmpxchg_double(
    s->cpu_slab->freelist, s->cpu_slab->tid,
    object, tid,
    next_object, next_tid(tid)))) {

   note_cmpxchg_failure("slab_alloc", s, tid);
   goto redo;
  }
  prefetch_freepointer(s, next_object);
  stat(s, ALLOC_FASTPATH);
 }

 maybe_wipe_obj_freeptr(s, object);

 /* 如果gfpflags標(biāo)志需要對object對象的內(nèi)存清零 */
 if (unlikely(slab_want_init_on_alloc(gfpflags, s)) && object)
  memset(object, 0, s->object_size);

 slab_post_alloc_hook(s, gfpflags, 1, &object);

 return object;
    }

__slab_alloc()：

__slab_alloc() {
 void *p;
 unsigned long flags;
 
 /* 
  * 關(guān)中斷。關(guān)閉當(dāng)前處理器上的所有中斷處理
  *
  * local_irq_save()將當(dāng)前的中斷狀態(tài)(開或關(guān))
  * 保存在flags中然后再禁用處理器上的中斷。
  * 
  * 與local_irq_save不同，local_irq_disable()
  * 不保存狀態(tài)而關(guān)閉本地處理器的中斷服務(wù)。 
  */
 local_irq_save(flags);  
#ifdef CONFIG_PREEMPT
 /*
  * 在關(guān)中斷之前，可能已經(jīng)被搶占并被調(diào)度在不同的CPU上，
  * 所以需要重新加載CPU區(qū)域的指針。
  */
 c = this_cpu_ptr(s->cpu_slab);
#endif
 /* 調(diào)用核心函數(shù)___slab_alloc() */
 p = ___slab_alloc(s, gfpflags, node, addr, c);
 
 /*
  * 恢復(fù)本地處理器的中斷。
  *
  * local_irq_restore()將local_irq_save()保存的狀態(tài)值(flags)恢復(fù)，
  * 注意是恢復(fù)之前的中斷狀態(tài)，不一定會開啟中斷。如果之前的狀態(tài)是
  * 開中斷，就打開中斷；如果之前的狀態(tài)是關(guān)中斷，就關(guān)閉中斷。
  * 而local_irq_enable()會無條件開啟中斷，所以可能會破壞之前的中
  * 斷環(huán)境。所以local_irq_restore()比local_irq_enable()更安全。
  */
 local_irq_restore(flags); 
 
        return p;
}

slub的frozen（凍結(jié)）和unfrozen（解凍）

如果cpu1的kcmem_cache_cpu的slab是frozen, 那么cpu1可以從該slab中取出或放回obj，但是cpu2不能從該slab中取obj, 只能把obj還給該slab。另外，cpu partial上的slab都是frozen狀態(tài)。node partial上的slab都是unfrozen。耗盡kmem_cache_cpu的slab的obj后解凍slab。

文章鏈接：
https://mp.weixin.qq.com/s/CJW8crYUqtRztavhpOR6uA

轉(zhuǎn)載自一口Linux

文章來源：人人都是極客 ，作者賀東升

版權(quán)申明：本文來源于網(wǎng)絡(luò)，免費傳達知識，版權(quán)歸原作者所有。如涉及作品版權(quán)問題，請聯(lián)系我進行刪除。