CSAPP八个lab，从ShellLab开始难度和码量开始迅速上升，需要我们熟练掌握书上的内容并灵活运用。
ShellLab要求我们实现一个简单版本的Linux Shell程序。前置知识主要包括第八章（进程控制，信号处理）和第十章（unix系统级IO）。第八章的讲解中有不少Shell的参考代码，可以提（yuan）供（yang）思（fu）路（zhi）。

读一读已经给出的代码

• 全局数据结构
  shell程序用job_t结构管理它的作业（job）。

struct job_t
{                          /* The job struct */
   pid_t pid;             /* job PID */
   int jid;               /* job ID [1, 2, ...] */
   int state;             /* UNDEF, BG, FG, or ST */
   char cmdline[MAXLINE]; /* command line */
};
struct job_t job_list[MAXJOBS]; /* The job list */

在此基础上，有实现好的addjob, deletejob等函数供我们使用。具体的实现不必细究（其实就是扫一遍数组）。但要牢记访问job_list这个全局数据结构的时候，要阻塞所有信号（教材P536）。

• main函数
  main看起来很长，但其实就是一个while(1)循环，不断地读入命令，调用eval执行任务。我们需要实现这个eval函数。
• parseline函数
  parseline也是封装好的辅助函数，用来处理命令行。它把结果存放在cmdline_tokens结构中，供eval使用。

总之，ShellLab已经帮我们实现了很多辅助工具，我们应当把注意力集中到Shell的核心——进程控制和信号处理上来。

Shell的功能

• 内置命令
  • quit
    直接退出Shell。
  • jobs
    打印作业列表。直接调用listjobs即可。
  • kill
    显式发送信号SIGTERM。kill 5表示发送给PID为5的子进程。kill %5表示发送给JID（shell自行管理的作业编号）为5的子进程。
  • bg/fg
    显式地要求作业在前台或后台执行。bg在后台继续执行一个挂起的后台进程（注意执行bg的时候一定没有正在执行的前台进程），fg在前台执行一个挂起的后台进程，或者直接将后台进程转换到前台执行。bg/fg和kill一样使用PID或JID（加‘%’）。
  • nohup
    非内置命令前加nohup表示要求shell忽略SIGHUP信号。
• IO重定向
  像Linux Shell一样，使用<表示输入重定向，>表示输出重定向。具体内容参见教材第十章（主要在P637）。
• 非内置命令
  像Linux Shell一样，格式为：文件名+参数列表。
• 来自键盘的信号
  像Linux Shell一样，ctrl-c表示终止（terminate）前台进程（发送SIGINT），ctrl-z表示停止/挂起（stop）前台进程（发送SIGTSTP，注意不是SIGSTOP！）。

Shell的基本框架：fork和execve

教材P543给出了Shell的基本框架。大致意思如下：

block SIGCHLD;
if ((pid = fork()) == 0){
	unblock SIGCHLD;
	execve();
}
block all signals;
addjob();
unblock;

注意以下几点：

• 一开始必须先阻塞SIGCHLD。这是因为如果在addjob之前执行sigchld_handler，就会尝试删除一个还没加入job_list的作业，导致错误。换句话说，保证这里的addjob赢得与sigchld_handler中deletejob的竞争。
• fork创建的子进程会继承父进程的阻塞信号集合。所以在子进程execve之前要恢复原有的阻塞信号集合，让子进程像没事发生一样去执行命令。
• 调用addjob访问全局数据结构，要阻塞所有信号。

再结合Lab的要求，我们需要增加这些功能：

• 为实现ctrl-c和ctrl-z，最开始还需要阻塞SIGINT和SIGTSTP，否则先执行handler会导致addjob加入终止的作业。
• Shell在执行前台程序的时候用户需要等待。也就是说，Shell进程需要显式地等待前台子进程结束，再准备读入下一个命令行。这里教材P545有详细的讲解，使用sigsuspend函数，让Shell进程等待SIGCHLD信号到达。
• 使用dup2函数（教材P637）实现IO重定向。

block SIGCHLD, SIGINT, SIGTSTP;
if (nohup) block SIGHUP;
if ((pid = fork()) == 0){
	unblock;
	input_id = open(tok.infile);
    dup2(input_id, STDIN_FILENO);
    output_id = open(tok.outfile);
    dup2(output_id, STDOUT_FILENO);
	execve();
}
block all signals;
addjob();
if (fg) wait SIGCHLD;
if (bg) print info;
unblock;

至此，非内置命令基本实现。

内置命令

switch (tok.builtins)
    {
    case BUILTIN_QUIT:
    	/* 直接退出Shell */
        exit(0);
    case BUILTIN_JOBS:
    	/* 打印作业列表，等待下一个命令行 */
        listjobs();
        return;
    case BUILTIN_BG:
    case BUILTIN_FG:
    	/* 待实现 */
        cmd_bg_fg();
        return;
    case BUILTIN_KILL:
    	/* 杀死进程，等待下一个命令行 */
    	/* 待实现 */
        kill_job();
        return;
    case BUILTIN_NOHUP:
    	/* 需要阻塞SIGHUP */
        block SIGHUP;
        break;
    case BUILTIN_NONE:
    	/* 啥也不做 */
        break;
    }

内置命令非常简单，上面已经实现了除kill和bg/fg之外的所有内置命令。

接下来我们看一看kill的实现。

void kill_job(const char *str)
{
    if (find_job(str))
    {
        kill(-job->pid, SIGTERM);
        print info;
    }
}

find_job处理命令字符串str，提取PID或JID，使用封装好的getjobpid和getjobbjid函数，搜索job_list。如果找到，kill_job向该作业所在进程组发送SIGTERM，使其终止。

之后是bg/fg：

void cmd_bg_fg(int bg, const char *str)
{
    struct job_t *job = find_job(str);
    /* bg 命令 */
    if (bg)
    {
    	/* 挂起的后台进程 */
        if (job->state == ST)
        {
            job->state = BG;
            kill(-job->pid, SIGCONT);/* 在后台继续执行 */
            print info;
        }
    }
    /* fg 命令 */
    else
    {
		/* 挂起或者正在执行的后台进程 */
        if (job->state == ST || job->state == BG)
        {
            job->state = FG;/* 到前台执行 */
            if (job->state == ST)
            	kill(-job->pid, SIGCONT);            
            wait SIGCHLD；
        }
    }
}

之前已经提到过，执行bg/fg时，不可能有正在运行的前台进程（状态为FG）。
执行bg时，如果目标状态是BG（正在后台执行），那么什么也不用做；如果目标状态是ST（挂起），那么做两件事：修改状态为BG，发送SIGCONT使之继续在后台执行。
执行fg时，修改目标状态为FG，如果是挂起的后台进程就发送SIGCONT使之继续。然后像前面所说处理前台进程一样，等待SIGCHLD到达。

信号处理程序(handler)

至此，仅剩三个信号处理程序未实现（sigchld_handler,sigint_handler,sigtstp_handler,分别对应SIGCHLD,SIGINT,SIGTSTP）。
根据Shell的功能要求，接收SIGINT和SIGTSTP后应当向其前台作业转发相同的信号（如果没有前台进程当然就什么也不用做）。
再看SIGCHLD。sigchld_handler的注释写道：The handler reaps all available zombie children, but doesn’t wait for any other currently running children to terminate.
这用waitpid函数即可实现（教材P516-P517）：

while ((pid = waitpid(-1, &state, WNOHANG | WUNTRACED)) > 0) 

注意：

• 使用while，一次回收尽可能多的子进程（教材P536-P539）。
• 第一个参数-1表示等待集合是所有的子进程。
• WNOHANG表示不要等待，即如果没有僵死子进程就立即返回0.
• WUNTRACED表示处理终止和停止的子进程（默认只处理终止的）。

	while ((pid = waitpid(-1, &state, WNOHANG | WUNTRACED)) > 0)
    {
        struct job_t *job = getjobpid(job_list, pid);
        /* 前台进程终止，flag和sigsuspend配合使用 */
        if (pid == fgpid(job_list))
        {
            flag = 1;
        }
        /* 停止 */
        if (WIFSTOPPED(state))
        {
            job->state = ST;
            print info;
        }
        /* 终止 */
        else
        {
            if (WIFSIGNALED(state))
            {
                print info;
            }
            deletejob(job_list, pid);
        }
    }

• WIFSTOPPED,WIFSIGNALED等宏的定义见P517.
• 信号处理程序应当使用异步信号安全的函数。具体来说，printf是不安全的。因此这里使用csapp.h中提供的sio_puts（实际上是对unix write函数的简单包装）。

附完整代码：

• handlers

/* 
 * 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, SIGTSTP, SIGTTIN or SIGTTOU signal. The 
 *     handler reaps all available zombie children, but doesn't wait 
 *     for any other currently running children to terminate.  
 */
void sigchld_handler(int sig)
{
    int state;
    sigset_t mask_all, prev;
    pid_t pid;
    sigfillset(&mask_all);
    /* WNOHANG: doesn't wait for any other currently running children to terminate */
    /* WUNTRACED: stop or terminate(default: only terminated process) */
    while ((pid = waitpid(-1, &state, WNOHANG | WUNTRACED)) > 0)
    {
        sigprocmask(SIG_BLOCK, &mask_all, &prev);
        struct job_t *job = getjobpid(job_list, pid);
        /* fg job stopped/terminated, shell need not wait anymore(sigsuspend) */
        if (pid == fgpid(job_list))
        {
            flag = 1;
        }
        if (WIFSTOPPED(state))
        {
            job->state = ST;
            sio_put("Job [%d] (%d) stopped by signal %d\n",
                    job->jid, job->pid, WSTOPSIG(state));
        }
        else
        {
            if (WIFSIGNALED(state))
            {
                sio_put("Job [%d] (%d) terminated by signal %d\n",
                        job->jid, job->pid, WTERMSIG(state));
            }
            deletejob(job_list, pid);
        }
        sigprocmask(SIG_SETMASK, &prev, NULL);
    }
}

/* 
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.  
 */
void sigint_handler(int sig)
{
    int old_errno = errno;
    sigset_t prev, mask_all;
    sigfillset(&mask_all);

    sigprocmask(SIG_BLOCK, &mask_all, &prev);
    pid_t pid = fgpid(job_list);
    sigprocmask(SIG_SETMASK, &prev, NULL);
    if (pid)
    {
        kill(-pid, SIGINT);
    }
    errno = old_errno;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.  
 */
void sigtstp_handler(int sig)
{
    int old_errno = errno;
    sigset_t prev, mask_all;
    sigfillset(&mask_all);

    sigprocmask(SIG_BLOCK, &mask_all, &prev);
    pid_t pid = fgpid(job_list);
    sigprocmask(SIG_SETMASK, &prev, NULL);
    if (pid)
    {
        kill(-pid, SIGTSTP);
    }
    errno = old_errno;
}

• eval

/* 
 * eval - Evaluate the command line that the user has just typed in
 * 
 * If the user has requested a built-in command (quit, jobs, bg or fg)
 * then execute it immediately. Otherwise, fork a child process and
 * run the job in the context of the child. If the job is running in
 * the foreground, wait for it to terminate and then return.  Note:
 * each child process must have a unique process group ID so that our
 * background children don't receive SIGINT (SIGTSTP) from the kernel
 * when we type ctrl-c (ctrl-z) at the keyboard.  
 */
void eval(char *cmdline)
{
    int bg; /* should the job run in bg or fg? */
    struct cmdline_tokens tok;
    pid_t pid;
    int input_id = STDIN_FILENO, output_id = STDOUT_FILENO;

    sigset_t prev, mask_all, mask0;
    sigfillset(&mask_all);
    sigemptyset(&mask0);

    sigset_t mask_sigchld;
    sigemptyset(&mask_sigchld);
    sigaddset(&mask_sigchld, SIGCHLD);

    sigset_t mask_sighup;
    sigemptyset(&mask_sighup);
    sigaddset(&mask_sighup, SIGHUP);

    sigaddset(&mask0, SIGCHLD);
    sigaddset(&mask0, SIGINT);
    sigaddset(&mask0, SIGTSTP);

    /* Parse command line */
    bg = parseline(cmdline, &tok);

    if (bg == -1) /* parsing error */
        return;

    if (tok.argv[0] == NULL) /* ignore empty lines */
        return;

    /* process builtin commands */
    switch (tok.builtins)
    {
    case BUILTIN_QUIT:
        exit(0);
        break;
    case BUILTIN_JOBS:
        if (tok.outfile)
        {
            output_id = open(tok.outfile, O_WRONLY, 0);
        }
        sigprocmask(SIG_BLOCK, &mask_all, &prev);
        listjobs(job_list, output_id);
        sigprocmask(SIG_SETMASK, &prev, NULL);
        if (tok.outfile)
        {
            close(output_id);
        }
        return;
    case BUILTIN_BG:
    case BUILTIN_FG:
        cmd_bg_fg(tok.builtins == BUILTIN_BG, tok.argv[1]);
        return;
    case BUILTIN_KILL:
        kill_job(tok.argv[1]);
        return;
    case BUILTIN_NOHUP:
        sigprocmask(SIG_BLOCK, &mask_sighup, NULL);
        break;
    case BUILTIN_NONE:
        break;
    }

    /* block SIGCHLD, SIGINT, SIGTSTP(and SIGHUP if nohup) */
    /* These three handlers assume the job has been added to the
    joblist, so the handlers must wait until 'addjob' is executed. */
    sigprocmask(SIG_BLOCK, &mask0, &prev);
    if ((pid = fork()) == 0)
    {
        /* unblock(in child process) */
        sigprocmask(SIG_SETMASK, &prev, NULL);
        /* input and output redirection */
        if (tok.infile)
        {
            input_id = open(tok.infile, O_RDONLY, 0);
            dup2(input_id, STDIN_FILENO);
        }
        if (tok.outfile)
        {
            output_id = open(tok.outfile, O_WRONLY, 0);
            dup2(output_id, STDOUT_FILENO);
        }
        setpgid(0, 0);
        const char *path =
            tok.argv[tok.builtins == BUILTIN_NOHUP ? 1 : 0];
        if (execve(path, tok.argv, environ) == -1)
        {
            printf("%s: Command not found\n", path);
            if (tok.infile)
            {
                close(input_id);
            }
            if (tok.outfile)
            {
                close(output_id);
            }
            exit(0);
        }
    }
    /* block all signals before use global variables */
    sigprocmask(SIG_BLOCK, &mask_all, NULL);
    addjob(job_list, pid, bg ? BG : FG, cmdline);
    /* fg, explicitly wait for signals(use 'sigsuspend')*/
    /* SIGCHLD should be blocked before, or 'flag = 1' in 'sigchld_handler'
    may be executed before here, which cause endless loop. */
    /* Here, all signals are blocked. */
    if (!bg)
    {
        flag = 0;
        while (!flag)
            sigsuspend(&prev);
    }
    else
    {
        struct job_t *job = getjobpid(job_list, pid);
        printf("[%d] (%d) %s\n", job->jid, job->pid, job->cmdline);
    }
    sigprocmask(SIG_SETMASK, &prev, NULL);
}

• other

/*
Interprete JID/PID and find the job(NULL if no such job)
"5" -> 5
"%5"-> 5
*/
struct job_t *find_job(const char *str)
{
    sigset_t mask_all, prev;
    sigfillset(&mask_all);
    sigprocmask(SIG_BLOCK, &mask_all, &prev);
    struct job_t *ret = NULL;
    int id;
    if (str[0] == '%')
    {
        id = atol(str + 1);
        ret = getjobjid(job_list, id);
        if (!ret)
        {
            printf("%s: No such job\n", str);
        }
    }
    else
    {
        id = atol(str);
        ret = getjobpid(job_list, id);
        if (!ret)
        {
            printf("(%d): No such process\n", id);
        }
    }
    sigprocmask(SIG_SETMASK, &prev, NULL);
    return ret;
}

/*
Interprete the command and send SIGTERM to kill child process group
*/
void kill_job(const char *str)
{
    struct job_t *job = find_job(str);
    if (job)
    {
        kill(-job->pid, SIGTERM);
        printf("[%d] (%d) %s\n", job->jid, job->pid, job->cmdline);
    }
}

/*
built-in command bg & fg
*/
void cmd_bg_fg(int bg, const char *str)
{
    struct job_t *job = find_job(str);
    sigset_t mask_empty;
    sigemptyset(&mask_empty);
    if (!job)
        return;
    /* when execute the command bg / fg, there can't be a frontground process*/
    if (bg)
    {
        /* continue to execute a stopped process in background */
        if (job->state == ST)
        {
            job->state = BG;
            kill(-job->pid, SIGCONT);
            printf("[%d] (%d) %s\n", job->jid, job->pid, job->cmdline);
        }
    }
    else
    {
        /* continue to execute a stopped process in frontground */
        if (job->state == ST)
        {
            job->state = FG;
            kill(-job->pid, SIGCONT);
            /* wait until SIGCHLD has been handled */
            /* which means the frontground process has terminated */
            flag = 0;
            while (!flag)
                sigsuspend(&mask_empty);
        }
        /* change a background process to execute in frontground */
        else if (job->state == BG)
        {
            job->state = FG;
            flag = 0;
            while (!flag)
                sigsuspend(&mask_empty);
        }
    }
}