Horbynz hub

⌈xv6-fall2021⌋ lab 1：Xv6 and Unix utilities

xv6
Word count: 7.2kReading time: 31 min
2022/02/28

LAB

传送门：Lab: Xv6 and Unix utilities


Boot xv6 (EASY)

clone xv6 仓库并切换到 util branch

1
2
3
4
5
$ git clone git://g.csail.mit.edu/xv6-labs-2021
Cloning into 'xv6-labs-2021'...
...
$ cd xv6-labs-2021
$ git checkout util

「注」上一篇 blog “环境配置” 最后 git clone 那个仓库不是本次实验所用仓库，只用作验证环境是否配置成功，可以 rm -rf PATHNANE/xv6 删掉

可以看到，git clone 后产生了一条 warning，并且当前路径内什么文件都没有。其实这是正常的，不用担心

键入 git branch -a 可以查看分支，每个分支对应每个 lab。换言之，每进行一个 lab，都需要先 git checkout LABx

当执行完 git checkout util 后会进入第一个 lab 实验环境

Git allows you to keep track of the changes you make to the code. For example, if you are finished with one of the exercises, and want to checkpoint your progress, you can commit your changes by running:

1
2
3
4
$ git commit -am 'my solution for util lab exercise 1'
Created commit 60d2135: my solution for util lab exercise 1
 1 files changed, 1 insertions(+), 0 deletions(-)
$

“git 会追踪你对代码做出的修改。例如，你完成了其中一个实验，并希望检查你的实验成果。你可以执行上述代码来 commit 你的更改”

You can keep track of your changes by using the git diff command. Running git diff will display the changes to your code since your last commit, and git diff origin/util will display the changes relative to the initial xv6-labs-2021 code. Here, origin/xv6-labs-2021 is the name of the git branch with the initial code you downloaded for the class.

“你可以用 git diff 来比较你对代码作出的修改。用 git diff origin/util 来比较你当前代码与最初那个 xv6-labs-2021 仓库的代码的差异，其中，origin/xv6-labs-2021 是最初分支的名字”

之后 make qemu 启动 xv6，ls 展示文件系统所有文件，本 assignment 就完成了，此处不再赘述


Grading and hand-in procedure

You can run make grade to test your solutions with the grading program.

“运行 make grade 以使用打分脚本（grading program）测试自己的实验程序。”

结合后面 assignment: sleep 最后一段话来看

Note that make grade runs all tests, including the ones for the assignments below.

“注意 make grade 会运行一个 lab 里面的所有 assignment，包括下面的其他小任务。”

也即是说，当前这个 lab utilities 包括五个 assignment: sleep, pingpong, primes, find, xargs。只要运行了 make grade，打分脚本会对全部五个 assignments 打分。

If you want to run the grade tests for one assignment, type:

1
$ ./grade-lab-util sleep

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

1
$ make GRADEFLAGS=sleep grade

which does the same.

“如果只是想测试其中一个 assignm，可以使用 ./grade-lab-util ASSIGNMENT 或 make GRADEFLAGS=ASSIGNMENT grade 来打分”


Summary

综上所述，进行一个实验时：

  • make GRADEFLAGS=ASSIGNMENT grade 测试 lab 里面每一个 assignment
  • make grade 测试整个 lab
  • git commit -am 'xxxx' 提交修改

Sleep (EASY)

要求

Implement the UNIX program sleep for xv6; 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.

“为 xv6 实现 Unix 的 sleep，要求用户指定一个时间片数量，sleep 要暂停这个数量的时间片。时间片由 xv6 定义，即两个时间中断之间间隔的时间。Solution 需要存放于 user/sleep.c 路径下”

提示

Look at some of the other programs in user/ (e.g., user/echo.c, user/grep.c, and user/rm.c) to see how you can obtain the command-line arguments passed to a program.

“阅读 user/ 路径下其他程序（如 user/echo.c, user/grep.c 和 user/rm.c），主要留意如何获得传递给程序的命令行参数”

————答：用 int main(int argc, char *argv[]) 获得，但要注意第二个参数是一个一维指针，而其元素是一维数组

If the user forgets to pass an argument, sleep should print an error message.

“如果用户忘记传递参数，请打印 error 信息”

————答：此处既可以 printf() 打印，也可以 fprintf(2, ...) 打印，后者可以参考 user/ls.c

The command-line argument is passed as a string; you can convert it to an integer using atoi (see user/ulib.c).

“命令行参数作为字符串而传递到 sleep，可以用 atoi()（参考 user/ulib.c）将字符串转化为整数”

See kernel/sysproc.c for the xv6 kernel code that implements the sleep system call (look for sys_sleep), user/user.h for the C definition of sleep callable from a user program, and user/usys.S for the assembler code that jumps from user code into the kernel for sleep.

“kernel/sysproc.c（里面的 sys_sleep()）是 xv6 内核态的 sleep() 系统调用；而 user/user.h 是 xv6 用户态下应用程序可调用的 sleep() 的 C 语言声明；并且 user/usys.S 是 sleep() 从用户态陷入用户态的汇编代码”

Summary

大概意思是用 xv6 提供的系统调用 sleep()，再封装一个 sleep 程序（或者说命令）

有一点要注意的是 main() 的参数，argv[0] 是命令，从 argv[1] 开始才是命令行参数————即若执行 sleep 10 那么 argv[0] 是 sleep，argv[1] 是 10

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// path: user/sleep.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
    if (argc <= 0) {
        printf("%s\n", "sleep: No argument!");
        //fprintf(2, "sleep: No argument!\n");
        exit(1);
    }

    int ticks = atoi(argv[1]);
    if (ticks < 0)    exit(1);
    int ret = sleep(ticks);
    if (ret < 0)    exit(1);

    exit(0);
}

Pingpong (EASY)

要求

Write a program that uses UNIX 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.

“利用 Unix 系统调用写一个程序，在两个进程之间通过一对管道（pipe）传送一个字节（“pingpong” a byte），即父进程往子进程方向，以及子进程往父进程这两个方向。当父进程向子进程发送一个字节时，子进程需要打印 “<pid>: received ping”（此处的 pid 是子进程的进程 id），然后子进程在管道向父进程写入字节，最后退出。当父进程读取来自子进程的数据时，需要打印 “<pid>: received pong”，然后退出。你的解决方案应该保存于 user/pingpong.c 路径下”


提示

首先，要求没说 “write a byte” 具体是什么内容，所以这里往管道里发送的数据是任意的

然后，大部分提示都是使用系统调用完成，所以此处不再赘述。最后一个提示大概意思是，用户程序可用的库函数是有限制的，可用的库函数在 user/user.h 能找到，除了 system calls 部分，其他部分的源码可在 user/ulib.c、user/printf.c 和 user/umalloc.c 找到


Summary

此处内容主要参考 xv6-handout-chap1-section1.3: Pipes

pipe 相当于一个缓冲区，主要和 fork() 配合使用，以处理 IPC（进程间通信）问题。

首先 fork() 复制父进程所有数据给子进程（引自 xv6-handout-chap1-section1.1: Processes and memory）

Fork gives the new process exactly the same memory contents (both instructions and data) as the calling process.

" fork() 使新进程拥有像当前进程一样相同的内存上下文（包括指令和数据）"

也就是执行完 fork()，父进程的 pipe 包括里面的数据都会被复制一份，产生的子进程也会包含这部分数据，从而达到数据从一个进程到另一个进程的效果（当然，需要注意，这个过程相当于 cpp 的浅拷贝，自 fork() 后父子两个进程并不是同一块内存映像，修改子进程并不能影响到父进程，反之亦然）

现在回到 pipe，关于 pipe 的使用还有很重要的一点（引自 xv6-handout-chap1-section1.3: Pipes）

If no data is available, a read on a pipe waits for either data to be written or for all file descriptors referring to the write end to be closed; in the later case, read will return 0, just as if the end of a data file had been reached.

“如果管道没有数据，对管道的 read() 会一直等待，直到管道有数据写入，或者该管道的所有写端文件描述符 fd 都被关闭了。如果是后者，相当于已接收到数据流最后一个文件，read() 会直接返回 0”

这是 xv6 pipe 很重要的一个特性————读阻塞。如果你要从管道中读数据，需要确保管道中有数据存在，否则读操作会一直阻塞相当于死循环。这个特性在后一个 assignment: primes 尤为重要，这里先打上预防针

现在总结一下，编程思路其实很简单。就是先 pipe()（一定要先创建管道，这样父子进程才能共享同一个管道），然后 fork() 创建父子进程，父进程先写后读，子进程先读后写


Solution

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
// path: user/pingpong.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main() {
    int p[2];
    char buf[32];

    pipe(p);
    if (fork() > 0) {                           // 父进程
	    int pid = getpid();
        int n = write(p[1], "1", 1);
        if (n != 1)    exit(1);
        close(p[1]);                            // 写完关闭写端
        n = read(p[0], buf, sizeof(buf));       // 读是阻塞操作，除非子进程写入数据
        if (n < 0)    exit(1);
	    printf("%d: received pong\n", pid);
        close(p[0]);
    } else {
	    int pid = getpid();
        int n = read(p[0], buf, sizeof(buf));   // 读是阻塞操作，除非父进程写入数据
        if (n < 0)    exit(1);
        close(p[0]);
        printf("%d: received ping\n", pid);
        n = write(p[1], "1", 1);
        if (n != 1)    exit(1);
        close(p[1]);
    }

    exit(0);
}

Primes (MODERATE)/(HARD)

要求

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

“使用管道写一个并发版本的 “素数筛子” 程序（prime sieve）。该程序源于 Unix 管道概念提出者——Doug McIlroy。参考 Bell Labs and CSP Threads 中间的图片以及周围的文字，了解怎样去实现 “素数筛子” 程序。你的解决方案需要保存于 user/primes.c”

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

“你的目标是使用 pipe() 和 fork() 设置管道。第一个进程将数字 2~35 送入管道。你要为每个素数创建一个进程，在这个进程里，需要从它前一个管道读数据，然后写入它后一个管道。xv6 限制了 fd 和进程号的数字，所以只要求求解 35 以内的素数”


提示

Once the first process reaches 35, it should wait until the entire pipeline terminates, including all children, grandchildren, &c. Thus the main primes process should only exit after all the output has been printed, and after all the other primes processes have exited.

“一旦第一个进程写入管道的数字到达 35，就应该停下来等。直到整个管线（流水线）执行完毕，包括所有子进程、子进程的子进程等等。因此主进程只能在所有输出打印完，所有其他素数进程退出后，才能退出”


Summary

这个 assignment 主要是复刻 “素数筛子”，所以第一步是弄懂 “素数筛子” 的思想。首先素数是除了 1 和自己本身外不含其他因子的数。所以从 2 开始，每遍历一个数字的时候把这个数的倍数都筛掉，因为这些倍数必存在当前这个数作为因子————比如当前遍历 2，其倍数 4, 6, 8…都含因子 2，因此不是素数，筛去。当遍历完所有 35 个数最后剩下来的就是 2~35 内所有素数

借用参考资料中的图：

现在应该可以理解这个图的意思了，就是想我们每个进程筛出一个数字的所有倍数。比如第一个进程从 2~35 中遍历所有数，只有不是 2 倍数的数才写入下一个进程的管道；第二个进程就筛出 3 的所有倍数，以此类推

上面打预防针的内存此处具体展开来说一下，就是读管道需不需要先关闭写端的问题

上面 pingpong 的情况是，先读后写没问题，也即是读之前可以不关闭写端。为什么可以这样呢？让我们来好好分析下 xv6-handout 关于管道读阻塞的介绍（还是 pingpong 引用的内容）

If no data is available, a read on a pipe waits for either data to be written or for all file descriptors referring to the write end to be closed; in the later case, read will return 0, just as if the end of a data file had been reached.

这段话不是说读之前一定要关闭写端，而是说管道的读操作只有在以下两种情况下才会返回：

  • 从管道中读到数据，无论全部读出还是读出部分，都可以返回，只是返回值不同
  • 管道无数据，但管道所有写端都关闭了。此时会立即返回 0

现在来总结一下：

  • pingpong 子进程不关闭写端，先读后写也没问题。因为父进程先往管道写数据，之后就可以确保子进程总是能读到数据
  • primes 子进程不关闭写端，先读后写会死循环。因为子进程会一直往下筛，筛到最后管道没数据了，如果进入子进程时不先关闭写端，就没法退出了

Solution

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
// path: user/primes.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

int main() {
    int p[2] = {0}, buf[64] = {0}, size = sizeof(int);

    // 第一个进程只需要 feed 所有数字然后等待即可
    pipe(p);
    for (int i = 2; i <= 35; ++i)
        if (write(p[1], &i, size) != size)    exit(1);
    while (1) {
        if (fork() == 0) {                      // 子进程
            close(p[1]);
            int n = 0, prime = 0, ptr = 0, tmp = 0;
            n = read(p[0], &prime, size);
            if (n == 0)    exit(0);             // 第一个字都读不出来就直接返回
            if (n < 0)    exit(1);
            printf("prime %d\n", prime);

            for (int i = 0; n > 0; ++i) {
                n = read(p[0], &tmp, size);
                if (n < 0)    exit(1);

                if (tmp % prime)    buf[ptr++] = tmp;
            }

            close(p[0]);
            pipe(p);                            // 开启另一个 pipe
            for (int i = 0; i < ptr; ++i)
                if (write(p[1], &buf[i], size) != size)    exit(1);
        } else {
            // 父进程，不止第一个进程会进来
            // 当第二个进程创建子进程后就变成了父进程
            // 此时该进程也会进来
            // 但无论怎样都好，反正父进程都让它等待即可
            close(p[0]);
            close(p[1]);
            wait(0);
            exit(0);
        }
    }
}

Find (MODERATE)

要求

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

“写一个 Unix find 命令的简单版本：在给定目录中找出所有文件。你的解决方案要求保存于 user/find.c”


提示

Look at user/ls.c to see how to read directories.

“阅读 user/ls.c 了解怎么读目录”

Use recursion to allow find to descend into sub-directories.

“递归 find 下层的（所有）子目录”

Changes to the file system persist across runs of qemu; to get a clean file system run make clean and then make qemu.

“如果一直运行 qemu 会改变文件系统（的组织），所以为了得到一个干净的文件系统，可以先 make clean 然后 make qemu”


Summary

这个 assignm 需要先了解 Unix find 命令，但其实不用了解得很深入，POSIX 标准的 find 很复杂可支持更灵活的通配符查找。而 xv6 所说的实现一个简单版本的 find，只要能像要求那样输出即可

我这里提供一个我自己实现的思路仅供参考，我所实现的 find 命令格式如下：

1
2
find . b        # 示例
find (directory) (filename)

第一个参数指定目录，第二个参数指定文件名。也就是说 find 后面至少两参数，并且 find 后面第一个参数必须是 dir（当然这里只是提供一种解决方案，我也在网上见过其他人 find . 用以查找所有文件的方案，但按我的思路执行 find . 是会出错的）

接下来参考 user/ls.c 来看看怎么样读取目录：

开头的函数 fmtname() 作用是标准化文件名，即相当于 printf("%14d", val) 的效果，也就是文件名长度不够 DIRSIZ 定义的长度，就补空格占位

第二个函数 ls() 内，fstat() 作用大概是将 fd 指向文件的元信息读出。元信息指该文件属于设备、文件还是目录等等，诸如此类的信息。

还是 ls() 内，stat() 作用大概是将某个路径下的元信息读出

其他内容应该不难理解了，最后，总结下读目录步骤：

  • open(PATHNAME)：打开文件
  • fstat()：读文件元信息
  • while()：检索此路径下所有文件类型

值得一提的是，if(de.inum == 0) 这个条件一定要加上，不然会死循环直到爆栈

我当时测试情况是这样的，当前在文件夹 a 内，里面只有一个文件 b，所以 ls a 是这样的：

1
2
3
.
..
b

看起来只需要遍历三次，但实际上还有一些不知道是什么的数据在文件 b 后面，这导致循环会一直向下执行下去


Solution

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
78
79
// path: user/find.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

// ls.c 里已经定义，且没被 static 修饰，所以直接引入
extern char *fmtname(char *);

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

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

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

    // 第二个参数不是目录(dir)，ERROR
    if (st.type == T_FILE) {
        fprintf(2, "find: %s is not a dir\n", dir);
        close(fd);
        return;
    }

    // 封装为绝对路径，存入 buf
    memmove(buf, dir, strlen(dir));
    p = buf + strlen(dir);
    *p++ = '/';
    if (st.type == T_DIR) {// 只处理形参 dir 为目录的情况(还可以是设备，但这里不考虑)
        // 遍历当前目录下所有文件/目录
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0)    continue;
            if (strcmp(".", de.name) == 0 || strcmp("..", de.name) == 0)    continue;

            // 封装为绝对路径，即此时 buf = dir + 当前迭代读出的文件/目录名
            memmove(p, de.name, strlen(de.name));
            p[strlen(de.name)] = '\0';

            if (stat(buf, &st) < 0) {
                printf("find: cannot stat %s\n", buf);
                continue;
            }

            if (st.type == T_DIR) {// 如果读出是目录，递归
                find(buf, path);
                continue;
            }

            if (strcmp(path, de.name) == 0) {// 如果读出是文件，判相等
                printf("%s\n", buf);
            }
        }
    }

    close(fd);
}

int
main(int argc, char *argv[])
{
    if(argc < 3) {
        fprintf(2, "find: cannot exec with too few parameters\n");
        exit(1);
    }
    for(int i = 2;  i < argc; i++)//可能有这种情况 find . file1 file2 file3
        find(argv[1], argv[i]);
    exit(0);
}

Xargs (MODERATE)

要求

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

“写一个 Unix xargs 命令的简单版本：从标准化输入 stdin 中读入行，然后将该行转化为命令行参数，最后执行命令。你的解决方案要求保存于 user/xargs.c”

The following example illustrates xarg’s behavior:

1
2
3
$ echo hello too | xargs echo bye
bye hello too
$

Note that the command here is “echo bye” and the additional arguments are “hello too”, making the command “echo bye hello too”, which outputs “bye hello too”.

“上面这个代码块展示了 xarg 的用法。注意 echo bye 命令以及额外的参数 “hello too”，组成了 xarg 的参数 “echo bye hello too”，这将会输出 “bye hello too””

上面这个例子有两个地方需要注意：

  • “|”：这是管道符，作用是将左边命令的输出，写入右边命令的 stdin。你可以将 stdin 理解为进程里面的一个缓冲区，进程从这个缓冲区里取数据，就是所谓的 “从 stdin 读入”。
  • 命令行参数：你可能会迷惑 stdin 参数和命令行参数有什么区别，但要意识到这两者不能混为一谈。有些命令（如 echo）只接受命令行参数而不接受 stdin 参数，所以 xargs 就来做这件事，将 stdin 参数转化为命令行参数，这样像 echo 这样的命令才能得以执行

Please note that xargs on UNIX makes an optimization where it will feed more than argument to the command at a time. We don’t expect you to make this optimization. To make xargs on UNIX behave the way we want it to for this lab, please run it with the -n option set to 1. For instance

1
2
3
4
$ echo "1\n2" | xargs -n 1 echo line
line 1
line 2
$

“请注意 Unix 的 xargs 命令，当用户提供更多参数时，xargs 会作出优化（作出了什么优化没说，其实也不重要）。我们不希望你也作出同样的优化。为了使 Unix xargs 命令以我们想要的方式表现，（对于多个参数的 xargs 命令）请（在 Unix 环境下）执行时带上
-n 1
选项（这才是本个 assignm 所期望的多参数选项的输出方式）。”（注：这里后半句的翻译我读得不是很懂，仅供参考）

但是，我参考了 菜鸟教程: Linux xargs 命令：-n 选项多行输出例子。这里用 Linux xargs 是因为找不到 Unix xargs 例子，唯一找到的是 GNU: xargs options，但里面并没有例子，只阐述了 xargs 的 POSIX 标准。不过 Linux 也是 Unix-like 系统，所以应该是一样用法的。参考例子后我觉得应该是下面这样输出多参数才对？

1
2
3
4
$ echo "1\n2" | xargs -n 1 echo line
line 1
2
$

对比上面例子，第二行输出我觉得应该是 2 而不是 line 2，当然这只是本人的理解，如果有误欢迎指出。事实上我也是这么实现的，结果通过测试了（只能说测试数据比较宽松，或者说我没读懂实验要求碰巧对？）。所以我揣测这个 assignm 的意图应该是对于多参数的 xargs，应该每个参数输出一行

然后还要注意到，上面涉及转义字符 ‘\n’ 的转化，不然像 “1\n2” 不可能出现两个参数。这里有个误区，直接 if (buffer[i] == '\n') 这样判断是错误的。我们现在是 OS DEVer，整个 kernel 是我们完成的，提取字符串这件事没人帮我们去做。

也就是说用户输入了字符串 “abc\ndef”，stdin 布局大概如下：

1
2
3
│0│1│2│3│4│5│6│7│8│9│
┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼
│"│a│b│c│\│n│d│e│f│"│

对于字符串首先要去掉双引号，然后处理转义字符，实际上应该判断 if (buffer[i] == '\' && buffer[i + 1] == 'n') 才对。但是另一方面，xv6 提供了 printf() 可用于格式化打印，所以为了统一输出操作，我们需要将 “\n” 转化为 ‘\n’（前者是字符串，后者是字符）即 ASCII 码 0xA


提示

Use fork and exec to invoke the command on each line of input. Use wait in the parent to wait for the child to complete the command.

“使用 fork() 和 exec() 去执行每行输入的命令，然后父进程调用 wait() 等待子进程完成命令”

To read individual lines of input, read a character at a time until a newline (‘\n’) appears.

“为了读入单独的一行，每次只读取一个字符，直到遇到回车”

kernel/param.h declares MAXARG, which may be useful if you need to declare an argv array.

“kernel/param.h 声明了 MAXARG，如果你想声明一个参数数组（像 main() 形参那样的 argv[] 数组）可以使用这个宏”

To test your solution for xargs, run the shell script xargstest.sh. Your solution is correct if it produces the following output:

1
2
3
4
5
6
7
8
$ make qemu
...
init: starting sh
$ sh < xargstest.sh
$ $ $ $ $ $ hello
hello
hello
$ $

You may have to go back and fix bugs in your find program. The output has many $ because the xv6 shell doesn’t realize it is processing commands from a file instead of from the console, and prints a $ for each command in the file.

“运行 shell 脚本 xargstest.sh 以测试你的 xargs 解决方案。若出现上面输出即表示正确。… … 你可能需要回头检查 find 命令（有可能之前侥幸通过但现在调用 find 命令出错），上面的输出有很多 $，因为 xv6 shell 没实现执行文件中的命令，只实现了执行 console 中的命令，所以才为文件里每条命令打印了 $”

这里解释下上面脚本的输出，先打开脚本，是以下内容：

1
2
3
4
5
6
mkdir a
echo hello > a/b
mkdir c
echo hello > c/b
echo hello > b
find . b | xargs grep hello

以下是预期输出：

1
2
3
4
5
6
7
8
$ make qemu
...
init: starting sh
$ sh < xargstest.sh
$ $ $ $ $ $ hello
hello
hello
$ $

共 6 条命令。第 1 条命令先执行，创建了一个目录 a，然后打印 $，第 2~5 同理。到了第 6 条命令，先执行 find 命令，打印了 3 个 hello，然后也打印 $。至于为什么最后一行有两个 $ ？第二个那是 xv6 shell 的命令提示符


Summary

前面说得可能有点乱，现在总结一下这个 assignm 期望效果：

1
2
3
4
5
6
7
8
9
10
11
$ echo hello too | xargs echo bye
bye hello too
$ 
$ echo "1\n2" | xargs echo line # 此处是我自己的理解
line 1
2                               # 原文是输出 "line 2"
$ 
$ find . b | xargs grep hello
./a/b: hello
./c/b: hello
./b: hello

我是按照这个效果去实现的，虽然可能对于第二个例子理解不对，但毕竟最终是通过测试了，所以还是那句话，仅供参考

所以我的思路如下：

  • 先将 stdin 读出来暂存于缓冲区，因为可能会有字符串参数，这需要提取。这里有一个要注意的地方是，stdin 最后一个字符必是回车，逻辑上应该要删掉的，但其实就算这个回车被追加到命令行参数数组里，最后也是多打印一个换行而已，而打分脚本我感觉判断比较宽松，所以不删应该也是没问题的。我在实现里删掉了，只是为了提醒自己 fd0 最后额外多一个换行符而已
  • 然后追加到命令行参数的数组 argv[] 里面。这里有一个要注意的地方是，追加多少个参数的问题。既然题目给出了宏 MAXARG，我猜追加的数量就是这个宏的值
  • 最后就是 fork() 然后交给子进程去 exec() 命令，这里也要注意 cd 命令除外，原因 xv6-handout 有，就不再阐述了

Solution

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
// path: user/xargs.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/param.h"
#include "user/user.h"

int
main(int argc, char **argv) {
    char buf[512];
    // 重新定义 argv[]->xargv[]
    char *xargv[MAXARG + 3];// xargs + exec + MAXARG(32个) + 0 结尾
    for (int i = 0; i < argc; ++i)    xargv[i] = argv[i];

    // 暂存 stdin 至 buf[]
    int i = 0;
    for (; i < sizeof(buf);) {
        char c;
        int n = read(0, &c, 1);
        if (n < 0)    exit(1);
        else if (n == 0)    break;
        buf[i++] = c;
    }
    buf[--i] = 0;// fd0 最后一个字符是回车，我这里覆盖掉，即改 CR->'\0'
    if (buf[0] == '"') {
        // 这块程序作用是："1\n2"->1\n2; "1\n2"hi"->"1\n2"
        // (只简单地取走前两个引号之间的字符，即使后面还有多的引号均忽略)
        int i = 1;
        for (; buf[i] != '"'; ++i)    buf[i - 1] = buf[i];
        buf[i] = 0;
        buf[i - 1] = 0;

        // 转化转义字符，但只处理 \n
        int size = strlen(buf);
        for (i = 0; i < size; ++i) {
            if (buf[i] == '\\'&& buf[i + 1] == 'n') {
                buf[i] = 0x0A;  // ASCII 0x0a = 回车
                memmove(&buf[i + 1], &buf[i + 2], size - i - 2);
                buf[size - 1] = 0;
                --size;
            }
        }
    }

    // buf[] 追加到 xargv[]
    char *p = buf;
    for (i = 0; i < strlen(buf) && argc < MAXARG + 2; ++i) {
        int j = 0;
        for (; i < strlen(buf); ++i, ++j)
            if (buf[i] == ' ' || buf[i] == '\n')    break;
        xargv[argc] = malloc(j + 1);
        memmove(xargv[argc], p, j);
        xargv[argc++][j] = 0;
        p = p + j + 1;
    }
    xargv[argc] = 0;

    // 将 xargv[] 移交 exec，注意 cd 命令除外(参考 user/sh.c)
    if (strcmp(xargv[1], "cd") == 0) {
        if (chdir(xargv[2]) < 0)    fprintf(2, "cd: cannot cd %s\n", xargv[2]);
        exit(0);
    }

    int pid = fork();
    if (pid < 0) {
        fprintf(2, "xargs: cannot xargs\n");
        exit(1);
    } else if (pid > 0) {
        wait(0);
        exit(0);
    } else {
        exec(xargv[1], &xargv[1]);// xargv[0] 只是 "xargs"，所以取再后一个
        exit(1);// exec 是不会返回的，唯一会返回的情况是出错了
    }
}

写于最后

万事开头难，第一次接触这些东西难免不适应，我最终花了 28h28m 完成整个 lab，总之，大家一起努力 👋

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. LAB
  2. 2. Boot xv6 (EASY)
    1. 2.1. Grading and hand-in procedure
    2. 2.2. Summary
  3. 3. Sleep (EASY)
    1. 3.1. 要求
    2. 3.2. 提示
    3. 3.3. Summary
    4. 3.4. Solution
  4. 4. Pingpong (EASY)
    1. 4.1. 要求
    2. 4.2. 提示
    3. 4.3. Summary
    4. 4.4. Solution
  5. 5. Primes (MODERATE)/(HARD)
    1. 5.1. 要求
    2. 5.2. 提示
    3. 5.3. Summary
    4. 5.4. Solution
  6. 6. Find (MODERATE)
    1. 6.1. 要求
    2. 6.2. 提示
    3. 6.3. Summary
    4. 6.4. Solution
  7. 7. Xargs (MODERATE)
    1. 7.1. 要求
    2. 7.2. 提示
    3. 7.3. Summary
    4. 7.4. Solution
  8. 8. 写于最后
Total : 18
2022
cpp translation winsock xv6
LIVEHOOD