Xv6

本文是笔者在学习 MIT 6.1810 2022 Fall 阅读 xv6 文档时所写,大部分是将原文翻译,笔者尽可能加入自己的理解并排版,应该会持续更新直到文档读完

Chapter 1 Operating system interfaces

xv6 实现的 Unix kernel 的服务和系统调用的子集

在 user 目录下可查看程序源码

System call Description
int fork() 创建一个进程,返回子进程的 PID
int exit(int status) 结束当前进程,status 返回给 wait()
int wait(int *status) 等待一个子进程 exit,exit 的 status 在 *status中,返回子进程 PID,没有子进程返回 -1
int kill(int pid) 结束 PID 对应的进程,返回 0 或 -1
int getpid() 返回当前进程的 PID
int sleep(int n) 暂停 n 个时钟
int exec(char *file, char *argv[]) 加载文件并使用参数执行,仅在错误时返回
char *sbrk(int n) 内存增加 n 字节,返回新内存的首地址
int open(char *file, int flags) 打开文件,flags 表示读写,返回一个 fd
int write(int fd, char *buf, int n) 从 buf 向 fd 写 n 字节,返回 n
int read(int fd, char *buf, int n) 从 fd 读 n 字节向 buf 写入,返回读的字节数
int close(int fd) 释放 fd
int dup(int fd) 返回与 fd 相同文件的一个新的 fd
int pipe(int p[]) 创建一个管道,将读写 fd 放入 p[0] 和 p[1]
int chdir(char *dir) 改变当前目录
int mkdir(char *dir) 创建一个目录
int mknod(char *file, int, int) 创建一个设备文件
int fstat(int fd, struct stat *st) 读取文件信息放入 st
int stat(char *file, struct stat *st) 读取文件信息放入 st
int link(char *file1, char *file2) 为 file1 创建另一个名字 file2,即硬链接
int unlink(char *file) 删除一个文件

如果没有另外说明,系统调用返回 0 为正常,返回 -1 为错误

进程和内存

父子进程的内存关系

I/O 和文件描述符

管道

p[0] 为读端,p[1] 为写端

如果读端没有数据,read 会等待数据写入或等待指向写端的所有 fd 关闭,后者类似到文件结尾, read 会返回 0

如果 read 到读端,会一直等待

shell 可以用 | 符号实现管道

grep fork sh.c | wc -l 将 | 左边的结果通过管道流向右边

多 | 可以创建进程树

  1. 管道可以自己清理自己
  2. 可以通过任意长度的数据流
  3. 管道可以并行执行

文件系统

#todo

真实世界

Unix 系统调用接口通过 POSIX 标准进行标准化

Chapter 2 Operating system organization

三个要求

  • 多路复用
  • 隔离
  • 交互

抽象物理资源

每个应用程序直接访问物理资源

  • 效率高
  • 需要应用程序之间可信且没有错误

因此需要进行强隔离,同时也会提供便利

禁止应用程序直接访问敏感的硬件资源,将资源抽象为服务

用户/管理者模式,系统调用

强隔离需要应用程序和操作系统之间有硬边界

CPU 能提供硬件支持

RISC-V 的 CPU 有三种模式:机器模式、管理者(supervisor)模式、用户模式

  • 机器模式
    • 执行的指令具有完全特权
    • 主要用具配置计算机,运行一段代码后会进入内核模式
  • 管理者模式
    • CPU 可执行特权指令
      • 启用、禁用终端
      • 读写页表寄存器
  • 用户模式
    • CPU 不能执行特权指令
      • 如果尝试执行,CPU 会切换到管理者模式,并且杀死应用程序
    • 通过系统调用来调用内核函数
      • 系统调用会跳转到内核指定的入口点
      • CPU 从用户模式切换到管理者模式
      • 内核可以验证系统调用的参数是否合理,决定是否进行请求的操作

内核和管理者模式似乎有点分不清?

笔者的理解:管理者模式是 RISC-V 的 CPU 定义的,相对于用户模式多了一些特权;内核是相对用户代码而言,运行在不同的模式下。模式对应着身份,内核和用户代码对应着一个实体

内核架构

宏内核设计

缺点:操作系统不同部分之间的接口复杂,编写代码容易出错

微内核设计

最大限度地减少内核模式下运行的操作系统代码数量,在用户模式下执行操作系统的大部分功能

xv6 kernel 代码架构

文件 描述 文件 描述
bio.c 文件系统的磁盘块缓冲 proc.c 进程和调度
console.c 连接到用户键盘和屏幕 sleeplock.c 放弃 CPU 的锁
entry.S 第一次启动的指令 spinlock.c 不放弃 CPU 的锁
exec.c exec() 系统调用 start.c 机器模式早期启动代码
file.c 文件描述符 string.c C 字符串和字节数组代码库
fs.c 文件系统 swtch.S 线程切换
kalloc.c 物理页分配器 syscall.c 系统调用的调度
kernelvec.S 处理来自内核的陷阱,定时器中断 sysfile.c 文件相关的系统调用
log.c 文件系统日志记录和崩溃恢复 sysproc.c 进程相关的系统调用
main.c 启动阶段控制其他模块的初始化 trampoline.S 切换用户/内核模式的汇编
pipe.c 管道 trap.c 处理陷阱和中断并从中返回
plic.c RISC-V 中断控制器 uart.c 串口控制台设备驱动
printf.c 格式化输出到控制台 virtio_disk.c 磁盘设备驱动
vm.c 管理页表和地址空间 defs.h 模块间接口的定义

进程

地址空间

每个进程有一个单独的页表,定义了进程的地址空间

  • 有许多因素限制了进程地址空间的最大值

    • RISC-V 的指针为 64 位
    • 在页表中查找虚拟地址时,硬件仅使用低 39 位
    • xv6 只使用 38 位 #why
    • 因此最大地址位 2^38^ - 1 = 0x3fffffffff,即 MAXVA(在 kernel/risc.h 中定义)、
  • 在地址空间的顶部保留了一页用作 trampoline(跳板、蹦床),一页用作映射进程的 trapframe(陷阱帧),xv6 用这两个页面进入和退出内核

    • trampoline 包含进入和退出内核的代码
    • trapframe 映射用于保存和恢复用户进程的状态

进程状态

xv6 内核维护每个进程的状态,存放到 proc 结构体中(kernel/proc.h

最重要的部分是页表、内核栈、运行状态

p->state 表示进程状态(分配、准备运行、等待IO、正在退出)

p->pagetable 保存页表,还用作存储进程内存的物理页地址的记录

栈空间

  • 每个进程有两个栈:用户栈和内核栈(p->kstack)
  • 在执行用户指令时,只有用户栈在使用,内核栈为空
  • 当进入内核模式(系统调用或中断),内核代码会在内核栈上执行,用户栈不变
  • 内核栈是独立的,即使进程破坏了用户栈,内核也可以执行

启动 xv6,第一个进程和系统调用的代码

  1. RISC-V 开机时,会自行初始化,运行存储在 ROM 中的引导加载程序
  2. 引导加载程序将 xv6 内核加载到内存 0x80000000 中,因为 0 ~ 0x80000000 之间包含 IO 设备(RISC-V 在分页硬件禁用和虚拟地址直接映射到物理地址条件下开始)
  3. 在机器模式下,从 _entry 开始执行 xv6
    • _entry 的指令设置一个栈,以便 xv6 运行 C 代码
    • xv6 在 kernel/start.c 中声明一个初始栈 stack0 的空间
    • _entry 的代码将栈顶寄存器 sp 加载到 stack0 的顶部 stack0+0x1000
    • 接下来调用 kernel/start.c 中的代码
  4. start 函数
    • 先在机器模式执行配置代码
      • 将 main 的地址写入 mepc 寄存器作为 mret 返回地址
      • 将所有中断和异常委托给内核模式
      • 将 0 写入 satp 页表寄存器,禁用内核模式下的虚拟内存转换
      • 对时钟芯片编程来生成计时器中断
    • 然后通过 mret 指令切换到内核模式,进入 main 函数
      • mret 常用于在内核模式调用进入机器模式后返回到内核模式
      • start 会将前一个模式设置为内核模式,以便符合 mret 的条件
  5. main 函数
    • 初始化控制台
    • 初始化物理页分配器
    • 创建内核页表
    • 加载启动页面
    • 初始化进程表
    • 根据内核位置设置代码(设置 ecall 的位置?)
    • 初始化中断控制 PLIC
    • 通过中断请求 PLIC 访问设备
    • 初始化 buffer 缓存
    • 初始化 inode 缓存
    • 初始化文件系统
    • 初始化磁盘
    • 进入 userinit 函数
  6. userinit 函数
    • 创建第一个进程
    • 执行用 RISC-V 编写的小程序,使用第一个系统调用
    • user/initcode.S 中把 SYS_exec 系统调用号传给 a7 寄存器,然后调用 ecall 进入内核

安全模型

#todo

真实世界

大多数操作系统采用了进程的概念,但是现代操作系统的进程支持多个线程,以允许单个进程利用多个 CPU,潜在地更改了接口(如 Linux 的 clone,fork 的一种变体),来控制线程共享的各个方面

Chapter 3 Page tables

#todo

分页硬件

#todo

内核地址空间

#todo

代码:创建一个地址空间

大多数处理地址空间和页表的代码在 kernel/vm.c

数据结构 pagetable_t,是指向 RISC-V 根页表的指针 typedef uint64 *pagetable_t,它可以是内核或每个进程的页表

  • 中心函数是 walk 和 mappages
    • walk:从页表中查找虚拟地址对应的 PTE
    • mappages:为新映射安装 PTE
  • kvm 开头的函数操作内核页表
  • uvm 开头的函数操作用户页表
  • copyincopyout 用于用户与内核之间传输数据

系统启动

一开始,main 调用 kvminit 来使用 kvmmake 创建内核页表,在此之前,地址直接映射到物理内存

然后调用 kvminithart 来安装内核页表,将根页表的物理地址写入 satp 寄存器,在此之后 CPU 会使用内核页表转换地址

kvmmake

  • 首先分配一页物理内存来保存根页表
  • 然后调用 kvmmap 来安装内核需要的 PTE
    • 包括内核的指令和数据,最高到 PHYSTOP 的物理内存,设备的内存范围
  • 然后调用 proc_mapstacks 给每个进程分配一个内核栈
    • 它调用 kvmmap 把每个栈映射到 KSTACK 生成的虚拟地址,留出了保护页的空间

kvmmap

  • 调用 mappages 安装 PTE

mappages

  • 它对每个虚拟地址先调用 walk 查找对应的 PTE 地址
  • 然后初始化 PTE 保存对应的 PPN 和 权限标志位

walk

  • 它对三级页表进行查询对应的 PTE
  • 若 PTE 无效且设置了 alloc 参数,walk 会分配一个新的页面,并把物理地址放入 PTE
  • 最后返回第三级页表的 PTE 地址

物理内存分配

xv6 在内核结尾与 PHSYTOP 之间分配运行时内存,一次分配和释放 4KB

xv6 追踪哪些页面是 freed,通过建立一个链表

分配包括从链表中移除,释放包括将 freed 页加入从链表中

代码:物理内存分配器

分配器位于 kernel/kalloc.c 中

数据结构是一个 free 链表,每个元素是 struct run,链表由一个 spin lock 保护,锁调用 acquirerelease,链表和锁被包装在 kmem 结构体中

kernel/kalloc.c
1
2
3
4
struct {
struct spinlock lock;
struct run *freelist;
} kmem;

xv6 应该通过解析硬件的配置信息来决定有多少物理内存可用

main 函数调用 kinit 来初始化分配器

kinit

初始化 free 链表来保存 free memory 的每一页(kernel 末尾与 PHSYTOP 之间的内存空间)

kinit 调用 freerange 来对每一页调用 kfree 向 free 链表添加内存

freerange 使用 PGROUNDUP 确保物理地址对齐(类似向上取整)

kfree 会将释放的页面所有值设为 1,然后使用头插法将页面首地址加入 free 链表

进程地址空间

每个进程有一个单独的页表

Address section Permission
MAXVA trapline RX–
trapframe R-W-
unused
heap R-WU
stack R-WU
guard page
data R-WU
Page aligned unused
0 text R-XU

trampoline 和 trapframe 映射在高地址,用户模式不可访问

trampoline:在调用 ecall 时会跳转到这里

trapframe:在调用 ecall 时,用户进程的通用寄存器会保存在这里

代码:sbrk

系统调用 sbrk 用于进程增减内存大小,由 growproc 实现

growproc 根据 n 的正负,调用 uvmalloc 或 uvmdealloc

uvmalloc 调用 kalloc 分配物理内存,然后调用 mappages 向用户页表添加 PTE

uvmdealloc 调用 uvmunmap,uvmunmap 使用 walk 找到对应的 PTE 和 kfree 释放物理内存

代码:exec

exec 使用 namei 打开二进制文件,然后读取 ELF 头

一个 ELF 文件包含一个 ELF 头(struct elfhdr),一系列程序 section 头(struct proghdr),每个 struct proghdr 描述了程序必须加载到内存中的 section,xv6 程序有两个,一个指令,一个是数据

  • 第一步是检查文件是否是 ELF 文件,它从 4 字节的魔术数字开始(0x7F,’E’,’L’,’F’,或者 ELF_MAGIC)
  • 使用 proc_pagetable 分配一个没有用户映射的新页表,用 uvmalloc 给每个 ELF 段分配内存,用 loadseg 加载每个段到内存中,loadseg 使用 walkaddr 找到物理地址写入每个段。使用 readi 读取每个段
  • 分配并初始化一页用户栈,将参数字符串复制到栈顶,在 ustack 记录字符串指针,ustack 前三个是 fake 返回程序计数器,argc 和 argv
  • exec 会在栈页的下面放一个不可访问的页
    • 在准备新的内存镜像时,如果检测到一个错误(如无效的程序段),会跳转到 bad 标签,释放新的镜像,返回 -1。一旦镜像完成,exec 提交新的页表,释放旧的
  • exec 从文件指定的地址将数据加载到内存中,因此 exec 是有风险的,需要执行很多检查

Real world

真正的内存分配器需要处理小分配和大分配

Chapter 4 Traps and system calls

trap(陷阱)是让CPU 搁置普通指令的执行,并将控制权转移到处理该事件的特殊代码

  • 系统调用
  • 异常
    • 除以 0 或使用无效的虚拟地址等
  • 中断
    • 设备发出信号,如磁盘完成读写请求时

通常,trap 发生时执行的代码不久后都需要恢复,代码并不需要意识到发生了任何特殊情况

  • 异常处理
    1. trap 强制将控制权转移给内核
    2. 内核保存寄存器和其他状态
    3. 内核执行处理代码
    4. 内核恢复保存的寄存器和状态并从陷阱中返回
    5. 原始代码从它停止的地方恢复

Xv6 在内核中处理所有 trap,trap 不会传递给用户代码

隔离要求只有内核可以使用硬件设备,且内核是一种方便的机制,可以在多个进程之间共享设备,不互相干扰,这对于异常也有意义,xv6 通过杀死违规程序来处理用户空间的所有异常

Xv6 处理 trap 有四个阶段

  1. RISC-V CPU 进行硬件操作
  2. 一些为内核 C 代码做好准备的汇编指令
  3. 决定如何处理 trap 的 C 函数
  4. 系统调用或设备驱动程序服务例程

处理 trap 的代码(汇编或 C)被称为 handler

handler 的第一步通常用汇编语言编写,称为 vector

RISC-V trap 机制

寄存器

控制寄存器:内核可读写,用于告诉 CPU 怎么处理 trap

  • stvec:保存内核处理 trap 的地址,发生 trap 时会跳转到该地址
    • Supervisor Trap Vector
    • 用户模式下会指向内核代码的 usertrap
    • 内核模式下会指向内核代码的 kerneltrap
  • sepc:发生 trap 时保存当前的 pc,在使用 sret 指令时,会跳转到 sepc 指向的地址
    • Supervisor Exception Program Counter
    • sret:从 trap 返回
    • 内核可控制 sepc 让 sret 返回到适当的位置
  • scause:描述 trap 类型
    • Supervisor Trap Cause
    • 8 表示系统调用
    • 其他表示错误或者中断
  • sscatch:辅助作用,防止在保存用户寄存器前将其覆盖
    • 一般用来保存 a0
    • 在 xv6 的 2020 版本用来保存 trapframe 地址
  • sstatus:以 bitmap 形式保存一些控制信息
    • Supervisor Status
    • SPP:表示 trap 来自用户模式(0)还是管理者模式(1),并且用来告诉 sret 返回到哪个模式
    • SIE:表示是否允许设备中断,若为 0 则 RISC-V 会推迟设备中断

在机器模式下有一组类似的控制寄存器,xv6 只在定时器中断的情况下使用

处理 trap 前

下面是除 定时器中断 外的 trap

  1. 将 sstatus 的 SIE 位 置零
    • 如果是设备中断,不会继续下面的操作
  2. 将 pc 复制给 sepc
  3. 保存当前模式到 sstatus 的 SSP
  4. 设置 scause 表示 trap 原因
  5. 设置为管理者模式
  6. 将 stvec 复制给 pc
  7. 开始执行新的 pc 指向的指令

注意:此时没有转换为内核页表,没有转换为内核栈,也没有保存除 pc 外的任何寄存器,这些需要由内核来实现

原因:这样能提供给内核更好的灵活性,例如在内核中发生 trap 并不需要转换页表,可以提高处理 trap 的性能

相关的汇编指令

  • ecall
    • environment call
    • 系统调用,一种 trap
  • sret
    • Supervisor Return
    • 将模式从管理者模式更改为指定的模式(sstatus 的 SPP 位)
    • 将 sepc 寄存器复制给 pc 寄存器
    • 启用设备中断(将 sstatus 的 SIE 位设为 1)
  • csrw
    • 写入控制寄存器 csrw sscratch, a0
  • csrr
    • 读取控制寄存器 csrr t0, sscratch

用户 trap

来自用户空间的 trap 的处理流程

  1. uservec(kernel/trampoline.S)
  2. usertrap(kernel/trap.c)
  3. usertrapret(kernel/trap.c)
  4. userret(kernel/trapline.S)

trampoline

由于RISC-V 硬件在发生 trap 时不会转换页表,这意味着 stvec 保存的地址(处理 trap 的地址)必须在用户页表中存在有效映射,并且在转换成内核页表后,必须在内核页表中也存在有效映射

Xv6 使用了一个 trampoline 页表来解决上面的限制条件

trampoline 页面包含 stvec 指向的 uservec 程序和用于返回到用户代码的 userret 程序

trampoline 在内核每个进程的页表中都映射到了 TRAMPOLINE(0x3ffffff000)地址上,位于虚拟地址顶部,它只允许管理者模式执行

trapframe

通用寄存器内容会保存到一个 trapframe 结构体,它通常在用户页表中映射到与 trampoline 相邻的位置(0x3fffffe000),且也只允许管理者模式访问

它的物理地址保存在 proc 结构体的 trapframe 成员变量中,以便内核能通过内核页表直接访问它

kernel/proc.h
1
2
3
4
5
6
7
8
struct trapframe {
/* 0 */ uint64 kernel_satp; // kernel page table
/* 8 */ uint64 kernel_sp; // top of process's kernel stack
/* 16 */ uint64 kernel_trap; // usertrap()
/* 24 */ uint64 epc; // saved user program counter
/* 32 */ uint64 kernel_hartid; // saved kernel tp
...
};
  • kernel_satp
    • 保存 kernel 页表地址
  • kernel_sp
    • 保存进程的内核栈顶地址
  • kernel_trap
    • 保存内核代码中的 usertrap 位置
  • epc
    • 保存用户的 pc
    • usertrap() 中会将 sepc 寄存器内容保存到这里
    • 因为可能会跳转到另一个用户进程去执行,sepc 寄存器可能会被更改
  • kernel_hartid
    • CPU 核心 id,表示该进程在哪个 CPU 核心运行,从 0 开始
  • 剩下的是通用寄存器

uservec

uservec 代码位于 kernel/trampoline.S 中

它的作用是保存用户代码的通用寄存器,切换内核栈、内核页表等,跳转到内核中处理 trap 的位置 usertrap(kernel/proc.c)

usertrap

usertrap 代码位于 kernel/trap.c 中

它的作用是确定 trap 的原因,处理它并返回

  1. 首先将 stvec 更改为 kernelvec(kernel/kenelvec.S),这样在内核中发生 trap 时,会进入 kerneltrap 进行处理,而不会进入 usertrap
  2. 将 sepc 保存到 trapframe 中,因为 trap 有可能时计时器中断,转换到另一个进程去执行,会将 sepc 覆盖
  3. 根据 trap 种类
    • 系统调用
      • p->trapframe->epc +=4 这样在回到用户进程时,会执行下一条指令,而不是再执行 ecall
      • 启用设备中断
      • 调用 syscall 来执行对应的系统调用
    • 设备中断
      • 调用 devintr 处理
    • 异常
      • 杀死出错的进程
  4. 检查进程是否被杀死,若杀死则调用 exit 退出
  5. 检查是否是计时器中断,若是则调用 yield 放弃 CPU

usertrapret

usertrapret 代码位于 kernel/trap.c 中

它的作用是设置 trapframe 和控制寄存器

  1. 将 stvec 更改为 uservec(kernel/trampoline.S)
  2. 设置 trapframe 中 uservec 需要使用的字段
  3. 设置 sstatus
  4. 设置 sepc 为之前保存的 pc
  5. 将用户页表放入 a0 传递给 userret

userret

userret 代码位于 kernel/trampoline.S 中

它的作用是切换为用户页表,从 trapframe 中恢复通用寄存器,调用 sret 跳转 sepc 指向的地址,返回到用户模式

代码:调用系统调用

user/initcode.S 将 exec 的参数放在 a0 和 a1 寄存器中,把系统调用号放在 a7 中

ecall 指令进入内核,执行 uservecusertrapsyscall 执行

syscall 在 trapframe 中检索 a7 保存的系统调用号,并用它索引到 syscall 中

syscall 返回时,将返回值记录到 p->trapframe->a0 中

然后用户空间的 exec 函数会将该值返回

系统调用号无效,会打印错误然后返回 -1

代码:系统调用参数

根据 RISC-V C 调用约定,系统调用参数存放在寄存器中

内核陷阱代码将寄存器的值保存到当前进程的 trapframe 中,这样内核可以找到它们

内核函数 argintargaddrargfd 从 trapframe 中检索系统调用参数作为整数、指针或文件描述符,它们都调用 argraw 从用户寄存器中检索

指针作为参数有两个挑战

  • 用户程序可能是错误或恶意的,传递一个无效的指针或欺骗内核用来访问内核内存的指针
  • xv6 内核页表映射与用户页表映射并不相同,不能用普通指令从提供的地址加载或存储数据

内核实现了安全的传输数据的函数

  • 文件系统调用如 exec 用 fetchstr(kernel/syscall.c)从用户空间检索字符串文件名参数
  • fetchstr 调用 copyinstr(kernel/vm.c)来完成
  • copyinstr 从用户页表的虚拟地址 p->pagetable->srcva 复制 max 字节到 dst 中
    • 因为 pagetable 不是当前的页表,copyinstr 使用 walkaddr(它会调用 walk) 在 pagetable 中查找 srcva,从而产生物理地址 pa0
    • 内核将每个物理内存地址映射到对应的内核虚拟地址,因此 copyinstr 能直接从 pa0 复制字符串字节到 dst
    • walkaddr(kernel/vm.c)会检查用户提供的虚拟地址是否是进程地址空间的一部分,因此程序不能欺骗内核来读取其他内存
  • 类似的功能 copyout 从内核读取数据到用户提供的地址

内核 trap

CPU 在执行内核时,stvec 会指向 kernelvec(kernel/kernelvec.S)

如果发生 trap 会跳转到 kernelvec 来处理 trap

kernelvec 将通用寄存器保存在中断的内核线程的栈中,trap 有可能导致切换线程,这样不会导致混乱

kernelvec 保存完寄存器后调用 kerneltrap(kernel/trap.c)

kerneltrap 会保存控制寄存器并处理两种 trap

  • 设备中断
    • 使用 devintr 检查设备中断
    • 如果是计时器中断,且进程的内核线程正在运行,kerneltrep 会调用 yield 让其他线程有机会运行
  • 异常
    • 内核会调用 panic 然后停止运行

kerneltrap 任务完成后,它需要返回到 trap 中断的代码,会恢复保存的控制寄存器,然后返回到 kernelvec

kernelvec 恢复保存的通用寄存器,然后执行 sret,返回中断的内核代码

在内核开始执行时有一段时间 stvec 仍然指向 uservec,这段时间内不允许发生设备中断

RISC-V 会在发生 trap 时关闭设备中断,让内核有时间设置 stvec 为 kernelvec

页面错误异常

CPU 会发出页面错误异常,当:

  • 虚拟地址在页表中没有映射
  • PTE 的 PTE_V 标志位为 0
  • PTE 的权限位阻止正在尝试的操作

RISC-V 区分三种页面错误:

  • load page faults
  • store page faults
  • instruction page faults
    • PC 寄存器的地址指向的指令无法翻译

xv6 的异常处理很单一:如果在用户空间发生异常,内核会杀死出错的进程,如果在内核中发生异常,内核会发生 panic

真实的操作系统会做很多有趣的处理

  • COW fork
  • Lazy allocation
  • Demand Paging
  • Paging to disk
  • Extending stacks
  • Memory-mapped files

COW fork

许多内核使用页面错误来实现 COW,加快 fork,它不需要复制内存,特别是在 fork 后 exec 时很高效

在 xv6 中,fork 会让子进程的初始内存与父进程的相同,它调用 uvmcopy 给子进程分配物理空间并复制父进程的内存给它

如果父子进程共享父进程的物理内存会更加高效

  • COW fork 的简单计划
    1. 父子进程一开始共享所有的物理页,且设为只读
    2. 当某个进程要写入内存时,CPU 抛出页面错误异常
    3. 内核的 trap 处理程序分配一个新的物理页面,并将原页面的内容复制过去
    4. 将出错进程的页表中相关 PTE 指向副本,允许读写,然后重新执行指令

COW 需要一个记录,来决定物理页面何时释放,它可能有多个进程在使用;当发生 store 页面错误时,如果该物理页面只有出错进程指向它,不需要再复制,直接使用

Lazy allocation

用户程序调用 sbrk 申请更多内存时,内核先增加它的 size,但不申请物理内存,不创建映射

当用户程序访问新地址时,会发生页面错误,内核再申请一页物理内存并在页表添加映射

  1. kalloc
  2. 初始化页面
  3. 页面映射
  4. 更新页表
  5. 重新执行指令

如果用户程序申请了很大内存,但是不去使用,Lazy allocation 会提高效率

lazy allocation 可以让空间成本随时间分摊,但是会导致页面错误的额外开销

内核可以通过分配一批连续页面,对页面错误的 trap 处理程序进行特殊化来减小开销

Demand paging

exec 中,xv6 会将程序的所有 text 和 data 直接加载到内存中,由于程序可能会很大,从磁盘中读取开销昂贵

  1. 现代内核为用户地址空间创建页表,但是 PTE 标记为无效
  2. 当出现页面错误时,内核将页面的内容从磁盘中读取,添加映射

Paging to disk

一个进程可能需要的内存多于计算机的 RAM,操作系统可能会实现 paging to disk

内核会将用户页面的一部分放在内存中,其余的页面保存到磁盘中的 paging area 区域,并将对应的 PTE 标记为无效

当进程尝试访问磁盘上的页面,会发生页面错误,内核会将该页面从硬盘中读取出来

如果没有多余的内存

内核先将一个页面驱逐,保存到磁盘中,将对应的 PTE 标记为无效,但是驱逐的花销是昂贵的

真实世界

如果将内核内存映射到每个进程的用户页表中,可以消除对页表切换的需求

生产环境的操作系统实现了 COW、Lazy allocation、Demand paging、Paging to disk、Memory-mapped files 等等

xv6 没有这样做,如果用完内存,

Chapter 5 Interrupts and device drivers

  • 驱动程序(driver)

    • 操作系统中管理特定设备的代码它配置硬件,告诉设备执行操作,处理产生的中断,与可能正在等待来自设备 I/O 的进程进行交互
    • driver 代码可能很复杂,因为驱动程序与它管理的设备要同时执行
    • driver 必须了解设备的硬件接口,接口可能很复杂且缺乏文档记录
    • 后续驱动程序用 driver 表示(别问,问就是 driver 在一堆中文里更清晰)
  • 中断(Interrupt)

    • 设备需要操作系统特别关注,它可以进行配置,产生中断(trap 的一种)
    • 当设备发起中断,内核 trap 处理代码能识别出设备中断并调用驱动程序的中断处理程序
    • 在 xv6 中,中断处理的分配在 devintr 函数中
  • 许多设备 driver 在两个上下文中执行代码

    • 在进程的内核线程中执行前半部分
      • 前半部分由需要执行 I/O 的系统调用(如 readwrite)来调用
      • 此代码可能请求硬件启动操作(如请求硬盘读取块),然后等待操作完成
      • 最后设备完成操作,发起中断
    • 在中断时执行后半部分
      • driver 的中断处理程序作为后半部分
      • 它找到设备完成的操作,在适当的情况唤醒正在等待的进程
      • 告诉硬件开始处理下一个操作

代码:控制台输入

控制台连接到 RISC-V

控制台 driver 位于 kernel/console.c,可作为驱动程序结构的一个简单说明

xv6 的控制台 driver 交互的 UART 硬件是 QEMU 仿真的 16550 芯片,在真实的计算机,一个 16550 芯片管理 RS232 串行链路,连接着一个中断或其他计算机。当运行 QEMU 时,它连接着键盘和显示器

控制台 driver 一次累积一行的输入,处理特殊的输入字符,如退格 backspace 和 control-u

当用户在 QEMU 中向 xv6 输入时,击键通过 QEMU 模拟的 UART 硬件传递给 xv6

  • 一些物理地址由 RISC-V 硬件连接到 UART 设备
    • 从这些物理地址读写是与设备硬件交互而不是内存
    • UART 的内存映射地址从 0x10000000 (或 UART0 kenrel/memlayout.h)开始

控制寄存器

UART 硬件在软件层面为一组内存映射的控制寄存器(这里的寄存器并不是 CPU 寄存器,而且位于 UART 硬件中的寄存器)

  • UART 控制寄存器宽度为 1 Byte,它们在 UART0 的偏移在 kernel/uart.c 中定义
  • LSR
    • line status register
    • 比特位表示输入的字符是否在等待软件读取
  • RHR
    • receive holding register
    • 保存等待读取的字符
    • 每次一个字符被读取,UART 硬件将它从一个 FIFO 的结构中删除
    • 当 FIFO 结构为空时将 LSR 的 ready 位清零
  • THR
    • transimit holding register
    • 保存等待传输的字符

UART 传输硬件很大程度上独立于接收硬件,如果软件向 THR 写 1 Byte,UART 就传输该字节

xv6 的控制台输入

xv6 的 main 调用 consoleinit 来初始化 UART 硬件,配置 UART 让它每接收到 1 Byte 输入就生成一个 receive 中断,每完成 1 Byte 的输出就生成一个 transmit complete 中断

  • 用户进程,如 shell,通过 user/init.c 打开的文件描述符,使用 read 系统调用从控制台获取输入行
  • read 系统调用通过内核的 consoleread 完成操作
  • consoleread 等待输入(通过中断),然后将字符放入 cons.buf 作为缓冲,把输入复制到用户空间,直到一整行输入到达,返回到用户进程
    • 如果用户还没有输入一整行,任何需要读取的进程都在 sleep 调用中等待

当用户输入一个字符

  • UART 硬件请求 RISC-V 发起中断,激活 xv6 的 trap 处理程序
  • trap 处理程序会调用 devintr,从 scause 寄存器查找中断来自哪个外部设备,然后告诉 PLIC 硬件单元哪个设备发出中断,如果来自 UART,devintr 会调用 uartintr
  • uartintr 读取来自 UART 硬件的等待输入的字符(RHR),将它们传给 consoleintr
  • consoleintr 会将字符积累在 cons.buf,但对 backspace 和一些其他字符特殊处理
  • 当一行新的字符到达(读取到 ‘\n’)时,consoleintr 会唤醒一个正在等着等待的 consoleread

代码:控制台输出

设备 driver 维护一个输入缓冲区 uart_tx_buf,因此需要输出的进程不需要等待 UART 完成发送,除非缓冲区已满

  • write 系统调用使用连接着控制台的文件描述符,最终会到达 uartputc
  • uartputc 将每个字符加入缓冲区,调用 uartstart 开始设备传输并返回

UART 每完成一个字节的发送,就会发起中断,uartintr 调用 uartstart 检查设备是否已经完成发送,然后将下一个缓冲的输出字符传给设备

如果一个进程将多个字节写入控制台,第一个字节会由 uartputc 调用的 uartstart 来发送,剩下的字节由 uartintr 调用的 uartstart 来发送

需要注意的是,这里通过缓冲和中断将设备活动和进程活动进行解耦

控制台 driver 可以处理输入,即使没有进程等待读取,一个后来的读取可以看到输入;进程可以不等待设备发送输出

解耦通过允许进程与设备 I/O 同时执行来提高性能,当设备速度慢(如 UART)或需要即时响应(如回应键入的字符)时尤其重要

这也被称为 I/O 并行

驱动程序中的并发

你可能注意到在 consolereadconsoleintr 中调用 acquire

这个调用申请一个🔒,保护控制台 driver 的数据结构免受并发访问影响

三个并发危险,可能会导致竞争或死锁

  • 两个在不同 CPU 核的进程同时调用 consoleread
  • 当 CPU 正在执行 consoleread 时,硬件可能请求该 CPU 发送控制台中断
  • 当 CPU 正在执行 consoleread 时,硬件可能在另一个 CPU 中发送控制台中断

drivers 的并发另一个需要小心的地方:一个进程可能等待设备输入,当另一个进程在运行时,输入的中断信号可能到达

中断处理程序不会考虑中断的进程和代码,例如一个中断处理程序无法安全地使用当前进程的页表调用 copyout,它只会做很少量的工作(如,将输入数据复制到缓冲区),并唤醒前半部分代码完成其余工作

定时器中断

Xv6 使用定时器中断维持时钟,使其能在进程之间切换进行调度

usertrapkerneltrap 中的 yield 调用也会导致这类切换

定时器中断来自 RISC-V 中每个 CPU 的时钟硬件,xv6 对这个时钟硬件编程,以定期中断每个 CPU

RISC-V 要求计时器中断要由机器模式接管,而不是管理者模式

RISC-V 机器模式不用分页执行代码,使用一组独立的控制寄存器,因此在机器模式执行普通的 xv6 内核代码时是不实际的

因此 xv6 将定时器中断独立于之前使用的 trap 机制进行处理

机器模式执行的代码在 kernel/start.c 中,在执行 main 之前,设置定时器中断的接收

  • 对 CLINT(core-local interruptor)硬件进行编程,以在一定延迟后生成中断
  • 设立一个类似 trapframe 的临时区域,帮助定时器中断处理程序保存寄存器和 CLINT 寄存器的地址
  • 最后 start 将 mtvec 设置为 timervec(在 kernel/kernelvec.S 中),启用定时器中断

真实世界

xv6 允许在执行内核和用户程序时启用设备和定时器中断

定时器中断强制线程切换,即使是在内核态运行,因此内核代码需要注意它可能被挂起,并在不同的 CPU 上恢复

如果内核线程有时花费大量时间计算而不返回用户空间,在内核线程之间公平地对 CPU 进行时间切片是有效的

如果只在执行用户代码时发生设备和定时器中断,会让内核更简单

在一台计算机上支持所有设备是一项艰巨的工作,因为有许多设备,有许多功能,设备和 driver 之间的协议可能很复杂且缺乏文档。在许多操作系统中,driver 比内核核心代码占用更多

UART driver 通过读取 UART 控制寄存器一次检索 1 Byte 的数据,称为 programmed I/O,因为软件正在驱动数据移动

DMA

  • 编程 I/O 很简单,但是速度太慢,无法在高数据速率下使用
  • xv6 的 UART driver 先将传入的数据复制到内核的缓冲区,再复制到用户空间,在低数据速率时有效,但如果设备产生或使用数据很快,两次复制会严重降低性能

因此有直接存储器访问(DMA)技术

  • DMA 硬件设备直接将传入的数据写入 RAM,并从 RAM 读取传出的数据
  • 高速移动大量数据的设备(现代磁盘和网络设备)通常使用直接存储器访问(DMA)

一些操作系统常使用 DMA 直接将数据在用户空间的缓冲区和设备硬件之间移动

DMA 设备 driver 在 RAM 中准备数据,对一个控制寄存器进行一次写入告诉设备去处理准备好的数据

中断优化

当一个设备在不可预测的时间需要关注时,中断是有意义的,但是中断有很高的 CPU 开销

高速设备(如网络和磁盘控制器)使用一些技巧减少中断的需求

  • 对整批传入或传出的请求发起一个中断
  • 轮询:完全禁用中断,定期检查设备是否需要关注

如果设备执行操作非常快,轮询效率较高,但是如果设备大部分时间处于空闲状态,则会浪费 CPU 时间

某些驱动程序根据当前设备负载会在轮询和中断之间动态切换

设备使用

如第 1 章所述,控制台在应用程序呈现为一个常规文件,应用程序通过 readwrite 系统调用读取输入,写入输出

应用程序可能想要控制不能作为标准文件系统调用的设备,Unix 操作系统支持 ioctl 系统调用应对这种情况

实时响应

计算机的一些使用需要系统在有限的时间内做出响应(严格安全的系统错过 deadline 可能会导致灾难)

xv6 不适合严格实时设置,严格实时操作系统往往是与应用程序链接的库,允许进行分析最坏情况下的响应时间

xv6 也不适合软实时应用程序,偶尔错过 deadline 是可以接受的,因为 xv6 调用程序过于简单,并且它在内核代码路径中有一段较长时间中断是禁止的

作者

Humoooor

发布于

2022-10-14

更新于

2022-11-17

许可协议

评论