MIT 6.S081/Fall 2019实验Lab: Simple xv6 shell，为xv6写一个简单的shell。应该能够使用参数运行命令，处理输入和输出重定向，并设置双元素管道。对于这些示例以及类似的命令，实现的shell应类似于 xv6 shell sh：

echo hello there
echo something > file.txt
ls | grep READ
grep lion < data.txt | wc > count
echo echo hello | nsh
find . b | xargs grep hello

同时，该实验不能使用动态内存分配接口，例如malloc()、sbrk()，取而代之的是，只有本地变量（栈分配的）和全局变量可以使用。可以对命令名的最大长度、参数的最大数量或者任何单个参数的最大长度等内容施加合理的固定限制。

本次实验的关键点和难点在于指令的解析和不同类型指令的执行。本文对主要思路和关键部分的代码实现进行说明，完整代码实现可以参考我的GitHub仓库.

1. shell执行流程

1. shell执行getcmd获得用户输入的命令；
2. shell执行fork创建一个shell进程的副本，然后shell进行wait状态；
3. 调用parsecmd(buf)解析输入的命令；
4. shell执行runcmd运行用户的命令；
5. runcmd函数调用exec系统调用加载适当的函数如：echo、cat、grep等；
6. 函数执行结束后，接着执行exit系统调用返回shell，shell从wait中退出。

据此编写main函数：

/*
    main process:
    get cmd -> cd? -> fork -> parse cmd -> run cmd -> get cmd
                   -> cd
*/
int main(void) {
    init_index();
    static char buf[MAXBUF];
    int fd;

    while ((fd = open("console", O_RDWR)) >= 0){
        if (fd >= 3) {
            close(fd);
            break;
        }
    }

    while (getcmd(buf, sizeof(buf)) >= 0) {
        if (buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' ') {
            buf[strlen(buf) - 1] = 0;
            if (chdir(buf+3) < 0) fprintf(2, "cannot cd %s\n", buf+3);
            continue;
        }
        if(fork() == 0) runcmd(parsecmd(buf));
        wait(0);
    }
    exit(0);
}

其中cd指令较为特殊，需要进行特判。

2. parsecmd解析指令

指令解析函数parsecmd执行的核心函数的parseline，这个函数是递归执行的，其执行流程如下：

1. 首先执行parsepipe的核心函数parseexec，调用execcmd，生成一个execcmd的结构体，然后调用parseredirs函数，检查是否有重定向符号"<“或”>"，如果有，则将之前的execcmd改为redircmd。将命令的入参保存在cmd->argv中；

2. 接着，检查用户输入的命令中是否有管道命令，如果有，递归调用parsepipe，则建立管道连接；

3. 返回parseline，执行命令中是否有&（返回命令），如果有，则生成一个新的backcmd；

4. 检查是否有；（多条命令分别要执行），如果有，递归调用parseline，将所有的命令分别解析后连接起来。

据此编写以下解析cmd的函数：

struct cmd* parsecmd(char *s) {
    struct cmd *cmd;
    char *es;
    es = s + strlen(s);
    cmd = parsepipe(&s, es);
    if (s != es) {
        fprintf(2, "leftovers: %s", s);
        exit(-1);
    }
    return cmd;
}

/*
    pipe cmd? -> left_cmd | right_cmd -> parseexec(left_cmd) -> pipecmd(left_cmd, parsepipe(right_cmd))
              -> parseexec(cmd)
*/
struct cmd* parsepipe(char **ps, char *es) {
    struct cmd *cmd;
    char *q, *eq;
    if (1 == scan(ps, es, "|", &q, &eq)) {
        cmd = parseexec(&q, eq);
        (*ps)++;
        cmd = pipecmd(cmd, parsepipe(ps, es));
    } else {
        cmd = parseexec(&q, eq);
    }
    return cmd;
}

struct cmd* parseexec(char **ps, char *es){
    char *q, *eq;
    int token, argc;
    struct execcmd *cmd;
    struct cmd *ret;

    ret = execcmd();
    cmd = (struct execcmd*)ret;

    argc = 0;
    ret = parseredirs(ret, ps, es);

    while(*ps < es) {
        if((token=gettoken(ps, es, &q, &eq)) == 0) break;

        if(token != 'a') {
            fprintf(2, "syntax error.\n");
            exit(-1);
        }

        cmd->argv[argc] = copy(q, eq);
        argc++;

        if(argc >= MAXARGS) {
            fprintf(2, "too many args.\n");
            exit(-1);
        }
        
        ret = parseredirs(ret, ps, es);
    }
    cmd->argv[argc] = 0;
    return ret;
}

/*
    cmd > file ->                                       -> redircmd(cmd, file)
                  cmd -> parseexec(cmd) -> execcmd(cmd)
                  file -> file
*/
struct cmd* parseredirs(struct cmd *cmd, char **ps, char *es) {
    int token;
    char *q, *eq;

    while(peek(ps, es, "<>")) {
        token = gettoken(ps, es, 0, 0);
        if (gettoken(ps, es, &q, &eq) != 'a') {
            fprintf(2, "missing file for redirection.\n");
            exit(-1);
        }

        switch(token) {
            case '<':
                // fprintf(2, "< cmd\n");
                cmd = redircmd(cmd, copy(q, eq), REDIR, O_RDONLY, 0);
                break;
            case '>':
                // fprintf(2, "> cmd\n");
                cmd = redircmd(cmd, copy(q, eq), REDIR, O_WRONLY|O_CREATE, 1);
                break;
        }
    }
    return cmd;
}

/*
    create pipecmd and convert it to cmd
*/
struct cmd *pipecmd(struct cmd *left, struct cmd *right) {
    if (++cmd_index[PIPE] >= MAXCMDS) {
        fprintf(2, "Too many commands.\n");
        exit(-1);
    }
    struct pipecmd *cmd = &mypipecmd[cmd_index[PIPE]];

    cmd->type = PIPE;
    cmd->left = left;
    cmd->right = right;

    return (struct cmd*) cmd;
}

/*
    create execcmd and convert it to cmd
*/
struct cmd *execcmd(void) {
    if (++cmd_index[EXEC] >= MAXCMDS) {
        fprintf(2, "Too many commands.\n");
        exit(-1);
    }
    struct execcmd *cmd = &myexeccmd[cmd_index[EXEC]];

    cmd->type = EXEC;
    
    return (struct cmd*)cmd;
}

/*
    create redircmd and convert it to cmd
*/
struct cmd *redircmd(struct cmd *subcmd, char *file, int type, int mode, int fd) {
    if (++cmd_index[REDIR] >= MAXCMDS) {
        fprintf(2, "Too many commands.\n");
        exit(-1);
    }
    struct redircmd *cmd = &myredircmd[cmd_index[REDIR]];

    cmd->type = type;
    cmd->cmd = subcmd;
    cmd->file = file;
    cmd->mode = mode;
    cmd->fd = fd;

    return (struct cmd*)cmd;
}

3. cmd执行

3.1 cmd结构体

参考sh.c中的cmd结构体定义，定义不同指令的结构体：

struct cmd {
  int type;
};

struct execcmd {
  int type;
  char *argv[MAXARGS];
  char *eargv[MAXARGS];
};

struct redircmd {
  int type;
  struct cmd *cmd;
  char *file;
  char *efile;
  int mode;
  int fd;
};

struct pipecmd {
  int type;
  struct cmd *left;
  struct cmd *right;
};

由于不能使用动态分配函数，所以事先定义指令数组，分配好空间：

/*
    not allowed to use m a l l o c()
    use global parameters instead
    index and cmd_index record the use of space
*/
struct cmd mycmd[MAXCMDS];
struct pipecmd mypipecmd[MAXCMDS];
struct execcmd myexeccmd[MAXCMDS];
struct redircmd myredircmd[MAXCMDS];
int cmd_index[MAXCMDS];
char mybuf[MAXBUF];
char cmdbuff[MAXBUF];
int index = 0;

3.2 cmd执行

不同类型的指令，最终都会使用exec进行执行，根据指令的不同类型，递归调用runcmd完成对不同指令的执行。

void runcmd(struct cmd *cmd) {
    int p[2];
    struct execcmd *ecmd;
    struct pipecmd *pcmd;
    struct redircmd *rcmd;

    if (cmd == 0) exit(0);

    switch(cmd->type) {
        default:
            fprintf(2, "error cmd.\n");
            exit(-1);
        case EXEC:
            ecmd = (struct execcmd*)cmd;

            if (ecmd->argv[0] == 0) exit(-1);
            if (-1 == exec(ecmd->argv[0], ecmd->argv)) fprintf(2, "exec %s failed.\n", ecmd->argv[0]);
            break;
        case REDIR:
            rcmd = (struct redircmd*)cmd;
            close(rcmd->fd);

            if (open(rcmd->file, rcmd->mode) < 0) {
                fprintf(2, "open %s failed.\n", rcmd->file);
                exit(-1);
            }
            runcmd(rcmd->cmd);
            break;
        case PIPE:
            pcmd = (struct pipecmd*)cmd;
            if (pipe(p) < 0) exit(-1);
            if (fork() == 0) {
                close(1);
                dup(p[1]);
                close(p[0]);
                close(p[1]);
                runcmd(pcmd->left);
            }
            if (fork() == 0) {
                close(0);
                dup(p[0]);
                close(p[0]);
                close(p[1]);
                runcmd(pcmd->right);
            }
            close(p[0]);
            close(p[1]);
            wait(0);
            wait(0);
            break;
    }
    exit(0);
}