写在前面：作为 mit 在国际上享誉盛名的 OS 实验，无数 CSer 及 OS 相关从业者都将完成 xv6 实验作为入坑 OS 的第一步。不得不说，xv6 确实有着独特的优势：

  • xv6 基于 RISC-V 开发，不需要被 x86 遗留下来的复杂机制所困扰，提供了一个清爽的、符合直觉的、优雅的学习生态 —— 与之对照的是泥工基于 x86 架构的 Linux 0.xx 系列实验，虽然赵炯博士的 linux 内核完全注释及 intel x86 的用户级手册提供了完善的资料，然而动辄几百页的手册确实使某些人望而生畏，进而放弃阅读，这无比令人遗憾。
  • xv6 实验环境的搭建非常便捷 (虽然必须承认，环境搭建过程中解决遇到的问题确实是不得不过的一关)，然而花费过多时间阅读上古文档的确是 a waste of time (鬼知道 bochs 的文档读了多久)。
  • xv6 的代码结构十分优雅：只需关注 kernel、mkfs、user 三个目录。虽然结构的简化导致了功能的简化，这对于初学者是十分友好的 (linux 0.11 的代码目录确实过于繁杂)，适当的留白还可以使初学者自由的填充内核，肆意的实现 idea 并测试。
  • xv6 提供了完整的学习资料 —— mit 6.1810 的课程录像、为 xv6 量身定做的手册 (xv6 book) 以及互联网上随处可见的 blog，可以帮助你更好的解决实验过程中的问题。一门好课所必备的要素，不仅要有深入浅出的内容讲授，更要有配套的、难度适中的实验及完善的资料及手册，这是大部分国内课程所欠缺的。
    PS：个人认为通过 “借鉴” blog 以获得灵感的行为是不提倡的，因为这会在无形中使你错过无数 treasure —— 实现过程中的细节、多样的实现思路、程序的健壮性与安全性…，对这些问题的思考会产生潜移默化的能力进步，尽管对完成实验没有直接的帮助，还会花费额外的时间。更有甚者直接采用 ctrl cv 大法速通了 xv6 实验用其填充简历，这不仅是对这门课程，更是对编写 xv6 并将其开源的几位教授的严重侮辱。

如此优秀实验的编写自然耗费了 Russ Cox、Frans Kaashoek 和 Robert Morris 三位教授宝贵精力，实验开源也为世界各地的 CSer 提供了宝贵的学习资源，请允许我献上由衷的感谢及敬意。

Lab: Xv6 and Unix utilities

此实验主要目的是熟悉 xv6 的架构、系统调用及相应用户程序的编写。实验本身十分简单，用户态程序的编写只需了解系统调用的格式 (API —— syscall) 及其作用，在实验过程中更应注重思考内核如何实现相应系统调用，并在 xv6 源码中验证。(Tips：巧妙使用 AI 确实可以极大提高效率)

sleep

Implement a user-level sleep program for xv6, along the lines of the UNIX sleep command. Your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

user/usys.S 包含系统调用 sleep 的用户态汇编代码：

1
2
3
4
sleep:
 li a7, SYS_sleep
 ecall
 ret

对于用户态程序，只需将对应系统调用编号 (SYS_sleep) 存入 a7 寄存器，随后执行 ecall 指令即可进入内核执行 sleep 系统调用。站在用户的视角，系统调用宛如一个黑匣，只需把对应参数存入对应内存或寄存器，执行 ecall 后便能得到一个我们期望的状态。jyy ：”操作系统中没有任何魔法。” —— 那我们便会有疑问，ecall 后执行了什么代码？ecall 又是如何定位到对应代码？ 然而面对庞大的内核代码，一行行的检索代码显然是不优雅的，曾经最为普遍的解决方式大概是阅读 xv6 book —— Chapter 4 Traps and system calls，然而当今更为推荐利用 AI 帮助我们检索代码，例如：

  • Q：xv6 在执行 ecall 指令后如何执行内核代码 (以 sleep 系统调用为例)？
    A: 在 xv6 中，当用户进程执行 ecall 指令（RISC-V 平台）后，处理器会触发一个 陷入（trap），从用户态（U-mode）切换到内核态（S-mode），并执行相应的内核代码。以下是 sleep 系统调用的执行流程：
    123balabala…
    总结
    整个 sleep 系统调用流程：

    1. 用户进程执行 sleep(n)，触发 ecall。
    2. usertrap() 处理 ecall，调用 syscall()。
    3. syscall() 调用 sys_sleep()，进入 sleep()。
    4. sleep() 使进程睡眠，调用 sched() 进行调度。
    5. 时钟中断 clockintr() 增加 ticks，调用 wakeup() 唤醒进程。
    6. scheduler() 重新调度 sleep 进程，恢复执行。

    这个流程展示了 xv6 如何利用 系统调用、进程调度、时钟中断 来实现 sleep。

如果对于某些细节实现仍然存在问题，可以继续深入：

  • Q：ecall 后跳到 usertrap 是何时设置的？
    A：ecall 指令执行后会进入 usertrap()，这是由 异常向量表（trap vector） 预先设置的，主要由 stvec（陷阱向量基址寄存器）控制。具体来说，usertrap() 在 ecall 触发后被调用的时机，取决于 stvec 在进程切换到用户态之前的设置。
    123balabala…
    总结
    • ecall 触发后，CPU 跳转到 stvec 指定的 uservec。
    • uservec 是个汇编入口，它切换内核栈并调用 usertrap()。
    • stvec 是在 用户进程切换前（usertrapret()） 设置为 uservec，确保 ecall 发生时进入 usertrap() 处理系统调用。

利用 AI 庞大的信息检索和处理能力可以极大的降低我们的学习门槛，学会提问因而显得至关重要，这不仅意味着要了解内核对于实现方法，更要思考其如此实现的原因，例如：

  • Q：为什么要在每个进程运行前将 stvec 设置到 usertrap 而不是统一设置？
    A：balabala…
    总结
    在 xv6 中，stvec 不能全局统一设置，而必须 在每个进程运行前动态调整，原因包括：

    1. 区分用户态和内核态陷入：进程进入内核态后 stvec 需要改为 kernelvec，否则内核态异常会错误跳转到 usertrap()。
    2. 每个进程的 uservec 可能不同：uservec 在 trampoline 区域，不同进程可能有不同的映射。
    3. 保证进程独立性：未来如果支持不同进程的 trap 处理方式，动态调整 stvec 让它们可以独立设置。
    4. 适配进程切换：不同进程运行前需要不同的 stvec，否则陷入时可能进入错误的异常处理代码。

    因此，在 xv6 的设计中，每次用户进程要运行前，都会在 usertrapret() 里 动态设置 stvec，确保 ecall 或其他用户态异常能够正确进入 usertrap()。

在内核代码学习过程中，如何做？为什么这样做？ 始终是贯彻始终的主线任务，你将扮演一位名为「哈兵」的神秘角色… 保持对一切事物的好奇和怀疑，你将一步步揭开 xv6 的神秘面纱。

pingpong

Write a user-level program that uses xv6 system calls to ‘’ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “<pid>: received ping”, where <pid> is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “<pid>: received pong”, and exit. Your solution should be in the file user/pingpong.c.

pipe 为不同进程间通信提供了灵活的接口，这不仅指管道构建时的任意性，还涉及到传输过程中隐含的通信规则。同样的，pipe 的实现不可避免的会涉及到文件系统、读写的并发性等复杂问题，故目前并不打算深入阅读其实现源码，这个任务会放在实验末期。

primes

Write a concurrent prime sieve program for xv6 using pipes and the design illustrated in the picture halfway down this page and the surrounding text. This idea is due to Doug McIlroy, inventor of Unix pipes. Your solution should be in the file user/primes.c.

很有意思的部分，参考文章中提到的 Bell Lab 让人有恍然隔世之感，在文章中你可以看到在那个硬件受到限制的年代，古早时期的码农们为解决问题天马行空又无比优雅的思路。根据实验要求，必须使初始进程最后退出，这也就规范了递归的方向。以下是我的实现 (感觉码风 烂的像屎 还有很大进步空间)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void sieve(int p_read){
    int prime;
    if(read(p_read, &prime, sizeof(prime)) == 0){
        exit(0);
    }
    fprintf(1, "prime %d\n", prime);
    
    int temp;
    int p[2];
    pipe(p);

    if(fork() == 0){
        // child
        close(p_read);
        close(p[1]);
        sieve(p[0]);
    } else {
        // parent
        close(p[0]);
        while(read(p_read, &temp, sizeof(temp)) != 0){
            if(temp % prime != 0){
                write(p[1], &temp, sizeof(temp));
            }
        }
        close(p[1]);
        wait(0);
    }

    exit(0);
}

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

    int p[2];
    pipe(p);

    if(fork() == 0){
        // child
        close(p[1]);
        sieve(p[0]);

    } else {
        // parent
        close(p[0]);
        for(int i = 2; i <= 35; i++){
            write(p[1], &i, sizeof(i));
        }
        close(p[1]);
        wait(0);
    }
    
    exit(0);
}

find

Write a simple version of the UNIX find program for xv6: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

有点麻烦的用户程序，因为其涉及到了文件系统中的数据结构，但 ls 的实现可以提供很大程度的参考 (注意是参考，直接不经大脑偷过来会比较麻烦)。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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 blank-padded name.
  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  memset(buf+strlen(p), 0, DIRSIZ-strlen(p));
  return buf;
}

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

    if((fd = open(path, O_RDONLY)) < 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_DEVICE:
    case T_FILE:
        if(strcmp(fmtname(path), filename) == 0){
            printf("%s\n", path);
        }
        break;

    case T_DIR:
        if(strlen(path) + 1 + DIRSIZ + 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 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                continue;
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;

            find(buf, filename);
        }
        break;
    }
    close(fd);
}
    
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);
}

该部分实现花费了我将近半个小时 debug，主要踩了两个坑：

  • 直接偷来的 fmtname 函数采用 ‘ ‘ (空格) 填充，导致 strcmp 函数返回错误，程序没有输出。
  • 在发现该问题后，鼠鼠非常爽快的用了 strcmp(fmtname(A), fmtname(B)) == 0 作为判断条件，结果就是所有文件都被输出了。最后发现是因为 fmtname 函数将返回字符串存储在函数内静态定义的 buf 中，strcmp 函数比较的地址空间指向同一地址，并且其首次保存的名称被覆盖掉了，这种低级错误令人忍俊不禁 默写 static 三遍✋😭🤚

所以说偷代码之前一定要读明白啊！！！

xargs

Write a simple version of the UNIX xargs program for xv6: its arguments describe a command to run, it reads lines from the standard input, and it runs the command for each line, appending the line to the command’s arguments. Your solution should be in the file user/xargs.c.

真实的 xargs on Unix 更为灵活，实现自然更为复杂，还好我们只用实现极简版。实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main(int argc, char *argv[]) {
    if(argc < 2) {
        fprintf(2, "usage: xargs command\n");
        exit(1);
    }

    char *argvs[MAXARG];
    for(int i = 1; i < argc; i++) {
        argvs[i - 1] = argv[i];
    }
  
    char buf[512];
    char *p = buf;
    while(read(0, p, sizeof(char)) > 0){
        if(*p != '\n'){
            p++;
        } else {
            *p = '\0';
            p = buf;
            argvs[argc - 1] = buf;
            if(fork() == 0){
                // child
                exec(argvs[0], argvs);
            } else {
                // father
                wait(0);
            }
        }
    }
    exit(0);
}

上例实现代码虽然可以顺利通过测试用例，在内存安全方面的考虑仍有所欠缺。不同于用户态程序在进程结束后释放掉内存空间，内核中处理字符串时要特别注意指针带来的内存问题。