MIT 6.S081 LAB

Lab1: Xv6 and Unix utilities
Lab2: system calls
- System call tracing (moderate)
- Sysinfo (moderate)
Lab3: page tables
Lab4: traps
Lab5: Copy-on-Write Fork for xv6
- 参考资料
Lab6: Multithreading
Others

MIT 6.S081 LAB。

Lab1: Xv6 and Unix utilities

Fetch the xv6 source for the lab and check out the util branch:

$ git clone git://g.csail.mit.edu/xv6-labs-2021
$ cd xv6-labs-2021
$ git checkout util

Build and run xv6:

$ make qemu

To quit qemu type: Ctrl-a x. (需要注意ctrl 与 A 同时按住抬起后，再按X，不要三个键同时按)

Grading and hand-in procedure 评分和上交程序

run make grade to test type make handin to submit

sleep (easy)

新建xv6-labs-2021/user/sleep.c

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

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fprintf(2, "Usage: sleep number ticks...\n");
        exit(1);
    }
    int ticks;
    ticks = atoi(argv[1]);
    if (ticks <= 0) {
        fprintf(2, "invalid number ticks.\n");
        exit(1);
    }
    sleep(ticks);
    exit(0);
}

Makefile中UPROGS中添加：

$U/_sleep\

Run the program from the xv6 shell:

$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

make grade runs all tests

run the grade tests for one assignment, type:

$ ./grade-lab-util sleep

This will run the grade tests that match “sleep”. Or, you can type:

$ make GRADEFLAGS=sleep grade

which does the same.

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-util sleep
make: 'kernel/kernel' is up to date.
== Test sleep, no arguments == sleep, no arguments: OK (6.0s) 
== Test sleep, returns == sleep, returns: OK (2.6s) 
== Test sleep, makes syscall == sleep, makes syscall: OK (4.6s) 
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

pingpong (easy)

管道是一种最基本的IPC(进程间通信)机制，作用于有血缘关系的进程之间，完成数据传递。

函数调用成功后返回r、w两个文件描述符。无需open，但需要手动close，规定：fd[0]->r；fd[1]->w，就像0对应标准输入，1对应标准输出一样。向管道文件读写数据其实是在读写内核缓冲区。

数据一旦被读走，便不在管道中存在，不可反复读取。采用半双工通信，数据一次只能在一个方向上流动。会自己进行阻塞，比如一方在读取，管道内没有数据的话会进行阻塞。

新建xv6-labs-2021/user/pingpong.c

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

int main(int argc, char *argv[])
{
    int pid;

    int p1[2];
    int p2[2];
    
    char buf[1];
    char* parentSendBuf = "p";
    char* childSendBuf  = "c";

    // 创建管道, 创建成功后0是读端, 1是写端
    if (pipe(p1) == -1) {
        printf("pipe error.\n");
        exit(-1);
    }
    if (pipe(p2) == -1) {
        printf("pipe error.\n");
        exit(-1);
    }

    pid = fork();
    if (pid < 0)  {
        printf("fork error.\n");
        exit(-1);
    }

    if (pid == 0){
        // 子线程
        close(p1[1]);
        close(p2[0]);
        read(p1[0], buf, sizeof(buf));
        printf("%d: received ping\n", getpid());
        write(p2[1], childSendBuf, 1);
    }
    else {
        // 父线程
        close(p1[0]);
        close(p2[1]);
        write(p1[1], parentSendBuf, 1);
        read(p2[0], buf, sizeof(buf));
        printf("%d: received pong\n", getpid());
    }

    exit(0);
}

Makefile中UPROGS中添加：

$U/_pingpong\

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-util pingpong
make: 'kernel/kernel' is up to date.
== Test pingpong == pingpong: OK (2.0s) 
    (Old xv6.out.pingpong failure log removed)
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

$ ./pingpong
4: received ping
3: received pong

primes (moderate)/(hard)

使用管道将 2 至 35 中的素数筛选出来。

首先将数字全部输入到最左边的管道，然后第一个进程打印出输入管道的第一个数 2 ，并将管道中所有 2 的倍数的数剔除。接着把剔除后的所有数字输入到右边的管道，然后第二个进程打印出从第一个进程中传入管道的第一个数 3 ，并将管道中所有 3 的倍数的数剔除。接着重复以上过程，最终打印出来的数都为素数。

新建xv6-labs-2021/user/primes.c

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

void primes(int fd) 
{
  int m;
  int n;
  if (read(fd, &m, sizeof(int)))
  {
    // 第一个数据一定是素数
    printf("prime %d\n", m);

    int p[2];
    int pid;

    pipe(p);

    pid = fork();
    if (pid == 0) 
    {
        close(p[0]);
        while (read(fd, &n, sizeof(int)))
        {
            // 如果该数不是管道中第一个数据的倍数
            if (n % m != 0) 
            {
                write(p[1], &n, sizeof(int));
            }
        }
        close(p[1]);
    }
    else if (pid > 0) 
    {
      close(p[1]);
      wait(0);
      primes(p[0]);
      close(p[0]);
    }
    else
    {
      printf("fork error!\n");
      exit(1);
    }
  }
  exit(0);
}

int main(int argc, char* argv[])
{
  int p[2];
  int pid;

  pipe(p);

  pid = fork();

  if (pid == 0)
  {
    int i;
    close(p[0]);
    for (i = 2; i <= 35; ++i) {
      write(p[1], &i, sizeof(int));
    }
    close(p[1]);
  } 
  else if (pid > 0) 
  {
    close(p[1]);
    // 父进程等待子进程把数据全部写入管道
    wait(0);
    primes(p[0]);
    close(p[0]);
  } 
  else 
  {
      printf("fork error!\n");
      exit(1);
  }
  exit(0);
}

Makefile中UPROGS中添加：

$U/_primes\

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-util primes
make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (2.0s) 
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ make qemu
...
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
$ 

find (moderate)

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

void 
find(const char* path, const char* filename)
{
  int fd;
  struct stat st;
  struct dirent de;
  char buf[512];
  char* p;

  fd = open(path, 0);
  if (fd < 0) {
    fprintf(2, "cannot open %s!\n", path);
    return;
  }
  
  if (fstat(fd, &st) < 0) {
    fprintf(2, "cannot stat %s!\n", path);
    close(fd);
    return;
  }

  if (st.type != T_DIR) {
    fprintf(2, "%s should be path!\n", path);
    close(fd);
    return;
  }

  if (strlen(path) + 1 + DIRSIZ + 1 > sizeof(buf)) {
    printf("path is too long!\n");
    close(fd);
    return;
  }

  strcpy(buf, path);
  p = buf+strlen(buf);
  *p++ = '/';

  while (read(fd, &de, sizeof(de)) == sizeof(de)) {
    if(de.inum == 0)
      continue;

    if (!strcmp(de.name, ".") || !strcmp(de.name, "..")) {
      continue;
    }

    memmove(p, de.name, DIRSIZ);
    p[DIRSIZ] = 0;
    if(stat(buf, &st) < 0){
      printf("cannot stat %s\n", buf);
      continue;
    }

    // printf("buf: %s, type: %d\n", buf, st.type);

    if (st.type == T_DIR) {
      
      find(buf, filename);
    }
    else if (st.type == T_FILE && !strcmp(de.name, filename)) {
      printf("%s\n", buf);
    }
  }
}

int 
main(int argc, char* argv[])
{
  if (argc != 3) {
    fprintf(2, "Usage: find path filename!\n");
    exit(1);
  }

  find(argv[1], argv[2]);

  exit(0);
}

$ make qemu
...
init: starting sh
$ echo > b
$ mkdir a
$ echo > a/b
$ find . b
./b
./a/b
$ 

xargs (moderate)

xargs命令的作用，是将标准输入转为命令行参数。

$ echo "hello world" | xargs echo
hello world

上面的代码将管道左侧的标准输入，转为命令行参数hello world，传给第二个echo命令。

$ echo "one two three" | xargs mkdir

上面的代码等同于mkdir one two three。如果不加xargs就会报错，提示mkdir缺少操作参数。

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

#define MAX_BUF_SIZE 1024

int 
main(int argc, char* argv[])
{
  if (argc < 2) {
      fprintf(2, "Usage: xargs commands\n");
      exit(1);
  } 

  int index = 0;
  // 子进程exec的参数
  char* argvs[MAXARG];
  for (int i = 1; i < argc; ++i) {
      argvs[index++] = argv[i];
  }

  // 存放从管道读出的数据
  char buf[MAX_BUF_SIZE] = {"\0"};

  while (read(0, buf, MAX_BUF_SIZE) > 0) {
      char temp[MAX_BUF_SIZE] = {"\0"};

      // xargs参数后面再追加参数
      argvs[index] = temp;

      for (int i = 0; i < strlen(buf); ++i) {
          if (buf[i] == '\n') {
              if (fork() == 0) {
                  exec(argv[1], argvs);
              }
              wait(0);
          }
          else {
              temp[i] = buf[i];
          }
      }
  }
  exit(0);
}

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-util xargs
make: 'kernel/kernel' is up to date.
== Test xargs == xargs: OK (3.9s) 

$ echo hello too | xargs echo bye
bye hello too
$

Create a new file, time.txt, and put in it a single integer, the number of hours you spent on the lab.

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ make grade
...
== Test sleep, no arguments == 
$ make qemu-gdb
sleep, no arguments: OK (4.0s) 
== Test sleep, returns == 
$ make qemu-gdb
sleep, returns: OK (1.9s) 
== Test sleep, makes syscall == 
$ make qemu-gdb
sleep, makes syscall: OK (1.4s) 
== Test pingpong == 
$ make qemu-gdb
pingpong: OK (1.6s) 
== Test primes == 
$ make qemu-gdb
primes: OK (1.9s) 
== Test find, in current directory == 
$ make qemu-gdb
find, in current directory: OK (1.8s) 
== Test find, recursive == 
$ make qemu-gdb
find, recursive: OK (2.5s) 
== Test xargs == 
$ make qemu-gdb
xargs: OK (3.1s) 
== Test time == 
time: OK 
Score: 100/100
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

Lab2: system calls

$ git fetch
$ git checkout syscall
$ make clean

系统调用全流程:

user/user.h: 用户态程序调用跳板函数 trace()
user/usys.S: 跳板函数 trace() 使用 CPU 提供的 ecall 指令，调用到内核态
kernel/syscall.c 到达内核态统一系统调用处理函数 syscall()，所有系统调用都会跳到这里来处理。
kernel/syscall.c syscall() 根据跳板传进来的系统调用编号，查询 syscalls[] 表，找到对应的内核函数并调用。
kernel/sysproc.c 到达 sys_trace() 函数，执行具体内核操作

这么繁琐的调用流程的主要目的是实现用户态和内核态的良好隔离。

并且由于内核与用户进程的页表不同，寄存器也不互通，所以参数无法直接通过 C 语言参数的形式传过来，而是需要使用 argaddr、argint、argstr 等系列函数，从进程的 trapframe 中读取用户进程寄存器中的参数。

同时由于页表不同，指针也不能直接互通访问（也就是内核不能直接对用户态传进来的指针进行解引用），而是需要使用 copyin、copyout 方法结合进程的页表，才能顺利找到用户态指针（逻辑地址）对应的物理内存地址。

System call tracing (moderate)

trace(1 « SYS_fork)表示 trace 命令后面的第一个参数是一个数字，这个数字怎么来的呢。通过将1左移系统调用号的位数。比如说例子中的32是将1左移五位，所以系统调用号就是5，对应的就是read，所以就只追踪read系统调用。而这个mask也是这样用的。第n位为1，就表示追踪第n个系统调用。

Makefile

UPROGS=\
    ...
    $U/_trace\

在user/user.h中添加系统调用函数定义

// system calls
...
int trace(int);

在user/usys.pl中添加入口

entry("trace");

该文件在make后生成user/usys.S汇编文件，将系统调用编号通过li(load imm)存入a7寄存器，然后使用ecall进入内核态。

.global trace
trace:
 li a7, SYS_trace
 ecall
 ret

在kernel/syscall.h中定义系统调用编号

// System call numbers
...
#define SYS_trace  22

kernel/proc.h

在proc结构体中添加一个trace_mast字段，之后在fork函数中复制该字段到新进程。

// Per-process state
struct proc {
  ...
  int trace_mask;
};

kernel/proc.c

static struct proc*
allocproc(void)
{
  ...
  p->trace_mask = 0;
  return p;
}

int
fork(void)
{
  ...
  np->trace_mask = p->trace_mask;
  ...
}

kernel/sysproc.c

// 通过argint函数读取参数，然后设置给trace_mask字段
uint64
sys_trace(void)
{
  int trace_arg;

  if(argint(0, &trace_arg) < 0)
    return -1;

  struct proc* p = myproc();
  p->trace_mask |= trace_arg;
  
  return 0;
}

kernel/syscall.c

extern uint64 sys_trace(void);

static uint64 (*syscalls[])(void) = {
  ...
  [SYS_trace]   sys_trace,
  ...
};

/*
  这里是 C 语言数组的一个语法，表示以方括号内的值作为元素下标。
  比如 int arr[] = {[3] 2333, [6] 6666} 代表 arr 的下标 3 的元素为 2333，
  下标 6 的元素为 6666，其他元素填充 0 的数组。（该语法在 C++ 中已不可用）
*/
const char *syscall_names[] = {
  [SYS_fork]    "fork",
  [SYS_exit]    "exit",
  [SYS_wait]    "wait",
  [SYS_pipe]    "pipe",
  [SYS_read]    "read",
  [SYS_kill]    "kill",
  [SYS_exec]    "exec",
  [SYS_fstat]   "fstat",
  [SYS_chdir]   "chdir",
  [SYS_dup]     "dup",
  [SYS_getpid]  "getpid",
  [SYS_sbrk]    "sbrk",
  [SYS_sleep]   "sleep",
  [SYS_uptime]  "uptime",
  [SYS_open]    "open",
  [SYS_write]   "write",
  [SYS_mknod]   "mknod",
  [SYS_unlink]  "unlink",
  [SYS_link]    "link",
  [SYS_mkdir]   "mkdir",
  [SYS_close]   "close",
  [SYS_trace]   "trace",
};


void
syscall(void)
{
  ...
  // 获取系统调用编号
  num = p->trapframe->a7;
  ...
  // 根据该系统编号查找syscalls数组中对应的处理函数并调用
  ...
  p->trapframe->a0 = syscalls[num]();
  // 判断掩码是否匹配
  if ((1<<num)&(p->trace_mask)) {
    printf("%d: syscall %s -> %d\n", p->pid, syscall_names[num], p->trapframe->a0);
  }
  ...
}

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-syscall trace
make: 'kernel/kernel' is up to date.
== Test trace 32 grep == trace 32 grep: OK (2.8s) 
== Test trace all grep == trace all grep: OK (0.8s) 
== Test trace nothing == trace nothing: OK (1.5s) 
== Test trace children == trace children: OK (18.3s) 
    (Old xv6.out.trace_children failure log removed)
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

Sysinfo (moderate)

添加一个系统调用，返回空闲的内存、以及已创建的进程数量。

Makefile

UPROGS=\
    ...
    $U/_sysinfo\
	$/_sysinfotest\

user/user.h

struct sysinfo;

// system calls
...
int sysinfo(struct sysinfo*);

user/usys.pl

entry("sysinfo");

kernel/syscall.h

#define SYS_sysinfo 23

kernel/syscall.c

extern uint64 sys_sysinfo(void);

static uint64 (*syscalls[])(void) = {
  ...
  [SYS_sysinfo]   sys_sysinfo,
};

const char *syscall_names[] = {
  ...
  [SYS_sysinfo]   "sysinfo",
};

新建user/sysinfo.c

#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/sysinfo.h"
#include "user/user.h"

int
main(int argc, char *argv[])
{
  if (argc != 1) {
    fprintf(2, "sysinfo need not param\n");
    exit(1);
  }

  struct sysinfo info;
  sysinfo(&info);
  printf("free space:%d, used process num:%d\n", info.freemem, info.nproc);
  exit(0);
}

kernel/sysproc.c

#include "sysinfo.h"

uint64
sys_sysinfo(void)
{
  // 从用户态读入一个指针，作为存放 sysinfo 结构的缓冲区
  uint64 addr;
  if (argaddr(0, &addr) < 0)
    return -1;

  struct sysinfo sinfo;
  sinfo.freemem = count_free_mem();
  sinfo.nproc = count_process();

  // 使用 copyout，结合当前进程的页表，获得进程传进来的指针（逻辑地址）对应的物理地址
  // 然后将 &sinfo 中的数据复制到该指针所指位置，供用户进程使用。
  if (copyout(myproc()->pagetable, addr, (char*)&sinfo, sizeof(sinfo)) < 0)
    return -1;

  return 0;
}

获取空闲内存：

在内核的头文件中声明计算空闲内存的函数，因为是内存相关的，所以放在 kalloc、kfree 等函数的的声明之后。

kernel/defs.h

// kalloc.c
...
uint64          count_free_mem(void);

内核通过kmen.freelist链表维护未使用的内存，链表的每个结点对应一个页表大小（PGSIZE）。

分配内存时从链表头部取走一个页表大小，释放内存时会使用头插法插入到该链表，因此计算未使用内存的字节数（freemem）只需要遍历该链表得到链表结点数，然后与页表大小相乘即可。

在 kalloc.c 中添加计算空闲内存的函数：

kernel/kalloc.c

uint64 count_free_mem(void)
{
  acquire(&kmem.lock);

  uint64 free_mem_bytes = 0;
  struct run *r = kmem.freelist;
  while (r) {
    free_mem_bytes += PGSIZE;
    r = r->next;
  }

  release(&kmem.lock);

  return free_mem_bytes;
}

获取运行的进程数：

kernel/defs.h

// proc.c
...
uint64          count_process(void);

kernel/proc.c

uint64 count_process(void)
{
  uint64 cnt = 0;

  struct proc *p;
  for (p = proc; p < &proc[NPROC]; p++) {
    if (p->state != UNUSED) {
      cnt++;
    }
  }

  return cnt;
}

$ sysinfo
free space:133386240, used process num:3

$ sysinfotest
sysinfotest: start
sysinfotest: OK


jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ ./grade-lab-syscall sysinfo
make: 'kernel/kernel' is up to date.
== Test sysinfotest == sysinfotest: OK (6.7s) 
    (Old xv6.out.sysinfotest failure log removed)
jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ 

Lab3: page tables

$ git fetch
$ git checkout pgtbl
$ make clean

Speed up system calls (easy)

在xv6中，如果用户态调用系统调用，就会切换到内核态，这中间一定是有开销的，至少CPU要保存用户态进程的上下文，然后CPU被内核占有，系统调用完成后再切换回来。

这个实验就是要加速getpid()。怎么加速呢？在内核和用户程序之间创建一个共享的只读页，这样内核往这个页里写入数据的时候，用户程序就可以不经复杂的系统调用直接读取它了。

实验要求，把一个只读页从USYSCALL(memlayout.h中定义的一个虚拟地址)映射的内核的某一个地方，并在页的起始处存储一个结构体struct usyscall。

For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping.

user/ulib.c

#ifdef LAB_PGTBL
int
ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;
  return u->pid;
}
#endif

很显然，ugetpid()直接从USYSCALL这个地址读数据，因此我们需要把usyscall结构写到此页表的开头。

You can perform the mapping in proc_pagetable() in kernel/proc.c. 提示说在proc_pagetable里面设置映射。

我们设置一个新的页usyscall，它位于trapframe的下面。

我们可以仿照trapframe的操作，在struct proc中添加一个参数struct usyscall *usyspage，然后用kalloc()分配一页内存，地址指向usyspage，并把该进程的pid存到页表中。稍后我们就把用户内存中的USYSCALL映射到这里。

kernel/proc.h

struct proc {
  ...
  struct trapframe *trapframe;
  struct usyscall *usyscall;
  ...
}

kernel/proc.c

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

  if ((p->usyscall = (struct usyscall*)kalloc()) == 0) {
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  p->usyscall->pid = p->pid;

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

usyspage有了值，就可以做映射操作了。这里要求只读页，因此把权限设成PTE_R，另外还要加上PTE_U，xv6手册里表明，不加PTE_U的页默认在supervisor mode里运行。

kernel/proc.c

pagetable_t
proc_pagetable(struct proc *p)
{
  ...
if(mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall), PTE_R | PTE_U) < 0) {
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }
  ...
}

然后做好释放，仿照freeproc里对trapframe里的操作来释放usyspage; 改下面这个proc_freepagetable函数，加上对USYSCALL的操作:

kernel/proc.c

static void
freeproc(struct proc *p)
{
  ...
  if(p->usyscall)
  kfree((void*)p->usyscall);
  p->usyscall = 0;
  ...
}

void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmunmap(pagetable, USYSCALL, 1, 0);
  uvmfree(pagetable, sz);
}

Print a page table (easy)

kernel/defs.h

// vm.c
...
void            vmprint(pagetable_t pagetable);

kernel/vm.c

void vmp(pagetable_t pagetable, int level)
{
  // 遍历该级页表的所有条目
  for (int i = 0; i < 512; ++i)
  {
    pte_t pte = pagetable[i];
    // 如果该条目有效则打印
    if (pte & PTE_V) {
      pagetable_t child = (pagetable_t)PTE2PA(pte);
      if (level == 2) printf("..");
      if (level == 1) printf(".. ..");
      if (level == 0) printf(".. .. ..");
      printf("%d: pte %p pa %p\n", i, pte, child);

      // 如果该PTE指向下一级页表则继续向下遍历, 对于指向下一级页表的 PTE 来说，它的标记位的R(可读)、W(可写)、X(可执行)均为 0
      if ((pte & (PTE_R | PTE_W | PTE_X)) == 0) {
        vmp(child, level - 1);
      }
    }
  }
}

void vmprint(pagetable_t pagetable)
{
  printf("page table %p\n", pagetable);
  vmp(pagetable, 2);
}

kernel/exec.c

int
exec(char *path, char **argv)
{
  ...
  // 打印 xv6 启动时的第 1 个进程的页表
  if (p->pid == 1) {
    vmprint(p->pagetable);
  }

  return argc;
  ...
}

运行结果

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ make qemu
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

xv6 kernel is booting

hart 2 starting
hart 1 starting
page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..509: pte 0x0000000021fdd813 pa 0x0000000087f76000
.. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000
init: starting sh
$ 

Detecting which pages have been accessed (hard)

从一个用户页表地址开始，搜索所有被访问过的页并返回一个bitmap来显示这些页是否被访问过。比如说，如果第二个页被访问过了，bitmap里从右往左数第二个bit就是1。

遍历输入参数表示的所有虚拟页在第 1 级页表中的 PTE，查看 PTE 的标记位 PTE_A，如果 PTE_A 为 1，则将掩码对应的位置 1，然后将该 PTE 的 PTE_A 位清空。

PTE_A位是由硬件设置的，所以我们只需要检测它就可以了。

kernel/riscv.h

#define PTE_A (1L << 6)

kernel/defs.h

// vm.c
...
pte_t*          walk(pagetable_t pagetable, uint64 va, int alloc);

kernel/sysproc.c

#ifdef LAB_PGTBL
int
sys_pgaccess(void)
{
  // lab pgtbl: your code here.
  uint64 addr;  // 虚拟页起始地址
  int pagenum;  // 待检测虚拟页个数
  uint64 mask;  // 稍后写到用户空间

  if (argaddr(0, &addr) < 0)
    return -1;
  if (argint(1, &pagenum) < 0)
    return -1;
  if (argaddr(2, &mask) < 0)
    return -1;

  // mask只有64位，待检测页最大个数为64
  if (pagenum > 64)
    return -1;

  uint64 bitmap = 0;
  pagetable_t pagetable = myproc()->pagetable;

  // 遍历所有页
  for (int i = 0; i < pagenum; i++) {
    uint64 va = addr + i * PGSIZE;
    pte_t *pte = walk(pagetable, va, 0);
    if (*pte & PTE_A) {
      bitmap |= (1 << i);
      *pte &= ~PTE_A;  //  clear PTE_A after checking
    }
  }

  // 写回用户空间
  copyout(pagetable, mask, (char*)&bitmap, sizeof(bitmap));

  return 0;
}
#endif

...
== Test pgtbltest == 
$ make qemu-gdb
(11.7s) 
== Test   pgtbltest: ugetpid == 
  pgtbltest: ugetpid: OK 
== Test   pgtbltest: pgaccess == 
  pgtbltest: pgaccess: OK 
== Test pte printout == 
$ make qemu-gdb
pte printout: OK (1.5s) 
...

参考资料

https://zhuanlan.zhihu.com/p/429304672
https://zhuanlan.zhihu.com/p/417239005
https://zhuanlan.zhihu.com/p/522878216
https://blog.csdn.net/u013577996/article/details/109582932

Lab4: traps

$ git fetch
$ git checkout traps
$ make clean

RISC-V assembly (easy)

首先，执行 make fs.img 指令，进行编译。然后查看生成的 user/call.asm 文件，其中的 main 函数如下：

000000000000001c <main>:

void main(void) {
  1c:	1141                	addi	sp,sp,-16
  1e:	e406                	sd	ra,8(sp)
  20:	e022                	sd	s0,0(sp)
  22:	0800                	addi	s0,sp,16
  printf("%d %d\n", f(8)+1, 13);
  24:	4635                	li	a2,13
  26:	45b1                	li	a1,12
  28:	00000517          	auipc	a0,0x0
  2c:	7b050513          	addi	a0,a0,1968 # 7d8 <malloc+0xea>
  30:	00000097          	auipc	ra,0x0
  34:	600080e7          	jalr	1536(ra) # 630 <printf>
  exit(0);
  38:	4501                	li	a0,0
  3a:	00000097          	auipc	ra,0x0
  3e:	27e080e7          	jalr	638(ra) # 2b8 <exit>

Q: 哪些寄存器存储了函数调用的参数？举个例子，main 调用 printf 的时候，13 被存在了哪个寄存器中？

A: A1. a0-a7, a2.

Q: main 中调用函数 f 对应的汇编代码在哪？对 g 的调用呢？ (提示：编译器有可能会内联(inline)一些函数)

A: nowhere, compiler optimization by inline function.

其实是没有这样的代码。 g(x) 被内联到 f(x) 中，然后 f(x) 又被进一步内联到 main() 中。所以看到的不是函数跳转，而是优化后的内联函数。

Q: printf 函数所在的地址是？

A: 0x0000000000000630 (ra=pc=0x30, 1536(ra)=0x0000000000000630).

其实，直接在 user/call.asm 代码中一直找，就能找到 printf 函数的地址。

也可以通过计算得到，首先将当前程序计数器的值赋给 ra 寄存器。auipc ra, 0x0，是指将当前立即数向右移动12位，然后加上 pc 寄存器的值，赋给 ra 寄存器，由于立即数为 0，因此 ra 的值即为 pc 的值。当前指令在0x30处，因此 pc = 0x30。1536(ra) 是指 1536 加上 ra 寄存器的值，1536 转为16进制再加上0x30 即为 0x0000000000000630。刚好是 printf 的地址。

Q: 在 main 中 jalr 跳转到 printf 之后，ra 的值是什么？

A: 0x38(ra=pc+4).

jalr 指令会将 pc + 4 赋给当前寄存器，刚好是其下一条指令的地址。

Q: 运行下面的代码
```
unsigned int i = 0x00646c72;
printf("H%x Wo%s", 57616, &i);
```
输出是什么？如果 RISC-V 是大端序的，要实现同样的效果，需要将 i 设置为什么？需要将 57616 修改为别的值吗？

A: He110 World, 0x726c6400, no change for 57616.

％x 表示以十六进制数形式输出整数，57616 的16进制表示就是 e110，与大小端序无关。 %s 是输出字符串，以整数 i 所在的开始地址，按照字符的格式读取字符，直到读取到 ‘\0’ 为止。当是小端序表示的时候，内存中存放的数是：72 6c 64 00，刚好对应rld。当是大端序的时候，则反过来了，因此需要将 i 以16进制数的方式逆转一下。

Q: 在下面的代码中，’y=’ 之后会答应什么？ (note: 答案不是一个具体的值) 为什么?
```
printf("x=%d y=%d", 3);
```
A: print the value of a2 register.

printf 接收到了两个参数，但实际需要三个参数，最后一个参数是放在 a2 寄存器中，由于没有输入第三个参数，因此 a2 寄存器中目前有啥就输出啥。

Backtrace (moderate)

主要需要我们理解函数调用栈的结构，一般每个函数栈帧的头部是返回地址和上一栈帧的尾部，抓住这一点，我们可以利用当前栈帧地址一直回溯到内核的所有调用栈。

在 xv6 中，fp为当前函数的栈顶指针，sp为栈指针。fp-8 存放返回地址，fp-16 存放原栈帧（调用函数的fp）。

内核为每个进程分配了一段栈帧内存页，用于存放栈。函数调用就是在该位置处进行的。需要记得的是：fp为当前函数的栈顶指针，sp为栈指针。fp-8 存放返回地址，fp-16 存放原栈帧（调用函数的fp）。因此，我们可以通过当前函数的栈顶指针 fp 来找到调用该函数的函数栈帧，然后递归地进行下去。直到到达当前页的开始地址。

kernel/defs.h

// printf.c
...
void            backtrace(void);

由于我们需要先获取到当前函数的栈帧 fp 的值，该值存放在 s0 寄存器中，因此需要写一个能够读取 s0 寄存器值得函数。按照实验指导书给的方法，在 kernel/riscv.h 添加读取 s0 寄存器的函数：

kernel/riscv.h

// read the current frame pointer
static inline uint64
r_fp()
{
uint64 x;
asm volatile("mv %0, s0" : "=r" (x));
return x;
}

kernel/printf.c

void backtrace(void) 
{
  uint64 fp = r_fp(), top = PGROUNDUP(fp);
  printf("backtrace:\n");
  for (; fp < top; fp = *((uint64*)(fp-16))) {
    printf("%p\n", *((uint64*)(fp-8)));
  }
}

在 kernel/printf.c 文件中的 panic 函数里添加 backtrace 的函数调用；在 sys_sleep 代码中也添加同样的函数调用。

kernel/printf.c

void
panic(char *s)
{
  pr.locking = 0;
  printf("panic: ");
  printf(s);
  printf("\n");
  backtrace();
  panicked = 1; // freeze uart output from other CPUs
  for(;;)
    ;
}

kernel/sysproc.c

uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  if(argint(0, &n) < 0)
    return -1;
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(myproc()->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  backtrace();
  return 0;
}

Alarm (hard)

实现一个定时调用的函数，每过一定数目的 cpu 的切片时间，调用一个用户函数，同时，在调用完成后，需要恢复到之前没调用时的状态。

user/user.h

// system calls
...
int sigalarm(int ticks, void (*handler)());
int sigreturn(void);

在 user/usys.pl 添加 entry，用于生成汇编代码：

entry("sigalarm");
entry("sigreturn");

kernel/syscall.h

#define SYS_sigalarm 22
#define SYS_sigreturn 23

kernel/syscall.c

extern uint64 sys_sigalarm(void);
extern uint64 sys_sigreturn(void);

[SYS_sigalarm]  sys_sigalarm,
[SYS_sigreturn] sys_sigreturn,

kernel/sysproc.c

uint64 sys_sigreturn(void)
{
  struct proc* p = myproc();
  *p->trapframe = *p->pretrapframe;
  p->ticks = 0;
  return 0;
}

在 kernel/proc.h 中的 proc 结构体添加字段，用于记录时间间隔，经过的时钟数和调用的函数信息：

int interval;
uint64 handler;
int ticks;

struct trapframe *pretrapframe;

在 kernel/sysproc.c 编写 sys_sigalarm() 函数，给 proc 结构体赋值：

uint64 sys_sigalarm(void)
{
  int interval;
  uint64 handler;
  struct proc *p;
  if (argint(0, &interval) < 0 || argaddr(1, &handler) < 0 || interval < 0) {
    return -1;
  }
  p = myproc();
  p->interval = interval;
  p->handler= handler;
  p->ticks = 0;
  return 0;
}

kernel/proc.c 的 allocproc 函数:

  p->interval = 0;
  p->handler = 0;
  p->ticks = 0;

  if ((p->pretrapframe = (struct trapframe*)kalloc()) == 0) {
     release(&p->lock);
  }

在进程结束后释放内存（freeproc 函数）：

  p->interval = 0;
  p->handler = 0;
  p->ticks = 0;

  if (p->pretrapframe)
    kfree((void*)p->pretrapframe);

在每次时钟中断处理时，判断是否调用 handler，如果调用了，就存储当前的 trapframe，用于调用之后的恢复 usertrap() in kernel/trap.c：

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2) {
    if (p->interval) {
      if (p->ticks == p->interval) {
        *p->pretrapframe = *p->trapframe;
        p->trapframe->epc = p->handler;
      }
      p->ticks++;
    }
    yield();
  }

修改 Makefile 文件中的 UPROGS 部分, 添加对 alarmtest.c 的编译:

UPROGS=\
    ...
	$U/_alarmtest\

make grade测试:

...
== Test backtrace test == 
$ make qemu-gdb
backtrace test: OK (5.0s) 
== Test running alarmtest == 
$ make qemu-gdb
(9.7s) 
== Test   alarmtest: test0 == 
  alarmtest: test0: OK 
== Test   alarmtest: test1 == 
  alarmtest: test1: OK 
== Test   alarmtest: test2 == 
  alarmtest: test2: OK 
...

参考资料

https://zhuanlan.zhihu.com/p/440454679
https://zhuanlan.zhihu.com/p/512353644

Lab5: Copy-on-Write Fork for xv6

$ git fetch
$ git checkout cow
$ make clean

实验只有一个任务，就是实现一个内存的写时复制机制（copy-on-write fork），也称为 COW。为什么要实现这个功能呢，主要原因是：

在 shell 中执行指令时，首先会 fork 一个子进程，然后在子进程中使用 exec 执行 shell 中的指令。在这个过程中，fork 需要完整的拷贝所有父进程的地址空间，但在 exec 执行时，又会完全丢弃这个地址空间，创建一个新的，因此会造成很大的浪费。

为了优化这个特定场景（fork 时）的内存利用率，我们可以在 fork 时，并不实际分配内存（与上一个实验的懒分配很像），而是让子进程和父进程共享相同的内存区域（页表不同，但指向的物理地址相同）。但为了保证进程之间的隔离性，我们不能同时对这块区域进行写操作，因此，设置共享的内存地址只有读权限。当需要向内存页中写入数据时，会触发缺页中断，此时再拷贝一个内存页，更新进程的页表，将内容写进去，然后重新执行刚才出错的指令。

在这个过程中，需要为每个物理内存页保存一个指向该内存页的页表数量。当为 0 时，表示没有进程使用该内存页，可以释放了；大于 1 时，每当有进程释放该内存页时，将对应的数值减一。

需要注意的是，这里要标记写入内存是 COW 场景。否则，如果真的有一个页面只能读不能写的话，就会出现问题。这里我们使用的是 PTE 页表项保留的标记位 RSW。

创建 page 的计数数组

不是所有的物理内存都可以被用户进程映射到的，这里有一个范围，即 KERNBASE 到 PHYSTOP。

由于一个页表的大小（PGSIZE）是 4096，因此数组的长度可以定义为：(PHYSTOP - KERNBASE) / PGSIZE

在 kernel/kalloc.c 中定义一个用于计数的数组：

uint page_ref[(PHYSTOP - KERNBASE) / PGSIZE];

在 kernel/riscv.h 中定义 COW 标记位和计算物理内存页下标的宏函数：

#define PTE_COW (1L << 8)

#define COW_INDEX(pa) (((uint64)(pa) - KERNBASE) >> 12)

kernel/kalloc.c:

void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r) {
    memset((char*)r, 5, PGSIZE); // fill with junk
    page_ref[COW_INDEX(r)] = 1;  // 设置值为1
  }
    
  return (void*)r;
}

void
kfree(void *pa)
{
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // 首先需要判断计数值是否大于1
  if (page_ref[COW_INDEX(pa)] > 1) {
    page_ref[COW_INDEX(pa)]--;
    return;
  }
  page_ref[COW_INDEX(pa)] = 0;

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

uvmcopy

将子进程的页表项中的所有虚拟地址全部映射到父进程的物理页面里面。在创建好计数数组后，在fork时，直接使用原来的物理页进行映射：

kernel/vm.c:

extern uint page_ref[];


int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  //char *mem;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    pa = PTE2PA(*pte);

    /*
      flags = PTE_FLAGS(*pte);
      if((mem = kalloc()) == 0)
        goto err;
      memmove(mem, (char*)pa, PGSIZE);
      if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
        kfree(mem);
        goto err;
      }
    */
    *pte = (*pte & ~PTE_W) | PTE_COW;
    flags = PTE_FLAGS(*pte);
    if (mappages(new, i, PGSIZE, pa, flags) != 0) {
      goto err;
    }
    page_ref[COW_INDEX(pa)]++;
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

处理中断usertrap

在发生写入没有写权限的页面时，就会处罚page fault的trap，此时我们需要申请新的物理页面然后映射到虚拟地址上，然后再次重新执行该指令。

kernel/trap.c

else if (r_scause() == 15) {
    // r_stval()返回RISC-V的stval寄存器,它包含了引起页面故障的虚拟地址。
    uint64 va = r_stval();
    if (va >= p->sz)
      p->killed = 1;
    else if (cow_alloc(p->pagetable, va))
      p->killed = 1;
}

kernel/defs.h

// kalloc.c
...
int             cow_alloc(pagetable_t pagetable, uint64 va);

kernel/kalloc.c

extern pte_t *walk(pagetable_t pagetable, uint64 va, int alloc);

int cow_alloc(pagetable_t pagetable, uint64 va)
{
  va = PGROUNDDOWN(va);
  if (va >= MAXVA) return -1;
  pte_t *pte = walk(pagetable, va, 0);
  if (pte == 0) return -1;
  uint64 pa = PTE2PA(*pte);
  if (pa == 0) return -1;
  uint64 flags = PTE_FLAGS(*pte);
  if (flags & PTE_COW) {
    uint64 mem = (uint64)kalloc();
    if (mem == 0) return -1;
    memmove((char*)mem, (char*)pa, PGSIZE);
    uvmunmap(pagetable, va, 1, 1);
    flags = (flags | PTE_W) & ~PTE_COW;
    if (mappages(pagetable, va, PGSIZE, mem, flags) != 0) {
      kfree((void*)mem);
      return -1;
    }
  }
  return 0;
}

copyout

kernel/vm.c

int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
  uint64 n, va0, pa0;

  while(len > 0){
    va0 = PGROUNDDOWN(dstva);
    if (cow_alloc(pagetable, va0) != 0)
      return -1;
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    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;
}

jason@jason-virtual-machine:~/6.S081/xv6-labs-2021$ make grade
...
== Test running cowtest == 
$ make qemu-gdb
(19.6s) 
== Test   simple == 
  simple: OK 
== Test   three == 
  three: OK 
== Test   file == 
  file: OK 
== Test usertests == 
$ make qemu-gdb
(474.6s) 
    (Old xv6.out.usertests failure log removed)
== Test   usertests: copyin == 
  usertests: copyin: OK 
== Test   usertests: copyout == 
  usertests: copyout: OK 
== Test   usertests: all tests == 
  usertests: all tests: OK 
...

参考资料

https://zhuanlan.zhihu.com/p/442455606

Lab6: Multithreading

$ git fetch
$ git checkout thread
$ make clean

Uthread: switching between threads (moderate)

uthread.c

// Saved registers for kernel context switches.
struct context {
  uint64 ra;
  uint64 sp;

  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};

struct thread {
  struct context context;
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
};

在thread_create()中添加保存新线程返回地址和栈指针。（注意这里栈的初始化，由于栈是向下增长的，我们要给sp赋正确的初值）

void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  // YOUR CODE HERE
  t->context.ra = (uint64)func;
  t->context.sp = (uint64)(t->stack+STACK_SIZE);
}

进行调度的时候进行上下文的切换。

void 
thread_schedule(void)
{
  struct thread *t, *next_thread;

  /* Find another runnable thread. */
  next_thread = 0;
  t = current_thread + 1;
  for(int i = 0; i < MAX_THREAD; i++){
    if(t >= all_thread + MAX_THREAD)
      t = all_thread;
    if(t->state == RUNNABLE) {
      next_thread = t;
      break;
    }
    t = t + 1;
  }

  if (next_thread == 0) {
    printf("thread_schedule: no runnable threads\n");
    exit(-1);
  }

  if (current_thread != next_thread) {         /* switch threads?  */
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    /* YOUR CODE HERE
     * Invoke thread_switch to switch from t to next_thread:
     * thread_switch(??, ??);
     */
    thread_switch((uint64)&t->context, (uint64)&next_thread->context);
  } else
    next_thread = 0;
}

其中上下文切换的代码：

参考kernel/swtch.S保存当前线程的寄存器，恢复即将要切换到线程的寄存器。

uthread_switch.S

thread_switch:
	/* YOUR CODE HERE */
	sd ra, 0(a0)
	sd sp, 8(a0)
	sd s0, 16(a0)
	sd s1, 24(a0)
	sd s2, 32(a0)
	sd s3, 40(a0)
	sd s4, 48(a0)
	sd s5, 56(a0)
	sd s6, 64(a0)
	sd s7, 72(a0)
	sd s8, 80(a0)
	sd s9, 88(a0)
	sd s10, 96(a0)
	sd s11, 104(a0)

	ld ra, 0(a1)
	ld sp, 8(a1)
	ld s0, 16(a1)
	ld s1, 24(a1)
	ld s2, 32(a1)
	ld s3, 40(a1)
	ld s4, 48(a1)
	ld s5, 56(a1)
	ld s6, 64(a1)
	ld s7, 72(a1)
	ld s8, 80(a1)
	ld s9, 88(a1)
	ld s10, 96(a1)
	ld s11, 104(a1)

	ret    /* return to ra */

Using threads (moderate)

notxv6/ph.c

pthread_mutex_t locks[NBUCKET];

int
main(int argc, char *argv[])
{
  //...
  // 初始化locks
  for (int i = 0; i < NBUCKET; i++) {
    pthread_mutex_init(&locks[i], NULL);
  }

  // first the puts
  //...
}


static 
void put(int key, int value)
{
  int i = key % NBUCKET;

  // is the key already present?
  struct entry *e = 0;
  for (e = table[i]; e != 0; e = e->next) {
    if (e->key == key)
      break;
  }

  pthread_mutex_lock(&locks[i]);

  if(e){
    // update the existing key.
    e->value = value;
  } else {
    // the new is new.
    insert(key, value, &table[i], table[i]);
  }

  pthread_mutex_unlock(&locks[i]);
}

Barrier(moderate)

notxv6/barrier.c

static void
barrier_init(void)
{
  assert(pthread_mutex_init(&bstate.barrier_mutex, NULL) == 0);
  assert(pthread_cond_init(&bstate.barrier_cond, NULL) == 0);
  bstate.nthread = 0;
  bstate.round = 0;
}

static void 
barrier()
{
  // YOUR CODE HERE
  //
  // Block until all threads have called barrier() and
  // then increment bstate.round.
  //
  pthread_mutex_lock(&bstate.barrier_mutex);
  if (++bstate.nthread == nthread) {
    bstate.round++;
    bstate.nthread = 0;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }
  else {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}

Others

学习资料

https://csdiy.wiki/操作系统/MIT6.S081/
https://www.zhihu.com/column/c_1294282919087964160

环境安装

ubuntu 20.04.1

sudo apt-get install git build-essential gdb-multiarch qemu-system-misc gcc-riscv64-linux-gnu binutils-riscv64-linux-gnu 

调试技巧

make qemu #正常启动
make qemu-gdb #以gdb模式启动
print #将print的内容重定向到文件中

课程笔记

1.6 open系统调用

文件描述符本质上对应了内核中的一个表单数据。内核维护了每个运行进程的状态，内核会为每一个运行进程保存一个表单，表单的key是文件描述符。这个表单让内核知道，每个文件描述符对应的实际内容是什么。这里比较关键的点是，每个进程都有自己独立的文件描述符空间，所以如果运行了两个不同的程序，对应两个不同的进程，如果它们都打开一个文件，它们或许可以得到相同数字的文件描述符，但是因为内核为每个进程都维护了一个独立的文件描述符空间，这里相同数字的文件描述符可能会对应到不同的文件。

当你运行C语言并执行例如open系统调用时，从技术上来说，open是一个C函数，但是这个函数内的指令实际上是机器指令，也就是说我们调用的open函数并不是一个C语言函数，它是由汇编语言实现，组成这个系统调用的汇编语言实际上在RISC-V中被称为ecall。这个特殊的指令将控制权转给内核。之后内核检查进程的内存和寄存器，并确定相应的参数。

1.7 Shell

Shell运行名为ls的程序，文件系统中会有一个文件名为ls，这个文件中包含了一些计算机指令，所以实际上，当我输入ls时，我是在要求Shell运行位于文件ls内的这些计算机指令。

除了运行程序以外，Shell还会做一些其他的事情，比如，它允许你能重定向IO。比如，我输入 ls > out。

1.8 fork系统调用

fork创建了一个新的进程。当我们在Shell中运行东西的时候，Shell实际上会创建一个新的进程来运行你输入的每一个指令。所以，当我输入ls时，我们需要Shell通过fork创建一个进程来运行ls，这里需要某种方式来让这个新的进程来运行ls程序中的指令，加载名为ls的文件中的指令（也就是后面的exec系统调用）。

1.9 exec, wait系统调用

有关exec系统调用，有一些重要的事情，

exec系统调用会保留当前的文件描述符表单。所以任何在exec系统调用之前的文件描述符，例如0，1，2等。它们在新的程序中表示相同的东西。
通常来说exec系统调用不会返回，因为exec会完全替换当前进程的内存，相当于当前进程不复存在了，所以exec系统调用已经没有地方能返回了。

对于那些想要运行程序，但是还希望能拿回控制权的场景，可以先执行fork系统调用，然后在子进程中调用exec。

这里有一些东西需要注意，实际上我认为你们很多人已经注意到了，这里是一个常用的写法，先调用fork，再在子进程中调用exec。这里实际上有些浪费，fork首先拷贝了整个父进程的，但是之后exec整个将这个拷贝丢弃了，并用你要运行的文件替换了内存的内容。某种程度上来说这里的拷贝操作浪费了，因为所有拷贝的内存都被丢弃并被exec替换。在大型程序中这里的影响会比较明显。如果你运行了一个几G的程序，并且调用fork，那么实际就会拷贝所有的内存，可能会要消耗将近1秒钟来完成拷贝，这可能会是个问题。

在这门课程的后面，你们会实现一些优化，比如说copy-on-write fork，这种方式会消除fork的几乎所有的明显的低效，而只拷贝执行exec所需要的内存，这里需要很多涉及到虚拟内存系统的技巧。

Unix并没有一个直接的方法让子进程等待父进程。wait系统调用只能等待当前进程的子进程。所以wait的工作原理是，如果当前进程有任何子进程，并且其中一个已经退出了，那么wait会返回。但是如果当前进程没有任何子进程，比如在这个简单的例子中，如果子进程调用了wait，因为子进程自己没有子进程了，所以wait会立即返回-1，表明出现错误了，当前的进程并没有任何子进程。

如果一个进程调用fork两次，如果它想要等两个子进程都退出，它需要调用wait两次。每个wait会在一个子进程退出时立即返回。当wait返回时，你实际上没有必要知道哪个子进程退出了，但是wait返回了子进程的进程号，所以在wait返回之后，你就可以知道是哪个子进程退出了。

3.2 操作系统隔离性（isolation）

使用操作系统的一个原因，甚至可以说是主要原因就是为了实现multiplexing和内存隔离。

3.4 硬件对于强隔离的支持

硬件对于强隔离的支持包括了：user/kernle mode和虚拟内存。

特殊权限指令主要是一些直接操纵硬件的指令和设置保护的指令，例如设置page table寄存器、关闭时钟中断。

在处理器里面有一个flag，在处理器的一个bit，当它为1的时候是user mode，当它为0时是kernel mode。当处理器在解析指令时，如果指令是特殊权限指令，并且该bit被设置为1，处理器会拒绝执行这条指令。

实际上RISC-V还有第三种模式称为machine mode。在大多数场景下，我们会忽略这种模式。

在RISC-V中，如果你在用户空间（user space）尝试执行一条特殊权限指令，用户程序会通过系统调用来切换到kernel mode。

当用户程序执行系统调用，会通过ECALL触发一个软中断（software interrupt），软中断会查询操作系统预先设定的中断向量表，并执行中断向量表中包含的中断处理程序。中断处理程序在内核中，这样就完成了user mode到kernel mode的切换，并执行用户程序想要执行的特殊权限指令。

处理器包含了page table，而page table将虚拟内存地址与物理内存地址做了对应。

每一个进程都会有自己独立的page table，这样的话，每一个进程只能访问出现在自己page table中的物理内存。

操作系统会设置page table，使得每一个进程都有不重合的物理内存，这样一个进程就不能访问其他进程的物理内存，因为其他进程的物理内存都不在它的page table中。一个进程甚至都不能随意编造一个内存地址，然后通过这个内存地址来访问其他进程的物理内存。这样就给了我们内存的强隔离性。

ls程序有了一个内存地址0，echo程序也有了一个内存地址0。但是操作系统会将两个程序的内存地址0映射到不同的物理内存地址，所以ls程序不能访问echo程序的内存，同样echo程序也不能访问ls程序的内存。

3.5 User/Kernel mode切换

有一种方式能够让应用程序可以将控制权转移给内核（Entering Kernel）。

在RISC-V中，有一个专门的指令用来实现这个功能，叫做ECALL。ECALL接收一个数字参数，当一个用户程序想要将程序执行的控制权转移到内核，它只需要执行ECALL指令，并传入一个数字。这里的数字参数代表了应用程序想要调用的System Call。

假设我现在要执行另一个系统调用write，相应的流程是类似的，write系统调用不能直接调用内核中的write代码，而是由封装好的系统调用函数执行ECALL指令。所以write函数实际上调用的是ECALL指令，指令的参数是代表了write系统调用的数字。之后控制权到了syscall函数，syscall会实际调用write系统调用。

3.6 宏内核 vs 微内核（Monolithic Kernel vs Micro Kernel）

XV6中，所有的操作系统服务都在kernel mode中，这种形式被称为Monolithic Kernel Design（宏内核）。

另一种设计主要关注点是减少内核中的代码，它被称为Micro Kernel Design（微内核）。

3.7 编译运行kernel

代码主要有三个部分组成：

第一个是kernel。我们可以ls kernel的内容，里面包含了基本上所有的内核文件。因为XV6是一个宏内核结构，这里所有的文件会被编译成一个叫做kernel的二进制文件，然后这个二进制文件会被运行在kernle mode中。
第二个部分是user。这基本上是运行在user mode的程序。这也是为什么一个目录称为kernel，另一个目录称为user的原因。
第三部分叫做mkfs。它会创建一个空的文件镜像，我们会将这个镜像存在磁盘上，这样我们就可以直接使用一个空的文件系统。

第一个指令位于地址0x80000000，对应的是一个RISC-V指令：auipc指令。

传给QEMU的几个参数：

kernel：这里传递的是内核文件（kernel目录下的kernel文件），这是将在QEMU中运行的程序文件。
m：这里传递的是RISC-V虚拟机将会使用的内存数量
smp：这里传递的是虚拟机可以使用的CPU核数
drive：传递的是虚拟机使用的磁盘驱动，这里传入的是fs.img文件

3.8 QEMU

QEMU表现的就像一个真正的计算机一样。当你想到QEMU时，你不应该认为它是一个C程序，你应该把它想成一个真正的主板。当你通过QEMU来运行你的内核时，你应该认为你的内核是运行在这样一个主板之上。

主板有一个开关，一个RISC-V处理器，有支持外设的空间，比如说一个接口是连接网线的，一个是PCI-E插槽，主板上还有一些内存芯片，这是一个你可以在上面编程的物理硬件，而XV6操作系统管理这样一块主板。

在QEMU的主循环中，只在做一件事情：

读取4字节或者8字节的RISC-V指令。
解析RISC-V指令，并找出对应的操作码（op code）。我们之前在看kernel.asm的时候，看过一些操作码的二进制版本。通过解析，或许可以知道这是一个ADD指令，或者是一个SUB指令。
之后，在软件中执行相应的指令。

3.9 XV6 启动过程

内核使用的起始地址就是QEMU指定的0x80000000这个地址。

XV6从entry.s开始启动。

kinit：设置好页表分配器（page allocator）
kvminit：设置好虚拟内存，这是下节课的内容
kvminithart：打开页表，也是下节课的内容
processinit：设置好初始进程或者说设置好进程表单
trapinit/trapinithart：设置好user/kernel mode转换代码
plicinit/plicinithart：设置好中断控制器PLIC（Platform Level Interrupt - Controller），我们后面在介绍中断的时候会详细的介绍这部分，这是我们用来与磁盘和console交互方式
binit：分配buffer cache
iinit：初始化inode缓存
fileinit：初始化文件系统
virtio_disk_init：初始化磁盘
userinit：最后当所有的设置都完成了，操作系统也运行起来了，会通过userinit运行第一个进程

4.2 地址空间（Address Spaces）

创造虚拟内存的一个出发点是你可以通过它实现隔离性。如果你正确的设置了page table，并且通过代码对它进行正确的管理，那么原则上你可以实现强隔离。

每个程序都运行在自己的地址空间，并且这些地址空间彼此之间相互独立。如果cat程序想要向地址1000写入数据，那么cat只会向它自己的地址1000，而不是Shell的地址1000写入数据。

虚拟内存可以比物理内存更大，物理内存也可以比虚拟内存更大。其实就是通过page table来实现，这里非常灵活。

4.3 页表（Page Table）

我们如何能够实现地址空间呢？或者说如何在一个物理内存上，创建不同的地址空间？最常见的方法，同时也是非常灵活的一种方法就是使用页表（Page Tables）。

对于任何一条带有地址的指令，其中的地址应该认为是虚拟内存地址而不是物理地址。假设寄存器a0中是地址0x1000，那么这是一个虚拟内存地址。虚拟内存地址会被转到内存管理单元（MMU，Memory Management Unit）。内存管理单元会将虚拟地址翻译成物理地址。之后这个物理地址会被用来索引物理内存，并从物理内存加载，或者向物理内存存储数据。

为了能够完成虚拟内存地址到物理内存地址的翻译，MMU会有一个表单，表单中，一边是虚拟内存地址，另一边是物理内存地址。

通常来说，内存地址对应关系的表单也保存在内存中。所以CPU中需要有一些寄存器用来存放表单在物理内存中的地址。现在，在内存的某个位置保存了地址关系表单，我们假设这个位置的物理内存地址是0x10。那么在RISC-V上一个叫做SATP的寄存器会保存地址0x10。CPU就可以告诉MMU，可以从哪找到将虚拟内存地址翻译成物理内存地址的表单。

这里的基本想法是每个应用程序都有自己独立的表单，并且这个表单定义了应用程序的地址空间。所以当操作系统将CPU从一个应用程序切换到另一个应用程序时，同时也需要切换SATP寄存器中的内容，从而指向新的进程保存在物理内存中的地址对应表单。这样的话，cat程序和Shell程序中相同的虚拟内存地址，就可以翻译到不同的物理内存地址，因为每个应用程序都有属于自己的不同的地址对应表单。

内核会写SATP寄存器，写SATP寄存器是一条特殊权限指令。所以，用户应用程序不能通过更新这个寄存器来更换一个地址对应表单，否则的话就会破坏隔离性。所以，只有运行在kernel mode的代码可以更新这个寄存器。

实际情况不可能是一个虚拟内存地址对应page table中的一个条目。

RISC-V中是如何工作的：

第一步：不要为每个地址创建一条表单条目，而是为每个page创建一条表单条目，所以每一次地址翻译都是针对一个page。而RISC-V中，一个page是4KB，也就是4096Bytes。这个大小非常常见，几乎所有的处理器都使用4KB大小的page或者支持4KB大小的page。现在，内存地址的翻译方式略微的不同了。首先对于虚拟内存地址，我们将它划分为两个部分，index和offset，index用来查找page，offset对应的是一个page中的哪个字节。

有关RISC-V的一件有意思的事情是，虚拟内存地址都是64bit，这也说的通，因为RISC-V的寄存器是64bit的。但是实际上，在我们使用的RSIC-V处理器上，并不是所有的64bit都被使用了，也就是说高25bit并没有被使用。这样的结果是限制了虚拟内存地址的数量，虚拟内存地址的数量现在只有2^39个，大概是512GB。

39bit中，有27bit被用来当做index，12bit被用来当做offset。offset必须是12bit，因为对应了一个page的4096个字节。

在RISC-V中，物理内存地址是56bit。所以物理内存可以大于单个虚拟内存地址空间，但是也最多到2^56。大多数主板还不支持2^56这么大的物理内存，但是原则上，如果你能造出这样的主板，那么最多可以支持2^56字节的物理内存。

物理内存地址是56bit，其中44bit是物理page号（PPN，Physical Page Number），剩下12bit是offset完全继承自虚拟内存地址（也就是地址转换时，只需要将虚拟内存中的27bit翻译成物理内存中的44bit的page号，剩下的12bitoffset直接拷贝过来即可）。

page table最多会有2^27个条目（虚拟内存地址中的index长度为27），这是个非常大的数字。如果每个进程都使用这么大的page table，进程需要为page table消耗大量的内存，并且很快物理内存就会耗尽。所以实际上，硬件并不是按照这里的方式来存储page table。从概念上来说，你可以认为page table是从0到2^27，但是实际上并不是这样。实际中，page table是一个多级的结构。虚拟内存地址中的27bit的index，实际上是由3个9bit的数字组成（L2，L1，L0）。

4.4 页表缓存（Translation Lookaside Buffer）

当处理器从内存加载或者存储数据时，基本上都要做3次内存查找，第一次在最高级的page directory，第二次在中间级的page directory，最后一次在最低级的page directory。所以对于一个虚拟内存地址的寻址，需要读三次内存，这里代价有点高。所以实际中，几乎所有的处理器都会对于最近使用过的虚拟地址的翻译结果有缓存。这个缓存被称为：Translation Lookside Buffer（通常翻译成页表缓存）。你会经常看到它的缩写TLB。基本上来说，这就是Page Table Entry的缓存，也就是PTE的缓存。

当处理器第一次查找一个虚拟地址时，硬件通过3级page table得到最终的PPN，TLB会保存虚拟地址到物理地址的映射关系。这样下一次当你访问同一个虚拟地址时，处理器可以查看TLB，TLB会直接返回物理地址，而不需要通过page table得到结果。

如果你切换了page table，操作系统需要告诉处理器当前正在切换page table，处理器会清空TLB。因为本质上来说，如果你切换了page table，TLB中的缓存将不再有用，它们需要被清空，否则地址翻译可能会出错。

4.5 Kernel Page Table

地址0是保留的，地址0x10090000对应以太网，地址0x80000000对应DDR内存，处理器外的易失存储（Off-Chip Volatile Memory），也就是主板上的DRAM芯片。

地址0x1000是boot ROM的物理地址，当你对主板上电，主板做的第一件事情就是运行存储在boot ROM中的代码，当boot完成之后，会跳转到地址0x80000000，操作系统需要确保那个地址有一些数据能够接着启动操作系统。

有两件重要的事情：

第一件事情是，有一些page在虚拟内存中的地址很靠后，比如kernel stack在虚拟内存中的地址就很靠后。这是因为在它之下有一个未被映射的Guard page，这个Guard page对应的PTE的Valid 标志位没有设置，这样，如果kernel stack耗尽了，它会溢出到Guard page，但是因为Guard page的PTE中Valid标志位未设置，会导致立即触发page fault，这样的结果好过内存越界之后造成的数据混乱。立即触发一个panic（也就是page fault），你就知道kernel stack出错了。同时我们也又不想浪费物理内存给Guard page，所以Guard page不会映射到任何物理内存，它只是占据了虚拟地址空间的一段靠后的地址。

同时，kernel stack被映射了两次，在靠后的虚拟地址映射了一次，在PHYSTOP下的Kernel data中又映射了一次，但是实际使用的时候用的是上面的部分，因为有Guard page会更加安全。

第二件事情是权限。例如Kernel text page被标位R-X，意味着你可以读它，也可以在这个地址段执行指令，但是你不能向Kernel text写数据。通过设置权限我们可以尽早的发现Bug从而避免Bug。对于Kernel data需要能被写入，所以它的标志位是RW-，但是你不能在这个地址段运行指令，所以它的X标志位未被设置。（注，所以，kernel text用来存代码，代码可以读，可以运行，但是不能篡改，kernel data用来存数据，数据可以读写，但是不能通过数据伪装代码在kernel中运行）

4.6 kvminit 函数

main函数中调用的一个函数是kvminit，这个函数会设置好kernel的地址空间。

5.2 RISC-V vs x86

RISC-V中的RISC是精简指令集（Reduced Instruction Set Computer）的意思，而x86通常被称为CISC，复杂指令集（Complex Instruction Set Computer）。

8.2 Lazy page allocation

在XV6中，sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。这意味着，进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。

使用虚拟内存和page fault handler，我们完全可以用某种更聪明的方法来解决这里的问题，这里就是利用lazy allocation。核心思想非常简单，sbrk系统调基本上不做任何事情，唯一需要做的事情就是提升p->sz，将p->sz增加n，其中n是需要新分配的内存page数量。但是内核在这个时间点并不会分配任何物理内存。之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，因为我们还没有将新的内存映射到page table。

MIT 6.S081 LAB

Lab1: Xv6 and Unix utilities

sleep (easy)

pingpong (easy)

primes (moderate)/(hard)

find (moderate)

xargs (moderate)

Lab2: system calls

System call tracing (moderate)

Sysinfo (moderate)

Lab3: page tables

Speed up system calls (easy)

Print a page table (easy)

Detecting which pages have been accessed (hard)

参考资料

Lab4: traps

RISC-V assembly (easy)

Backtrace (moderate)

Alarm (hard)

参考资料

Lab5: Copy-on-Write Fork for xv6

参考资料

Lab6: Multithreading

Uthread: switching between threads (moderate)

Using threads (moderate)

Barrier(moderate)

Others

学习资料

环境安装

调试技巧

课程笔记

1.6 open系统调用

1.7 Shell

1.8 fork系统调用

1.9 exec, wait系统调用

3.2 操作系统隔离性（isolation）

3.4 硬件对于强隔离的支持

3.5 User/Kernel mode切换

3.6 宏内核 vs 微内核 （Monolithic Kernel vs Micro Kernel）

3.7 编译运行kernel

3.8 QEMU

3.9 XV6 启动过程

4.2 地址空间（Address Spaces）

4.3 页表（Page Table）

4.4 页表缓存（Translation Lookaside Buffer）

4.5 Kernel Page Table

4.6 kvminit 函数

5.2 RISC-V vs x86

8.2 Lazy page allocation

Comments

3.6 宏内核 vs 微内核（Monolithic Kernel vs Micro Kernel）