Linux 内存管理：slab 分配器

Linux 内存管理是一个非常复杂的子系统，要完全说清的话估计要一本书的篇幅。但 Linux 内存管理可以划分成多个部分来阐述，这篇文章主要介绍 slab 算法。

Linux 有个叫伙伴系统的分配算法，这个算法主要解决分配连续个内存页的问题。伙伴分配算法主要以内存页（ 4KB ）作为分配单位，就是说伙伴分配算法每次可以分配 2 ^order 个内存页（ order 为 0 、 1 、 2...9 ）。但有时候我们只需要申请一个很小的内存区（如 32 字节），这时候使用伙伴分配算法就显得浪费了。为了解决小内存分配问题， Linux 使用了 slab 分配算法。

相关数据结构

slab 算法有两个重要的数据结构，一个是 kmem_cache_t ，另外一个是 slab_t 。下面我们先来看看 kmem_cache_t 结构：

1.        struct  kmem_cache_s { 

2.             struct  list_head    slabs_full;

3.             struct  list_head    slabs_partial;

4.             struct  list_head    slabs_free;

5.             unsigned   int         objsize;

6.             unsigned   int         flags;

7.             unsigned   int         num;

8.            spinlock_t          spinlock; 

9.         

10.            /* 2) slab additions /removals */  

11.           /* order of pgs per slab (2^n) */  

12.            unsigned   int         gfporder; 

13.        

14.            /* force GFP flags, e.g. GFP_DMA */  

15.            unsigned   int         gfpflags; 

16.        

17.           size_t              colour;

18.            unsigned   int         colour_off;

19.            unsigned   int         colour_next;

20.           kmem_cache_t        *slabp_cache; 

21.            ...  

22.            struct  list_head      next;

23.            ...

24.       };

下面介绍一下 kmem_cache_t 结构中比较重要的字段：

1. slab_full ：完全分配的 slab

2. slab_partial ：部分分配的 slab

3. slab_free ：没有被分配过的 slab

4. objsize ：存储的对象大小

5. num ：一个 slab 能够存储的对象个数

6. gfporder ：一个 slab 由 2 ^gfporder 个内存页组成

7. colour/colour_off/colour_next ：着色区大小（后面会讲到）

slab_t 结构定义如下：

1.        typedef   struct  slab_s { 

2.             struct  list_head    list;

3.             unsigned   long        colouroff;

4.             void                 *s_mem;

5.             unsigned   int         inuse;

6.            kmem_bufctl_t        free;

7.        } slab_t;

slab_t 结构各个字段的用途如下：

1. list ：连接（全满 / 部分 / 全空）链

2. colouroff ：着色补偿

3. s_mem ：存储对象的起始内存地址

4. inuse ：已经分配多少个对象

5. free ：用于连接空闲的对象

用图来表示它们之间的关系，如下：

这里需要解释一下，一个 slab 会被划分为多个对象（可以理解为结构体），这些对象是 slab 算法分配的最小单元，而一个 slab 一般有一个或者多个内存页（但不能超过 2 ⁴ 个页面）组成。

在 kmem_cache_t 结构中的 slab_free 链表的 slab 是内存回收的主要备选对象。由于对象是从 slab 中分配和释放，所以单个 slab 可以在 slab 列表中进行一定。例如，当一个 slab 中所有对象被分配完时，就从 slab_partial 列表中移动到 slab_full 列表中。而当一个在 slab_free 列表中的 slab 被分配对象时，就会从 slab_free 列表中移动到 slab_partial 列表中。当一个 slab 中所有对象被释放时，就会从 slab_partial 列表中移动到 slab_free 列表中。

slab分配器初始化

slab 分配器的初始化由 kmem_cache_init() 函数完成，如下：

1.        void  __init kmem_cache_init( void ) 

2.        { 

3.            size_t left_over; 

4.         

5.            init_MUTEX(&cache_chain_sem); 

6.            INIT_LIST_HEAD(&cache_chain); 

7.         

8.            kmem_cache_estimate( 0 , cache_cache.objsize,  0 , 

9.                    &left_over, &cache_cache.num); 

10.            if  (!cache_cache.num) 

11.               BUG(); 

12.        

13.           cache_cache.colour = left_over/cache_cache.colour_off; 

14.           cache_cache.colour_next =  0 ; 

15.      }

这个函数主要用来初始化 cache_cache 这个变量， cache_cache 是一个类型为 kmem_cache_t 的结构体变量，定义如下：

1.        static  kmem_cache_t cache_cache = { 

2.            slabs_full:       LIST_HEAD_INIT(cache_cache.slabs_full), 

3.            slabs_partial:    LIST_HEAD_INIT(cache_cache.slabs_partial), 

4.            slabs_free:       LIST_HEAD_INIT(cache_cache.slabs_free), 

5.            objsize:          sizeof(kmem_cache_t), 

6.            flags:            SLAB_NO_REAP, 

7.            spinlock:         SPIN_LOCK_UNLOCKED, 

8.            colour_off:       L1_CACHE_BYTES, 

9.            name:             "kmem_cache" , 

10.       };

为什么需要一个这样的对象呢？因为本身 kmem_cache_t 结构体也是小内存对象，所以也应该有 slab 分配器来分配的，但这样就出现 “ 鸡蛋和鸡谁先出现 ” 的问题。在系统初始化的时候， slab 分配器还没有初始化，所以并不能使用 slab 分配器来分配一个 kmem_cache_t 对象，这时候只能通过定义一个 kmem_cache_t 类型的静态变量来来管理 slab 分配器了，所以 cache_cache 静态变量就是用来管理 slab 分配器的。

从上面的代码可知， cache_cache 的 objsize 字段被设置为 sizeof(kmem_cache_t) 的大小，所以这个对象主要是用来分配不同类型的 kmem_cache_t 对象的。

kmem_cache_init() 函数调用了 kmem_cache_estimate() 函数来计算一个 slab 能够保存多少个大小为 cache_cache.objsize 的对象，并保存到 cache_cache.num 字段中。一个 slab 中不可能全部都用来分配对象的，举个例子：一个 4096 字节大小的 slab 用来分配大小为 22 字节的对象，可以划分为 186 个，但还剩余 4 字节不能使用的，所以这部分内存用来作为着色区。着色区的作用是为了错开不同的 slab ，让 CPU 更有效的缓存 slab 。当然这属于优化部分，对 slab 分配算法没有多大的影响。就是说就算不对 slab 进行着色操作， slab 分配算法还是可以工作起来的。

kmem_cache_t对象申请

kmem_cache_t 是用来管理和分配对象的，所以要使用 slab 分配器时，必须先申请一个 kmem_cache_t 对象，申请 kmem_cache_t 对象由 kmem_cache_create() 函数进行：

1.        kmem_cache_t *kmem_cache_create ( 

2.             const   char  *name, 

3.            size_t size, 

4.            size_t offset, 

5.             unsigned   long  flags, 

6.             void  (*ctor)( void *, kmem_cache_t *,  unsigned   long ), 

7.             void  (*dtor)( void *, kmem_cache_t *,  unsigned   long ) 

8.        ) { 

9.            ... 

10.           cachep = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL); 

11.            if  (!cachep) 

12.                goto  opps; 

13.           memset(cachep,  0 , sizeof(kmem_cache_t)); 

14.           ... 

15.            do  {

16.                unsigned   int  break_flag =  0 ; 

17.       cal_wastage: 

18.               kmem_cache_estimate(cachep->gfporder, size, flags, 

19.                               &left_over, &cachep->num); 

20.                if  (break_flag) 

21.                    break ;

22.                if  (cachep->gfporder >= MAX_GFP_ORDER) 

23.                    break ; 

24.                if  (!cachep->num)

25.                    goto  next; 

26.                if  (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) { 

27.                    /* Oops, this num of objs will cause problems. */  

28.                   cachep->gfporder--; 

29.                   break_flag++; 

30.                    goto  cal_wastage; 

31.               } 

32.        

33.                if  (cachep->gfporder >= slab_break_gfp_order) 

34.                    break ; 

35.        

36.                if  ((left_over* 8 ) <= (PAGE_SIZE<<cachep->gfporder)) 

37.                    break ;     /* Acceptable internal fragmentation. */  

38.       next: 

39.               cachep->gfporder++; 

40.           }  while  ( 1 ); 

41.        

42.            if  (flags & CFLGS_OFF_SLAB && left_over >= slab_size) { 

43.               flags &= ~CFLGS_OFF_SLAB; 

44.               left_over -= slab_size; 

45.           } 

46.        

47.            /* Offset must be a multiple of the alignment. */  

48.           offset += (align- 1 ); 

49.           offset &= ~(align- 1 ); 

50.            if  (!offset) 

51.               offset = L1_CACHE_BYTES; 

52.           cachep->colour_off = offset; 

53.           cachep->colour = left_over/offset; 

54.        

55.           cachep->flags = flags; 

56.           cachep->gfpflags =  0 ; 

57.            if  (flags & SLAB_CACHE_DMA) 

58.               cachep->gfpflags |= GFP_DMA; 

59.           spin_lock_init(&cachep->spinlock); 

60.           cachep->objsize = size; 

61.           INIT_LIST_HEAD(&cachep->slabs_full); 

62.           INIT_LIST_HEAD(&cachep->slabs_partial); 

63.           INIT_LIST_HEAD(&cachep->slabs_free); 

64.        

65.            if  (flags & CFLGS_OFF_SLAB) 

66.               cachep->slabp_cache = kmem_find_general_cachep(slab_size, 0 ); 

67.           cachep->ctor = ctor; 

68.           cachep->dtor = dtor; 

69.           strcpy(cachep->name, name); 

70.        

71.           down(&cache_chain_sem); 

72.           { 

73.                struct  list_head *p; 

74.        

75.               list_for_each(p, &cache_chain) { 

76.                   kmem_cache_t *pc = list_entry(p, kmem_cache_t, next); 

77.               } 

78.           } 

79.        

80.           list_add(&cachep->next, &cache_chain); 

81.           up(&cache_chain_sem); 

82.       opps: 

83.            return  cachep; 

84.       }

kmem_cache_create() 函数比较长，所以上面代码去掉了一些不那么重要的地方，使代码更清晰的体现其原理。

在 kmem_cache_create() 函数中，首先调用 kmem_cache_alloc() 函数申请一个 kmem_cache_t 对象，我们看到调用 kmem_cache_alloc() 时，传入的就是 cache_cache 变量。申请完 kmem_cache_t 对象后需要对其进行初始化操作，主要是对 kmem_cache_t 对象的所有字段进行初始化： 1) 计算需要多少个页面来作为 slab 的大小。 2) 计算一个 slab 能够分配多少个对象。 3) 计算着色区信息。 4) 初始化 slab_full / slab_partial / slab_free 链表。 5) 把申请的 kmem_cache_t 对象保存到 cache_chain 链表中。

对象分配

申请完 kmem_cache_t 对象后，就使用通过调用 kmem_cache_alloc() 函数来申请指定的对象。 kmem_cache_alloc() 函数代码如下：

1.        static  inline  void  * 

2.        kmem_cache_alloc_one_tail (kmem_cache_t *cachep, slab_t *slabp) 

3.        { 

4.             void  *objp; 

5.         

6.            slabp->inuse++; 

7.            objp = slabp->s_mem + slabp->free*cachep->objsize; 

8.            slabp->free = slab_bufctl(slabp)[slabp->free]; 

9.         

10.            if  (unlikely(slabp->free == BUFCTL_END)) { 

11.               list_del(&slabp->list); 

12.               list_add(&slabp->list, &cachep->slabs_full); 

13.           } 

14.            return  objp; 

15.       }

16.        

17.       static  inline  void  * 

18.       __kmem_cache_alloc(kmem_cache_t *cachep,  int  flags) 

19.       { 

20.            unsigned   long  save_flags; 

21.            void * objp; 

22.            struct  list_head * slabs_partial, * entry; 

23.           slab_t *slabp;     

24.        

25.           kmem_cache_alloc_head(cachep, flags); 

26.       try_again: 

27.           local_irq_save(save_flags); 

28.        

29.           slabs_partial = &(cachep)->slabs_partial;

30.           entry = slabs_partial->next;

31.        

32.            if  (unlikely(entry == slabs_partial)) {

33.                struct  list_head * slabs_free;

34.               slabs_free = &(cachep)->slabs_free;

35.               entry = slabs_free->next;

36.                if  (unlikely(entry == slabs_free))

37.                    goto  alloc_new_slab;

38.               list_del(entry);

39.               list_add(entry, slabs_partial);

40.           }

41.        

42.           slabp = list_entry(entry, slab_t, list); 

43.           objp = kmem_cache_alloc_one_tail(cachep, slabp); 

44.        

45.           local_irq_restore(save_flags); 

46.            return  objp; 

47.        

48.       alloc_new_slab: 

49.           local_irq_restore(save_flags); 

50.            if  (kmem_cache_grow(cachep, flags)) 

51.                goto  try_again; 

52.            return  NULL; 

53.       }

kmem_cache_alloc() 函数被我展开之后如上代码， kmem_cache_alloc() 函数的主要步骤是： 1) 从 kmem_cache_t 对象的 slab_partial 列表中查找是否有 slab 可用，如果有就直接从 slab 中分配一个对象。 2) 如果 slab_partial 列表中没有可用的 slab ，那么就从 slab_free 列表中查找可用的 slab ，如果有可用 slab ，就从 slab 分配一个对象，并且把此 slab 放置到 slab_partial 列表中。 3) 如果 slab_free 列表中没有可用的 slab ，那么就调用 kmem_cache_grow() 函数申请新的 slab 来进行对象的分配。

一个 slab 的结构如下图：

灰色部分是着色区，绿色部分是 slab 管理结构，黄色部分是空闲对象链表的索引，红色部分是对象的实体。我们可以看到 slab 结构的 s_mem 字段指向了对象实体列表的起始地址。

分配对象的时候就是先通过 slab 结构的 free 字段查看是否有空闲的对象可用， free 字段保存了空闲对象链表的首节点索引。

对象释放

对象的释放比较简单，主要通过调用 kmem_cache_free() 函数完成，而 kmem_cache_free() 函数最终会调用 kmem_cache_free_one() 函数，代码如下：

1.        static  inline  void  

2.        kmem_cache_free_one(kmem_cache_t *cachep,  void  *objp) 

3.        { 

4.            slab_t* slabp; 

5.         

6.            { 

7.                 unsigned   int  objnr = (objp-slabp->s_mem)/cachep->objsize;  

8.                slab_bufctl(slabp)[objnr] = slabp->free; 

9.                slabp->free = objnr; 

10.           } 

11.        

12.            /* fixup slab chains */  

13.           { 

14.                int  inuse = slabp->inuse; 

15.                if  (unlikely(!--slabp->inuse)) { 

16.                    /* Was partial or full, now empty. */  

17.                   list_del(&slabp->list); 

18.                   list_add(&slabp->list, &cachep->slabs_free); 

19.               }  else   if  (unlikely(inuse == cachep->num)) { 

20.                    /* Was full. */  

21.                   list_del(&slabp->list); 

22.                   list_add(&slabp->list, &cachep->slabs_partial); 

23.               } 

24.           } 

25.       }

对象释放的时候首先会把对象的索引添加到 slab 的空闲对象链表中，然后根据 slab 的使用情况移动 slab 到合适的列表中。 1) 如果 slab 所有对象都被释放完时，把 slab 放置到 slab_free 列表中。 2) 如果对象所在的 slab 原来在 slab_full 中，那么就把 slab 移动到 slab_partial 中。