Tiny SHell

Instructions: Remember, all assignments in CS 3410 are individual. You must submit work that is 100% your own. Remember to ask for help from the CS 3410 staff in office hours or on Ed! If you discuss the assignment with anyone else, be careful not to share your actual work, and include an acknowledgment of the discussion in a collaboration.txt file along with your submission.

The assignment is due via Gradescope at 11:59pm on the due date indicated on the schedule.

Submission

You only need to submit one file to Gradescope:

  • tsh.c, which will contain your solution to Task 1

Provided Files

  • tsh.c, which will contain your implementation of tsh. This is the only provided file you should modify.
  • sdriver.pl, a testing tool. It executes a shell as a child process and sends it commands and signals from a trace file. It then captures and displays the output.
  • tshref, which contains an executable that serves as the reference solution for tsh.
  • Makefile, which contains the build commands for this assignment.
  • traces/trace{01-16}.txt, which are designed to test the correctness of your shell.

Overview

Your task in this assignment is to implement a command-line shell. It’s easy to forget that a shell, despite its centrality as the user interface to a computer, is “just another normal program.” It is not part of the kernel, and it does not have any kind of special privileges. It processes commands that you type and then uses standard OS facilities to launch other programs on your behalf.

With this assignment, we hope to demystify how the essential, OS-adjacent parts of a computer system work.

What Is a Shell?

For our purposes, a shell is an interactive command-line interpreter. It prints a prompt, waits for the user to enter a command line on its standard input stream, and then carries out some action that the command describes.

A command is a string, consisting of whitespace-separated words, like ls -l somedir. The first word (ls in our example) is the command: either a special built-in command name or the name of an executable file to launch. The remaining words (-l and somedir in the example) are arguments to pass to the command. The command receives this list of arguments as strings and can do anything it likes with them. (That’s what the argc and argv arguments to C’s main function receive.)

In the case of a built-in command, the shell can immediately take some action itself. Some shell built-ins in “real” Unix shells you may have used before include set, source, exit, and alias.

Most of the time, however, commands refer to actual executable files (i.e., compiled programs) that exist in the filesystem. ls is the name of an executable file, for example (it is not a built-in command in most shells). Your shell has a set of directories it looks in to find executables. (If you want to know where ls lives on your machine, type which ls.) You can also type the full path to any executable to use it. On my machine, for example, /bin/ls -l somedir is equivalent to ls -l somedir.

A shell’s main purpose is to launch and manage processes to carry out these shell commands. In general, a single command might entail launching multiple processes—together, we’ll call this group of processes a job. For example, you can type ls | head -n 2 to combine the ls and head executables (if you want to see only the first 2 files in a directory); the job for this command consists of an ls process and a head process with the standard output of the first connected to the standard input of the second.

Background Jobs

Most commands run in the foreground: the shell waits for them to complete before showing you another prompt. Unix shells also support launching long-running commands in the background. This way, you can continue typing other commands while you wait for the background one to finish.

To run a command in the background, put a & at the end. For example, try typing this in your computer’s “real” shell:

$ sleep 5

The sleep command runs for 5 seconds in the foreground, during which you can’t type any new commands. Now try this version:

$ sleep 5 &

Your shell will print out some information about the background job it launched, and then it will immediately print another prompt and let you type more commands.

Job Control

Because you can have any number of background jobs running at once, shells provide job control features to manage them. For example:

  • To see a list of currently running jobs, type jobs.
  • To bring a background job into the foreground, type fg <job>.
  • To interrupt the current foreground job, type control-C. (You’ve probably used this one before!)
  • To pause the current foreground job and send it into the background, type control-Z.
  • To start a paused background job, type bg <job>.

These job-control features involve sending signals to a job’s processes. Namely, when you type control-C, the shell sends the SIGINT (“interrupt”) signal to every process in the foreground job. The processes can choose to handle this signal however they want (or to not handle it at all); it is only by convention that well-behaved programs exit when they receive SIGINT. Typing control-C is not the only way to send the SIGINT signal; for example, you can also send it to a process of your choice by typing kill -s INT <pid>.

Pausing and resuming (control-Z, bg, and fg) uses the SIGTSTP (“terminal stop”) and SIGCONT (“continue”) signals.

Task 0 (Lab): Implementing Test Programs with System Calls

In lab, you will write four C programs that will be extremely beneficial to you as you test your shell implementation:

  • myspin.c: Sleeps for n seconds in 1-second chunks.
  • myint.c: Sleeps for n seconds and sends SIGINT to itself.
  • mystop.c: Sleeps for n seconds and sends SIGTSTP to itself.
  • mysplit.c: Fork a child process that sleeps for n seconds in 1-second chunks.

These programs will help you test the behavior of your shell while you work on it. The problem with “normal” programs, like /bin/ls, is that they usually consist of a single process that finishes immediately—so they aren’t very useful for testing the way background jobs behave. These small programs provide an artificial way to check that your shell’s job-control features work correctly.

These test programs sleep repeatedly for 1-second intervals. That means making n calls to the C sleep() function in a loop. The reason is that this strategy will make the programs more responsive to signals—they can handle signals between adjacent sleep() calls.

Step 1: myspin

Create a file called myspin.c.

Include the libraries stdio.h, unistd.h, and stdlib.h at the top of the file and write the main function:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <signal.h>

int main(int argc, char* argv[]) {
  return 0;
}

Build and run your program in the usual way. Name your executable myspin.

Now, write the main function. Running rv qemu myspin <N> should sleep for N seconds. Use the Unix sleep function. Your program should only sleep in one-second chunks: i.e., it should only ever call sleep(1).

You may also want to browse the C standard library headers for other useful functions.

Check-in with the TAs once you’ve finished this step.

Step 2: myint

Create a file called myint.c. You can start with the same header files as in the previous step.

This program should sleep for N seconds (again in 1-second chunks) and then send itself the SIGINT signal (which will cause the process to exit). You can copy the sleeping-related code from myspin.c.

Use the kill() function from signal.h to send the signal. (Contrary to the name, the kill() function can send any signal—not just SIGKILL.) The first argument to the kill() function is the process ID (pid) where the signal should be sent; the getpid() function function can help with this. The second argument is the signal to send; use the SIGINT macro for this value.

Test your program by building it and then running rv qemu myint 2 or similar. If you want to check that your program is actually getting interrupted, try this:

$ rv sh -c 'qemu myint 2 ; echo $?'

That uses [the special $? shell variable][exit-var] to check the exit code of the command. An exit code of 130 means that the process received SIGINT.

Step 3: mystop

Next, write mystop.c. It should work the same way as myint.c but send the SIGTSTP signal instead of SIGINT.

It is OK to copy code from myint.c. Build and test your program. (The exit status should be 0, so myint should appear to behave identically to myspin.)

Step 4: mysplit

Finally, write mysplit.c. This program should spawn a subprocess that sleeps for N seconds (again in 1-second chunks), and it should wait for that subprocess to exit.

Use the fork() function from unistd.h to launch a subprocess. Your program will need to behave differently in the parent process and in the child process. In the child process, use your same old sleep loop to wait for N seconds. In the parent process, use the waitpid() function to block until the child process finishes.

The waitpid() function takes three arguments: the process ID to wait for, an “out-parameter” stat_loc for the status of the subprocess, and an options parameter for extra flags. You don’t need either of the latter things, so you can pass a null pointer and 0 for them—so waitpid(your_child_process_id, NULL, 0) will suffice.

Build and test your program. It should work the same way as myspin, i.e., it should sleep for N seconds when you pass N as the command-line argument.

Here’s an idea you can use to check that your myspin is actually launching a subprocess:

$ rv sh -c 'qemu mysplit 5 & (sleep 1 ; ps ax)'

That launches mysplit in the background and then uses the ps command to list the processes running on the machine. If mysplit is working correctly, you should see two different qemu mysplit 5 processes running with different pids. If you try this with myspin instead, there should only be one corresponding process.

Task 1: Implement tsh

Your task is to implement a Tiny SHell, named tsh!

Your tsh implementation will have these features:

  • The prompt should be the string tsh> . (This is done for you!)
  • Handle commands consisting of lists of words, separated by one or more spaces. The first word is the command name. The remaining words are the arguments for that command. If the name is a known built-in command, then tsh should handle it internally. Otherwise, it assumes that it is the path to an executable file, which it loads and runs in a new child process. (The command must be a filesystem path, like /bin/ls, not just plain ls—your tsh does not need to have the “path search” feature that full-featured shells have.)
  • tsh does not need to support pipes (|) or I/O redirection (> and <). (You can try this for an extra challenge if you like!)
  • Typing control-C or control-Z should send a SIGINT (SIGSTP) signal to the current foreground job, as well as any descendants of that job (e.g., any child processes that it forked). If there is no foreground job, then these key combinations should have no effect.
  • If the command line ends with an ampersand &, then tsh should run the job in the background. Otherwise, it should run in the foreground.
  • The shell will assign a job ID (jid) to each job it launches. This jid is distinct from the process ID (pid) that the OS kernel assigns automatically to every new process. The shell will assign jids itself in sequential order. (We have provided all the functions you need to maintain the job list and jids: see addjob, for example.) When the user refers to jobs on the command line, use a % prefix: for example, %5 denotes jid 5. In contexts where both jids and pids are allowed, %5 is a jid and 5 means pid 5.
  • Support these built-in commands:
    • exit: Terminate the shell.
    • jobs: List all background jobs. For the exact output format, try running jobs in the reference implementation. Each line should look like [jid] (pid) Running <command>.
    • bg <job>: Resume <job> (which may be either a pid or a jid) by sending it the SIGCONT signal. Let the job run in the background.
    • fg <job>: Resume <job> as above, using SIGCONT, and then make it the foreground job. Foreground jobs can receive input from the user, so typing characters should send them to the current foreground job.
  • tsh should reap all of its zombie children. When a process exits, it remains in the kernel’s process table. You will need to use waitpid on all children to “reap” these zombies. You can detect that a child process was a zombie using the WIFEXITED macro (see the manual page for waitpid); then, remove it from your shell’s job list.
  • If any job terminates because it receives a signal that it didn’t handle, then tsh should recognize this event and print a message with the job’s pid and a description of the offending signal. The message should look like Job [jid] (pid) terminated by signal <n>. For examples, try the reference implementation.

Functions to Implement

You will need to write these functions, all in tsh.c:

  • void eval(char* cmdline): Evaluate a given command line.
  • int builtin_cmd(char** argv): If the command is a built-in command, execute it immediately. Otherwise, do nothing.
  • void do_bgfg(char** argv): Execute the built-in bg and fg commands.
  • void waitfg(pid_t pid): Block until process pid is no longer the foreground process.
  • void sigchld_handler(int sig): The kernel sends a SIGCHLD to the shell whenever a child job terminates, stops because it received a SIGSTOP or SIGTSTP signal. This handler should clean up child jobs which have terminated.
  • void sigint_handler(int sig): The kernel sends a SIGINT to the shell whenever the user types ctrl-c at the keyboard. Catch it and send it along to the foreground job.
  • void sigstp_handler(int sig): The kernel sends a SIGSTP to the shell whenever the user types ctrl-z at the keyboard. Catch it and send it along to the foreground job.

The division of labor between the first four functions is largely a suggestion. It is possible to implement all of the logic in eval, but we do not recommend this as it will be much harder for you to track down bugs and fix them. Separate the functionality between built-in commands, bg/fg, and other helper functions.

Hints

Helper Functions and APIs

There are many helper functions in tsh.c intended to help you manipulate command-line strings and the job list. Do not re-invent the wheel! Read the code and the functions we’ve provided before you start.

In addition, these functions (defined in signal.h, sys/wait.h, and/or unistd.h) will come in handy:

  • waitpid: waits for a child process to terminate. Note the WUNTRACED and WNOHANG options; they will be useful.
  • kill: sends a signal to a process or set of processes
  • fork: creates a child process
  • execve: executes a program
  • setpgid: sets process group ID
  • sigprocmask: sets blocked signals for the calling process

The manual pages for these functions have a lot of detail about how to use them.

One of the tricky parts of this assignment is deciding the allocation of work between waitfg and the sigchld_handler functions. Recall that waitfg blocks until process pid is no longer the foreground process, and sigchld_handler cleans up terminated child jobs when a SIGCHLD signal is received. We recommend doing this:

  • In waitfg, use a busy loop around the sleep function.
  • In sigchld_handler, use waitpid to check whether a process has stopped (either suspended, terminated, or exited).

Other solutions are possible, but they can get confusing.

Ideas For Handling Signals

In eval, the parent must use sigprocmask to block SIGCHLD signals before it forks the child, and then unblock these signals, again using sigprocmask after it adds the child to the job list by calling addjob. Since children inherit the blocked vectors of their parents, the child must be sure to then unblock SIGCHLD signals before it execs the new program.

Basically, all sigprocmask does is take a collection of signals and add them to a blocked set or an unblocked set. Why would we want to do this? In general, sometimes it is important to block signals in a critical section of code. In our case, we have a concrete example: the parent needs to block the SIGCHLD signals in this way in order to avoid the race condition where the child is reaped by sigchld_handler (and thus removed from the job list) before the parent calls addjob.

When you implement your signal handlers, be sure to send SIGINT and SIGTSTP signals to the entire foreground process group. The kill function’s first argument, pid, can be positive or negative: positive numbers kill a single process, and negative numbers kill an entire process group. Use -pid here.

When you run your program from a standard Unix shell, your shell is running in the foreground process group. If your shell then creates a child process, by default that child will also be a member of the foreground process group. Since typing control-C sends a SIGINT to every process in the foreground, typing control-C will send a SIGINT to your shell, as well as every process that your shell created, which obviously isn’t correct. Here is the workaround: after the fork but before the execve, the child process should call setpgid(0, 0), which puts the child in a new process group whose group ID is identical to the child’s pid. This ensures that there will only be one process, your shell, in the foreground process group. When you type control-C, the shell should catch the resulting SIGINT and then forward it to the appropriate foreground job.

When your shell receives SIGCHLD, this means that something happened in one of the jobs that you launched: the job either suspended, resumed after being suspended, was terminated, or exited normally. Unfortunately, there is no direct way to determine which job caused the SIGCHLD signal to raise. It might be the foreground job or it might be a background job that has exited or been terminated (“zombies”). However, given a job’s PID, you can tell what happened to it, using waitpid. Be sure to reap all child processes, i.e., call waitpid eventually on all processes, both the foreground job and the background zombies. You don’t need to worry about handling SIGCHLD signals that come from re-started jobs, since they’ll exit on their own (or be terminated) later.

Ideas For Debugging

If you ever want to explore how a given feature “should” work, you can try it in a “real” shell like bash or zsh, or run the reference shell we’ve provided (called tshref).

It is also a very good idea to try out your shell by hand, rather than relying ony on the shell driver and trace files (see below). While successful runs of those provide evidence that your solution is correct, they don’t help much when you need to find and fix a bug. Instead, try running your solution directly, with verbose mode turned on — rv qemu tsh -v — and trace the commands that are in one of the traces/trace*.txt files (ignoring the “echo” commands, of course, as well as the ones in all caps, which are just used by the sdriver.pl script). Specifically, look at the displayed response after you type each command.

Also, this is a setting in which your best bet is to add “scaffolding”, i.e. printf statements that help you to see the control flow of your program, as the more structured debugging with GDB will be difficult to use. When you do this, be sure to flush your output right away (fflush(stdout)); otherwise, the execution of parent and child processes won’t necessary display your statements when you expect them. In addition to adding these in your tsh.c code, try scaffolding some or all of your Task 0 programs, particularly myspin.c.

If you want to test your shell on certain executables like ls or echo, you can obtain the path to the binary by typing the command which ls in your “real” shell. (tsh does not support automatic path searching, so you need to type the full path to the ls executable file.)

Finally, programs such as more, less, vi, and emacs do strange things with terminal settings. Don’t run these programs from tsh—stick with simple text-based programs like ls, ps, and echo.

Running and Testing

We have provided some tools to help you check your work.

Reference Solution

The executable tshref is the reference solution for your shell. Run this program to resolve any questions about how your shell should behave. Your shell should emit output that is identical to the reference solution (except for pids, which the OS assigns and will change from run to run).

Use rv qemu tshref to run this reference implementation.

Shell Driver and Trace Files

The sdriver.pl program executes a shell as a child process, sends it commands and signals as directed by a trace file, and captures and displays the output from the shell. It is useful for testing your shell with a series of actions that would be tedious to type by hand.

Use the -h argument to learn about the usage of sdriver.pl:

$ rv ./sdriver.pl -h
Usage: /root/./sdriver.pl [-hv] -t <trace> -s <shellprog> -a <args>
Options:
  -h            Print this message
  -v            Be more verbose
  -t <trace>    Trace file
  -s <shell>    Shell program to test
  -a <args>     Shell arguments
  -g            Generate output for autograder

We have also provided 16 trace files (trace{01-16}.txt) that you will use in conjunction with the shell driver to test the correctness of the shell. The low-numbered trace files do very simple tests, and the higher-numbered traces do more complicated tests.

We recommend that you use the trace files to guide the development of your shell. Start with trace01.txt, and make your tsh produce identical output to our tshref reference implementation. Then move on to trace02.txt, and so on.

Let’s try running one trace file on your shell, tsh, and then on our reference implementation, tshref. The commands for trace01.txt look like this:

$ rv ./sdriver.pl -t trace01.txt -s tsh -a "-p"     # Use your `tsh`.
$ rv ./sdriver.pl -t trace01.txt -s tshref -a "-p"  # Use `tshref`.

We have provided a Makefile that makes these commands faster to type. Use these targets:

$ rv make test01   # Use your `tsh`.
$ rv make rtest01  # Use the reference `tshref`.

Look inside the trace files to understand how they work. Most lines are commands to run in the shell. There are special lines like SLEEP and INT that tell the driver to take certain actions, such as waiting or sending a signal to the shell process. INT simulates a control-C, and TSTP simulates a control-Z.

Submission

Submit your tsh.c via Gradescope.

Rubric

  • 40 points: Correctness on the given traces
  • 60 points: Correctness on additional, grading-only traces