6.828 Homework xv6 shell

date: 2019-02-16
tags: OS 6.828

这个作业是要求完成sh.c这个文件，来写一个shell。做这个作业之前还是需要看一下xv6 book的第一章的，不然有些地方会不明白。以及，真正的xv6的shell版本在xv6-public/sh.c中，可以参考学习。同时，lecture 4中的第一部分一些关于这次作业的问题，我们也在这里进行讨论。

Executing simple commands

简单来说，shell就是一个会循环读入每一行并对每一行做出反应的程序。所以除去cd指令（比较例外...），都是先fork一下，然后在child里对读进来的buffer进行parse并然后依据parse的内容运行对应的程序。

对于执行简单工具，读过parse之后知道，simple commands就是用type == ' '来表示的，其argv就是execv需要的，所以核心是：

case ' ':
    ecmd = (struct execcmd*)cmd;
    if(ecmd->argv[0] == 0)
      _exit(0);
    execv(ecmd->argv[0], ecmd->argv);
    fprintf(stderr, "exec %s failed\n", ecmd->argv[0]);
    break;

注意，runcmd里面这个代码不能进行普通的printf，应该是因为都是在child里面运行的，而为什么输出最后都能返回parent，应该是因为执行的结果被重定向回了parent。但是神奇的是可以通过stderr输出，不知道为什么。。。

问题：

exec

这里问了几个问题。。。我几乎一个都答不上来。。。

why two execv() arguments? 不明白。。。

what happens to the arguments? 第一个是调用的可执行文件，第二个是参数列表

can execv return? 正常是不返回的，如果返回就说明有error

shell是如何继续运行的？用fork实现的

I/O redirection

注意，open，dup都会选择当时没被用的最小的file descriptor。然后io redirection在xv6 book里面有很相似的例子，代码很简单先关掉再打开就好了。

case '>':
case '<':
    rcmd = (struct redircmd*)cmd;
    int mode = S_IRUSR | S_IWUSR;
    close(rcmd->fd);
    if(open(rcmd->file, rcmd->flags, mode) < 0) {
        fprintf(stderr, "Fail to open %s\n", rcmd->file);
        _exit(-1);
    }
    runcmd(rcmd->cmd);
    break;

问题：

redirect

kernel是通过file descriptor table来进行redirect的

因为用了fork，之后对fd的操作都是和main shell无关的，所以不会影响main shell

Implement pipes

这里的难点就是pipe。对于pipe的讲解可以用xv6 book里面的例子来说：

int p[2];
char *argv[2];
argv[0] = "wc";
argv[1] = 0;
pipe(p);
if(fork() == 0) {  // 在child里面就留两个，一个是0 -> pipe read, 1 -> stdout
	close(0);  // child里不连上stdin了
	dup(p[0]);  // 0 -> pipe read
	close(p[0]);  // p[0]不连着pipe read
	close(p[1]);  // p[1]不连着pipe write了
	exec("/bin/wc", argv);
} else {  // parent里面不动0, 1，然后留下p[1] -> pipe write，来向child写入
	close(p[0]);
	write(p[1], "hello world\n", 12);
	close(p[1]);
}

对于pipe的重要测试例子是/bin/sleep 3 | /bin/echo hi，这里最开始我也没写对...后来参考了xv6-public里面的代码才写出来。

case '|':
    pcmd = (struct pipecmd*)cmd;
    if(pipe(p) < 0) {
        fprintf(stderr, "Fail to create pipe\n");
        _exit(-1);
    }
    if(fork1() == 0){
      close(1);
      dup(p[1]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->left);  // the execv will end this child
    }
    if(fork1() == 0){
      close(0);
      dup(p[0]);
      close(p[0]);
      close(p[1]);
      fprintf(stderr, "right\n");
      runcmd(pcmd->right);  // the execv will end this child
    }
    close(p[0]);
    close(p[1]);
    wait(&r);
    wait(&r);
    break;

在分析问题之前，先简单介绍一下pipe的原理，本部分来自于xv6 book的Code: pipe部分，现在的理解可能有所欠缺，需要对锁有更好的理解之后再来。

每个pipe的结构如下：

struct pipe {
  struct spinlock lock;
  char data[PIPESIZE];
  uint nread;     // number of bytes read
  uint nwrite;    // number of bytes written
  int readopen;   // read fd is still open
  int writeopen;  // write fd is still open
};

其中data就是buffer，而这个buffer是循环存储的。nread和nwrite分别记录了读入和写入的数量，注意这两个是绝对值，没有对PIPESIZE进行求余。pipewrite会先获取lock，其会进行写入。当buffer满了的时候，会调用wakeup，来唤醒任何sleeping readers，并sleeps on $p->write以等待一些reader读出一些data。这时piperead就会获取lock，开始读入，读到p->nwrite = p->nread或者需要的量为止，然后调用wakeup唤醒pipewrite。

问题：

pipe
- 如果ls比wc快很多怎么办？
快很多的话会先把信息存在pipe的buffer里，如果buffer满了，会先sleep，等wc开始read之后再继续。
- 如果ls比wc慢很多怎么办？
慢很多的话，pipe read会等待有数据读进来再说。
- command何时决定结束：有wait，所以左边右边的command都结束就可以了。
下面的两文可以用 (/bin/ls | /usr/bin/wc) 进行测试
- reader(右边的指令)没有关闭write end会直接卡住
原因是pipe read如果返回的是空数据的话，会等待任何写入（blocking），或者待所有write descriptor都关闭了就返回0。所以如果不关的话，read就无法停止了，而wc这样的程序里面都是等read返回0来跳出循环的，所以就卡住了。
- writer（左边的指令）没有关闭read end则不会卡住
原因是write的blocking是关于不能写入的，而和多一个reader没什么关系，因为那个正常的reader会把所有的数据都读走。
- how does the kernel know when to free the pipe buffer?
When all file descriptors associated with a pipe or FIFO special file are closed, any data remaining in the pipe or FIFO shall be discarded.

close

所以如果关闭了所有的read，或者关闭了所有的write应该pipe就会被free掉了。
how does the shell know a pipeline end?

两个wait都跑完了的时候pipeline就结束了。

为什么需要fork两次？

fork两次是为了让左右的程序同时开始运行，且等都结束再返回。不fork的话就没办法用wait进行限制了。

如果运行pcmd->left不进行fork：

那代码大致是这样的：

case '|':
    pcmd = (struct pipecmd*)cmd;
    if(pipe(p) < 0) {
        fprintf(stderr, "Fail to create pipe\n");
        _exit(-1);
    }
    if(fork1() == 0){
      close(0);
      dup(p[0]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->right);  // the execv will end this child
    }
    close(1);
    dup(p[1]);
    close(p[0]);
    close(p[1]);
    runcmd(pcmd->left);  // the execv will end this child
    break;

因为本来就应该左边作为右边的输入，所以不能wait，这导致如果左边返回很快，就直接返回了，如运行/bin/ls | /bin/sleep 3，本来结果应该等3秒的，现在就直接返回了。

如果运行pcmd->right不进行fork：

如果right不进行fork，那么代码大致是这样的：

case '|':
    pcmd = (struct pipecmd*)cmd;
    if(pipe(p) < 0) {
        fprintf(stderr, "Fail to create pipe\n");
        _exit(-1);
    }
    if(fork1() == 0){
      close(1);
      dup(p[1]);
      close(p[0]);
      close(p[1]);
      runcmd(pcmd->left);  // the execv will end this child
    }
    wait(&r);
    close(0);
    dup(p[0]);
    close(p[0]);
    close(p[1]);
    runcmd(pcmd->right);  // the execv will end this child
    break;

用/bin/sleep 3 | /bin/echo hi进行测试，这个指令的输出应该是瞬间输出hi之后等3秒。但是现在这个版本因为等sleep运行完之后再运行echo，结果就是先等3秒，再输出hi。如果去掉wait运行完echo就直接返回了，直接忽略了sleep。

为什么等两个都运行起来之后再wait而不是同时wait？

这个的代码就是上面一段代码，原因就是为了能够让两个东西同时运行起来。不然的话，比如说要读进来一个大文件，然后对其进行wc，就会出现大文件充满了pipe buffer，导致writer block，因为还没有返回，所以没有reader，从而就整体锁住了这样的问题。

关于pipe部分的一些内部实现和结构在note10中有提到，有兴趣可以看一下。

还有一些challenge problems，这次就先不写了，以后有机会吧。

写完这三部分之后就可以运行测试代码了，

$ ./sh
6.828$ sh < t.sh
     10      10      51
     10      10      51

注意这里我并没有去写PATH这部分，所以改了t.sh，具体每个指令在哪里可以通过运行which指令来获取，如

$ which ls
/bin/ls

等项目代码部署到git上之后，会在这里贴一下我的sh.c的代码链接的。

zhuzilin's Blog

about

6.828 Homework xv6 shell

Executing simple commands

I/O redirection

Implement pipes