bbbGan

Virtual Memory in xv6

2023/04/02 xv6 共 4429 字，约 13 分钟

page table in xv6

RISC-V可以通过设置SATP寄存器选择模式Sv39（Supervisor mode 39-bit），是一个3级页表，每一个页表大小为4096字节，即一个物理页，可以存放 4096 / 8 个PTE，虚拟地址前 25位为保留位，在这之后 27 位每9位代表一级页表的页内偏移，PTE中 10 - 53 位代表 下一级页表的物理页面，最后10位为flag，描述了该PTE的·一些性质，比如访问权限。在页表机制工作的时候，只需要把第一级页表的物理地址载入SATP寄存器中即可。

指令都是虚拟地址，虚拟地址转为物理地址由硬件MMU完成。每个CPU都有MMU、TLB、SATP，每次切换进程的时候需要flush TLB，如果MMU在进行地址转换的时候缺少PTE，会触发page-fault异常。

pagetable.png

在XV6中，内核页表的布局如下所示，在内核中页表中，0x80000000以下为设备地址，KERNERLBASE - PHYSTOP为 128M。

直接映射简化了读取或写入物理内存的内核代码。但有一部分也不是直接映射的

  • 蹦床页面(trampoline page)。它映射在虚拟地址空间的顶部；用户页表具有相同的映射。
  • 内核栈页面。每个进程在内核页表都有自己的内核栈，它将映射到偏高一些的地址，这样xv6在它之下就可以留下一个未映射的保护页(guard page)。保护页的PTE是无效的（也就是说PTE_V没有设置），所以如果内核溢出内核栈就会引发一个异常，内核触发panic。如果没有保护页，栈溢出将会覆盖其他内核内存，引发错误操作。
  • 虽然内核通过高地址内存映射使用内核栈，是它们也可以通过直接映射的地址进入内核。另一种设计可能只有直接映射，并在直接映射的地址使用栈。然而，在这种安排中，提供保护页将涉及取消映射虚拟地址，否则虚拟地址将引用物理内存，这将很难使用。

kernellayout

XV6的内存分配很简单，本来是硬件的配置解析有多少内存可以用，但是直接假定有128M内存，把图中的Free memory按页为单位链在一个，作为 kalloc 给系统使用。

每个进程有自己的进程空间，XV6进程页表和内核页表是分离。

首先，不同进程的页表将用户地址转换为物理内存的不同页面，这样每个进程都拥有私有内存。第二，每个进程看到的自己的内存空间都是以0地址起始的连续虚拟地址，而进程的物理内存可以是非连续的。第三，内核在用户地址空间的顶部映射一个带有蹦床（trampoline）代码的页面，这样在所有地址空间都可以看到一个单独的物理内存页面。

userlayout

内核页表的布局是靠什么决定的呢？

内核页表的布局由kernel.ld链接器脚本实现，下面是其中文本节的实现

.text : {
*(.text .text.*)  # 把所有以.text开头的节全部合并
. = ALIGN(0x1000); # 将当前地址调整为0x1000的倍数
 _trampoline = .;  # 定义一个名为_trampoline的符号，它的值就是当前地址（也就是.text段的结束地址）
 *(trampsec)
 . = ALIGN(0x1000); # 匹配所有名为trampsec的节，将它们合并到.text段中。
 ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page");
 PROVIDE(etext = .); # 定义一个名为etext的符号，它的值就是当前地址。etext通常用于标记.text段的结束地址，以便于程序可以在运行时得到它的值。
}

进程页表的布局靠什么决定呢？

进程页表的布局在实现 proc_pagetable 和 exec 的时候决定。而根本上来说，其实是根据ELF的布局决定的，先载入ELF，然后载入栈和guard page。

第一个进程如何启动的？

void
userinit(void)
{
  struct proc *p;
  p = allocproc(); //  alloc 一个进程
  initproc = p;
  uvminit(p->pagetable, initcode, sizeof(initcode)); 
  // 把代码 `exec("/init")`的机器码形式加载到 `p->pagetable`的 0地址开始的位置。
  p->sz = PGSIZE;
  p->trapframe->epc = 0;      // 用户程序计数器
  p->trapframe->sp = PGSIZE;  // 用户栈指针

  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");
  p->state = RUNNABLE;
  release(&p->lock);
}

配置了之后在 scheduler中启动该进程，返回到用户空间，开始执行，然后就会跳转到用户空间的 init.c的main函数中，打开0，1，2文件描述符之后，exec到可执行文件 sh

Real World

待补充：没有很完善，阅读Linux源码后进行补充

地址空间随机化

（Address Space Layout Randomization，ASLR）在加载程序时，在程序的基地址上加上一个随机的偏移量，然后再映射到物理地址空间中。这个偏移量可以使用伪随机数生成器生成，保证每次随机的结果都不同。

内存分配

伙伴系统算法（buddy system）：把所有的空闲页框分为11块链表，每个链表分别包含1-2^10个连续的页框，分配的时候从小到大查找，找到刚好满足的大小，释放的时候把2快同样大小的内存进行迭代合并。（合并之后再次尝试合并）

每CPU页框高速缓存：每CPU页框高速缓存通过为每个 CPU 维护一个本地的页帧高速缓存来避免这种竞争。当一个 CPU 请求分配一个页帧时，它会首先检查自己的本地高速缓存，如果本地高速缓存中有空闲的页帧，则直接从本地高速缓存中分配。

slab分配器

SLAB分配器是Linux内核中的一种内存分配器，用于分配内核中的小型、重复使用的对象。它的目标是提高内存分配的效率，同时减少内存碎片的产生。

SLAB分配器在分配对象时采用了一种双层缓存的策略。每个缓存都包含了一个空闲对象列表和一个高速缓存，高速缓存中存储了最近使用的对象。当一个对象被释放时，它会被添加到空闲对象列表中，而不是立即返回到内存池中。当需要分配一个新的对象时，SLAB分配器首先检查高速缓存中是否有可用的对象，如果有，则直接返回该对象，否则它会从空闲对象列表中获取一个对象并添加到高速缓存中。

kmalloc分配器

kmalloc是Linux内核中的一种内存分配器，专门用于分配内核中的小型、重复使用的对象。与malloc不同，kmalloc使用物理上连续的内存块来分配内存，这可以避免内存碎片的产生，并且在内核空间中更为高效。

进程地址空间

Linux内核中内核被映射在高位置，而用户空间被映射在低位置，用户空间包括了进程的代码、数据、堆、栈等。以及还有xv6没有的共享库映射区域：共享库映射区域是将共享库映射到进程地址空间中的区域。

线性区，红黑树

在线性区（vm_area_struct）是Linux内核中用于表示进程虚拟地址空间的数据结构之一。在线性区中，包含了一段连续的虚拟地址范围，它描述了内存区域的属性（如可读可写、私有共享等），并指向一个页表，用于将虚拟地址转换为物理地址。线性区通常会组成一颗红黑树（rb_root），以便快速查找和插入区域。

回收页框PFRA

PFRA（Page Frame Reclamation Algorithm）是一个Linux内核中的页面回收算法，它用于在系统内存紧张时回收进程占用的物理内存页面，以便系统可以将这些页面分配给其他进程使用。

PFRA算法的核心思想是通过优先回收那些最有可能被重新分配的页面来提高内存的利用率。具体来说，PFRA算法通过维护一个“活跃页面列表”（Active Page List）和一个“非活跃页面列表”（Inactive Page List）来进行页面的管理。活跃页面列表包含那些最近被访问过的页面，而非活跃页面列表则包含那些很久没有被访问过的页面。当系统需要回收页面时，PFRA算法会首先从非活跃页面列表中回收页面，因为这些页面最有可能被重新分配给其他进程使用。如果非活跃页面列表中的页面不足以满足回收需求，算法会继续从活跃页面列表中回收页面。（LRU）

侧信道攻击，如Meltdown和Spectre

Meltdown和Spectre是两种广为人知的侧信道攻击，它们利用了现代处理器中的一个重要特性——指令执行时的乱序执行和分支预测机制，来泄露内核和其他进程的敏感数据。具体来说，这两种攻击方式都利用了处理器中的缓存侧信道，通过精心构造的恶意程序，让处理器在执行过程中访问不受控制的内存地址，并利用缓存的工作原理来推断出这些内存地址中存储的敏感数据。

交换空间限制分配页面的虚拟页面总数

在Linux中，分配页面的虚拟页面总数是受到交换空间大小的限制的。当系统内存不足时，Linux会将一部分内存中的数据交换到交换空间中，并将这部分内存释放出来。但是，如果虚拟页面总数过大，会导致交换空间被快速耗尽，从而降低系统的性能和稳定性。因此，Linux内核会根据交换空间的大小来限制虚拟页面总数，以确保系统的稳定性和性能。

Labs

打印页表

​ 这个很简单，就是遍历而已，像walk函数一样遍历。

添加页表

​ 给每个进程添加一个内核页表，并且把用户页表映射到内核页表中。

  • 首先在proc结构体中添加字段，然后在allocproc中把内核映射到新建页表 kpagetable，在释放该页表的时候需要注意不要释放物理内存，只是释放页表，修改 scheduler（） 以将进程的内核页表加载到 核心的SATP寄存器
  • 在更改用户页表的同时，把相同的映射到内核页表中，同样的只是相同的映射，共享物理页，同时需要控制长度，不能超过PLIC。但是可以超过 CLINT，因此 CLINT不能映射到内核页表。
  • 在释放页表的时候选择遍历去释放，而不是前面映射了什么释放什么，因为可能在运行的时候会有新的页表映射，因此需要全部遍历释放。

Copy-on-Write

  • 需要选取PTE中的保留位定义标记一个页面是否为COW Fork页面的标志位
  • 给每一个页加上一个引用计数，在复制的时候增加引用计数，在kree中减少引用计数，如果引用计数为0的时候，表示可以回收。
  • 不为子进程分配内存，而是使父子进程共享内存，但禁用PTE_W，同时标记PTE_F，记得调用kaddrefcnt增加引用计数
  • 修改usertrap，当出现错误的时候，调用对应的页面错误处理函数，这里的任务分配页面复制内容，然后 ret

Lazy Allocation

  • 在调用sbrk的时候不分配实际页面，只是增加地址。
  • 在使用地址的时候会触发中断，进入中断处理函数，在这里进行判断一下是不是有效地址，如果有效，分配新的地址即可

Search

    Table of Contents