Linux内存管理 - slab分配器详解

客官°小女子只卖身不卖艺 2023-01-10 10:13 95阅读 0赞

## linux相关视频解析： ##

[90分钟了解Linux内存架构，numa的优势，slab的实现，vmalloc的原理][90_Linux_numa_slab_vmalloc]  
[5个方面分析linux内核架构，让你对内核不再陌生][5_linux]  
[手把手带你实现一个Linux内核文件系统][Linux]

Linux有个叫伙伴系统的分配算法，这个算法主要解决分配连续个内存页的问题。伙伴分配算法主要以内存页（4KB）作为分配单位，就是说伙伴分配算法每次可以分配 2order 个内存页（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由2gfporder个内存页组成
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：用于连接空闲的对象

用图来表示它们之间的关系，如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70_pic_center]

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

在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列表中。

**【文章福利】需要C/C++ Linux服务器架构师学习资料加群812855908（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70]

## 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的结构如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70_pic_center 1]

灰色部分是着色区，绿色部分是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中。

[90_Linux_numa_slab_vmalloc]: https://www.bilibili.com/video/BV1mK4y1H7JL/
[5_linux]: https://www.bilibili.com/video/BV1z5411G7Y6/
[Linux]: https://www.bilibili.com/video/BV1Wr4y1c712/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/ca7b18a80737460e824e2d34b7b83ce8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210123152343600.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210123151956161.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTg5NzY5,size_16,color_FFFFFF,t_70#pic_center