leveldb之Compact

xv6 chapter2: Operating system organization

• 资源抽象
  Q: 为什么要有操作系统？，因为其实用户程序可以自己编写与硬件交互的程序，将需要的功能实现成一个库就可以
  A: 上述方式在每个程序”合法”运行且没有bug时可以工作，但由于要同时运行多个用户程序，以及程序之间需要进行通信，就需要将硬件资源隔离开由操作系统统一管理，用户程序使用操作系统提供的统一的对硬件的抽象接口。比如Unix就把文件抽象为文件描述符与open,read,write和close四个系统调用。这样也减少了用户的开发负担，让用户程序可以更专注于业务逻辑。

上面说到OS任务之一是将硬件资源进行抽象，最重要的硬件资源之一就是CPU，与之对应的抽象就是进程。对用户程序来说分配到进程就像分配到CPU，可以运行自己的代码，自己独占整个CPU，无需考虑对CPU的释放，对进程的调度和分配交给OS进行。另外还有对存储等的抽象，这在后面的页表会详细介绍。

总的来说OS一个重要的任务就是对硬件资源进行抽象，并提供一组系统调用，对用户来说操作系统也表现为一组调用接口，其实这就跟问题里面的描述差不多，只不过这个”库”不是由用户写的，而是公共的。所以系统调用的设计都需要精心设计，做到简洁不简单。

• 模式与安全性
  上面提到了操作系统必须将硬件资源与用户程序隔离开，即有些命令只能由操作系统执行(比如一些硬件操作指令)，要做到这一点就必须在机器级别上区分系统和用户代码，否则仅靠程序是无法控制用户这种行为的。

机器为这种隔离性的支持就是设定CPU的模式，不同的模式可以执行不同的指令，越级执行指令就会引发硬件中断停止程序并转到操作系统。RISC-V设定了3种模式:1.机器模式(拥有所有权限，一般在机器启动时处于该权限，主要用于配置机器) 2.管理者模式(操作系统运行在这一级别) 3.用户模式(用户程序级别)。所以操作系统的另一个定义也可以是特权模式下运行的程序

但是用户模式下能进行的动作是有限的，比如用户的确需要写入硬盘数据，这需要OS内的代码完成，而用户是不能直接调用内核的函数的，RISC-V提供了ecall指令来完成这个功能，用户调用的系统调用其实就是对ecall的包装。因为系统调用的入口是内核控制的，用户程序只能按照规定传入参数之后调用ecall，之后转到内核控制的入口处会由内核检查参数是否正确，防止用户程序传入恶意参数使内核跳转到恶意代码去执行。

• 内核结构
  常见的内核组织结构有宏内核和微内核两种，宏内核指整个OS都运行在特权级，这种组织的优点是效率比较高，各模块紧密结合。缺点就是一旦内核有bug将会引起重大的错误甚至宕机。而内核本身是一个巨大的项目，不可能消除所有的bug。与之相对的就是微内核结构，这种结构的kernel只留下一些最基础的功能在特权级比如进程通信与硬件操作。其它功能实现成一个用户程序运行在user mode下，比如文件系统和调度程序。xv6采用宏内核结构，代码组织如图所示，关于每个文件具体接口在kernel/defs.h里面可以看到。
  

• xv6的第一个系统调用过程
  RISC-V机器启动后会从从固定的ROM里执行一段程序，也就是loader，loader负责将内核加载进内存，然后将跳转到_entry，也就是entry.S(kernel/entry.S)的内容。entry.S是每个CPU启动时首先执行的代码，具体内容为根据CPU的id将sp设置到对应的位置之后就调用start.c(kernel/start.c)里的start函数。start函数主要负责配置一些机器选项，因为现在还处于机器模式，配置完成后将降低级别到特权模式。降低特权需要用到mret指令，start函数配置好一些基础设置(清空中断，关闭分页，初始化时钟中断)之后就设置好返回地址为main(kernel/main.c)，main里面开始就真正初始化一些操作系统相关的内容，这里会根据CPU的id执行不一样的操作，一些公用的初始化操作由0号CPU完成，之后开启第一个进程，由userinit(kernel/proc.c)完成。
  这个userinit比较有意思单独说一下，在userinit调用之前进行的一系列初始化还没有开启一个真正的进程，所以现在系统处于一个没有进程的状态，一般情况下创建进程使用fork系统调用，但是因为当前不存在一个进程无法进行fork，所以第一个进程必须手动构造。下面是它的代码:
  ```c
  // Set up first user process.
  void
  userinit(void)
  {
  struct proc *p;

  p = allocproc();
  initproc = p;

  // allocate one user page and copy initcode’s instructions
  // and data into it.
  uvmfirst(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;

  // prepare for the very first “return” from kernel to user.
  p->trapframe->epc = 0; // user program counter
  p->trapframe->sp = PGSIZE; // user stack pointer

  safestrcpy(p->name, “initcode”, sizeof(p->name));
  p->cwd = namei(“/“);

  p->state = RUNNABLE;

  release(&p->lock);

}

代码的注释已经非常清晰了，先看一下整体的流程，首先调用allocproc申请到一个PCB，前面提到过每个进程都有一个PCB用于记录进程信息，然后就是关键的`uvmfirst(p->pagetable,initcode,sizeof(initcode))`，这里是在手动将命令放到进程的地址空间，因为这个进程不是fork得到的，没有用户代码，所以需要手动将代码放到它的地址空间。initcode已经在本文件前面定义过，是一个字节数组，由汇编的initcode.S编译成二进制然后查看它的二进制代码得到。initcode.S(user/initcode.S)里面的注释也非常清晰，就是相当于exec("init",argv)调用。然后进行一些PCB的其它初始化。
现在看一下里面的细节，首先是allocproc函数，它是本文件的一个static函数，是一个分配PCB非常原始的操作，代码如下:
```c
static struct proc*
allocproc(void)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state == UNUSED) {
      goto found;
    } else {
      release(&p->lock);
    }
  }
  return 0;

found:
  p->pid = allocpid();
  p->state = USED;

  // Allocate a trapframe page.
  if((p->trapframe = (struct trapframe *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  // Set up new context to start executing at forkret,
  // which returns to user space.
  memset(&p->context, 0, sizeof(p->context));
  p->context.ra = (uint64)forkret;
  p->context.sp = p->kstack + PGSIZE;

  return p;
}

首先它会寻找一个UNUSED的PCB，然后为它分配pid和页表等内容，关键的是p->context.ra=(uint64)forkret，也就是说每个进程申请初始化时默认是从fork过来然后恢复时进入到forkret，所以新进程被调度时恢复上下文首先会进到forkret，进行一些中断返回操作之后userinit会拉起一个init进程，这是第一个进程，同时它会创建一个shell进程。另外值得一提的是在allocproc里面对锁进行了acquire但最后没有release，将release交给了调用者，这样保证调用者在申请得到PCB之后具有对它的操作权。

Lab:system calls

做这个实验还需要知道xv6的系统调用过程，在book的4.2与4.3简单介绍了一下，更具体的系统调用过程可以在下一个实验了解。

1. 首先内核有各个系统调用的实现，它们都具有相同的函数声明格式即uint64 f(void)，这样就可以把它们放在一个统一的函数指针数组里，这个函数指针数组在kernel/syscall.c里定义，也可以在这里看到所有系统调用的声明，对应的系统调用号在kernel/syscall.h里定义。而各个系统调用的具体实现分散在几个文件里，kernel/sysproc.c是与进程相关的系统调用，kernel/sysfiles.c是与文件相关的系统调用。这些函数的相同点都是参数为void，函数需要的参数由kernel/syscall.c里定义的函数(argint,argaddr,argfd)提取，一方面是为了统一系统调用函数的声明以放进一个数组，另一方面是为了安全，如果直接使用用户提供的参数可能用户传入一些恶意地址，然后系统被骗到对应地址进行操作。

2. 用户那边无法直接调用sys_系函数，而是通过一种叫stub的机制完成。系统调用的声明参数都是void，且对用户不可见，只有具体的系统调用实现知道需要哪些参数，要从哪里提取，所以就需要为用户提供一组”库”，对用户来说它们就是普通的函数，根据函数声明使用即可，而它们内部会将参数设置成系统调用正确的参数再通过ecall指令陷入真正的内核，做这种工作的函数就称为stub，它们的名字一般与相应的系统调用所对应。user/usys.pl会生成一份usys.S，这个汇编文件定义了用户的stub，做的工作就是将对应的trap号装到a7寄存器然后调用ecall指令，调用参数由编译器装到对应的寄存器，由于RISC-V架构有很多寄存器，函数调用参数基本都用寄存器传递(整数参数a0-a6，浮点数fa0-fa7)。

3. ecall会让代码跳转到uservec(kernel/tramponline.S)，ecall跳转的地方由stvec决定，在trap.c里会被设置成kernelvec与uservec，前者用于内核态下发生异常，后者则是用户态下，uservec做好一些保护工作后就会调用usertrap(kernel/trap.c)，在这里会保存一些寄存器的内容到每个进程的trapframe中，每个进程的trapframe的虚拟地址是一样，在进到uservec的时候只有特权级变了，pagetable还没有变，设置完后会跳转到usertrap(kernel/trap.c)

4. usertrap进来之后会保存返回地址，然后将stvec设置为kernelvec，因为后面进入内核态之后的中断处理的操作会不一样，然后会判断引起中断的原因，如果中断号为8则调用syscall()对系统调用进行解析

5. syscall()定义在(kernel/syscall.c)里面，主要是根据传来的系统调用号跳转到对应的系统调用，里面用到的syscalls就是一个函数指针数组

• 1. 实现一个trace系统调用，接收一个mask参数，该参数会设置哪些系统调用被追踪，本设置只会影响该进程及其子进程，不影响其它进程，被trace的系统调用返回时需要输出系统调用的名称以及返回结果(类似于shell的strace)

根据提示，

1. 可以为每个进程设置一个变量来记录哪些系统调用被追踪了，由于是只影响本进程，所以非常适合放在PCB里面，另外为了尽可能表示多的系统调用，将该变量设为了一个uint64，可以表示64个系统调用，当前30都没有用到，所以是比较充足的。因此在proc.h里的proc结构体添加了uint64 tmask变量，它的初始化工作在allocproc里完成，放在acquire(&p->lock)之后，p->tmask = 0
2. 前面设置好了需要用到的数据结构，现在来实现sys_trace，它的实现如下:

uint64
sys_trace(void)
{
    uint64 tmask;
    argaddr(0,&tmask);
    myproc()->tmask = tmask;
    return 0;

}

实现比较的简单，只要将参数设置到tmask即可，参考前面系统调用获取参数的方式，由于传进来的是一个uint64，所以使用argaddr来获取。由于要打印对应的系统调用名称以及一个进程可能会调用多个不同系统调用，最终打印的地方应该能看到系统调用号与系统调用的对应关系，以及系统调用成功的返回结果，而刚刚的syscall函数就很符合这个条件，于是修改syscall如下:

void
syscall(void)
{
  int num;
  struct proc *p = myproc();

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    // Use num to lookup the system call function for num, call it,
    // and store its return value in p->trapframe->a0
    p->trapframe->a0 = syscalls[num]();
    if(p->tmask & (1<<num)){
      printf("%d: syscall %s -> %d\n",
            p->pid, syscallnames[num], p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

就是利用p->tmask判断当前进程对该系统调用是否跟踪，如果跟踪则打印对应的名字与返回结果(存在a0寄存器里面)，syscallnames定义为一个char *[]，索引对应相对的系统调用名字，之后就是在syscall.h里为sys_trace分配系统调用号以及在syscalls对应添加sys_trace

3. 上面主要是对内核的实现，用户不能直接调用，需要前面提到的stub，因此先在user.h里添加声明int trace(uint64)，然后在usys.pl里添加entry(“trace”)，另外由于把trace的参数设定为了uint64，我在ulib.c里添加了一个atol函数来将字符串转换为uint64

• 2. 实现一个sysinfo系统调用，它接收一个struct sysinfo指针，系统调用会根据这个指针填充对应信息到用户空间的结构体内

这个实验难点在于怎么在内核空间往用户空间写数据，因为切换到内核空间之后页表会发生变化。但是根据提示发现内核里有一个叫copyout的函数负责这件事，在内核状态下将数据拷贝到用户空间下指定地址，一个重要的参数就是用户页表地址，这个可以从用myproc()获取当前运行进程然后从PCB获取，sysinfo实现如下:

uint64
sys_sysinfo(void)
{
    uint64 addr;
    struct sysinfo sinfo;
    argaddr(0,&addr);
    sinfo.nproc = proc_unused();
    sinfo.freemem = mem_unused();
    if((copyout(myproc()->pagetable,addr,(char*)&sinfo,sizeof(sinfo)) < 0))
        return -1;
    return 0;
}

其中用到的proc_unusey与mem_unused分别实现在proc.c与kalloc.c，比较简单就不再列出。值得看下的是copyout的实现，在kernel/vm.c里，代码如下:

// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;
  pte_t *pte;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if(va0 >= MAXVA)
      return -1;
    pte = walk(pagetable, va0, 0);
    if(pte == 0 || (*pte & PTE_V) == 0 || (*pte & PTE_U) == 0 ||
       (*pte & PTE_W) == 0)
      return -1;
    pa0 = PTE2PA(*pte);
    n = PGSIZE - (dstva - va0);
    if(n > len)
      n = len;
    memmove((void *)(pa0 + (dstva - va0)), src, n);

    len -= n;
    src += n;
    dstva = va0 + PGSIZE;
  }
  return 0;
}

依然是非常规范优雅的代码风格，注释非常清晰，整个操作还是在内核状态下操作的，所以肯定有一个将用户空间地址转换到内核空间地址的过程，walk与PTE2PA就是做这个工作的，walk可以根据pagetable来查找虚拟地址va0对应的PTE，PTE2PA能根据pte的内容得出对应的物理地址，而内核空间的页表是可以直接访问所有物理地址的，也就是得到的这个物理地址在内核状态下可以直接用，所以可以直接使用memmove。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2128099421@qq.com