MIT 6.828 -- Lab 2: Simple Shell

Lab 2 of MIT 6.828/6.S081 Fall 2019 is Simple Shell: implementing a simple shell program. This post explains the approach to the lab in detail and takes an in-depth look at the shell implementation that ships with xv6.

Preparation

First, the lab requirements:

1. The shell must support basic command execution, redirection (< >), and pipes ( | )
2. No dynamic memory allocation with malloc()
3. Use "@" instead of "$" as the command-line prompt
4. Close file descriptors promptly, and handle errors from system calls

xv6 ships with a shell implementation in sh.c. Besides redirection and pipes, it supports parentheses, command lists, background commands, and more, and its overall design is fairly complex. So we don't need to lean much on the existing code. We can meet the requirements with a simpler approach and read the xv6 shell implementation after finishing.

A shell is essentially a user program that connects the user and the operating system. Once started, it keeps reading and parsing the commands the user types, calls OS interfaces to execute them, and returns the results to the user. Running the shell in user mode rather than kernel mode means it is fully decoupled from the kernel and pluggable, which is why you can easily switch between shells like bash, zsh, and ksh.

Implementation Approach

Below is the overall approach to the lab. The full code, with detailed comments, is on GitHub.

First, a few core system calls you need to know:

• fork(): Creates a child process, copying memory into a separate process space. The code tells the child (returns 0) from the parent (returns the child's pid) by the return value. The shell forks a child to execute each command it receives, except cd, because that has to change the current directory of the main process.
• wait(): Blocks the parent until a child process exits. If you fork() several children, you need to call wait() several times to wait for all of them to finish. wait() also cannot wait for grandchild processes.
• exec(char path, char *argv): Runs the specified command by loading a new executable into memory and running it, replacing the current process space. Code after exec() in the original program never runs, which is why the shell forks a process to exec the command; otherwise it couldn't go on to handle the next command.

Main Logic

The program's main logic is in main(): it reads standard input in a loop and fork()s a child to handle each command. The child first splits the received string into an array of strings for easier handling, then parses and executes the command.

int main(void) {
  char buf[MAXLEN];             // buffer that receives the command
  char *argv[MAXARGS];          // string array (array of pointers)
  int argc;                     // number of arguments

  while (getcmd(buf, sizeof(buf)) >= 0) {
    if (fork() == 0) {
      argc = split(buf, argv);  // split on spaces into a string array
      runcmd(argv, argc);       // parse and execute the command
    }
    wait(0);                    // wait for the child to exit
  }
  exit(0);
}

getcmd() is simple: it reads standard input with gets(), and you can take it straight from sh.c. So let's go straight to split(), which processes the input command by splitting it on spaces into an argument array for later parsing and execution. The idea is to split in place on the source string: collect the start address of each argument into a pointer array and terminate each argument with a null character "0" at its end, which yields the array of argument strings.

int split(char * cmd, char ** argv) {
  int i = 0, j = 0, len = 0;

  len = strlen(cmd);
  while (i < len && cmd[i]) {
    while (i < len && strchr(whitespace, cmd[i])) {   // skip whitespace
      i++;
    }
    if (i < len) {  
      argv[j++] = cmd + i;   // store the start of each argument in the pointer array
    }
    while (i < len && !strchr(whitespace, cmd[i])) {  // skip non-whitespace characters
      i++;
    }
    cmd[i++] = 0;            // terminate each argument with '\0' at the first space after it
  }
  argv[j] = 0;               // marks the end of the argument array
  return j;                  // return the number of arguments
}

Next comes runcmd(), which parses special symbols and executes the command. Arguments are handled as follows:

• Pipes: parse from left to right; on finding the | symbol, create a child process for the command on each side, connect their standard file descriptors, and recurse into runcmd()
• Redirection: on a < or > symbol, close the corresponding standard fd and open the file
• Regular arguments: put them in the argument array to be executed

void runcmd(char **argv, int argc) {
  int i, j = 0;
  char tok;
  char *cmd[MAXARGS];

  for (i = 0; i < argc; i++) {
    if (strcmp(argv[i], "|") == 0) {
      runpipe(argv, argc, i);       // handle the pipe
      return;
    }
  }
  for (i = 0; i < argc; i++) {
    tok = argv[i][0];               // first character of this argument
    if (strchr("<>", tok)) {
      if (i == argc-1) { 
        panic("missing file for redirection");    // error if no file follows
      }
      runredir(tok, argv[i+1]);     // handle redirection
      i++;
    } else {
      cmd[j++] = argv[i];           // collect arguments
    }
  }
  cmd[j] = 0;
  exec(cmd[0], cmd);                // execute the command
}

Note: compared with sh.c, a shortcoming of this parser is that it doesn't handle a symbol attached to the next argument, as in echo 123 >1.txt or echo 123 |grep 12. The arguments in the test cases are all separated by spaces, so I kept it simple here.

Redirection

Before covering how pipe and redir (redirection) are implemented, I need to explain the concept of a file descriptor (fd). For every open file, the kernel creates a corresponding file object. The kernel also maintains a pointer array for each process that stores the addresses of that process's file objects, and an fd is simply an index into this pointer array. So the reference path is: fd -> kernel pointer array -> file object -> file on disk.

An fd is an integer allocated in increasing order. Every process has 3 fds open by default: standard input (0), standard output (1), and standard error (2). A few system calls are commonly used on fds:

• close(int fd): Closes an fd and removes the corresponding pointer from the kernel array. The file is closed only when the file object's reference count drops to 0
• dup(int fd): Duplicates an fd by adding a pointer in the kernel array that points to the same file. The new fd is the lowest integer currently available
• pipe(int * fd): Creates a pipe between two fds. Data written to one fd can be read from the other

Redirection moves a process's standard input/output onto an open file. The implementation relies on fds being allocated in increasing order: close() the standard I/O fd, then open() the target file. The file's fd automatically takes the place of the standard I/O fd we closed, and that gives us redirection.

void runredir(char tok, char * file) {
  switch (tok) {
  case '<':
    close(0);   
    open(file, O_RDONLY);
    break;
  case '>':
    close(1);
    open(file, O_WRONLY|O_CREATE);
    break;  
  default:
    break;
  }
}

Pipes

A pipe makes the standard output of the left process the standard input of the right process. The approach:

• Call pipe() to connect two fds, then call fork() twice to create two child processes. Both sibling processes inherit the fds connected by the pipe. (Note: calling fork twice here follows the sh.c implementation. In practice I found that calling fork() only once each time, with the parent as the left-side input process and the child forking recursively, also passes the tests.)
• In the child, close() the standard output fd, dup() the fd for one end of the pipe, then run the command
• The parent calls wait() twice to wait for both children to finish

The approach also shows that, because pipes rely on child processes inheriting fds, they can only be used for communication between related processes.

void runpipe(char **argv, int argc, int index) {    // index is the position of the | symbol in the array
  int p[2];

  pipe(p);                                 // create the pipe
  if (fork1() == 0) {
    close(1);                              // close standard output
    dup(p[1]);                             // duplicate the pipe fd
    close(p[0]);      
    close(p[1]);
    runcmd(argv, index);                   // recursively run the left command
  } 
  if (fork1() == 0) {
    close(0);
    dup(p[0]);
    close(p[0]);
    close(p[1]);
    runcmd(argv+index+1, argc-index-1);    // recursively run the right command
  }
  // close the fds we no longer need
  close(p[0]);
  close(p[1]);
  // wait for both children to finish
  wait(0);
  wait(0);
}

That covers the basic functionality. To test it:

• Append $U/_nsh\ to the UPROGS section of the Makefile
• Run make qemu to build and enter the xv6 command line. You can then run the script testsh nsh to execute the test cases, or run nsh to enter our shell and debug it by hand
• Finally, run make grade in the xv6-riscv-fall1 root directory to get a score.

The Shell Implementation in xv6

xv6's shell is implemented in user/sh.c. The general idea is similar to our nsh: it reads, parses, and executes user commands in a loop, but it supports more command types and its design is more complex.

1. Main logic

sh.c separates command parsing from command execution. It first recursively builds a structured command tree, then recursively walks the tree and executes the commands in it. It defines a struct for each supported command type: executable command (execcmd), redirection (redircmd), pipe (pipecmd), sequential command list (listcmd), and background command (backcmd). All of these "inherit" from a base cmd struct:

struct cmd {
  int type;       // command type
};

Each command type also has a "constructor" that allocates the struct's memory with malloc() and returns it cast to a cmd pointer. When it's actually used, it is cast back to the concrete type based on the type field. (The pointer points to the start address of the struct, and fields are accessed according to the declared type, so the cast doesn't affect usage.)

This applies object-oriented ideas, using pointers and type casts to achieve something like "polymorphism." parsecmd() acts like a "factory": it builds a different type of command depending on the input and returns them all uniformly as the base class, and runcmd() then runs different logic depending on the concrete type.

if (fork() == 0) {
  // parsecmd returns a cmd, runcmd takes a cmd
  runcmd(parsecmd(buf));  
}

This design separates parsing from execution, which makes the code logic clearer and gives each function a single job. It also improves extensibility: to add a new command type later, you only need to define a new struct and write the corresponding parsing and handling functions, with little impact on the other command types.

2. Command parsing

Parsing and structuring commands happens in parsecmd(), which handles symbols for pipes, redirection, sequential execution of multiple commands, background execution, parenthesized grouping, and so on. It relies heavily on the following two neat helper functions:

• peek(char **ps, char *es, char *toks): Checks whether the first character of the string *ps appears in the string toks, where es points to the end of the string. It also strips the leading whitespace from the string *ps. For example, peek(ps, es, "<>") checks whether the first character of the current string is one of "<>".
• int gettoken(char **ps, char *es, char *q, char *eq): Also takes the start (ps) and end (es) of the string. Each call strips the first run of whitespace and everything before it, and the q and eq passed in point to the argument that was removed. If the removed content matches one of the specified symbols such as "| < >", it returns that symbol; otherwise it returns the constant 'a'. For example, calling gettoken() on the string "cat < 1.txt" leaves the source string as "< 1.txt", with q and eq pointing to the start and end of "cat", and returns the character 'a'.

parsecmd() parses commands through a chain of calls, like a pipeline, in the order parsecmd() -> parseline() -> parsepipe() -> parseexec() -> parseblock() -> parseredirs(), each handling a different type of command. Working from left to right, it repeatedly uses peek() to check the current symbol and gettoken() to get the space-separated arguments, building a tree-shaped command structure. Unlike a conventional tree, each node in this command tree can be of a different type: for example, a pipe command's left and right fields are both of type cmd, but their concrete structures may differ.

One more detail: after parsing finishes, it also calls nulterminate to terminate the arguments recursively. The command we finally execute is of type execcmd. Its argv pointer array points to the start address of each argument, and it also maintains an eargv pointer array, filled from the eq values returned by gettoken(), that points to the end address of each argument in the list. nulterminate() sets the character at every eargv position to '0', which neatly splits the arguments within the source string.

3. Command execution

The runcmd() execution function recursively walks the entire command tree, checks the type field of each cmd struct, and handles it accordingly. The EXEC, PIPE, and REDIR commands are similar to our nsh implementation, and the remaining types are fairly simple:

• LIST: sequential commands separated by a semicolon ;. It forks a child to run the left command, waits for it to finish, then runs the right command, which gives sequential execution;
• BACK: a background command ending with &. It forks a child to run the command, and the parent exits right away.

Lab code: https://github.com/zhayujie/xv6-riscv-fall19

Permalink: https://zhayujie.com/mit6828-lab-shell.html