6.s081/6.1810（Fall 2022）Lab1:Utilities_6.1810 lab

前言

这个Lab就是个热身Lab，跟着走吧~

其他篇章

环境搭建
Lab1: Utilities
Lab2: System calls
Lab3: Page tables
Lab4: Traps
Lab5: Copy-on-Write Fork for xv6

参考链接

官网链接
xv6手册链接，这个挺重要的，建议做lab之前最好读一读。
xv6手册中文版，这是几位先辈们的辛勤奉献来的呀！再习惯英文文档阅读我还是更喜欢中文一点，开源无敌！
个人代码仓库
官方文档
友情提示：建议看完xv6 book第一章再开始做

1. Boot xv6 (easy)

这个就是安装xv6，前面环境搭建篇章已经写过了，不赘述。只说一点，我们可以在xv6的目录里使用make grade进行评测。

2. sleep (easy)

这是本lab的第一个代码！也是给你熟悉一下环境的，在这个lab中，我们很多C语言库函数是调用不了的，我们能调用的函数都在user/user.h里给你列好了，其中包含20个system call和14个库函数，我们就需要通过这些东西去写我们的代码。（友情提醒：sleep这个函数是给用户调用的，我们同样要写在user文件夹里）

看图写话，从xv6 book可以知道，2代表标准错误流，所以我们给fprintf传入2

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

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

  sleep(atoi(argv[1]));
  exit(0);
}
1
2
3
4
5
6
7
8
9
10
11
12

顺便说一句，fprintf不能打印中文= =，我的国产化OS梦泡汤啦（

然后由于我们新写了一个sleep.c，要在Makefile里加上一行$U/_sleep\

本地推送，WSL拉取，然后make qemu，可以看到成功运行，我们试一下我们写的sleep，可以看到单输一个sleep报错了。

可以多试一试，比如说输个sleep 50，会发现大概卡了5s

然后退出来，输入命令评测

./grade-lab-util sleep
1

官方还提供了一个测试命令make GRADEFLAGS=sleep grade也可以测试，说是效果一样，不过我试了一下这玩意要打印一大堆东西，不如上面那个。

3. pingpong (easy)

这个题的要求是通过管道（pipe）在父子进程间传输一个byte，并打印信息和pid，父进程传过去，子进程传回来，所以叫“pingpong”。

文档给了几个tips，告诉我们可以用这几个system call来完成，下面简单介绍一下这几个东西

首先是fork，fork用于创建子进程，它有一个返回值，对于父进程返回子进程的PID，子进程则返回0，我们可以通过这个去区别父进程与子进程，其中可以通过exit终结本进程，在父进程中可以使用wait去保证之后的代码是在子进程之后执行的。因此可以搭这样一个框架：

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

int main(int argc, char* argv[])
{
  int pid = fork();
  if (!pid) 
  {
    // 子进程
  }
  else if (pid > 0)
  {
    // 父进程
  }
  else
  {
    // fork失败
  }

  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

但是值得注意的一点是父进程与子进程拥有不同的内存空间和寄存器，改变一个进程中的变量不会影响另一个进程，这就意味着父子进程间的通信不能单单靠变量完成，于是就引入了我们的管道（pipe）

先介绍一下管道

管道是一个小的内核缓冲区，它以文件描述符对的形式提供给进程，一个用于写操作，一个用于读操作。从管道的一端写的数据可以从管道的另一端读取。管道提供了一种进程间交互的方式。

事实上，pipe相当于额外打开了一个文件，它依托于内核，所以父子进程都能访问它（一个不太恰当的比喻是，把父子进程想象成C语言的各个函数，而pipe是静态区的变量），以此进行进程间通信。具体到xv6实现，pipe函数接受一个长度为2的数组（指针），一个用于读，一个用于写，通过这个我们就可以实现进程通信了，由于pipe是半双工的，即不能同时执行读与写，因此我们想要实现“pingpong”，需要两个pipe

...
  // 创建两个管道
  int p[2][2];
  pipe(p[0]), pipe(p[1]);
...
1
2
3
4
5

创建完管道，我们就去看一下怎么通过write和read去读写管道。先看一下这两个system call吧：

int write(int fd, const void* buf, int n);
int read(int fd, void* buf, int n);
1
2

read(fd, buf, n): 从 fd 读最多 n 个字节（fd 可能没有 n 个字节），将它们拷贝到 buf 中，然后返回读出的字节数，当没有数据可读时，read 就会返回0，这就表示文件结束了
write(fd, buf, n): 写 buf 中的 n 个字节到 fd 并且返回实际写出的字节数。如果返回值小于 n 那么只可能是发生了错误

值得注意的一点是，pipe在读写时都会阻塞，因此我们在读写一端的时候都需要去关闭另一端。
搞清楚这几点写起来就比较容易了（getpid应该不用说了）：

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

int main(int argc, char* argv[])
{
  // 创建两个管道
  int p[2][2];
  pipe(p[0]), pipe(p[1]);

  // 传输用字节
  char buf[] = { 'a' };

  // 创建子进程
  int pid = fork();
  if (!pid) 
  {
    // 子进程
    // 关闭写端
    close(p[0][1]);
    if (read(p[0][0], buf, 1) > 0)
    {
      printf("%d: received ping\n", getpid());
    }
    else     
    {
      printf("%d: read error\n", getpid());
    }
    // 关闭读端
    close(p[1][0]);
    write(p[1][1], buf, 1);
    exit(0);
  }
  else if (pid > 0)
  {
    // 父进程
    // 关闭读端
    close(p[0][0]);
    write(p[0][1], buf, 1);

    wait(0);
    // 关闭写端
    close(p[1][1]);
    if (read(p[1][0], buf, 1) > 0)
    {
      printf("%d: received pong\n", getpid());
    }
    else
    {
      printf("%d: read error\n", getpid());
    }
  }
  else
  {
    // fork失败
    printf("fork error\n");
  }
  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

同样的，我们在UPROGS中加入$U/_pingpong\：

测试一下：

一样的，退出来用./grade-lab-util pingpong测一下，搞定！

4. primes (moderate)/(hard)

这是是第一个不是easy的题，不过其实也挺easy的。

先放要求，这个题要求使用pipe实现一个素数筛（埃氏筛，之前写过一个C语言/C++版本）筛得35以下的素数，实现方法可以看一下这篇论文。

埃氏筛是一种很朴素的素数筛法，大家应该也都知道，这里简单介绍一下：首先我们确定一个素数，然后我们遍历一串连续的数，每次拿到素数时，划去所有它的倍数，以此类推，直到到达设置的阈值。

//埃拉托斯特尼筛法-优化
void eratosthenes_opt(void) {
	bool* prime = (bool*)calloc((NUM + 5), sizeof(bool));
	memset(prime + 2, true, NUM + 3);

	unsigned tmp = sqrt(NUM);
	for (size_t i = 2; i <= tmp; i++)
		if (prime[i])
			for (size_t mutiple = i * i; mutiple <= NUM; prime[mutiple] = false, mutiple += i);

	/*for (size_t i = 0; i <= NUM; i++)
		if (prime[i])
			printf("%ud ", n);*/

	if (prime != NULL) {
		free(prime);
		prime = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

那么筛法和多线程、或者说这里的fork与pipe有什么关系呢？我们借用上面那篇paper中的一张图可以简单解释一下：

大概实际是这样一个流程：

• 根进程（也就是第一个父进程）将[2, 35]的整数写入pipe的写端，fork出一个子进程
• 每一个子进程都从父进程（也就是所谓的left neighbor）的pipe读端读取数据，其中第一个数据必为素数（因为它接受了所有它之前的数的试除），以这个数为基准筛除所有它的倍数，将剩下的数写入pipe的写端，fork出子进程
• 重复第二步直到新进程无数可读，意味着所有数都被筛干净了，筛法完成，循环结束

这是一个很巧妙、很清晰的想法，搞清楚这一点后实现起来就比较简单了，只是这里有一个小tip，同时也在要求中提到了，那就是xv6（实际上是所有OS，只是xv6在这更突出）的文件描述符是有限的，而我们知道我们的每一个pipe都会绑定有文件描述符，因此我们要做好资源管理，将不用的管道关闭掉，比如说我们知道某个进程只需要读端，就要先关闭写端、并在读完后关闭读端，此外由于这个代码相对前几个较大，我在此处采用了一些宏定义增强了可读性，并处理了一些错误，下面给出代码：

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

#define primeMax  35
#define stdin     0
#define stdout    1
#define stderr    2
#define pipeRead  0
#define pipeWrite 1

void primeFunc(int left[2])
{
  int prime, n;
  close(left[pipeWrite]);
  if (!read(left[pipeRead], &prime, sizeof(prime)))
  { // 读取失败，筛法结束，递归出口
    close(left[pipeRead]);
    exit(0);
  }

  printf("prime %d\n", prime);
  int right[2], pid;
  if (pipe(right) < 0)
  {
    write(stderr, "pipe failed\n", 12);
    exit(-1);
  }

  if ((pid = fork()) < 0)
  {
    write(stderr, "fork failed\n", 12);
    close(right[pipeRead]);
    close(right[pipeWrite]);
    close(left[pipeRead]);
    exit(-1);
  }
  else if (!pid)
  { // 父进程
    close(right[pipeRead]);
    while (read(left[pipeRead], &n, sizeof(n)))
    {
      if (n % prime)
      { // 非倍数，写入pipe
        write(right[pipeWrite], &n, sizeof(n));
      }
    }
    close(left[pipeRead]);
    close(right[pipeWrite]);

    wait(0);
    exit(0);
  }
  else
  { // 子进程
    primeFunc(right);
    exit(0);
  }
}

int main(int argc, char* argv[])
{
  int p[2], pid;
  if (pipe(p) < 0)
  {
    write(stderr, "pipe failed\n", 12);
    exit(-1);
  }

  if ((pid = fork()) < 0)
  {
    write(stderr, "fork failed\n", 12);
    exit(-1);
  }
  else if (!pid)
  { // 根进程将2 - 35写入pipe
    close(p[pipeRead]);
    for (int i = 2; i <= primeMax; i++)
    {
      write(p[pipeWrite], &i, sizeof(i));
    }
    close(p[pipeWrite]);

    wait(0);
    exit(0);
  }
  else
  {
    primeFunc(p);
    exit(0);
  }

  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
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

修改makefile之类的操作我就不写在这了，都是一样的，编译运行一下，结果很完美：

./grade-lab-util primes测试，通过，收工！（吐槽一下CSDN，我编辑这一节的时候本来是写了很多，然后再去跑编译测试的，没想到跑完回来被浏览器刷新了= =，CSDN就不能给文章编辑给一个自动保存草稿箱吗，醉了）

5. find (moderate)

这个题目要求实现一个find程序，找到文件树中的所有这个名字的文件。在写之前，先简单介绍一下这个find是怎么用的吧，搞清楚需求。

find命令语法格式为:find [path...] [expression]，由于这个题目只用做一个“simple version”，因此可以将path理解为搜索的根目录，expression理解为文件名。

Unix有一句哲理名言，叫作“Everything is a file”（万物皆文件）。而反映到实际就是对于每个对象都有一个文件描述符，那么我们是怎么区别一个对象到底是文件、文件夹，还是别的什么东西的呢？我们可以使用fstat获取一个文件描述符指向的文件的信息，它填充一个名为 stat 的结构体：

#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device

struct stat {
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};
1
2
3
4
5
6
7
8
9
10
11

可以看到，stat实际上是维护了文件的一些元数据，包括大小、inode number以及我们这里所需要的type，通过宏定义我们可以猜测出：type分为三种，分别为Directory、File、Device，我们正是通过这一条来区分对象的实际型别。

至于诸如如何打开文件夹、如何比较文件等等操作，我们可以按照文档中的说法，查看ls.c文件作为参考，实际上，我们最后要做的便是深度优先搜索递归遍历我们给出的path，并逐一进行比较即可，还要注意递归时不要递归到.和..、及时关闭无用的文件描述符！下面给出代码：

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

#define STDIN 0
#define STDOUT 1
#define STDERR 2
#define BUFSIZE 512

char* fmtname(char* path)
{
  char* p;
  // 找到最后一个 / 后面的字符
  for (p = path + strlen(path); p >= path && *p != '/'; p--)
    ;
  return p + 1;
}

/**
 * @brief 在指定路径下查找指定文件
 * 
 * @param path 路径
 * @param filename 文件名
 */
void find(char* path, const char* filename)
{
  char buf[BUFSIZE], * p;
  int fd;
  struct dirent de;
  struct stat st;

  // 尝试打开文件
  if ((fd = open(path, O_RDONLY)) < 0) {
    fprintf(STDERR, "find: cannot open %s\n", path);
    return;
  }

  // 尝试获取文件信息
  if (fstat(fd, &st) < 0) {
    fprintf(STDERR, "find: cannot stat %s\n", path);
    close(fd);
    return;
  }

  switch (st.type) {
  case T_FILE:
    if (strcmp(fmtname(path), filename) == 0) {
      printf("%s\n", path);
    }
    break;
  case T_DIR:
    // 如果路径过长，报错
    if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
      printf("find: path too long\n");
      break;
    }

    // 将路径拷贝到 buf 中
    strcpy(buf, path);
    p = buf + strlen(buf);
    // 在路径后面加上 /
    *p++ = '/';
    // 读取目录下的文件
    while (read(fd, &de, sizeof(de)) == sizeof(de)) {
      // 如果文件不存在，或者是 . 或者是 ..，则跳过
      if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
        continue;
      // 将文件名拷贝到 buf 中
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if (stat(buf, &st) < 0) {
        printf("find: cannot stat %s\n", buf);
        continue;
      }
      find(buf, filename);
    }
    break;
  }
  // 及时关闭文件，避免资源泄露
  close(fd);
}

int main(int argc, char* argv[])
{
  if (argc != 3) {
    fprintf(STDERR, "Usage: find <path> <filename>\n");
    exit(1);
  }
  find(argv[1], argv[2]);
  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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

./grade-lab-util find评测通过，不多解释：

6. xargs (moderate)

然后就是本次的最后一个task——xargs：

首先介绍一下这个xargs是干啥用的——我们知道shell脚本里的管道的作用是将左侧的标准输出作为右侧的标准输入，但是实际上我们上面已经实现过几个用户态的函数了，实际上我们发现使用标准输入传参的时候并不多，我们多是利用的命令行参数传参，这个时候就展现出我们的xargs的作用了——它可以将标准输入转化为命令行参数传入，这就可以结合管道，写出相对功能复杂的脚本了。

因此，我们需要先读取argv[1]~argv[argc - 1]的参数（*argv显然必为xargs），然后处理标准输入中的内容，按题目要求，每一行为一个参数传入，因此我们就采用\n分割，这里也没有啥split之类的东西，就只好手搓了（本来我是想一次性读入然后采用strchr分割的，一直有问题，实在找不到为什么错了索性就单个字符读了55555）。

读取到所有的参数后，我们就需要去调用命令argv[1]，这时可以使用exec系统调用，整体思路都比较简单，代码如下：

/*****************************************************************//**
 * \file   xargs.c
 * \brief  Write a simple version of the UNIX xargs program: its
 *         arguments describe a command to run, it reads lines from
 *         the standard input, and it runs the command for each line,
 *         appending the line to the command's arguments. Your solution
 *         should be in the file user/xargs.c
 *
 * \author JMC
 * \date   July 2023
 *********************************************************************/

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

#define MAX_ARG_LEN 32
#define MAX_ARG_NUM 32
#define STDIN 0
#define STDOUT 1
#define STDERR 2
#define NULL (void*)0



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

  // 读取命令行参数
  char* cmd[MAX_ARG_NUM] = {};
  for (int i = 1; i < argc; i++)
  {
    cmd[i - 1] = argv[i];
  }

  // 读取标准输入
  char buf, arg[MAX_ARG_LEN];
  for (int i = 0; read(STDIN, &buf, 1) > 0; )
  {
    if (buf == '\n')
    {
      // 读取到换行符，将参数传递给命令
      arg[i] = '\0';

      // fork一个子进程执行命令
      int pid = fork();
      if (pid < 0)
      {
        fprintf(STDERR, "fork error\n");
        exit(1);
      }
      else if (pid == 0)
      {
        // 子进程执行命令
        cmd[argc - 1] = arg;
        if (exec(cmd[0], cmd) < 0)
        {
          fprintf(STDERR, "exec error\n");
          exit(1);
        }
      }
      else
      {
        // 父进程等待子进程结束
        wait(NULL);
        i = 0;
      }
    }
    else
    {
      arg[i++] = buf;
    }
  }
  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
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

./grade-lab-util xargs测试，通过

最终测试

然后跑一下最终测试make grade，注意要先在主目录下创建time.txt并写入花费的小时数（比方说6）。

• 没创建time.txt会报错Cannot read time.txt：
  
• 创建了time.txt但没填数字会报错time.txt does not contain a single integer (number of hours spent on the lab)：
  
• 本地测试全部通过截图：
  
  Lab1大功告成！没想到这么简单的一个lab1都花了我老半天时间，5555