MIT 6.S081 All in one

闲着没事把 6.S081 2021 ~ 2025 年的实验都写了一遍。

Lab0 - 环境配置

系统为Archlinux物理机，环境如下：

安装依赖

参考：https://pdos.csail.mit.edu/6.828/2021/tools.html

首先安装转义riscv64的包：

sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb

riscv64-linux-gnu-gcc --version
qemu-system-riscv64 --version

riscv64-linux-gnu-gcc (GCC) 15.1.0
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

QEMU emulator version 10.2.2
Copyright (c) 2003-2025 Fabrice Bellard and the QEMU Project developers

安装 qemu:

图省事安装 qemu-arch-extra-git 就够了。用 qemu 环境比较多的同学可以直接安装 qemu-full

sudo pacman -S qemu-full

编译运行

参考：https://pdos.csail.mit.edu/6.828/2021/labs/util.html

实验用的 xv6 和 github 上的的不太一样，别傻乎乎去 clone github 上的。如果要其他年份的就把末尾的xv6-labs-2021改为其他年份就行。

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

在较早年份的实验中，xv6 默认是 master 分支，里面什么都没有，根据不同实验要求切换到相应分支即可。

git checkout util
ls
conf/    mkfs/         user/                  fs.img            gradelib.py  Makefile  xv6.out
kernel/  __pycache__/  compile_commands.json  grade-lab-pgtbl*  LICENSE      README

2021 - 2024 年的实验直接编译会提示各种编译错误。这里只说一下我遇到的，大多都是因为 -Werror 标志 把所有 warning 当 error 处理。图省事可以直接在 Makefile 里把这个 flag 删了。

1. 提示 user/sh.c:58:1: error: infinite recursion detected [-Werror=infinite-recursion]

在 user/sh.c 中 runcmd 函数前添加一行__attribute__((noreturn))即可。

2. 提示 user/usertests.c:2829:6: error: initialization of 'void (*)(char *)' from incompatible pointer type 'void (*)(void)' [-Wincompatible-pointer-types]

在 user/usertest.c 中将 rwsbrk() 添加一个 char * 参数即可。rwsbrk(char *argv)

2025 年的实验可以直接编译，无须任何改动。

然后运行 make qemu 即可

make qemu
riscv64-linux-gnu-gcc    -c -o kernel/entry.o kernel/entry.S
riscv64-linux-gnu-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_PGTBL -DLAB_PGTBL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie  -c -o kernel/kalloc.o kernel/kalloc.c
riscv64-linux-gnu-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_PGTBL -DLAB_PGTBL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie  -c -o kernel/string.o kernel/string.c

...

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
init: starting sh
$

最后出现这几行就说明编译成功了，按ctrl + a, x退出模拟环境。

配置 Lsp

一直使用 clangd 作为分析工具，需要 compile_commands.json 文件来告诉 clangd 编译参数。通过 bear 这个工具可以轻易的生成。

sudo pacman -S bear
make clean # 从头开始编译，否则生成的编译信息会不全
bear -- make qemu

xv6 根目录下出现 compile_commands.json 文件即可。

clangd 分析会生成 .cache/ 目录，不应该加入 git 维护的内容中，所以在 .gitignore 文件里新增一行：

...
ph
barrier
.cache/

至此 xv6 环境就配置完毕。

Lab1 util：Unix utilities | UNIX 实用程序

本节实验主要用于入门系统编程，利用系统调用底层工具。根据课程官网的要求，需要看完Lecture 1,阅读完教材第一章$Operation \space System \space interfaces$。

此外，实验手册中的 Hints 很重要，大多数实验跟着提示一步一步实现都能完成。

Sleep (easy)

实现 sleep ticks 程序。即在终端输入 sleep 10 可以让内核“睡眠” $10$ 个 ticks。

首先按照Hint-1的提示看一眼user/echo.c是什么，可以看到下面的一段代码：

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

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

    for (i = 1; i < argc; i++) {
        write(1, argv[i], strlen(argv[i]));
        if (i + 1 < argc) {
            write(1, " ", 1);
        } else {
            write(1, "\n", 1);
        }
    }
    exit(0);
}

argc存储终端传入的参数个数，argv存储传入的参数的具体内容。例如运行 echo hello 命令，argc 等于 $2$，argv 分别为 "echo" 和 "hello"。

xv6 内核已经实现了 sys_sleep 系统调用(见kernel/syscall.h 及 kernel/sysproc.c)。直接处理参数然后调用 sys_sleep 即可。

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

int
main(int argc, char *argv[]) {
  int i;
  if (argc < 2) {
    fprintf(2, "Usage: sleep ticsk\n");
    exit(1);
  }
  
  i = atoi(argv[1]);
  sleep(i);

  exit(0);
}

pingpong (eaxy)

练习 fork 和 pipe 以及 write/read 系统调用。和课程上 $pipe2$ 的例子差不多(see pipe2.c)。

注意管道是单向的，所以需要两个管道来实现父子进程的双向通信。

养成好习惯，不用的管道立刻释放，不占用 fd。这在 primes 实验很重要。

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

#define READ 0
#define WRITE 1

int
main(int argc, char *argv[]) {
  // parent to child
  int fd1[2];
  pipe(fd1);

  // child to parent
  int fd2[2];
  pipe(fd2);

  char buf[2];

  int pid = fork();

  // parent
  if (pid != 0) {
    // close useless pipe
    close(fd2[WRITE]); close(fd1[READ]);

    // send a byte to child
    if (write(fd1[WRITE], "#", 1) != 1) {
      fprintf(2, "cannot write a byte to child.\n");
      exit(1);
    }
    close(fd1[WRITE]);

    // read a byte from child
    if (read(fd2[READ], buf, 1) != 1) {
      fprintf(2, "cannot read a byte from child.\n");
      exit(1);
    }
    close(fd2[READ]);

    // print a pong message
    fprintf(1, "%d: received pong\n", getpid());
    wait(0);
  } else {
    // close useless pipe
    close(fd1[WRITE]); close(fd2[READ]);

    // read a byte from parent
    if (read(fd1[READ], buf, 1) != 1) {
      fprintf(2, "cannot read a byte from parent.\n");
      exit(1);
    }
    close(fd1[READ]);

    // print a ping message
    fprintf(1, "%d: received ping\n", getpid());

    // write a byte to parent
    if (write(fd2[WRITE], buf, 1) != 1) {
      fprintf(2, "cannot write a byte to parent.\n");
      exit(1);
    }
    close(fd2[WRITE]);
  }

  exit(0);
}

Primes (hard)

这个实验很多教程实现的都有问题。大多数人实现的都是上一个进程把所有东西都输入管道之后再启动子进程，即并没有实现多个进程之间并行。

要我们实现埃氏筛的管道版本。给没接触过算法竞赛的同学稍微解释一下，埃氏筛通过筛除已知质数的所有倍数，以此来得到质数。即第一轮遍历将所有 $2$ 的倍数都筛出，第二轮遍历将所有 $3$ 的倍数筛出，第三轮遍历将所有 $5$ 的倍数筛出。C ++ 版本代码如下：

std::vector<bool> is_prime(N + 1, true);
std::vector<int> primes;

for (int i = 2;i < N;i ++) {
    if (!is_prime[i]) continue;
    primes.push_back(i);
    for (int j = i + i;j < N;j += i) {
        is_prime[i] = false;
    }
}

这个实验要求我们把遍历改为进程，每一个进程负责筛选一个质因子。

每个进程都需要一遍读取上一个进程发来的数字，同时筛选后发给下一个进程。每个进程收到的第一个质数即该进程用于筛选的质因子。可以写出如下的代码：

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

#define READ 0
#define WRITE 1

void
seive(int left[2]) {
  close(left[WRITE]);
  
  int first;
  // donot hove any more number.
  if (read(left[READ], &first, sizeof(int)) == 0) {
    exit(0);
  }

  fprintf(1, "prime %d\n", first);

  int right[2];
  pipe(right);

  int cur;
  int pid = fork();
  if (pid == 0) {
    seive(right);
  } else {
    close(right[READ]);

    // read, filt and write
    while (read(left[READ], &cur, sizeof(int)) == sizeof(int)) {
      if (cur % first != 0) {
        if (write(right[WRITE], &cur, sizeof(int)) != sizeof(int)) {
          fprintf(2, "pid %d: write error.\n", getpid());
          exit(1);
        }
      }
    }

    close(left[READ]);
    close(right[WRITE]);
    
    wait(0);
  }
}

int
main(int argc, char *argv[]) {
  int p[2];
  pipe(p);
  
  // process 1 push all number to process 2
  // then process i filt all number that can be divide by i
  
  int pid = fork();
  // parent
  if (pid != 0) {
    close(p[READ]);

    // sent all number to child
    for (int i = 2;i <= 35;i ++) {
      if (write(p[WRITE], &i, sizeof(int)) != sizeof(int)) {
        fprintf(2, "cannot write %d to process 2.\n", i);
        exit(1);
      }
    }

    close(p[WRITE]);
    // wait for all child finished.
    wait(0);
  } else {
    seive(p);
  }

  exit(0);
}

find (moderate)

实现 find 程序，在特定目录下查找所有特定名称的文件。

提示中提到了 user/ls.c 目录，先看一下这个文件。一开始是一个 fmtname 函数，用于将文件名格式化为 DIRSIZ 个字符长度。之后反复使用 read 读取字节流到 dirent 结构体，并通过 fstat 函数读取 dirent 的状态到 state 结构体中。

struct dirent 定义在 kernel/fs.h 中：

// Directory is a file containing a sequence of dirent structures.
#define DIRSIZ 14

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

注释中明确说了 “目录是一个包括一系列dirent结构体的文件”。并且 name 字段的大小是 DIRSIZ，这也解释了为什么要用 fmtname 来格式化字符串长度。

struct stat 定义在 kernel/stat.h 中：

#define T_DIR 1      // Directory
#define T_FILE 2     // File
#define T_DEVICE 3   // Device

struct stat {
    int dev;       // File system's disk device
    uint ino;      // Inode number
    short type;    // Type of file
    short nlink;   // Number of links to file
    uint64 size;   // Size of file in bytes
};

结合 user/ls.c 中的相关代码：

if ((fd = open(path, 0)) < 0) {
        fprintf(2, "ls: cannot open %s\n", path);
        return;
    }

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

我们不难猜出，xv6 中一切都是以文件的形式来存储的，目录、文件、设备等所有东西只不过是不同格式的文件。通过 open 系统调用打开一个目录，通过 read 系统调用不断读取目录中的内容，存储在 struct dirent 结构体中。通过 fstat 函数来识别这个文件的信息，存储在 struct state 中。通过 state 中的 type 字段查看是 目录、文件还是设备。

如果是文件，则比较 de.name 是否和给定的参数相同。如果是目录，则递归的 find 子目录。大概照着 ls.c 抄一下。

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

void find(char* path, char* filename) {
    int fd;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }

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

    if (st.type != T_DIR) {
        fprintf(2, "find: %s should be a dir, but found a file.\n", path);
        exit(1);
    }

    char buf[512];
    
    // strlen(path) + 1 表示path的长度 + '\0'
    // DIRSIZ 是文件名最大长度, 见kernel/fs.h 54行
    // 最后还要在末位加上`/`，e.g. code/user -> code/user/
    if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
        fprintf(2, "find: path too long.\n");
        exit(1);
    }

    strcpy(buf, path);
    char *p = buf + strlen(buf);
    *p ++ = '/';
    // 运算优先级: *p ---> p ++. 即p指向'/'的后一个位置

    struct dirent de;
    while (read(fd, &de, sizeof(de)) == sizeof(de)) {
        if (de.inum == 0) continue;
        // 将de.name复制到p后面,最大长度为DIRSIZ
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;
        if (stat(buf, &st) < 0) {
            fprintf(2, "find: cannot stat %s\n", buf);
            continue;
        }
        switch (st.type) {
        case T_FILE:
            if (strcmp(de.name, filename) == 0) fprintf(1, "%s\n", buf);
            break;
        case T_DIR:
            if (strcmp(de.name, ".") == 0) continue;
            if (strcmp(de.name, "..") == 0) continue;
            find(buf, filename);
        }
    }
}

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

    if (argc == 2) {
        find(".", argv[1]);
    } else {
        find(argv[1], argv[2]);
    }

    exit(0);
}

xargs (moderate)

有时候想通过管道传递参数给不同的命令，例如 echo world | echo hello。但是我们知道 echo 并不是从标准输入中获取参数，而是从 cmd 中传递。于是就需要一个程序 xargs，将从标准输入的参数拦截下来，并通过 exec 传递给另一个命令。即 echo world | xargs echo hello

所以我们只需要从 标准IO 中读取将上一个程序的输出，并将其拼接到 cmd 参数的后面，用 fork/exec 那一套运行 cmd 即可。这题主要难在 C 语言的大便字符串上。

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

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

  char *cmd_argv[MAXARG];
  char buf[512];
  int i;

  for (i = 1; i < argc; i++) {
    cmd_argv[i - 1] = argv[i];
  }

  while (1) {
    int p = 0;
    int n;
    
    while (1) {
      n = read(0, &buf[p], 1);
      if (n <= 0 || buf[p] == '\n') break;
      p++;
    }

    if (n <= 0 && p == 0) break;

    buf[p] = '\0';

    cmd_argv[argc - 1] = buf;
    cmd_argv[argc] = 0;

    if (fork() == 0) {
      exec(cmd_argv[0], cmd_argv);
      fprintf(2, "xargs: exec %s failed\n", cmd_argv[0]);
      exit(1);
    } else {
      wait(0);
    }
  }

  exit(0);
}

sixfive (moderate) 2025

这是 2025 版的新实验。从用户参数中读取指定文件，并输出文件中所有能被 $5$ 和 $6$ 整除的数字。一个合法数字应该由 "-\r\t\n./," 这 $7$ 个字符分割。即 xv6 中的 $6$ 不是一个合法数字，但 /6 中的 $6$ 为合法数字。

没啥好说的，直接 read/write 完事。

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

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

  for (int i = 1;i < argc;i ++) {
    int fd;
    if ((fd = open(argv[i], 0)) < 0) {
      fprintf(2, "sixfive error: cannot open file %s.\n", argv[i]);
      close(fd);
      exit(1);
    }

    char c;
    int cur = 0, flag = 0;

    while (read(fd, &c, sizeof(char)) == sizeof(char)) {
      if (c >= '0' && c <= '9') {
        cur = cur * 10 + c - '0';
        flag = 1;
      } else {
        if (c == '-' || c == '\r' || c == '\t' || c == '\n' 
            || c == '.' || c == '/' || c == ',') {
          if ((cur % 5 == 0 || cur % 6 == 0) && flag == 1)
            fprintf(1, "%d\n", cur);
        }
        cur = 0; flag = 0;
      }
    }
    close(fd);
  }
  exit(0);
}

memdump (easy) 2025

要实现有点类似 printf 的一个东西，通过解析 fmt 字符串，按照特定的格式解析 data，并输出。注意指针之间的转换即可。

void
memdump(char *fmt, char *data)
{
  int len = strlen(fmt);
  for (int i = 0;i < len;i ++) {
    if (fmt[i] == 'i') {
      printf("%d\n", *(int *)data);
      data += 4;
    } else if (fmt[i] == 'p') {
      printf("%llx\n", *(long long *) data);
      data += 8;
    } else if (fmt[i] == 'h') {
      // see kernel/printf.c.
      // xv6's standard library does not support the %hd flag
      // which used to printf short integer.
      short cur = *(short *) data;
      data += 2;
      printf("%d\n", cur);
    } else if (fmt[i] == 'c') {
      printf("%c\n", *data);
      data ++;
    } else if (fmt[i] == 's') {
      char *p = (char *)*(unsigned long long *)data;
      printf("%s\n", p);
      data += 8;
    } else if (fmt[i] == 'S') {
      int offset =  strlen(data);
      printf("%s\n", data);
      data += offset;
    }
  } 
}

exec (moderate)

给之前实现的 find 程序新增一个 -exec 标志，将找到的每一个文件名分别作为参数传递为 exec 。也没什么好说的，细心处理 fork/exec 即可。

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

char *exec_argv[MAXARG];
int has_exec = 0;
int exec_argc = 0;

void find(char* path, char* filename) {
    int fd;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }

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

    if (st.type != T_DIR) {
        fprintf(2, "find: %s should be a dir, but found a file.\n", path);
        close(fd);
        return;
    }

    char buf[512];
    if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
        fprintf(2, "find: path too long.\n");
        close(fd);
        return;
    }

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

    struct dirent de;
    while (read(fd, &de, sizeof(de)) == sizeof(de)) {
        if (de.inum == 0) continue;
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;

        if (stat(buf, &st) < 0) {
            continue;
        }

        if (st.type == T_FILE) {
            if (strcmp(de.name, filename) == 0) {
                if (has_exec) {
                    int pid = fork();
                    if (pid == 0) {
                        exec_argv[exec_argc] = buf;
                        exec_argv[exec_argc + 1] = 0;
                        exec(exec_argv[0], exec_argv);
                        fprintf(2, "find: exec %s failed\n", exec_argv[0]);
                        exit(1);
                    } else if (pid > 0) {
                        wait(0);
                    }
                } else {
                    fprintf(1, "%s\n", buf);
                }
            }
        } else if (st.type == T_DIR) {
            if (strcmp(de.name, ".") != 0 && strcmp(de.name, "..") != 0) {
                find(buf, filename);
            }
        }
    }
    close(fd);
}

int main(int argc, char* argv[]) {
    if (argc < 3) {
        fprintf(2, "Usage: find [path] [filename] [-exec cmd args...]\n");
        exit(1);
    }

    char *path = argv[1];
    char *filename = argv[2];

    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-exec") == 0) {
            has_exec = 1;
            int k = 0;
            for (int j = i + 1; j < argc; j++) {
                if (k < MAXARG - 2) {
                    exec_argv[k++] = argv[j];
                }
            }
            exec_argc = k;
            break;
        }
    }

    find(path, filename);
    exit(0);
}

Lab2 syscall: System Calls | 系统调用

这一章开始就正式进入内核开发。第二章主要是实现新的系统调用。

根据课程官网的要求，需要阅读完教材的第二章$Operating \space system \space organization$。并且读懂下列源代码：kernel/proc.h, kernel/defs.h, kernel/entry.S, kernel/main.c, user/initcode.S, user/init.c, 简略了解kernel/proc.c, kernel/exec.c。

写这个 Lab 之前先总结一下 xv6 系统调用的过程。

用户进程中的系统调用实现在 user/usys.S 中。将系统调用号存放在 a7 寄存器中，执行 ecall 指令进入内核态。通过一系列 trap 指令将寄存器放入 trapfram->a7 中。

以 fork 为例，user/usys.S:

.global fork
fork:
 li a7, SYS_fork
 ecall
 ret

之后调用 syscall() 函数(见 kernel/syscall.c)，从 trapfram->a7 中取出系统调用号，并通过一个函数指针数组调用对应的系统调用实现。

kernel/syscall.c:

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

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]();
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

和进程有关系统调用的实现在 kernel/sysproc.c，和文件有关的在 kernel/sysfile.c。系统调用号存储在 kernel/syscall.h。

System call tracing (moderate)

实现一个系统调用 trace mask，用于追踪特定的系统调用。

从上面的 syscall() 函数中可以看到，在 p->trapframe->a0 = syscalls[num]() 之前判断 num 是否在掩码中，如果有打印信息就可以了。

首先新建一个系统调用的存根：

• 在 kernel/syscall.h 中加入 #define SYS_trace 22
• 在 kernel/syscall.c 中加入 sys_trace 的声明 extern uint64 sys_trace(void);; 在 syscalls 数组中加入 [SYS_trace] sys_trace 。
• 在 user/user.h 中加入函数用户态接口声明 int trace(int);
• 在 user/usys.pl 中加入入口声明 entry("trace");

总结起来就是出现系统调用的地方都抄一个 trace 上去。

根据提示，新增一个 int trace_mask 成员变量到 struct proc 中，这样就可以记录哪些系统调用是要追踪的了。同时将 kernel/proc.c 中的 fork 中，将父进程的 trace_mask 复制给子进程。

在 kernel/sysproc.c 中新增 sys_trace 的实现，将用户参数复制到 struct proc 中新增的 trace_mask 中。

uint64
sys_trace(void) {
  int mask;
  if (argint(0, &mask) < 0)
    return -1;
  myproc()->trace_mask = mask;
  return 0;
}

由于需要打印系统调用的名字，我们照 syscalls 数组抄一个从 系统调用号 映射到 系统调用名字 的数组。

static char *syscall_name[] = {
  "#", // ensure the index stars from 1
  "fork", "exit", "wait", "pipe",
  "read", "kill", "exec", "fstat",
  "chdir", "dup", "getpid", "sbrk",
  "sleep", "uptime", "open", "write",
  "mknod", "unlink", "link", "mkdir",
  "close", "trace", "sysinfo"
};

然后在 syscall 函数修改为如果有掩码就输出信息即可。

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

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    p->trapframe->a0 = syscalls[num]();
    if ((p->trace_mask >> num) & 1) {
      printf("%d: syscall %s -> %d\n", p->pid, syscall_name[num], p->trapframe->a0);
    }
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

Sysinfo (moderate)

先按照上一个任务的方法加入一个 sysinfo 系统调用. 这里在 kernel 文件夹下再写一个 sysinfo.c 来实现这个系统调用. 在 Makefile 的 OBJS 加入 $K/sysinfo.o \(因为我在sysinfo.c中实现，所以要链接这个文件。如果直接在kernel/proc.c中实现就不用).

看filestat()函数能得知copyout函数的功能，加上sys_fstat()中虚拟地址是从a0读出来的。所以很容易能写出下面代码。

sysinfo.c：

#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "date.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "proc.h"
#include "sysinfo.h"

extern uint64 freemem();
extern uint64 num_proc();


uint64
sys_sysinfo(void) {
  struct sysinfo info;
  struct proc *p;
  uint64 va;

  info.freemem = freemem();
  info.nproc = num_proc();

  p = myproc();
  if (argaddr(0, &va) < 0)
    return -1;
  if(copyout(p->pagetable, va, (char *)&info, sizeof(info)) < 0)
    return -1;

  return 0;
}

然后是freemem()和num_proc()。

在kernel/kalloc.c中添加，看一下前面的kalloc()函数，在看一下struct kmem。

struct run {
    struct run* next;
};

struct {
    struct spinlock lock;
    struct run* freelist;
} kmem;

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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
    return (void*)r;
}

其中freelist是一个链表，存储所有空闲内存页面的地址。所以我们只需要遍历这个链表，每一项都加上PGSIZE即可。

freemem：

uint64 freemem() {
    struct run* r;
    uint64 tot = 0;

    acquire(&kmem.lock);
    for (r=kmem.freelist; r; r = r->next) 
        tot += PGSIZE;
    release(&kmem.lock);

    return tot;
}

然后看一看 kernel/proc.c 中的 procdump 函数可以知道，proc 数组中存放的是所有进程控制块的地址，所以遍历 proc 即可。

在kernel/proc.c中添加：

uint32 num_proc() {
    uint32 tot = 0;
    struct proc* p;
    for (p = proc;p < &proc[NPROC];p ++) {
        if (p->state != UNUSED) tot ++;
    }
    return tot;
}

Attack xv6 (moderate) 2024

这个实验中，kernel/vm.c 以及 kernel/kalloc.c 中的 memset 都被注释了，即释放、申请内存时，新内存会存储之前内存的值。这允许我们通过一些手段得到其他进程的信息。

先从 user/attacktext 中进行分析。首先父进程调用第一个 fork 来创建子进程 $1$，通过 secrect 函数向某块内存写入一句话。之后立刻调用第二个fork 创建子进程 $2$，通过 attack 函数尝试得到这段话。

再分别看看 secrect.c 和 attact.c。attack.c 即我们要实现的东西。secrect.c 首先通过 sbrk 系统调用申请了 $32$ 页新内存，并在第 $9$ 块页面的起点写了一条提示语句: "my very very very secret pw is: "，最后紧跟着写入一条密码。

user/secrect.c:

int
main(int argc, char *argv[])
{
  if(argc != 2){
    printf("Usage: secret the-secret\n");
    exit(1);
  }
  char *end = sbrk(PGSIZE*32);
  end = end + 9 * PGSIZE;
  strcpy(end, "my very very very secret pw is:   ");
  strcpy(end+32, argv[1]);
  exit(0);
}

由于 secrect 和 attack 中间并没有其他进程产生，也没有任何内存申请，所以子进程 $2$ 中很大概率能分配到 attack 中释放的内存。

所以我们可以在 attack 中申请大量的内存页，然后遍历这些内存页，看看哪个页的开头有那句提示词，然后偏移 $32$ 个字节即为密码。

需要注意的是，每一页的前 $8$ 个字节在 freelist 中是用来存储 struct next *r 的，所以我们要从第 $9$ 开始匹配。如果全部匹配的话，似乎会匹配到 .rodata 段，然后偏移 $32$ 的位置是脏数据。

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

int
main(int argc, char *argv[])
{
  char *mem = sbrk(32 * PGSIZE);

  for (int i = 0; i < 32; i++) {
    char *page = mem + i * PGSIZE;

    fprintf(1, "debug: %p\n", *(void **)page);
    if (page[8] == 'v' && page[9] == 'e' && page[10] == 'r' && page[11] == 'y') {
      
      fprintf(1, "debug: %s\n", page+8);
      write(2, page + 32, 8);
      break;
    }
  }

  exit(1);
}

当然，也有一些大佬硬分析出来了这一页会被分配在第 $16$ 页的位置。可以参考 这篇博客。

Sandbox a command (moderate) 2025

新增一个 sandbox 系统调用，禁止掩码对应的系统调用执行。

大概就是 trace 实验的改版，把输出修改为 continue 即可。注意这个实验有两个参数 mask 和filename，但是我们暂时只用得到第一个参数。

kernel/sysproc.c

uint64
sys_interpose(void) {
  int mask;
  char path[MAXPATH];
  struct proc *p;
  argint(0, &mask);
  if (argstr(1, path, sizeof(path)) < 0)
    return -1;

  p = myproc();
  p->interpose_mask = mask;
  safestrcpy(p->interpose_path, path, sizeof(p->interpose_path));
  return 0;
}

kernel/syscall.c

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

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    // Lab 2 - Sandbox a command
    // Check the mask to ensure the process can run the system call
    if ((p->interpose_mask >> num) & 1) {
      p->trapframe->a0 = -1;
      return ;
    }
    // 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]();
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

Sandbox with allowed pathnames (easy) 2025

用上文提到的 filename 参数，如果 open 和 exec 的 pathname 匹配，则运行该系统调用执行。

没啥好说的，用 argstr 从用户空间拷贝出来，比较一下即可。

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

  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    // Check the mask to ensure the process can run the system call
    if ((p->interpose_mask >> num) & 1) {
      // if open or exec are masked, check if the
      // pathname matches the allowed pathname.
      if (num == SYS_open || num == SYS_exec) {
        char path[MAXPATH];
        if (argstr(0, path, MAXPATH) >= 0) {
          if (strncmp(path, p->interpose_path, MAXPATH) == 0) {
            p->trapframe->a0 = syscalls[num]();
            return ;
          }
        }
      }
      // do not be allowed
      p->trapframe->a0 = -1;
      return ;
    }
    // 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]();
  } else {
    printf("%d %s: unknown sys call %d\n",
            p->pid, p->name, num);
    p->trapframe->a0 = -1;
  }
}

Lab3 pgtbl: Page tables | 页表

主要内容为熟悉页表遍历，地址转换。2024 年的实验还涉及到进程内存的管理。

Speed up system calls (easy)

需要给 user proc 分配一块单独的页面，使得能和 kernel 共享一些数据，这样来加快某些系统调用。例如 ugetpid()，不用来回跳转内核态，kernel 直接将 pid 存储到该页面，只需在用户态读取相关数据即可。

跟着提示先看看proc_pagetable()，可以看到就是用mappages()来将虚拟地址映射到物理地址。权限只需要设置PTE_R保证能读取，PTE_U保证用户内存能访问即可。

然后看一眼allocproc(), 就是调用kalloc()来给struct proc里面的各个部分分配空间。

最后在看看freeproc(), 对应把allocproc分配的东西，该free的free，该置0的置0。

所以我们要做的就很明显了：

• 创建进程时，多存储一个struct usyscall。
• 创建进程页面时，将struct usyscall映射到USYSCALL。
• 销毁进程时，将struct usyscall释放，并且清空页表。

在struct proc添加struct usyscall成员变量。

struct proc {
    // 省略其他
    struct usyscall* usyscall_info;
}

然后在allocproc中分配内存，并且初始化。NOTE：usyscall的分配要在p->pagetable分配前实现。不然下一步页表会映射为空。

static struct proc* allocproc(void) {
    // 省略其他
    if ((p->usyscall_info = (struct usyscall*)kalloc()) == 0) {
        freeproc(p);
        release(&p->lock);
        return 0;
    }
    p->usyspage->pid = p->pid;
}

然后在proc_pagetable()中添加映射。NOTE：uvmumap要把上两次map的页面也删除。

proc_pagetable() {
    // 省略其他
    if (mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall), PTE_R | PTR_U) < ) {
        uvmunmap(pagetable, TRAMPOLINE, 1, 0);
        uvmunmap(pagetable, TRAPFRAME, 1, 0);
        uvmfree(pagetable, 0);
        return 0;
    }
}

对应的要把 freeproc 和 proc_freepagetable 里面把申请的内存/页表也清空。

static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  if(p->usyscall)
    kfree((void*)p->usyscall);
  p->usyscall = 0; // free memory
  p->pagetable = 0;
  p->sz = 0;
  p->pid = 0;
  p->parent = 0;
  p->name[0] = 0;
  p->chan = 0;
  p->killed = 0;
  p->xstate = 0;
  p->state = UNUSED;
}

pagetable_t
proc_pagetable(struct proc *p)
{
  // ...

  // Lab 3 - Speed up system calls
  // map the usyscall page to speed up getpid()
  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;
  }

  return pagetable;
}

Print a page table (easy)

我们需要定义一个vmprint函数。该函数应该有一个参数pagetable_t，作为要可视化的页表，然后按下面的格式打印这个页表的信息。添加一行if (p->pid == 1) vmprimt(p->pagetable)在exec.c中，在返回argc之前输出第一个进程的页面信息。

提示里面说了freewalk函数很重要，所以外面先读一下这个函数。

// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(pagetable_t pagetable) {
    // there are 2^9 = 512 PTEs in a page table.
    for (int i = 0; i < 512; i++) {
        pte_t pte = pagetable[i];
        if ((pte & PTE_V) && (pte & (PTE_R | PTE_W | PTE_X)) == 0) {
            // this PTE points to a lower-level page table.
            uint64 child = PTE2PA(pte);
            freewalk((pagetable_t)child);
            pagetable[i] = 0;
        } else if (pte & PTE_V) {
            panic("freewalk: leaf");
        }
    }
    kfree((void *)pagetable);
}

首先传入了一个页表，并且遍历里面的所有项。如果 pte 不为空并且 PTE_V 标志位为 $1$，说明这项页面存在，并且映射了一个虚拟内存到物理内存。如果 PTE_R、PTE_R、PRE_X 都为0，说明这个页面为高级页表，读取下一级页表的地址，递归调用 freewalk 来遍历。

emmmm，然后就没什么好说的了，照着上面加点输出就可以。

vmprint:

// lab3 - exercise 2
// print a page table
void
vmprint(pagetable_t pagetable, int depth) {
    if (depth == 1)
        printf("page table %p\n", pagetable);
    for (int i = 0;i < 512;i ++) {
        pte_t pte = pagetable[i];
        // printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
        if (pte & PTE_V) {
             for (int j = 1;j <= depth;j ++)
                printf("..%s", j == depth ? "" : " ");
            printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
            if ((pte & (PTE_R | PTE_W | PTE_X)) == 0) {
                pagetable_t child = (pagetable_t)PTE2PA(pte);
                vmprint((pagetable_t)child, depth + 1);
            }
        }
    }
}

然后在kernel/defs.h中添加原型：

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

在exec.c的return前插入代码：

if(p->pid==1) 
    vmprint(p->pagetable);
return argc; // this ends up in a0, the first argument to main(argc, argv)

Detecting which pages have been accessed (hard)

大概意思可能和 cache 中的脏位差不多。检测到上一次调用 sys_pgaccess() 这段时间内，哪些页表项被访问过。

需要注意的是，PTE_A位是由RISC-V硬件来维护的，在xv6中则是由 qemu 模拟器来负责维护，内核不用考虑什么时候将 PTE_A 置为1。

还是教材上这张图, RISC-V硬件页表的标记位：

可以看到 $access$ 标志位是第 $6$ 位(从 $0$ 数起，从左到右)。所以在 kernel/riscv.h 下面，添加一位PTE_A的定义。

#define PTE_V (1L << 0)   // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4)   // 1 -> user can access
#define PTE_A (1L << 6)   // Lab pgtbl: Whether it has been visited

按照 $lab2$ 的内容看看系统调用需要添加的东西，真良心全添加好了。所以我们只用考虑怎么来实现 sys_pgaccess。 在kernel/sysproc.c中

#ifdef LAB_PGTBL
int sys_pgaccess(void) {
    // lab pgtbl: your code here.
    return 0;
}
#endif

我们用一个 $64$ 位的整数来当作 bitmask，一位表示一张页表，所以只能访问 $64$ 张页表。即参数里的 pgnums 不能超过 $64$。然后就是从用户进程页表中的 va 开始，往下访问 pgnums 张页表项，如果 $i$ 个 PTE 的 access 位为 $1$，则 bitmask 中第 $i$ 位也置为1。由于sys_pgaccess()也会访问页表，这个操作也会将 PTE_A 置为 $1$，所以在标记完bitmask之后，需要将 PTE_A 重置。

int
sys_pgaccess(void)
{
  // lab pgtbl: your code here.
  // virtual address
  uint64 va;
  if (argaddr(0, &va) < 0) {
    return -1;
  }

  // the number of page table to check.
  int pgnums;
  if (argint(1, &pgnums) < 0) {
    return -1;
  }

  // user virtual address
  uint64 ua;
  if (argaddr(2, &ua) < 0) {
    return -1;
  }

  uint64 bitmask = 0;
  struct proc* p = myproc();

  for (int i = 0; i < pgnums; i++) {
    if (va >= MAXVA) return -1;
    pte_t *pte = walk(p->pagetable, va, 0);
    if (pte != 0 && (*pte & PTE_V)) {
      if (*pte & PTE_A) {
        bitmask |= (1 << i);
        *pte &= ~PTE_A;
      }
    }
    va += PGSIZE;
  }

  if (copyout(p->pagetable, ua, (char*)&bitmask, sizeof(bitmask)) < 0) {
    return -1;
  }

  return 0;
}

然后报错说walk()没被定义，看一眼kernel/defs.h，发现没有walk函数原型，所以添加一个即可。

int copyinstr(pagetable_t, char*, uint64, uint64);
pte_t* walk(pagetable_t, uint64, int);

Use superpages (Hard) 2024

这是我觉得十分 hard 的一个实验。当用户进程调用 sbrk(n) 申请内存时，如果 $n$ 大于 2MB，则分配一整块 2MB 的页，而不是 $512$ 块 4KB 的页。

要完成这个实验，需要从 物理内存分配器(kernel/kalloc.c)、虚拟内存映射(kernel/vm.c: mappages()) 以及 虚拟内存分配(kernel/vm.c:uvmalloc, uvmcopy, uvmfree等) $3$ 个方面都作修改。

采用静态分配的方法，从 PHYSTOP 往下开始分配，防止和 kinit() 冲突。同时在 kernel/riscv.h 和 kernel/memlayout.h 中维护 Superpage 的块数和起始地址。我这里分配了 $8$ 块 Superpages，即 PHYSTOP - 8*2*1024*1024 到 PHYSTOP 这 16MB 为 Superpage。

xv6 默认的 kalloc() 只能分配 4KB 的页。超级页要求连续的 2MB 物理空间。照着 struct freelist、kinit() 这些都抄一份对应的 superxxx() 。

kernel/kalloc.c

void superfreerange(void *pa_start, void *pa_end);
// Lab 3 - Use Superpages
// super page
struct superpage {
  struct superpage *next;
};


struct {
  struct spinlock lock;
  struct superpage *freelist;
} supermem;

void
superinit()
{
  initlock(&supermem.lock, "supermem");
  superfreerange((void *)SUPERPGSTART, (void*)PHYSTOP);
}

void
superfreerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)SUPERPGROUNDUP((uint64)pa_start);
  for (; p + SUPERPGSIZE <= (char*)pa_end;p += SUPERPGSIZE)
    superfree(p);
}

void
superfree(void *pa)
{
  struct superpage *r;

  if (((uint64)pa % SUPERPGSIZE) != 0 || (uint64)pa < SUPERPGSTART || (uint64)pa >= PHYSTOP)
    panic("superfree");

  memset(pa, 1, SUPERPGSIZE);

  r = (struct superpage*)pa;

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

void *
superalloc(void)
{
  struct superpage *r;
  acquire(&supermem.lock);
  r = supermem.freelist;
  if (r) 
    supermem.freelist = r->next;
  release(&supermem.lock);

  if (r)
    memset((char*)r, 5, SUPERPGSIZE); // fill with junk
  return (void*)r;
} 

然后修改 kinit() 里面，使得 4KB 的页面不和超级页重叠。

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)SUPERPGSTART);
}

同理修改 kfree 里面的判断逻辑。

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

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

最后别忘了在 kernel/main.c 中 kinit() 的前面调用 superinit() 来初始化 Superpage 。

然后查看一下 sys_sbrk 逻辑，发现 sys_sbrk 是调用 uvmalloc 来分配物理内存，调用 mappages 来建立映射， 调用 uvmunmap 来释放页面。同时，fork 时候会调用 uvmcopy 来复制父进程页表。这 $3$ 个函数我们都需要修改。

首先仿照 walk 函数编写一个 superwalk，使得 walk 能停留在 L1 级页表。只需要修改一下循环条件即可。

pte_t *
superwalk(pagetable_t pagetable, uint64 va, int alloc, int le)
{
  if (va >= MAXVA)
    panic("walk");

  for(int level = 2; level > le; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
#ifdef LAB_PGTBL
      if(PTE_LEAF(*pte)) {
        return pte;
      }
#endif
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(le, va)];
}

对着 mappages 写一个 mapsuperpages，一次性分配 2MB 页表。由于不太可能一次性申请太多 Superpage，我偷个懒没有写 size 参数。

int
mapsuperpages(pagetable_t pagetable, uint64 va, uint64 pa, int perm)
{
  pte_t *pte;

  if ((va % SUPERPGSIZE)!= 0)
    panic("mapsuperpages: va not aligned");

  if ((pte = superwalk(pagetable, va, 1, 1)) == 0)
    return -1;

  if (*pte & PTE_V)
    panic("mapsuperpgaes: remap");

  *pte = PA2PTE(pa) | perm | PTE_V;
  return 0;
}

然后是 uvmalloc、uvmunmap、uvmcopy 这 $3$ 哥们。大概也是照着原本的逻辑写，只是修改为对应的 super 函数。需要注意的就是 Superpage 分配失败不要直接 panic，而是继续执行分配普通页的逻辑(实在不知道怎么写了，用了违背祖宗的 goto QAQ)。

uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz;a < newsz; ) {
    if (newsz - a >= SUPERPGSIZE && (a % SUPERPGSIZE) == 0) {
      mem = superalloc();
      if (mem != 0) {
        memset(mem, 0, SUPERPGSIZE);
        if (mapsuperpages(pagetable, a, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
          superfree(mem);
          goto err;
        }
        a += SUPERPGSIZE;
        continue;
      }
      // 如果分配失败，不报错，而是向下尝试分配 4kb 页面
    }

    // 4kb 分配逻辑
    mem = kalloc();
    if (mem == 0) {
      goto err;
    }
    memset(mem, 0, PGSIZE);
    if (mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
      kfree(mem);
      goto err;
    }
    a += PGSIZE;
  }
  return newsz;

err:
  uvmdealloc(pagetable, a, oldsz);
  return 0;
}

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;) {
    pte = superwalk(old, i, 0, 1);
    // 检查是否为 superpage
    if (pte && (*pte & PTE_V) && (*pte & (PTE_R|PTE_W|PTE_X))) {
      pa = PTE2PA(*pte);
      flags = PTE_FLAGS(*pte);
      if ((mem = superalloc()) == 0)
        goto err;
      memmove((void *)mem, (void*)pa, SUPERPGSIZE);
      if (mapsuperpages(new, i, (uint64)mem, flags) != 0) {
        superfree((void*)mem);
        goto err;
      }
      i += SUPERPGSIZE;
      continue;
    }

    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;
    }
    i += PGSIZE;
  }
  return 0;

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

void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  for (a = va;a < va + npages*PGSIZE;) {
    pte = superwalk(pagetable, a, 0, 1);

    // 如果为超级页
    if (pte && (*pte & PTE_V) && (*pte & (PTE_R|PTE_W|PTE_X))) {
      if (do_free) {
        uint64 pa = PTE2PA(*pte);
        superfree((void*)pa);
      }
      *pte = 0;
      a += SUPERPGSIZE;
      continue;
    }

    // 正常的 4kb
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0) {
      printf("va=%ld pte=%ld\n", a, *pte);
      panic("uvmunmap: not mapped");
    }
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
    a += PGSIZE;
  }
}

Lab4 traps: Traps | 陷入

这部分实验更加深入的探究利用 trap 机制实现的 System Calls，并通过一个用户级的中断来模拟 xv6 上真实中断的过程。

RISC-V assembly (easy)

在本部分中将给出一段 RISC-V 汇编代码，通过阅读代码我们要回答几个问题，并把答案存储在主目录下的 answers-traps.txt 下。

运行 make fs.img后会编译user/call.c, 并生成user/call.asm。我们需要观察call.asm下的g、f、main函数。

RISC-V 参考文档：RISC-V unprivileged instructions
RISC-V privileged instructions

哪些寄存器包含函数的参数？例如，在 main 调用 printf 时，哪个寄存器保存 $13$？

查阅Calling conventions手册，可以发现 $a_0 \rightarrow a_7$为函数参数和返回值寄存器。

13属于第三个参数(第一个为format string，第二个为f(8) + 1)。所以存储在$a_2$寄存器中。

在 main 的汇编代码中，函数 f 的调用在哪里？对 g 的调用在哪里？ 提示：编译器可能会内联函数）。

我们先分析一下g()的汇编代码。

int g(int x) {
   0:	1141                	addi	sp,sp,-16
   2:	e406                	sd	ra,8(sp)
   4:	e022                	sd	s0,0(sp)
   6:	0800                	addi	s0,sp,16
    return x + 3;
}
   8:	250d                	addiw	a0,a0,3
   a:	60a2                	ld	ra,8(sp)
   c:	6402                	ld	s0,0(sp)
   e:	0141                	addi	sp,sp,16
  10:	8082                	ret

首先将栈顶指针sp往下移动16字节，等价与要入栈两个元素。将ra，即caller进程的pc值，存入栈的第一个位置。将s0，即caller进程的其他寄存器保存地址，存放到第二个位置。

然后将a0的值加3，存储到a0寄存器中。然后从栈中恢复ra和s0的地址，此时CPU能返回原进程继续执行。然后ret指令将a0复制给原进程，即返回值。

f()函数和g()大同小异，只是编译器将return g(x)直接展开为x + 3了。

main函数中可以看到，直接将12写入a1，直接将13写入a2。所以推测直接将f(8) + 1计算在编译器计算出来，当常数写入了。

printf 函数位于哪个地址？

可以看到jalr跳转到了ra + 1544的地址，也就是0x640的地方。所以printf应该在这个位置。

在 jalr 跳转至 main 函数的 printf 时，寄存器 ra 中有什么值？

当程序进行跳转时，我们需要将 ra 寄存器存储的返回地址指向 printf 执行结束后返回到主程序的位置，也就是当前位置 PC 加 4，也就是 0x38

Backtrace (moderate)

要实现一个类似 gdb 的调用追踪，打印出每一次函数调用的函数首地址。

GCC 编译器会将当前执行函数的帧指针存储在寄存器 s0 中。将以下函数添加到 kernel/riscv.h, 并在回溯中调用该函数来读取当前帧指针。该函数使用内联汇编读取 s0。

static inline uint64
r_fp()
{
  uint64 x;
  asm volatile("mv %0, s0" : "=r" (x) );
  return x;
}

首先读出s0寄存器的值，即当前函数的栈指针。然后用类似链表遍历的方式，每次输出return address的值，然后移动到prev frame继续遍历即可。

xv6 为内核中的每个堆栈分配一个 page 大小的页面。可以使用 PGROUNDDOWN(fp) 和 PGROUNDUP(fp) 计算堆栈页面的顶部和底部地址（参见 kernel/riscv.h）。我们遍历的时候，如果发现地址超过这个页面，即说明该进程的函数调用结束了。

void backtrace(void) {
    printf("backtrace:\n");
    uint64 fp = r_fp();
    while (fp != PGROUNDUP(fp)) {   // until get to stack bottom
        // get return addr in current stack frame
        uint64 ra = *(uint64*)(fp - 8);
        printf("%p\n", ra);
        // go to prev stack frame
        fp = *(uint64*)(fp - 16);
    }
}

然后在sys_sleep()和panic()中调用backtrace。

Alarm (hard)

要实现一个 sigalarm(interal, handler) 的系统调用，在之后的每隔 interval 个 CPU 周期(即 sleep 实验中的 ticks)，就强制执行 handler 函数。调用 sigalarm(0, 0) 表示终止 Alarm。此外还要实现一个 sigreturn() 系统调用，如果 handler 调用了这个系统调用，就应该停止执行 handler 的内容，恢复原进程的正常执行。

这个实验还是挺难的，需要彻底理解 trap 的过程。这里不再重复了，可以多看看 Lecture 6 和 Lecutre 7。我们先看一看测试 user/alarmtest.c 中的 test0()。

void
periodic()
{
  count = count + 1;
  printf("alarm!\n");
  sigreturn();
}

// tests whether the kernel calls
// the alarm handler even a single time.
void
test0()
{
  int i;
  printf("test0 start\n");
  count = 0;
  sigalarm(2, periodic);
  for(i = 0; i < 1000*500000; i++){
    if((i % 1000000) == 0)
      write(2, ".", 1);
    if(count > 0)
      break;
  }
  sigalarm(0, 0);
  if(count > 0){
    printf("test0 passed\n");
  } else {
    printf("\ntest0 failed: the kernel never called the alarm handler\n");
  }
}

这个测试的意思就是：原本在 test0 中正常进行循环，但是之前调用了 sigalarm(2, periodic)，所以每两个 ticks 就进入到 periodic 中打印 “alarm!”，并通过 sigreturn 返回 test0，继续执行循环。

$test0$ 的提示特别细致，大概意思就是说：不能在内核中执行 handler，必须要返回用户态执行。那么我们知道，trap 中是通过 epc 这个寄存器来确定返回的地址的，所以要跳转到 epc，我们只需要修改 p->trapframe->epc 为 handler 的地址即可。

那么怎么判断过了多少个 ticks 呢。这里有一个前置知识：RISC-V 硬件(或主板，我不清楚具体是什么硬件) 会在每一个时钟周期产生一个时钟中断，且在 trap.c 中会处理这个中断。时钟中断可以通过 which_dev == 2 来识别，且这个逻辑在 kernel/trap.c 中的 usertrap 中会处理。

根据提示里，我们有两种方法来维护举例上一次调用 handler 过了多少个 ticks：1. 在 struct proc 中维护该进程自上次调用来过了多少 ticks。2. 在 struct proc 中维护举例下一次调用还有多少 ticks。两种方法都利用时钟产生的中断来进行更新。这里采用了第 $2$ 中方法。

此外，由于 sigreturn 需要恢复现场，但是 handler 可能会修改到进程 context，并且 sigalarm 需要修改 epc 寄存器，我们还需要复制一份 trapframe。

在 test1 中提到，需要防止 alarm 嵌套执行，即运行 handler 的过程中又调用 sigalarm 产生了第二次 handler。我们需要模仿 interrupt 中的开关中断标志，维护一个 alarm_off。

加上需要传递给内核的 interval 和 handler 地址这两个参数，我们需要在 struct proc 中新增 $5$ 个部分：

• alarm_interval 表明中断的间隔数。

• void(*alarm_handler)() 一个函数指针，指向 handler 的地址。

• alarm_ticks 距离下一次中断还有多少时钟周期。

• struct trapframe alarm_trapframe 备份经常的上下文。

• alarm_goingoff 指明关中断还是开中断。

struct proc {
  struct spinlock lock;

  // ...

  int alarm_interval;         // Alarm interval (0 for disabled)
  void(*alarm_handler)();
  int alarm_ticks;             // how many ticks left before next alarm goes off
  struct trapframe *alarm_trapframe; // A copy of trapfram
  int alarm_goingoff;
};

注意不要忘记在 kernel/proc.c 中的 allocproc 中给 alarm_trapframe 分配内存，同时在 freeproc 中释放内存。同时还要在 initproc 中初始化其他变量。

添加系统调用的东西就不重复了，按照第 2 章的要求自行添加即可。直接来看 sys_sigalarm，类似 trace 一样，将参数读出并更新至 struct proc 即可。

kernel/sysproc.c

uint64
sys_sigalarm()
{
  int ticks;
  uint64 handler;

  if (argint(0, &ticks) < 0)
    return -1;
  if (argaddr(1, &handler) < 0)
    return -1;

  struct proc *p = myproc();
  p->alarm_interval = ticks;
  p->alarm_handler = (void(*)())handler;
  p->alarm_ticks = ticks;

  return 0;
}

然后是 usertrap。首先判断 p->alarm_interval 是否为0，如果为 $0$ 则说明 sigalarm 并未开启。然后 p->alarm_ticks 减一，表示又过了一个时钟周期。如果 alarm_ticks 为 $0$ 且 alarm_goingoff 为 $0$，则说明当前时钟周期要跳转到 handler，执行以下操作：将 alarm_ticks 重新置为 alarm_interval，备份 trapframe，修改 epc 为 alarm_handler，并将 alarm_goingoff 置为 $1$，表示关中断。

void
usertrap(void)
{
  if(p->killed)
    exit(-1);

 // ...

  if (which_dev == 2) {
    if (p->alarm_interval != 0) {
      if (--p->alarm_ticks <= 0) {
        if (!p->alarm_goingoff) {
          p->alarm_ticks = p->alarm_interval; // reset the conuter
          *p->alarm_trapframe = *p->trapframe; // backup registers
          p->trapframe->epc = (uint64)p->alarm_handler; // jump to handler
          p->alarm_goingoff = 1;
        }
      }
    }
    yield();
  }

  usertrapret();
}

最后是 sys_sigreturn。由于 sigreturn 一定实在 handler 中被调用的，此时 alarm_goingoff 一定开启，我们需要将他置为 $0$。然后恢复 trapframe 即可。

uint64
sys_sigreturn()
{
  struct proc *p = myproc();
  *p->trapframe = *p->alarm_trapframe;
  p->alarm_goingoff = 0;
  return 0;
}

Lab5 COW: Copy-on-Write fork (hard)

xv6 中最著名的一个实验来了。实现 UNIX 中的写时复制系统。

在传统的 fork 中，内核会把父进程的所有内存都拷贝到子进程中，当然这十分耗时。并且大多数 fork 之后都会调用 exec 进行替换，这样原来复制的数据就都浪费了。

而写时复制就用到了懒分配的思想：fork 的时候并不实际进行复制，而是把父子进程都映射到同一块物理区域，并把写入权限 PTE_W 置为 $0$。这样，当有一个进程进行写入的时候，就会出现一个 $pagefault$。我们这时候再把这块页面复制出来，同时其他页面保持不变，这样即可实现高效的 fork 。

实现 COW 后，可能有多个进程共享一个页帧，那么只有当所有进程中释放这个页的时候，我们才能真正释放这块页面，不然都只是将其从页表中清除。

然后跟着提示就能一点一点实现了。

首先是 uvmcopy()。修改 uvmcopy()，把父进程的物理内存直接映射到子进程的虚拟内存上，而不是去分配新的内存。清除父进程和子进程 PTE_COW 的 PTE_W。可以从 PTE 中预留的位选一个来作为 COW 位。

// kernel/riscv.h
// ...
#define PTE_U (1L << 4) // 1 -> user can access
#define PTE_COW (1L << 8)

// kernel/vm.c
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  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);
    if (*pte & PTE_W) {
      *pte = (*pte & ~PTE_W) | PTE_COW;
    }
    flags = PTE_FLAGS(*pte);
    if (mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
    krefpage((void*)pa); // 给页面引用 +1
  }
  return 0;

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

然后是 usertrap()。修改 usertrap() 来处理缺页错误。如果缺页错误发生在 COW 页上，就分配一个新的物理页，拷贝原页帧的数据到新页，并设置新页的 PTE_W。写入导致的缺页异常，异常号为 $15$，从 scause 寄存器读出即可。

// kernel/vm.c

// check whether it is a vali page and a cow page
int
uvmcheckcowpage(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;

  return va < MAXVA
    && ((pte = walk(pagetable, va, 0)) != 0)
    && (*pte & PTE_V)
    && (*pte & PTE_U)
    && (*pte & PTE_COW);
}

// alloc a page and copy it
int
uvmcowcopy(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;

  if ((pte = walk(pagetable, va, 0)) == 0)
    panic("uvmcowcopy: walk");

  uint64 pa = PTE2PA(*pte);
  uint64 new = (uint64)kcopy_n_deref((void*)pa); // 拷贝一个 COW 页面
  if (new == 0)
    return -1;

  uint64 flags = (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW;
  uvmunmap(pagetable, PGROUNDDOWN(va), 1, 0);
  if (mappages(pagetable, va, 1, new, flags) == -1) {
    panic("uvmcowcopy: mappages");
  }

  return 0;
}

// kernel/trap.c
void
usertrap(void)
{
  // ...

  } else if((which_dev = devintr()) != 0){
    // ok
  } else if ((r_scause() == 15) && uvmcheckcowpage(p->pagetable, r_stval())) {
    if (uvmcowcopy(p->pagetable, r_stval()) == -1) {
      p->killed = 1;
    }
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }

  if(p->killed)
    exit(-1);

 // ...
}

然后是引用计数。对于每个页帧，都有一个引用计数，代表有多少个 COW 页正在使用这个页。那如果没有任何 COW 页还在使用这个页帧，我们就可以真正的释放这个页了。在 kalloc() 函数中，我们会把一个页的引用计数设为 $1$。然后在 kalloc() 函数中，我们需要先减少这个页的引用计数，如果减少后为 $0$，就可以直接释放这个页。

修改 pageref 可能有竞态问题，需要一个锁来保证只有一个进程进行修改。

#define PA2IDX(p) (((p) - KERNBASE)/PGSIZE)

struct spinlock pgreflock;
int pageref[PA2IDX(PHYSTOP)];

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&pgreflock, "cowref");
  freerange(end, (void*)PHYSTOP);
}

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

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

  acquire(&pgreflock);
  if (-- PA2PGREF(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);
  }
  release(&pgreflock);
}

最后在 uvmcopy 中，我们需要给每一个页的引用计数 $+1$。

void
krefpage(void* pa)
{
  acquire(&pgreflock);
  PA2PGREF(pa) ++;
  release(&pgreflock);
}

在 uvmcowcopy 中用到的 kcopy_n_deref 如下：

void
*kcopy_n_deref(void *pa)
{
  acquire(&pgreflock);

  if (PA2PGREF(pa) <= 1) {
    release(&pgreflock);
    return pa;
  }

  uint64 newpa = (uint64)kalloc();
  if (newpa == 0) {
    release(&pgreflock);
    return 0;
  }
  memmove((void*)newpa, (void*)pa, PGSIZE);
  PA2PGREF(pa) --;

  release(&pgreflock);
  return (void*)newpa;
}

最后还有一个提示：copyout 也会尝试写入数据，但是并不会引发缺页异常， 而是直接 panic。我们修改它进行 COW copy。

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

  while(len > 0){
    if (uvmcheckcowpage(pagetable, dstva))
      uvmcowcopy(pagetable, dstva);
    va0 = PGROUNDDOWN(dstva);
    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;
}

这个实验我感觉难度和 super page 一样，需要改动内核的地方特别多，还需要注意锁的问题。我在写这个实验的时候参考了 这个博客 和 这个博客。

End

后面的文件系统、设备驱动之类的，似乎对 AI infra 没有太大帮助了，这门课就暂时到这里吧。

下一门是 CMU 15-418 Parallel Computing