這是我自學 MIT6.S081 作業系統課程的 lab 程式碼筆記第一篇：Unix utilities。此 lab 大致耗時：4小時。

課程地址：http://pdos.csail.mit.edu/6.S081/2020/schedule.html
Lab 地址：http://pdos.csail.mit.edu/6.S081/2020/labs/util.html
我的程式碼地址：http://github.com/Miigon/my-xv6-labs-2020/tree/util
Commits: http://github.com/Miigon/my-xv6-labs-2020/commits/util

本文中程式碼註釋是編寫部落格的時候加入的，原倉庫中的程式碼可能缺乏註釋或程式碼不完全相同。

Lab 1: Unix utilities

This lab will familiarize you with xv6 and its system calls.

實現幾個 unix 實用工具，熟悉 xv6 的開發環境以及系統呼叫。

Boot xv6 (easy)

準備環境，編譯編譯器、QEMU，克隆倉庫，略過。 $ git clone git://g.csail.mit.edu/xv6-labs-2020 $ cd xv6-labs-2020 $ git checkout util $ make qemu

sleep (easy)

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.

練手題，記得在 Makefile 中將 sleep 加入構建目標裡。

```c // sleep.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h" // 必須以這個順序 include，由於三個標頭檔案有依賴關係

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

makefile UPROGS=\ $U/_cat\ $U/_echo\ $U/_forktest\ $U/_grep\ $U/_init\ $U/_kill\ $U/_ln\ $U/_ls\ $U/_mkdir\ $U/_rm\ $U/_sh\ $U/_stressfs\ $U/_usertests\ $U/_grind\ $U/_wc\ $U/_zombie\ $U/_sleep\ . # here !!!

pingpong (easy)

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() 複製本程序建立子程序，建立兩個管道，分別用於父子之間兩個方向的資料傳輸。

```c // pingpong.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

int main(int argc, char **argv) { // 建立管道會得到一個長度為 2 的 int 陣列 // 其中 0 為用於從管道讀取資料的檔案描述符，1 為用於向管道寫入資料的檔案描述符 int pp2c[2], pc2p[2]; pipe(pp2c); // 建立用於父程序 -> 子程序的管道 pipe(pc2p); // 建立用於子程序 -> 父程序的管道

if(fork() != 0) { // parent process
    write(pp2c[1], "!", 1); // 1. 父程序首先向發出該位元組
    char buf;
    read(pc2p[0], &buf, 1); // 2. 父程序傳送完成後，開始等待子程序的回覆
    printf("%d: received pong\n", getpid()); // 5. 子程序收到資料，read 返回，輸出 pong
    wait(0);
} else { // child process
    char buf;
    read(pp2c[0], &buf, 1); // 3. 子程序讀取管道，收到父程序傳送的位元組資料
    printf("%d: received ping\n", getpid());
    write(pc2p[1], &buf, 1); // 4. 子程序通過 子->父 管道，將位元組送回父程序
}
exit(0);

} ```

注：序號只為方便理解，實際執行順序由於兩程序具體排程情況不定，不一定嚴格按照該順序執行，但是結果相同。

$ pingpong 4: received ping 3: received pong $

primes (moderate) / (hard)

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.

十分好玩的一道題hhhhh，使用多程序和管道，每一個程序作為一個 stage，篩掉某個素數的所有倍數（篩法）。很巧妙的形式實現了多執行緒的篩法求素數。具體原理和流程可以看課程提供的這篇文章。

主程序：生成 n ∈ [2,35] -> 子程序1：篩掉所有 2 的倍數 -> 子程序2：篩掉所有 3 的倍數 -> 子程序3：篩掉所有 5 的倍數 -> ..... 每一個 stage 以當前數集中最小的數字作為素數輸出（每個 stage 中數集中最小的數一定是一個素數，因為它沒有被任何比它小的數篩掉），並篩掉輸入中該素數的所有倍數（必然不是素數），然後將剩下的數傳遞給下一 stage。最後會形成一條子程序鏈，而由於每一個程序都呼叫了 wait(0); 等待其子程序，所以會在最末端也就是最後一個 stage 完成的時候，沿著鏈條向上依次退出各個程序。

```c // primes.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

// 一次 sieve 呼叫是一個篩子階段，會從 pleft 獲取並輸出一個素數 p，篩除 p 的所有倍數 // 同時建立下一 stage 的程序以及相應輸入管道 pright，然後將剩下的數傳到下一 stage 處理 void sieve(int pleft[2]) { // pleft 是來自該 stage 左端程序的輸入管道 int p; read(pleft[0], &p, sizeof(p)); // 讀第一個數，必然是素數 if(p == -1) { // 如果是哨兵 -1，則代表所有數字處理完畢，退出程式 exit(0); } printf("prime %d\n", p);

int pright[2];
pipe(pright); // 建立用於輸出到下一 stage 的程序的輸出管道 pright

if(fork() == 0) {
    // 子程序 （下一個 stage）
    close(pright[1]); // 子程序只需要對輸入管道 pright 進行讀，而不需要寫，所以關掉子程序的輸入管道寫檔案描述符，降低程序開啟的檔案描述符數量
    close(pleft[0]); // 這裡的 pleft 是*父程序*的輸入管道，子程序用不到，關掉
    sieve(pright); // 子程序以父程序的輸出管道作為輸入，開始進行下一個 stage 的處理。

} else {
    // 父程序 （當前 stage）
    close(pright[0]); // 同上，父程序只需要對子程序的輸入管道進行寫而不需要讀，所以關掉父程序的讀檔案描述符
    int buf;
    while(read(pleft[0], &buf, sizeof(buf)) && buf != -1) { // 從左端的程序讀入數字
        if(buf % p != 0) { // 篩掉能被該程序篩掉的數字
            write(pright[1], &buf, sizeof(buf)); // 將剩餘的數字寫到右端程序
        }
    }
    buf = -1;
    write(pright[1], &buf, sizeof(buf)); // 補寫最後的 -1，標示輸入完成。
    wait(0); // 等待該程序的子程序完成，也就是下一 stage
    exit(0);
}

}

int main(int argc, char **argv) { // 主程序 int input_pipe[2]; pipe(input_pipe); // 準備好輸入管道，輸入 2 到 35 之間的所有整數。

if(fork() == 0) {
    // 第一個 stage 的子程序
    close(input_pipe[1]); // 子程序只需要讀輸入管道，而不需要寫，關掉子程序的管道寫檔案描述符
    sieve(input_pipe);
    exit(0);
} else {
    // 主程序
    close(input_pipe[0]); // 同上
    int i;
    for(i=2;i<=35;i++){ // 生成 [2, 35]，輸入管道鏈最左端
        write(input_pipe[1], &i, sizeof(i));
    }
    i = -1;
    write(input_pipe[1], &i, sizeof(i)); // 末尾輸入 -1，用於標識輸入完成
}
wait(0); // 等待第一個 stage 完成。注意：這裡無法等待子程序的子程序，只能等待直接子程序，無法等待間接子程序。在 sieve() 中會為每個 stage 再各自執行 wait(0)，形成等待鏈。
exit(0);

} ```

這一道的主要坑就是，stage 之間的管道 pleft 和 pright，要注意關閉不需要用到的檔案描述符，否則跑到 n = 13 的時候就會爆掉，出現讀到全是 0 的情況。 prime 2 prime 3 prime 5 prime 7 prime 11 prime 13 prime 0 prime 0 prime 0 prime 0 prime 0 prime 0 ...

這裡的理由是，fork 會將父程序的所有檔案描述符都複製到子程序裡，而 xv6 每個程序能開啟的檔案描述符總數只有 16 個（見 defs.h 中的 NOFILE 和 proc.h 中的 struct file *ofile[NOFILE]; // Open files）。

由於一個管道會同時開啟一個輸入檔案和一個輸出檔案，所以一個管道就佔用了 2 個檔案描述符，並且複製的子程序還會複製父程序的描述符，於是跑到第六七層後，就會由於最末端的子程序出現 16 個檔案描述符都被佔滿的情況，導致新管道建立失敗。

解決方法有兩部分： * 關閉管道的兩個方向中不需要用到的方向的檔案描述符（在具體程序中將管道變成只讀/只寫）

原理：每個程序從左側的讀入管道中只需要讀資料，並且只需要寫資料到右側的輸出管道，所以可以把左側管道的寫描述符，以及右側管道的讀描述符關閉，而不會影響程式執行這裡注意檔案描述符是程序獨立的，在某個程序內關閉檔案描述符，不會影響到其他程序 * 子程序建立後，關閉父程序與祖父程序之間的檔案描述符（因為子程序並不需要用到之前 stage 的管道）

具體的操作在上面程式碼中有體現。（fork 後、執行操作前，close 掉不需要用掉的檔案描述符） $ primes prime 2 prime 3 prime 5 prime 7 prime 11 prime 13 prime 17 prime 19 prime 23 prime 29 prime 31 $

find (moderate)

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.

這裡基本原理與 ls 相同，基本上可以從 ls.c 改造得到：

```c // find.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

include "kernel/fs.h"

void find(char path, char target) { 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:
    // 如果檔名結尾匹配 `/target`，則視為匹配
    if(strcmp(path+strlen(path)-strlen(target), target) == 0) {
        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(strcmp(buf+strlen(buf)-2, "/.") != 0 && strcmp(buf+strlen(buf)-3, "/..") != 0) {
            find(buf, target); // 遞迴查詢
        }
    }
    break;
}
close(fd);

}

int main(int argc, char *argv[]) { if(argc < 3){ exit(0); } char target[512]; target[0] = '/'; // 為查詢的檔名新增 / 在開頭 strcpy(target+1, argv[2]); find(argv[1], target); exit(0); } ```

$ find . b ./b ./a/b

xargs (moderate)

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.

編寫 xargs 工具，從標準輸入讀入資料，將每一行當作引數，加入到傳給 xargs 的程式名和引數後面作為額外引數，然後執行。

```c // xargs.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

include "kernel/fs.h"

// 帶引數列表，執行某個程式 void run(char program, char *args) { if(fork() == 0) { // child exec exec(program, args); exit(0); } return; // parent return }

int main(int argc, char argv[]){ char buf[2048]; // 讀入時使用的記憶體池 char p = buf, last_p = buf; // 當前引數的結束、開始指標 char argsbuf[128]; // 全部引數列表，字串指標陣列，包含 argv 傳進來的引數和 stdin 讀入的引數 char args = argsbuf; // 指向 argsbuf 中第一個從 stdin 讀入的引數 for(int i=1;i<argc;i++) { // 將 argv 提供的引數加入到最終的引數列表中 *args = argv[i]; args++; } char pa = args; // 開始讀入引數 while(read(0, p, 1) != 0) { if(p == ' ' || p == '\n') { // 讀入一個引數完成（以空格分隔，如 echo hello world，則 hello 和 world 各為一個引數） p = '\0'; // 將空格替換為 \0 分割開各個引數，這樣可以直接使用記憶體池中的字串作為引數字串 // 而不用額外開闢空間 (pa++) = last_p; last_p = p+1;

        if(*p == '\n') {
            // 讀入一行完成
            *pa = 0; // 引數列表末尾用 null 標識列表結束
            run(argv[1], argsbuf); // 執行最後一行指令
            pa = args; // 重置讀入引數指標，準備讀入下一行
        }
    }
    p++;
}
if(pa != args) { // 如果最後一行不是空行
    // 收尾最後一個引數
    *p = '\0';
    *(pa++) = last_p;
    // 收尾最後一行
    *pa = 0; // 引數列表末尾用 null 標識列表結束
    // 執行最後一行指令
    run(argv[1], argsbuf);
}
while(wait(0) != -1) {}; // 迴圈等待所有子程序完成，每一次 wait(0) 等待一個
exit(0);

} ```

上程式用到了一些指標與C字串構成的取巧用法。

Optional challenges

額外 challenge，不是滿分必要條件，會挑選有意思的或有意義的做。

uptime (easy)

Write an uptime program that prints the uptime in terms of ticks using the uptime system call. (easy)

```c // uptime.c

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

int main() { printf("%d\n", uptime()); exit(0); } ```

regex for find (easy)

Support regular expressions in name matching for find. grep.c has some primitive support for regular expressions. (easy)

從 grep.c 把 match 函式抄過來：

```c // find.c 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 cre 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; } ```

再將匹配規則改為用 match 匹配即可： c // find.c // .... switch(st.type){ case T_FILE: if(match(target, path)) { printf("%s\n", path); } break; case T_DIR: // ....

improved shell

not print a $ when processing shell commands from a file (moderate) - 完成

改進前（輸出了很多多餘 $）： $ cat xargstest.sh | sh $ $ $ $ $ $ hello hello hello $ $ 改進後： $ sh xargstest.sh hello hello hello $

modify the shell to support wait (easy) - 完成

$ wait 20 (wait 20 ticks with no output...) $

modify the shell to support lists of commands, separated by ";" (moderate) - 完成

$ echo hello; echo world; echo 2333333! hello world 2333333! $

modify the shell to support sub-shells by implementing "(" and ")" (moderate) - 跳過
modify the shell to support tab completion (easy) - 完成

``` $ sh xar [tab][回車] auto-completed: xargstest.sh

hello hello hello $ ec [tab][空格] hello,world! [回車] auto-completed: echo

hello,world! ```

modify the shell to keep a history of passed shell commands (moderate) - 跳過

shell 程式碼過長，已經放到 GitHub:

修改記錄：http://github.com/Miigon/my-xv6-labs-2020/commit/5f91ae357e5dbc031e4164e13141e6096596656d#diff-c5682e6f79d8e68b805047fc80c703adb4dbb0b972fa009bdfed1ea69dddd93f 完整檔案：http://github.com/Miigon/my-xv6-labs-2020/blob/5f91ae357e5dbc031e4164e13141e6096596656d/user/sh.c

主要點在，系統提供的 gets 不足以滿足我們的需求，所以將系統的 gets 實現拷貝到 sh.c 中，然後進行改進（支援對 \t 的檢測）。然後就是自動補全的實現，使用與 ls.c 相同的目錄遍歷邏輯，然後將字首匹配的檔名自動替換到當前輸入緩衝區內，實現自動補全。從檔案執行 shell 指令碼，由於 cat foobar.sh | sh 的形式，shell 收到的指令來自標準輸入（無法分辨是來自檔案還是來自使用者輸入），故加入一個引數，輸入要執行的指令碼檔名，然後另外開啟該指令碼執行，並判斷不輸出 $。

[mit6.s081] 筆記 Lab1: Unix utilities | Unix 實用工具

Lab 1: Unix utilities

Boot xv6 (easy)

sleep (easy)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h" // 必須以這個順序 include，由於三個標頭檔案有依賴關係

pingpong (easy)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

primes (moderate) / (hard)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

find (moderate)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

include "kernel/fs.h"

xargs (moderate)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

include "kernel/fs.h"

Optional challenges

uptime (easy)

include "kernel/types.h"

include "kernel/stat.h"

include "user/user.h"

regex for find (easy)

improved shell