一、内存管理

1. 每个进程应该有自己的内存空间。内存空间都是独立的、相互隔离的。对于每个进程来讲，看起来应该都是独占的。进程不能直接访问物理内存地址，因为假如三个程序同时访问或写入同一个物理内存地址，就会产生冲突或数据安全问题。

为了解决该问题，操作系统会给进程分配一个虚拟地址。所有进程看到的这个地址都是一样的，里面的内存都是从0开始编号。在程序里面，指令写入的地址是虚拟地址。操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。当程序要访问虚拟地址的时候，由内核的数据结构进行转换，转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了。

2. 操作系统的内存管理，主要分为三个方面：

（1）物理内存的管理，相当于会议室管理员管理会议室。物理内存地址只有内存管理模块能够使用；

（2）虚拟地址的管理，就像在项目组（进程）的视角，会议室的虚拟地址应该如何组织。每个进程看到的是独立的、互不干扰的虚拟地址空间；

（3）虚拟地址和物理地址如何映射，就像会议室管理员如和管理映射表。

关于如何规划内存空间，可以用下面的用户代码为例子：

#include <stdio.h>
#include <stdlib.h>

int max_length = 128;

char * generate(int length){
  int i;
  char * buffer = (char*) malloc (length+1);
  if (buffer == NULL)
    return NULL;
  for (i=0; i<length; i++){
    buffer[i]=rand()%26+'a';
  }
  buffer[length]='\0';
  return buffer;
}

int main(int argc, char *argv[])
{
  int num;
  char * buffer;

  printf ("Input the string length : ");
  scanf ("%d", &num);

  if(num > max_length){
    num = max_length;
  }

  buffer = generate(num);

  printf ("Random string is: %s\n",buffer);
  free (buffer);

  return 0;
}

这个程序就是根据用户输入的整数来生成字符串，最长是128。由于字符串的长度不是固定的，因而不能提前知道，需要动态地分配内存，使用malloc函数。当然用完了需要释放内存，这就要使用free函数。这个简单的程序在使用内存时有以下几种方式：

（1）代码需要放在内存里面；

（2）全局变量例如max_length；

（3）常量字符串"Input the string length : "；

（4）函数栈，例如局部变量num是作为参数传给generate函数的，这里面涉及了函数调用、局部变量、函数参数等，都是保存在函数栈上面的；

（5）堆，malloc分配的内存在堆里面；

（6）这里还涉及对glibc的调用，所以glibc的代码是以so文件的形式存在的，也需要放在内存里。

其中malloc会调用系统调用，进入内核，所以这个程序一旦运行起来，内核部分还需要分配内存：

（1）内核的代码要在内存里面；

（2）内核中也有全局变量；

（3）每个进程都要有一个task_struct；

（4）每个进程还有一个内核栈；

（5）在内核里面也有动态分配的内存；

（6）虚拟地址到物理地址的映射表。

3. 对于内存的访问，用户态的进程使用虚拟地址，内核态的也基本都是使用虚拟地址（对内存空间进行统一控制），只有虚拟地址到物理地址的映射表容易让人产生疑问，这个感觉起来是内存管理模块的一部分，这个是“实”是“虚”呢？这个问题会放到内存映射的部分见分晓。

既然都是虚拟地址，就先不管映射到物理地址以后是如何布局的，反正现在至少从“虚”的角度来看，这一大片连续的内存空间都是进程自己的了。如果是32位，有2^32 = 4G的内存空间，不管内存是不是真的有4G。如果是64位系统，在x86_64下面其实只使用了48位，48位地址长度也对应了256TB的内存地址空间。

首先这么大的虚拟空间一分为二，一部分用来放内核的东西，称为内核空间，一部分用来放进程的东西，称为用户空间。用户空间在下，在低地址，假设就是0号到29号会议室；内核空间在上，在高地址，假设是30号到39号会议室。这两部分空间的分界线因为32位和64位的不同而不同，这里暂不深究。对于普通进程来说，内核空间的那部分虽然虚拟地址就在那里，但是不能访问，示意图如下所示：

从最低位开始排起，先是Text Segment、Data Segment和BSS Segment。Text Segment是存放二进制可执行代码的位置，Data Segment存放静态常量，BSS Segment存放未初始化的静态变量。之前讲ELF格式的时候提到过，在二进制执行文件里就有这三个部分，这里就是把二进制执行文件的三个部分加载到内存里面。接下来是堆（Heap）段，堆是往高地址增长的，是用来动态分配内存的区域，malloc就是在这里面分配的。接下来的区域是Memory Mapping Segment，这块地址可以用来把文件映射进内存里用，如果二进制执行文件依赖于某个动态链接库，就是在这个区域里面将so文件映射到内存中。再下面就是栈（Stack）地址段，主线程的函数调用的函数栈就是用这里的。如果普通进程还想进一步访问内核空间，是没办法的，如果需要进行更高权限的工作，就需要调用系统调用，进入内核。

一旦进入了内核，就换了一副视角。刚才是普通进程的视角，觉得整个空间是它独占的，没有其他进程存在。当然另一个进程也这样认为，因为它们互相看不到对方。也就是说，不同进程的0号到29号会议室放的东西都不一样。但是到了内核里面，无论是从哪个进程进来的，看到的都是同一个内核空间，看到的都是同一个进程列表。虽然内核栈是各用各的，但是如果想知道的话，还是能够知道每个进程的内核栈在哪里的。所以如果要访问一些公共的数据结构，需要进行锁保护。也就是说不同的进程进入到内核后，进入的30号到39号会议室是同一批会议室，如下所示：

内核代码访问内核的数据结构，大部分的情况下都是使用虚拟地址的，虽然内核代码权限很大，但是能够使用的虚拟地址范围也只能在内核空间，也即内核代码访问内核数据结构。只能用例如30号到39号这些编号，不能用用户态的0到29号，因为这些是被进程空间占用的。而且进程有很多个，内核不知道当前指的0号地址是哪个进程的0号地址。在内核里面也会有内核的代码，同样有Text Segment、Data Segment和BSS Segment，内核启动的时候，内核代码也是ELF格式的。

4. 规划虚拟内存空间的时候，也是将空间分成多个段进行保存。分段机制的原理如下所示：

分段机制下的虚拟地址由两部分组成，段选择子和段内偏移量。段选择子就保存在之前提到的段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。虚拟地址中的段内偏移量应该位于0和段界限之间。如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。例如将上面的虚拟空间分成以下4个段，用0～3来编号。每个段在段表中有一个项，在物理空间中，段的排列如下图的右边所示：

例如要访问段2中偏移量600的虚拟地址，可以计算出物理地址为：段2基地址2000 + 偏移量600 = 2600。来看看Linux是如何使用这个机制的，在Linux里面段表全称段描述符表（segment descriptors），放在全局描述符表GDT（Global Descriptor Table）里面，会有下面的宏来初始化段描述符表里面的表项：

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

一个段表项由段基地址base、段界限limit，还有一些标识符组成，如下所示：

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

这里面对于64位的和32位的，都定义了内核代码段、内核数据段、用户代码段和用户数据段。另外，还会定义下面四个段选择子，指向上面的段描述符表项，在内核初始化的时候，启动第一个用户态的进程（1号进程），就是将这四个值赋值给段寄存器：

#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)

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

5. 其实Linux倾向于另外一种从虚拟地址到物理地址的转换方式，称为分页（Paging）。对于物理内存，操作系统把它分成一块一块大小相同的页，这样更方便管理，例如有的内存页面长时间不用了，可以暂时写到硬盘上，称为换出。一旦需要的时候，再加载进来，叫作换入。这样可以扩大可用物理内存的大小，提高物理内存的利用率。换入和换出都是以页为单位的，页的大小一般为4KB。为了能够定位和访问每个页，需要有个页表，保存每个页的起始地址，再加上在页内的偏移量，组成线性地址，就能对于内存中的每个位置进行访问了，如下所示：

虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址。这个基地址与页内偏移的组合就形成了物理内存地址。下面的图举了一个简单页表的例子，虚拟内存中的页通过页表映射为了物理内存中的页：

32位环境下，虚拟地址空间共4GB。如果分成4KB一个页，那就是1M个页。每个页表项需要4个字节来存储，那么整个4GB空间的映射就需要4MB的内存来存储映射表。如果每个进程都有自己的映射表，100个进程就需要400MB的内存。对于内核来讲有点大了。为什么会这么大呢？因为页表中所有页表项必须提前建好，并且要求是连续的，因为它是一个数组。如果不连续不是数组，就没有办法通过虚拟地址里面的页号，直接找到对应的页表项了。

那怎么办呢？可以采用多级页表的方式，试着将页表再分页，4G的空间需要4M的页表来存储映射，把这4M分成1K（1024）个4K，每个4K又能放在一页里面，这样1K个4K就是1K个页，这1K个页也需要一个表进行管理，称为页目录表，这个页目录表里面有1K项，每项4个字节，页目录表占空间大小也是4K。页目录表的1K项里每一项都代表一个页表的地址。

页目录里有1K项，用10位（1024=2^10）就可以表示访问页目录里的某一项，这一项其实对应的是某个页表的索引，也即4K个实际存放数据的页所在的页表的地址。每个页表的项也是4个字节（页表里的项就是一个实际的页的起始地址），因而整个页表的页表项也是1K个，再用10位就可以访问到页表里的某一项，页表项中的一项对应的就是一个实际页，即存放数据的页，这个页的大小也是4K，最后用12位（1024*4=2^12）偏移位就可以定位到这个实际页范围内的任何一个位置，如下所示：

如果这样的话，映射4GB地址空间就需要4MB+4KB的内存，这样不是更大了吗？当然如果所有页都是满的，确实是更大了，但是系统往往不会为一个进程分配那么多内存。比如说上面图中，假设只给这个进程分配了一个数据页，如果只使用页表，也需要完整的1M个页表项共4M的内存，但是如果使用了页目录，页目录需要1K个目录项全部分配，才会占用内存4K，但是里面通常只有一个目录项被使用了。到了页表，只需要分配能够管理那个数据页的内存就可以了，也就是说最多4K+4K，这样内存就节省多了。

当然对于64位的系统，两级肯定不够了，就变成了四级目录，分别是全局页目录项PGD（Page Global Directory）、上层页目录项PUD（Page Upper Directory）、中间页目录项PMD（Page Middle Directory）和页表项PTE（Page Table Entry），如下所示：

6. 因此，可以把内存管理系统精细化为下面三件事情：

（1）虚拟内存空间的管理，将虚拟内存分成大小相等的页；

（2）物理内存的管理，将物理内存分成大小相等的页；

（3）内存映射，将虚拟内存也和物理内存也映射起来，并且在内存紧张的时候可以换出到硬盘中。示意图如下所示：

二、进程空间管理

7. 来详细看看上面三个方面中的第一个方面，进程的虚拟内存空间是如何管理的。进程的虚拟地址空间，其实就是站在项目组的角度来看内存，所以就从task_struct出发来看，这里面有一个struct mm_struct结构来管理内存：

struct mm_struct    *mm;

在struct mm_struct里面，有这样一个成员变量：

unsigned long task_size;    /* size of task vm space */

之前提到，整个虚拟内存空间要一分为二，一部分是用户态地址空间，一部分是内核态地址空间，那这两部分的分界线在哪里呢？这就要task_size来定义。对于32位的系统，内核里面是这样定义TASK_SIZE的：

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

可以看到“User space process size: 3GB”，即对于32位系统，最大能够寻址2^32=4G，其中用户态虚拟地址空间是3G，内核态是1G。对64位系统来说，有“User space process size. 47bits minus one guard page.”这是什么意思呢？当执行一个新的进程的时候，会做以下的设置：

current->mm->task_size = TASK_SIZE;

对于64位系统，虚拟地址只使用了48位。就像代码里写的一样，1左移了47位，就相当于48位地址空间一半的位置0x0000800000000000，然后减去一个页，就是0x00007FFFFFFFF000，共128T。同样，内核空间也是128T。内核空间和用户空间之间隔着很大的空隙，以此来进行隔离。如下所示：

8. 先来看用户态虚拟空间的布局。之前提到用户态虚拟空间里面有几类数据，例如代码、全局变量、堆、栈、内存映射区等。在struct mm_struct里面，有下面这些变量定义了这些区域的统计信息和位置：

unsigned long mmap_base;  /* base of mmap area */
unsigned long total_vm;    /* Total pages mapped */
unsigned long locked_vm;  /* Pages that have PG_mlocked set */
unsigned long 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 */
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;

其中，total_vm是总共映射的页的数目。这么大的虚拟地址空间，不可能都有真实内存对应，所以这里是映射的数目。当内存吃紧的时候，有些页可以换出到硬盘上，有的页因为比较重要，不能换出。locked_vm就是被锁定不能换出，pinned_vm是不能换出也不能移动。data_vm是存放数据的页的数目，exec_vm是存放可执行文件的页的数目，stack_vm是栈所占的页的数目。start_code和end_code表示可执行代码的开始和结束位置，start_data和end_data表示已初始化数据的开始位置和结束位置。

start_brk是堆的起始位置，brk是堆当前的结束位置。前面提过malloc申请一小块内存，就是通过改变brk位置实现的。start_stack是栈的起始位置，栈的结束位置不在成员变量中，而在寄存器的栈顶指针中。arg_start和arg_end是参数列表的位置， env_start和env_end是环境变量的位置。它们都位于栈中最高地址的地方。mmap_base表示虚拟地址空间中用于内存映射的起始地址，一般情况下，这个空间是从高地址到低地址增长的。前面提到malloc申请一大块内存的时候，就是通过mmap在这里映射一块区域到物理内存，加载动态链接库so文件，也是在这个区域里面，映射一块区域到so文件。

这下所有用户态的区域的位置基本上都描述清楚了。整个布局就像下面这张图这样，虽然32位和64位的空间相差很大，但是区域的类别和布局是相似的：

9. 除了位置信息之外，struct mm_struct里面还专门有一个结构vm_area_struct来描述这些区域的属性，如下所示：

struct vm_area_struct *mmap;    /* list of VMAs */
struct rb_root mm_rb;

这里面一个是单链表，用于将这些区域串起来。另外还有一个红黑树。在进程调度的时候用的也是红黑树，它的好处就是查找和修改都很快。这里用红黑树就是为了快速查找一个内存区域，并在需要改变的时候，能够快速修改。 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将这个区域串在链表上。vm_rb将这个区域放在红黑树上。vm_ops里面是对这个内存区域可以做的操作的定义。虚拟内存区域可以映射到物理内存，也可以映射到文件，映射到物理内存的时候称为匿名映射，anon_vma中anoy就是anonymous，映射到文件就需要有vm_file指定被映射的文件。

那这些vm_area_struct是如何和上面的内存区域关联的呢？这个事情是在load_elf_binary里面实现的，加载内核的是它，启动第一个用户态进程init的是它，fork完了以后调用exec运行一个二进制程序的也是它。当exec运行一个二进制程序的时候，除了解析ELF的格式之外，另外一个重要的事情就是建立内存映射，如下所示：

static int load_elf_binary(struct linux_binprm *bprm)
{
......
  setup_new_exec(bprm);
......
  retval = setup_arg_pages(bprm, randomize_stack_top(STACK_TOP),
         executable_stack);
......
  error = elf_map(bprm->file, load_bias + vaddr, elf_ppnt,
        elf_prot, elf_flags, total_size);
......
  retval = set_brk(elf_bss, elf_brk, bss_prot);
......
  elf_entry = load_elf_interp(&loc->interp_elf_ex,
              interpreter,
              &interp_map_addr,
              load_bias, interp_elf_phdata);
......
  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;
......
}

load_elf_binary会完成以下的事情：

（1）调用setup_new_exec，设置内存映射区mmap_base；

（2）调用setup_arg_pages，设置栈的vm_area_struct，这里面设置了mm->arg_start是指向栈底的，current->mm->start_stack就是栈底；

（3）elf_map会将ELF文件中的代码部分映射到内存中来；

（4）set_brk设置了堆的vm_area_struct，这里面设置了current->mm->start_brk = current->mm->brk，也即堆里面还是空的；

（5）load_elf_interp将依赖的so映射到内存中的内存映射区域。

最终就形成下面这个内存映射图：

10. 映射完毕后，什么情况下会修改呢？第一种情况是函数的调用，涉及函数栈的改变，主要是改变栈顶指针。第二种情况是通过malloc申请一个堆内的空间，当然底层要么执行brk，要么执行mmap。关于内存映射的部分后面再说，这里重点看一下brk是怎么做的。brk系统调用实现的入口是sys_brk函数，如下所示：

SYSCALL_DEFINE1(brk, unsigned long, brk)
{
  unsigned long retval;
  unsigned long newbrk, oldbrk;
  struct mm_struct *mm = current->mm;
  struct vm_area_struct *next;
......
  newbrk = PAGE_ALIGN(brk);
  oldbrk = PAGE_ALIGN(mm->brk);
  if (oldbrk == newbrk)
    goto set_brk;


  /* Always allow shrinking brk. */
  if (brk <= mm->brk) {
    if (!do_munmap(mm, newbrk, oldbrk-newbrk, &uf))
      goto set_brk;
    goto out;
  }


  /* Check against existing mmap mappings. */
  next = find_vma(mm, oldbrk);
  if (next && newbrk + PAGE_SIZE > vm_start_gap(next))
    goto out;


  /* Ok, looks good - let it rip. */
  if (do_brk(oldbrk, newbrk-oldbrk, &uf) < 0)
    goto out;


set_brk:
  mm->brk = brk;
......
  return brk;
out:
  retval = mm->brk;
  return retval

前面提过，堆是从低地址向高地址增长的，sys_brk函数的参数brk是新的堆顶位置，而当前的mm->brk是原来堆顶的位置。首先要做的第一个事情，将原来的堆顶和现在的堆顶，都按照页对齐地址，然后比较两者大小，如果两者相同说明这次增加的堆的量很小，还在一个页里面，不需要另行分配页，直接跳到set_brk那里，设置mm->brk为新的brk就可以了。

如果发现新旧堆顶不在一个页里面，就要跨页了。如果发现新堆顶小于旧堆顶，这说明不是新分配内存了，而是释放内存了，至少释放了一页，于是调用do_munmap将这一页的内存映射去掉。如果堆将要扩大，就要调用find_vma，如果打开这个函数，看到的是对红黑树的查找，找到的是原堆顶所在的vm_area_struct的下一个vm_area_struct，看当前的堆顶和下一个vm_area_struct之间还能不能分配一个完整的页。如果不能，只好直接退出返回，内存空间都被占满了。

如果还有空间，就调用do_brk进一步分配堆空间，从旧堆顶开始，分配计算出的新旧堆顶之间的页数，如下所示：

static int do_brk(unsigned long addr, unsigned long len, struct list_head *uf)
{
  return do_brk_flags(addr, len, 0, uf);
}


static int do_brk_flags(unsigned long addr, unsigned long request, unsigned long flags, struct list_head *uf)
{
  struct mm_struct *mm = current->mm;
  struct vm_area_struct *vma, *prev;
  unsigned long len;
  struct rb_node **rb_link, *rb_parent;
  pgoff_t pgoff = addr >> PAGE_SHIFT;
  int error;


  len = PAGE_ALIGN(request);
......
  find_vma_links(mm, addr, addr + len, &prev, &rb_link,
            &rb_parent);
......
  vma = vma_merge(mm, prev, addr, addr + len, flags,
      NULL, NULL, pgoff, NULL, NULL_VM_UFFD_CTX);
  if (vma)
    goto out;
......
  vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);
  INIT_LIST_HEAD(&vma->anon_vma_chain);
  vma->vm_mm = mm;
  vma->vm_start = addr;
  vma->vm_end = addr + len;
  vma->vm_pgoff = pgoff;
  vma->vm_flags = flags;
  vma->vm_page_prot = vm_get_page_prot(flags);
  vma_link(mm, vma, prev, rb_link, rb_parent);
out:
  perf_event_mmap(vma);
  mm->total_vm += len >> PAGE_SHIFT;
  mm->data_vm += len >> PAGE_SHIFT;
  if (flags & VM_LOCKED)
    mm->locked_vm += (len >> PAGE_SHIFT);
  vma->vm_flags |= VM_SOFTDIRTY;
  return 0;

在do_brk中，调用find_vma_links找到将来的vm_area_struct节点在红黑树的位置，找到它的父节点、前序节点。接下来调用vma_merge，看这个新节点是否能够和现有树中的节点合并。如果地址是连着的，能够合并，则不用创建新的vm_area_struct了，直接跳到out，更新统计值即可；如果不能合并，则创建新的vm_area_struct，既加到anon_vma_chain链表中，也加到红黑树中。

11. 上面用户态虚拟空间分析完毕，接下来分析内核态虚拟空间。内核态的虚拟空间和某一个进程没有关系，所有进程通过系统调用进入到内核之后，看到的虚拟地址空间都是一样的。这里强调一下，千万别以为到了内核里面，就会直接使用物理内存地址了，这里讨论的还是虚拟内存地址，但是由于内核总是涉及管理物理内存，因而总是隐隐约约发生关系，所以这里必须思路清晰，分清楚物理内存地址和虚拟内存地址。

在内核态，32位和64位的布局差别比较大，主要是因为32位内核态空间太小。来看32位的内核态的布局，如下所示：

32位系统的内核态虚拟地址空间一共就1G，占绝大部分的是前896M，称为直接映射区，就是这一块空间是连续的，和物理内存是非常简单的映射关系，其实就是虚拟内存地址减去3G，就得到物理内存的位置。在内核里面有两个宏：__pa(vaddr)返回与虚拟地址vaddr相关的物理地址；__va(paddr)则计算出对应于物理地址paddr的虚拟地址，如下所示：

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

但是要注意，这里虚拟地址和物理地址发生了关联关系，在物理内存的开始的896M的空间，会被直接映射到3G至3G+896M的虚拟地址，这样容易给一种感觉，是这些内存访问起来和物理内存差不多，并不是，在大部分情况下对于这一段内存的访问，在内核中还是会使用虚拟地址的，并且将来也会为这一段空间建设页表，对这段地址的访问也会走之前提到的分页地址的流程，只不过页表里面比较简单，是直接的一一对应而已。

这896M还需要仔细分解。在系统启动的时候，物理内存的前1M已经被占用了（实模式），从1M开始加载内核代码段，然后就是内核的全局变量、BSS 等，也是ELF里面涵盖的。这样内核的代码段、全局变量、BSS也就会被映射到3G后的虚拟地址空间里面。具体的物理内存布局可以查看/proc/iomem。

在内核运行的过程中，如果碰到系统调用创建进程，会创建task_struct这样的实例，内核的进程管理代码会将实例创建在3G至3G+896M的虚拟空间中，当然也会被放在物理内存里面的前896M里面，相应的页表也会被创建。在内核运行的过程中，还会涉及内核栈的分配，内核的进程管理的代码也会将内核栈创建在3G至3G+896M的虚拟空间中，当然也就会被放在物理内存里面的前896M里面，相应的页表也会被创建。

896M这个值在内核中被定义为high_memory，在此之上常称为“高端内存”。这是个很笼统的说法，到底是虚拟内存的3G+896M以上的是高端内存，还是物理内存896M以上的是高端内存呢？这里需要辨析一下，高端内存是物理内存的概念，它仅仅是内核中的内存管理模块看待物理内存的时候的概念。前面也提过，在内核中除了内存管理模块直接操作物理地址之外，内核的其他模块仍然要操作虚拟地址，而虚拟地址是需要内存管理模块分配和映射好的。

假设电脑有2G内存，如果内核的其他模块想要访问物理内存1.5G的地方，应该怎么办呢？首先不能使用物理地址，需要使用内存管理模块分配的虚拟地址，但是虚拟内存地址中的0到3G地址已经被用户态进程占用去了，作为内核不能使用。因为如果写物理1.5G的虚拟内存位置，一方面不知道应该根据哪个进程的页表进行映射；另一方面就算映射了也不是内核真正想访问的物理内存的地方，所以内核能够使用的虚拟内存地址，只剩下物理1G减去896M的空间了。

于是和上面的图一样，可以将剩下的虚拟内存地址分成下面这几个部分：

（1）在896M到VMALLOC_START之间有8M的空间。

（2）VMALLOC_START到VMALLOC_END之间称为内核动态映射空间，即内核如果想像用户态进程一样malloc申请内存，在内核里面可以使用vmalloc。假设物理内存里面，896M到1.5G之间已经被用户态进程占用了，并且映射关系放在了进程的页表中，内核vmalloc的时候，只能从物理内存1.5G的位置开始分配，就需要使用这一段的虚拟地址进行映射，映射关系放在专门给内核自己用的页表里面。

（3）PKMAP_BASE到FIXADDR_START的空间称为持久内核映射。使用alloc_pages()函数的时候，在物理内存的高端内存得到struct page结构，可以调用kmap将其在映射到这个区域。

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

（5）在最后一个区域可以通过kmap_atomic实现临时内核映射。假设用户态的进程要映射一个文件到内存中，先要映射用户态进程空间的一段虚拟地址到物理内存，然后将文件内容写入这个物理内存供用户态进程访问。给用户态进程分配物理内存页可以通过alloc_pages()。分配完毕后，按理说将用户态进程虚拟地址和物理内存的映射关系放在用户态进程的页表中，就完事了，这时用户态进程可以通过用户态的虚拟地址，经过页表映射后访问物理内存，应该不需要内核态的虚拟地址里面也划出一块来，也映射到这个物理内存页。但是如果要把文件内容写入物理内存，这件事情要内核来干，它也需要虚拟内存地址，就只好通过kmap_atomic做一个临时映射，通过临时划分的内核虚拟地址写入物理内存完毕后，再kunmap_atomic来解映射即可。

12. 接下来看64位的内核布局。其实64位的内核布局反而简单，因为虚拟空间实在是太大了，根本不需要所谓的高端内存，因为内核是128T。64位的内存布局如图所示：

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

（1）从0xffff800000000000开始就是内核的部分，只不过一开始有8T的空档区域。

（2）从__PAGE_OFFSET_BASE(0xffff880000000000)开始的64T的虚拟地址空间是直接映射区域，也就是减去PAGE_OFFSET就是物理地址。虚拟地址和物理地址之间的映射在大部分情况下还是会通过建立页表的方式进行映射。

（3）从VMALLOC_START（0xffffc90000000000）开始到VMALLOC_END（0xffffe90000000000）的32T空间是给vmalloc的。

（4）从VMEMMAP_START（0xffffea0000000000）开始的1T空间用于存放物理页面的描述结构struct page。

（5）从__START_KERNEL_map（0xffffffff80000000）开始的512M用于存放内核代码段、全局变量、BSS等。这里对应到物理内存开始的位置，减去 __START_KERNEL_map 就能得到物理内存的地址。这里和直接映射区有点像，但是不矛盾，因为直接映射区之前有8T的空当区域，早就过了内核代码在物理内存中加载的位置。

13. 一个进程要运行起来需要以下的内存结构：

（1）用户态：代码段、全局变量、BSS、函数栈、堆、内存映射区。

（2）内核态：内核的代码、全局变量、BSS、内核数据结构例如task_struct、内核栈、内核中动态分配的内存。

因此，总结一下进程运行状态在 32 位下对应关系如下：

对于64位的对应关系，只是稍有区别，如下所示：

三、物理内存管理

14. 由于物理地址是连续的，页也是连续的，每个页大小也是一样的，因而对于任何一个地址，只要直接除一下每页的大小，很容易直接算出在哪一页。每个页有一个结构struct page表示，这个结构也是放在一个数组里面，这样根据页号，很容易通过下标找到相应的struct page结构。如果是这样，整个物理内存的布局就非常简单、易管理，这就是最经典的平坦内存模型（Flat Memory Model）。CPU是通过总线去访问内存的，这就是最经典的内存使用方式，如下所示：

在这种模式下，CPU可能也会有多个，在总线的一侧。所有的内存条组成一大片内存，在总线的另一侧，所有的CPU访问内存都要过总线，而且距离都是一样的，这种模式称为SMP（Symmetric multiprocessing，对称多处理器）。当然，它也有一个显著的缺点，就是总线会成为瓶颈，因为数据都要经过它。如下所示：

为了提高性能和可扩展性，后来有了一种更高级的模式，NUMA（Non-uniform memory access，非一致内存访问）。在这种模式下，内存不是一整块，每个CPU都有自己的本地内存，CPU访问本地内存不用过总线，因而速度要快很多，每个CPU和内存在一起，称为一个NUMA节点。但是在本地内存不足的情况下，每个CPU都可以去另外的NUMA节点申请内存，这个时候访问延时就会比较长。

这样，内存被分成了多个节点，每个节点再被分成一个一个的页面。由于页需要全局唯一定位，页还是需要有全局唯一的页号的，但是由于物理内存不是连起来的了，页号也就不再连续了，于是内存模型变成了非连续内存模型，管理起来就复杂一些。需要指出的是，NUMA往往是非连续内存模型，而非连续内存模型不一定就是NUMA，有时候一大片内存的情况下，也会有物理内存地址不连续的情况。后来内存技术更强可以支持热插拔了，这个时候不连续成为常态，于是就有了稀疏内存模型。

15.当前的主流场景是NUMA方式，首先要有代码能够表示NUMA节点的概念，于是就有了下面这个结构typedef struct pglist_data pg_data_t：

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;

它里面有以下的成员变量：

（1）每一个节点都有自己的ID：node_id；

（2）node_mem_map就是这个节点的struct page数组，用于描述这个节点里面所有的页；

（3）node_start_pfn是这个节点的起始页号；

（4）node_spanned_pages是这个节点中包含不连续物理内存地址的总页数；

（5）node_present_pages是真正可用的物理页的数目。

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

每一个节点分成一个个区域zone，放在数组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影响它处理其他事情，所以有了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访问内存在本节点速度最快，但是如果本节点内存不够，还是需要去其他节点进行分配。既然整个内存被分成了多个节点，那pglist_data应该放在一个数组里面，每个节点一项，就像下面代码里一样：

struct pglist_data *node_data[MAX_NUMNODES] __read_mostly;

16. 到这里把内存分成了节点，把节点分成了区域。接下来看一个区域里是如何组织的。表示区域的数据结构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里面，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快速访问段描述符，在CPU里有段描述符缓存。CPU访问这个缓存的速度比内存快得多。同样对于页来讲，也是这样的。如果一个页被加载到CPU高速缓存里面，这就是一个热页（Hot Page），CPU读起来速度会快很多，如果没有就是冷页（Cold Page）。由于每个CPU都有自己的高速缓存，因而per_cpu_pageset也是每个CPU一个。

17. 接下来就到了组成物理内存的基本单位，页的数据结构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 */
      };
    ......
    }

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

第一种模式，要用就用一整页。这一整页的内存，或者直接和虚拟地址空间建立映射关系，这种称为匿名页（Anonymous Page），或者用于关联一个文件，然后再和虚拟地址空间建立映射关系，这样的文件称为内存映射文件（Memory-mapped File）。如果某一页是这种使用模式，则会使用union中的以下变量：

（1）struct address_space *mapping就是用于内存映射，如果是匿名页最低位为1；如果是映射文件最低位为0；

（2）pgoff_t index是在映射区的偏移量；

（3）atomic_t _mapcount，每个进程都有自己的页表，这里指有多少个页表项指向了这个页；

（4）struct list_head lru表示这一页应该在一个链表上，可能在不同链表上，例如这个页面被换出，就在换出页的链表中；

（5）compound相关的变量用于复合页（Compound Page），就是将物理上连续的两个或多个页看成一个独立的大页。

第二种模式，仅需分配小块内存。有时候不需要一下子分配这么多的内存，例如分配一个task_struct结构，只需要分配小块的内存，去存储这个进程描述结构的对象。为了满足对这种小内存块的需要，Linux系统采用了一种被称为slab allocator的技术，用于分配称为slab的一小块内存，基本原理是从内存管理模块申请一整块页，然后划分成多个小块的存储池，用复杂的队列来维护这些小块的状态，状态包括：被分配了、被放回池子、应该被回收等。

也正是因为slab allocator对于队列的维护过于复杂，后来就有了一种不使用队列的分配器slub allocator，后面再提这个分配器。但是看源码会发现，slub allocator里还是用了很多slab的字眼，因为它保留了slab的用户接口，可以看成slab allocator的另一种实现。还有一种小块内存的分配器称为slob，非常简单，主要使用在小型的嵌入式系统。

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

(1)s_mem是已经分配了正在使用的slab的第一个对象；

(2)freelist是池子中的空闲对象；

(3)rcu_head是需要释放的列表。

18. 前面讲到物理内存的组织，从节点到区域到页到小块。接下来看物理内存的分配。对于要分配比较大的内存，例如到分配页级别的，可以使用伙伴系统（Buddy System）。Linux中内存管理的页大小为4KB，把所有的空闲页分组为11个页块链表，每个页块链表分别包含多个页块，有1、2、4、8、16、32、64、128、256、512和1024个连续页的页块，即最大可以申请1024个连续页，对应4MB大小的连续内存。每个页块第一个页的物理地址是该页块大小的整数倍，如下图所示：

可以看到，第i个页块链表中，页块中页的数目为2^i。在struct zone里面有以下的定义：

struct free_area  free_area[MAX_ORDER];

free_are是一个数组，MAX_ORDER就是11即整数。

当向内核请求分配(2^(i-1)，2^i]数目的页块时，按照2^i页块请求处理。如果对应的页块链表中没有空闲页块，那就在更大的页块链表中去找。当分配的页块中有多余的页时，伙伴系统会根据多余的页块大小插入到对应的空闲页块链表中。例如要请求一个128个页的页块时，先检查128个页的页块链表是否有空闲块。如果没有则查256个页的页块链表；如果有空闲块的话，则将256个页的页块分成两份128页，一份被使用，一份插入到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;
}

alloc_pages会调用alloc_pages_current， gfp表示希望在哪个区域中分配这个内存：

（1）GFP_USER用于分配一个页映射到用户进程的虚拟地址空间，并且希望直接被内核或者硬件访问，主要用于一个用户进程希望通过内存映射的方式，访问某些硬件的缓存，例如显卡缓存；

（2）GFP_KERNEL用于内核中分配页，主要分配ZONE_NORMAL区域，也即直接映射区；

（3）GFP_HIGHMEM就是主要分配高端区域的内存。

上面这些区域，都是物理内存区域。另一个参数order，就是表示分配2的order次方个页。接下来调用__alloc_pages_nodemask，这是伙伴系统的核心方法，它会调用get_page_from_freelist，它的逻辑也很容易理解，就是在一个循环中先看当前节点的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_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的页块链表里面去找。找到以后，除了将页块从链表中取下来，还要把多余的的部分放到其他页块链表里面。expand就是干这个事情的，如下所示：

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

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

19. 物理内存的组织形式，就像下面图中所示，如果有多个CPU，那就有多个节点。每个节点用struct pglist_data表示，放在一个数组里面。每个节点分为多个区域，每个区域用struct zone表示，也放在一个数组里面。每个区域分为多个页，为了方便分配，空闲页放在struct free_area里面，使用伙伴系统进行管理和分配，每一页用struct page表示：

20. 上面提到了整页的分配机制。如果遇到小的对象，会使用slub分配器进行分配。创建进程的时候，会调用dup_task_struct，它想要试图复制一个task_struct对象，需要先调用alloc_task_struct_node，分配一个task_struct对象。从下面代码可以看出，它调用了kmem_cache_alloc_node函数，在task_struct的缓存区域task_struct_cachep分配了一块内存：

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

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

在系统初始化时，task_struct_cachep会被kmem_cache_create函数创建，这个函数专门用于分配task_struct对象的缓存，这个缓存区的名字就在引号里叫task_struct。缓存区中每一块的大小正好等于task_struct的大小，也就是 arch_task_struct_size。有了这个缓存区，每次创建task_struct时，不用到内存里面去分配，先在缓存里看看有没有直接可用的，这就是kmem_cache_alloc_node的作用。当一个进程结束，task_struct也不用直接被销毁，而是放回到缓存中，这就是kmem_cache_free的作用。这样新进程创建的时候，就可以直接用现成缓存中的task_struct了。

21.缓存区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 kmem_cache里面有个变量struct list_head list，对于操作系统来讲要创建和管理的缓存不止task_struct，mm_struct、fs_struct也需要缓存。因此，所有的缓存最后都会放在一个链表里面，也就是LIST_HEAD(slab_caches)。对于缓存来讲，其实就是分配了连续几页的大内存块，然后根据缓存对象的大小，切成小内存块，所以这里有三个kmem_cache_order_objects类型的变量。这里的order表示2的order次方个页的大内存块，objects指能够存放的缓存对象的数量。最终，将大内存块切分成小内存块，样子就像下面这样：

每一项的结构都是缓存对象后面跟一个下一个空闲对象的指针，这样非常方便将所有空闲对象链成一个链，这就相当用数组实现一个可随机插入和删除的链表。所以这里面有三个变量：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里面是如何存放缓存块的，如下所示：

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

在这里，page指向大内存块的第一个页，缓存块就是从里面分配的。freelist指向大内存块里面第一个空闲的项，按照上面注释，这一项会有指针指向下一个空闲的项，最终所有空闲的项会形成一个链表。partial指向的也是大内存块的第一个页，之所以叫partial（部分），是因为它里面部分被分配出去了，部分是空的，这是一个备用列表，当page满了，就会从这里找。再来看kmem_cache_node的定义，如下所示：

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

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

22. 下面来看看这个缓存块分配过程。kmem_cache_alloc_node会调用slab_alloc_node，先重点看这里面的注释，这里说的就是快速通道和普通通道的概念，如下所示：

/*
 * Inlined fastpath so that allocation functions (kmalloc, 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重新试下就可以了，因为大块空闲内存替换过去了。如果还不行，就要到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，开始在这个节点进行分配，如下所示：

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

acquire_slab会从kmem_cache_node的partial链表中拿下一大块内存来，并且将freelist也就是第一块空闲的缓存块，赋值给t。并且当第一轮循环的时候，将kmem_cache_cpu的page指向取下来的这一大块内存，返回的object就是这块内存里面的第一个缓存块 t。如果kmem_cache_cpu也有一个partial，就会进行第二轮，再次取下一大块内存来，这次调用put_cpu_partial，放到kmem_cache_cpu的partial里面。如果kmem_cache_node里也没有空闲的内存，这就说明原来分配的页里面都放满了，就要回到new_slab_objects函数，里面new_slab函数会调用allocate_slab。如下所示：

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

在这里看到了alloc_slab_page分配页面。分配的时候要按kmem_cache_order_objects里面的order来。如果第一次分配不成功，说明内存已经很紧张了，那就换成min版本的kmem_cache_order_objects。

23. 另一个物理内存管理必须要处理的事情就是，页面换出。每个进程都有自己的虚拟地址空间，无论是32位还是64位，虚拟地址空间都非常大，物理内存不可能有这么多的空间放得下。所以一般情况下，页面只有在被使用的时候，才会放在物理内存中。如果过了一段时间不被使用，即便用户进程并没有释放它，物理内存管理也有责任做一定的干预，例如将这些物理内存中的页面换出到硬盘上去；将空出的物理内存，交给活跃的进程去使用。

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

还有一种情况，是作为内存管理系统应该主动去做的，而不能等出了事儿再做，这就是内核线程kswapd。这个内核线程在系统初始化的时候就被创建，这样它会进入一个无限循环，直到系统停止。在这个循环中，如果内存使用没有那么紧张，那它就继续sleep；如果内存紧张了，就需要去检查一下内存，看看是否需要换出一些内存页。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);
      }
    }
......
  }
......

这里有个lru列表。从下面的定义可以想象，所有的页面都被挂在LRU（Least Recent Use，最近最少使用）列表中，也就是说这个列表里面会按照活跃程度进行排序，这样就容易把不怎么用的内存页拿出来做处理。内存页总共分两类，一类是匿名页，和虚拟地址空间进行关联；一类是内存映射，不但和虚拟地址空间关联，还和文件管理关联。它们每一类都有两个列表，一个是active一个是inactive，顾名思义，active就是比较活跃的，inactive就是不怎么活跃的。这两个里面的页会变化，过一段时间活跃的可能变为不活跃，不活跃的可能变为活跃。如果要换出内存，那就是从不活跃的列表中找出最不活跃的，换出到硬盘上。lru_list的实现如下所示：

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

从上面代码可以看出，shrink_list会先缩减活跃页面列表，再压缩不活跃的页面列表。对于不活跃列表的缩减，shrink_inactive_list就需要对页面进行回收；对于匿名页来讲，需要分配swap，将内存页写入文件系统；对于内存映射关联了文件的，需要将在内存中对于文件的修改写回到文件中。

24. 对于物理内存来讲，从下层到上层的关系及分配模式如下：

 

（1）物理内存分NUMA节点，分别进行管理；

（2）每个NUMA节点分成多个内存区域；

（3）每个内存区域分成多个物理页面；

（4）伙伴系统将多个连续的页面作为一个大的内存块分配给上层；

（5）kswapd负责物理页面的换入换出；Linux内存的换入和换出涉及swap分区；

（6）Slub Allocator将从伙伴系统申请的大内存块切成小块，分配给其他系统。

四、用户态内存映射

25. 之前既提到了虚拟内存空间是如何组织的，也看到了物理页是如何管理的。现在需要一些数据结构，将二者关联起来。每一个进程都有一个列表vm_area_struct，指向虚拟地址空间不同的内存块，这个变量的名字叫mmap，如下所示：

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


struct vm_area_struct {
  /*
   * For areas with an address space and backing store,
   * linkage into the address_space->i_mmap interval tree.
   */
  struct {
    struct rb_node rb;
    unsigned long rb_subtree_last;
  } shared;




  /*
   * A file's MAP_PRIVATE vma can be in both i_mmap tree and anon_vma
   * list, after a COW of one of the file pages.  A MAP_SHARED vma
   * can only be in the i_mmap tree.  An anonymous MAP_PRIVATE, stack
   * or brk vma (with NULL file) can only be in an anon_vma list.
   */
  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;
  /* Information about our backing store: */
  unsigned long vm_pgoff;    /* Offset (within vm_file) in PAGE_SIZE
             units */
  struct file * vm_file;    /* File we map to (can be NULL). */
  void * vm_private_data;    /* was vm_pte (shared mem) */

其实内存映射不仅仅是物理内存和虚拟内存之间的映射，还包括将文件中的内容映射到虚拟内存空间，这个时候访问内存空间就能够访问到文件里面的数据，而仅有物理内存和虚拟内存的映射，是一种特殊情况。如下图所示：

如果要申请小块内存，就用brk。如果申请一大块内存，就要用mmap。对于堆的申请来讲，mmap是映射内存空间到物理内存。另外，如果一个进程想映射一个文件到自己的虚拟内存空间，也要通过mmap系统调用，这个时候mmap是映射内存空间到物理内存再到文件。可见mmap这个系统调用是核心，现在来看mmap这个系统调用的实现：

SYSCALL_DEFINE6(mmap, unsigned long, addr, unsigned long, len,
                unsigned long, prot, unsigned long, flags,
                unsigned long, fd, unsigned long, off)
{
......
        error = sys_mmap_pgoff(addr, len, prot, flags, fd, off >> PAGE_SHIFT);
......
}


SYSCALL_DEFINE6(mmap_pgoff, unsigned long, addr, unsigned long, len,
    unsigned long, prot, unsigned long, flags,
    unsigned long, fd, unsigned long, pgoff)
{
  struct file *file = NULL;
......
  file = fget(fd);
......
  retval = vm_mmap_pgoff(file, addr, len, prot, flags, pgoff);
  return retval;
}

如果要映射到文件，fd会传进来一个文件描述符，并且mmap_pgoff里面通过fget函数，根据文件描述符获得struct file。struct file表示打开的一个文件。接下来的调用链是vm_mmap_pgoff->do_mmap_pgoff->do_mmap，这里面主要干了两件事情：

（1）调用get_unmapped_area找到一个没有映射的区域；

（2）调用mmap_region映射这个区域。

26. 先来看get_unmapped_area函数的实现，如下所示：

unsigned long
get_unmapped_area(struct file *file, unsigned long addr, unsigned long len,
    unsigned long pgoff, unsigned long flags)
{
  unsigned long (*get_area)(struct file *, unsigned long,
          unsigned long, unsigned long, unsigned long);
......
  get_area = current->mm->get_unmapped_area;
  if (file) {
    if (file->f_op->get_unmapped_area)
      get_area = file->f_op->get_unmapped_area;
  } 
......
}

这里面如果是匿名映射，则调用mm_struct里面的get_unmapped_area函数，这个函数其实是arch_get_unmapped_area，它会调用find_vma_prev，在表示虚拟内存区域的vm_area_struct红黑树上找到相应的位置。之所以这个变量叫prev，是说这个时候虚拟内存区域还没有建立，只能在红黑树找到前一个vm_area_struct。

如果不是匿名映射，而是映射到一个文件，这样在Linux里每个打开的文件都有一个struct file结构，里面有一个file_operations，用来表示和这个文件相关的操作。如果是ext4文件系统，调用的是thp_get_unmapped_area，如果仔细看这个函数，会发现最终还是调用mm_struct里的get_unmapped_area函数，和匿名映射殊途同归，如下所示：

const struct file_operations ext4_file_operations = {
......
        .mmap           = ext4_file_mmap
        .get_unmapped_area = thp_get_unmapped_area,
};


unsigned long __thp_get_unmapped_area(struct file *filp, unsigned long len,
                loff_t off, unsigned long flags, unsigned long size)
{
        unsigned long addr;
        loff_t off_end = off + len;
        loff_t off_align = round_up(off, size);
        unsigned long len_pad;
        len_pad = len + size;
......
        addr = current->mm->get_unmapped_area(filp, 0, len_pad,
                                              off >> PAGE_SHIFT, flags);
        addr += (off - addr) & (size - 1);
        return addr;
}

再来看mmap_region，看它如何映射这个虚拟内存区域，如下所示：

unsigned long mmap_region(struct file *file, unsigned long addr,
    unsigned long len, vm_flags_t vm_flags, unsigned long pgoff,
    struct list_head *uf)
{
  struct mm_struct *mm = current->mm;
  struct vm_area_struct *vma, *prev;
  struct rb_node **rb_link, *rb_parent;


  /*
   * Can we just expand an old mapping?
   */
  vma = vma_merge(mm, prev, addr, addr + len, vm_flags,
      NULL, file, pgoff, NULL, NULL_VM_UFFD_CTX);
  if (vma)
    goto out;


  /*
   * Determine the object being mapped and call the appropriate
   * specific mapper. the address has already been validated, but
   * not unmapped, but the maps are removed from the list.
   */
  vma = kmem_cache_zalloc(vm_area_cachep, GFP_KERNEL);
  if (!vma) {
    error = -ENOMEM;
    goto unacct_error;
  }


  vma->vm_mm = mm;
  vma->vm_start = addr;
  vma->vm_end = addr + len;
  vma->vm_flags = vm_flags;
  vma->vm_page_prot = vm_get_page_prot(vm_flags);
  vma->vm_pgoff = pgoff;
  INIT_LIST_HEAD(&vma->anon_vma_chain);


  if (file) {
    vma->vm_file = get_file(file);
    error = call_mmap(file, vma);
    addr = vma->vm_start;
    vm_flags = vma->vm_flags;
  } 
......
  vma_link(mm, vma, prev, rb_link, rb_parent);
  return addr;
.....

上面刚找到了虚拟内存区域的前一个vm_area_struct，首先要看新的区域是否能基于前一个区域进行扩展，也即调用vma_merge，看是否能和前一个vm_area_struct合并到一起。如果能就不用重新创建了，如果不能就需要调用kmem_cache_zalloc，在Slub里创建一个新的vm_area_struct对象，设置起始和结束位置，将它加入队列。如果是映射到文件，则设置vm_file为目标文件，调用call_mmap，其实就是调用file_operations的mmap函数，对于ext4文件系统调用的是ext4_file_mmap。从这个函数的参数可以看出，这一刻文件和内存开始发生关系了。这里将vm_area_struct的内存操作设置为文件系统操作，也就是说，此时读写内存其实就是读写文件系统。call_mmap和ext4_file_mmap的实现如下所示：

static inline int call_mmap(struct file *file, struct vm_area_struct *vma)
{
  return file->f_op->mmap(file, vma);
}


static int ext4_file_mmap(struct file *file, struct vm_area_struct *vma)
{
......
      vma->vm_ops = &ext4_file_vm_ops;
......
}

再回到mmap_region函数。最终，vma_link函数将新创建的vm_area_struct挂在了mm_struct里面的红黑树上，这时从内存到文件的映射关系，至少在逻辑层面建立起来了。那从文件到内存的映射关系呢？vma_link还做了另外一件事情，就是__vma_link_file，它用于建立反向的这层映射关系。对于打开的文件，会有一个结构struct file来表示，它有个成员指向struct address_space结构，这里面有棵变量名为i_mmap的红黑树，vm_area_struct就挂在这棵树上，如下所示：

struct address_space {
  struct inode    *host;    /* owner: inode, block_device */
......
  struct rb_root    i_mmap;    /* tree of private and shared mappings */
......
  const struct address_space_operations *a_ops;  /* methods */
......
}


static void __vma_link_file(struct vm_area_struct *vma)
{
  struct file *file;


  file = vma->vm_file;
  if (file) {
    struct address_space *mapping = file->f_mapping;
    vma_interval_tree_insert(vma, &mapping->i_mmap);
  }

到这里，虚拟内存映射就告一段落了，但好像还没和物理内存发生任何关系，还在虚拟内存里面折腾？因为到内存映射为止，还没有开始真正访问内存，这时内存管理并不直接分配物理内存，因为物理内存相对于虚拟地址空间太宝贵了，只有等真正用的那一刻才会开始分配。

27. 一旦开始访问虚拟内存的某个地址，如果发现并没有对应的物理页，那就触发缺页中断，调用do_page_fault，如下所示：

dotraplinkage void notrace
do_page_fault(struct pt_regs *regs, unsigned long error_code)
{
  unsigned long address = read_cr2(); /* Get the faulting address */
......
  __do_page_fault(regs, error_code, address);
......
}


/*
 * This routine handles page faults.  It determines the address,
 * and the problem, and then passes it off to one of the appropriate
 * routines.
 */
static noinline void
__do_page_fault(struct pt_regs *regs, unsigned long error_code,
    unsigned long address)
{
  struct vm_area_struct *vma;
  struct task_struct *tsk;
  struct mm_struct *mm;
  tsk = current;
  mm = tsk->mm;


  if (unlikely(fault_in_kernel_space(address))) {
    if (vmalloc_fault(address) >= 0)
      return;
  }
......
  vma = find_vma(mm, address);
......
  fault = handle_mm_fault(vma, address, flags);
......

在__do_page_fault里，先要判断缺页中断是发生在内核还是用户态。如果发生在内核则调用vmalloc_fault，这就和虚拟内存的布局对应上了。在内核里面，vmalloc区域需要内核页表映射到物理页。这里把内核的这部分先放着，接着看用户空间的部分。接下来在用户空间里面，找到访问的那个地址所在的区域vm_area_struct，然后调用handle_mm_fault来映射这个区域，如下所示：

static int __handle_mm_fault(struct vm_area_struct *vma, unsigned long address,
    unsigned int flags)
{
  struct vm_fault vmf = {
    .vma = vma,
    .address = address & PAGE_MASK,
    .flags = flags,
    .pgoff = linear_page_index(vma, address),
    .gfp_mask = __get_fault_gfp_mask(vma),
  };
  struct mm_struct *mm = vma->vm_mm;
  pgd_t *pgd;
  p4d_t *p4d;
  int ret;


  pgd = pgd_offset(mm, address);
  p4d = p4d_alloc(mm, pgd, address);
......
  vmf.pud = pud_alloc(mm, p4d, address);
......
  vmf.pmd = pmd_alloc(mm, vmf.pud, address);
......
  return handle_pte_fault(&vmf);
}

到这里，终于看到了熟悉的PGD、P4G、PUD、PMD、PTE，这就是四级页表的概念，因为暂且不考虑五级页表，暂时先忽略P4G。四级页表的结构如下所示：

每个进程在用户态都有独立的内存地址空间，为了这个进程独立完成映射，每个进程都有独立的进程页表，这个页表中最顶级的是pgd，存放在task_struct中的mm_struct的pgd变量里面。在一个进程新创建的时候，会调用fork，对于内存的部分会调用copy_mm，里面调用dup_mm，如下所示：

/*
 * Allocate a new mm structure and copy contents from the
 * mm structure of the passed in task structure.
 */
static struct mm_struct *dup_mm(struct task_struct *tsk)
{
  struct mm_struct *mm, *oldmm = current->mm;
  mm = allocate_mm();
  memcpy(mm, oldmm, sizeof(*mm));
  if (!mm_init(mm, tsk, mm->user_ns))
    goto fail_nomem;
  err = dup_mmap(mm, oldmm);
  return mm;
}

在这里，除了创建一个新的mm_struct，并且通过memcpy将它和父进程的弄成一模一样之外，还需要调用mm_init进行初始化。接下来，mm_init调用mm_alloc_pgd分配全局页目录项，赋值给mm_struct的pgd成员变量，如下所示：

static inline int mm_alloc_pgd(struct mm_struct *mm)
{
  mm->pgd = pgd_alloc(mm);
  return 0;
}

pgd_alloc里除了分配PGD之外，还做了很重要的一个事情，就是调用pgd_ctor，如下所示：

static void pgd_ctor(struct mm_struct *mm, pgd_t *pgd)
{
  /* If the pgd points to a shared pagetable level (either the
     ptes in non-PAE, or shared PMD in PAE), then just copy the
     references from swapper_pg_dir. */
  if (CONFIG_PGTABLE_LEVELS == 2 ||
      (CONFIG_PGTABLE_LEVELS == 3 && SHARED_KERNEL_PMD) ||
      CONFIG_PGTABLE_LEVELS >= 4) {
    clone_pgd_range(pgd + KERNEL_PGD_BOUNDARY,
        swapper_pg_dir + KERNEL_PGD_BOUNDARY,
        KERNEL_PGD_PTRS);
  }
......
}

pgd_ctor 干了什么事情呢？注意看里面的注释，它拷贝了对于swapper_pg_dir的引用。swapper_pg_dir是内核页表的最顶级的全局页目录。一个进程的虚拟地址空间包含用户态和内核态两部分，为了从虚拟地址空间映射到物理页面，页表也分为用户地址空间的页表和内核页表，这就和上面遇到的vmalloc有关系了。在内核里面，映射靠内核页表，这里内核页表会拷贝一份到进程的页表。至于swapper_pg_dir是什么，怎么初始化和工作的，放到后面讨论。

至此，一个进程fork完毕之后，有了内核页表，有了自己顶级的pgd，但是对于用户地址空间来讲，还完全没有映射过。这需要等到这个进程在某个CPU上运行，并且对内存访问的那一刻了。当这个进程被调度到某个CPU上运行的时候，要调用context_switch进行上下文切换。对于内存方面的切换会调用switch_mm_irqs_off，这里面会调用load_new_mm_cr3。

cr3是CPU的一个寄存器，它会指向当前进程的顶级pgd。如果CPU的指令要访问进程的虚拟内存，它就会自动从cr3里面得到pgd在物理内存的地址，然后根据里面的页表解析虚拟内存的地址为物理内存，从而访问真正的物理内存上的数据。这里需要注意两点：

（1）cr3里面存放当前进程的顶级pgd，这个是硬件的要求，cr3里面需要存放pgd在物理内存的地址，不能是虚拟地址。因而load_new_mm_cr3里面会使用__pa，将mm_struct里面的成员变量pgd（mm_struct里存的都是虚拟地址）变为物理地址，才能加载到cr3里面去。

（2）用户进程在运行的过程中，访问虚拟内存中的数据，会被cr3里指向的页表转换为物理地址后，才在物理内存中访问数据，这个过程都是CPU在用户态运行的，地址转换的过程无需进入内核态。

只有访问虚拟内存的时候，发现没有映射多余物理内存，页表也没有创建过，才触发缺页异常。进入内核调用do_page_fault，一直调用到__handle_mm_fault，这才有了上面提到这个函数的时候看到的代码。既然原来没有创建过页表，那只好补上，于是__handle_mm_fault调用pud_alloc和pmd_alloc来创建相应的页目录项，最后调用handle_pte_fault来创建页表项。这样，终于将页表整个机制的各个部分串了起来。

28. 但是物理的内存还没找到，还得接着分析handle_pte_fault的实现，如下所示：

static int handle_pte_fault(struct vm_fault *vmf)
{
  pte_t entry;
......
  vmf->pte = pte_offset_map(vmf->pmd, vmf->address);
  vmf->orig_pte = *vmf->pte;
......
  if (!vmf->pte) {
    if (vma_is_anonymous(vmf->vma))
      return do_anonymous_page(vmf);
    else
      return do_fault(vmf);
  }


  if (!pte_present(vmf->orig_pte))
    return do_swap_page(vmf);
......
}

这里面总的来说分了三种情况。如果PTE也就是页表项，从来没有出现过，那就是新映射的页。如果是匿名页，就是第一种情况，应该映射到一个物理内存页，在这里调用的是do_anonymous_page。如果是映射到文件，调用的就是do_fault，这是第二种情况。如果PTE原来出现过，说明原来页面在物理内存中，后来换出到硬盘了，现在应该换回来，调用的是do_swap_page。

来看第一种情况，do_anonymous_page。对于匿名页的映射，需要先通过pte_alloc分配一个页表项，然后通过alloc_zeroed_user_highpage_movable分配一个页。之后它会调用alloc_pages_vma，并最终调用__alloc_pages_nodemask，如下所示：

static int do_anonymous_page(struct vm_fault *vmf)
{
  struct vm_area_struct *vma = vmf->vma;
  struct mem_cgroup *memcg;
  struct page *page;
  int ret = 0;
  pte_t entry;
......
  if (pte_alloc(vma->vm_mm, vmf->pmd, vmf->address))
    return VM_FAULT_OOM;
......
  page = alloc_zeroed_user_highpage_movable(vma, vmf->address);
......
  entry = mk_pte(page, vma->vm_page_prot);
  if (vma->vm_flags & VM_WRITE)
    entry = pte_mkwrite(pte_mkdirty(entry));


  vmf->pte = pte_offset_map_lock(vma->vm_mm, vmf->pmd, vmf->address,
      &vmf->ptl);
......
  set_pte_at(vma->vm_mm, vmf->address, vmf->pte, entry);
......
}

__alloc_pages_nodemask就是伙伴系统的核心函数，专门用来分配物理页面的。do_anonymous_page接下来要调用mk_pte，将页表项指向新分配的物理页，set_pte_at会将页表项塞到页表里面。

29. 第二种情况映射到文件do_fault，最终会调用__do_fault，如下所示：

static int __do_fault(struct vm_fault *vmf)
{
  struct vm_area_struct *vma = vmf->vma;
  int ret;
......
  ret = vma->vm_ops->fault(vmf);
......
  return ret;
}

这里调用了struct vm_operations_struct vm_ops的fault函数，还记得上面用mmap映射文件的时候，对于ext4文件系统，vm_ops指向了ext4_file_vm_ops，也就是调用了ext4_filemap_fault，如下所示：

static const struct vm_operations_struct ext4_file_vm_ops = {
  .fault    = ext4_filemap_fault,
  .map_pages  = filemap_map_pages,
  .page_mkwrite   = ext4_page_mkwrite,
};


int ext4_filemap_fault(struct vm_fault *vmf)
{
  struct inode *inode = file_inode(vmf->vma->vm_file);
......
  err = filemap_fault(vmf);
......
  return err;
}

vm_file就是当时mmap的时候映射的那个文件，然后需要调用filemap_fault，如下所示：

int filemap_fault(struct vm_fault *vmf)
{
  int error;
  struct file *file = vmf->vma->vm_file;
  struct address_space *mapping = file->f_mapping;
  struct inode *inode = mapping->host;
  pgoff_t offset = vmf->pgoff;
  struct page *page;
  int ret = 0;
......
  page = find_get_page(mapping, offset);
  if (likely(page) && !(vmf->flags & FAULT_FLAG_TRIED)) {
    do_async_mmap_readahead(vmf->vma, ra, file, page, offset);
  } else if (!page) {
    goto no_cached_page;
  }
......
  vmf->page = page;
  return ret | VM_FAULT_LOCKED;
no_cached_page:
  error = page_cache_read(file, offset, vmf->gfp_mask);
......
}

对于文件映射来说，一般这个文件会在物理内存里面有页作为它的缓存，find_get_page就是找那个缓存页。如果找到了，就调用do_async_mmap_readahead，预读一些数据到内存里面；如果没有就跳到no_cached_page。如果没有物理内存中的缓存页，那就调用page_cache_read。在这里显示分配一个缓存页，将这一页加到lru表里面，然后在address_space（用于反转映射，内存到文件系统）中调用address_space_operations的readpage函数，将文件内容读到内存中，如下所示：

static int page_cache_read(struct file *file, pgoff_t offset, gfp_t gfp_mask)
{
  struct address_space *mapping = file->f_mapping;
  struct page *page;
......
  page = __page_cache_alloc(gfp_mask|__GFP_COLD);
......
  ret = add_to_page_cache_lru(page, mapping, offset, gfp_mask & GFP_KERNEL);
......
  ret = mapping->a_ops->readpage(file, page);
......
}

struct address_space_operations对 ext4文件系统的定义如下所示：

static const struct address_space_operations ext4_aops = {
  .readpage    = ext4_readpage,
  .readpages    = ext4_readpages,
......
};


static int ext4_read_inline_page(struct inode *inode, struct page *page)
{
  void *kaddr;
......
  kaddr = kmap_atomic(page);
  ret = ext4_read_inline_data(inode, kaddr, len, &iloc);
  flush_dcache_page(page);
  kunmap_atomic(kaddr);
......
}

这么说来，上面的readpage调用的其实是ext4_readpage，这里不详细介绍ext4_readpage具体干了什么，只要知道这里最后会调用ext4_read_inline_page，这里面有部分逻辑和内存映射有关就行。

在ext4_read_inline_page函数里，需要先调用kmap_atomic，将物理内存映射到内核的虚拟地址空间，得到内核中的地址kaddr。kmap_atomic前面提过是用来做临时内核映射的，本来把物理内存映射到用户虚拟地址空间，不需要在内核里面映射一把，但是现在因为要从文件里面读取数据并写入这个物理页面，又不能使用物理地址只能使用虚拟地址，这就需要在内核里面临时映射一把，临时映射后ext4_read_inline_data读取文件到这个虚拟地址，读取完毕后取消这个临时映射，即调用kunmap_atomic就行了。至于kmap_atomic的具体实现，放到内核映射部分再说。

30. 再来看第三种情况，do_swap_page。之前讲过物理内存管理，部分空间如果长时间不用，就要换出到硬盘即swap，现在这部分数据又要访问了，还得想办法再次读到内存中来，如下所示：

int do_swap_page(struct vm_fault *vmf)
{
  struct vm_area_struct *vma = vmf->vma;
  struct page *page, *swapcache;
  struct mem_cgroup *memcg;
  swp_entry_t entry;
  pte_t pte;
......
  entry = pte_to_swp_entry(vmf->orig_pte);
......
  page = lookup_swap_cache(entry);
  if (!page) {
    page = swapin_readahead(entry, GFP_HIGHUSER_MOVABLE, vma,
          vmf->address);
......
  } 
......
  swapcache = page;
......
  pte = mk_pte(page, vma->vm_page_prot);
......
  set_pte_at(vma->vm_mm, vmf->address, vmf->pte, pte);
  vmf->orig_pte = pte;
......
  swap_free(entry);
......
}

do_swap_page函数会先查找swap文件有没有缓存页。如果没有就调用swapin_readahead，将swap文件读到内存中来，形成内存页，并通过mk_pte生成页表项。set_pte_at将页表项插入页表，swap_free将swap文件清理，因为重新加载回内存了，不再需要swap文件了。swapin_readahead会最终调用swap_readpage，在这里看到了熟悉的readpage函数，也就是说读取普通文件和读取swap文件，过程是一样的，同样需要用kmap_atomic做临时映射，如下所示：

int swap_readpage(struct page *page, bool do_poll)
{
  struct bio *bio;
  int ret = 0;
  struct swap_info_struct *sis = page_swap_info(page);
  blk_qc_t qc;
  struct block_device *bdev;
......
  if (sis->flags & SWP_FILE) {
    struct file *swap_file = sis->swap_file;
    struct address_space *mapping = swap_file->f_mapping;
    ret = mapping->a_ops->readpage(swap_file, page);
    return ret;
  }
......
}

通过上面复杂的过程，用户态缺页异常处理完毕了。物理内存中有了页面，页表也建立好了映射。接下来，用户程序在虚拟内存空间里面，可以通过虚拟地址顺利经过页表映射的访问物理页面上的数据了。然而为了加快映射速度，并不需要每次从虚拟地址到物理地址的转换都走一遍页表。页表一般都很大，只能存放在内存中。操作系统每次访问内存都要折腾两步，先通过查询页表得到物理地址，然后访问该物理地址读取指令、数据。

为了提高映射速度，引入了TLB（Translation Lookaside Buffer），经常称为快表，即专门用来做地址映射的硬件设备，如下图所示：

TLB不在内存中，可存储的数据比较少，但是比内存要快。所以TLB就相当于页表的Cache，其中存储了当前最可能被访问到的页表项，其内容是部分页表项的一个副本。有了TLB之后，地址映射的过程就像上图中，先查TLB表，快表中有映射关系，然后直接转换为物理地址。如果在TLB查不到映射关系时，才会到内存中查询页表。

31. 总结一下，用户态的内存映射机制包含以下几个部分：

（1）用户态内存映射函数mmap，包括用它来做匿名映射和文件映射。

（2）用户态的页表结构，存储位置在mm_struct中。

（3）在用户态访问没有映射的内存会引发缺页异常，分配物理页表、补齐页表。如果是匿名映射则分配物理内存；如果是swap，则将swap文件读入；如果是文件映射，则将文件读入。

五、内核态内存映射

32. 内核态的内存映射机制，主要包含以下几个部分：

（1）内核态内存映射函数vmalloc、kmap_atomic是如何工作的；

（2）内核态页表是放在哪里的，如何工作的；

（3）swapper_pg_dir是怎么回事；出现了内核态缺页异常应该怎么办。

和用户态页表不同，在系统初始化的时候，就要创建内核页表了。从内核页表的根swapper_pg_dir开始找线索，在arch/x86/include/asm/pgtable_64.h中就能找到它的定义，如下所示：

extern pud_t level3_kernel_pgt[512];
extern pud_t level3_ident_pgt[512];
extern pmd_t level2_kernel_pgt[512];
extern pmd_t level2_fixmap_pgt[512];
extern pmd_t level2_ident_pgt[512];
extern pte_t level1_fixmap_pgt[512];
extern pgd_t init_top_pgt[];


#define swapper_pg_dir init_top_pgt

swapper_pg_dir指向内核最顶级的目录pgd，同时出现的还有几个页目录项。可以回忆一下64位系统的虚拟地址空间的布局，其中XXX_ident_pgt对应的是直接映射区，XXX_kernel_pgt对应的是内核代码区，XXX_fixmap_pgt对应的是固定映射区。它们是在哪里初始化的呢？在汇编语言的文件里的arch\x86\kernel\head_64.S，这段代码比较难看懂，只要明白它是干什么的就行了：

__INITDATA


NEXT_PAGE(init_top_pgt)
  .quad   level3_ident_pgt - __START_KERNEL_map + _KERNPG_TABLE
  .org    init_top_pgt + PGD_PAGE_OFFSET*8, 0
  .quad   level3_ident_pgt - __START_KERNEL_map + _KERNPG_TABLE
  .org    init_top_pgt + PGD_START_KERNEL*8, 0
  /* (2^48-(2*1024*1024*1024))/(2^39) = 511 */
  .quad   level3_kernel_pgt - __START_KERNEL_map + _PAGE_TABLE


NEXT_PAGE(level3_ident_pgt)
  .quad  level2_ident_pgt - __START_KERNEL_map + _KERNPG_TABLE
  .fill  511, 8, 0
NEXT_PAGE(level2_ident_pgt)
  /* Since I easily can, map the first 1G.
   * Don't set NX because code runs from these pages.
   */
  PMDS(0, __PAGE_KERNEL_IDENT_LARGE_EXEC, PTRS_PER_PMD)


NEXT_PAGE(level3_kernel_pgt)
  .fill  L3_START_KERNEL,8,0
  /* (2^48-(2*1024*1024*1024)-((2^39)*511))/(2^30) = 510 */
  .quad  level2_kernel_pgt - __START_KERNEL_map + _KERNPG_TABLE
  .quad  level2_fixmap_pgt - __START_KERNEL_map + _PAGE_TABLE


NEXT_PAGE(level2_kernel_pgt)
  /*
   * 512 MB kernel mapping. We spend a full page on this pagetable
   * anyway.
   *
   * The kernel code+data+bss must not be bigger than that.
   *
   * (NOTE: at +512MB starts the module area, see MODULES_VADDR.
   *  If you want to increase this then increase MODULES_VADDR
   *  too.)
   */
  PMDS(0, __PAGE_KERNEL_LARGE_EXEC,
    KERNEL_IMAGE_SIZE/PMD_SIZE)


NEXT_PAGE(level2_fixmap_pgt)
  .fill  506,8,0
  .quad  level1_fixmap_pgt - __START_KERNEL_map + _PAGE_TABLE
  /* 8MB reserved for vsyscalls + a 2MB hole = 4 + 1 entries */
  .fill  5,8,0


NEXT_PAGE(level1_fixmap_pgt)
  .fill  51

内核页表的顶级目录init_top_pgt，定义在__INITDATA里面。在ELF的格式和虚拟内存空间的布局中，它们都有代码段，还有一些初始化了的全局变量放在.init区域，__INITDATA这些说的就是这个区域。可以看到页表的根其实是全局变量，这就使得系统初始化的时候，甚至内存管理模块还没有初始化的时候，很容易就可以定位到。接下来，定义init_top_pgt包含哪些项，这个汇编代码比较难懂了，可以简单地认为quad是声明了一项的内容，org是跳到了某个位置。

所以init_top_pgt有三项，上来先有一项指向的是level3_ident_pgt，也即直接映射区页表的三级目录。为什么要减去__START_KERNEL_map呢？因为level3_ident_pgt是定义在内核代码里的，写代码的时候写的都是虚拟地址，也不知道将来加载的物理地址是多少。所以level3_ident_pgt是在虚拟地址的内核代码段里的，而__START_KERNEL_map正是虚拟地址空间的内核代码段的起始地址。这样，level3_ident_pgt减去__START_KERNEL_map才是物理地址。

第一项定义完了以后，接下来通过org跳到PGD_PAGE_OFFSET的位置，通过quad再定义一项。从定义可以看出，这一项对应的是__PAGE_OFFSET_BASE。__PAGE_OFFSET_BASE是虚拟地址空间里面内核的起始地址。第二项也指向level3_ident_pgt，也就是内核态的直接映射区，如下所示：

PGD_PAGE_OFFSET = pgd_index(__PAGE_OFFSET_BASE)
PGD_START_KERNEL = pgd_index(__START_KERNEL_map)
L3_START_KERNEL = pud_index(__START_KERNEL_map)

第二项定义完了以后，接下来跳到PGD_START_KERNEL的位置，再定义一项。从定义可以看出，这一项应该是__START_KERNEL_map对应的项，__START_KERNEL_map是虚拟地址空间里面内核代码段的起始地址。第三项指向level3_kernel_pgt，即内核代码区。接下来的代码就很类似了，就是初始化一个表项，然后指向下一级目录，最终形成下面这张图：

33. 内核页表定义完了，一开始这里面的页表能够覆盖的内存范围比较小，例如内核代码区512M，直接映射区1G。这个时候，其实只要能够映射基本的内核代码和数据结构就可以了。可以看出上图的树形表里面还空着很多项，可以用于将来映射巨大的内核虚拟地址空间，等用到的时候再进行映射。如果是用户态进程页表，会有mm_struct指向进程顶级目录pgd，对于内核来讲，也定义了一个mm_struct，指向swapper_pg_dir，如下所示：

struct mm_struct init_mm = {
  .mm_rb    = RB_ROOT,
  .pgd    = swapper_pg_dir,
  .mm_users  = ATOMIC_INIT(2),
  .mm_count  = ATOMIC_INIT(1),
  .mmap_sem  = __RWSEM_INITIALIZER(init_mm.mmap_sem),
  .page_table_lock =  __SPIN_LOCK_UNLOCKED(init_mm.page_table_lock),
  .mmlist    = LIST_HEAD_INIT(init_mm.mmlist),
  .user_ns  = &init_user_ns,
  INIT_MM_CONTEXT(init_mm)
};

定义完了内核页表，接下来是初始化内核页表，在系统启动的时候start_kernel会调用setup_arch，如下所示：

void __init setup_arch(char **cmdline_p)
{
  /*
   * copy kernel address range established so far and switch
   * to the proper swapper page table
   */
  clone_pgd_range(swapper_pg_dir     + KERNEL_PGD_BOUNDARY,
      initial_page_table + KERNEL_PGD_BOUNDARY,
      KERNEL_PGD_PTRS);


  load_cr3(swapper_pg_dir);
  __flush_tlb_all();
......
  init_mm.start_code = (unsigned long) _text;
  init_mm.end_code = (unsigned long) _etext;
  init_mm.end_data = (unsigned long) _edata;
  init_mm.brk = _brk_end;
......
  init_mem_mapping();
......
}

在setup_arch中，load_cr3(swapper_pg_dir)说明内核页表要开始起作用了（硬件要求），并且刷新了TLB，初始化init_mm的成员变量，最重要的就是init_mem_mapping，最终它会调用kernel_physical_mapping_init，如下所示：

/*
 * Create page table mapping for the physical memory for specific physical
 * addresses. The virtual and physical addresses have to be aligned on PMD level
 * down. It returns the last physical address mapped.
 */
unsigned long __meminit
kernel_physical_mapping_init(unsigned long paddr_start,
           unsigned long paddr_end,
           unsigned long page_size_mask)
{
  unsigned long vaddr, vaddr_start, vaddr_end, vaddr_next, paddr_last;


  paddr_last = paddr_end;
  vaddr = (unsigned long)__va(paddr_start);
  vaddr_end = (unsigned long)__va(paddr_end);
  vaddr_start = vaddr;


  for (; vaddr < vaddr_end; vaddr = vaddr_next) {
    pgd_t *pgd = pgd_offset_k(vaddr);
    p4d_t *p4d;


    vaddr_next = (vaddr & PGDIR_MASK) + PGDIR_SIZE;


    if (pgd_val(*pgd)) {
      p4d = (p4d_t *)pgd_page_vaddr(*pgd);
      paddr_last = phys_p4d_init(p4d, __pa(vaddr),
               __pa(vaddr_end),
               page_size_mask);
      continue;
    }


    p4d = alloc_low_page();
    paddr_last = phys_p4d_init(p4d, __pa(vaddr), __pa(vaddr_end),
             page_size_mask);


    p4d_populate(&init_mm, p4d_offset(pgd, vaddr), (pud_t *) p4d);
  }
  __flush_tlb_all();


  return paddr_l

在kernel_physical_mapping_init里，先通过__va将物理地址转换为虚拟地址，然后再创建虚拟地址和物理地址的映射页表。既然对于内核来讲，可以用__va 和 __pa直接在虚拟地址和物理地址之间直接转来转去，为啥还要辛辛苦苦建立页表呢？因为这是CPU和内存的硬件的需求，也就是说CPU在保护模式下访问虚拟地址的时候，就会用CR3这个寄存器，这个寄存器是CPU定义的，作为操作系统是软件，只能按照硬件的要求来。

那么按照将系统初始化的过程，系统早早就进入了保护模式，到了setup_arch里面才load_cr3，如果使用cr3是硬件的要求，那之前是怎么办的呢？如果仔细去看arch\x86\kernel\head_64.S，这里面除了初始化内核页表之外，在这之前还有另一个页表early_top_pgt，这个页表就是专门用在真正的内核页表初始化之前，为了遵循硬件的要求而设置的。早期页表不是这里的重点，就不展开多说了。

34. 在用户态可以通过malloc函数分配内存，malloc在分配比较大的内存的时候，底层调用的是mmap，当然也可以直接通过mmap做内存映射，在内核里也有相应的函数。在虚拟地址空间里面，有个vmalloc区域，从VMALLOC_START开始到VMALLOC_END，可以用于映射一段物理内存。vmalloc的实现如下所示：

/**
 *  vmalloc  -  allocate virtually contiguous memory
 *  @size:    allocation size
 *  Allocate enough pages to cover @size from the page level
 *  allocator and map them into contiguous kernel virtual space.
 *
 *  For tight control over page level allocator and protection flags
 *  use __vmalloc() instead.
 */
void *vmalloc(unsigned long size)
{
  return __vmalloc_node_flags(size, NUMA_NO_NODE,
            GFP_KERNEL);
}


static void *__vmalloc_node(unsigned long size, unsigned long align,
          gfp_t gfp_mask, pgprot_t prot,
          int node, const void *caller)
{
  return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
        gfp_mask, prot, 0, node, caller);
}

再来看内核的临时映射函数kmap_atomic的实现，从下面的代码可以看出，如果是32位有高端地址的，就需要调用set_pte通过内核页表进行临时映射；如果是64位不需要高端地址的，就调用page_address，里面会调用lowmem_page_address，其实低端内存的映射，会直接使用 __va 进行临时映射：

void *kmap_atomic_prot(struct page *page, pgprot_t prot)
{
......
  if (!PageHighMem(page))
    return page_address(page);
......
  vaddr = __fix_to_virt(FIX_KMAP_BEGIN + idx);
  set_pte(kmap_pte-idx, mk_pte(page, prot));
......
  return (void *)vaddr;
}


void *kmap_atomic(struct page *page)
{
  return kmap_atomic_prot(page, kmap_prot);
}


static __always_inline void *lowmem_page_address(const struct page *page)
{
  return page_to_virt(page);
}


#define page_to_virt(x)  __va(PFN_PHYS(page_to_pfn(x)

35. 可以看出，kmap_atomic和vmalloc不同。kmap_atomic发现没有页表的时候，就直接创建页表进行映射了。而vmalloc没有，它只分配了内核的虚拟地址。所以访问它的时候，会产生缺页异常。内核态的缺页异常还是会调用do_page_fault，但是会走到上面用户态缺页异常中还没有详细说的那部分vmalloc_fault，这个函数并不复杂，主要用于关联内核页表项：

/*
 * 32-bit:
 *
 *   Handle a fault on the vmalloc or module mapping area
 */
static noinline int vmalloc_fault(unsigned long address)
{
  unsigned long pgd_paddr;
  pmd_t *pmd_k;
  pte_t *pte_k;


  /* Make sure we are in vmalloc area: */
  if (!(address >= VMALLOC_START && address < VMALLOC_END))
    return -1;


  /*
   * Synchronize this task's top level page-table
   * with the 'reference' page table.
   *
   * Do _not_ use "current" here. We might be inside
   * an interrupt in the middle of a task switch..
   */
  pgd_paddr = read_cr3_pa();
  pmd_k = vmalloc_sync_one(__va(pgd_paddr), address);
  if (!pmd_k)
    return -1;


  pte_k = pte_offset_kernel(pmd_k, address);
  if (!pte_present(*pte_k))
    return -1;


  return 0

36. 总结一下整个内存管理的体系，如下所示：

（1）物理内存根据NUMA架构分节点，每个节点里面再分区域，每个区域里面再分页。

（2）物理页通过伙伴系统进行分配。分配的物理页面要变成虚拟地址让上层可以访问，kswapd可以根据物理页面的使用情况对页面进行换入换出。

（3）对于内存的分配需求，可能来自内核态也可能来自用户态。

（4）对于内核态，kmalloc在分配大内存的时候，以及vmalloc分配不连续物理页的时候，直接使用伙伴系统，分配后转换为虚拟地址，访问的时候需要通过内核页表进行映射。

（5）对于kmem_cache以及kmalloc分配小内存，则使用slub分配器，将伙伴系统分配出来的大块内存切成一小块一小块进行分配。kmem_cache和kmalloc的部分不会被换出，因为用这两个函数分配的内存多用于保持内核关键的数据结构。

（6）内核态中vmalloc分配的部分会被换出，因而当访问的时候，发现不在就会调用do_page_fault。

（7）对于用户态的内存分配，或者直接调用mmap系统调用分配，或者调用malloc。调用malloc的时候，如果分配小的内存，就用sys_brk系统调用；如果分配大的内存，还是用sys_mmap系统调用。正常情况下，用户态的内存都是可以换出的，因而一旦发现内存中不存在，就会调用do_page_fault映射一下。