Lab: Xv6 and Unix utilities

tags: 6.1810

Setup env

以 mac m1 為例，首先安裝開發者工具
$ xcode-select --install

接著安裝 homebrew，package manager
$ /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"

接著安裝 riscv tool chain

$ brew tap riscv/riscv
$ brew install riscv-gnu-toolchain

安裝完成後，測試

$ riscv64-unknown-elf-gcc --version
riscv64-unknown-elf-gcc (g1ea978e3066-dirty) 12.1.0
Copyright (C) 2022 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Boot xv6

目標是在 qemu 執行 xv6 kernel

首先下載程式碼

$ git clone git://g.csail.mit.edu/xv6-labs-2022
Cloning into 'xv6-labs-2022'...
...

下載後進入 xv6 資料夾
$ cd xv6-labs-2022

確認 branch 是否為 util

$ git status
On branch util
Your branch is up to date with 'origin/util'.

nothing to commit, working tree clean

如果不是的話執行git branch util切換到 util

執行 qemu 模擬器

$ make qemu
riscv64-unknown-elf-gcc    -c -o kernel/entry.o kernel/entry.S
riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie   -c -o kernel/start.o kernel/start.c
...
riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o
riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm
riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym
mkfs/mkfs fs.img README  user/xargstest.sh user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie
nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000
balloc: first 591 blocks have been allocated
balloc: write bitmap block at sector 45
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$

進到 xv6 後，執行 ls ，就算完成了。

$ ls
.              1 1 1024
..             1 1 1024
README         2 2 2227
xargstest.sh   2 3 93
cat            2 4 32864
echo           2 5 31720
forktest       2 6 15856
grep           2 7 36240
init           2 8 32216
kill           2 9 31680
ln             2 10 31504
ls             2 11 34808
mkdir          2 12 31736
rm             2 13 31720
sh             2 14 54168
stressfs       2 15 32608
usertests      2 16 178800
grind          2 17 47528
wc             2 18 33816
zombie         2 19 31080
console        3 20 0

要離開 qemu 的話，先按 ctrl+a，再按 x，就可以離開。

sleep

撰寫一個呼叫 sys_sleep 的程式

根據提示，先參考 user/echo.c 瞭解如何取得 command-line 參數，

# user/echo.c
int
main(int argc, char *argv[])
{
  int i;

  for(i = 1; i < argc; i++){
    write(1, argv[i], strlen(argv[i]));
    if(i + 1 < argc){
      write(1, " ", 1);
    } else {
      write(1, "\n", 1);
    }
  }
  exit(0);
}

argc 是參數數量。如果沒有帶入參數的話是1。
argv 是一個 array of pointer，指向字串，c 語言的字串為一段連續的記憶體，型態為 char，結尾是 \0。當把 char[] 當作參數傳遞時，char[] 與 char *是等價的。

於是 sleep.c 可以寫為

# sleep.c

int
main(int argc, char *argv[])
{
    if (argc != 2) {
        printf("Use ./sleep second.\n");
        exit(1);
    }
}

接著透過 atoi 將參數轉換成 integer.

# sleep.c

int
main(int argc, char *argv[])
{
    if (argc != 2) {
        printf("Use ./sleep second.\n");
        exit(1);
    }
    int n = atoi(argv[1]);
}

下一步是呼叫 sys_sleep，
參考 user.h 可以知道 sys_sleep 的 prototype 為int sleep(int);

# sleep.c

int
main(int argc, char *argv[])
{
    if (argc != 2) {
        printf("Use ./sleep second.\n");
        exit(1);
    }
    int n = atoi(argv[1]);
    sleep(n);
    exit(0);
}

最後增加 sleep 到 makefile 就大功告成拉！
執行 qemu 測試

$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

使用自動打分數系統
make GRADEFLAGS=sleep grade

pingpong

學習使用 pipe, fork

首先建立一個 pipe

# pingpong.c
int
main(int argc, char *argv[])
{
    int fds[2];
    if (pipe(fds) == -1)
        exit(1);
}

接著呼叫 fork()

# pingpong.c
int
main(int argc, char *argv[])
{
    ...
    int pid = fork();
    if (pid < 0) {
        printf("fork() failed\n");
        exit(1)
            
    } else if (pid == 0) {
        // child
    } else {
        // parent
    }
}

parent 先發送一個 byte 給 child， child 接收後回傳一個 byte 給 parent

# pingpong.c
int
main(int argc, char *argv[])
{
    ...
    int pid = fork();
    char c;
    
    if (pid < 0) {
        printf("fork() failed\n");
        exit(1)
            
    } else if (pid == 0) {
        // child
        read(fd[0], &c, sizeof(c));
        printf("%d: received ping", getpid());
        write(fd[1], &c, sizeof(c));
        
    } else {
        // parent
        write(fd[1], &c, sizeof(c));
        read(fd[0], &c, sizeof(c));
        printf("%d: received pong", getpid());
    }
    exit(0);
}

最後增加 pingpong 到 makefile，執行 qemu

 $ make qemu
...
init: starting sh
$ pingpong
4: received ping
3: received pong
$

primes

閱讀 Bell Labs and CSP Threads

每一個格子代表一個 process，會過濾 input，將合適的 output 傳遞下去，最左邊需要一個 process 傳遞所有的資料
先建立 parent 及 child ，並做 redirect，沒有用到的 io 先關掉

# primes
int main(int argc, char const *argv[])
{
    int fds[2];
    if (pipe(fds) < 0) {
        printf("pipe() failed\n");
        exit(1);
    }

    int pid = fork();
    if (pid < 0) {
        printf("pid() failed\n");
        exit(1);
    } else if (pid == 0) {
        close(0);
        dup(fds[0]);
        close(fds[0]);
        close(fds[1]);
        exit(0);
    } else {
        close(1);
        dup(fds[1]);
        close(fds[0]);
        close(fds[1]);
        for (int i = 2; i <= 35; i++) {
            write(1, &i, sizeof(i));
        }
        close(1);
        if (wait(0) < 0) {
            fprintf(2, "wait() failed\n");
            exit(1);
        }
    }
    exit(0);
}

child 第一個接收到的數字 n 會當作基準，之後的數字可以被 n 整除的話就過濾掉，
以下程式碼 csp() 透過 read() 判斷是否需要建立新的 child，若 read()有回傳表示需要，沒有用到的 pipe 要先關閉，否則 read() 不會回傳，程式不會結束。

void csp()
{
    int p;

    // get number from right side
    if (read(0, &p, sizeof(p))) {
        printf("prime %d\n", p);
        int fds[2];
        if (pipe(fds) < 0) {
            printf("pipe() failed in csp()\n");
            exit(1);
        }
        
        int pid;
        if ((pid = fork()) < 0) {
            printf("fork() failed\n");
            exit(1);
        } else if (pid == 0) {
            close(0);
            dup(fds[0]);
            close(fds[0]);
            close(fds[1]);
            csp();
        } else {
            close(1);
            dup(fds[1]);
            close(fds[0]);
            close(fds[1]);
            int n;
            while (read(0, &n, sizeof(n))) {
                if (n % p)
                    write(1, &n, sizeof(n));
            }
        }
    }
    close(0);
    close(1);
    wait(0);
}
int main(int argc, char const *argv[])
{
    ...
    } else if (pid == 0) {
        close(0);
        dup(fds[0]);
        close(fds[0]);
        close(fds[1]);
        csp();
    } else {
    ...
}

# primes
    int fds[2];
    if (pipe(fds) < 0) {
        printf("pipe() failed\n");
        exit(1);
    }

    int pid = fork();
    if (pid < 0) {
        printf("pid() failed\n");
        exit(1);
    } else if (pid == 0) {
        // use pseudo code https://swtch.com/~rsc/thread/
        close(0);
        dup(fds[0]);
        close(fds[0]);
        close(fds[1]);
        csp();
    } else {
        close(1);
        dup(fds[1]);
        close(fds[0]);
        close(fds[1]);
        for (int i = 2; i <= 35; i++) {
            write(1, &i, sizeof(i));
        }
        // close pipe so child process will return from read().
        close(1);
        if (wait(0) < 0) {
            fprintf(2, "wait() failed\n");
            exit(1);
        }
    }
    exit(0);
}

find

參考 user/ls.c 的架構，

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

void
find(char *path)
{
  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_DEVICE:
  case T_FILE:
    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)) {
      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;
      }
    }
    break;
  }
  close(fd);
}

int
main(int argc, char *argv[])
{
  if(argc != 3){
    printf("Use ./find path file\n");
    exit(1);
  }
  find(argv[1]);
  exit(0);
}

find 需要比對每個檔案名稱，若是名稱相同，印出路徑。
參考 fmtname()，cmpname() 比對檔案名稱是否相同。

void
cmpname(char *path, char *fileName)
{
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  if (strcmp(p, fileName) == 0)
    printf("%s\n", path);
}

在一開始呼叫 cmpname

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

+   cmpname(path, fileName);
    ...
}

接著考慮 . 及 ..，若是這兩個資料夾名稱，則不遞迴執行 find()

  case T_DIR:
    ...
    while(read(fd, &de, sizeof(de)) == sizeof(de)) {
        ...
+       if (strcmp(".", de.name) == 0 || strcmp("..", de.name) == 0) 
+           continue;
+       find(buf, fileName);
    }

xargs

• argvs 為執行 exec 時帶入的參數
• 透過 read 切割 input，將 input 放到 buf
• buf 放到 argvs 的最後一項

int main(int argc, char *argv[])
{
    char buf[128];
    char *argvs[MAXARG];
    char c;
    char *p = buf;

    memset(argvs, 0, sizeof(argvs));

    int i;
    for (i = 1; i < argc; i++) {
        argvs[i - 1] = argv[i];
    }
    argvs[i-1] = buf;
    while (read(0, &c, sizeof(c))) {
        if (c != '\n' && p < (buf + sizeof(buf))) {
            *p++ = c;
        } else {
            *p = '\0';
            xargs(argvs);
            p = buf;
        }
    }
    return 0;
}

xargs 執行程式並帶入對應的參數

void
xargs(char *argv[])
{
    int pid;

    if ((pid = fork()) < 0) {
        printf("xargs: fork() failed\n");
        exit(1);
    } else if (pid == 0) {
        close(0);
        exec(argv[0], argv);
    }
    wait(0);
}

references

https://pdos.csail.mit.edu/6.S081/2022/tools.html
https://github.com/mit-pdos/xv6-riscv