MIT6828 学习笔记 002 (lab utilities)

MIT6828 学习笔记 002 (lab utilities)

RayAlto OP
  2023-03-22 19:50:04 2023-03-22 19:50:04 创建   2024-03-10 16:48:48 2024-03-10 16:48:48 更新    

1. 准备工作 (ArchLinux)

1.1. 软件

我用的是 Arch ，其他发行版应该也有差不多的软件包

1
sudo pacman -S riscv64-linux-gnu-binutils riscv64-linux-gnu-gcc riscv64-linux-gnu-gdb qemu-system-riscv

1.2. 源码

1
git clone https://github.com/mit-pdos/xv6-riscv.git

好像这个更方便一点，里面有各个 lab 特化的 branch 和检验用的脚本：

1
git clone git://g.csail.mit.edu/xv6-labs-2022

如果一切都没问题的话，在源码目录下：

1
make qemu

应该就可以进入 Xv6 Shell 了

不知道为啥 Xv6 一启动就能把 load average 拉到 3 ，加上 CPUS=1 可以把 load average 维持在 1.3 左右，风扇依然狂转， CPU 直升 80 度

2. 实验

2.1. sleep

在 Xv6 里实现 sleep 程序，源码放在 user/sleep.c 里。我的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, const char *argv[]) {
    if (argc != 2) {
        write(2, argv[0], strlen(argv[0]));
        write(2, ": only 1 numeric parameter is required\n", 39);
        exit(1);
    }
    for (int i = 0; i < strlen(argv[1]); i++) {
        if (argv[1][i] > '9' || argv[1][i] < '0') {
            write(2, argv[0], strlen(argv[0]));
            write(2, ": \"", 3);
            write(2, argv[1], strlen(argv[1]));
            write(2, "\" is not a number\n", 18);
            exit(1);
        }
    }
    int nsleep=atoi(argv[1]);
    sleep(nsleep);
    exit(0);
}

在 Makefile 174 行 UPROGS 里加上 _sleep 就可以在 make qemu 时编译并在运行 Xv6 时把写的 sleep 程序复制进去。

在 git://g.csail.mit.edu/xv6-labs-2022 clone 下来的话可以通过：

1
./grade-lab-util sleep

自动检测结果，我的运行结果：

1
2
3
4
make: 'kernel/kernel' is up to date.
== Test sleep, no arguments == sleep, no arguments: OK (0.6s)
== Test sleep, returns == sleep, returns: OK (0.9s)
== Test sleep, makes syscall == sleep, makes syscall: OK (1.0s)

2.2. pingpong

和 book 的 Chapter1 的练习题差不多，父进程向子进程发送一个字节，子进程应该输出 <pid>: received ping ，然后子进程向父进程发送一个字节后 exit ，父进程输出 <pid>: received pong 后 exit ，源码放在 user/pingpong.c ，我的答案：

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
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, const char *argv[]) {
    int parent_pipe2child[2];
    if (pipe(parent_pipe2child) != 0) {
        write(2, argv[0], strlen(argv[0]));
        write(2, ": pipe failed\n", 14);
        exit(1);
    }
    int child_pipe2parent[2];
    if (pipe(child_pipe2parent) != 0) {
        write(2, argv[0], strlen(argv[0]));
        write(2, ": pipe failed\n", 14);
        exit(1);
    }
    int pid = fork();
    if (pid < 0) {
        write(2, argv[0], strlen(argv[0]));
        write(2, ": fork failed\n", 14);
        exit(1);
    }
    char buf = 'a';
    if (pid == 0) {
        // parent process
        pid = getpid();
        close(parent_pipe2child[0]);
        close(child_pipe2parent[1]);
        write(parent_pipe2child[1], &buf, 1); // ping
        read(child_pipe2parent[0], &buf, 1); // receive pong
        printf("%d: received pong\n", pid);
        wait((void *)0);
        exit(0);
    }
    else {
        // child process
        close(parent_pipe2child[1]);
        close(child_pipe2parent[0]);
        read(parent_pipe2child[0], &buf, 1); // receive ping
        printf("%d: received ping\n", pid);
        write(child_pipe2parent[1], &buf, 1); // pong
        exit(0);
    }
    exit(0);
}

2.3. primes

通过进程和管道采用这样的方式：

sieve prime

实现打印 2~35 之间的质数，源码放在 user/primes.c ，我的答案：

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
#include "kernel/types.h"
#include "user/user.h"

int build_neighbor();
void handle(int read_fd);

/**
 * make a pipe, fork a child, make the child handle(read_fd) and exit
 * return write_fd to parent
 * remember to close(write_fd)
 */
int build_neighbor() {
    int p[2];
    if (pipe(p) != 0) {
        write(2, "pipe failed\n", 12);
        exit(1);
    }
    int pid = fork();
    if (pid < 0) {
        write(2, "fork failed\n", 12);
        exit(1);
    }
    if (pid != 0) {
        // in child process, read from pipe
        close(p[1]);
        // listen to pipe[0]
        handle(p[0]);
        wait((void *)0);
        // child exit here
        exit(0);
        // child cannot get out of this block
    }
    // parent process, write to pipe
    close(p[0]);
    // return the write fd
    return p[1];
}

void handle(int read_fd) {
    int write_fd = -1;
    int p = 0;
    read(read_fd, &p, sizeof(p));
    printf("prime %d\n", p);
    int n = 0;
    while (read(read_fd, &n, sizeof(n)) != 0) {
        if (n % p == 0) {
            // drop
            continue;
        }
        if (write_fd == -1) {
            write_fd = build_neighbor();
        }
        // send the number to right neighbor
        write(write_fd, &n, sizeof(n));
    }
    if (write_fd != -1) {
        close(write_fd);
    }
    close(read_fd);
}

int main(int argc, const char *argv[]) {
    int write_fd = build_neighbor();
    for (int i = 2; i <= 35; i++) {
        // send the numbers to the rignt neighbor
        write(write_fd, &i, sizeof(i));
    }
    close(write_fd);
    wait((void *)0);
    exit(0);
}

2.4. find

实现一个精简版的 find 源码放在 user/find.c ，我的答案：

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
#include "kernel/types.h"
#include "kernel/fcntl.h"
#include "kernel/fs.h"
#include "kernel/stat.h"
#include "user/user.h"

#define SEP     '/'
#define BUF_LEN 512

void verify_dir(const char* dir, int* fd, struct stat* st) {
    *fd = open(dir, O_RDONLY);
    if (*fd < 0) {
        fprintf(2, "cannot open %s\n", dir);
        exit(1);
    }
    if (fstat(*fd, st) < 0) {
        fprintf(2, "cannot stat %s\n", dir);
        close(*fd);
        exit(1);
    }
}

void find(const char* base_dir,
          const char* file_name,
          const char* target_name) {
    int fd = 0;
    struct stat st;
    struct dirent de;
    // contatenate
    char buf[BUF_LEN];
    char* p = (void*)0;
    strcpy(buf, base_dir);
    p = buf + strlen(base_dir);
    if (p[-1] != SEP) {
        *p = SEP;
        p++;
    }
    memmove(p, file_name, DIRSIZ);
    p[DIRSIZ] = '\0';
    verify_dir(buf, &fd, &st);
    switch (st.type) {
    case T_DIR:
        if (strlen(buf) + 1 + DIRSIZ + 1 > sizeof(buf)) {
            printf("%s: dir too long\n", base_dir);
            break;
        }
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0 || strcmp(".", de.name) == 0
                || strcmp("..", de.name) == 0) {
                continue;
            }
            find(buf, de.name, target_name);
        }
    case T_DEVICE:
    case T_FILE:
        if (strcmp(file_name, target_name) == 0) {
            printf("%s\n", buf);
        }
    }
    close(fd);
}

int main(int argc, const char* argv[]) {
    if (argc != 3) {
        fprintf(2, "%s: expected 3 params, got %d", argv[0], argc);
    }
    find(argv[1], "", argv[2]);
    exit(0);
}

如果 open 失败了可以检查一下有没有 close 掉之前的 fd ， Xv6 在 kernel/param.h 定义了 NOFILE 为 16 ，也就是每个进程最多有 16 个 fd ，超过这个数会导致 open 失败。

2.5. xargs

实现一个简单的 xargs ，源码放在 user/xargs.c ，我的答案：

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
#include "kernel/types.h"
#include "user/user.h"

#define BUF_LEN 512

int main(int argc, char* argv[]) {
    if (argc < 2) {
        fprintf(2, "%s: at least 1 params is required\n", argv[0]);
        exit(1);
    }
    char buf[BUF_LEN];
    int read_len = 0;
    char* p_buf = buf;
    int pid = 0;
    while (read(0, p_buf, 1) != 0) {
        if (*p_buf != '\n') {
            p_buf++;
            read_len++;
            if (read_len >= BUF_LEN) {
                fprintf(2,
                        "%s: stdin too long, up to %d byte is acceptable\n",
                        argv[0],
                        BUF_LEN);
            }
            continue;
        }
        // line end
        *p_buf = '\0';
        char* child_argv[argc + 1];
        // copy argv from main except for argv[0] to child_argv
        for (int i = 1, j = 0; i < argc; i++, j++) {
            child_argv[j] = argv[i];
        }
        // add arg from stdin
        child_argv[argc - 1] = buf;
        child_argv[argc] = (void*)0;
        pid = fork();
        if (pid < 0) {
            fprintf(2, "%s: fork failed\n", argv[0]);
            exit(1);
        }
        if (pid > 0) {
            exec(child_argv[0], child_argv);
        }
        p_buf = buf;
        read_len = 0;
    }
    wait((void*)0);
    exit(0);
}
  • 为了方便这里定义了 BUF_LEN ，来自 stdin 的内容不能超过这个长度。
  • 这里直接用了 main 的 argv 里的其他参数，没有复制，为了能放进 exec 里没加 const 。
  • 没看懂题目说用 -n 1 是什么意思，反正这样写能过测试，不管了。
目录
MIT6828 学习笔记 002 (lab utilities)
  1. 1. 准备工作 (ArchLinux)
    1. 1.1. 软件
    2. 1.2. 源码
  2. 2. 实验
    1. 2.1. sleep
    2. 2.2. pingpong
    3. 2.3. primes
    4. 2.4. find
    5. 2.5. xargs