文章

[mit6.s081] Lab1: Unix utilities 实验记录

发表于 更新于
作者 ypj
16 分钟阅读
[mit6.s081] Lab1: Unix utilities 实验记录

这是实验过程中参考的一些相关资源:

Lab 1: Unix utilities

主题：熟悉 xv6 及其系统调用。

Boot xv6

这部分的主要内容就是完成实验环境的配置，可以参考课程主页的lab tools page完成相关配置。

sleep

要求：实现 xv6 的 UNIX 程序 sleep ；你的 sleep 应该暂停用户指定的 tick 数。一个 tick 是由 xv6 内核定义的时间概念，即计时器芯片两次中断之间的时间。你的解决方案应在文件 user/sleep.c 中。

重点关注hint中指出的几个文件： user/user.h、user/usys.S、kernel/sysproc.c

首先我们需要明白当实现一个用户程序但需要系统调用时，用户程序是不能直接调用内核函数的。用户态和内核态是隔离的，用户程序想要请求内核服务，必须通过ecall陷入内核。所以每个系统调用都需要一个用户态可见的“函数”，从而让C代码可以像普通函数一样调用。

这个“函数“就是stubs（系统调用桩），放在usys.S内，它本身不是内核代码，而是用户程序调用系统调用时进入内核的入口。

在user.h中有：

1

int sleep(int)

这是一个函数声明，调用它时，参数按照RISC-V调用约定放到a0,返回值也从a0取。

而usys.S中：

1
2
3
4

sleep:
 li a7, SYS_sleep # 把系统调用号 SYS_sleep放入a7
 ecall # 环境调用指令，让用户态陷入内核态，此时CPU会跳到内核的异常入口，最终进入usertrap()
 ret # 返回到调用sleep的C代码

就是这个函数的定义，二者之间的关系可以理解为：user.h声明接口，让用户C代码能编译通过；usys.S提供符号sleep，让链接器能找到实现，SYS_sleep系统调用号对应的内核处理函数就在kernel/sysproc.c中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

uint64
sys_sleep(void)
{
  int n;	//用户设置的中断数
  uint ticks0;

  if(argint(0, &n) < 0)	//从 trapframe->a0 取出 n
    return -1;

  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(myproc()->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);
  return 0;
}

整个完整的调用链就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

用户 C 代码：
  sleep(10);

usys.S：
  li a7, SYS_sleep     # a7 = 13
  ecall                # 陷入内核，a0 = 10

内核 usertrap/syscall：
  num = p->trapframe->a7      # num = SYS_sleep = 13
  syscalls[num]()             # syscalls[13] == sys_sleep
  -> 调用 sys_sleep()

sys_sleep()：
  argint(0, &n)               # 从 trapframe->a0 取出 10
  ...


syscall()：
  p->trapframe->a0 = 返回值
  sret 返回用户态

usys.S：
  从 ecall 后面继续执行
  ret 返回 C 调用者

所以最终实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

int main(int argc, char *argv[]) {
    if (argc != 2) {	//必须为2个参数
        fprintf(2, "usage: sleep [ticks num]\n");
        exit(1);
    }

    uint n = atoi(argv[1]);	//将字符串转换为整型
    int ret = sleep(n);		
    exit(ret);
}

pingpong

要求：编写一个程序，使用 UNIX 系统调用在两个进程之间通过一对管道（一个用于每个方向）传递一个字节。父进程应向子进程发送一个字节；子进程应打印<pid>: received ping，其中是其进程 ID，将字节写入管道给父进程，然后退出；父进程应从子进程读取字节，打印<pid>: received pong，然后退出。您的解决方案应保存在 user/pingpong.c 文件中。

这里需要注意的点是管道是单向的，半双工的，一个管道只能固定一个方向传输数据，如果父子进程要互相发送数据，就需要两个方向各一个管道:

  • p2c：parent → child，父进程写，子进程读；
  • c2p：child → parent，子进程写，父进程读。

最终实现为：

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

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

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

    int p2c[2]; // parent->child
    int c2p[2]; // child -> parent
    pipe(p2c);
    pipe(c2p);

    if(fork() == 0) {	//子进程
        close(p2c[1]);	
        close(c2p[0]);	

        char buf[1];
        int n = read(p2c[0], buf, sizeof(buf));

        if(n > 0) {
            fprintf(1, "%d: received ping\n", getpid());
            close(p2c[0]); 
            write(c2p[1], buf, sizeof(buf));
            close(c2p[1]);
            exit(0);
        } 
        exit(1);
    } else {
        close(p2c[0]);
        close(c2p[1]);

        char buf[1] = {'a'};
        write(p2c[1], buf, sizeof(buf));
        close(p2c[1]);
        int n = read(c2p[0], buf, sizeof(buf));
        if(n > 0) {
            fprintf(1, "%d: received pong\n", getpid());
        }
        close(c2p[0]);
        wait(0);
        exit(n > 0 ? 0: 1);
    }
}

primes

要求：使用管道编写一个并发质数筛。你的目标是使用 pipe 和 fork 来设置管道。第一个进程将数字 2 到 35 输入到管道中。对于每个质数，你需要安排创建一个进程，该进程从其左边的邻居通过管道读取，并向其右边的邻居通过另一个管道写入。由于 xv6 的文件描述符和进程数量有限，第一个进程可以在 35 处停止。你的解决方案应保存在文件 user/primes.c 中。

这里需要注意的点是：主进程只负责产生2-35的数字，每个素数由对应的那个进程筛选，而且每个进程只负责一个素数。

整体流程为：

  1. 第一个进程（主进程）：把 2 到 35 全部写进管道。
  2. 第二个进程：从管道读。它读到的第一个数一定是素数，打印 prime 2。然后继续读剩下的数，把不能被 2 整除的数写到下一个管道。
  3. 第三个进程：从第二个管道读。它读到的第一个数是 3，打印 prime 3。然后继续读，把不能被 3 整除的数写到下一个管道。
  4. 第四个进程：读到的第一个数是 5，打印 prime 5，把不能被 5 整除的数传下去。
  5. 以此类推，直到某个进程读不到任何数（管道写端关闭，read 返回 0），它就直接退出，不再创建下一个进程。

最终实现为：

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

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

void primes(int p) {
    int buf;
    if(read(p, &buf, sizeof(buf)) == 0) {
        close(p);
        exit(0);
    }

    fprintf(1, "prime %d\n", buf);

    int pp[2];
    pipe(pp);

    if(fork() == 0) {
        close(pp[1]);
        close(p);
        primes(pp[0]);
    } else {
        close(pp[0]);
        int num;
        while(read(p, &num, sizeof(num)) > 0) {
            if(num % buf != 0) {
                write(pp[1], &num, sizeof(num));
            }
        }
        close(p);
        close(pp[1]);
        wait(0);
        exit(0);
    }
}

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

    int p[2];
    pipe(p);

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

find

要求：编写一个简单版的 UNIX find 程序：在目录树中查找所有具有特定名称的文件。你的解决方案应放在文件 user/find.c 中。

这里可以参考user/ls.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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

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

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), ' ', DIRSIZ-strlen(p));
  return buf;
}

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

  // path -> fd -> st

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

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

  switch(st.type){
  case T_FILE:
    printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size);
    break;

  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("ls: path too long\n");
      break;
    }
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';
    // 目录在磁盘中就是一个普通文件，它的数据块存放着连续的目录项
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      //跳过空的目录项，删除一个文件时，把对应的inum改为0.
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);
      //如果文件名长度正好等于DIRSIZ，那么de.name里没有\0，所以补充\0，保证p指向的是一段合法的字符串
      p[DIRSIZ] = 0;
      //获取子项文件信息
      if(stat(buf, &st) < 0){
        printf("ls: cannot stat %s\n", buf);
        continue;
      }
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}

int
main(int argc, char *argv[])
{
  int i;

  if(argc < 2){
    ls(".");
    exit(0);
  }
  for(i=1; i<argc; i++)
    ls(argv[i]);
  exit(0);
}

最终实现为：

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

char* extract(char* file) { //提取文件名
    char* p = file + strlen(file); //'\0'
    while(p > file && *p != '/') {
        p--;
    }
    if(*p == '/') return p + 1;
    return file;
}

void find(char* path, char* file) {
    int fd = open(path, 0);
    struct dirent de;
    struct stat st;
    char buf[512], *p;
    if(fd < 0) {
        fprintf(2, "cannot open %s\n", path);
        return;
    }

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

    switch (st.type) {
    case T_FILE:    //如果恰好是需要的文件，直接打印
        if(strcmp(extract(path), file) == 0) {
            printf("%s\n", path);
        }
        close(fd);
        break;

    case T_DIR:
        strcpy(buf, path);
        p = buf + strlen(buf);
        *p++ = '/';
        while (read(fd, &de, sizeof(de)) == sizeof(de)) {
            if (de.inum == 0) continue; //被删除的文件，跳过

            char name[DIRSIZ + 1];
            memmove(name, de.name, DIRSIZ);
            name[DIRSIZ] = 0;
            if (strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) //跳过.和..
                continue;

            memmove(p, name, DIRSIZ);
            p[DIRSIZ] = 0;
            find(buf, file); //进入下级目录继续寻找
        }
    break;
    }
    close(fd);
}

int
main(int argc, char *argv[])
{
    if(argc != 3) {
        fprintf(2, "usage: [Dont find path file]\n");
        exit(1);
    }

    find(argv[1], argv[2]);
    exit(0);
}

xargs

要求：编写 UNIX xargs 程序的简单版本：从标准输入读取行，并为每一行运行一个命令，将行作为参数传递给该命令。您的解决方案应保存在文件 user/xargs.c 中。

这个实验需要注意的就是标准输入的数据按行处理，对于每行，以空格和制表符作为分割获取参数，最后和固定参数进行拼接。最后用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
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

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

void run_command(char* command, char** args, int argcount, char* line) {
    char* line_args[MAXARG];
    int line_argc = 0;

    char *p = line;
    while(*p) {
        while(*p == ' ' || *p == '\t')p++; //遍历行，遇到空格或制表符就当作分隔符
        if(*p == 0) break;
        line_args[line_argc++] = p;
        while(*p && *p != ' ') p++;
        if(*p) {
            *p = 0;
            p++;
        }
    }

    if(line_argc == 0) return;

    char *argv[MAXARG];
    int idx = 0;
    argv[idx++] = command;
    for(int i = 0; i < argcount; ++i) {
        if(idx >= MAXARG - 1) break;
        argv[idx++] = args[i];
    }
    for(int i = 0; i < line_argc; ++i) {    //拼接标准输入的参数
        if(idx >= MAXARG - 1) break;
        argv[idx++] = line_args[i];
    }
    argv[idx] = 0;

    if(fork() == 0) {   //fork + exec
        exec(command, argv);
        fprintf(2, "xargs: exec %s failed\n", command);
        exit(1);
    } else {
        wait(0);
    }
}

int main(int argc, char *argv[]) {
    if(argc < 2) {
        fprintf(2, "usage: xargs command [args...]\n");
        exit(1);
    }

    char* command = argv[1];
    char *args[MAXARG];
    int argcount = argc - 2;
    for(int i = 0; i < argcount; ++i) {
        args[i] = argv[i + 2];
    }

    char buf[512];
    char c;
    int n = 0;
    while(read(0, &c, 1) == 1) {  //按行处理
        if(c == '\n') {
            buf[n] = 0;
            run_command(command, args, argcount, buf);
            n = 0;
        } else {
            if(n < sizeof(buf) - 1) {
                buf[n++] = c;
            }
        }
    }

    if(n > 0) { //恰好只有一行
        buf[n] = 0;
        run_command(command, args, argcount, buf);
    }
    exit(0);
}
项目
操作系统 xv6
本文由作者按照 CC BY 4.0 进行授权