MIT 6.S081 Lab1: Xv6 and Unix utilities

Posted on Edited on In

1. sleep

1.1 描述

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

可以了解一下atoi的简单实现，参考一下user文件中的其他命令的实现。

1.2 实现

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

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

  int i = atoi(argv[1]);
  sleep(i);
  exit(0);
}

2. pingpong

2.1 描述

Write a program that uses UNIX system calls to ‘’ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “: received ping”, where is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “: received pong”, and exit. Your solution should be in the file user/pingpong.c.

需要熟悉fork、write、read、pipe等系统调用的使用，来实现父进程与子进程之间的通过管道的数据传输，应用在xv6中的实现的一组库函数(在user/user.h中)来实现本例。

2.2 实现

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

char buf[1];

int
main(int argc, char* argv[]) {
  int p[2];
  pipe(p);
  int pid = fork();
  if (pid > 0) {  // parent
    close(p[0]);
    if (write(p[1], buf, sizeof(buf)) > 0) {
      wait(0);
      printf("%d: received pong\n", getpid());
    } else {
      return 0;
    }
    close(p[1]);
  } else if (pid == 0) {  // child
    close(p[1]);
    if (read(p[0], buf, sizeof(buf)) > 0) {
      printf("%d: received ping\n", getpid());
    } else {
      return 0;
    }
    close(p[0]);
  } else {  // error
    fprintf(2, "error\n");
    exit(1);
  }
  exit(0);
}

3. primes

3.1 描述

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

应用埃氏筛法实现对素数的筛选，下面给出的是迭代实现，注意利用该条件终止迭代*Hint: read returns zero when the write-side of a pipe is closed.*。每次迭代创建一个管道，父进程通过将原始数据写管道，子进程在读阶段将数据中非素数筛出并保留筛出数据到缓冲区供下次传递使用，并打印数据

3.2 实现

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

int
main(int argc, char* argv[]) {
  int p[2];
  int buf[36];
  int pid = 0;
  // initialize.
  int index = 0;
  for (int i = 2; i <= 35; ++i) {
    buf[index++] = i;
  }
  // use the sieve function 埃氏筛法
  while (index > 0) {
    pipe(p);  // Create pipe every valid loop.
    if ((pid = fork()) == 0) {     // child
      // sieve operation.
      int prime = 0;
      int index = -1;
      int temp = 0;
      close(p[1]);
      while (read(p[0], &temp, sizeof(temp)) != 0) {
        // handle to sieve prime numbers.
        if (index < 0) {
          prime = temp;
          index++;
        } else {
          if (temp % prime != 0) buf[index++] = temp;
        }
      }
      printf("prime %d\n", prime);
      close(p[0]);
    } else if (pid > 0) {  // parent
      close(p[0]);
      for (int i = 0; i < index; ++i) {
        write(p[1], &buf[i], sizeof(buf[i]);
      }
      close(p[1]);
      wait(0);   // main process is waiting all child processes to quit.
      exit(0); 
    } else {
      fprintf(2, "fork failure.\n");
      exit(1);
    }
  }
  exit(0);
}

4. find

4.1 描述

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

参考user/ls.c文件了解如何读取目录，其实实现是类似的，只不过find命令需要实现递归。

4.2 实现

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

/**
 * @brief transmit the complete filename path to the filename eradicated dir.
 * 
 * @param path complete filename path.
 * @return return the filename eradicated part behind the last slash "/".
 */
char*
fmtname(char* path) {
  static char buf[DIRSIZ+1];  // +1表示buf最后一个字符为字符串结束符
  char* p;
  
  // 从后向前遍历找到最底层的文件/目录名
  for (p = path+strlen(path); p >= path && *p != '/'; p--);
  p++;  // 跳过slash指向最底层文件/目录名称的第一个字符

  // 对这个名称进行处理，如果大于最大的目录名称则直接返回该名称；小于则进行空字符的填充
  if (strlen(p) >= DIRSIZ)
    return p;
  // 将改名称写入buf中
  memmove(buf, p, strlen(p));
  /* fill the white space into the rest of the DIRSIZ that
   * guarantee the correctness of strcmp func.
  */
  // DIRSIZ为目录名称的最大长度(14个字符)，目录名称的长度小于14那么就填充对应的' '字符，
  // 来保证在能够在strcmp中两个比较的目录名称都是14个字符
  memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
  buf[strlen(p)] = 0;   // 字符串结束符，数组下标由0开始，也就是在该名称后面加上字符串结束符
  return buf;
}

void
find(char* path, char* name) {
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;  // 文件状态结构体

  if ((fd = open(path, 0)) < 0) {  // open系统调用通过文件路径获取文件描述符
    fprintf(2, "find: cannot open %s\n", path);
    return;
  }

  if (fstat(fd, &st) < 0) {   // 将文件描述符对应的stat结构返回到st参数中
    fprintf(2, "find: cannot open %s\n", path);
    close(fd);
    return;
  }

  switch (st.type)  // 记录文件的类型，st.type的类型为short。xv6用分别用三个宏表示文件类型，依次从1开始(T_DIR, T_FILE, T_DEVICE)
  {
  case T_FILE:
    if (!strcmp(name, fmtname(path)))  // 如果相等strcmp返回0
      printf("%s\n", path);
    break;
  
  case T_DIR: 
    // 个人感觉两个+1都指的是slash占位符
    if (strlen(path)+1+DIRSIZ+1 > sizeof(buf)) {
      printf("find: path too long\n");
      break;
    }

    /* buf store the complete path and hold the buf pointer in front of it that
     * is convenient to print the complete path which we expect to output.
    */
    strcpy(buf, path);
    p = buf + strlen(buf);  // 将p指向buf的最后一个字符
    *p++ = '/';   // i.e. *(p++) = '/'(优先级从右向左).
    while (read(fd, &de, sizeof(de)) == sizeof(de)) {  // 读取文件的目录结构到de结构体(实际上fstat也大概是这么实现的，注意到这两个结构体都是满足字节对齐的)
      if (de.inum == 0)             // inum为当前目录下子目录的个数，如果为0就没必要往下找了
        continue;
      memmove(p, de.name, DIRSIZ);  // 将目录名称移动到p指向的区域
      p[DIRSIZ] = 0;                // 字符串结束符
      if (!strcmp(de.name, ".") || !strcmp(de.name, "..")) {  // 如果是上一级目录或者是当前目录则continue
        continue;
      }
      find(buf, name);  // recursive.
    }
    break;
  }
  close(fd);
}

int
main(int argc, char** argv) {
  if (argc < 3) {
    fprintf(2, "usage: find path name...\n");
    return 0;
  }
  for (int i = 2; i < argc; ++i) {
    find(argv[1], argv[i]);
  }
  exit(0);
}

5. xargs

5.1 描述

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

需要去了解linux中xargs命令的实现，需要注意的是argv提取的是由xargs之后的参数(运行的是xargs程序)，从管道中提取数据作为xargs后面命令的参数。通过read从标准输入读数据，将其中的’\n’和’ ‘参数分隔符用字符串结束符替代，并添加在参数列表的后面，由exec系统调用执行。xargs - build and execute command lines from standard input，完成了用标准输入的内容作为xargs的参数

5.2 实现

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

#define MAXLINE 1024

int
main(int argc, char** argv) {
  if (argc > MAXARG) {
    fprintf(2, "xargs: arg is too much\n");
    return 0;
  }
  char* param[MAXARG];
  char line[MAXLINE];  // 读缓冲区

  int pid;
  int n;
  int arg_param = 0;
  char* cmd = argv[1];  // xargs后面跟的命令
  for (int i = 1; i < argc; ++i)
    param[arg_param++] = argv[i];  // xargs后的参数放在参数列表的前面随后跟着管道前的标准输入提取的参数
  if ((pid=fork()) > 0) {   // parent.
    wait(0);
  } else if (pid == 0) {    // child.
    int index = 0;  // 读缓冲区的索引
    char* arg = (char*)malloc(sizeof(char));  // 暂存读到的参数
    // 从标准输入(fd为0)中(管道前执行的命令)提取行，并为每一行运行一个命令，将"该行作为参数"提供给xargs后的命令
    while((n = read(0, line, MAXLINE)) > 0) {
      for (int i = 0; i < n; ++i) {
        if (line[i] == ' ' || line[i] == '\n') {
          arg[index] = 0;  // '\0' 换为字符串结束符，方便提取
          printf("%s\n", arg);
          index = 0;
          param[arg_param++] = arg;  // 放入参数列表中
          arg = (char*)malloc(sizeof(char));  // 再初始化暂存的参数或者命令的区域
        } else {
          arg[index++] = line[i];  // 继续遍历读缓冲区的护具
        }
      }
      exec(cmd, param);  // 将每一个标准输入行中的参数提供给xargs后的命令作为参数
    }
  } else {
    fprintf(2, "fork error\n");
    exit(1);
  }
  exit(0);
}

总结

通过完成lab1中xv6相应的命令函数的实现，以及相关代码的阅读，加深了了我对linux部分命令实现原理的理解，同时也熟悉了基本的系统调用函数。