Linux内核内存管理与漏洞利用

前言

网上已经有很多关于Linux内核内存管理的分析和介绍了，但是不影响我再写一篇：一方面是作为其他文章的补充，另一方面则是自己学习的记录、总结和沉淀。

伙伴系统

伙伴系统即Buddy System，是一种简单高效的内存分配策略。其主要思想是将大块内存按照一定策略去不断拆分（在到达最小的块之前），直至存在满足指定请求大小的最小块。其中块的大小由其相对根块的位置指定，通常称为order(阶)。一个最简单的拆分方式就是以2为指数进行拆分，例如定义最小块的大小为64K，order上限为4，则最大块的大小为：

64K * 2^4 = 1024K

最大块的order为4，最小块的order为0。对于请求大小为k的块，最小块为N，则其order值为align(k)/N。为什么叫buddy system呢？假设一个大块A所分解成的两个小块B和C，其中B和C就相互为彼此的 天使 buddy。只有彼此的buddy才能够进行合并。

使用Buddy算法的的应用有很多，其中Linux内核就是一个，此外jemalloc也是使用Buddy技术的一个现代内存分配器。

Linux内核中的伙伴系统块大小为一页，通常是4096字节。最大的order一般是10，即MAX_ORDER为11。

 /* Free memory management - zoned buddy allocator.  */
  #ifndef CONFIG_FORCE_MAX_ZONEORDER
  #define MAX_ORDER 11
  #else
  #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  #endif
  #define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

在Linux内核中，分配和释放较大内存都是直接通过伙伴系统，即：

struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
void free_pages(unsigned long addr, unsigned int order);

order为0-10，指定从哪一阶伙伴中分配，order为n则分配2^n页大小的内存。操作系统中可以通过procfs查看伙伴系统的分配情况，如下：

$ cat /proc/buddyinfo
Node 0, zone      DMA      1      1      0      0      2      1      1      0      1      1      3
Node 0, zone    DMA32   3416   4852   3098   3205   3209   3029     33     22     15      7     52
Node 0, zone   Normal  29330 192053 148293  90568  33732   9018   2688    411    942    999   1852
Node 1, zone   Normal    107   1229  18644  76650  46053   8383   4398   5486   1751    497     84

此外，还有/proc/pagetypeinfo也可用于查看内存页的信息。

Slab分配器

上面说到，由于效率原因，伙伴系统中分配内存是以页为单位的，即使所分配的object大小为1byte，也需要分配一页，这样就导致了比较大的内存碎片。因此Linux引入了Slab分配器，加速对object的分配和释放速度，同时也减少碎片空间。

最初接触的时候心里通常有个大大的问号：Slab是什么？理解这个问题至关重要，经过翻阅多种资料和文章，可以大概这么回答：

1.Slab是一种缓存策略

2.Slab是一片缓冲区

3.Slab是一个或者多个连续的page

在内核代码中，我们能看到SLAB、SLOB、SLUB，其实都是兼容SLAB接口的具体分配器

说句题外话，SLOB (Simple List Of Blocks) 可以看做是针对嵌入式设备优化的分配器，通常只需要几MB的内存。其采用了非常简单的first-fit算法来寻找合适的内存block。这种实现虽然去除了几乎所有的额外开销，但也因此会产生额外的内存碎片，因此一般只用于内存极度受限的场景。

数据结构

在本文中，我会尽量少粘贴大段的代码进行分析，但Slub分配器是比较依赖于实现而不是设计的，因此数据结构的介绍是难免的。

page

描述一个页的数据结构就是struct page。为了节约空间，page使用了大量的union结构，针对不同用处的页使用不同的字段。

Slab是一个或者多个连续页组成的内存空间，那么本质上指向一个Slab的数据结构不是别的，就是struct page *，对应Slab中的信息可以通过第一个page的某些字段描述。记住这点对后面的理解很重要。

【文章福利】【Linux内核内存管理专题训练营】火热开营！！

最新Linux内核技术详解

独家Linux内核内存管理干货分享

入营地址：inux内核内存管理专题训练营

两天持续技术输出： -------------------- 第一天： 1.物理内存映射及空间划分 2.ARM32/64页表的映射过程 3.分配物理页面及Slab分配器 4.实战：VMA查找/插入/合并 -------------------- 第二天： 5.实战：mallocap系统调用实现 6.缺页中断处理/反向映射 7.回收页面/匿名页面生命周期 8.KSM实现/Dirty COW内存漏洞

kmem_cache

kmem_cache是Slab的主要管理结构，申请和释放对象都需要经过该结构操作，部分重要字段如下：

 /*
   * Slab cache management.
   */
  struct kmem_cache {
      struct kmem_cache_cpu __percpu *cpu_slab;
      /* Used for retriving partial slabs etc */
      unsigned long flags;
      unsigned long min_partial;
      int size;       /* The size of an object including meta data */
      int object_size;    /* The size of an object without meta data */
      int offset;     /* Free pointer offset. */
  #ifdef CONFIG_SLUB_CPU_PARTIAL
      int cpu_partial;    /* Number of per cpu partial objects to keep around */
  #endif
      ...
      struct kmem_cache_node *node[MAX_NUMNODES];
}

重点关注cpu_slab和node。

cpu_slab包含当前CPU的Slab。这是个__percpu的对象，什么意思呢？我的理解是内核为了加速当前CPU的访问，会对每个CPU保存一个变量，这样在当前CPU访问该变量时候就可以免去加锁的开销。在调试中发现该变量的值是个类似0x18940这样比较小的数，这个地址是没有映射的，访问percpu变量需要通过raw_cpu_ptr宏去获取实际的地址。

node数组中包括其他CPU的Slab。为什么叫做node？其实这是NUMA系统中的node概念。NUMA是为了多核优化而产生的架构，可以令某个CPU访问某段内存的速度更快。node的定义是“一段内存，其中每个字节到CPU的距离相等”，更加通俗的解释是：“在同一物理总线上的内存+CPUs+IO+……”，

kmem_cache_cpu

cpu_slab是kmem_cache_cpu结构，如下：

 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
  };

freelist指向第一个空闲的对象(假设为x)，page指向x所在slab(的第一页)。这里的page有以下特点：

• objects = slab的对象数
• inuse = objects
• frozen = 1
• freelist = NULL

partial主要包含本地部分分配的slab。partial指向的page有以下特点：

• next指向下一个slab(page)
• freelist指向slab中第一个空闲object
• inuse = slab中已使用的object个数
• frozen = 1

其中第一个page的pbojects记录了partial objects数。

kmem_cache_node

struct kmem_cache_node {
    spinlock_t list_lock;
    ...
#ifdef CONFIG_SLUB
    unsigned long nr_partial;
    struct list_head partial;
    ..
#endif
};

这个数据结构根据配置的SL[OAU]B分配器而异，对于SLUB而言，使用的字段就只有两个，nr_partial和partial。其中partial是Linux内核中可插拔式通用双链表结构，使用内核中双链表的接口进行操作。nr_partial表示partial双链表中的元素个数，即slab的个数。

partial->next指向的page结构，用于该结构的page有如下特点：

• frozon = 0
• freelist指向slab中第一个空闲object
• inuse表示对应slab使用中的object个数
• 通过lru字段索引链表中的下一个/前一个page

前三点没什么好说的，大家都差不多。需要关注的是第四点，这里不像cpu partial那样通过next指针连接页表，而是通过lru字段：

struct page {
...
      /*
       * Third double word block
       *
       * WARNING: bit 0 of the first word encode PageTail(). That means
       * the rest users of the storage space MUST NOT use the bit to
       * avoid collision and false-positive PageTail().
       */
      union {
          struct list_head lru;   /* Pageout list, eg. active_list
                       * protected by zone_lru_lock !
                       * Can be used as a generic list
                       * by the page owner.
                       */
     ...

分配和释放

终于讲到了重点。关于slub的分配和释放有很多文章介绍过，而且风格不同，有的是对着代码逐行分析，有的是画图介绍，这里我仅按照我自己的理解去说，如有谬误欢迎指出。

对象的分配和释放涉及到几个指针，分别是：

• p1: 对象的虚拟地址(void *)
• p2: 对象地址所对应的page(struct page*)
• p3: 对象所属的slab(struct page*)
• p4: 对象所属的cache控制体(struct kmem_cache*)

一个虚地址所对应的页首地址是是通过PAGE_MASK，因为页是对齐的，但需要注意页首地址并不是page指针所指向的地方。p1->p2的转换通过virt_to_page实现。

p2->p4可以通过page->slab_cache得到，这也是p1->p4函数virt_to_cache的操作。

分配

对象的分配，不考虑特殊情况的话(比如超过N页的对象直接通过伙伴系统分配)，一般流程如下：

1.kmem_cache_cpu->freelist不为空，直接出链返回；

2.kmem_cache_cpu->page->freelist不为空，则出链，更新cpu_slab->freelist，然后返回；

3.kmem_cache_cpu->partial不为空，取出第一个slab，更新cpu_slab的freelist和page，取出对象然后返回；

4.kmem_cache_node->partial不为空，取出第一个，类似3更新cpu_slab的freelist和page并返回；

5.上面都是空的，则通过伙伴系统分配新的slab，挂到kmem_cache_cpu中，然后goto 1；