# CS:APP Shell Lab

## Background
本實驗希望我們做出一個 Unix Shell 。所以我們可以先來看一個簡單的 Shell 程式是如何實作的。

首先，Shell 的定義就是由使用者在 command line 上輸入字串，而 Shell 再根據字串執行對應的動作。因此接收到字串後便進入評估(`eval`)。

而 `eval` 函式需要做以下的事:
1. 判斷是在前台(foreground)或是後台(background)運行。
2. 解析第一個參數是否為 Shell 內建的命令
3. 若第二點為真，則直接調用該功能函式，並結束這個命令
4. 若第二點為否，則 Shell 會創建一個子行程，並在子行程中執行所請求的程式

:::info
前台與後台的差別：
* 前台就如我們平常的 command 一樣，Shell 一定會等到命令執行結束後才會給你重新輸入
* 後台則是讓該命令執行，Shell 不去管他，直接回到主程式接收下一個命令

詳細實作會在後面說明。
:::
簡單範例如下。

#include "csapp.h"
#define MAXARGS 128
/* Function prototypes */
void eval(char *cmdline);
int parseline(char *buf, char **argv);
int builtin_command(char **argv);
int main()
{
	char cmdline[MAXLINE]; /* Command line */

 	while (1) {
 		/* Read */
 		printf("> ");
 		Fgets(cmdline, MAXLINE, stdin);
 		if (feof(stdin))
 		exit(0);

 		/* Evaluate */
 		eval(cmdline);
	}
}

講完了基本流程，接著需要思考兩件事。Shell 必須實現作業控制(job)與信號處理(Signal)。作業表明了 Shell 程式中運行的行程。每當新增一個新的命令時，需要增加，結束時需要刪除。而信號處理則是 Shell 必須要回應來自 Kernel 的信號，例如 Ctrl-C 或 Ctrl-Z。因此需要撰寫 Signal_handler 來處理。

## 作業要求
上面簡單說明了 Shell 程式的基本程序。現在來說明本實驗需要實作的函式。

* `eval`: 解析和解釋 command line 的主程式
* `builtin_cmd`: 識別並解釋內建指令：`quit`、`fg`、`bg` 和 `jobs`
* `do_bgfg`: 實作 `bg` 與 `fg` 的內建命令
* `waitfg`: 等待前台作業完成
* `sigchld_handler`: 獲取 `SIGCHILD` 信號
* `sigint_handler`: 獲取 `SIGINT`(Ctrl-C)
* `sigtstp_handler`: 獲取 `SIGTSTP`(Ctrl-Z)

> [Shell Lab PDF](http://csapp.cs.cmu.edu/3e/shlab.pdf)

## `main`
本實驗已經提供寫好的主程式如下，可以看到結構與上面例子大致相同。但因為 `eval` 函式會涉及到一些議題，因此我們從簡單的開始寫起。

int main(int argc, char **argv) 
{
    char c;
    char cmdline[MAXLINE];
    int emit_prompt = 1; /* emit prompt (default) */

    /* Redirect stderr to stdout (so that driver will get all output
     * on the pipe connected to stdout) */
    dup2(1, 2);

    /* Parse the command line */
    while ((c = getopt(argc, argv, "hvp")) != EOF) {
        switch (c) {
        case 'h':             /* print help message */
            usage();
	    break;
        case 'v':             /* emit additional diagnostic info */
            verbose = 1;
	    break;
        case 'p':             /* don't print a prompt */
            emit_prompt = 0;  /* handy for automatic testing */
	    break;
	default:
            usage();
	}
    }

    /* Install the signal handlers */

    /* These are the ones you will need to implement */
    Signal(SIGINT,  sigint_handler);   /* ctrl-c */
    Signal(SIGTSTP, sigtstp_handler);  /* ctrl-z */
    Signal(SIGCHLD, sigchld_handler);  /* Terminated or stopped child */

    /* This one provides a clean way to kill the shell */
    Signal(SIGQUIT, sigquit_handler); 

    /* Initialize the job list */
    initjobs(jobs);

    /* Execute the shell's read/eval loop */
    while (1) {

	/* Read command line */
	if (emit_prompt) {
	    printf("%s", prompt);
	    fflush(stdout);
	}
	if ((fgets(cmdline, MAXLINE, stdin) == NULL) && ferror(stdin))
	    app_error("fgets error");
	if (feof(stdin)) { /* End of file (ctrl-d) */
	    fflush(stdout);
	    exit(0);
	}

	/* Evaluate the command line */
	eval(cmdline);
	fflush(stdout);
	fflush(stdout);
    } 

    exit(0); /* control never reaches here */
}

## `builtin_cmd`
在課本 8.4.6 的圖 8-24 中有給出簡單的範例。現在我們需要將其擴展到可以處裡 `quit`、`fg`、`bg` 和 `jobs` 命令。若是內建命令回傳 1，反之回傳 0。

* `quit`: 直接結束 Shell 程式
* `fg` or `bg`: 執行 `do_bgfg` 函式
* `jobs`: 執行 `listjobs` 函式
* `&`: 不理它（`parseline` 函式會負責處理它）

int builtin_cmd(char **argv) 
{
    if (!strcmp(argv[0], "quit"))
        exit(0);
    if (!strcmp(argv[0], "fg") || !strcmp(argv[0], "bg")) {
        do_bgfg(argv);
        return 1;
    }
    if (!strcmp(argv[0], "jobs")) {
        listjobs(jobs);
        return 1;
    }
    if (!strcmp(argv[0], "&")) {
        return 1;
    }
    return 0;
}

## `eval`
如同前面 background 提到 `eval` 函式的功能。而在課本的 Fig 8-24 有給出範例的程式碼。我們先複習一下要做的事：

1. 判斷是在前台(foreground)或是後台(background)運行。
2. 解析第一個參數是否為 Shell 內建的命令
3. 若第二點為真，則直接調用該功能函式，並結束這個命令
4. 若第二點為否，則 Shell 會創建一個子行程，並在子行程中執行所請求的程式

### Race condition
需要修改的地方是我們實作的 Shell 必須包含作業控制。簡單來說就是需要在每次執行新的命令時使用 `addjob` 新增作業，而當命令執行結束後便要使用 `deletejob` 刪除作業。新增就直接在函式的後面做新增就好，而當一個子行程中止時，kernel 會向其父行程送發送 `SIGCHLD` 信號。叫父行程去回收殭屍行程。那也就是說只要在 `sigchld_handler` 裡面刪除作業就好。

但重點來了，我們知道說使用 `fork` 產生子行程我們沒辦法預測到底是父行程會先執行還是子行程會先執行。這樣就會導致一個嚴重的問題，如下圖所示，當子行程在父行程還沒 addjob 前就執行完的話，kernel 會向父行程(Shell)發送 `SIGCHLD` 信號，便會觸發`sigchld_handler`，就直接刪除作業了，但是父行程根本就還沒新增完成阿。這就導致 race condition。


### Soultion
那解法就是利用阻塞(block)信號的方式。原理是這樣，在 `addjob` 函式之前，先阻塞所有的信號，在執行結束後在恢復。這樣就可以讓 `addjob` 函式執行期間不會受到任何信號的中斷了。

但是下圖是在 `fork` 之前先把 `SIGCHLD` 信號阻塞，在子行程在把它 unblock ，如果照我們上面講的，在 `addjob` 函式之前，先阻塞所有的信號就好啦。原因是可能父行程完全執行不到的情況下子行程就已經執行結束了。所以利用 `fork` 出來的子行程會繼承父行程的信號狀態，在子行程在 unblock，而父行程就會在阻塞所有信號之前，就已經阻塞 `SIGCHLD` 信號。


### Block and Unblock signal
在 `signal.h` 定義了一些信號操作的 API，信號的阻塞都需要利用集合(set)的概念。

#include <signal.h>

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);
int sigemptyset(sigset_t *set); // 創建空集合
int sigfillset(sigset_t *set); // 創建所有信號的集合
int sigaddset(sigset_t *set, int signum); // 新增信號到集合裡
int sigdelset(sigset_t *set, int signum); // 刪除信號到集合裡

而要對信號阻塞就要使用 `sigprocmask` 函式，`how` 參數有以下幾個：
* `SIG_BLOCK`: 加入 set 中的信號進行阻塞 (blocked = blocked | set)
* `SIG_UNBLOCK`: 把 set 中的信號解除阻塞 (blocked = blocked & ~set)
* `SIG_SETMASK`: 阻塞 set 中所有信號 (blocked = set)

而 `oldset` 會保存當前的信號集合狀態。

### 程式碼實現
關於信號的實現，如以下幾點：
* 在 `fork` 之前對`SIGCHLD` 信號阻塞
* 在子行程中解除 `SIGCHLD` 信號阻塞，使其可以發送信號
* 在父行程中將所有信號阻塞，使得 `addjob` 函式為 critical section
* 當使用者使用 ctrl-c 或 ctrl-z 時，kernel 會發送 SIGINT 到前台的每個行程，也就是會發送給 Shell 本身以及其運行的程式。但我們不希望 Shell 本身被刪除，因此在運行子行程時，可以使用 `setpgid(0, 0)` 使子行程獨立成一個 process group。

另一方面，在最後判斷是否要在後台運行，若是要在前台運行，在原本的程式 (Fig 8.24) 中是直接使用 `waitpid` API 直接等待子行程結束。本作業希望使用 `waitfg` 函式來解決一些問題，具體實作在下一節。

void eval(char *cmdline) 
{
    char* argv[MAXARGS];
    char buf[MAXLINE];
    int bg;
    pid_t pid;

    strcpy(buf, cmdline);
    bg = parseline(buf, argv);

    if (argv[0] == NULL)
        return; /* Ignore empty lines */

    sigset_t mask_all, mask_one, mask_prev;
    sigfillset(&mask_all); 
    sigemptyset(&mask_one);
    sigaddset(&mask_one, SIGCHLD);
    if (!builtin_cmd(argv)) {
        /* Block SIGCHLD signal */
        sigprocmask(SIG_BLOCK, &mask_one, &mask_prev);
        if ((pid = fork()) == 0) { /* Child run user job */
            setpgid(0, 0);
            /* Unblock SIGCHLD signal */
            sigprocmask(SIG_SETMASK, &mask_prev, NULL);
            if (execve(argv[0], argv, environ) < 0) { 
                printf("%s: Command not found\n", argv[0]);
                exit(0);
            }
        }

        /* Parent add job, will not be interrupted by any signal */
        sigprocmask(SIG_BLOCK, &mask_all, NULL);
        addjob(jobs, pid, bg ? BG:FG, buf);
        sigprocmask(SIG_SETMASK, &mask_prev, NULL);

        if (!bg) {
            waitfg(pid);
        }
        else {
            printf("[%d] (%d) %s",pid2jid(pid), pid, cmdline);
        }
    }
    return;
}

## `waitfg`
這個函式是要等待子行程完成。這部份的討論在課本的 8.5.7 有說明。以下說明:

1. 解法一： 最簡單的想法就是使用一個 busy wait 的方式一直等待，但顯然處理器會一直呼叫 `fgpid` 函式，非常浪費資源。

while (pid == fgpid(jobs)); // waste CPU

2. 解法二： 如同微處理機學到的，busy wait 的方式不好的話改用 interrupt 的方式就好啦。因此可以在迴圈內插入 `pause` 函式，其作用是會讓行程暫停直到被信號中斷。但有個嚴重的 race condition 問題，就是當 SIGCHLD 信號是在 while 測試與 `pause` 函式之前發生，`pause` 函式可能會永遠醒不來。

while (pid == fgpid(jobs)) // race condition
	pause();	

3. 解法三：可以將 `pause` 改成 `sleep` 函式。很明顯這樣程式會跑得非常慢，就算可以將 time slice 設小一點也不能確定多小才剛好。

while (pid == fgpid(jobs)) // waste time
	sleep(1);	

4. 解法四：使用 `sigsuspend` 函式，其作用是可以使 `pause` 函式為 atomic，就等價於

sigprocmask(SIG_BLOCK, &mask, &prev);
pause();
sigprocmask(SIG_SETMASK, &prev, NULL);

也就是說在解法二中擔心的 race condition 就被解決掉了。因為我們可以在前面先阻塞掉信號，接著在迴圈裡呼叫 `sigsuspend` 函式，它確保打開信號、暫停行程、阻塞信號是不可被中斷的，也就不可出現在 SIGCHLD 信號是在 while 測試與 `pause` 函式之前發生。

while (pid == fgpid(jobs)) // good
	sigsuspend(&mask_prev);

因此按照解法四的思路，來撰寫 `waitfg`

void waitfg(pid_t pid)
{
    sigset_t mask_one, mask_prev;
    sigemptyset(&mask_one);
    sigaddset(&mask_one, SIGCHLD);
    sigprocmask(SIG_BLOCK, &mask_one, &mask_prev); /* Block SIGCHLD */

    while (pid == fgpid(jobs)) // good
        sigsuspend(&mask_prev);

    sigprocmask(SIG_SETMASK, &mask_prev, NULL); /* Set to prev mask */
    return;
}

## `sigint_handler`
在課本 8.5.5 有詳細介紹 Signal handler 需要注意的地方。以下簡單說明:
* handler 需要盡量簡單
* handler 內只能使用非同步信號安全的函式
* 保存與恢復 `errno`
* 阻塞所有信號

當按下 `ctrl-C` 時，kernel 會發送 `SIGINT` 信號。接著由 `sigint_handler` 處理。注意到 `kill` 函式:

int kill(pid_t pid, int sig);

* `pid_t pid`：要傳送訊號的目標進程的進程 ID（PID）。
* 如果 `pid > 0`，則訊號 sig 將傳送給進程 ID 等於 pid 的進程。
* 如果 `pid == 0`，則訊號 `sig` 將傳送給與呼叫進程屬於同一進程組的所有進程。
* 如果 `pid < -1`，則訊號 `sig` 將傳送給進程組 ID 等於 pid 的所有進程。
* 如果 `pid == -1`，則訊號 `sig` 將傳送給所有有權限發送訊號的進程（除了進程 ID 為 1 的進程）。
* `int sig`：要傳送的訊號編號。常見的訊號包括 `SIGINT`、`SIGTERM`、`SIGKILL` 等。

因此需要將 `pid` 設置為負的，使其可以對整個 process group 發送信號。

void sigint_handler(int sig) 
{
    int eldorrno = errno;
    sigset_t mask_all, mask_prev;
    /* Block all signal */
    sigfillset(&mask_all);
    sigprocmask(SIG_BLOCK, &mask_all, &mask_prev);
    pid_t pid = fgpid(jobs);
    if (pid != 0) { // ?
        kill(-pid, SIGINT);
        sigprocmask(SIG_SETMASK, &mask_prev, NULL);
        return;
    }
    sigprocmask(SIG_SETMASK, &mask_prev, NULL);    
    errno = olderrno;
    return;
}

## `sigtstp_handler`
而與前面雷同，當按下 `ctrl-Z` 時，kernel 會發送 `SIGTSTP` 信號。接著由 `sigtstp_handler` 將這個信號傳給這個 pid 所在的 process group 裡的所有行程。

void sigtstp_handler(int sig) 
{
    int eldorrno = errno;
    sigset_t mask_all, mask_prev;
    /* Block all signal */
    sigfillset(&mask_all);
    sigprocmask(SIG_BLOCK, &mask_all, &mask_prev);
    pid_t pid = fgpid(jobs);
    if (pid != 0) { // ?
        kill(-pid, SIGTSTP);
        sigprocmask(SIG_SETMASK, &mask_prev, NULL);
        return;
    }
    sigprocmask(SIG_SETMASK, &mask_prev, NULL);    
    errno = olderrno;
    return;
}

## `sigchld_handler`
在 Shell 執行的子行程中止時，或者是子行程收到 SIGSTOP 或 SIGTSTP 信號後，kernel 會向 Shell 發送 SIGCHLD 信號。而 `sigchld_handler` 就要負責回收 (reaped) 殭屍行程。
> sigchld_handler - The kernel sends a SIGCHLD to the shell whenever a child job terminates (becomes a zombie), or stops because it received a SIGSTOP or SIGTSTP signal. The handler reaps all available zombie children, but doesn't wait for any other currently running children to terminate.

:::info
暫停(Stopped)與終止(terminated)的差異：

* 暫停: 作業系統響應某些信號，例如使用者按下 Ctrl-Z 觸發 SIGTSTP 信號。而被暫停的行程的資源仍然佔用著記憶體空間
* 終止: 表示行程已經執行完成了，也有可能是因為收到 SIGKILL 或 SIGTERM 信號，而終止的行程就不佔任何資源在記憶體裡面了
:::

要使用 `waitpid` 函式來回收。在課本 8.4.3 中有詳細說明。我們可以透過 `options` 參數來調整 `waitpid` 函式的行為。

pid_t waitpid(pid_t pid, int *status, int options);

以上述的行為來講，可以使用下面兩個參數:
* `WNOHANG`:
* 若沒有任何子行程的狀態發生變化，則會返回 0
* `WUNTRACED`:
* 若有**子行程終止**，返回該子行程的 PID。
* 若有**子行程因信號暫停執行**（stopped），返回該子行程的 PID。

而透過將參數 `pid` 設置為 -1，使得其等待集合就是由父行程所有的子行程組成的。`status` 參數則是當回傳值大於 0 時才有效。而此時就代表上述條件被觸發。就可以進行回收作業了。

1. `WIFEXITED(status)`: 如果子行程是通過使用 `exit` 函式，或是正常使用 return 回傳，那我們就單純的把它從作業列表中刪除。
2. `WIFSIGNALED(status)`: 如果子行程是被一個未被捕獲的信號終止，則除了把它從作業列表中刪除之外，印出作業被哪個信號終止。
3. `WIFSTOPPED(status)`: 如果子行程是暫停的，那就不需要把它從作業列表中刪除。而是要標注其作業是暫停狀態，並印出作業被哪個信號暫停。

前面說到信號處理函式只能使用非同步信號安全的函式，而 `printf` 並不是。所以必須要在前面阻塞掉所有信號。

void sigchld_handler(int sig) 
{
    int errno;
    int status;
    sigset_t mask_all, mask_prev;
    pid_t pid;
    struct job_t *job;
	
    sigfillset(&mask_all);
    
    while ((pid = waitpid(-1, &status, WNOHANG | WUNTRACED)) > 0) {
        sigprocmask(SIG_BLOCK, &mask_all, &prev); // block all signal
        if (WIFEXITED(status)) {
            deletejob(jobs, pid);
        }
        if (WIFSIGNALED(status)) {
            printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
            deletejob(jobs, pid);
        }
        if (WIFSTOPPED(status)) {
            job = getjobpid(jobs, pid);
            job->state = ST;
            printf("Job [%d] (%d) stoped by signal %d\n", pid2jid(pid), pid, WSTOPSIG(status));
        }
        sigprocmask(SIG_SETMASK, &prev, NULL); // unblock all signal
    }
    errno = olderrno;
    return;
}

我們來簡單梳理一下執行流程，首先先看 `pause` 函式的說明。它的作用是將 Shell 行程變成睡眠(sleep)狀態，直到信號處理執行結束。而因為在 `sigchld_handler` 中將前台作業刪除了，因此在 `fgpid` 函式會回傳 0，因而終止 `waitfg` 函式。

DESCRIPTION
       pause()  causes the calling process (or thread) to sleep until a signal
       is delivered that either terminates the process or causes  the  invoca‐
       tion of a signal-catching function.

RETURN VALUE
       pause()  returns  only when a signal was caught and the signal-catching
       function returned.  In this case, pause() returns -1, and errno is  set
       to EINTR.

## `do_bgfg`
這個函式是當使用者輸入 `fg` 或 `bg` 指令時進入。有兩種用法。第一種是在第二個參數寫 `%1`，1 可以換成其他數字，意指將該數字對應的 job 設為前台或後台。第二種是直接寫數字 `1`，表示將 pid 為 1 的行程設為前台或後台。接著我們需要考慮到一些例外情況:

* 輸入值為 `NULL`: 印出錯誤訊息
* 第一種情況: 若為 `%` 開頭，檢測出數字即為 `jid`，在從 `getjobjid` 取得 job 的結構體。需檢查是否有此 job
* 第二種情況: 若為數字開頭，從 `getjobpid` 取得 job 的結構體。需檢查是否有此 job

不管是前後台，都要向該 job 的 process group 發送 `SIGCONT` 信號。若是後台，則打印訊息後不用管它。若是前台則使用 `waitfg` 等待。

void do_bgfg(char **argv) 
{
    sigset_t mask_all, mask_prev;
    pid_t pid = 0;
    int jid = 0;
    int bg = 0;
    struct job_t *job;

    sigfillset(&mask_all);
    sigprocmask(SIG_BLOCK, &mask_all, &mask_prev);
    if (argv[1] == NULL) {
        printf("%s command requires PID or %%jobid argument\n", argv[0]);
        sigprocmask(SIG_SETMASK, &mask_prev, NULL);
        return;
    }
    if (argv[1][0] == '%') {
        sscanf(&argv[1][1], "%d", &jid);
        job = getjobjid(jobs, jid);
        if (job == NULL) {
            printf("%%%d: No such job\n", jid);
            sigprocmask(SIG_SETMASK, &mask_prev, NULL);
            return;
        }
    }
    else if (argv[1][0] >= 48 && argv[1][0] <= 57) {
        job = getjobpid(jobs, pid);
        if(job == NULL) {
            printf("(%d): No such process\n", pid);
            sigprocmask(SIG_SETMASK, &mask_prev, NULL);
            return;
        }
    }
    else {
        printf("%s: argument must be a PID or %%jobid\n", argv[0]);
        sigprocmask(SIG_SETMASK, &mask_prev, NULL);
        return;
    }

    if (!strcmp(argv[0], "bg"))
        bg = 1;
    kill(-(job->pid), SIGCONT);
    job->state = (bg ? BG : FG);
    sigprocmask(SIG_SETMASK, &mask_prev, NULL);
    if (bg) {
        printf("[%d] (%d) %s",job->jid, job->pid, job->cmdline);
    }
    else {
        waitfg(pid);
    }
    return;
}

## Test
編譯通過後，就可以進行測試。一共有 16 個測試關卡，可以對照著標準答案。若是自己的 Shell 跑出來的結果與標準答案一樣，就通過了。以下是命令範例，需要從 01 測試到 16。

$ make test01
$ make rtest01