Linux 内核｜内存管理

本文结合了诸多资料，以更加结构化的方式构建内存管理的知识体系，从虚拟内存布局到物理内存分配，全面地描述了内存管理中最重要的三件事。

1.前言

《linux-insides》作者说内存管理是操作系统内核中最复杂的部分。

概括来讲，Linux 内存管理主要有三件事，全文也会按照这三件事来叙述。

虚拟内存管理：将虚拟内存分成大小相等的页。
物理内存管理：将物理内存分成大小相等的页。
虚拟内存和物理内存的映射：通过页表将虚拟内存也和物理内存映射起来，并且在物理内存紧张的时候可以换出到硬盘中。

2.虚拟内存管理

每个进程创建时，都会分配一个虚拟内存空间，如图所示，虚拟内存空间分为用户空间和内核空间。

2.1 用户空间和内核空间的划分

在 Linux 里面，无论是进程，还是线程，到了内核里面，我们统一都叫任务（Task），由一个统一的结构 task_struct 进行管理。task_struct 中使用了 mm_struct 结构来管理内存。

1	`struct mm_struct *mm;`

mm_struct 中定义了用户态大小。highest_vm_end存储当前虚拟内存地址的最大地址。task_size则是用户态的大小。

struct mm_struct {
......
    unsigned long task_size;    /* size of task vm space */
    unsigned long highest_vm_end;   /* highest vma end address */
......
}

当创建一个新的进程的时候，会做以下的设置：

1	`current->mm->task_size = TASK_SIZE;`

TASK_SIZE 定义如下，也就是 PAGE_OFFSET，其中 32 位系统和 64 位系统分开来看，重点看代码中的注释。

#ifdef CONFIG_X86_32
/*
 * User space process size: 3GB (default).
 */
#define TASK_SIZE    PAGE_OFFSET
#define TASK_SIZE_MAX    TASK_SIZE
/*
config PAGE_OFFSET
        hex
        default 0xC0000000
        depends on X86_32
*/
#else
/*
 * User space process size. 47bits minus one guard page.
*/
#define TASK_SIZE_MAX  ((1UL << 47) - PAGE_SIZE)
#define TASK_SIZE    (test_thread_flag(TIF_ADDR32) ? \
          IA32_PAGE_OFFSET : TASK_SIZE_MAX)
......

（1）32 位系统

对于 32 位系统，最大能够寻址 2^32=4G。
从注释看，用户态最大地址默认是 0xC0000000。故用户态是 3G，内核态是 1G。

（2）64 位系统

对于 64 位系统，虚拟地址只使用了 48 位，2^48=256T。
其中用户态是 128T - 1K，内核态是 128T，用户态和内核态之间隔着很大的空隙，以此来进行隔离。
#define TASK_SIZE_MAX ((1UL << 47) - PAGE_SIZE) **解释：**1 左移 47 位，0x800000000000 = 128T，还需要再减去一页保护页，大小为 PAGE_SIZE，也就是 1K。

2.2 用户空间的布局

（1）受保护区域

这个区域很小，用户不可操作，在 C 语言中，NULL 其实是宏定义，#define NULL (void*)0，也就是说，空指针其实指的就是这个地址。

（2）ELF

ELF 段 = test 段 + data 段 + bss 段。其作用分别是：

Text Segment：存放二进制可执行代码。
Data Segment：存放已初始化的 static 常量、全局变量。
BSS Segment，Block Started by Symbol：存放未初始化的 static 变量、全局变量。

Linux 可执行程序的文件格式是 ELF。每次执行都是从 main 函数位置开始执行，即 test 段。

PS：可以使用 file 命令来查看文件类型。比如，查看可执行文件 zsh，如下。

1
2

➜ ~ file /bin/zsh
zsh: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=dc4d89bbb8fb95d61a21500ba5c100d04a0fa8d5, stripped

（3）Heap

堆的大小是不固定的，它是从地址往高地址增长的。
Heap 用来动态分配内存的区域，使用 malloc 申请小内存（128K以内），就是通过系统调用 brk 在Heap 分配的。

（4）Memory Mapping Segment

内存映射区，可以将文件映射进内存中。
执行二进制文件时需要链接某些动态链接库，可以把相应的 so 文件映射进此区域。
使用 mmap 可以将文件映射到内存映射区，可以快速地更改磁盘文件或进行进程间通信。
malloc 申请大内存，是通过系统调用 mmap 在 内存映射区 分配大块虚拟内存空间。
使用 munmap 释放内存映射区。

（5）Stack

普通局部变量，自动管理内存，后进先出 LIFO。
函数调用的函数栈就是用这里的。

2.3 用户空间的数据结构

mm_struct：/include/linux/mm_types.h
vm：virtual memory.
vma：virtual memory areas.

2.3.1 位置信息

用户空间里面有各个数据段，例如代码、堆、栈、内存映射区等。在 mm_struct 中定义了这些区域的统计信息和位置。

struct mm_struct {
......    
    unsigned long mmap_base;    /* base of mmap area */
    unsigned long mmap_legacy_base; /* base of mmap area in bottom-up allocations */    
......
    unsigned long hiwater_rss; /* High-watermark of RSS usage */
    unsigned long hiwater_vm;  /* High-water virtual memory usage */
    unsigned long total_vm;    /* Total pages mapped */
    unsigned long locked_vm;   /* Pages that have PG_mlocked set */
    atomic64_t    pinned_vm;   /* Refcount permanently increased */
    unsigned long data_vm;     /* VM_WRITE & ~VM_SHARED & ~VM_STACK */
    unsigned long exec_vm;     /* VM_EXEC & ~VM_WRITE & ~VM_STACK */
    unsigned long stack_vm;    /* VM_STACK */    
    spinlock_t arg_lock; /* protect the below fields */
    unsigned long start_code, end_code, start_data, end_data;
    unsigned long start_brk, brk, start_stack;
    unsigned long arg_start, arg_end, env_start, env_end;
    unsigned long saved_auxv[AT_VECTOR_SIZE]; /* for /proc/PID/auxv */    
......
}

mmap_base：内存映射区的起始地址，内存映射区是从高地址到低地址增长的。
total_vm：映射的总页数。当内存吃紧的时候，有些页可以换出到硬盘上，有的页因为比较重要，会被锁定，不能换出。
locked_vm：被锁定不能换出的页数。
pinned_vm：不能换出也不能移动的页数。
data_vm：存放数据的页数。
exec_vm：存放可执行文件的页数。
stack_vm：存放栈的页数。
start_code 和 end_code：可执行代码的开始和结束位置
start_data 和 end_data ：已初始化数据的开始位置和结束位置
start_brk ：堆的起始位置
brk ：堆当前的结束位置
start_stack ：栈的起始位置，栈的结束位置在寄存器的栈顶指针中
arg_start 和 arg_end ：参数列表的位置，位于栈中最高地址的地方。
env_start 和 env_end ：环境变量的位置，位于栈中最高地址的地方。

2.3.2 属性信息

除了位置信息之外，还有一个重要结构 vm_area_struct，专门来描述这些代码、全局变量、堆、栈、内存映射区等区域的属性。

struct vm_area_struct {
        /* The first cache line has the info for VMA tree walking. */
        unsigned long vm_start;                /* Our start address within vm_mm. */
        unsigned long vm_end;                /* The first byte after our end address within vm_mm. */
        /* linked list of VM areas per task, sorted by address */
        struct vm_area_struct *vm_next, *vm_prev;
        struct rb_node vm_rb;
        struct mm_struct *vm_mm;        /* The address space we belong to. */
        struct list_head anon_vma_chain; /* Serialized by mmap_sem &
                                          * page_table_lock */
        struct anon_vma *anon_vma;        /* Serialized by page_table_lock */
        /* Function pointers to deal with this struct. */
        const struct vm_operations_struct *vm_ops;
        struct file * vm_file;                /* File we map to (can be NULL). */
        void * vm_private_data;                /* was vm_pte (shared mem) */

} __randomize_layout;

vm_start 和 vm_end：指定了该区域在用户空间中的起始和结束地址。
vm_next 和 vm_prev：如下图，将当前区域串在链表 mmap 上。
vm_rb：对应一颗红黑树的节点，这颗红黑树将所有vm_area_struct组合起来，便于增删查找。
vm_ops：对这个内存区域可以做的操作的定义。
anon_vma：匿名映射。虚拟内存区域可以映射到物理内存，也可以映射到文件，映射到物理内存的时候称为匿名映射，映射到文件需要 vm_file 指定被映射文件，vm_pgoff 存储偏移量。

在上图可以看到，在 mm_struct 中定义了两个指针，mmap 和 mm_rb。

mmap 指向一个通过vm_next和vm_prev组合而成的双向链表，将各个区域 vm_area_struct 串联起来。
mm_rb 指向一颗红黑树，这颗红黑树将所有vm_area_struct组合起来，便于增删查找。

struct mm_struct {
......    
    struct vm_area_struct *mmap;        /* list of VMAs */
    struct rb_root mm_rb;  
......    
}

mm_rb 的类型是 rb_root；vm_rb 的类型是 rb_node。二者定义如下，可以看出 mm_rb 就是 struct rb_node *类型。

struct rb_node {
        unsigned long  __rb_parent_color;
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
        struct rb_node *rb_node;
};

2.4 用户空间内存映射的建立

load_elf_binary ：/fs/binfmt_elf

换句话问：mm_struct 中各区域的位置、属性信息是如何与众多 vm_area_struct 联系起来的呢？
**一句话答：**在 load_elf_binary 中完成。load_elf_binary 中定义了一个 mm_struct 类型指针变量 mm，并指向 current->mm（当前进程的 mm_struct）。通过对 mm 的赋值，完成内存映射的建立。

无论是加载内核、调用第一个用户态进程 init，还是 exec 运行一个二进制程序都需要加载 ELF 文件，即调用 load_elf_binary 函数。

在 load_elf_binary 中，加载 ELF 文件后，会建立内存映射，主要做以下几件事：

调用 setup_new_exec，设置内存映射区 mmap_base；
调用 setup_arg_pages，设置栈的 vm_area_struct，这里面设置了 mm->arg_start 是指向栈底的，current->mm->start_stack 就是栈底；
elf_map 会将 ELF 文件中的代码部分映射到内存中来；
set_brk 设置了堆的 vm_area_struct，这里面设置了 current->mm->start_brk = current->mm->brk，也就是说，堆里面还是空的；
load_elf_interp 将依赖的 so 文件映射到内存中的内存映射区域。

static int load_elf_binary(struct linux_binprm *bprm)
{
......
  setup_new_exec(bprm);  // 设置内存映射区 mmap_base
......
  retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
                                 executable_stack);  // 设置栈的 vm_area_struct
......
  error = elf_map(bprm->file, load_bias + vaddr, elf_ppnt,
                                elf_prot, elf_flags, total_size);  // 加载 ELF 中代码
......
  retval = set_brk(elf_bss, elf_brk, bss_prot); // 设置了堆的 vm_area_struct
......
  elf_entry = load_elf_interp(&loc->interp_elf_ex,
                                            interpreter,
                                            &interp_map_addr,
                                            load_bias, interp_elf_phdata);
......
  mm = current->mm;
  // current 是 get_current() 的宏，current 就是当前进程的指针。
  // mm 指向 current->mm，也就是说，之后的所有操作，都是在操作进程的 mm_struct。
  
  current->mm->end_code = end_code;
  current->mm->start_code = start_code;
  current->mm->start_data = start_data;
  current->mm->end_data = end_data;
  current->mm->start_stack = bprm->p;
......
}

2.5 内核空间的布局

到了内核里面，并不会直接使用物理内存地址了，依然使用虚拟地址，以下讨论的均是虚拟地址。

在看内核态布局之前，先明确四个重要概念。

（1）进程无法访问内核空间

进程无法访问，只能通过调用系统调用，进入内核。

（2）创建进程时内核态会创建**task_struct** 实例

进程创建需要使用系统调用，此时内核态会在直接映射区创建 task_struct 实例。task_struct 中有 mm_struct 来管理虚拟地址空间。

（3）内核空间是共享的

内核态的虚拟地址空间和进程是无关的，所有进程通过系统调用进入到内核之后，看到的虚拟地址空间都是一样的。
在内核空间中，每个进程都有独立的内核栈，内核栈是各用各的。但是如果想知道的话，还是能够知道每个进程的内核栈在哪里的。所以，如果要访问一些公共的数据结构，需要进行锁保护。

（4）内核里面也会有内核的代码

内核同样有 Text Segment、Data Segment 和 BSS Segment。
内核启动的时候，内核代码也是 ELF 格式的。

在内核态，32 位和 64 位的布局差别比较大，主要是因为 32 位内核态空间太小了，下面分别讨论。

2.5.1 32 位内核态布局

（1）直接映射区

32 位的内核态虚拟地址空间一共就 1G，占绝大部分的前 896M 就是直接映射区。直接映射区和物理内存的一整块空间直接映射。虚拟内存地址减去 3G，就得到物理内存的位置。

内核中有两个宏用于虚拟地址和物理地址之间的转化：

__pa(vaddr) 返回与虚拟地址 vaddr 相关的物理地址。
__va(paddr) 则计算出对应于物理地址 paddr 的虚拟地址。

// 目录：/source/arch/alpha/include/asm/page.h

#define __pa(x)    ((unsigned long) (x) - PAGE_OFFSET)
#define __va(x)    ((void *)((unsigned long) (x) + PAGE_OFFSET))

直接映射区主要有三部分：

**ELF 段：**在系统启动的时候，物理内存的前 1M 已经被占用了。因为直接映射区是直接映射到物理内存的 0 - 896M 区域，所以虚拟内存空间中，也是从 1M 之后加载 txt、data、bss 段。
task_struct **实例：**在内核运行的过程中，如果碰到系统调用创建进程，会创建 task_struct 实例，内核的进程管理代码会将实例创建在 3G 至 3G+896M 的虚拟空间中，当然也会被放在物理内存里面的前 896M 里面，相应的页表也会被创建。
**内核栈：**在内核运行的过程中，会涉及内核栈的分配，内核的进程管理的代码会将内核栈创建在 3G 至 3G+896M 的虚拟空间中，当然也就会被放在物理内存里面的前 896M 里面，相应的页表也会被创建。

**补充：**一个物理内存的概念：高端内存

x86 架构中将物理地址空间划分三部分，也叫区域（后面在讲物理内存的组织方式会详细提到区域。）：ZONE_DMA、ZONE_NORMAL 和 ZONE_HIGHMEM。ZONE_HIGHMEM 被称为高端内存，也就是 896M 到 4G 之间的这段物理内存（32 位最大寻址空间为 4G）。
内核中除了内存管理模块外，其余均操作虚拟地址。但是 896M 到 1G ，只有这 128M 虚拟地址空间，无法直接映射/访问到所有的高端内存。
这 128M 虚拟地址空间分为内核动态映射空间、持久内核映射区、固定映射区、临时映射区。通过这四个区进行动态映射，达到访问所有高端内存的目的。
访问高端内存的最基本思想：在 128M 虚拟地址空间中，借一段虚拟地址空间，建立临时地址映射，用完后释放，这段虚拟地址空间可以循环使用，访问所有物理内存。

（2）内核动态映射空间（noncontiguous memory allocation）

VMALLOC_START 到 VMALLOC_END 之间称为内核动态映射空间，，在内核里可以使用 vmalloc 来申请内存。
例子：假设物理内存中 896M 到 1.5G 之间已经被用户态进程占用了，并且映射关系放在了进程的页表中，内核 vmalloc 的时候，只能从分配物理内存 1.5G 开始，就需要使用内核动态映射空间的虚拟地址进行映射，映射关系放在专门给内核自己用的页表里面。

（3）持久内核映射区（permanent kernel mapping）

PKMAP_BASE 到 FIXADDR_START 的空间称为持久内核映射，这个地址范围是 4G-8M 到 4G-4M 之间。
使用 alloc_pages() 函数的时候，在物理内存的高端内存得到 struct page 结构，可以调用 kmap() 将其在映射到这个区域。
因为允许永久映射的数量有限，当不再需要高端内存时，应该解除映射，这可以通过kunmap()函数来完成。

（4）固定映射区（fixing mapping）

FIXADDR_START 到 FIXADDR_TOP(0xFFFF F000) 的空间，称为固定映射区域。
主要用于满足特殊需求。

（5）临时映射区（temporary kernel mapping）

在固定映射区中，会使用一些空间当作临时映射区。
临时内核映射通过 kmap_atomic 和 kunmap_atomic 实现，主要用于当需要写入物理内存或主存时的操作，如将文件从主存写入内存或者将文件从内存写入主存时使用。
例子：用户态需要将一个文件映射到虚拟地址空间中。

2.5.2 63 位内核态布局

注意：下图引用自《趣谈 Linux 操作系统》，作者在做图时，部分地址偏移了1 Byte，但不影响整体叙述逻辑（我这边太懒了，就不重画了）。
打个比方，一个 16 Byte 的空间，首地址是 0x00，最后一块地址应该是 0x0F，作者写成了 0x10。
比如在图中，VMALLOC_START 是 vmalloc 区域的首地址，VMALLOC_END 是 vmalloc 区域的最后一块地址。Vmalloc 区域是 32T，所以 VMALLOC_END 应该是 0xFFFF E8FF FFFF FFFF。

64 位的内核布局反而简单，因为虚拟空间实在是太大了，根本不需要高端内存，因为内核虚拟地址空间是 128T，根本不可能有物理内存超过这个值。

64 位的内核主要包含以下几个部分：

从 0xFFFF 8000 0000 0000 开始就是内核的部分，只不过一开始有 8T 的空档区域。
从 __PAGE_OFFSET_BASE(0xFFFF 8800 0000 0000) 开始的 64T 的虚拟地址空间是直接映射区域，减去 PAGE_OFFSET（即内核态与用户态的分界线）就是物理地址。

注意：因为 64 位的直接映射区 64T 足够大，足以直接映射整个物理内存。但大部分情况下，虚拟地址和物理地址之间的映射还是会通过建立页表的方式进行映射。

从 VMALLOC_START（0xFFFF C900 0000 0000）开始到 VMALLOC_END（0xFFFF E900 0000 0000）的 32T 的空间是给 vmalloc 的。
从 VMEMMAP_START（0xFFFF EA00 0000 0000） 开始的 1T 空间用于存放物理页面的描述结构 struct page的。
从 __START_KERNEL_map（0xFFFF FFFF 8000 0000） 开始的 512M 用于存放内核代码段、全局变量、BSS 等。这里对应到物理内存开始的位置，减去 __START_KERNEL_map 就能得到物理内存的地址。这里和直接映射区有点像，但是不矛盾，因为直接映射区之前有 8T 的空档区域，早就过了内核代码在物理内存中加载的位置。

2.6 一张图总结

32 位

创建进程时，内核态会在直接映射区创建 task_struct 用来管理进程。task_struct 中有 mm_struct 来管理虚拟地址空间。

下图中，直接映射区有 task_struct、mm_struct、vm_area_struct 来表示虚拟地址空间。但需要注意的是，一个系统中有多个进程，直接映射区中也是有多个 task_struct，而不是只对应一个虚拟内存空间。

64 位

与 32 位相比，64位的内核态简单得多，并且内核态代码有专门的代码段。

3.地址映射之分段机制

在 Linux 内核｜启动中，有提到分段机制，规划虚拟空间的时候，也是将空间分成多个段（Segment）进行保存。

3.1 分段机制的原理

分段机制下的虚拟地址由两部分组成，段选择子和段内偏移量。

段选择子就保存在咱们前面讲过的段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。
虚拟地址中的段内偏移量应该位于 0 和段界限之间。如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。

例如，我们将上面的虚拟空间分成以下 4 个段，用 0～3 来编号。每个段在段表中有一个项，在物理空间中，段的排列如下图的右边所示。

如果要访问段 2 中偏移量 600 的虚拟地址，我们可以计算出物理地址为，段 2 基地址 2000 + 偏移量 600 = 2600。

3.2 分段机制在 Linux 中的使用

段表全称段描述符表（segment descriptors），放在全局描述符表 GDT（Global Descriptor Table）里面，会有下面的宏来初始化段描述符表里面的表项。从 GDT_ENTRY_INIT 宏可以看出，一个段表项由段基地址 base、段界限 limit，还有一些标识符组成。

#define GDT_ENTRY_INIT(flags, base, limit) { { { \
        .a = ((limit) & 0xffff) | (((base) & 0xffff) << 16), \
        .b = (((base) & 0xff0000) >> 16) | (((flags) & 0xf0ff) << 8) | \
            ((limit) & 0xf0000) | ((base) & 0xff000000), \
} } }

在下面代码中可以看到，无论 64 位的还是 32 位的，都使用 GDT_ENTRY_INIT 定义了内核代码段、内核数据段、用户代码段和用户数据段。

DEFINE_PER_CPU_PAGE_ALIGNED(struct gdt_page, gdt_page) = { .gdt = {
#ifdef CONFIG_X86_64
    [GDT_ENTRY_KERNEL32_CS]     = GDT_ENTRY_INIT(0xc09b, 0, 0xfffff),
    [GDT_ENTRY_KERNEL_CS]       = GDT_ENTRY_INIT(0xa09b, 0, 0xfffff),
    [GDT_ENTRY_KERNEL_DS]       = GDT_ENTRY_INIT(0xc093, 0, 0xfffff),
    [GDT_ENTRY_DEFAULT_USER32_CS]   = GDT_ENTRY_INIT(0xc0fb, 0, 0xfffff),
    [GDT_ENTRY_DEFAULT_USER_DS] = GDT_ENTRY_INIT(0xc0f3, 0, 0xfffff),
    [GDT_ENTRY_DEFAULT_USER_CS] = GDT_ENTRY_INIT(0xa0fb, 0, 0xfffff),
#else
    [GDT_ENTRY_KERNEL_CS]       = GDT_ENTRY_INIT(0xc09a, 0, 0xfffff),
    [GDT_ENTRY_KERNEL_DS]       = GDT_ENTRY_INIT(0xc092, 0, 0xfffff),
    [GDT_ENTRY_DEFAULT_USER_CS] = GDT_ENTRY_INIT(0xc0fa, 0, 0xfffff),
    [GDT_ENTRY_DEFAULT_USER_DS] = GDT_ENTRY_INIT(0xc0f2, 0, 0xfffff),
......
#endif
} };
EXPORT_PER_CPU_SYMBOL_GPL(gdt_page);

值得注意的是，上面代码中 GDT_ENTRY_INIT 第二个参数 base 都是 0，也就是说，所有的段的起始地址都是一样的，都是 0。

在 Linux 操作系统中，并没有使用到全部的分段功能。
那分段是不是完全没有用处呢？分段可以做权限审核，例如用户态 DPL 是 3，内核态 DPL 是 0。当用户态试图访问内核态的时候，会因为权限不足而报错。

#define __KERNEL_CS         (GDT_ENTRY_KERNEL_CS*8)
#define __KERNEL_DS         (GDT_ENTRY_KERNEL_DS*8)
#define __USER_DS           (GDT_ENTRY_DEFAULT_USER_DS*8 + 3)
#define __USER_CS           (GDT_ENTRY_DEFAULT_USER_CS*8 + 3)

Linux 倾向于另外一种从虚拟地址到物理地址的转换方式，称为分页（Paging）。

4.地址映射之分页机制

4.1 物理内存分页

操作系统把物理内存分成一块一块大小相同的页，这样更方便管理。有的内存页面长时间不用了，可以暂时写到硬盘上，称为换出。一旦需要的时候，再加载进来，叫作换入。**好处：**这样可以扩大可用物理内存的大小，提高物理内存的利用率。

换入和换出都是以页为单位的，页面的大小一般为 4KB。为了能够定位和访问每个页，需要有个页表，保存每个页的起始地址，再加上在页内的偏移量，组成线性地址，就能对于内存中的每个位置进行访问了。

4.2 虚拟内存分页

虚拟内存地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址。这个基地址与页内偏移的组合就形成了物理内存地址。

虚拟内存中的页通过页表映射到物理内存中的页。

4.3 问题：页表过大

32 位环境下，虚拟地址空间共 4GB。如果分成 4KB 一个页，那就是 1M 个页。每个页表项需要 4 个字节来存储，那么整个 4GB 空间的映射就需要 4MB 的内存来存储映射表。如果每个进程都有自己的映射表，100 个进程就需要 400MB 的内存。对于 1G 的内核态来讲，页表太大。

而且页表中所有页表项必须提前建好，并且要求虚拟地址里面的页号是连续的。否则无法通过虚拟地址里面的页号找到对应的页表项。

4.4 解决：多级页表

（1）什么是多级页表

4G 的虚拟地址空间需要 4M 的页表来储存映射。将这 4M 的空间进行分页，则需要 4K 的页表来储存映射，这 4K 的页表称为页目录页。

（2）多级页表需要多少内存来映射

如上图所示，4G 的虚拟地址空间需要使用 4M + 4K 的内存来映射。但实际上并不会给一个进程分配所有的内存。

当某进程需要一页数据时，如果只使用页表，1M 个页表项，就需要 4M 的内存来储建立页表。但如果使用页目录表，只需要使用 8K，也就是上图中红色区域。

为什么呢？保存 1K 个页目录项，需要 4K 内存。通过页目录项，就可以定位到页表项的大致范围，这个大致范围就是页表项所在的页表项页，而页表项页只需 4K。所以加起来只需要 4K + 4K = 8K。

（3）如何找到映射的物理地址

一个虚拟地址 4 Byte，32 bit。其中，页目录项 10 bit，页表项 10 bit，页内偏移 12 bit。（仔细想想，10bit/10bit/12bit 完全够用，可以定位虚拟内存/物理内存的任何一个位置）

通过 前 10bit 在页目录表中找到页目录项。页目录项中记录了一整页页表的物理地址。
通过 中间 10bit 在这页页表中，找到页表项。页表项中记录了虚拟地址的页，所对应的物理地址页。
通过 最后 12bit 的页内偏移量，在物理地址页中定位到想要的数据。

4.5 64 位的四级目录

对于 64 位的系统，两级也不够用，就变成了四级目录，分别是全局页目录项 PGD（Page Global Directory）、上层页目录项 PUD（Page Upper Directory）、中间页目录项 PMD（Page Middle Directory）和页表项 PTE（Page Table Entry）。

5.物理内存管理之组织方式

5.1 三种内存模型的演进

下面关于内存模型的三张图出自内存模型这篇文章，写的非常详尽。

5.1.1 什么是内存模型

物理内存被划分成一个个大小为 4K 的页帧（Page Frame），每个页帧都有唯一的编号，叫PFN(Page Frame Number)。
对于每个物理页帧，内核都会创建一个 struct page 的数据结构来封装每个物理页帧的状态，因此物理页帧与 page 之间存在着1:1的关系。
系统必须提供两者之间相互转换的方式，即系统可以通过 PFN 拿到对应的 struct page, 也可以通过 struct page 得到对应的 PFN, 内核中提供了两个宏来完成该转换，分别是 page_to_pfn 与 pfn_to_page。
内存模型是指 Linux 内核用怎么样的方式去管理物理内存，其主要解决的问题就是如何组织内存页帧，使得 PFN 与 struct page 转换能够高效便捷地实现。

5.1.2 平坦内存模型 FLATMEM

FLAT memory mode

理想情况下，物理内存是一块地址连续的存储空间，这样物理页帧的PFN也是连续的，因此最简单直接地方式是将所有的 struct page 保存在全局变量 mem_map 中。每个 struct page 的索引就是对应物理页帧的PFN。因而对于任何一个地址，只要直接除一下每页的大小，很容易直接算出在哪一页。
如果是这样，整个物理内存的布局就非常简单、易管理，这就是最经典的平坦内存模型（Flat Memory Model）。
Linux早期使用的就是这种内存模型，比如下面所讲的 SMP / UMA 就是使用的 FLATMEM。

5.1.3 不连续内存模型 DISCONTIGMEM

Discontiguous Memory Model

如果物理内存存在大块的不连续区间，由于 mem_map 使用PFN作为 page 的索引，那么这些不连续区间对应的PFN就也会占用 mem_map 中的位置，形成空洞（hole），造成大量的内存空间浪费。
比如后面讲的 NUMA 就是非连续内存模型。
为了解决以上问题，对于每个 NUMA 的内存节点，Linux都构造一个独立的内存管理子系统，由 struct pglist_data 表示。pg_data_t 包含 node_mem_map 数组，它映射属于该节点的物理页面。
每个 node_mem_map 数组其实就是一个 FLATMEM。
DISCONTIGMEM是个稍纵即逝的内存模型，在SPARSEMEM出现后即被完全替代。

5.1.4 稀疏内存模型 SPARSEMEM

Sparse Memory Model

DISCONTIGMEM 的本意是应对非连续的物理内存，但其又将NUMA架构下的每个 node 看着是连续的，这其实并不合理，特别是在支持内存热插拔的系统当中。
系统需要一种机制能够更灵活地管理粒度更小的连续内存区块，这种内存模型叫着稀疏内存模型（Sparse Memory Model）。
SPARSEMEM 已经完全覆盖了前两个内存模型的所有功能，特别是可以完全替代不够灵活的 DISCONTIGMEM，SPARSEMEM 是当前内核默认的选择。

5.2 两种多处理器计算机体系架构

下面描述的对称多处理器与非对称多处理器中，所指的处理器是物理 CPU 的意思（是硬件概念，和在软件看来多核和多线程就是多个处理器），多处理器就是主板上有多个 CPU 插槽（socket）。家用 PC 通常是单 socket，服务器通常可支持 2 socket（也常称为“双路”），也有 4 或者 8 socket。

5.2.1 易混概念

有关处理器 processor、CPU、核心 Core、线程 Threads 可以看这个知乎问题下「知乎用户G0K17q」和「木头龙」的回答。

（1）处理器 processor

对程序指令进行处理的设备。一开始是指那一小片物理处理器。随着技术发展，有了多核多线程处理器。在软件角度来看，多核多线程和多个物理处理器没有区别，能处理程序指令就是处理器。（所以常说的 processor 数、CPU数其实就是下面讲的线程数 threads ）

（2）CPU

某些计算机因为通用处理器的性能无法满足应用的性能需要，可以通过加装特殊的专用处理器来提供特定应用的性能。比如图形处理器 GPU 就是专用处理器。这些专用处理器有一个统一的名词叫 Coprocessor，协处理器。为了与协处理器区分，传统的处理器一般称之为CPU（Central Process Unit，中央处理器）。

（3）核心 Core

物理核心，指 CPU 上完整、可独立执行控制流的处理单元，也是操作系统调度进程的单位。x86 的核包含了CPU运算的基本部件，如逻辑运算单元(ALU), 浮点运算单元(FPU), L1和L2缓存。一个Socket里可以有多个Core。

（4）线程 Threads

也被常称为逻辑核心 logical core 、虚拟核心 virtual core、逻辑处理器 logical processor、processor 数、CPU 数（茴字的四种写法，咳咳）。CPU利用超线程(Hyper-Threading)技术，在一个物理核心 Core 内部引入了额外的硬件设计模拟了两个逻辑处理器 (Logical Processor)。每个逻辑处理器都有独立的处理器状态，但共享Core内部的计算资源，如ALU，FPU，L1，L2缓存。

（5）CPU 线程和程序线程

这两个线程并不是一回事。程序的线程是软件概念，一个程序有多个线程，可以在处理器上轮流并发执行。CPU的线程是硬件的概念，线程数就是逻辑核心数。16线程就是能让16个线程并行执行。

（6）常用查询命令

# 查看物理 cpu 数：
cat /proc/cpuinfo| grep "physical id"| sort| uniq| wc -l

# 查看每个物理 cpu 中 核心数(core 数)：
cat /proc/cpuinfo | grep "cpu cores" | uniq

# 查看总的逻辑 cpu 数（processor 数）：
cat /proc/cpuinfo| grep "processor"| wc -l

# 查看 cpu 型号：
cat /proc/cpuinfo | grep name | cut -f2 -d: | uniq -c

5.2.2 对称多处理器 SMP

Symmetric multiprocessing

对称多处理器架构，是目前最常见的多处理器计算机架构。CPU 是通过总线去访问内存的，这就是最经典的内存使用方式。（题外话：youtube 一个博主–笔记本维修厮，录修电脑的视频，很有意思。在他的维修案例中，经常会换南桥、北桥。实际上南桥、北桥就是下图中的 IO 芯片）

在这种模式下，CPU 也会有多个，在总线的一侧。所有的内存条组成一大片内存，在总线的另一侧，所有的 CPU 访问内存都要过总线，而且距离都是一样的，这种模式称为 SMP。

5.2.3 非对称多处理器 AMP

Asymmetric Multiprocessing

非对称多处理器架构，则是与SMP相对的概念。举个 AMP 的例子，大部分手机都有两个处理器，AP（Application Processor，应用处理器）负责运算，BP（Baseband Processor，基带处理器）负责通信。AP 和 BP 两个处理器架构不一样，也叫异构。

**再次说明：**SMP 和 AMP 讨论的只计算机系统层面的，关注对称与非对称，指的是多个物理处理器是否对称，也就是说多个物理处理器是否相同，而不关注处理器内部的设计。比如骁龙888处理器中有大小核，也就是说里面的物理核心 core 是不同，所以也叫做异构。但这不是我们探讨的范围，我们不关心物理处理器内部。

5.2.4 SMP 和 AMP 区别

SMP 的多个处理器都是同构的，使用相同架构的 CPU；而 AMP 的多个处理器则可能是异构的。
SMP 的多个处理器共享同一内存地址空间；而AMP的每个处理器则拥有自己独立的地址空间。
SMP 的多个处理器操通常共享一个操作系统的实例；而 AMP 的每个处理器可以有或者没有运行操作系统，运行操作系统的CPU也是在运行多个独立的实例。
SMP 的多处理器之间可以通过共享内存来协同通信；而 AMP 则需要提供一种处理器间的通信机制。
x86多处理器服务器都是 SMP 架构的，而很多嵌入式系统则是 AMP 架构的。

5.3 SMP 系统的两种内存架构

SMP 系统中有两种模式 UMA 和 NUMA，这是根据处理器对共享内存的访问的距离来区分的。

5.3.1 UMA 一致性内存访问

Uniform memory access

UMA 模式下，处理器对共享内存的访问距离和时间是相同的。但UMA 有一个显著的缺点，就是总线会成为瓶颈，因为数据都要走它。
起初，SMP 系统都是 UMA 模式，UMA 是 SMP 架构系统最经典的内存架构。所以很多在表述时，UMA 和 SMP 可以相互替换。

5.3.2 NUMA 非一致内存访问

Non-uniform memory access

为了提高性能和可扩展性，后来有了一种更高级的模式，NUMA（Non-uniform memory access），非一致内存访问。
在这种模式下，内存不是一整块。内存的访问时间是依赖于处理器和内存之间的相对位置的。这种设计里存在和处理器相对近的内存，通常被称作本地内存；还有和处理器相对远的内存，通常被称为非本地内存。
每个 CPU 都有自己的本地内存，CPU 访问本地内存不用过总线，因而速度要快很多。在本地内存不足的情况下，每个 CPU 都可以去另外的 NUMA 节点申请内存，这个时候访问延时就会比较长。

5.4 NUMA 架构的节点、区域、页

这里主要分析当前的主流场景，NUMA 方式。

节点

（1）概念

每个 CPU 和本地内存在一起，称为一个 NUMA 节点。
内存被分成了多个节点，每个节点再被分成一个一个的页。由于页需要全局唯一定位，页还是需要有全局唯一的页号的。但是由于物理内存不是连起来的了，页号也就不再连续了。
于是内存模型就变成了非连续内存模型（后来被稀疏内存模型替代），管理起来就复杂一些。

（2）数据结构

NUMA 节点用 typedef struct pglist_data pg_data_t 这个结构来表示，主要有以下的成员变量：

node_id：每一个节点都有自己的 ID。
node_mem_map：当前节点的 struct page 数组，用于描述这个节点里面的所有的页。
node_start_pfn：当前节点的起始页号。
node_spanned_pages：当前节点中包含不连续的物理内存地址的页面数。
node_present_pages：真正可用的物理页面的数目。
nr_zones：当前节点的区域的数量。（区域下面会描述）
node_zonelists：备用节点和它的内存区域的情况。如果本节点内存不够怎么办，就需要在备用节点中分配内存。

举个例子：64M 物理内存隔着一个 4M 的空洞，然后是另外的 64M 物理内存。这样换算成页面数目就是，16K 个页面隔着 1K 个页面，然后是另外 16K 个页面。这种情况下，node_spanned_pages 就是 33K 个页面，node_present_pages 就是 32K 个页面。

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;
    wait_queue_head_t kswapd_wait;
    wait_queue_head_t pfmemalloc_wait;
    struct task_struct *kswapd; /* Protected by mem_hotplug_begin/end() */
    int kswapd_order;
    enum zone_type kswapd_classzone_idx;
    int kswapd_failures;        /* Number of 'reclaimed == 0' runs */
......
} pg_data_t;

（3）节点数组

整个内存被分成了多个节点，多个 pglist_data 放在一个数组里面。每个节点一项，就像下面代码里面一样：

1	`struct pglist_data *node_data[MAX_NUMNODES] __read_mostly;`

区域

区域是针对物理内存的。

（1）概念

每一个节点分成多个区域 zone，放在数组 node_zones 里面。这个数组的大小为 MAX_NR_ZONES。

（2）区域的类型

区域的类型有如下几种，在上面描述 32 位内核态布局时，在高端内存部分已简单提过，这里详细说明。

ZONE_DMA：指可用于作 DMA（Direct Memory Access，直接内存存取）的内存。DMA 是这样一种机制：要把外设的数据读入内存或把内存的数据传送到外设，原来都要通过 CPU 控制完成，但是这会占用 CPU，影响 CPU 处理其他事情，所以有了 DMA 模式。CPU 只需向 DMA 控制器下达指令，让 DMA 控制器来处理数据的传送，数据传送完毕再把信息反馈给 CPU，这样就可以解放 CPU。
ZONE_DMA32：对于 64 位系统，有两个 DMA 区域。除了上面说的 ZONE_DMA，还有ZONE_DMA32。
ZONE_NORMAL：直接映射区，在上文 32 位内核态布局这部分有提到过，从物理内存到虚拟内存的内核区域，通过加上一个常量直接映射。
ZONE_HIGHMEM：高端内存区，对于 32 位系统来说超过 896M 的地方，对于 64 位没必要有的一段区域。
ZONE_MOVABLE：可移动区域，通过将物理内存划分为可移动分配区域和不可移动分配区域来避免内存碎片。

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

（3）区域的数据结构

区域的实现数据结构为zone。

zone_start_pfn：在一个 zone 里面，zone_start_pfn 表示属于这个 zone 的第一个页。
spanned_pages：区域总共跨多少页。代码注释中有描述，spanned_pages = zone_end_pfn - zone_start_pfn，也即 spanned_pages 指的是不管中间有没有物理内存空洞，反正就是最后的页号减去起始的页号。
present_pages：区域在物理内存中真实存在的页数。代码注释中有描述，present_pages = spanned_pages - absent_pages(pages in holes)，区域总共跨多少页减去物理空洞，得到区域中真实的页。
managed_pages：区域被伙伴系统管理的所有页数。代码注释中有描述，managed_pages present_pages - reserved_pages。
per_cpu_pageset：用于区分冷热页。如果一个页被加载到 CPU 高速缓存里面，这就是一个热页（Hot Page），CPU 读起来速度会快很多，如果没有就是冷页（Cold Page）。由于每个 CPU 都有自己的高速缓存，因而 per_cpu_pageset 也是每个 CPU 一个。

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_

页

（1）概念

页是组成物理内存的基本单位。

（2）数据结构

页的数据结构是 struct page。这是一个很复杂的结构，里面使用了很多的 union 联合体。union 结构是在 C 语言中被用于同一块内存根据情况保存不同类型数据的一种方式。之所以用了 union，是因为一个物理页面使用模式有多种。

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

5.5 物理页的两种使用模式

物理页的使用方式不同，union 中也会使用不同的变量。

第一种模式：要用就用一整页

（1）概念

这一整页的内存，或者直接和虚拟地址空间建立映射关系，我们把这种称为匿名页（Anonymous Page）。或者用于关联一个文件，然后再和虚拟地址空间建立映射关系，这样的文件，我们称为内存映射文件（Memory-mapped File）。

（2）数据结构

如果某一页是这种使用模式，struct page 会使用 union 中的以下变量：

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

第二种模式：仅需分配小块内存

目前内核中有三种方式来实现小块内存分配：slab, slub, slob。最先有 slab 分配器，slub/slob 分配器是改进版，slob 分配器适用于小内存嵌入式设备，而 slub 分配器目前已逐渐成为主流块分配器。

有时候，我们不需要一下子分配这么多的内存，例如分配一个 task_struct 结构，只需要分配小块的内存，去存储这个进程描述结构的对象。

（1）slab

为了满足对这种小内存块的需要，Linux 系统采用了一种被称为 slab allocator 的技术，用于分配称为 slab 的一小块内存。它的基本原理是从内存管理模块申请一整块页，然后划分成多个小块的存储池，用复杂的队列来维护这些小块的状态（状态包括：被分配了 / 被放回池子 / 应该被回收）。

如果某一页是用于分割成一小块一小块的内存进行分配的使用模式，则会使用 union 中的以下变量：

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

（2）slub

正是因为 slab allocator 对于队列的维护过于复杂，后来就有了一种不使用队列的分配器 slub allocator，后面我们会解析这个分配器。

（3）slob

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

6.物理内存管理之页的分配

6.1 伙伴系统

对于要分配比较大的内存，分配页级别的，可以使用伙伴系统（Buddy System）。伙伴系统在学习笔记｜操作系统中有形象的描述过。

6.1.1 特点

Linux 中的内存管理的“页”大小为 4KB。
把所有的空闲页分组为 11 个页块链表，每个块链表分别包含很多个大小的页块，有 1、2、4、8、16、32、64、128、256、512、1024 个连续页的页块。最大可以申请 1024 个连续页，对应 4MB 大小的连续内存。
每个页块的第一个页的物理地址是该页块大小的整数倍。
第 i 个页块链表中，每个页块中页的数目为 2^i。

在 struct zone 里面有定义了 struct free_area 类型的数组。

1	`struct free_area free_area[MAX_ORDER];`

上面代码中，MAX_ORDER 是 11，表示最大可以申请到 2^(11-1) = 1024 个连续页。在 free_area[10] 所指向的页块链表中，页块都是由 1024 个连续页组成的。

1	`#define MAX_ORDER 11`

6.1.2 分配方式

当向内核请求分配 (2^(i-1)，2^i] 数目的页块时，按照 2^i 页块请求处理。
如果对应的页块链表中没有空闲页块，那我们就在更大的页块链表中去找。
当分配的页块中有多余的页时，伙伴系统会根据多余的页块大小插入到对应的空闲页块链表中。
例如：要请求一个 128 个页的页块时，先检查 128 个页的页块链表是否有空闲块。如果没有，则查 256 个页的页块链表；如果有空闲块的话，则将 256 个页的页块分成两份，一份使用，一份插入 128 个页的页块链表中。如果还是没有，就查 512 个页的页块链表；如果有的话，就分裂为 128、128、256 三个页块，一个 128 的使用，剩余两个插入对应页块链表。

上面这个过程，我们可以在分配页的函数 alloc_pages 中看到。

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

（1）首先， alloc_pages 会调用 alloc_pages_current，alloc_pages_current 的参数的注释很详细。参数 order，表示分配 2 的 order 次方个页；参数 gfp 表示希望在哪个区域中分配这个内存：

GFP_USER 用于分配一个页映射到用户进程的虚拟地址空间，并且希望直接被内核或者硬件访问，主要用于一个用户进程希望通过内存映射的方式，访问某些硬件的缓存，例如显卡缓存。
GFP_KERNEL 用于内核中分配页，主要分配 ZONE_NORMAL 区域，即直接映射区。
GFP_HIGHMEM，顾名思义就是主要分配高端区域的内存。

**（2）接下来，**调用 __alloc_pages_nodemask。这是伙伴系统的核心方法。

它会调用 get_page_from_freelist。这里面的逻辑就是，在一个循环中先看当前节点的 zone。如果找不到空闲页，则再看备用节点的 zone。每一个 zone，都有伙伴系统维护的各种大小的队列，就像上面伙伴系统原理里讲的那样。
get_page_from_freelist 最后调用 rmqueue 就是找到合适大小的那个队列，把页面取下来。

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

**（3）最后，**进入 rmqueue 的调用链：rmqueue->__rmqueue->__rmqueue_smallest。在这里可以看到伙伴系统的逻辑。

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

从当前的 order，也即指数开始，在伙伴系统的 free_area 找 2^order 大小的页块。
如果链表的第一个不为空，就找到了；如果为空，就到更大的 order 的页块链表里面去找。
找到以后，将页块从链表中取下来，当前页块链表的空闲空间 nr_free 计时减 1。
除此之外，我们还要把多余的的部分放到其他页块链表里面。

__rmqueue_smallest 最后调用 expand就是将多余的的部分放到其他页块链表里面。

area-- 就是伙伴系统那个表里面的前一项。
前一项里面的页块大小是当前项的页块大小除以 2，size 右移一位也就是除以 2。
list_add 就是加到链表上，nr_free++ 就是计数加 1。

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

6.1.3 一张图总结

如果有多个 CPU，那就有多个节点。每个节点用 struct pglist_data 表示，放在一个数组里面。
每个节点分为多个区域，每个区域用 struct zone 表示，也放在一个数组里面。
每个区域分为多个页。为了方便分配，空闲页放在 struct free_area 里面，使用伙伴系统进行管理和分配，每一页用 struct page 表示。

6.2 Slub allocator

除了整页分配，对于小内存的分配，会使用 slub 分配器。在上文中提到 slub 分配器目前是主流块分配器，下面具体来看一下 slub 的工作原理。

这篇文章 slub 算法写的非常清晰形象，下面的图片都来自于这篇文章。

6.2.1 基本框架

一切源于 kmalloc_caches[12] 这个数组，该数组的定义如下：

1	`struct kmem_cache kmalloc_caches[PAGE_SHIFT] __cacheline_aligned;`

kmalloc_caches[12] 这个数组中有 12 个 kmem_cache 结构体，每个结构体负责分配一种大小的内存，分别是 2^3、2^4、…2^11个字节，另外还有两个特殊的组，分别是 96B 和 192B，共11组。

比如进程创建时，需要创建 task_struct、mm_struct、fs_struct 等不同大小的小内存块，就可以使用对应大小的 kmem_cache 来分配。

kmalloc_caches 用于管理 slab 缓存。slab 缓存包含多个 slab 页面，一个 slab 页面包含多个页，并将这块内存划分成大小相同的对象 object。

kmalloc_caches 中有两个结构体 kmem_cache_cpu 和 kmem_cache_node，每个NUMA节点都对应一个，分别是缓存分配的fast path和slow path。

struct kmem_cache_cpu：用于管理每个 CPU 的 slab 页面，可以使用无锁访问，提高缓存对象分配速度。kmem_cache_cpu 中只保留 1 个 slab 页面。
struct kmem_cache_node：用于管理每个 Node 的 slab 页面，由于每个 Node 的访问速度不一致，slab 页面由 Node 来管理。

下图是整个 slub 系统的框图：

6.2.2 object 的数据结构

一个物理页被划分成多个 object，多个空闲 object 形成一个链表，如图，object_size 表示某内存块的大小，size 表示该内存块加上指针的总大小，offset表示下一个空闲内存块的指针的偏移量。

上图是指针外置的方式，实际上还有指针内置的方式。在可用内存块中，使用前 8 个字节储存指针变量。因为当这块内存被分配出去后，当前 object 就会从空闲链表里删除，就无需保留指针。

6.2.3 分配过程

每个NUMA节点都有一个 kmem_cache_cpu、kmem_cache_node，分别是缓存分配的fast path和slow path。

每次分配的时候，要先从 kmem_cache_cpu 进行分配。如果 kmem_cache_cpu 里面没有空闲的块，那就到 kmem_cache_node 中进行分配；如果还是没有空闲的块，才去伙伴系统分配新的页。

（1）第一次分配

slub 系统刚刚创建出来，kmem_cache_cpu 和 kmem_cache_node 没有 slab 页面可以用来分配。
只能向伙伴系统申请一个或多个 page，并将其分成多个 object。
取出一个 object 返回给进程，其余的标记为空闲放入 kmem_cache_cpu 的一个 slab 页面中保存。
kmem_cache_cpu 的 freelist 变量保存着下一个空闲 objetc 的地址。

（2） kmem_cache_cpu 保存的 slab 页面中有空闲的 object。

这种最简单，直接将 kmem_cache_cpu 中 slab 页面的空闲 object 返回给进程。freelist 指向下一个空闲的 object。

（3） kmem_cache_cpu 中没有空闲的 object，但 kmem_cache_node 的 partial 中有空闲的 object。

kmem_cache_node 中有多个 slab 页面。其中 full 指向已经分配完毕的 slab 页面，partial 指向未分配完的 slab 页面。
kmem_cache_cpu 中无可用 slab 页面，则将这个用完的 slab 页面转移到 full 指向的链表下。
将 partial 的未分配完的 slab 页面转移到 kmem_cache_cpu 下。
kmem_cache_cpu 中找出空闲的 object 返回给进程。