XV6 Lab 1: Xv6 and Unix utilities

本章节的实验是为了熟悉 XV6 环境和 interface 而准备的。包含了 interface 调用、多进程编程、Pipeline。

阅读 book-riscv-ref3 熟悉 XV6 的系统组织形式

sleep

通过调用 user.h 中的系统调用函数来完成 sleep 程序。主要是为了介绍系统调用的工作方式。

/**
 * @author chenghua.wang
 * @brief Lab1-utilities. sleep prog using syscall.
 * @time Feb 23, 2023
 * */

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

int
main(int argc, char *argv[]){
  if (argc != 2){
    printf("[ error ] you should follow anw integer with sleep prog to indicate ticks times!\n");
    exit(1); // failure
  }
  sleep(atoi(argv[1])); // sys call provided by user.h
  exit(0); // success
}

下面以 sleep(int) 系统调用来阐述 XV6 中调用的流程。sleep 函数在 user/user.h 中声明，具体的函数定义则通过其他模块的动态连接最终合成可执行文件 _sleep.

在 user/usys.S 中 sleep 调用的汇编代码是这样的:

.global sleep
 sleep:
  li a7, SYS_sleep
  ecall
  ret

这里的 sleep 就是上面那个 sleep 函数的定义，就是说执行 sleep 时，就是执行这段汇编代码。可以看到在用户空间 sleep 函数的任务就是将 SYS_sleep 放入 a7 中，然后中断。SYS_sleep 在 kernel/syscall.h 中宏定义为一个系统调用号。可以看到这个 usys.S 文件也包含了这个头文件。

// kernel/syscall.h
#define SYS_sleep  13

接下来在 kernel/syscall.c 中，可以看到 SYS_sleep 转换为了对应的 sys_sleep:

// kernel/syscall.c
// An array mapping syscall numbers from syscall.h
// to the function that handles the system call.
static uint64 (*syscalls[])(void) = {
[SYS_fork]    sys_fork,
[SYS_exit]    sys_exit,
[SYS_wait]    sys_wait,
[SYS_pipe]    sys_pipe,
[SYS_read]    sys_read,
[SYS_kill]    sys_kill,
[SYS_exec]    sys_exec,
[SYS_fstat]   sys_fstat,
[SYS_chdir]   sys_chdir,
[SYS_dup]     sys_dup,
[SYS_getpid]  sys_getpid,
[SYS_sbrk]    sys_sbrk,
[SYS_sleep]   sys_sleep,
[SYS_uptime]  sys_uptime,
[SYS_open]    sys_open,
[SYS_write]   sys_write,
[SYS_mknod]   sys_mknod,
[SYS_unlink]  sys_unlink,
[SYS_link]    sys_link,
[SYS_mkdir]   sys_mkdir,
[SYS_close]   sys_close,
};

pingpong

使用 pipe 进行父进程和子进程之间的调用。注意管道 0, 1 的关闭。

/**
 * @author chenghua.wang
 * @brief Lab-1-utilities pingpong. Using the pipe syscall.
 * */

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

char* buf[8];

int
main() {
  int p[2];
  pipe(p); // using syscall to create pipe.

  // 1. child
  if (fork() == 0){
    int id = getpid();
    read(p[0], buf, 1);
    close(p[0]);

    printf("%d: received ping\n", id);

    write(p[1], "c", 1);
    close(p[1]);
  } else { // 2. parent
    int id = getpid();
    write(p[1], "p", 1);
    close(p[1]);

    wait(0);

    read(p[0], buf, 1);
    close(p[0]);
    printf("%d: received pong\n", id);
  }
  exit(0);
}

prime

通过管道作为不同进程之间通信的渠道来进行多进程求解素数，实现素数筛。这里因为 XV6 的限制只能开 34 个进程。

算法的具体流程非常的简单:

有管道 p_{0} 把数据(2->35)全都填入
p_{0} 右端连接一个进程，这个进程筛去 p_{0} 中 %2==0的，将剩下的数传递给 p_{1} 管道。
以此类推。

只需要注意两次管道的关闭就好了。

/**
 * @author chenghua.wang
 * @brief using concurrency to get primes.
 * @time Feb 23, 2023
 * */

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

int child(int previous_pipe[2]) {
  int child_pipe[2];
  int prime;
  close(previous_pipe[1]); // child do not need write data to previous pipe.
  int len = read(previous_pipe[0], &prime, 1);
  if (!len) {
    close(previous_pipe[0]); // no data need to read anymore.
    exit(0); // success.
  }
  pipe(child_pipe);
  printf("prime %d\n", prime);
  int num;
  if (fork() == 0) {
    close(previous_pipe[0]);
    child(child_pipe);
  } else {
    close(child_pipe[0]);
    while(1) {
      int len = read(previous_pipe[0], &num, 1);
      if (len == 0) break;
      if (num % prime != 0) {
        write(child_pipe[1], &num, 1);
      }
    }
    close(child_pipe[1]);
    close(previous_pipe[0]);
    wait(0);
  }
  exit(0); // success
}

int
main() {
  int parent_pipe[2];
  pipe(parent_pipe);

  if (fork() == 0) {
    child(parent_pipe);
  } else {
    close(parent_pipe[0]); // parent do not need to read data.
    for (int i = 2; i < 36; ++i) {
      write(parent_pipe[1], &i, sizeof(int));
    }
    close(parent_pipe[1]); // parent do not need to write anymore.
    wait(0); // wait for child process done.
  }

  exit(0);
}

find

基本上就是 XV6 中 ls 程序的改版。只不过判断是文件夹的话要递归。

/**
 * @author chenghua.wang
 * @brief Lab1-utilities find
 * @time Feb 23, 2023
 * */

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h" // for file system. DIRSIZ, etc.

char* fmtname(char *path) {
  char *p;
  for (p = path + strlen(path); p >= path && *p != '/'; --p);
  p++;
  return p;
}

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

  // open file.
  if ((fd = open(directory, 0)) < 0) {
    fprintf(2, "find: cannot open %s\n", directory);
    return;
  }

  // get the state of this file
  if (fstat(fd, &st) < 0) {
    fprintf(2, "find: cannot get stat of %s\n", directory);
    close(fd);
    return;
  }
  // find the correct type need to check.
  // 1. path-> find if file_name is same.
  // 2. directory-> run find func again.
  // 3. others('.', '..')-> skip.
  switch(st.type) {
    case T_DEVICE:
    case T_FILE:
      if (strcmp(file_name, fmtname(directory)) == 0) {
        printf("%s\n", directory);
      }
      break;
    case T_DIR:
      strcpy(buf, directory);
      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;
        memmove(p, de.name, DIRSIZ);
        p[DIRSIZ] = 0;
        find(buf, file_name);
      }
      break;
  }
  close(fd);
}

int
main(int argc, char *argv[]) {
  if (argc != 3) {
    printf("[ error ] find [directory] ['name']\n");
    exit(1); // failure
  }
  find(argv[1], argv[2]);
  exit(0); // success
}

xargs

我想 XV6 这个实验主要是想考察 exec 的作用。xargs 从标准输入得到数据，然后对每一行数据重新填入 argv 再执行。

/**
 * @author chenghua.wang
 * @brief Lab1-utilities xargs.
 * @time Feb 23, 2023
 * */

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

char buf[512];

int
main(int argc, char *argv[]) {
  char *pass_argv[64];
  for (int i = 0; i < argc; ++i) {
    pass_argv[i] = argv[i + 1]; // the terminate 0 is also moved.
  }
  for (;;) {
    // to read a line
    int i = 0;
    for(;;++i) {
      int len = read(0, &buf[i], 1); // read from stdin.
      if (len == 0 || buf[i] == '\n') break;
    }
    if (i == 0) break;
    // exec a line
    buf[i] = 0;
    pass_argv[argc - 1] = buf;
    if (fork() == 0) {
      exec(pass_argv[0], pass_argv);
      exit(0); // success
    } else {
      wait(0);
    }
  }
  exit(0); // success
}

sleep#

pingpong#

prime#

find#

xargs#

sleep

pingpong

prime

find

xargs