6.S081-Lab 1 Xv6 and Unix utilities

发表于2022-05-29更新于2023-04-25字数统计1.9k阅读时长16分阅读次数

前言

6.S081是MIT的一门操作系统课，这门课程使用一个简化的 Unix-like 系统 xv6 为例进行讲解，该课程主要作业是一系列的Lab，本篇博客记录第一个 Lab：Xv6 and Unix utilities。这次 Lab的主要内容是编写一些简化版本的小程序，这些小程序通过调用内核提供的系统调用来完成功能。Lab链接：https://pdos.csail.mit.edu/6.828/2021/labs/util.html

sleep

比较简单，直接调用系统调用sleep即可AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @file sleep.c
 * @author fxd (fanxiaodong@buaa.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-05-25
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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

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

pingpong

通过fork系统调用创建一个子进程，并通过管道实现两个父子进程之间的双向通信。

这里需要注意的是，管道中的数据是“无主数据”，一个进程写进管道中的数据可能被它自己再次读出来，所以需要创建两个独立的管道；还有就是及时将不需要使用的管道端关闭。

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
/**
 * @file pingpong.c 创建两个管道，以实现父子间双向通信
 * @author fxd (fanxiaodong@buaa.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-05-25
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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

int main(int argc, char *argv[])
{
    int p1[2];
    int p2[2];
    pipe(p1);
    pipe(p2);

    int pid;
    if ((pid = fork()) < 0) {
        fprintf(2, "fork err");
        exit(1);
    } else if (pid == 0) {
        // child
        close(p1[0]);
        close(p2[1]);
        char buf[1];
        if (read(p2[0], buf, 1) > 0) {
            fprintf(1, "%d: received ping\n", getpid());
        }
        write(p1[1], buf, 1);
        close(p1[1]);
        exit(0);
    } else {
        // parent
        close(p1[1]);
        close(p2[0]);
        write(p2[1], "h", 1);
        close(p2[1]);
        char buf[1];
        if(read(p1[0], buf, 1) > 0){
            fprintf(1, "%d: received pong\n", getpid());
        }
        wait(0);
        exit(0);
    }

}

primes

创建一系列的进程，父子进程之间通过管道进行通信，以此实现质数过滤的效果。第一个进程将2-35通过管道送入子进程，子进程打印第一个2，然后将管道中剩余数中能被2整除的丢弃，剩余的数通过管道送入它自己的子进程，如此递归。

做这道题的时候一定要记得将不使用的管道及时关闭，不然可能会出现两个问题：

  1. 文件描述符fd不够用。
  2. 管道输入端不关闭时，输出端使用 read读取时会阻塞不返回，程序就死在了某处。
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
80
81
82
83
84
85
86
87
88
89
/**
 * @file primes.c 创建一系列的管道，用于过滤质数，本题需要注意的是一定将不使用的管道端关闭，不然有些读操作会阻塞
 * @author fxd (fanxiaodong@buaa.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-05-25
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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

void child_proc(int* p) {
    // read first num from pipe and print it
    int num;
    int ret;
    if ((ret = read(p[0], &num, sizeof(int))) != sizeof(int)) {
        exit(0);
    }
    
    printf("prime %d\n", num);

    // feed num into next pipe
    int p1[2];
    if (pipe(p1) < 0) {
        fprintf(2, "pipe p1 err\n");
        exit(1);
    }
    int pid;
    if ((pid = fork()) < 0) {
        fprintf(2, "fork err\n");
        exit(1);
    } else if (pid == 0) {
        close(p[0]);
        close(p1[1]); // close pipe no need, otherwise read block
        // child
        child_proc(p1);
    } else {
        // parent
        close(p1[0]);
        int num1;
        int ret;
        while ((ret=read(p[0], &num1, sizeof(int))) == sizeof(int)) {
            if (num1 % num != 0) {
                if (write(p1[1], &num1, sizeof(int)) != sizeof(int)) {
                    fprintf(2, "write err\n");
                    exit(1);
                }
            }
        }
        close(p1[1]);
        close(p[0]);
        wait(0);
        exit(0);
    }
}

int main(int argc, char* argv[]) 
{
    int p[2];
    if (pipe(p) < 0) {
        fprintf(2, "pipe err\n");
        exit(1);
    }
    int pid;
    if ((pid = fork()) < 0) {
        fprintf(2, "fork err\n");
        exit(1);
    } else if (pid == 0) {
        // child
        close(p[1]);
        child_proc(p);
    } else {
        // parent feed num into pipe
        close(p[0]);
        for (int i=2; i<=35; ++i) {
            if (write(p[1], &i, sizeof(int)) != sizeof(int)) {
                fprintf(2, "write err\n");
                exit(1);
            }
        }
        close(p[1]);
        wait(0);
        exit(0);
    }
    exit(0);
}

find

这道题是要求实现一个简易版本的find命令，思路也是比较简单，递归的遍历目录中的子文件或子目录，可以参考ls.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
 * @file find.c 实现简易版的 find，递归的遍历目录树寻找 filename
 * @author fxd (fanxiaodong@buaa.edu.cn)
 * @brief 
 * @version 0.1
 * @date 2022-05-26
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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

// 从路径获取文件名
char* fmtname(char *path)
{
    char *p;

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

    return p;
}

// 递归的对路径path寻找filename
void find_aux(char* path, char* filename) {
    char buf[512];
    int fd;
    char* p;
    struct stat st;
    struct dirent de;
    char* cur_name = fmtname(path);
    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "find_aux: cannot open %s\n", path);
        return;
    }
    if(fstat(fd, &st) < 0){
        fprintf(2, "find_aux: cannot stat %s\n", path);
        close(fd);
        return;
    }
    switch (st.type) {
    // 如果是文件，则对比名称
    case T_FILE:
        if (strcmp(cur_name, filename) == 0) {
            printf("%s\n", path);
        }
        break;
    // 如果是目录则深入寻找
    case T_DIR:
        // do not dive into .. or .
        if (strcmp(".", cur_name) == 0 || strcmp("..", cur_name) == 0) {
            return;
        }
        if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
            printf("find_aux: path too long\n");
            break;
        }
        strcpy(buf, path);
        p = buf+strlen(buf);
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            memmove(p, &de.name, DIRSIZ);
            find_aux(buf, filename);
        }
    }
    close(fd);
}

int main(int argc, char* argv[]) 
{
    if (argc != 3) {
        fprintf(2, "Usage: find dir filename\n");
        exit(1);
    }
    // handle . and ..
    if (strcmp(".", argv[1]) == 0 || strcmp("..", argv[1]) == 0) {
        int fd;
        char buf[30];
        strcpy(buf, argv[1]);
        int len = strlen(buf);
        buf[len++] = '/';
        if ((fd = open(argv[1], 0)) < 0) {
            fprintf(2, "main: cannot open %s\n", argv[1]);
            exit(1);
        }
        struct dirent de;
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            // avoid . and ..
            if(strcmp(".", de.name) == 0 || strcmp("..", de.name) == 0)
                continue;
            // 读的时候会有个空路径，需要排除
            if(de.inum == 0)
                continue;
            memmove(buf+len, de.name, DIRSIZ);
            find_aux(buf, argv[2]);
        }
        close(fd);
    } else {
        find_aux(argv[1], argv[2]);
    }
    exit(0);
}

xargs

实现一个简化版本的xargs，xargs从标准输入中读取多行数据，每行数据作为后续命令的参数，通常配合管道使用，便于将上一个命令的输出作为后一个命令的参数，例如：

1
2
$ echo hello | xargs echo bye
bye hello

实现的思路是通过对标准输入中的字符进行判断，如果是\n则通过fork和exec系统调用来执行一次命令，等到子进程执行完之后继续读标准输入。

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
/**
 * @file xargs.c UNIX xargs 的简易实现
 * @author your name (you@domain.com)
 * @brief 
 * @version 0.1
 * @date 2022-05-28
 * 
 * @copyright Copyright (c) 2022
 * 
 */

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

#define BUF_SIZE 512

int main(int argc, char* argv[]) {
    if (argc < 2) {
        fprintf(2, "Usage: xargs command\n");
        exit(1);
    }
    char* args[MAXARG+1];
    int index = 0;
    for (int i=1; i<argc; ++i) {
        args[index++] = argv[i];
    }

    char buf[BUF_SIZE];
    char *p = buf;
    while (read(0, p, 1) == 1) {
        if ((*p) == '\n') {
            *p = 0;
            int pid;
            if ((pid = fork()) == 0) {
                // child
                // exec only one arg
                args[index] = buf;
                exec(argv[1], args);
                fprintf(2, "exec %s failed\n", argv[1]);
                exit(0);
            }
            // parent
            wait(0);
            p = buf;
        } else {
            ++p;
        }
    }
    exit(0);
}

测试结果

2021/5/29测试通过：

1
make grade

参考文献

  1. https://pdos.csail.mit.edu/6.828/2021/schedule.html