XV6操作系统代码阅读心得(一):启动加载、中断与系统调用

4 minute read

Published:

XV6操作系统是MIT 6.828课程中使用的教学操作系统,是在现代硬件上对Unix V6系统的重写。XV6总共只有一万多行,非常适合初学者用于学习和实践操作系统相关知识。

MIT 6.828的课程网站是https://pdos.csail.mit.edu/6.828/。XV6操作系统有官方文档,英文版在前面的网站可以下载,中文版翻译参见https://th0ar.gitbooks.io/xv6-chinese/content/。

此部分内容另有PPT

前置知识

在阅读XV6操作系统代码前,需要熟练掌握C语言,了解有关X86体系结构的基本知识,操作系统相关的基本概念,以及关于编译、链接相关的基本知识。关于相关理论知识,个人推荐的教材是文末的参考文献[1]、[2]。此外,阅读过程中可能遇到很多新概念,熟练掌握Google和Stack Overflow也是必须的。其中,尤其有用的资料是OS Dev Wiki和x86指令手册。最后,推荐能熟练使用某种代码编辑器,提升自己阅读代码的效率。

相关知识总结

1. 内核态与用户态

在操作系统中,内核态指的是操作系统内核在运行时系统的状态,在这个状态下,内核程序具有访问任何已有硬件和执行任何已有指令的权限;用户态指的是用户进程在执行时系统的状态,在这个状态下,用户进程只能执行一部分指令,按照操作系统提供的系统调用来访问硬件和与其他进程交互。将内核态与用户态隔离是为了提升系统整体的安全性和健壮性,避免恶意进程和出错进程破坏系统。

2. 中断与系统调用

中断是一种能让操作系统响应外部硬件的机制,比如说,在一个用户进程执行时,另一个用户进程请求的磁盘文件加载完毕,那么需要设计一个中断信号来通知操作系统,暂停当前用户进程,让操作系统处理这个中断事件;而系统调用则是使得用户进程能够陷入内核态,请求某种系统服务的机制,比如利用系统提供的syscall指令陷入内核,为进程完成需要内核权限的输入输出任务,然后返回用户态,进程继续执行。

计算机在运行时,通过CPU内某些寄存器的权限位来得知当前是处于内核态还是用户态。比如,在x86系统中,CPU通过检查%cs寄存器内的CPL位,来检查当前指令的执行权限级别。在XV6系统中,CPL0代表内核态,CPL3代表用户态。如果指令的执行权限不符合CPL位的值,那么就会产生一个通用保护异常(General Protection Fault)。

3. ELF文件

ELF是Unix系统中主要被使用的可执行文件格式,详细信息可以参考https://en.wikipedia.org/wiki/Executable_and_Linkable_Format。在bootmain()函数中,涉及到了ELF中两个重要的概念,ELF Header和Program Header。ELF Header记录了ELF文件相关的基本信息,其中包含一组Program Header,每个Program Header记录ELF文件中的一段代码或者数据的具体位置和大小等基本信息。Program Header所指向的ELF段包括.text .data等。bootmain()函数就是先从加载到内存0x10000地址处的ELF Header中获得所有Program Header的信息,然后将这些Program段依次从磁盘加载到内存中。通过readelf命令,可以查看内核究竟有哪些Program Header,得到结果如下:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .text             PROGBITS        80100000 001000 008111 00  AX  0   0  4
  [ 2] .rodata           PROGBITS        80108114 009114 000672 00   A  0   0  4
  [ 3] .stab             PROGBITS        80108786 009786 000001 0c  WA  4   0  1
  [ 4] .stabstr          STRTAB          80108787 009787 000001 00  WA  0   0  1
  [ 5] .data             PROGBITS        80109000 00a000 002596 00  WA  0   0 4096
  [ 6] .bss              NOBITS          8010b5a0 00c596 00715c 00  WA  0   0 32
  [ 7] .debug_line       PROGBITS        00000000 00c596 001f8c 00      0   0  1
  [ 8] .debug_info       PROGBITS        00000000 00e522 00a965 00      0   0  1
  [ 9] .debug_abbrev     PROGBITS        00000000 018e87 0026ed 00      0   0  1
  [10] .debug_aranges    PROGBITS        00000000 01b578 0003a0 00      0   0  8
  [11] .debug_loc        PROGBITS        00000000 01b918 002f30 00      0   0  1
  [12] .debug_str        PROGBITS        00000000 01e848 000cdc 01  MS  0   0  1
  [13] .comment          PROGBITS        00000000 01f524 00001c 01  MS  0   0  1
  [14] .debug_ranges     PROGBITS        00000000 01f540 000018 00      0   0  1
  [15] .shstrtab         STRTAB          00000000 01f558 0000a5 00      0   0  1
  [16] .symtab           SYMTAB          00000000 01f8d0 0023d0 10     17 138  4
  [17] .strtab           STRTAB          00000000 021ca0 0012d0 00      0   0  1

XV6系统的启动过程

a

在源代码中,XV6系统的启动运行轨迹如图。系统的启动分为以下几个步骤:

  1. 首先,在bootasm.S中,系统必须初始化CPU的运行状态。具体地说,需要将x86 CPU从启动时默认的Intel 8088 16位实模式切换到80386之后的32位保护模式;然后设置初始的GDT(详细解释参见https://wiki.osdev.org/Global_Descriptor_Table),将虚拟地址直接按值映射到物理地址;最后,调用bootmain.c中的bootmain()函数。

  2. bootmain()函数的主要任务是将内核的ELF文件从硬盘中加载进内存,并将控制权转交给内核程序。具体地说,此函数首先将ELF文件的前4096个字节(也就是第一个内存页)从磁盘里加载进来,然后根据ELF文件头里记录的文件大小和不同的程序头信息,将完整的ELF文件加载到内存中。然后根据ELF文件里记录的入口点,将控制权转交给XV6系统。

  3. entry.S的主要任务是设置页表,让分页硬件能够正常运行,然后跳转到main.cmain()函数处,开始整个操作系统的运行。

  4. main()函数首先初始化了与内存管理、进程管理、中断控制、文件管理相关的各种模块,然后启动第一个叫做initcode的用户进程。至此,整个XV6系统启动完毕。

XV6的操作系统的加载与真实情况有一些区别。首先,XV6操作系统作为教学操作系统,它的启动过程是相对比较简单的。XV6并不会在启动时对主板上的硬件做全面的检查,而真实的Bootloader会对所有连接到计算机的所有硬件的状态进行检查。此外,XV6的Boot loader足够精简,以至于能够被压缩到小于512字节,从而能够直接将Bootloader加载进0x7c00的内存位置。真实的操作系统中,通常会有一个两步加载的过程。首先将一个加载Bootloader的程序加载在0x7c00处,然后加载进完整的功能复杂的Bootloader,再使用Bootloader加载内核。

bootmain()函数详解

void bootmain(void)
{
  struct elfhdr *elf;
  struct proghdr *ph, *eph;
  void (*entry)(void);
  uchar* pa;

  elf = (struct elfhdr*)0x10000;  // scratch space

  // Read 1st page off disk
  readseg((uchar*)elf, 4096, 0);

  // Is this an ELF executable?
  if(elf->magic != ELF_MAGIC)
    return;  // let bootasm.S handle error

  // Load each program segment (ignores ph flags).
  ph = (struct proghdr*)((uchar*)elf + elf->phoff);
  eph = ph + elf->phnum;
  for(; ph < eph; ph++){
    pa = (uchar*)ph->paddr;
    readseg(pa, ph->filesz, ph->off);
    if(ph->memsz > ph->filesz)
      stosb(pa + ph->filesz, 0, ph->memsz - ph->filesz);
  }

  // Call the entry point from the ELF header.
  // Does not return!
  entry = (void(*)(void))(elf->entry);
  entry();
}

bootmain.c中的bootmain()函数是XV6系统启动的核心代码。bootmain()函数首先从磁盘中读取第一个内存页(11行);然后判断读取到的内存页是否是ELF文件的开头(14-15行);如果是的话,根据ELF文件头内保存的每个程序头和其长度信息,依次将程序读入内存(18-25行);最后,从ELF文件头内找到程序的入口点,跳转到那里执行(29-30行)。通过readelf命令可以得到ELF文件中程序头的详细信息。总而言之,boot loader在XV6系统的启动中主要用来将内核的ELF文件从硬盘中加载进内存,并将控制权转交给内核程序。

通过获取struct elfhdrstruct proghdr的位置和大小信息(18-19行,elf->phoff elf->phnum),就能得知XV6内核程序段(Program Header)的位置和数量,在加载硬盘扇区的过程中,逐步向前移动ph指针,一个个加载对应的程序段。对于一个程序段,通过ph->fileszph->off获得程序段的大小和位置,使用readseg()函数来加载程序段,逐步向前移动pa指针,直到加载进的磁盘扇区使得加载进的扇区大小超过程序文件的结尾epa,从而完成单个程序段的加载。对于单个内核程序段,代码确保它会填满最后一个内存页。

XV6系统的中断管理

1. 中断描述符与中断描述符表

中断描述符表是X86体系结构中保护模式下用来存放中断服务程序信息的数据结构,其中的条目被称为中断描述符。在XV6数据结构中,涉及的数据结构如下

// Gate descriptors for interrupts and traps
struct gatedesc {
  uint off_15_0 : 16;   // low 16 bits of offset in segment
  uint cs : 16;         // code segment selector
  uint args : 5;        // # args, 0 for interrupt/trap gates
  uint rsv1 : 3;        // reserved(should be zero I guess)
  uint type : 4;        // type(STS_{IG32,TG32})
  uint s : 1;           // must be 0 (system)
  uint dpl : 2;         // descriptor(meaning new) privilege level
  uint p : 1;           // Present
  uint off_31_16 : 16;  // high bits of offset in segment
};
struct gatedesc idt[256];
extern uint vectors[]; 

其中,struct gatedesc的格式与X86体系结构所要求的完全相同https://wiki.osdev.org/Interrupt_Descriptor_Table。对于第$i$条中断描述符,CS寄存器存储的是内核代码段的段编号SEG_KCODE,offset部分存储的是vector[i]的地址。在XV6系统中,所有的vector[i]地址均指向trapasm.S中的alltraps函数。

2. XV6中断管理的初始化

由于中断机制是由CPU硬件支持的,所以计算机在运行阶段一开始时,BIOS就开启并支持中断。但是,在XV6系统的启动过程中,第一条指令就使用cli指令来屏蔽中断,直到第一个进程调度时才会在scheduler()里使用STI指令允许硬件中断。在允许硬件中断之前,必须先配置好中断描述符表,具体的实现在tvinit()和idtinit()函数中

void tvinit(void) {
  int i;

  for(i = 0; i < 256; i++)
    SETGATE(idt[i], 0, SEG_KCODE<<3, vectors[i], 0);
  SETGATE(idt[T_SYSCALL], 1, SEG_KCODE<<3, vectors[T_SYSCALL], DPL_USER);

  initlock(&tickslock, "time");
}
void idtinit(void) {
  lidt(idt, sizeof(idt));
}

在XV6系统中,只有中断和系统调用机制可以实现用户态到内核态的转变。因此,即使是第一个用户进程启动时,XV6系统也会在内核态手动构建Trap Frame,设置Trap Frame中的CS寄存器上的相关权限位,然后调用中断返回函数进入用户态。XV6中的硬件中断都是使用CTI和STI指令来进行开关。在实际的计算机中,中断分为外部中断和内部中断。外部中断包括来自外部IO设备的中断、来自时钟的中断、断电信号等,外部中断又分为可屏蔽中断和不可屏蔽中断。对于内部中断,包括由软件调用INT指令触发的中断和由CPU内部错误(指令除零等)触发的中断。

3. XV6中断处理过程举例

以除零错误为例。当XV6的指令执行中遇到除零错误时,首先CPU硬件会发现这个错误,触发中断处理机制。在中断处理机制中,硬件会执行如下步骤:

  1. 从IDT 中获得第 n 个描述符,n 就是 int 的参数。
  2. 检查CS的域 CPL <= DPL,DPL 是描述符中记录的特权级。
  3. 如果目标段选择符的 PL < CPL,就在 CPU 内部的寄存器中保存ESP和SS的值。
  4. 从一个任务段描述符中加载SS和ESP。
  5. 将SS压栈。
  6. 将ESP压栈。
  7. 将EFLAGS压栈。
  8. 将CS压栈。
  9. 将EIP压栈。
  10. 清除EFLAGS的一些位。
  11. 设置CS和EIP为描述符中的值。

此时,由于CS已经被设置为描述符中的值(SEG_KCODE),所以此时已经进入了内核态,并且EIP指向了trapasm.S中alltraps函数的开头。在alltrap函数中,系统将用户寄存器压栈,构建Trap Frame,并且设置数据寄存器段为内核数据段,然后跳转到trap.c中的trap函数。在trap函数中,首先通过检查中断调用号,发现这不是一个系统调用,也不是一个外部硬件中断,因此进入如下代码段:

    if(myproc() == 0 || (tf->cs&3) == 0){
      // In kernel, it must be our mistake.
      cprintf("unexpected trap %d from cpu %d eip %x (cr2=0x%x)\n",
              tf->trapno, cpuid(), tf->eip, rcr2());
      panic("trap");
    }
    // In user space, assume process misbehaved.
    cprintf("pid %d %s: trap %d err %d on cpu %d "
            "eip 0x%x addr 0x%x--kill proc\n",
            myproc()->pid, myproc()->name, tf->trapno,
            tf->err, cpuid(), tf->eip, rcr2());
    myproc()->killed = 1;

根据触发中断的是内核态还是用户进程,执行不同的处理。如果是用户进程出错了,那么系统会杀死这个用户进程;如果是内核进程出错了,那么在输出一段错误信息后,整个系统进入死循环。

如果是一个可以修复的错误,比如页错误,那么系统会在处理完后返回trap()函数进入trapret()函数,在这个函数中恢复进程的执行上下文,让整个系统返回到触发中断的位置和状态。

4. 如何在XV6中添加新的系统调用(以setrlimit为例)

在Linux系统中,setrlimit系统调用的作用是设置资源使用限制。我们以setrlimit为例,要在XV6系统中添加一个新的系统调用,首先在syscall.h中添加一个新的系统调用的定义

#define SYS_setrlimit  22

然后,在syscall.c中增加新的系统调用的函数指针

static int (*syscalls[])(void) = {
        ...
    [SYS_setrlimit] sys_setrlimit,
};

当然现在sys_setrlimit这个符号还不存在,因此在sysproc.c中声明并实现这个函数

int sys_setrlimit(int resource, const struct rlimit *rlim) {
    // set max memory for this process, etc
}

最后,在user.h中声明setrlimit()这个函数系统调用函数的接口,并在usys.S中添加有关的用户系统调用接口。

SYSCALL(setrlimit)

int setrlimit(int resource, const struct rlimit *rlim);

一些问题

1. 在中断描述符表里存放了一个CS寄存器的值,为什么要有这个CS寄存器?

这个问题事实上涉及到了很多关于x86的底层实现的细节。在80386中,硬件对内存访问支持保护模式,在32位保护模式中,CPU使用Global Descriptor Table来存储有关内存段的信息,使用CS寄存器来存储GDT的索引,通过这个方式来索引内存段的过程中,可以通过GDT中的相应位来设置这块内存的权限。注意,这与操作系统的虚拟内存是相互独立的两个机制。对于XV6系统而言,GDT中只有5个描述符,分别是内核代码段、内核数据段、用户代码段、用户数据段和TSS,对应的定义如下

   // various segment selectors.
   #define SEG_KCODE 1  // kernel code
   #define SEG_KDATA 2  // kernel data+stack
   #define SEG_UCODE 3  // user code
   #define SEG_UDATA 4  // user data+stack
   #define SEG_TSS   5  // this process's task state

在中断切换的时候,需要从用户代码段切换到内核代码段,因此需要保存CS的值,在中断返回的时候再弹出。此外,中断描述符表中的CS寄存器的值指明了中断处理程序应该使用的CS值,也就是对应的内存段。

2. 在从用户态和内核态之间切换的时候,代码的执行权限是如何被设置的?

代码的执行权限由CS寄存器中的权限位标记。在中断调用时,INT指令会保存原来的CS寄存器,读入新的CS寄存器,从而维持中断前后的代码执行权限不变。对于第一个用户进程的而言,需要在启动前手动设置CS寄存器的相关权限位才行,具体的代码片段如下

    p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
    p->tf->ds = (SEG_UDATA << 3) | DPL_USER;

参考文献

  1. Bryant, Randal E., O’Hallaron David Richard, and O’Hallaron David Richard. Computer systems: a programmer’s perspective. Vol. 281. Upper Saddle River: Prentice Hall, 2003.
  2. Silberschatz, Abraham, Greg Gagne, and Peter B. Galvin. Operating system concepts. Wiley, 2018.