MIT 6.828 - 1. Lab 01: Xv6 and Unix utilities

Tags: MIT 6.828

实验总结

  1. 本次实验用时约五个小时，足证我代码能力之退化。
  2. 对于实验三中难懂的 redirect()， twd2 认为可以往 xv6 中加一个 dup2 函数，我表示同意。需要进一步研究 xv6 结构，确定如何添加。

遇到的其他问题包括：

  1. 突然间发现 gcc 不认 uint 类型了。经检查发现用户态程序需要手动 #include "kernel/types.h" ，不然会爆炸。

测试结果：

1
2
3
$ make grade
# ... lines omitted
Score: 100/100

0. 实验准备

实验指导连接

上来直接：

1
2
$ cd xv6-riscv-fall19
$ git checkout util

实验指导简要介绍了如何把 xv6 跑起来（make then make qemu），如何交作业（make handin），如何测试成绩（make grade）。

下面介绍各个子任务如何写。

1. sleep

顾名思义写一个 sleep 例程，休眠一定的 tick 数，tick 的定义是时间中断。

Hints: Look at some of the other programs in user/ to see how you can obtain the command-line arguments passed to a program. If the user forgets to pass an argument, sleep should print an error message. The command-line argument is passed as a string; you can convert it to an integer using atoi (see user/ulib.c). Use the system call sleep (see user/usys.S and kernel/sysproc.c). Make sure main calls exit() in order to exit your program. Add the program to UPROGS in Makefile and compile user programs by typing make fs.img. Look at Kernighan and Ritchie's book The C programming language (second edition) (K&R) to learn about C.

首先 make clean，然后照猫画虎写一下 user/sleep.c：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
  if (argc != 2)
    write(2, "Error message", strlen("Error message"));

  int x = atoi(argv[1]);

  sleep(x);

  exit();
}

按照说明修改 Makefile ，给 UPROG 变量追加一个项目，运行即可。

2. pingpong

如法炮制。

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

int main(int argc, char *argv[]) {
  int parent_fd[2], child_fd[2];
  pipe(parent_fd);
  pipe(child_fd);
  char buf[64];

  if (fork()) {
    // Parent
    write(parent_fd[1], "ping", strlen("ping"));
    read(child_fd[0], buf, 4);
    printf("%d: received %s\n", getpid(), buf);
  } else {
    // Child
    read(parent_fd[0], buf, 4);
    printf("%d: received %s\n", getpid(), buf);
    write(child_fd[1], "pong", strlen("pong"));
  }

  exit();
}

3. primes

照猫画虎。

负责我的课程助教 twd2 认为，redirect(int, int[]) 这个函数有问题，原因在于 xv6 没有 dup2(int, int) ，这个函数是网上抄的。

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

void source() {
  int i;
  for (i = 2; i < 36; i++) {
    write(1, &i, sizeof(i));
  }
}

void cull(int p) {
  int n;
  while (read(0, &n, sizeof(n))) {
    if (n % p != 0) {
      write(1, &n, sizeof(n));
    }
  }
}

void redirect(int k, int pd[]) {
  close(k);
  dup(pd[k]);
  close(pd[0]);
  close(pd[1]);
}

void sink() {
  int pd[2];
  int p;

  if (read(0, &p, sizeof(p))) {
    printf("prime %d\n", p);
    pipe(pd);
    if (fork()) {
      redirect(0, pd);
      sink();
    } else {
      redirect(1, pd);
      cull(p);
    }
  }
}

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

  int pd[2];
  pipe(pd);

  if (fork()) {
    redirect(0, pd);
    sink();
  } else {
    redirect(1, pd);
    source();
  }

  exit();
}

4. find

Bonus 是加 regex 支持，好，抄 user/grep.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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#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;
}

// Regexp matcher from Kernighan & Pike,
// The Practice of Programming, Chapter 9.

int matchhere(char*, char*);
int matchstar(int, char*, char*);

int
match(char *re, char *text)
{
  if(re[0] == '^')
    return matchhere(re+1, text);
  do{  // must look at empty string
    if(matchhere(re, text))
      return 1;
  }while(*text++ != '\0');
  return 0;
}

// matchhere: search for re at beginning of text
int matchhere(char *re, char *text)
{
  if(re[0] == '\0')
    return 1;
  if(re[1] == '*')
    return matchstar(re[0], re+2, text);
  if(re[0] == '$' && re[1] == '\0')
    return *text == '\0';
  if(*text!='\0' && (re[0]=='.' || re[0]==*text))
    return matchhere(re+1, text+1);
  return 0;
}

// matchstar: search for c*re at beginning of text
int matchstar(int c, char *re, char *text)
{
  do{  // a * matches zero or more instances
    if(matchhere(re, text))
      return 1;
  }while(*text!='\0' && (*text++==c || c=='.'));
  return 0;
}

void
find(char *path, char *re)
{
  char buf[512], *p;
  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 stat %s\n", path);
    close(fd);
    return;
  }

  switch(st.type){
  case T_FILE:
    if(match(re, fmtname(path)))
      printf("%s\n", path);
    break;

  case T_DIR:
    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;
      }

      if(strlen(de.name) == 1 && de.name[0] == '.')
        continue;
      if(strlen(de.name) == 2 && de.name[0] == '.' && de.name[1] == '.')
        continue;

      find(buf, re);
    }
    break;
  }
  close(fd);
}


int main(int argc, char *argv[]) {
  if(argc <= 2)
    fprintf(2, "find: not enough params provided");
  find(argv[1], argv[2]);
  
  exit();
}

5. xargs

需要参考 user/sh.c、user/cat.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
#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char *argv[]) {
  char buf2[512];
  char buf[32][32];
  char *pass[32];

  for (int i = 0; i < 32; i++)
    pass[i] = buf[i];

  int i;
  for (i = 1; i < argc; i++)
    strcpy(buf[i - 1], argv[i]);

  int n;
  while ((n = read(0, buf2, sizeof(buf2))) > 0) {
    int pos = argc - 1;
    char *c = buf[pos];
    for (char *p = buf2; *p; p++) {
      if (*p == ' ' || *p == '\n') {
        *c = '\0';
        pos++;
        c = buf[pos];
      } else
        *c++ = *p;
    }
    *c = '\0';
    pos++;
    pass[pos] = 0;

    if (fork()) {
      wait();
    } else
      exec(pass[0], pass);
  }

  if (n < 0) {
    printf("xargs: read error\n");
    exit();
  }

  exit();
}
知识共享许可协议 2000 - 2099 MonKey's Blog | 自豪地采用 Hexo + Pandoc + KaTeX + Highlight.js