MIT 6.S081 Lab: Xv6 and Unix utilities

3 Jul 2022

A multitude of small delights constitute happiness.

开始学习MIT的操作系统6.S081课程的第一个Lab。Lab有grade程序，提交网站也可以用教育网邮箱注册。本Lab主要是熟悉xv6的代码与系统调用，本篇博客尽量不贴代码，记录一下写时的体会。

sleep

写一个sleep程序通过系统调用sleep完成停止一段时间。写这段代码可以看 kernel/sysproc.c 中内核代码关于 sleep 调用的实现, 头文件 user/user.h 有系统调用以及一些C库函数的声明，汇编代码 user/usys.S 是负责从用户代码跳转到内核代码的系统调用实现。有意思的是，这段汇编代码是通过 user/usys.pl 生成的。

#!/usr/bin/perl -w

# Generate usys.S, the stubs for syscalls.

print "# generated by usys.pl - do not edit\n";

print "#include \"kernel/syscall.h\"\n";

sub entry {
    my $name = shift;
    print ".global $name\n";
    print "${name}:\n";
    print " li a7, SYS_${name}\n";
    print " ecall\n";
    print " ret\n";
}
	
entry("fork");
entry("exit");
entry("wait");
entry("pipe");
entry("read");
entry("write");
entry("close");
entry("kill");
entry("exec");
entry("open");
entry("mknod");
entry("unlink");
entry("fstat");
entry("link");
entry("mkdir");
entry("chdir");
entry("dup");
entry("getpid");
entry("sbrk");
entry("sleep");
entry("uptime");

之前做另一个Lab有相关记录梳理。

在 int 指令后，硬件接管改变当前优先级，并存部分上下文(即PC, regs, eflags, stack pointer等，定义在 trapframe 中，硬件与OS各存部分，见 x86.h 的 trapframe 注释)，然后将控制交给 OS , 即根据 IDT 寻找到对应代码位置。在 xv6 中 IDT 指定的代码地址在 vectors.S （其由 vectors.pl 生成）。

由于6.S081的xv6是risc-v的，指令会有所不同，比如这个ecall指令与x86-64的int指令不同。但系统调用后改变优先级，上下文切换，陷入内核，代码跳转，这整个流程在操作系统的思想里是相同的。

pingpong

这个程序目的是通过 fork 一个子程序，在程序间通过 pipe 进行通信。比较简单。

primes

这个程序要求实现素数筛选，但需要多个进程以一种流水线的形式实现埃氏筛。这个是并发编程的一个典型程序。文章介绍了并发编程的历史时，用到这个例子。

小小解释一下代码实现的关键就是区分流水线的头部与尾部，并且及时关闭不需要的管道文件描述符，区分读端与写端。这应该是本Lab逻辑上最难的一个题。

#include "kernel/types.h"
#include "user/user.h"


static void tobuf(int X, char* buf);
static void tonum(char* buf, int* X);

int
main(int argc, char* argv[])
{
    int p, num;
    int pre, post;
    int fds[2];
    char buf[4];

    while(1) {
        fprintf(1, "prime 2\n");
        pipe(fds);

        if(fork() == 0) {
            close(fds[1]);
            break;
        }
        close(fds[0]);
        post = fds[1];
        num = 2;
        while(num < 35) {
            if(++num % 2) {
                tobuf(num, buf);
                write(post, buf, 4);
            }       
        }

        close(post);
        wait((int *)0);
        exit(0);
    }

    // not frist
    while (1)
    {
        pre = fds[0];
        if(0 == read(pre, buf, 4)) {
            // the last process
            close(pre);
            exit(0);
        }
        tonum(buf, &p);
        fprintf(1, "prime %d\n", p);

        pipe(fds);

        if(fork() == 0) {
            close(fds[1]);
            continue;
        }
        else{
            close(fds[0]);
            post = fds[1];
            while(read(pre, buf, 4)) {
                tonum(buf, &num);
                if(num % p) write(post, buf, 4);
            }
            close(pre);
            close(post);
            wait((int *) 0);
            exit(0);
        }
    }
}

static void 
tobuf(int X, char* buf) 
{
    buf[0] = (X & 0xf);
    buf[1] = ((X & 0xf0) >> 4);
    buf[2] = ((X & 0xf00) >> 8);
    buf[3] = ((X & 0xf000) >> 12);
}

static void 
tonum(char* buf, int* X)
{
    int ret = buf[0];
    ret |= (buf[1] << 4);
    ret |= (buf[2] << 8);
    ret |= (buf[3] << 12);
    *X = ret;
}

find

实现一个简单版本 Unix find 程序，从一个目录树下查找特定文件名的文件。因为是一个目录树下，所有我实现为递归地搜索子目录。一个容易出错的点是搜索了 . 与 .. 目录。参考 user/ls.c 的实现，了解通过 fstat 调用区分一个文件类型，通过 struct dirent 和 read 读取目录下的所有条目。虽然 read 操作是读取二进制数据，但通过设计结构体的字节布局，也可以将二进制流完美读取。

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

struct dirent e;
while(read(dirFd, &de, sizeof de) == sizeof de) { 
    //iterate all entries of a dir
}

xargs

实现一个简易版Unix xargs 从标准输入按行读取，并为每一行运行一个命令，将对应行作为参数添加到命令结尾。需要实现一个有缓冲区的按行读取，然后运行命令通过 fork-exec-wait idiom 即可。我在实现时尝试不使用库加入一些命令参数，的确很麻烦。真实编写命令行工具还是需要用参数解析库。实现这个题目有个简单问题，当 exec 时 argv 作为 char** 每个参数的 char* 指向的字符串在何处？当前程序不是会被替换吗？那么被参数 char* 指向的内存理应不存在了。事实上，内核会将每个char*指向的内容复制到内核空间，再复制回已经加载程序的用户空间。接下来讲讲xv6的实现，代码在 kernal/sysfile.c 文件的sys_exec函数中，这些函数正是汇编代码 user/usys.S 跳转的系统调用内核实现地址。可以看到这些 sys_xxx 函数参数列表为空，因为每个系统调用参数不同，但需要通过相同的汇编代码进行跳转，所以获取参数就交给具体实现。简单说就是通过 kernel/syscall.c 中 argraw 函数从 trapframe 上读相关寄存器（a0~a5）的值。

static uint64
argraw(int n)
{
  struct proc *p = myproc();
  switch (n) {
  case 0:
    return p->trapframe->a0;
  case 1:
    return p->trapframe->a1;
  case 2:
    return p->trapframe->a2;
  case 3:
    return p->trapframe->a3;
  case 4:
    return p->trapframe->a4;
  case 5:
    return p->trapframe->a5;
  }
  panic("argraw");
  return -1;
}

其他一些辅助函数 argstr argaddr argint 本质上就是了解寄存器上值类型的前提下通过 argraw 读取。接下来简单讲讲 sys_exec 的实现。

uint64
sys_exec(void)
{
  char path[MAXPATH], *argv[MAXARG];
  int i;
  uint64 uargv, uarg;

  if(argstr(0, path, MAXPATH) < 0 || argaddr(1, &uargv) < 0){
    return -1;
  }
  memset(argv, 0, sizeof(argv));
  for(i=0;; i++){
    if(i >= NELEM(argv)){
      goto bad;
    }
    if(fetchaddr(uargv+sizeof(uint64)*i, (uint64*)&uarg) < 0){
      goto bad;
    }
    if(uarg == 0){
      argv[i] = 0;
      break;
    }
    argv[i] = kalloc();
    if(argv[i] == 0)
      goto bad;
    if(fetchstr(uarg, argv[i], PGSIZE) < 0)
      goto bad;
  }

  int ret = exec(path, argv);

  for(i = 0; i < NELEM(argv) && argv[i] != 0; i++)
    kfree(argv[i]);

  return ret;

 bad:
  for(i = 0; i < NELEM(argv) && argv[i] != 0; i++)
    kfree(argv[i]);
  return -1;
}

首先通过 argstr 与 argaddr 将参数读取到 path 与 uargv 中。path指向栈上内存，经过 argstr 后这块内存上就是原参数0指向的字符串。 uargv 存参数数组的首地址（原 char * argv[]的值）。

当前栈上的argv会替换调用 exec 时的 argv。暂时将 argv 数组中的所有指针置为空指针。

接下来通过循环，将uargv代表的指针数组中每一个指针读取到 uarg 中。这里有个判断 uarg == 0 ，正是由于系统调用exec的argv以空指针结尾，由此判断参数列表的结尾。

    argv[i] = kalloc();
    if(argv[i] == 0)
      goto bad;
    if(fetchstr(uarg, argv[i], PGSIZE) < 0)
      goto bad;

kalloc会分配一个 4096 字节的物理内存，并将内存的首地址返回。然后 fetchstr 将 uarg 指向的地址的内容复制到 argv[i] 指向的物理页中。至此在

int ret = exec(path, argv);

之前，所有的代码都是将用户空间的参数字符串，复制到内核空间，无论是栈上，还是”堆上”(kmem.freelist)。而在这个 exec 函数里，内核真正实现了检查 ELF 文件头，加载对应程序进入内存，将参数字符串从内核空间复制到用户空间等工作，这里不再展开。一些 sys_exec 如何回收为参数字符串分配的内核空间内存也不细致展开。

Conclusion

Lab的内容很简单，比较有意思的是内核实现系统调用，通过阅读代码可以了解操作系统内核的许多细节。

Reference

operating-system