【MIT 6.S081】2020, 实验记录（1），Lab: Xv6 and Unix utilities

实验准备

这个 lab 用来学习尝试如何通过 system call 来实现常见的 shell 命令行程序，比如 ls、sleep、xargs 等。

• 实验官网

可以使用 docker 搭建实验环境：

docker pull debian:bullseye
docker run -it --name mit6.s081 -d debian:bullseye /bin/bash

然后按照实验官网的介绍，在 git 下载源代码并启动。

Tasks

Task 1: Boot xv6

这个 task 就是在 git 上下载源代码，并启动 xv6 系统：

$ make qemu

成功后就可以看到 OS 成功启动。

Task 2: sleep

本 task 以及接下来的 task，都是在 /user 目录下实现用户级程序。

这个 task 新建一个 user/sleep.c，并通过调用 system call 来实现睡眠的功能，代码较为简单：

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

int
mian(int argc, char *argv[])
{
    if (argc < 2) {
        fprintf(2, "Usage: sleep ticks...\n");
        exit(1);
    }

    int ticks = atoi(argv[1]);
    sleep(ticks);  // 系统调用的 sleep，声明在 `user/user.h` 中
    exit(0);
}

完成后在 Makefile 中的 UPROGS 里添加上 sleep。

测试：

./grade-lab-util sleep

Task 3: pingpong

通过该 task 学会 fork 一个子进程，并实现父进程与子进程的通信。

我们需要实现 fork 一个子进程，并让父进程向子进程发送一个字节，然后子进程再向父进程发送一个字节。

关键技术细节：

• 使用 pipe 函数建立用于进程间通信的通道：

int fds[2];
pipe(fds);

这里 fds[0] 用于 read，fds[1] 用于 write，每个进程在使用完某个 fd 后需要 close 掉 fd。

• read() 函数的行为：在另一方未关闭写的 fd 时，自己读取且没有更多消息时会阻塞住；而在另一方关闭了写的 fd 且自己没有更多消息可以读时，会立刻返回 0.

代码实现：

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


int
main(int argc, char *argv[])
{
    int fds[2], pid, n, xstatus;
    enum { BYTE_SZ=1 };
    if (pipe(fds) != 0) {
        printf("pipe() failed\n");
        exit(1);
    }
    pid = fork();
    if (pid > 0) {  // parent proc
        // 向子进程发送一个字节
        char parent_buf[BYTE_SZ];
        if (write(fds[1], "x", BYTE_SZ) != BYTE_SZ) {
            printf("pingpong oops 1\n");
            exit(1);
        }
        // 等待子进程结束
        wait(&xstatus);
        if (xstatus != 0) {
            exit(xstatus);
        }
        // 读取子进程发送过来的字节
        while ((n = read(fds[0], parent_buf, BYTE_SZ)) > 0) {
            if (parent_buf[0] != 'x') {
                printf("pingpong oops 2\n");
                exit(1);
            }
            printf("%d: received pong\n", getpid());
            close(fds[0]);
            close(fds[1]);
            exit(0);
        }
    } else if (pid == 0) {  // child proc
        // 等待读取父进程发送的字节
        char child_buf[BYTE_SZ];
        while ((n = read(fds[0], child_buf, BYTE_SZ)) > 0) {
            if (child_buf[0] != 'x') {
                printf("pingpong oops 2\n");
                exit(1);
            }
            printf("%d: received ping\n", getpid());
            // 向父进程发送一个字节
            if (write(fds[1], "x", BYTE_SZ) != BYTE_SZ) {
                printf("pingpong oops 2\n");
                exit(1);
            }
            close(fds[0]);
            close(fds[1]);
            exit(0);
        }
    } else {
        printf("fork() failed\n");
        exit(1);
    }
    exit(0);
}

测试：

Task 4: primes

这里需要使用 fork 子进程和进程间通信的技术实现 2~35 以内质数的筛选。

思路如下：

大致就是：

• 第一个进程将 2~35 写入管道
• 然后 fork 第二个进程，逐个从管道中读出数字，再将符合条件的数字送入下一个管道给第三个进程
• 第三个进程类似…

代码实现如下：

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


#define INT_SIZE (sizeof(int))
#define MAX_LIMIT  35
#define READ_END 0
#define WRITE_END 1


int
main(int argc, char *argv[])
{
    int fds1[2], fds2[2], n, p, xstatus, pid;
    int *left_fds = fds1;  // 左通道
    int *right_fds = fds2; // 右通道
    if (pipe(left_fds) != 0 || pipe(right_fds) != 0) {
        printf("pipe() failed\n");
        exit(1);
    }
    // feed numbers
    for (int i = 2; i < MAX_LIMIT; ++i) {
        write(left_fds[WRITE_END], &i, INT_SIZE);
    }
    close(left_fds[WRITE_END]);
    int first_loop = 1;
    while (1) {
        int is_success = read(left_fds[READ_END], &n, INT_SIZE);  // read from left
        if (is_success == 0) {   // if read end
            close(left_fds[READ_END]);
            close(right_fds[READ_END]);
            close(right_fds[WRITE_END]);
            if (first_loop != 1) {
                wait(&xstatus);
                exit(xstatus);
            } else {
                exit(0);
            }
        }
        // 如果是第一次进入 Loop，则需要打印 prime 并创建一个子进程
        if (first_loop == 1) {
            pid = fork();
            if (pid == 0) {  // child proc
                first_loop = 1;
                close(left_fds[READ_END]);
                close(left_fds[WRITE_END]);
                int *temp = left_fds;
                left_fds = right_fds;
                right_fds = temp;
                if (pipe(right_fds) != 0) {
                    printf("pipe() failed\n");
                    exit(1);
                }
                close(left_fds[WRITE_END]);
                continue;
            } else if (pid > 0) {  // parent proc
                first_loop = 0;
                p = n;
                printf("prime %d\n", p);
                continue;
            } else {
                printf("fork() failed\n");
                exit(1);
            }
        } else {
            if ((n % p) != 0) {
                write(right_fds[WRITE_END], &n, INT_SIZE);
            }
        }
    }
}

测试：

Task 5: find

find 命令实现在一个目录中递归地寻找特定名的文件。

在代码实现中，需要对子目录进行递归查询，这里对文件和目录的遍历可以参考 ls.c 中的代码。代码实现如下：

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


/**
 * 获取一个 path 的名称，比如 `./a/b` 将返回 `b`
*/
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));
  buf[strlen(p)] = '\0';
  return buf;
}

void find(char *path, char const * const target) {
    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 open %s\n", path);
        close(fd);
        return;
    }

    switch (st.type) {
    case T_FILE: {
        char *fname = fmtname(path);
        if (strcmp(fname, target) == 0) {
            printf("%s\n", path);
        }
        break;
    }
    case T_DIR: {
        char buf[512], *p;
        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)
                continue;
            memmove(p, de.name, DIRSIZ);
            p[DIRSIZ] = 0;
            if (stat(buf, &st) < 0) {
                printf("find: cannot stat %s\n", buf);
                continue;
            }
            char* dir_name = fmtname(buf);
            if (strcmp(dir_name, ".") != 0 && strcmp(dir_name, "..") != 0) {
                find(buf, target);
            }
        }
        break;
    }}
    close(fd);
}

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

    exit(0);
}

实验测试：

Task 6: xargs

先解释一下这个命令的作用，以下面这个示例为例：

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

把 | 前面命令的 stdout 输出当作 xargs 命令的 stdin，然后 xargs 依次读取 stdin 的每一行，把每一行拼到 xargs 后面“echo byte”字符串后面并当成一个命令来执行。所以上面这个命令执行的结果等价于 xargs echo bye hello too。

再举一个例子，比如 echo "1\n2" | xargs echo bye 的执行结果，相当于依次执行 echo bye 1 和 echo bye 2。

在代码实现中，就是每次从 stdin 中读取一行，然后将其与 xargs 后面的字符串拼起来形成一个命令，fork 出一个子进程并交给 exec 来执行：

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


#define STDIN 0
#define BUF_SZ 512

static char buf[1024];
static char *args[MAXARG];
static int arg_num_init = 0;
static int argnum = 0;

int readline(int fd) {
    char readbuf[2];
    argnum = arg_num_init;
    int offset = 0;
    while (1) {
        // 找到第一个非空字符
        while (1) {
            if (read(fd, readbuf, 1) != 1) {
                return 0;
            }
            if (readbuf[0] == '\n') {
                return 1;
            }
            if (readbuf[0] != ' ' && readbuf[0] != '\t') {
                args[argnum++] = buf + offset;
                buf[offset++] = readbuf[0];
                break;
            }
        }
        // 找到一个 arg
        while (1) {
            if (read(fd, buf + offset, 1) != 1) {
                buf[offset] = '\0';
                return 0;
            }
            if (buf[offset] == '\n') {
                buf[offset] = '\0';
                return 1;
            }
            if (buf[offset] == ' ' || buf[offset] == '\t') {
                buf[offset++] = '\0';
                break;
            }
            ++offset; 
        }
    }
}


int
main(int argc, char *argv[])
{
    int pid, status;
    if (argc < 2) {
        fprintf(2, "Usage: xargs command ...\n");
        exit(1);
    }
    char *command = argv[1];
    arg_num_init = argc - 1;
    args[0] = command;
    for (int i = 1; i < argc; i++) {
        args[i] = argv[i + 1];
    }
    int flag = 1;
    while (flag) {
        flag = readline(STDIN);
        args[argnum] = 0;
        if (flag == 0 && argnum == arg_num_init) {
            exit(0);
        }
        pid = fork();
        if (pid == 0) {
            exec(command, args);
            printf("exec failed!\n");
            exit(1);
        } else {
            wait(&status);
        }
    }
    exit(0);
}

实验测试：