Linux Kernel | Linux 内存管理-物理内存

1. 物理内存管理

1.1. 硬件架构

传统的 SMP（Symmetric multiprocessing）系统中，所有处理器都共享系统总线。因此当处理器的数目增大时，系统总线的竞争冲突加大，系统总线成为瓶颈。

为了提高性能和可扩展性，后来有了一种更高级的模式，NUMA （Non-uniform memory access，非统一内存访问）。在 NUMA 架构中，全系统的内存在物理上变成分布的了，而不是一整块，每一组 CPU （虽然下图中画的是一个 CPU）都有自己对应的内存，称为本地内存（这些内存的集合就是全系统的物理内存）。CPU 访问本地内存不用过总线，因而速度要快很多。但是当本地内存不足的情况下，每个 CPU 都可以去另外的 NUMA 节点申请内存，这个时候访问延时就会比较长了。 **而一个 NUMA 节点则由一组 CPU 和 本地内存组成。**多个 NUMA 通过高速互联网络连接，最终构成了整个 NUMA 系统。

在实际情况下 SMP 和 NUMA 是混合使用的，在 NUMA 节点内部使用 SMP 体系结构。

1.2. 内存模型

1.2.1. 平坦内存模型（Flat Memory Model）

从 0 开始对物理页编号，这样每个物理页都会有个页号。由于物理地址是连续的，页也是连续的，每个页大小也是一样的。因而对于任何一个地址，只要直接除一下每页的大小，很容易直接算出在哪一页。每个页有一个结构 struct page 表示，这个结构也是放在一个数组里面，这样根据页号，很容易通过下标找到相应的 struct page 结构。

这种比较适合于 SMP 模式中的。

1.2.2. 非连续内存模型

NUMA 结构中，系统的所有内存被分成了多个节点，每个节点会再被分成一个一个的页面。由于页还是需要全局唯一定位，所以它还是会有全局唯一的页号。但是，由于物理内存不是连起来了的，那么页号就不再连续了。于是内存模型变成了非连续内存模型。

需要注意的是：NUMA 往往是非连续内存模型。而非连续内存模型不一定就是 NUMA，有时候一大片内存的情况下，也会有物理内存地址不连续的情况。

1.2.3. 稀疏内存模型

后来内存支持了热插拔，这个时候不连续已经成为常态，接着就有稀疏内存模型。

1.3. 物理内存的组织

下面主要讲解当前的主流场景，也就是 NUMA 方式。

在 NUMA 中，内存被分成了三层（节点 -> 区域 -> 页）：

每个节点用 struct pglist_data 表示，放在一个数组里面。

struct pglist_data *node_data[MAX_NUMNODES] __read_mostly;

每个节点分为多个区域，每个区域用 struct zone 表示，放在 struct pglist_data 中的一个数组里面。

每个区域分为多个页，每个物理页用 struct page 表示。为了方便分配，空闲页放在每个区域的 struct free_area 里面，使用伙伴系统进行管理和分配。

1.3.1. 节点

首先是 NUMA 节点的表示，Linux 内核中使用typedef struct pglist_data pg_data_t来表示 NUMA 节点。

typedef struct pglist_data {
  struct zone node_zones[MAX_NR_ZONES];
  struct zonelist node_zonelists[MAX_ZONELISTS];
  int nr_zones;
  struct page *node_mem_map;
  unsigned long node_start_pfn;
  unsigned long node_present_pages; /* total number of physical pages */
  unsigned long node_spanned_pages; /* total size of physical page range, including holes */
  int node_id;
......
} pg_data_t;

这个结构体中主要有以下这些成员变量：

• node_id 是每一个节点的 ID；

• node_mem_map 是这个节点的 struct page 数组，用来描述这个节点里面的所有的页；

• node_struct_pfn 是这个节点的起始页号；

• node_spanned_pages 是这个节点中包含了不连续的物理内存地址的页面数；

• node_present_pages 是真正可用的物理页面的数目；

  怎么理解后面的两个成员变量呢？一个 NUMA 节点中，有一块连续的 64MB 物理内存，接下去它隔着一个 4M 的空洞，然后是另外的一块连续的 64MB 物理内存。那么换算成 4KB 一页的话，node_spanned_pages 就是 33K 个页面（64 MB 是 16K 个页面，包含了中间的那个空洞），node_present_pages 是 32K 个页面（不包含中间的那个空洞）。

• 每一个节点又分为一个个区域 Zone，见 struct pglist_data 中的 node_zones 数组，这个数组的大小是 MAX_NR_ZONES。

  每个区域的定义如下所示，区域的划分都是针对物理内存的：

  enum zone_type {
  #ifdef CONFIG_ZONE_DMA
    ZONE_DMA,
  #endif
  #ifdef CONFIG_ZONE_DMA32
    ZONE_DMA32,
  #endif
    ZONE_NORMAL,
  #ifdef CONFIG_HIGHMEM
    ZONE_HIGHMEM,
  #endif
    ZONE_MOVABLE,
    __MAX_NR_ZONES
  };
  

  • ZONE_DMA 是指可用于作 DMA（Direct Memory Access，直接内存存取）的内存。

    DMA 机制：很早之前要把外设的数据读入内存或把内存的数据传送到外设，都需要通过 CPU 控制完成，但是这会占用 CPU，影响 CPU 处理其他事情。而 DMA 机制中，CPU 只需向 DMA 控制器下达指令，让 DMA 控制器来处理数据的传送，数据传送完毕再把信息反馈给 CPU，这样就可以解放 CPU。

  • 对于 64 位系统，有两个 DMA 区域。除了上面说的 ZONE_DMA，还有 ZONE_DMA32。

  • ZONE_NORMAL 是直接映射区，从物理内存到虚拟内存的内核区域，通过加上一个常量直接映射。

  • ZONE_HIGHMEM 是高端内存区，对于 32 位系统来说超过 896M 的地方，对于 64 位没必要有的一段区域。

  • ZONE_MOVABLE 是可移动区域，通过将物理内存划分为可移动分配区域和不可移动分配区域来避免内存碎片。

• nr_zones 表示当前节点的区域的数量；

• node_zonelists 是备用节点和它的内存区域的情况。NUMA 节点中 CPU 访问本地内存是速度最快的，但是如果本节点内存不够的话，还是需要从其他节点进行分配。毕竟，就算在备用节点里面选择，慢了点也比没有强。

1.3.2. 区域-Zone

Linux 区域使用 struct zone 表示，

struct zone {
......
  struct pglist_data  *zone_pgdat;
  struct per_cpu_pageset __percpu *pageset;

  unsigned long    zone_start_pfn;

  /*
   * spanned_pages is the total pages spanned by the zone, including
   * holes, which is calculated as:
   *   spanned_pages = zone_end_pfn - zone_start_pfn;
   *
   * present_pages is physical pages existing within the zone, which
   * is calculated as:
   *  present_pages = spanned_pages - absent_pages(pages in holes);
   *
   * managed_pages is present pages managed by the buddy system, which
   * is calculated as (reserved_pages includes pages allocated by the
   * bootmem allocator):
   *  managed_pages = present_pages - reserved_pages;
   *
   */
  unsigned long    managed_pages;
  unsigned long    spanned_pages;
  unsigned long    present_pages;

  const char    *name;
......
  /* free areas of different sizes */
  struct free_area  free_area[MAX_ORDER];

  /* zone flags, see below */
  unsigned long    flags;

  /* Primarily protects free_area */
  spinlock_t    lock;
......
} ____cacheline_internodealigned_in_

• zone_start_pfn 表示属于这个 zone 的第一个页。

• spanned_pages = zone_end_pfn - zone_start_pfn，也即 spanned_pages 指的是不管中间有没有物理内存空洞，反正就是最后的页号减去起始的页号。

• present_pages = spanned_pages - absent_pages(pages in holes)，也即 present_pages 是这个 zone 在物理内存中真实存在的所有 page 数目。

• managed_pages = present_pages - reserved_pages，也即 managed_pages 是这个 zone 被伙伴系统管理的所有的 page 数目。

• per_cpu_pageset 用于区分冷热页。

  如果一个页被加载到 CPU 高速缓存里面，这就是一个热页（Hot Page），CPU 读起来速度会快很多，如果没有就是冷页（Cold Page）。由于每个 CPU 都有自己的高速缓存，因而 per_cpu_pageset 也是每个 CPU 一个。

1.3.3. 页

页是组成物理内存的基本单位，采用 struct page 表示。

struct page {
  unsigned long flags;
  union {
    struct address_space *mapping;  
    void *s_mem;      /* slab first object */
    atomic_t compound_mapcount;  /* first tail page */
  };
  union {
    pgoff_t index;    /* Our offset within mapping. */
    void *freelist;    /* sl[aou]b first free object */
  };
  union {
    unsigned counters;
    struct {
      union {
        atomic_t _mapcount;
        unsigned int active;    /* SLAB */
        struct {      /* SLUB */
          unsigned inuse:16;
          unsigned objects:15;
          unsigned frozen:1;
        };
        int units;      /* SLOB */
      };
      atomic_t _refcount;
    };
  };
  union {
    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 */
  };
  ......
}

struct page 里面有很多的 union，union 结构是在 C 语言中根据情况将不同类型数据保存在同一块内存的一种方式（也就是说同样大小的内存，它存的可以是不同类型的数据结构）。而之所以使用 union，是因为一个物理页面使用模式有很多种。

• 第一种模式，一整页一块用。这一整页要不直接和虚拟地址空间建立映射关系，那么此时是被称为匿名页（anonymous page）；要不就是关联一个文件，然后再跟虚拟地址空间建立映射关系，这样的文件被称为内存映射文件（Memory-mapped File）。

  • struct address_space *mapping 就是用于内存映射，如果是匿名页，最低位为 1；如果是映射文件，最低位为 0；
  • pgoff_t index 是在映射区的偏移量；
  • atomic_t _mapcount，每个进程都有自己的页表，这里指有多少个页表项指向了这个页；
  • struct list_head lru 表示这一页所在的链表，例如这个页面被换出，就在换出页的链表中；
  • compound 相关的变量用于复合页（Compound Page），就是将物理上连续的两个或多个页看成一个独立的大页。

• 第二种模式，用于分配小块内存。比如，有时候，我们不需要分配一个页这么多的内存，比如分配一个 task_struct 结构，只需要分配小块的内存，去存储这个进程描述结构的对象，也就是某一页是用于分割成一小块一小块的内存进行分配的使用模式。

  这种情况下则会使用 union 中的以下变量：

  • s_mem 是已经分配了正在使用的 slab 的第一个对象；
  • freelist 是池子中的空闲对象；
  • rcu_head 是需要释放的列表。

1.4. 物理内存分配

1.4.1. 伙伴系统（Buddy System）

对于要分配比较大的内存，例如到分配页级别的，可以使用伙伴系统（Buddy System）。

1.4.1.1. 基本思想

将物理内存划分为连续的块，以块作为基本单位进行分配。每个块都由一个或多个连续的物理页组成，每个块的物理页的数量必须是 2 的 n 次幂（0<=n<预设的最大值），预设的最大值一般根据实际由开发者指定。

当一个请求需要分配 m 个物理页的时候，伙伴系统会寻找一个合适的块，该块包含 2^{n 个物理页，且满足 2}(n-1)<m<= 2^n。当不存在这么大的块的时候，大的块可以分裂成两半，分裂出来的两个块互为伙伴。分裂的出来块还可以继续分裂，直到得到一个大小合适的块去服务相应的分配请求。

在一个块被释放后，分配器会找到其伙伴块，若伙伴块也处于空闲的状态，则将这两个伙伴块合并，形成一个大一号的伙空闲块。以此类推，可以继续向上合并。

1.4.1.2. 具体实现

伙伴系统把所有的空闲页分组成了 11 个页块链表，不同的页块链表包含不同数量但是连续的页，有 1、2、4、8、16、32、64、128、256、512 和 1024 个连续页的页块（最大可申请 1024 个连续页，即 4MB 大小的连续内存）。对于第 i 个页块链表来说，页块中页的数目为 2^{i。需要注意的是：每个页块的第一个页的物理地址是该页块大小的整数倍，比如大小为 16 个页框的块,其起始地址是 16*2}12 的倍数.。

在 struct zone 里面有存储这 11 个页块链表的数组（也就是说每个 zone 就会有这样一个数组）：

struct free_area  free_area[MAX_ORDER];

#define MAX_ORDER 11

当向内核请求分配 (2^(i-1)，2i]数目的页块时，按照 2^i 页块请求处理，从链表中找出一个空闲的页块进行分配。如果对应的页块链表中没有空闲页块，那我们就在更大的页块链表中去找。当分配的页块中有多余的页时，伙伴系统会根据多余的页块大小插入到对应的空闲页块链表中。

例如，要请求一个 128 个页的页块时，先检查 128 个页的页块链表是否有空闲块。如果没有，则查 256 个页的页块链表；如果有空闲块的话，则将 256 个页的页块分成两份，一份使用，一份插入 128 个页的页块链表中。如果还是没有，就查 512 个页的页块链表；如果有的话，就分裂为 128、128、256 三个页块，一个 128 的使用，剩余两个插入对应页块链表。

上述分配的过程，可以在分配页的函数 alloc_page() 中看到，alloc_pages 会调用 alloc_pages_current，而它有两个参数：

• 第一个 gfp，它的介绍可见注释，表示希望在哪个区域中分配这个内存
  • GFP_USER 用于分配一个页映射到用户进程的虚拟地址空间，并且希望直接被内核或者硬件访问，主要用于一个用户进程希望通过内存映射的方式，访问某些硬件的缓存，例如显卡缓存；
  • GFP_KERNEL 用于内核中分配页，主要分配 ZONE_NORMAL 区域，也即直接映射区；
  • GFP_HIGHMEM，顾名思义就是主要分配高端区域的内存。
• 另一个参数是 order，表示它需要 2^order 个页。

static inline struct page *
alloc_pages(gfp_t gfp_mask, unsigned int order)
{
  return alloc_pages_current(gfp_mask, order);
}

/**
 *   alloc_pages_current - Allocate pages.
 *
 *  @gfp:
 *    %GFP_USER   user allocation,
 *        %GFP_KERNEL kernel allocation,
 *        %GFP_HIGHMEM highmem allocation,
 *        %GFP_FS     don't call back into a file system.
 *        %GFP_ATOMIC don't sleep.
 *  @order: Power of two of allocation size in pages. 0 is a single page.
 *
 *  Allocate a page from the kernel page pool.  When not in
 *  interrupt context and apply the current process NUMA policy.
 *  Returns NULL when no page can be allocated.
 */
struct page *alloc_pages_current(gfp_t gfp, unsigned order)
{
  struct mempolicy *pol = &default_policy;
  struct page *page;
......
  page = __alloc_pages_nodemask(gfp, order,
        policy_node(gfp, pol, numa_node_id()),
        policy_nodemask(gfp, pol));
......
  return page;
}

接下来 alloc_pages_current 会调用 __alloc_pages_nodemask() 进行分配。这个是伙伴系统的核心方法，而它会调用 get_page_from_freelist()，这个函数的逻辑很容器理解：就是通过一个循环，先看当前节点的相应 zone 有没有符合要求的空闲页，如果在当前节点的 zone 中找不到空闲页的话，那就去看看备用节点中的 zone。

static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
            const struct alloc_context *ac)
{
......
  for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, ac->nodemask) {
    struct page *page;
......
    page = rmqueue(ac->preferred_zoneref->zone, zone, order,
        gfp_mask, alloc_flags, ac->migratetype);
......
}

由于节点中的每一个 zone 都维护着这样的空闲链表，所以这里直接调用 rmqueue 就可以找到合适的链表，把所需要的空闲页面块取下来，同时更新空闲链表。

rmqueue 的调用链为：rmqueue->__rmqueue->__rmqueue_smallest。在 __rmqueue_smallest 函数中可以看到伙伴系统的逻辑：从当前的 order，也即指数开始，在伙伴系统的 free_area 找 2^order 大小的页块。如果链表的第一个不为空，就找到了；如果为空，就到更大的 order 的页块链表里面去找。找到以后，除了将页块从链表中取下来，我们还要把多余部分放到其他页块链表里面。

其中 expand() 函数就是用来把多余部分放到其他页块链表里面的：area-- 就是伙伴系统那个表里面的前一项，前一项里面的页块大小是当前项的页块大小除以 2，size 右移一位也就是除以 2，list_add 就是加到链表上，nr_free++ 就是计数加 1。

static inline struct page *__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype)
{
    unsigned int current_order;
    struct free_area *area;
    struct page *page;


    /* Find a page of the appropriate size in the preferred list */
    for (current_order = order; current_order < MAX_ORDER; ++current_order) {
      area = &(zone->free_area[current_order]);
      page = list_first_entry_or_null(&area->free_list[migratetype],
                                      struct page, lru);
      if (!page)
        continue;
      list_del(&page->lru);
      rmv_page_order(page);
      area->nr_free--;
      expand(zone, page, order, current_order, area, migratetype);
      set_pcppage_migratetype(page, migratetype);
      return page;
    }


    return NULL;
}


static inline void expand(struct zone *zone, struct page *page,
  int low, int high, struct free_area *area,
  int migratetype)
{
  unsigned long size = 1 << high;


  while (high > low) {
    area--;
    high--;
    size >>= 1;
......
    list_add(&page[size].lru, &area->free_list[migratetype]);
    area->nr_free++;
    set_page_order(&page[size], high);
  }
}

PS：伙伴伙伴不就是要结伴嘛，所以简单来说，伙伴系统的思想就是对半分割空间，也可以将两个对半合成一个。

1.4.1.3. 优缺点

更多的是优点：

1. 由于分裂和合并都是级联的，就是都是连续的物理页，所以可以很好地缓解外部碎片问题。
2. 确定一个伙伴块十分简单，互为伙伴的两个块的物理地址仅仅有一位不同，且该位由块的大小决定。比如块 A（0-8KB）和块B（8-16KB）互为伙伴块，块大小为 8KB，它们仅在 13 位不同。因此，伙伴系统能高效、有效地管理物理内存页。

1.4.2. SLAB 分配器

伙伴系统最小的分配单位是 4KB，但是大多数情况下，内核需要分配的内存大小通常是几十字节的或者几百字节的，比如像 task_struct 这种小内存块的需要。如果使用伙伴系统会出现严重的内存碎片，导致内存资源利用率降低。

1.4.2.1. 基本思想

基于上述要求，20 世纪 90 年代，Solaris 2.4 内核中设计并实现了 SLAB 分配器。它的基本原理是从内存管理模块申请一整块页，然后划分成多个小块的存储池，用复杂的队列来维护这些小块的状态（状态包括：被分配了 / 被放回池子 / 应该被回收）。

但是，21 世纪初，内核开发人员发现 SLAB 存在一些问题，比如维护太多的队列、实现日趋复杂、存储开销增大。于是在 SLAB 分配器的基础上设计了 SLUB 分配器。SLUB 分配器极大简化了 SLAB 分配器的设计和数据结构，在降低复杂度的同时依然能够提供与原来相当甚至更好的性能，同时也继承了 SLAB 分配器的接口。

SLAB 分配器家族中，还有一种最简单的分配器称为 SLOB 分配器，主要是为了满足内存稀缺场景的需求，具有最小的存储开销（主要用在小型的嵌入式系统上），但在内存碎片处理上比不上 SLUB、SLAB 分配器。

SLAB、SLUB、SLOB 往往被统称为 SLAB 分配器。

Linux 2.6.23 之后，SLUB 分配器成为 Linux 内核默认使用的分配器。

SLUB 分配器为了满足操作系统分配小对象的要求，其依赖于伙伴系统对物理页的分配。就是把伙伴系统分配的大块内存进一步细化成小块内存进行管理。SLUB 只分配固定大小的内存块（这是因为内核分配的对象大小相对比较固定，也为了避免外部碎片），块的大小通常是 2^n 个字节（一般 3<=n<12）。

对于每种块大小，SLUB 分配器都会使用独立的内存资源池进行分配，如图所示就是一种块大小对应的资源池。

SLUB 分配器会向伙伴系统申请一定大小的物理内存块，并将物理内存块作为一个 slab。slab 会被划分成等长的小块内存，内部的小块内存会被组织成空闲链表的形式。一个内存资源池还有 current 和 partial 两个指针，current 仅指向一个 slab，所有的分配请求都将从这个指针指向的 slab 中获取空闲内存块。partial 指针指向由所有拥有空闲内存块的 slab 组成的链表。

当 SLUB 分配器接收到一个分配请求之后，SLUB 会先定位到能够满足请求大小且最接近的内存资源池（每个内存块大小都有一个内存资源池）。然后从 current 指向的 slab 中拿出一个空闲块返回即可。如果 current 指向的 slab 在取出一个空闲块之后，不再拥有空闲块了，则从 partial 指针指向的链表中取出一个 slab 交给 current 指针。如果 partial 指针指向的链表为空，那么 SLUB 分配器就会向伙伴系统申请分配新的物理内存块作为新的 slab。

当 SLUB 分配器收到一个释放请求之后，它将释放的块放入相应的 slab 空闲链表中。如果该 slab 原本已经没有空闲块了，也就是全部分配完了，那么会将这个 slab 添加到 partial 指向的链表中。如果该 slab 变成所有内存块都是空闲的，那么这个 slab 就可以被释放，还给伙伴系统。

1.4.2.2. 具体实现

还有一种小块内存的分配器称为 slob，非常简单，主要使用在小型的嵌入式系统。

1.4.2.2.1. 整体过程

首先在系统初始化的时候，kmem_cache_create 函数会创建分配了 task_struct 对象的缓存。这个缓存的名字叫做 task_struct_cachep。缓存中的每一块的大小正好等于 task_struct 的大小，也就是 arch_task_struct_size。

static struct kmem_cache *task_struct_cachep;

task_struct_cachep = kmem_cache_create("task_struct",
      arch_task_struct_size, align,
      SLAB_PANIC|SLAB_NOTRACK|SLAB_ACCOUNT, NULL);

那么，在创建进程的时候，会调用 dup_task_struct，它会试图复制一个 task_struct 对象，这个时候先调用 alloc_task_struct_node，分配一个 task_struct 对象。而 alloc_task_struct_node 中会调用 kmem_cache_alloc_node 函数，这个函数会先在 task_struct 的缓存区域 task_struct_cachep 中尝试分配一个 task_struct。

当一个进程结束，task_struct 也不用直接被销毁，而是放回到缓存中，这就是 kmem_cache_free 的作用。

static inline struct task_struct *alloc_task_struct_node(int node)
{
  return kmem_cache_alloc_node(task_struct_cachep, GFP_KERNEL, node);
}

static inline void free_task_struct(struct task_struct *tsk)
{
  kmem_cache_free(task_struct_cachep, tsk);
}

另外，这些内存小块的分配和释放都是基于虚拟地址的。其实，当物理内存分配完毕一整页的时候，会通过page_address分配一个虚拟地址。

1.4.2.2.2. 缓存结构

下面来看一下 struct 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;
  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_order_objects oo;
  /* Allocation and freeing of slabs */
  struct kmem_cache_order_objects max;
  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 *);
......
  const char *name;  /* Name (only for display!) */
  struct list_head list;  /* List of slab caches */
......
  struct kmem_cache_node *node[MAX_NUMNODES];
};

• 首先是 struct list_head list，对于内核来说，需要创建和管理的缓存绝对不止 task_struct，比如 mm_struct、fs_struct 这些都需要，而这个成员变量的作用就是将多个 struct kmem_cache 结构体串起来的，都放到一个链表里面。LIST_HEAD(slab_caches) 指向的就是这个链表。

• 之后是三个 kmem_cache_order_objects 类型的变量。其中 order 就是指 2 的 order 次方个页面的大内存块，而 object 就是指能够存放的缓存对象的数量。

• 接下去是 size、object_size、offset 三个变量。

  对于缓存来讲，其实就是分配了连续几页的大内存块，然后根据缓存对象的大小，切成小内存块，示意图如下所示。每一项的结构都是缓存对象后面跟一个下一个空闲对象的指针，这样非常方便将所有的空闲对象链成一个链。其实，这就相当于咱们数据结构里面学的，用数组实现一个可随机插入和删除的链表。

  

  所以：

  • size 是包含了这个指针之后的大小；
  • object_size 是纯对象的大小；
  • offset 就是把下一个空闲对象的指针存放在这一项里的偏移量。

• 之后是 kmem_cache_cpu 和 kmem_cache_node，它们都是每个 NUMA 节点上有一个，它们的主要作用是记录缓存对象哪些被分配了、哪些在空着，什么情况下整个大内存块都被分配完了，需要向伙伴系统申请几个页形成新的大内存块等信息。

  如图所示，在分配缓存块的时候，要分两种路径，fast path 和 slow path，也就是快速通道和普通通道。其中 kmem_cache_cpu 就是快速通道，kmem_cache_node 是普通通道。每次分配的时候，要先从 kmem_cache_cpu 进行分配。如果 kmem_cache_cpu 里面没有空闲的块，那就到 kmem_cache_node 中进行分配；如果还是没有空闲的块，才去伙伴系统分配新的页。

  

  那么，kmem_cache_cpu 里面是如何存放缓存块的。

  • 在这里，page 指向大内存块的第一个页，缓存块就是从里面分配的。
  • freelist 指向大内存块里面第一个空闲的项。由于每一项会有指针指向下一个空闲的项，最终所有空闲的项会形成一个链表。
  • partial 指向的也是大内存块的第一个页，之所以名字叫 partial（部分），就是因为它里面部分被分配出去了，部分是空的。这是一个备用列表，当 page 都被分配了出去之后，就会从这里找。

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

  下面，我们来看一下 kmem_cache_node 的定义。

  • 这里面也有一个 partial，是一个链表。这个链表里存放的是含有部分空闲内存块的页。这是 kmem_cache_cpu 里面的 partial 的备用列表，如果那里没有，就到这里来找。

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

需要注意的是当一个页都是空闲的时候，那么这个内存页会被回收。

1.4.2.2.3. 分配过程

下面我们来具体看下具体的分配过程，上面提到了 kmem_cache_alloc_node 会从缓存中分配 task_struct。

那么在 kmem_cache_alloc_node 中会调用 slab_alloc_node（从这个函数的注释中可以看到快速通道和普通通道的概念）。

/*
 * Inlined fastpath so that allocation functions (, kmem_cache_alloc)
 * have the fastpath folded into their functions. So no function call
 * overhead for requests that can be satisfied on the fastpath.
 *
 * The fastpath works by first checking if the lockless freelist can be used.
 * If not then __slab_alloc is called for slow processing.
 *
 * Otherwise we can simply pick the next object from the lockless free list.
 */
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
    gfp_t gfpflags, int node, unsigned long addr)
{
  void *object;
  struct kmem_cache_cpu *c;
  struct page *page;
  unsigned long tid;
......
  tid = this_cpu_read(s->cpu_slab->tid);
  c = raw_cpu_ptr(s->cpu_slab);
......
  object = c->freelist;
  page = c->page;
  if (unlikely(!object || !node_match(page, node))) {
    object = __slab_alloc(s, gfpflags, node, addr, c);
    stat(s, ALLOC_SLOWPATH);
  } 
......
  return object;
}

首先是快速通道，会先取出 cpu_slab 也即 kmem_cache_cpu 的 freelist，这就是第一个空闲的项，可以直接返回了。如果没有空闲的了，则只好进入普通通道，也就是调用 __slab_alloc。

static void *___slab_alloc(struct kmem_cache *s, gfp_t gfpflags, int node,
        unsigned long addr, struct kmem_cache_cpu *c)
{
  void *freelist;
  struct page *page;
......
redo:
......
  /* must check again c->freelist in case of cpu migration or IRQ */
  freelist = c->freelist;
  if (freelist)
    goto load_freelist;


  freelist = get_freelist(s, page);


  if (!freelist) {
    c->page = NULL;
    stat(s, DEACTIVATE_BYPASS);
    goto new_slab;
  }


load_freelist:
  c->freelist = get_freepointer(s, freelist);
  c->tid = next_tid(c->tid);
  return freelist;


new_slab:


  if (slub_percpu_partial(c)) {
    page = c->page = slub_percpu_partial(c);
    slub_set_percpu_partial(c, page);
    stat(s, CPU_PARTIAL_ALLOC);
    goto redo;
  }


  freelist = new_slab_objects(s, gfpflags, node, &c);
......
  return freeli
}

• 在这里，会首先再次尝试一下 kmem_cache_cpu 的 freelist。这是因为，万一当前进程被中断，等回来的时候，别人已经释放了一些缓存，说不定又有空间了呢。如果找到了，就跳到 load_freelist，在这里将 freelist 指向下一个空闲项，返回就可以了。

• 如果 freelist 还是没有，则跳到 new_slab 里面去。这里面我们先去 kmem_cache_cpu 的 partial 里面看。如果 partial 不是空的，那就将 kmem_cache_cpu 的 page，也就是快速通道的那一大块内存，替换为 partial 里面的大块内存。然后跳转到 redo，重新试下，这次应该就可以成功了。

• 如果 kmem_cache_cpu 的 partial 是空的，那么就要执行 new_slab_objects 函数了。

  static inline void *new_slab_objects(struct kmem_cache *s, gfp_t flags,
        int node, struct kmem_cache_cpu **pc)
  {
    void *freelist;
    struct kmem_cache_cpu *c = *pc;
    struct page *page;
  
  
    freelist = get_partial(s, flags, node, c);
  
  
    if (freelist)
      return freelist;
  
  
    page = new_slab(s, flags, node);
    if (page) {
      c = raw_cpu_ptr(s->cpu_slab);
      if (c->page)
        flush_slab(s, c);
  
  
      freelist = page->freelist;
      page->freelist = NULL;
  
  
      stat(s, ALLOC_SLAB);
      c->page = page;
      *pc = c;
    } else
      freelist = NULL;
  
  
    return freelis
  }
  

  • 在这里，get_partial 会根据 node id，找到相应的 kmem_cache_node，然后调用 get_partial_node，开始在这个节点进行分配。

    在 get_partial_node 中 acquire_slab 会从 kmem_cache_node 的 partial 链表中拿下一大块内存来，并且将 freelist，也就是第一块空闲的缓存块，赋值给 t。

    如果可以取到的话，也就是 t 不为空的话，那么在第一轮循坏的时候，会将 kmem_cache_cpu 的 page 指向取下来的这一大块内存。返回的 object 就是这块内存里面的第一个缓存块 t。

    如果 kmem_cache_cpu 也有一个 partial，就会进行第二轮，再次取下一大块内存来，这次调用 put_cpu_partial，放到 kmem_cache_cpu 的 partial 里面。

    /*
     * Try to allocate a partial slab from a specific node.
     */
    static void *get_partial_node(struct kmem_cache *s, struct kmem_cache_node *n,
            struct kmem_cache_cpu *c, gfp_t flags)
    {
      struct page *page, *page2;
      void *object = NULL;
      int available = 0;
      int objects;
    ......
      list_for_each_entry_safe(page, page2, &n->partial, lru) {
        void *t;
    
    
        t = acquire_slab(s, n, page, object == NULL, &objects);
        if (!t)
          break;
    
    
        available += objects;
        if (!object) {
          c->page = page;
          stat(s, ALLOC_FROM_PARTIAL);
          object = t;
        } else {
          put_cpu_partial(s, page, 0);
          stat(s, CPU_PARTIAL_NODE);
        }
        if (!kmem_cache_has_cpu_partial(s)
          || available > slub_cpu_partial(s) / 2)
          break;
      }
    ......
      return object;
    }
    

  • 之后回到 new_slab_objects 函数，通过 freelist 判断是否有分配到。如果也没有，比如 kmem_cache_node 里面也没有空闲的内存，也就是原来分配的页里面都放满了。

  那么这个时候会调用 new_slab 函数，而这个函数会调用 allocate_slab。alloc_slab_page 函数分配的时候，会按 kmem_cache_order_objects 里面的 order 来。如果第一次分配不成功，说明内存已经很紧张了，那就换成 min 版本的 kmem_cache_order_objects。

  static struct page *allocate_slab(struct kmem_cache *s, gfp_t flags, int node)
  {
    struct page *page;
    struct kmem_cache_order_objects oo = s->oo;
    gfp_t alloc_gfp;
    void *start, *p;
    int idx, order;
    bool shuffle;
  
  
    flags &= gfp_allowed_mask;
  ......
    page = alloc_slab_page(s, alloc_gfp, node, oo);
    if (unlikely(!page)) {
      oo = s->min;
      alloc_gfp = flags;
      /*
       * Allocation may have failed due to fragmentation.
       * Try a lower order alloc if possible
       */
      page = alloc_slab_page(s, alloc_gfp, node, oo);
      if (unlikely(!page))
        goto out;
      stat(s, ORDER_FALLBACK);
    }
  ......
    return page;
  }
  

• 那么最终会返回所需要的结构体。

1.4.2.3. 优缺点

SLUB 的好处在于避免了外部碎片，并且分配速度很快。

1.5. 页面换出

一般情况下，页面只有在被使用的时候，才会放在物理内存中。如果过了一段时间不被使用，即便用户进程并没有释放它，物理内存管理也有责任做一定的干预。例如，将这些物理内存中的页面换出到硬盘上去；将空出的物理内存，交给活跃的进程去使用。

那么页面换出的常见情况有以下两种：

• 最常见的情况就是，分配内存的时候，发现没有内存可分配了，就试图回收一下。例如，在申请一个页面的时候，会调用 get_page_from_freelist，接下来的调用链为 get_page_from_freelist->node_reclaim->__node_reclaim->shrink_node，通过这个调用链可以看出，页面换出也是以内存节点为单位的。

• 第二种情况是内存管理系统应该主动去做的，而不是等没有内存了才进行页面换出。负责这个换出的是内核线程 kswapd（每个 NUMA 节点都有一个单独的 kswapd 线程）。kswapd 在系统初始化的时候就被创建了，它是一个无限循环，在循坏中，如果内存使用没有那么紧张，它就不做换出，但是当内存紧张的时候，它就会去检查一些内存，看看是否需要换出一些内存页。

  /*
   * The background pageout daemon, started as a kernel thread
   * from the init process.
   *
   * This basically trickles out pages so that we have _some_
   * free memory available even if there is no other activity
   * that frees anything up. This is needed for things like routing
   * etc, where we otherwise might have all activity going on in
   * asynchronous contexts that cannot page things out.
   *
   * If there are applications that are active memory-allocators
   * (most normal use), this basically shouldn't matter.
   */
  static int kswapd(void *p)
  {
    unsigned int alloc_order, reclaim_order;
    unsigned int classzone_idx = MAX_NR_ZONES - 1;
    pg_data_t *pgdat = (pg_data_t*)p;
    struct task_struct *tsk = current;
  
  
      for ( ; ; ) {
  ......
          kswapd_try_to_sleep(pgdat, alloc_order, reclaim_order,
            classzone_idx);
  ......
          reclaim_order = balance_pgdat(pgdat, alloc_order, classzone_idx);
  ......
      }
  }
  

  这里的调用链路也是 balance_pgdat->kswapd_shrink_node->shrink_node，是以内存节点为单位的，最后也是调用 shrink_node。shrink_node 之后会调用 shrink_node_memcg。

  /*
   * This is a basic per-node page freer.  Used by both kswapd and direct reclaim.
   */
  static void shrink_node_memcg(struct pglist_data *pgdat, struct mem_cgroup *memcg,
              struct scan_control *sc, unsigned long *lru_pages)
  {
  ......
    unsigned long nr[NR_LRU_LISTS];
    enum lru_list lru;
  ......
    while (nr[LRU_INACTIVE_ANON] || nr[LRU_ACTIVE_FILE] ||
            nr[LRU_INACTIVE_FILE]) {
      unsigned long nr_anon, nr_file, percentage;
      unsigned long nr_scanned;
  
  
      for_each_evictable_lru(lru) {
        if (nr[lru]) {
          nr_to_scan = min(nr[lru], SWAP_CLUSTER_MAX);
          nr[lru] -= nr_to_scan;
  
  
          nr_reclaimed += shrink_list(lru, nr_to_scan,
                    lruvec, memcg, sc);
        }
      }
  ......
    }
  ......
  }
  
  enum lru_list {
    LRU_INACTIVE_ANON = LRU_BASE,
    LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    LRU_UNEVICTABLE,
    NR_LRU_LISTS
  };
  
  #define for_each_evictable_lru(lru) for (lru = 0; lru <= LRU_ACTIVE_FILE; lru++)
  
  
  static unsigned long shrink_list(enum lru_list lru, unsigned long nr_to_scan, struct lruvec *lruvec, struct mem_cgroup *memcg, struct scan_control *sc)
  {
    if (is_active_lru(lru)) {
      if (inactive_list_is_low(lruvec, is_file_lru(lru),
             memcg, sc, true))
        shrink_active_list(nr_to_scan, lruvec, sc, lru);
      return 0;
    }
  
    return shrink_inactive_list(nr_to_scan, lruvec, sc, lru);
  }
  

  • 这里面有个 LRU 链表，所有的页面都被挂在 LRU 链表中。LRU 是 Least Recent Use，也就是最近最少使用。这个链表会按照活跃程度进行排序，这样就容易把不怎么用的内存页拿出来。

  • 另外，可以看到内存页总共分两类，一类是匿名页，和虚拟地址空间进行关联；一类是内存映射，不但和虚拟地址空间关联，还和文件管理关联。它们每一类都有两个列表，一个是 active，一个是 inactive。顾名思义，active 就是比较活跃的，inactive 就是不怎么活跃的。这两个里面的页会变化，过一段时间，活跃的可能变为不活跃，不活跃的可能变为活跃。如果要换出内存，那就是从不活跃的列表中找出最不活跃的，换出到硬盘上。

    shrink_list 会先缩减活跃页面列表（将活跃中的一些页面换到不活跃中），再压缩不活跃的页面列表。对于不活跃列表的缩减，shrink_inactive_list 就需要对页面进行回收：对于匿名页来讲，需要分配 swap，将内存页写入 swap 中；对于内存映射关联了文件的，我们需要将在内存中对于文件的修改写回到文件中。

另外，换出的页会在页表的相应位置做标记，说明已经换出。

1.5.1. 总结

关于物理内存分配和页面换出的总结如下：