9.2 Linux虚拟内存系统 #
Linux 为每个进程维护了一个单独的虚拟地址空间。
操作系统给每个进程分配了一个地址空间，其布局如上图。“地址空间”是一个逻辑概念，定义了进程理论上可以访问的所有虚拟地址的范围；页表是一个物理数据结构，记录了地址空间中哪些区域已经被映射到物理内存。CPU在取指或者访问数据时，给出的是一个虚拟地址，并利用这个虚拟地址去查页表，从而去找到对应的物理内存。可以说，地址空间是对物理内存的抽象，是给CPU提供便利的。而具体的寻址还是需要页表和物理内存来实现。同时这样的抽象也为地址的合理性检查提供了便利。
可以发现每个进程的地址空间分为两个部分：
- 高地址处是内核空间，一部分是与进程相关的私有数据，如内核栈、进程控制块PCB、页表等等，这些在每个进程中是独立的，每个进程都不相同；另一部分则是内核代码和数据，这些则是每个进程共享的，具体的方式是每个进程的页表负责映射“高地址内核空间”的那些页表项，都指向物理内存中完全相同的那一页，对每个进程都一样。比如PCB就在这里。
- 低地址处是用户空间，包括
.rodata,.bss,.data,.text段以及堆栈等等。
可以使用
cat /proc/[PID]/maps来查看
在Linux中，struct mm_struct *mm是整个进程用户态虚拟地址空间的总入口，包含页目录、虚拟内存区域链表等全部信息。如pgd_t *pgd是页目录的起始地址，在x86中会在利用这个值时保存在CR3寄存器中。
9.2.1 Linux虚拟内存区域 #
Linux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域(area)就是已经存在着的（已分配的）虚拟内存的连续片(chunk), 这些页是以某种方式相关联的。
通过阅读linux源码发现在v6.1之前（不包含6.1），虚拟内存确实是按照csapp书中图上这样的组织方式进行的；而在v6.1及以后的版本中，mm_struct中不再有vm_area_struct，变为一个maple_tree的结构来管理虚拟空间。这里先看看书中所说版本的代码：
在/include/linux/sched.h中定义了struct task_struct，可以在其中找到成员struct mm_struct *mm，也就是上图中的第一个指针；
// /include/linux/sched.h
struct task_struct {
...
struct mm_struct *mm;
...
}在/include/linux/mm_types.h中定义了struct mm_struct，如下：
// /include/linux/mm_types.h
struct mm_struct {
...
struct vm_area_struct *mmap; /* list of VMAs */
struct rb_root mm_rb;
...
}在/include/linux/mm_types.h中定义了struct vm_area_struct，如下：
// /include/linux/mm_types.h
struct vm_area_struct {
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. */
pgprot_t vm_page_prot; /* Access permissions of this VMA. */
unsigned long vm_flags; /* Flags, see mm.h. */
}可以发现这些区域(vm_area)是以链表方式组织的，且更具体是使用红黑树组织的，可以发现在mm_struct中有嵌入的struct rb_node mm_rb；在vm_area_struct中有嵌入的struct rb_node vm_rb。事实上，在后面提到的缺页处理中查看某个虚拟地址是否合法的时候，利用红黑树的结构能够快速地判断，且mm_rb作为根节点、vm_rb作为其余节点进行查询。有关红黑树的具体内容见9.2.3的内容。
9.2.2 Linux缺页异常处理 #
假设MMU在试图翻译某个虚拟地址A时，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序随后就执行下面的步骤:
- (1) 虚拟地址A是合法的吗？换句话说，A在某个区域结构定义的区域内吗？为了回答这个问题，缺页处理程序搜索区域结构的链表，把A和每个区域结构(
vm_area_struct)中的vm_start和vm_end做比较。如果这个指令是不合法的，那么缺页处理程序就触发一个段错误，从而终止这个进程。这个情况在下图中标识为"1"。
因为一个进程可以创建任意数量的新虚拟内存区域，所以顺序搜索区域结构的链表花销可能会很大。因此在实际中，Linux在链表中构建了一棵红黑树，并在这棵树上进行查找。
-
(2) 试图进行的内存访问是否合法？换句话说，进程是否有读、写或者执行这个区域内页面的权限？例如，这个缺页是不是由一条试图对这个代码段里的只读页面进行写操作的存储指令造成的？这个缺页是不是因为一个运行在用户模式中的进程试图从内核虚拟内存中读取字造成的？如果试图进行的访问是不合法的，那么缺页处理程序会触发一个保护异常，从而终止这个进程。这种情况在下图中标识为"2"。
-
(3) 此刻，内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成的。它是这样来处理这个缺页的:选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换人新的页面并更新页表。当缺页处理程序返回时，CPU重新启动引起缺页的指令，这条指令将再次发送A到MMU。这次，MMU就能正常地翻译A，而不会再产生缺页中断了。
9.2.3 红黑树在虚拟内存中的应用浅析 #
注：以下代码均来自于Linux v5.0。
写这一小部分的动机是原书上提到了：
我想看看在源码中怎么实现红黑树的，就去https://elixir.bootlin.com/linux中搜索了一下，具体如下：
9.2.3.1 红黑树节点的定义 #
在/include/linux/rbtree.h中给出了节点的定义：
// /include/linux/rbtree.h
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;
};
// 后续还有很多操作函数的声明
可以发现一个节点的成员有：父亲节点的指针、左右子孩子的指针，并且父亲节点的颜色作为第三位与父节点指针组合在了一起。原因是节点地址按照64位对齐，那么每个节点的地址的第三位势必都是0，而颜色只有红黑两种，只需一位就可以进行标记，那么就有了__rb_parent_color = rb_parent_addr | rb_parent_color。想要取出来父节点地址也很简单，只需要把低3位置0即可。（这里和动态内存分配中的隐式空闲链表的头部尾部设计是类似的，由于空闲块地址都是64位对齐的，低三位必定都是0，那么就可以利用这3位来标记当前块是空闲的还是已分配的了，具体见下图）
此外在这个文件中还有一些比较关键的宏定义，例如在文件/include/linux/kernel.h中所定义的container_of宏：
// /include/linux/kernel.h
/**
* container_of - cast a member of a structure out to the containing structure
* @ptr: the pointer to the member.
* @type: the type of the container struct this is embedded in.
* @member: the name of the member within the struct.
*
*/
#define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \
!__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })这个宏的名称就很直白：取某某的容器，具体地看，其作用是利用ptr指针减去该指针到其所处结构体起始地址的偏移量(offsetof(type, member))，以获得该指针所处结构体的起始地址的指针。这个宏解决的问题是：只知道结构体中某个成员的指针，如何获得整个结构体的指针？运算方式就是：
其中BUILD_BUG_ON_MSG：如果不匹配，编译时报错；((type *)0)->member：使用空指针访问成员，仅在编译时，不实际执行。而offsetof是编译器内置功能，计算成员在结构体中的偏移量。({ }) 是一个表达式，有返回值，保持宏的表达式的特性可以赋值。
此外，该文件还对其进行了一层包装：
// /include/linux/rbtree.h
#define rb_entry(ptr, type, member) container_of(ptr, type, member)这样的好处是，可以将红黑树的节点嵌入到其他数据结构当中，也就是说可以将一个struct rb_node *rb_node节点作为成员放在其他数据结构中。这样的好处是，当我们在红黑树中查找到一个节点时，可以通过rb_entry宏来获取包含该节点的更大结构体的指针，从而访问该结构体的其他成员。在进行红黑树操作时，这种方式非常有用，因为我们通常需要访问包含节点的结构体的其他信息，而不仅仅是节点本身。下面可给出一个具体的例子来说明：
struct my_data {
int value;
struct rb_node node; // 红黑树节点作为成员
};
// 假设我们有一个指向红黑树节点的指针 rb_node_ptr
struct my_data *data_ptr = rb_entry(rb_node_ptr, struct my_data, node);在这个例子中，rb_entry 宏将 rb_node_ptr 转换为指向包含该节点的 my_data 结构体的指针 data_ptr，从而可以访问 my_data 结构体中的其他成员（如 value）。而这些其他成员正好可以作为红黑树节点的附加信息使用，比如在插入节点时进行的比较规则。
这里突然想到这个宏与cpp类的this指针很相似，this指针在编译器层面会将结构体的地址作为第一个参数传递给非静态成员函数，相当于是已知结构体的地址了；而这里的宏是需要程序员显式调用的，是利用节点的地址反推出其所在结构体的地址的。
9.2.3.2 红黑树在虚拟内存中的应用 #
我找到了在9.2.2中提到的缺页异常处理的代码逻辑，位于/arch/x86/mm/fault.c中，下面省略非常繁杂的判断部分只给出缺页处理中可能会遇到的三种情况的部分（段错误、保护异常、合法缺页）：
// /arch/x86/mm/fault.c
/*
* Handle faults in the user portion of the address space. Nothing in here
* should check X86_PF_USER without a specific justification: for almost
* all purposes, we should treat a normal kernel access to user memory
* (e.g. get_user(), put_user(), etc.) the same as the WRUSS instruction.
* The one exception is AC flag handling, which is, per the x86
* architecture, special for WRUSS.
*/
static inline
void do_user_addr_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;
vm_fault_t fault;
unsigned int flags = FAULT_FLAG_DEFAULT;
tsk = current;
mm = tsk->mm;
...
vma = find_vma(mm, address); // 查找包含address的VMA
// 情况1：没有找到包含address的VMA，触发段错误
if (unlikely(!vma)) {
bad_area(regs, hw_error_code, address);
return;
}
// 情况2：正常缺页，访问未加载的有效页面
if (likely(vma->vm_start <= address))
goto good_area;
if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
bad_area(regs, hw_error_code, address);
return;
}
if (unlikely(expand_stack(vma, address))) {
bad_area(regs, hw_error_code, address);
return;
}
/*
* Ok, we have a good vm_area for this memory access, so
* we can handle it..
*/
good_area:
if (unlikely(access_error(hw_error_code, vma))) {
// 情况3：VMA 存在，但访问权限不合法，触发保护异常
bad_area_access_error(regs, hw_error_code, address, vma);
return;
}
fault = handle_mm_fault(vma, address, flags);
...
}在这个函数中有几个关键点：
(1) likely, unlikely #
likely 和 unlikely 宏的定义如下：
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)__builtin_expect 是 GCC 的内置函数，用来对选择语句的判断条件进行优化，常用于一个判断条件经常成立（如 likely）或经常不成立（如 unlikely）的情况。__builtin_expect 的函数原型为 long __builtin_expect(long exp, long c)，返回值为完整表达式 exp 的值，它的作用是期望表达式 exp 的值等于 c。如果 exp == c 条件成立的机会占绝大多数，那么性能将会得到提升，否则性能反而会下降。
因此，if (unlikely(a)) 和 if (likely(a)) 的执行等价于 if (a) ，区别在于 unlikely 和 likely 函数的加入会优化编译。这样做的目的可以提高 CPU 指令判断效率，减少指令跳转而降低性能。
if (likely(a > b)) {
// 这里的代码更有可能被执行
fun1();
} else {
// 这里的代码不太可能被执行
fun2();
}此处参考来源：https://blog.csdn.net/ludaoyi88/article/details/113832126
(2) vma(virtual memory area)是如何找到的
#
查看函数find_vma，来自文件/mm/mmap.c/：
// /mm/mmap.c
/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
struct rb_node *rb_node;
struct vm_area_struct *vma;
/* Check the cache first. */
vma = vmacache_find(mm, addr);
if (likely(vma))
return vma;
rb_node = mm->mm_rb.rb_node; // 红黑树根节点：mm_rb.rb_node
while (rb_node) {
struct vm_area_struct *tmp;
tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
if (tmp->vm_end > addr) {
vma = tmp;
if (tmp->vm_start <= addr)
break;
rb_node = rb_node->rb_left;
} else
rb_node = rb_node->rb_right;
}
if (vma)
vmacache_update(addr, vma);
return vma;
}函数功能是查找包含地址 addr 的 vma，查找第一个满足 addr < vm_end 的 vma，返回找到的 vma 或 NULL。这样设计的原理来自于将红黑树节点嵌入在两个数据结构中：
// mm_struct 中的定义
struct mm_struct {
struct rb_root mm_rb; // 红黑树的根节点
// ...
};
// vm_area_struct 中的定义
struct vm_area_struct {
// ...
struct rb_node vm_rb; // 红黑树节点，嵌入在VMA中
// ...
};mm->mm_rb是VMA红黑树的入口点，所有的vma都通过vm_rb链接成红黑树，利用红黑树节点的遍历规则，加上rb_entry宏获得结构体地址，借助成员变量vm_start和vm_end来进行比较规则，实现查到满足条件的vma。我觉得这个函数是比较有精髓的一个了，红黑树在虚拟内存中的作用很集中地体现在这个函数当中。
(3) 在情况2的情况下正常缺页 #
此时进入good_area，进入/mm/memory.c: handle_mm_fault() -> /mm/memory.c: __handle_mm_fault() -> /mm/memory.c: handle_pte_fault()，这里面会进一步检查PTE的相关情况，并确定所需要的信息是应该从交换区来、还是从内存来等等，具体的代码在handle_pte_fault()中：
...
if (!vmf->pte) {
if (vma_is_anonymous(vmf->vma))
return do_anonymous_page(vmf); // 匿名页缺页，如malloc后的第一次写
else
return do_fault(vmf); // 文件映射的缺页，如mmap后的第一次读
}
if (!pte_present(vmf->orig_pte))
return do_swap_page(vmf); // PTE有值，但是不在内存，从交换区找
if (pte_protnone(vmf->orig_pte) && vma_is_accessible(vmf->vma))
return do_numa_page(vmf); // NUMA迁移
vmf->ptl = pte_lockptr(vmf->vma->vm_mm, vmf->pmd);
spin_lock(vmf->ptl);
entry = vmf->orig_pte;
if (unlikely(!pte_same(*vmf->pte, entry)))
goto unlock;
if (vmf->flags & FAULT_FLAG_WRITE) {
if (!pte_write(entry))
return do_wp_page(vmf); // COW缺页，如fork后的写
entry = pte_mkdirty(entry);
}
...9.2.3.3 版本变化 #
我发现自从v6.1以后，mm_struct的结构发生了变化，没有了struct rb_root mm_rb;，而变为：struct maple_tree mm_mt;。很明显从此以后没有再使用红黑树进行存储虚拟内存块了，而是转向了B树的变体：Maple Tree。经过查询ai得知，对比有以下好处：
-
红黑树的局限性:
- 缓存不友好：红黑树的节点分散在内存中
- 锁争用严重：全局锁影响并发性能
- 范围查询低效：查找重叠区间的操作复杂
- 内存开销大：每个 VMA 需要额外的指针
-
Maple Tree 的优势:
- 更好的缓存局部性：节点内多个元素连续存储
- 更细粒度的锁：读写锁分离，支持 RCU
- 高效的范围操作：原生支持区间查询
- 内存效率更高：减少指针开销
在/mm/mmap.c中，find_vma函数也发生了变化：
// /mm/mmap.c
/**
* find_vma() - Find the VMA for a given address, or the next VMA.
* @mm: The mm_struct to check
* @addr: The address
*
* Returns: The VMA associated with addr, or the next VMA.
* May return %NULL in the case of no VMA at addr or above.
*/
struct vm_area_struct *find_vma(struct mm_struct *mm, unsigned long addr)
{
unsigned long index = addr;
mmap_assert_locked(mm);
return mt_find(&mm->mm_mt, &index, ULONG_MAX);
}mt_find函数在/lib/maple_tree.c中，具体内容后续有时间再学习吧。
总结：
我在之前学习的数据结构与算法中，往往都是构建一颗完成的树，树的每个节点都存储好需要的数据；而在linux中，是“反过来的”，即定义数据结构的时候，把树的节点作为成员放入到其中。那如何找到某个节点所处的结构体指针呢？可以用container_of宏来完成。在虚拟内存块的管理中，linux在6.1之前的版本中使用了：
mm_struct → mm_rb (红黑树根) → vm_area_struct (通过vm_rb链接)而在后续中则使用了B树的变体：
mm_struct → mm_mt (Maple Tree根) → vm_area_struct (通过Maple Tree节点)这也说明CSAPP这本书参考的linux版本较早。