MIT S6.081 labs 笔记

utilities

用时 5h 左右.

Boot xv6

配环境配了半个多小时。官网的引导还是非常清晰的。

sleep

xv6 系统 exec指令时，创建一个子进程执行该用户指令，用户函数中可能会有系统调用。这时会陷入内核态并进行操作，再返回。全部执行完后要 exit 来让进程退出。

调用系统调用 sleep.

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

int main(int argc, char* argv[])
{
    if (argc < 2) {
        char* str;
        str = "Usage: sleep sleeptime..\n";
        write(1, str, strlen(str));
        exit(0);
    }
    int time = atoi(argv[1]);
    sleep(time);
    exit(0);
}

注意标准输入的 fd 号是 0，标准输出是 1，错误输出（stderr）是 2.

其中，系统调用 sleep(time) 将当前进程挂起 (time) 个 tick. 如果 sleep 过程中发生信号中断，会返回剩余没睡完的时间。

可能看书不仔细，没有找到 qemu 模拟的一个 tick 是多久。Linux 下的 sleep() 不是按 tick 睡而是按秒睡。

pingpong

该任务要求用 pipe 实现父进程和子进程的通信，子进程写一个 byte 发送给父进程。

pipe() 会创建一个管道，占用两个文件描述符 fd[2]，fd[0] 用于读，fd[1] 用于写。fork() 之后父进程 wait() 一下，等子进程做完它的事再去管道读。

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

int main(int argc, int *argv[]) {
    int fd[2];
    if (pipe(fd) < 0) {
        fprintf(2, "Pipe creation failed\n");
        exit(1);
    }
    int pid;
    if (!(pid = fork())) {
        fprintf(1, "%d: received ping\n", getpid());
        write(fd[1], "x", 1);
    }
    else {
        wait(0);
        fprintf(1, "%d: received pong\n", getpid());
        char *buf = malloc(sizeof(char));
        read(fd[0], buf, 1);
        fprintf(1, "message %s received\n", buf);
        free(buf);
    }
    close(fd[0]);
    close(fd[1]);
    exit(0);
}

primes

用 pipeline 求素数。题目说求 35 以内的就可以，但是测的时候求 100 多也没问题。做法是在每次递归时，将待筛选的数输入 pipe 内，让下一层递归读取并筛去，筛完的数再递归到下一层。

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

void test_prime(int fd) {
    int num, p;
    int rd;
    if ((rd = read(fd, &num, 4)) && rd != 4) {
        // end of recursion
        fprintf(2, "pipe read is not in int type\n");
        exit(0);
    }
    else if (!rd) exit(0);

    fprintf(1, "prime %d\n", num);
    int son_fd[2];

    pipe(son_fd);
    if (!fork()) { // child
        close(fd);
        close(son_fd[1]);
        test_prime(son_fd[0]);
    }
    else {
        close(son_fd[0]);
        while ((rd = read(fd, &p, 4))) {
            if (rd != 4) {
                fprintf(2, "pipe read is not in int type\n");
                exit(1);
            }
            if (p % num) {
                write(son_fd[1], &p, 4);
            }
        }
        close(son_fd[1]);
        close(fd);
        wait(0);
        exit(0);
    }
}

int main(int argc, char *argv[]) {
    int fd[2];
    pipe(fd);
    int i, n = 35;
    for (i = 2; i <= n; ++i) { // initialize
        write(fd[1], &i, 4);
    }
    close(fd[1]);
    test_prime(fd[0]);
    exit(0);
}

find

照着 ls 写递归版本就行。要先熟悉 stat、dirent 等描述结构体。stat详细可以看 stat.h。dirent 描述的是当前被读取的目录信息，其中包括索引节点号 inum 和目录名 name.

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

char*
fmtname(char *path)
{
  static char buf[DIRSIZ+1];
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  // Return name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  *(buf + strlen(p)) = 0;
  return buf;
}

void find(char* path, char* target) {
    char buf[512];
    char* p;
    int fd;
    struct dirent de;
    struct stat st;
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find: cannot open %s\n", path);
        return;
    }
    if (fstat(fd, &st) < 0) {
        fprintf(2, "find: cannot stat %s\n", path);
        close(fd);
        return;
    }
    switch(st.type) {
        case T_FILE:
            // printf("%s is a file, fmtname: %s, target: %s\n", path, fmtname(path), target);
            if (!strcmp(target, fmtname(path))) {
                printf("%s\n", path);
            }
            break;
        case T_DIR:
        // printf("%s is a directory\n", path);
            if (strlen(path) + DIRSIZ + 1 + 1 > sizeof(buf)) {
                printf("find: path too long\n");
                break;
            }
            strcpy(buf, path);
            p = buf + strlen(buf);
            *p++ = '/';
            while (read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0) continue;
                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                if (!strcmp(de.name, ".") || !strcmp(de.name, ".."))
                    continue;
                find(buf, target);
            }
            break;
        default:
            break;
    }
    close(fd);
}

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

xargs

模拟题。把当前标准输入中的内容存下来，接到 argv 后面，再在子进程中 exec 就可以了。

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

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

    // copy args to command ptr
    char *command[MAXARG];
    argc--;
    for (int i = 0; i < argc; ++i) {
        command[i] = argv[i + 1];
    }

    // read std input to buf, and append buf
    int input_size, argptr;
    while ((input_size = read(0, buf, sizeof(buf))) > 0) {
        argc++, argptr = 0;
        command[argc - 1] = malloc(64 * sizeof(char));
        for (int i = 0; i < input_size; ++i) {
            char ch = buf[i];
            if (ch == ' ') {
                argc++, argptr = 0;
                command[argc - 1] = malloc(64 * sizeof(char));
                if (argc > MAXARG) {
                    fprintf(2, "xargs: too many args!\n");
                    exit(1);
                }
            }
            else if (ch == '\n') {
                break;
            }
            else {
                command[argc - 1][argptr++] = ch;
            }
        }
    }

    // use childproc to execute the command follows xargs
    if (!fork()) {
        exec(argv[1], command);
    }
    else {
        wait(0);
    }
    exit(0);
}

---

最后 make grade 99 分，原来还需要上传一个完成时间。

echo 5 > time.txt && make grade

make grade，100/100

syscall

用时 4h 左右。

首先是 riscv64 gdb 的安装。直接 riscv64-unknown-elf-gdb 之后是这样：

riscv64-unknown-elf-gdb: command not found

先拷贝一份 gdb 源码到本地，再 mkdir build && cd build.

执行：

sudo apt install libgmp-dev
../configure --prefix=/usr/local --with-python=/usr/bin/python --target=riscv64-unknown-elf --enable-tui=yes
make -j$(nproc)
sudo make install

完成 riscv 版本 gdb 的安装。

再执行 riscv64-unknown-elf-gdb，就能启动 gdb 了。

（P.S. 做完 util 之后觉得 wsl2 太慢太卡了，还是要上 Ubuntu. 但是太久没用 Ubuntu, 到这一步花了我好几个小时 orz）

折腾完环境终于能进入正题了

Using gdb

在一个终端启动 make qemu-gdb，记录 tcp::26000

在另一个终端打开 gdb（riscv版或者 gdb-multiarch ）, 并输入

target remote localhost:26000

完成连接。进入 kernel

file kernel/kernel

然后按说明调试.

或者直接 gdb-multiarch -x .gdbinit

建议先阅读 xv6 books 的第四节。

问题答案：

Looking at the backtrace output, which function called syscall?

usertrap() in kernel/trap.c

What is the value of p->trapframe->a7 and what does that value represent? (Hint: look user/initcode.S, the first user program xv6 starts.)

1. sys status. EXEC or EXIT. in start at user/initcode.S, a7 is assigned with SYS_EXEC.

What was the previous mode that the CPU was in?

usermode. check sstatus:

p/t $sstatus
$5 = 100010

(Here we do as instruction, and if we check ‘p’ we’ll get ‘value has been optimized out’. It’s because creation of *p is after our breakpoint! what a fool is me.)

Write down the assembly instruction the kernel is panicing at. Which register corresponds to the varialable num?

80002078: 00002903 lw s2,0(zero) # 0 <_entry-0x80000000>

s2.

Why does the kernel crash? Hint: look at figure 3-3 in the text; is address 0 mapped in the kernel address space? Is that confirmed by the value in scause above? (See description of scause in RISC-V privileged instructions)

check scause, $1 = 13.

13 represents a load page fault. That’s because we load data from addr 0. 0 is not avaliable. Kernel space begins at 0x80000000.

What is the name of the binary that was running when the kernel paniced? What is its process id (pid)?

initcode.

pid is 1.

use p/x *p.

System call tracing

看不太懂。。这是要干啥。跟着 hint，找到 syscall.c 下的

// Fetch the nth 32-bit system call argument.
void
argint(int n, int *ip)
{
  *ip = argraw(n);
}

获取系统调用的第 n 个参数。

然后还找到有个函数 myproc() 返回当前正在运行的进程的 proc 结构体。

在 proc 中新建一个掩码变量，获取进行的系统调用号后用掩码与一下就知道现在调用什么了。根据 hint，还要注意 fork 时为子进程也 copy 一下掩码这个变量。

另外怎么没有地方提起返回值的问题。这里测试程序其实是规定了 trace 返回 0 的。

commit](https://github.com/Eykenis/xv6-labs-2022/commit/68a932a62dd3d357da8e84c9a77d3046da12443f))

Sysinfo

该系统调用输出一个 sysinfo 结构体。其中包括空闲内存大小和使用中的进程数量两个信息。

先将 sysinfotest 加入，会编译失败。去 user.h 声明一下 sysinfo 的结构体和函数。

xv6 的内存管理

xv6 将内存以链表的形式将空闲空间组织起来。见 kalloc.c 中对 run 和 kmem 的定义。run 就是一个单链表的定义。

kmem 的三个参数中，freelist 为空闲页链表。我们可以在 kalloc 函数中窥见 kmem 的运作方式。注意到每次 kalloc 都必须加锁。因为页表相关属于临界操作。

我们可以照着写 freememcount 函数用于计算页表空闲大小。虽然这里我们不修改临界资源，但为了避免结果不一致，还是加锁为好。

int
freememcount(void)
{
  uint64 freepg_cnt = 0;
  
  struct run* r;
  
  acquire(&kmem.lock);
  r = kmem.freelist;
  while (r) {
    r = r->next;
    freepg_cnt++;
  }
  release(&kmem.lock);

  return freepg_cnt * PGSIZE;
}

然后再来看proc.c. 所有的进程都在 struct proc proc[NPROC] 这个全局变量中，我们只需要遍历这个 proc 数组，然后看看状态不为 UNUSED 的有多少个就可以了。

int
procnum(void)
{
  struct proc* p;
  int proc_count = 0;

  for (p = proc; p != &proc[NPROC]; p++) {
    if (p->state != UNUSED) {
      proc_count++;
    }
  }
  return proc_count;
}

现在还有一个问题，我们这些操作都是在内核空间做的，我们需要将信息拷贝至用户空间。参考 copyout 函数的实现。

uint64
sys_sysinfo(void)
{
  uint64 st;
  struct sysinfo info;
  struct proc *p = myproc();

  argaddr(0, &st); // first arg in sysinfo() (userspace)

  info.freemem = freememcount();
  info.nproc = procnum();

  if (copyout(p->pagetable, st, &info, sizeof(info)) < 0)
    return -1;
  return 0;
}

commit

Pgtbl

看了很久的 book

Speed up system calls

应该属于进程间共享内存方式的通信。要求在内核和用户程序之间创建一个只读页，然后将 struct syscall 存入只读页中 USYSCALL 映射的地址。

ugetpid() 实现：

ugetpid(void)
{
  struct usyscall *u = (struct usyscall *)USYSCALL;
  return u->pid;
}

也就是说我们要在进程创建时，将进程用户空间 USYSCALL 这个地址位置存入 usyscall 的内容。

观察 memlayout.h。

// riscv.h
#define PGSIZE 4096
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
// memlayout.h
#define TRAMPOLINE (MAXVA - PGSIZE)
#define TRAPFRAME (TRAMPOLINE - PGSIZE)
#define USYSCALL (TRAPFRAME - PGSIZE)

xv6 使用 Sv39 RISC-V 架构，64 位虚拟地址只有低 39 位被使用。

在转换物理地址的过程中，虚拟地址高 27 位用于定位 PTE。PTE 将指向一个 44 位的带标记位的物理页号，然后虚拟地址的低 12 位为偏移。最后得到一个 56 位的物理地址。

所以，对于我们的进程，它拥有 2^39^ = 512G 空间，PGSIZE = 4M. 地址空间自顶向下分别为 trampoline(1 页)、trapframe(1 页)、heap, user stack 和 user text and data.

heap 是自顶向下增长的。所以，我们要将 usyscall 的内容存在堆底也就是进程虚拟地址的第三页。

hint 中的 mempages 即用于进行 proc 结构体中各个变量和地址空间的映射。

问题：写完之后 test，发生了 scause，signal=15，为 page fault. 访问页面出错了。

于是上 printf 调试大法。

最后发现子进程中 fork 会导致 ugetpid 运行缺页。

继续排查，发现是 allocproc 函数出了问题，应当在 proc_pagetable 之前就分配好 usyscall 的空间。因为proc_pagetable() 为进程各项分配页表映射。如果分配映射时 usyscall 还没被分配空间的话，肯定会导致 page fault.

又是一个不仔细导致的错误，有点低级。

再回顾整个 allocproc 过程：

1. 薅一个空闲进程过来
2. 为进程内指针分配物理空间（kalloc）
3. 创建一个页表，进行页表映射，以此创建进程各个项的用户空间地址。
4. 创建新的上下文。

Which other xv6 system call(s) could be made faster using this shared page? Explain how.

fork(). We add a pointer *proc in struct usyscall, then children could access there parent in USYSCALL page.

commit

Print a page table

主要参考 freewalk 函数。这个 freewalk 用于释放页表映射，过程中访问了各个页表。

看 freewalk 的时候注意了 freewalk 考虑了 riscv 的多级页表，会进行相应的递归调用。而且遇到 leaf 页表项会 panic. 这说明 freewalk 之前要先释放掉所有 leaf pagetable.

总之照着写就能写出来了。注意格式。

void recur_vmprint(pagetable_t pagetable, int level){
  for (int i = 0; i < 512; ++i) {
    pte_t pte = pagetable[i];
    if ((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {
      uint64 child = PTE2PA(pte);
      for (int j = 0; j < level; ++j)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, child);
      recur_vmprint((pagetable_t)child, level + 1);
    }
    else if (pte & PTE_V){
      for (int j = 0; j < level; ++j)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    }
  }
}

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

commit