内核分配器的功能

在操作系统管理的虚拟内存中，用于内存管理的最小单位是页，大多数传统的架构是4KB。由于进程每次申请分配4KB是不现实的，比如分配几个字节或几十个字节，这时需要中间机制来管理页面的微型内存。
为此，内核实现了一个分配器来管理页中碎片内存的分配和回收。可以把分配器理解为一个零售供应商：它收购大量的库存（4KB大小的页），然后在模块需要时分成小块出售。这种分配的基本版就是SLAB。

SLAB

当内核子系统为对象请求、释放数据时，主要的开销在于初始化、销毁过程，而不是为对象分配的内存。如果有一组经常使用的内核对象，那么可以将它们保存在一个可快速使用的地方，使整个过程更有效率。
这就是SLAB的原理：分配器跟踪这些块，称为缓存，当收到为某种类型的数据对象分配内存的请求时，它可以立即使用已经分配过的来满足请求。这种情况下，SLAB是内存中包含预先分配的内存块的一个或多个连续页面。
SLAB可能存在以下状态之一：

• empty：SLAB中所有对象都是空闲的
• partial：SLAB中包含被分配的对象和空闲对象
• full：SLAB中所有对象都被分配

分配器的目的是尽可能快的处理请求，因此跟踪过程至关重要，这个过程通过缓存完成，而每种对象类型都有一个缓存。

SLUB

SLUB是SLAB的变体，旨在实现更好的调试、更少的碎片和更好的性能。它沿用SLAB的基本功能，优化了SLAB中多处理器的设计缺陷。自从2008年Linux 2.6.23以来SLUB被设置为默认分配器。

接下来会观察SLUB的实现细节，并通过常用的场景给出示例。

SLAB中的对象通过链表互相连接，这样分配器总是可以找到下一个空闲对象，而不需要关心已经使用的数据：

SLUB和SLAB不同：指向下一个空闲对象的指针直接存储在对象本身内部的结构体中，并不需要额外的内存空间进行存储，且保证SLAB功能100%的利用效率。在某些特殊情况，指针存储在对象结构体中的一个偏移量里面，这根据不同平台的CPU而定。

上图中objsize表示对象自身的大小，offset是next指针之前的空间大小，size是总大小。

所有的这些信息，以及更多的信息，都存储在一个kmem_cache结构体中，它的结构体定义如下：

/*
 * Slab cache management.
 */
struct kmem_cache {
	struct kmem_cache_cpu __percpu *cpu_slab;
	/* Used for retrieving partial slabs, etc. */
	slab_flags_t flags;
	unsigned long min_partial;
	unsigned int size;	/* The size of an object including metadata */
	unsigned int object_size;/* The size of an object without metadata */
	unsigned int offset;	/* Free pointer offset */
	......
	struct kmem_cache_node *node[MAX_NUMNODES];
}

每个对象有且只有一个kmem_cache，并且该对象的所有slab都由相同的kmem_cache管理，这些结构体通过双向链表互相链接，可以通过导出的slab_caches变量从内核中的任何位置访问。slab_caches定义如下：

extern struct list_head slab_caches;  // list_head用于管理双向链表

在kmem_cache结构体中，存储了两种指针以跟踪对象：一个kmem_cache_node数组，是结构体最后一个成员struct kmem_cache_node *node[MAX_NUMNODES] ；另一个是指向kmem_cache_cpu的指针，结构体第一个成员struct kmem_cache_cpu __percpu *cpu_slab 。

• kmem_cache_node跟踪不活动的partial和full的对象，在空闲的情况被访问，或者当活动的slab被填满时用另一个partial替换它：

  /*
   * The slab lists for all objects.
   */
  struct kmem_cache_node {
  	spinlock_t list_lock;
  
  #ifdef CONFIG_SLAB
  	struct list_head slabs_partial;	/* partial list first, better asm code */
  	struct list_head slabs_full;
  	struct list_head slabs_free;
  	unsigned long total_slabs;	/* length of all slab lists */
  	unsigned long free_slabs;	/* length of free slab list only */
  	unsigned long free_objects;
  	unsigned int free_limit;
  	unsigned int colour_next;	/* Per-node cache coloring */
  	struct array_cache *shared;	/* shared per node */
  	struct alien_cache **alien;	/* on other nodes */
  	unsigned long next_reap;	/* updated without locking */
  	int free_touched;		/* updated without locking */
  #endif
  
  #ifdef CONFIG_SLUB
  	unsigned long nr_partial;
  	struct list_head partial;
  #ifdef CONFIG_SLUB_DEBUG
  	atomic_long_t nr_slabs;
  	atomic_long_t total_objects;
  	struct list_head full;
  #endif
  #endif
  
  };
  

• kmem_cache_cpu管理活动的slab，它只有一个，并且与当前的CPU相关（不同的处理器有不同的缓存）。下一次申请始终由freelist字段指向的slab返回：

  struct kmem_cache_cpu {
  	void **freelist;	/* Pointer to next available object */
  	unsigned long tid;	/* Globally unique transaction id */
  	struct page *page;	/* The slab from which we are allocating */
  #ifdef CONFIG_SLUB_CPU_PARTIAL
  	struct page *partial;	/* Partially allocated frozen slabs */
  #endif
  #ifdef CONFIG_SLUB_STATS
  	unsigned stat[NR_SLUB_STAT_ITEMS];
  #endif
  };
  

以下是kmem_cache结构体成员的关系：

例子

• 普通分配

  分配器从kmem_cache找到kmem_cache_cpu访问freelist找到第一个空闲对象，返回该对象（蓝色部分）。相应的更新指针将其从链表中删除，并将freelist指向下一个空闲对象：

• 分配即将满的对象

  返回最后一个对象后，已填满的页面将移动到full list中，将另一个partial list置为活动的slab：

• 申请即将满的partial list里面的对象，并且没有其他partial list时

  返回最后一个活动的对象之后，已填满的页会放入full list，然后系统分配一个全新的slab成为活动slab：

• 普通释放

  当释放一个属于partial list（或活动）的对象时，SLUB只是将其标记为空闲并更新指针：

• 释放即将为empty list的对象

  当释放属于partial list的最后一个对象时，slab被释放，交给内存管理单元：

• 在full list里面释放

  当释放full list里面的对象时，释放后它不再是full list，将其放入partial list：