Problem set 4: Shell

In this assignment, you’ll leverage fork, exec, pipe, and several other interesting system calls to build a command shell. You will implement simple commands, conditional commands (&& and ||), pipes, background commands, and redirections, as well as the incredible cd command.

As with Problem Set 1, we’re staging your work in two parts.

Your shell implements a subset of the bash shell’s syntax, and is generally compatible with bash for the features they share. You may be interested in a tutorial for Unix shells.

Get the code

Start with the cs61-psets Git repository you used for Problem Set 3 and run git pull handout main to merge our code, which is in the pset4 subdirectory, with your previous work. If you have any “conflicts” from Problem Set 3, resolve them before continuing further. Run git push to save your work back to GitHub.

Shell grammar

There are two main phases to writing a shell: the shell must parse commands from a command line string, and then it must execute those commands. We’ve completed most of the parsing phase for you. The shell_tokenizer object parses tokens from a command line, and can differentiate between normal words like “echo” and special control operators like “;” or “>”. The command_line_parser object and its friends (conditional_parser, pipeline_parser, command_parser) consume tokens from shell_tokenizer, but also understands the shell grammar, and can determine where a command line (or conditional, or pipeline, or command) ends.

sh61 command lines obey this grammar, with each input line a “command_line”:

command_line ::= (empty)
          |  conditional
          |  conditional ";" command_line
          |  conditional "&" command_line

conditional ::=  pipeline
          |   conditional "&&" pipeline
          |   conditional "||" pipeline

pipeline ::=  command
          |   pipeline "|" command

command  ::=  word
          |   redirection
          |   command word
          |   command redirection

redirection  ::=  redirectionop filename
redirectionop  ::=  "<"  |  ">"  |  "2>"

This grammar says, for example, that the command list “echo foo && echo bar & echo baz” is parsed and executed like this:

  {   { echo foo } && { echo bar }   } & { echo baz }

The && is “inside” the background command, so “echo foo && echo bar” runs in the background and “echo baz” runs in the foreground. The overall command list comprises two conditionals, “echo foo && echo bar” and “echo baz”; these conditionals divide into three (trivial) pipelines, “echo foo”, “echo bar”, and “echo baz”; and each of those piplines contains a single command.

A robust shell will detect errors in its input and handle them gracefully, but for this problem set, we promise that all the inputs we use in tests follow the grammar above.

About BNF grammars

Tests (Pset 4a)

In the first week, we want you to design tests for a shell at the same time as you start implementing your own. We provide a test harness, sh61_tester, to make this easier; each test you write will be a small C++ program that runs a shell on a script and checks what happened. Read shtest.hh for its full interface. Here’s an example:

// Test: A failed redirection prints an error and the command fails
#include "shtest.hh"

int main(int argc, char* argv[]) {
    sh61_tester t(argc, argv);
    t.run("echo Unwanted < nonexistent.txt || echo Wanted");
    // The first `echo` command reports an error message and fails
    assert(t.stderr().contains("No such file or directory"));
    // Since that didn’t exit with status 0, `||` runs the next `echo` command
    assert(t.stdout() == "Wanted\n");
}

A test sets up the run (with functions like t.write_file(name, contents)), calls run() with one or more command lines to run, and then checks the results with assert and functions like t.stdout(), t.stderr(), t.exit_status(), t.elapsed(), and t.file_contents(name). The harness also fails a test if the shell crashes, causes a sanitizer error, or runs longer than its time limit (5 seconds unless the test calls t.set_time_limit).

Tests live in the t/, tt/, and torture/ subdirectories, one test per file. (There are no torture or tt/ tests in the initial handout. We will hand out torture tests as part of pset 4b.) To build and run a test, use make check-NAME, as in make check-redir-002; this finds the test in any of those directories. You can also run a built test directly, as in t/redir-002. A test that passes prints nothing; a test that fails says why:

$ t/simple-001
simple-001: t/simple-001.cc:7: int main(int, char**): Assertion `t.stdout() == "Hooray\n"' failed.
Aborted

To run a test against a different shell, such as bash, set SHTEST_SHELL:

$ SHTEST_SHELL=bash t/simple-001
$

A good test is:

Name each test after the feature it tests, using the phase names simple, list, cond, pipe, bg, zombie, redir, and cd, as in t/cond-mytest.cc. Then make check-cond will run your test along with ours.

Each test runs the shell in its own directory, which is removed when the test exits. To see the shell’s output after a failure, give the test an existing directory to use instead, as in t/cond-mytest -d mydir; the script and the shell’s output will be left in mydir/script, mydir/stdout, and mydir/stderr.

How to write tests

A strong test will often involve commonly-installed, commonly-used utility programs that have predictable output and exit status. For instance, true, false, and echo are powerful enough to test many properties of conditional execution even on their own. Documentation can be accessed via the man page, e.g. man cat, or often also through a help switch, e.g. cat --help.

Shell Program Description
cat Write named files (or standard input) to standard output.
wc Count lines, words, and characters in named files (or standard input).
head -n N Print first N lines of standard input.
head -c N Print first N characters of standard input.
tail -n N Print last N lines of standard input.
echo ARG1 ARG2... Print arguments to standard output.
printf FORMAT ARG... Print arguments with printf-style formatting.
true Always succeed (exit with status 0).
false Always fail (exit with status 1).
yes Print y (or any arguments) forever.
sort Sort lines in input.
uniq Drop duplicate lines in input (or print only duplicate lines).
tr Change characters; e.g., tr a-z A-Z makes all letters uppercase.
ps List processes.
sleep N Pause for N seconds, then exit with status 0.
cut Cut selected portions of each line of a file.
grep PATTERN Print lines in named files (or standard input) that match a regular expression PATTERN.
tac Write lines in named files (or standard input) in reverse order to standard output.

To check on the shell while it runs—for instance, to see whether a background command is still running, or whether the shell has left a zombie—use t.after(seconds, function) and t.processes(), described in shtest.hh.

How to proceed

The main work of this assignment is implementing the shell. Phases 1–3 are part of pset 4a; Phases 4–8 are part of pset 4b.

If you’re confused about a shell feature and the tutorials and manuals don’t help, run some experiments! The bash shell, which is default on Docker, is compatible with our shell. (The zsh shell, which is default on Mac OS X, is mostly compatible.)

See the commonly-used programs for testing ideas.

Run your shell by typing ./sh61 and entering commands at the prompt. Exit your shell by typing Control-D at the prompt; the Control-D will cause the shell to detect the end-of-file for the shell input.

Pset 4a turnin (Monday 10/26, 11:59pm EDT):

  1. Post at least five tests publicly to Ed, each with a brief description of what it tests. Your tests should cover different features. After the deadline, we’ll collect everyone’s tests and post them together.
  2. Implement Phases 1–3: your shell should pass make check-simple, make check-list, and make check-cond, including your own tests for those phases.
  3. Commit your tests and your shell to GitHub.

Phase 1: Simple commands

You can implement features in whatever order you prefer, but our suggested order may help structure your work.

First, support simple commands like “echo foo” by changing command::run and run_line. You’ll use at least the following system calls: fork, execvp, and waitpid. For guidance, consult:

Testing note. In this pset, you will parse parts of a command line and you will make run_line and friends execute that command line. Most of your bugs will involve problems with run_line, command::run, and helper functions you write, but it’s also possible to misuse the parser classes, or to have undefined behavior. So, make sure you think through your testing strategy. Consider using strace to trace the operation of your shell, for example! Here are some notes about how.

To exit a forked copy of the shell (for example, if execvp fails), use the _exit system call. For instance, call _exit(1) or, equivalently, _exit(EXIT_FAILURE) to exit with status 1.

Your code for this problem set should never call the exit function. exit (without the underscore) is a libc library call, not a system call; exit performs cleanup actions (e.g., messing with open stdio files) that shouldn’t happen in child processes—these actions should only happen in the parent shell. If you call exit instead of _exit from child processes, you may see weird behavior where, for example, the parent shell re-executes parts of a command file.

Run make check-simple to test your work.

Phase 2: Command lists

Support foreground command lists, which are chains of commands linked by ; (and optionally terminated by ;). The semicolon runs two commands in sequence—the first command must complete before the second begins.

This phase will require changes to run_line, at least. You will start using more of the functionality of command_line_parser, specifically command_line_parser::conditional_begin().

Run make check-list to check your work.

About command_line_parser and the other parser types

The command_line_parser object, and related sub-parser objects conditional_parser, pipeline_parser, and command_parser, understand the shell grammar and offer functions that navigate command lines. You’ll use more of their functions in almost every phase.

Each sub-parser navigates within a parent region. For instance, conditional_parser navigates the conditionals within a command line. Create a sub-parser by calling a function like conditional_begin(). Advance the sub-parser to its next region with ++p (iterator-like notation).

The important functions of parser objects are:

  • Iterate by command: command_begin() returns a command_parser for the first command in the current region. ++cmdpar advances this parser to the next command within its parent region. The comparison cmdpar == parent.end() checks whether cmdpar has reached the end of the parent region.
  • Iterate by pipeline or conditional: Similarly, pipeline_begin() returns a pipeline_parser that navigates by pipelines, and conditional_begin() returns a conditional_parser that navigates by conditionals.
  • Iterate by tokens: token_begin() returns a shell_tokenizer iterating over the tokens in the region. Use tok.type(), tok.str(), and ++tok to analyze the returned tokens.
  • Next operation: If it is a sub-parser, it.next_op() returns the token type, like TYPE_SEQUENCE or TYPE_AND, of the next token within the parent region. (At the end of the parent region, it returns TYPE_EOL.) For example, in the conditional a && b || c, the next_op()s after the three pipelines are TYPE_AND, TYPE_OR, and TYPE_EOL.
  • Truthiness test (if (parser) or while (parser)): Returns true unless parser has reached the end of its parent region.

But the best way to see this work is by example.

Simplicity note. As you add more features to your shell, your code will naturally get more complicated. But try to resist unnecessary complication. Don’t copy whole blocks of code—avoid this pattern:

if (feature 1 is enabled) {
    step 1 of child process creation;
    step 2 of child process creation;
    step 3a of child process creation;
    step 4 of child process creation;
    step 5a of child process creation;
} else if (feature 2 is enabled) {
    step 1 of child process creation;
    step 2 of child process creation;
    step 3b of child process creation;
    step 4 of child process creation;
    step 5b of child process creation;
} else {
    step 1a of child process creation;
    step 2 of child process creation;
    step 3c of child process creation;
    step 4b of child process creation;
    step 5a of child process creation;
}

Instead, aim for something like this:

step 1 of child process creation;
step 2 of child process creation;
if (feature 1 is enabled) {
    step 3a of child process creation;
} else {
    step 3b of child process creation;
}
step 4 of child process creation;
if (feature 1 is enabled) {
    step 5a of child process creation;
} else if (feature 2 is enabled) {
    step 5b of child process creation;
}
...

The second style is more robust to changes in requirements, because adding another feature requires local changes, as opposed to many distributed changes across slightly-different blocks of code.

Our solutions, with all features enabled, have two lines that call fork(), two lines that call waitpid(), and one line that calls execvp().

Phase 3: Conditionals

Support conditionals, which are chains of commands linked by && and/or ||. Each of these operators runs two commands, but the second command is run conditionally, based on the status of the first command. For example:

$ true ; echo print
          # The second command always runs, because ';' is an
          # unconditional control operator.
print
$ false ; echo print
print
$ true && echo print
          # With &&, though, the 2nd command runs ONLY if
          # the first command exits with status 0.
          # (WIFEXITED(status) && WEXITSTATUS(status) == 0)
print
$ false && echo print
          # (prints nothing)
$ true || echo print
          # With ||, the 2nd command runs ONLY if the first
          # command (1) DOES NOT exit, or (2) exits with status
          # nonzero. || is the opposite of &&.
          # (prints nothing)
$ false || echo print
print

The && and || operators have higher precedence than ; and &, so a command list can contain many conditionals. && and || have the same precedence and they associate to the left. The exit status of a conditional is taken from the last command executed in that conditional. For example, true || false has status 0 (the exit status of true) and true && false has exit status 1 (the exit status of false).

To support conditionals, you’ll probably make changes to run_line and struct command (and you might add new helper functions).

You’ll also use the WIFEXITED and WEXITSTATUS macros defined in man waitpid.

Run make check-cond to check your work.

Phase 4: Pipelines

Pset 4b: We think you should be able to implement phases 1–3 of your shell for pset 4a, the intermediate deadline. The other phases are due with the complete shell turnin in pset 4b. Nevertheless, keep reading! The tests you write for 4a should check functionality from phases 4–7.

Support pipelines, which are chains of commands linked by |. The pipe operator | runs two commands, connecting the standard output of the left command to the standard input of the right command. Unlike conditionals and lists, the commands in a pipeline run in parallel. The shell starts all the pipeline’s commands concurrently.

The | operator has higher precedence than && and ||, so a conditional can contain several pipelines. The exit status of a pipeline equals the exit status of its last command.

If a foreground pipeline has two or more commands, your shell must wait at least for the last command to complete. Normal shells, such as Linux bash, wait for all commands in the pipeline to complete before moving on (though only the last command’s status matters); your shell may wait for these other commands to complete, but it is also OK to just wait for the last command.

To support pipelines, you’ll need to use some new system calls—namely pipe, dup2, and close—and change command::run, run_line, and struct command.

See the Process control notes that discuss pipe and pipe in a shell.

Run make check-pipe to check your work.

Phase 5: Background

Now add support for background commands, such as sleep 1 &. A conditional chain is “backgrounded” when the parent shell does not wait for it to complete. Thus, the parent shell can accept and run new command lines even as background commands execute.

The & background operator TYPE_BACKGROUND has the same precedence as ; TYPE_SEQUENCE. You must support simple background commands, such as sleep 10 &, and you must support background conditional chains, such as sleep 10 && echo foo &. Run experiments to see how background conditional chains work. For instance, try:

$ sleep 10 && echo foo & echo bar

You can also use strace to explore how the default Linux shell handles background conditional chains. Try:

$ strace -e trace=%process -o strace.out -f sh -c "sleep 10 && echo foo & echo bar"

See our testing notes for information about process-related straces.

Background support will require changes to run_line.

Run make check-bg to test your work.

Background conditional hints

Every conditional chain must be managed by a shell process that collects command exit status values and implements logic for && and ||. But the parent shell process cannot manage a background conditional chain! Background conditional chains execute in parallel, alongside the parent shell (which is busy doing other things). This means a new shell process is required to manage the background conditional chain.

Can you think of a convenient system call that can create a clone of the parent shell process, so that the clone could manage a background conditional chain? We hope so.

Cloned shell processes, often called subshells, are useful for many advanced shell features, including background conditional chains. A subshell should handle only a limited set of commands and then _exit; otherwise it would interfere with the parent shell. Here, a subshell used for a background conditional chain should _exit after that conditional chain completes.

Phase 6: Zombie processes

Your shell should eventually reap all its zombie processes using waitpid. The waitpid man page contains some helpful information on zombie processes.

Hint: You must reap all zombies eventually, but you don’t need to reap them immediately. We don’t recommend using signal handlers to reap zombies, since a signal handler can interfere with the waitpid calls used to wait for foreground processes to complete. A well-placed waitpid loop will suffice to reap zombies; where should it go?

Run make check-zombie to test your work.

Phase 7: Redirections

Now support redirections, where some of a command’s file descriptors are sent to disk files. You must handle three kinds of redirection:

For instance, echo foo > x writes foo into the file named x.

shell_tokenizer represents redirect operators, such as <, > and 2>, as type TYPE_REDIRECT_OP. Each redirection operator must be followed by a filename, which is a TYPE_NORMAL token. You’ll also change command::run to set up the redirections, using system calls open, dup2, and close.

The shell sets up a command’s redirections before executing the command. If a redirection fails (because the file can’t be opened), the shell doesn’t actually run the command. Instead, the child process that would normally have run the command prints an error message to standard error and exits with status 1. Your shell should behave this way too. For example:

$ echo > /tmp/directorydoesnotexist/foo
/tmp/directorydoesnotexist/foo: No such file or directory
$ echo > /tmp/directorydoesnotexist/foo && echo print
/tmp/directorydoesnotexist/foo: No such file or directory
$ echo > /tmp/directorydoesnotexist/foo || echo print
/tmp/directorydoesnotexist/foo: No such file or directory
print

How to figure out the right error message? Try man strerror!

Hint: Your calls to open will have different arguments depending on what type of redirection is used. How to figure out what those arguments are? Well, you could use the manual page (man 2 open); or you could use strace to check the regular shell’s behavior. Try this:

$ strace -o strace.txt -f sh -c "echo foo > output.txt"

Look in strace.txt. Which flags were provided to open (or a variant, such as openat) for output.txt? Try this with different redirection types.

Run make check-redir to test your work.

Phase 8: The cd command

Finally, your shell should support the cd directory command. The cd command is special; why?

Run make check-cd to test your work.

You must support cd commands that are part of conditionals, as in cd foo && echo bar, but you do not need to support cd commands that are part of a multi-process pipeline.

Checking your work

Use make check to run the tests in t/ and torture/ against your shell, stopping at the first failure. Your shell is built with sanitizers by default; make SAN=1 LSAN=1 check also checks for memory leaks.

To run some of the tests, use make check-NAME, which runs every test in t/, tt/, and torture/ whose name starts with NAME. For example, make check-simple runs all the simple-command tests, and make check-redir-002 runs just one test. In pset 4b, make check-torture will run our torture tests.

As always, it can be great to write more tests of your own!

Turnin

Hand in your code by editing README.md and AUTHORS.md, committing your changes, and pushing the result to GitHub. Please indicate which commit is your final submission through your commit message and/or a flag on the grading server.

This lab was originally created for CS 61.