Chapter 3 页表与内存管理

操作系统 MIT6.s081
操作系统
发布日期:   2025-02-17
更新日期:   2025-02-19
文章字数:   6.6k
阅读时长:   23 分
阅读次数:  

Chapter 3 Page tables

重要要点

  • 页表与内存管理：
    • 分页机制实现了虚拟地址到物理地址的转换，每个进程拥有独立的地址空间。
    • 页表是内存管理的关键数据结构，用于记录虚拟地址与物理地址的映射关系。
    • 操作系统通过页表实现内存保护和资源隔离，确保进程不会访问其他进程或内核的内存。
    • 页面错误（Page Fault）是由分页硬件在无法找到有效 PTE 时触发的异常，操作系统可以利用软件实现的页错误处理程序来管理系统内存。
  • 地址空间布局：
    • 进程的用户地址空间包括文本、数据、堆栈和堆，内核地址空间独立于用户地址空间，包含内核代码、数据和内核堆栈。
    • xv6 的内核地址空间和用户地址空间都通过页表进行映射，确保内核和用户代码使用不同的虚拟地址范围。
  • 硬件支持与功能实现：
    • RISC-V 架构提供了硬件分页支持，包括页表结构（页目录和页表）以及相关的控制寄存器（如 satp）。
    • xv6 利用硬件分页机制实现了高效的内存管理，包括地址翻译、内存保护和页面错误处理。

关键概念和名词

  1. 页表（Page Table）：
    • 用于实现虚拟地址到物理地址转换的数据结构，由操作系统维护和更新。
    • 在 xv6 中，每个进程的页表保存在 struct proc 中，内核页表是全局的，保存在 kern_pgdir 中。
  2. 调度算法（Scheduling Algorithm）：
    • 虽然主要在 Chapter7 中详细讨论，但页表管理的效率对调度算法至关重要，因为进程切换和时间片轮转需要保存和恢复进程的页表。
  3. fork()：
    • xv6 中实现的 fork 系统调用通过复制父进程的页表来创建子进程，确保子进程拥有与父进程相同的内存布局。
  4. 虚存访问模型（Virtual Memory Access Model）：
    • 包括分页、段式和段页式等多种方式，xv6 采用分页模型，硬件和软件协同工作，实现高效内存访问和管理。
  5. 内存映射（Memory Mapping）：
    • 将文件或设备映射到进程的地址空间，操作系统通过修改页表实现，允许进程像访问普通内存一样访问文件或设备。

需要了解的背景知识

  • 操作系统原理：
    • 内存管理原理，包括虚拟内存、物理内存、页面错误和内存映射等概念。
    • 进程管理，包括进程隔离、上下文切换和虚拟地址空间分配。
    • 文件系统知识，包括文件存储和访问方式。
    • 虚存访问模型，了解操作系统如何管理内存和地址空间。
  • 数据结构：
    • 理解队列、堆栈、链表等数据结构，因为页表和其他内存管理结构通常使用这些数据结构实现。
    • 了解树形结构，因为页表可以被视为多层树结构。
  • 系统编程：
    • 熟悉 C 语言和汇编语言编程，因为 xv6 是用 C 语言实现的，并包含一些汇编代码。
    • 了解操作系统内核编程的基本概念，如中断、异常处理和系统调用。

学习目标

  1. 理解虚存访问模型和分页机制：
    • 掌握虚拟地址到物理地址的翻译过程，以及页表在这一过程中的作用。
    • 弄清楚页目录和页表的结构如何构建分页模型。
  2. 掌握内存管理的实现细节：
    • 理解 xv6 的内存管理系统如何分配和回收内存。
    • 了解页面错误的处理机制，包括如何为新页表项分配物理内存。
  3. 分析和理解重要代码和函数：
    • 能够阅读和理解 xv6 中与页表相关的源码，如 walk、mappages 等函数的实现。
    • 理解如何通过修改页表实现内存映射和共享。
  4. 学习硬件与软件的协同工作：
    • 知道 RISC-V 架构中与分页相关的硬件特性，如 satp 寄存器、页面大小和分页级别。
    • 理解操作系统如何利用这些硬件特性实现高效的内存管理。

重要代码和函数

  1. walk 函数：

    c复制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) {
        pte_t *pte;
        uint64 pfn;

        pte = &pagetable[PDX(va)];
        if (*pte & PTE_V) {
            pfn = PTE2PA(*pte) / PGSIZE;
            pte = (pte_t*)kvmalloc(pfn) + PTX(va);
        } else if (alloc) {
            // 分配新的页表页并映射
        }
        return pte;
    }
    • 作用：查找虚拟地址对应的页表项，并根据需要分配新的页表页。

  2. mappages 函数：

    c复制

    1
    2
    3
    4
    5
    void mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int pte_flags) {
        for (uint64 a = va; a < va + size; a += PGSIZE) {
            walk(pagetable, a, 1)[PTX(a)] = (pa + (a - va)) | (pte_flags | PTE_V);
        }
    }
    • 作用：将虚拟地址范围映射到物理地址，并设置页表项的权限标志。

  3. kvminit 函数：

    • 作用：初始化内核页表，映射内核代码、数据和堆栈。

  4. kvmtrap 函数：

    • 作用：处理内核中的故障和中断，包括页面错误。

  5. uservec 和 userret 函数：

    • 作用：
      • uservec 是用户态异常的汇编入口点，负责保存用户寄存器并切换到内核模式。
      • userret 是返回用户态的汇编代码，负责恢复用户寄存器并切换回用户模式。

学习建议

  1. 阅读相关文档：
    • 仔细阅读 RISC-V 的分页硬件文档，了解页表结构和控制寄存器的使用。
    • 查阅 xv6 的官方文档和注释，理解页面错误处理和内存管理的实现细节。
  2. 学习和理解源码：
    • 重点阅读和理解 vm.c 文件中的代码，特别是 walk、mappages 和 kvmalloc 等函数。
    • 使用调试工具如 gdb 或 QEMU 的调试功能，逐步执行代码，观察页表和内存的变化。
  3. 动手实践：
    • 尝试修改 xv6 的内存管理代码，实现新的功能或优化现有实现。例如：
      • 实现更高效的内存分配算法。
      • 添加对大页表的支持，减少页表的层次。
      • 优化页面错误处理程序，提高性能。
  4. 重复巩固知识点：
    • 对于复杂的概念，如分页模型和页表结构，需要多次复习和练习，确保能够熟练掌握。
    • 通过编写小的测试程序或实验，验证对内存管理的理解。

3.0 为什么需要页表

正如chapter2所说，每个进程都有自己独立的内存和地址空间。

这也就要求我们实现一定的内存强隔离，让进程之间不会相互影响。

但是，对于每个进程，我们不能都赋予一个定值的内存大小，这样吃大锅饭的行为会造成小进程的资源浪费，和大进程的资源不足。

页表是一种数据结构，就好像电话本一样，记录了其上所有表的地址。

页表使操作系统能够以 4096 ( 2 12 ) 字节对齐块的粒度控制虚拟到物理地址转换。

它们允许 xv6 隔离不同进程的地址空间并将它们复用到单个物理内存上。页表是一种流行的设计，因为它们提供了一定程度的间接性，允许操作系统执行许多技巧。

3.1 Paging hardware

CPU中执行指令使用的是虚拟地址。

RAM中执行内存操作使用的是物理地址

RISC-V 页表硬件通过将每个虚拟地址映射到物理地址来连接这两种地址。

虚拟地址到物理地址的实现

RISCV是64位机器，地址也就是64位。

在sv39配置中，我们只使用低39位，高25位不使用。

RISC-V 页表逻辑上是 2^27 (134,217,728) 的数组 page table entries(PTEs) 。

每个 PTE 包含一个 44 位物理页号 (PPN) 和一些标志。

分页硬件通过使用 39 位中的高 27 位索引到页表中找到 PTE 来翻译虚拟地址，并制作一个 56 位物理地址，其高 44位来自 PTE 中的 PPN，其低 12 位被复制来自原始虚拟地址Offset。

PTE = PPN + flags

PTE的标志位

flags这些标志位告诉分页硬件如何允许使用关联的虚拟地址。

RISC-V 虚拟和物理地址，具有简化的逻辑页表

分级页表页

页表作为三层树存储在物理内存中。树的根是一个 4096 字节的页表页，包含 512 个 PTE，其中包含树的下一级页表页的物理地址。每个页面都包含树中最终级别的 512 个 PTE。分页硬件使用这27 位中的前 9 位来选择根页表页中的 PTE，中间 9 位来选择树的下一级页表页中的 PTE，最后 9 位来选择期末 PTE。

如果转换地址所需的三个 PTE 中的任何一个不存在，则分页硬件会引发 page-fault

exception ，将其留给内核来处理异常（请参阅第 4 章）。

对于分级页表页，我们可以与三级缓存一起理解，都是减少复杂性的结果。

但三级结构的潜在缺点是 CPU 必须从内存加载三个 PTE 来执行加载/存储指令中的虚拟地址到物理地址的转换。为了避免从物理内存加载 PTE 的成本，RISC-V CPU 将页表条目缓存在 Translation**Look-aside Buffer (TLB) 。

对于不同进程，如何实现页表切换

为了告诉 CPU 使用页表，内核必须将根页表页的物理地址写入 satp 寄存器。CPU 将使用其自己的 satp 指向的页表来转换后续指令生成的所有地址。每个 CPU 都有自己的satp ，以便不同的 CPU 可以运行不同的进程，每个进程都有一个由自己的页表描述的私有地址空间。

虚拟地址到物理地址的硬件机制

3.2 内核地址空间

在chapter2中，我们提到，进程拥有独立的地址空间。

分别是在用户空间和系统空间之中，所以我们也需要使用cpu来为进程维护页表状态。

内核使用“直接映射”获取 RAM 和内存映射设备寄存器；即将资源映射到等于物理地址的虚拟地址。例如，内核本身在虚拟地址空间和物理内存中都位于 KERNBASE=0x80000000。

内核本身也需要运行在虚拟地址空间中，但它需要能够直接访问物理内存。

通过直接映射，内核可以将自身加载到虚拟地址空间的某个固定位置（如 KERNBASE=0x80000000），同时这个虚拟地址空间直接对应物理内存的某个区域。

如何将内核虚拟地址映射到物理地址

有几个未直接映射的内核虚拟地址：

  • trampoline 页

    • 它映射在虚拟地址空间的顶部；
    • 用户页表具有相同的映射。
    • 物理页（保存 trampoline 代码）在内核的虚拟地址空间中映射两次：一次在虚拟地址空间的顶部，一次是直接映射。

    在用户空间和内核之间共享一个只读区域的数据来加速某些系统调用。这消除了在执行这些系统调用时需要跨越内核边界的需要。

  • 内核堆栈页

    • 每个进程都有自己的内核堆栈，该堆栈被映射到高位，以便在其下方xv6 可以留下未映射的 guard page 。
    • 保护页面的 PTE 无效（即 PTE_V 未设置），因此如果内核溢出内核堆栈，很可能会导致异常并且内核会出现 Panic。如果没有保护页，溢出的堆栈将覆盖其他内核内存，从而导致不正确的操作。Panic 崩溃是更好的选择。

3.3 代码：创建地址空间

1. xv6 虚拟内存管理的核心代码

xv6 中与虚拟内存相关的代码主要集中在 kernel/vm.c 文件中。核心数据结构是 pagetable_t，它是一个指向 RISC-V 根页表页的指针，可以表示内核页表或某个进程的用户页表。

2. 核心功能

  • walk 函数：用于查找虚拟地址对应的页表项（PTE）。它模拟 RISC-V 的分页硬件，逐级遍历页表，直到找到目标虚拟地址的 PTE。如果 PTE 无效且设置了分配标志（alloc），它会分配新的页表页并将其地址写入 PTE。
  • mappages 函数：用于安装新的虚拟地址到物理地址的映射。它会逐页处理虚拟地址范围，并为每个虚拟地址调用 walk 来查找或创建 PTE，然后设置 PTE 的权限和物理页号。

3. 内核页表的初始化

在 xv6 启动的早期阶段，main 函数会调用 kvminit 来初始化内核的页表：

  • kvmmake：负责创建内核页表。它首先分配物理内存页来保存根页表页，然后调用 kvmmap 安装内核所需的地址映射，包括内核代码、数据、物理内存（高达 PHYSTOP）以及设备内存范围。
  • proc_mapstacks：为每个进程分配内核堆栈，并调用 kvmmap 将堆栈映射到虚拟地址空间，同时为无效的堆栈保护页留出空间。

4. 页表映射的实现

  • kvmmap：调用 mappages 来安装虚拟地址到物理地址的映射。它逐页处理虚拟地址范围，并为每个虚拟地址调用 walk 来查找或创建 PTE，然后设置 PTE 的权限和物理页号。
  • walk：逐级遍历页表，使用虚拟地址的高位来索引页表项。如果 PTE 无效且设置了分配标志，它会分配新的页表页，并将物理地址写入 PTE。

5. 直接映射的依赖

xv6 的内核虚拟地址空间通过直接映射的方式访问物理内存。例如：

  • 当 walk 函数遍历页表时，它会从 PTE 中提取下一级页表的物理地址，并直接将其作为虚拟地址使用，因为内核的虚拟地址空间与物理内存是直接映射的。

6. 内核页表的安装

  • kvminithart：将内核页表的根页表页物理地址写入 satp 寄存器，使 CPU 开始使用内核页表进行地址转换。由于内核使用恒等映射，虚拟地址可以直接映射到物理地址。

7. TLB 管理

每个 RISC-V CPU 都有一个翻译后备缓冲区（TLB），用于缓存页表条目。当 xv6 修改页表时，必须通知 CPU 使相应的 TLB 条目失效，以防止旧的映射被错误使用：

  • sfence.vma 指令：用于刷新当前 CPU 的 TLB。xv6 在以下场景中使用该指令：
    1. 在 kvminithart 中，安装内核页表后刷新 TLB。
    2. 在切换到用户页表的 trampoline 代码中，返回用户空间前刷新 TLB。
    3. 在修改页表前，刷新 TLB 以确保所有未完成的加载和存储操作完成。

8. 地址空间标识符（ASID）

RISC-V 支持地址空间标识符（ASID），用于区分不同进程的地址空间，从而避免刷新整个 TLB。然而，xv6 并没有使用这一功能。

总结

xv6 的虚拟内存管理通过 kernel/vm.c 文件中的核心函数（如 walk 和 mappages）实现页表的初始化和映射。内核页表在启动时通过 kvminit 和 kvmmake 初始化，并通过直接映射的方式访问物理内存。TLB 的刷新通过 sfence.vma 指令实现，以确保页表修改后地址转换的正确性。xv6 的设计简洁高效，尽管没有使用 ASID 功能，但仍然能够有效地管理虚拟内存和地址空间。

3.4 物理内存分配

内核必须在运行时为页表、用户内存、内核堆栈和管道缓冲区分配和释放物理内存。xv6 使用内核末尾和 PHYSTOP 用于运行时分配。它一次分配和释放整个 4096 字节页面。它通过将链接列表穿过页面本身来跟踪哪些页面是空闲的。分配包括从链表中删除页面；释放包括将释放的页面添加到列表中。（freelist也就是加入一个空闲页面的链表之中)

3.5 代码：物理内存分配器

1
2
3
4
5
6
7
8
struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

分配器的数据结构是可用于分配的物理内存页的空闲列表。

每个空闲页面的列表元素是 struct run

内存的分配过程

  1. main函数调用kinit 来初始化分配器（kernel/kalloc.c:27）。
  2. kinit 将空闲列表初始化为内核结束到 PHYSTOP 之间的所有页面。
  3. kinit 调用 freerange，通过逐页调用 kfree 将内存添加到空闲列表中。
    1. 由于页表项（PTE）只能引用 4096 字节边界对齐的物理地址（即 4096 的倍数），freerange 使用 PGROUNDUP 来确保只释放对齐的物理地址。

对齐的物理地址及其重要性

对齐的物理地址是指物理地址的值是某个特定值（如4096字节）的整数倍。在计算机系统中，特别是涉及到内存管理和页表操作时，地址对齐是一个重要的概念。例如，在RISC-V架构中，页表项（PTE）只能引用按4096字节边界对齐的物理地址。

为什么只释放对齐的物理地址

  1. 页表管理的需要
    在现代操作系统中，物理内存通常以页（Page）为单位进行管理，每一页的大小通常是4096字节。页表项（PTE）用于将虚拟地址映射到物理地址，而PTE只能指向按4096字节对齐的物理地址。因此，操作系统在分配和释放内存时，必须确保物理地址是对齐的，以符合页表项的要求。
  2. 简化内存管理
    使用对齐的物理地址可以简化内存分配器的设计。例如，xv6的物理内存分配器通过freerange函数将内存添加到空闲列表中，而freerange使用PGROUNDUP宏来确保只处理对齐的物理地址。这样可以避免处理非对齐地址带来的复杂性，同时确保内存分配和释放的高效性。
  3. 硬件和性能优化
    硬件通常对地址对齐有特定要求，对齐的地址可以提高内存访问的效率。非对齐地址可能导致额外的硬件开销，甚至可能引发错误。因此，操作系统在设计内存管理机制时，会优先使用对齐的地址。
  4. 避免错误和未定义行为
    如果释放的物理地址不是对齐的，可能会导致页表项指向无效的物理地址，从而引发硬件错误或未定义行为。为了避免这些问题，操作系统在设计内存管理机制时，会确保只释放对齐的物理地址。

总结

对齐的物理地址是内存管理中的一个重要概念，它确保了页表项能够正确地引用物理内存，并简化了内存分配器的设计。在xv6中，freerange函数通过PGROUNDUP宏确保只释放对齐的物理地址，从而满足页表项的要求并优化系统性能。

3.6 进程地址空间

进程的用户地址空间及其初始堆栈。

1. 进程地址空间的隔离与切换

  • 每个进程的独立页表：在 xv6 中，每个进程都有一个独立的页表。页表的作用是将虚拟地址映射到物理地址。
  • 进程切换与页表切换：当 xv6 在不同进程之间切换时，它不仅切换进程的上下文，还会切换页表。这意味着每个进程都有自己独立的地址空间，进程之间无法直接访问彼此的内存。

2. 用户内存的布局与寻址范围

  • 用户内存的起始地址：每个进程的用户内存从虚拟地址 0 开始。
  • 寻址范围：用户内存的上限由 MAXVA 定义（在 kernel/riscv.h:360 中）。理论上，xv6 的进程可以寻址高达 256 GB 的内存空间。
  • 实际使用：尽管寻址范围很大，但大多数进程并不会使用整个用户地址空间。未使用的页表项（PTE）的 PTE_V 标志会被清零，表示这些地址空间未被映射到物理内存。

3. 用户内存的动态分配

  • 分配物理页面：当进程请求更多用户内存时，xv6 使用以下步骤分配内存：
    1. 调用 kalloc：通过内核的物理内存分配器 kalloc 分配物理页面。
    2. 更新页表：为新分配的物理页面在进程的页表中添加页表项（PTE），并设置以下标志：
      • PTE_W（可写）
      • PTE_X（可执行）
      • PTE_R（可读）
      • PTE_U（用户模式可访问）
      • PTE_V（页表项有效）
  • 页表的作用：
    • 隔离性：不同进程的页表将用户地址映射到不同的物理页面，确保每个进程的用户内存是私有的。
    • 虚拟地址连续性：进程看到的内存是虚拟地址从 0 开始的连续空间，但实际的物理内存可以是不连续的。
    • 共享页面：内核在用户地址空间的顶部映射了一个包含 trampoline 代码的页面。这个页面在所有进程的地址空间中都可见，但只占用一个物理页面。

4. 用户内存布局的详细结构

  • 栈的布局：
    • 栈的大小：用户栈是一个单独的页面（通常为 4KB）。
    • 栈的初始内容：由 exec 系统调用创建，栈的顶部包含以下内容：
      1. 命令行参数字符串：存储用户输入的命令行参数。
      2. 指针数组：指向命令行参数字符串的指针数组。
      3. 启动参数：包含 argc 和 argv，使得程序可以从 main 函数开始运行，就好像调用了 main(argc, argv)。
  • 栈溢出保护：
    • 保护页：为了防止用户栈溢出，xv6 在栈的下方放置了一个不可访问的保护页。
    • 保护机制：通过清除保护页的 PTE_U 标志，使其对用户模式程序不可访问。
    • 异常处理：如果栈溢出，进程尝试访问保护页时，硬件会触发页面错误异常（page-fault exception）。
    • 现实系统的处理方式：在真实操作系统中，可能会在栈溢出时自动分配更多内存，而不是直接触发异常。

5. 页表的其他应用

  • 内核代码映射：内核在用户地址空间的顶部映射了一个包含 trampoline 代码的页面。这个页面在所有进程的地址空间中都可见，但只占用一个物理页面。
  • 内存隔离与共享：通过页表，xv6 实现了进程之间的内存隔离，同时允许某些页面（如 trampoline 页面）在多个进程之间共享。

总结

xv6 通过为每个进程维护独立的页表，实现了进程之间的内存隔离和地址空间管理。用户内存从虚拟地址 0 开始，理论上可以寻址高达 256 GB 的内存空间，但实际上大多数进程只使用其中的一部分。页表项（PTE）的标志位用于控制页面的访问权限。用户栈是一个单独的页面，初始内容由 exec 创建，栈的下方有一个不可访问的保护页用于防止栈溢出。通过这些机制，xv6 在保证内存隔离的同时，也实现了内存的高效利用和保护。

3.7 代码：sbrk

sbrk 是一个进程用来收缩或扩展其内存的系统调用。该系统调用由 growproc 函数实现（kernel/proc.c:253）。

  • growproc 根据参数 n 是正数还是负数，调用 uvmalloc 或 uvmdealloc。
    • uvmalloc（kernel/vm.c:221）使用 kalloc 分配物理内存，并通过 mappages 将页表项（PTEs）添加到用户页表中。
    • uvmdealloc 调用 uvmunmap（kernel/vm.c:166），后者使用 walk 查找 PTEs，并通过 kfree 释放它们指向的物理内存。

xv6 使用进程的页表不仅是为了告诉硬件如何映射用户虚拟地址，而且作为记录分配给该进程的物理内存页面的唯一记录。这就是为什么释放用户内存（在 uvmunmap 中）需要检查用户页表的原因。

3.8 代码：exec

  • 功能：exec 用于创建地址空间的用户部分，从文件系统中的文件初始化用户空间。
  • 核心步骤：
    1. 检查文件格式：通过 ELF 头的“魔数”验证文件是否为有效的 ELF 二进制文件。
    2. 分配页表：通过 proc_pagetable 创建一个没有用户映射的新页表。
    3. 加载程序段：使用 uvmalloc 分配内存，并通过 loadseg 将 ELF 段加载到内存中。
    4. 初始化用户栈：分配一个栈页，将参数字符串复制到栈顶，并在栈末尾放置空指针。
    5. 保护机制：在栈页下方放置一个不可访问的页面，防止程序栈溢出。
  • 安全性问题：
    • ELF 文件中的地址可能指向内核空间，导致内核崩溃或安全漏洞。
    • xv6 通过检查溢出等手段避免这些问题，但在复杂场景下仍可能存在漏洞。

3.9 现实世界中的考虑

  • 分页硬件的使用：xv6 使用分页硬件进行内存保护和映射，但相对简单，缺乏高级特性（如页错误处理）。
  • 物理地址映射问题：xv6 假设地址 0x8000000 处有物理 RAM，这在真实硬件上可能导致问题，因为真实硬件的物理地址布局是不可预测的。
  • 内存管理优化：
    • RISC-V 支持“超级页”，适用于大内存机器，可减少页表操作开销。
    • xv6 缺乏动态内存分配器（如 malloc），限制了复杂数据结构的使用。
    • 现实中的内核需要支持多种大小的内存分配，以提高效率和灵活性。
文章作者: MIKA
文章链接: https://erinmi4.github.io/2025/02/17/cao-zuo-xi-tong-lec3/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 MIKA !
操作系统 MIT6.s081
  目录