code Build a shell to explore the process model.

• Assign: Monday, 24 April
• Due: 11:59pm Monday, 1 May
• Collaboration: Recommended Pair code assignment policy, as defined by the syllabus and honor code.
• Starter Code: (Need help?)
  1. If partnered: Designate one partner as the owner and grant the other partner write permission on the owner's cs240-shell-owner repository on Bitbucket.
  2. Everyone: hg clone ssh://hg@bitbucket.org/cs240codetub/cs240-shell-owner
  3. If partnered: In your repository working directory, run ./partner.py to record your partner's Bitbucket username.
• Submit: Commit and push your final revision and double check. (Need help?)
• Relevant Reference:
  • operating systems, process model
  • shells and signals
  • process lab
  • bash guide
  • C resources
  • debugging resources
  • Mercurial Team Workflow
  • M. Goshawk, Standard Book of Spells.
  • T. Sullivan, She sells C shells by the C shore...

Contents

• Overview
  • Setup
  • Tasks
  • Grading
• Part 1: Basics and Foreground Jobs (Wingardium Leviosa)
  • Shell Loop
  • Built-in Commands
  • Executable Commands
  • Reference
• Part 2: Background Jobs (Evanesco)
  • Background Jobs
  • jobs command
  • Job Lists
• Extra Credit Part 3: Job Management (Accio)
  • Keyboard Interrupts
  • fg and bg
  • Polite Exit
• Getting Out of Trouble (Expelliarmus)
• Extra Credit Part 4: Open-Ended Extensions (Expecto Patronum)

Overview

It’s time to build a shell! You have used the bash shell since the first CS 240 lab (if not earlier). You now know enough to build a small shell. Your shell, which should probably acquire a punny name containing “sh” by the time you are done building it, will provide basic functions familiar from bash.¹

A shell is a command language interpreter and a prolific manager of processes. The goal of this assignment is to explore the process model, process management, and systems programming. You implemented a parser for simple shell commands in the Pointer Potions assignment. In this assignment you will:

• use process control features of the operating system (fork, execvp, waitpid, etc.)
• manage basic concurrency of foreground and background processes
• use simple C data structures
• practice debugging skills
• think critically about how to implement a given specification
• read documentation to find relevant library functions
• increase your proficiency with C and basic systems programming

Setup

Use a CS 240 computing environment. The shell you build might work on similar (UNIX, Mac OS X, Cygwin) platforms (no guarantees!), but it must work on our platforms for grading.

Your Intermediate Dictionary of Spells contains the following files:

• Makefile: recipe for building the shell
• command.c, command.h: command-parsing library (Pointer Potions)
• joblist.c, joblist.h: data structure for managing background jobs
• shell.c: main shell implementation that you will edit
• terminal.c, terminal.h: wrappers for terminal setup

Compile the shell with make to produce an executable called shell. Run the shell with: ./shell. Exit the shell by typing Control-d (or exit, once you have implemented it). Remove all compiled files (including the executable) with make clean.

Tasks

Implement the shell in parts. Complete and test each part before reading or starting the next.

1. Required support for basic built-in commands and foreground jobs.
2. Required support for background jobs.
3. Extra Credit Optional support for job management.
4. Extra Credit Optional open-ended extensions.

Grading

Your grade is computed from 100 points, as follows:

• Correctness and completeness (70 points):
  • Your shell must implement the features described in the specification.
    • Built-in commands (15 points)
    • Foreground jobs (20 points)
    • Background jobs (20 points)
    • jobs command (15 points)
  • Perform extensive testing to increase your confidence in your shell’s correctness.
• Safety (15 points):
  • Your shell code must be free of compiler warnings, memory errors, and memory leaks (run valgrind!)
• Design, style, documentation (15 points):
  • Review notes in the Pointer Potions sample solutions for tips on designing clean, readable C code.
• Extra Credit Job management (+10 points)
• Extra Credit Open-ended extensions (+variable points)
  • Discuss with instructors.

If forced to choose, implement fewer features cleanly and correctly rather than more features sloppily or incorrectly.

Part 1: Basics and Foreground Jobs (Wingardium Leviosa)

In this part, you implement support for basic built-in shell commands and support for running arbitrary executable programs in the foreground. Each feature is described with two parts:

• The declarative specification describes the required behavior that you must implement: “The shell does X.”
• The imperative implementation guide recommends code structure and relevant library functions or system calls: “Call Y with Z. Documentation: …”

Test out any of these features in bash to understand expected behavior.

Shell Loop

Specification

At the top-level the shell is a loop that repeatedly:

1. Prints a prompt (e.g., ->).
2. Reads a command.
3. Executes that command.

The shell accepts two types of commands:

• Built-in commands are functions of the shell itself. They change or inspect the state of the shell without creating any new processes.
  • Example: the exit command exits the shell.
• Executable commands are executable programs from the filesystem run in a separate process. Any command that is not built-in is assumed to refer to an executable. All such commands are run in a single general way.
  • Example: the ls executable lists the contents of the current working directory.

Implementation

A top-level shell loop is provided in main. It uses the GNU readline library to print a prompt for the user and accept user input for a command line. The provided loop (and shell) exits if the user types the Control-D key combination at a prompt, sending the special EOF (end-of-file or end-of-input) character.

Currently, the provided loop parses a command line to a command array, frees the command line, prints the parsed command array, and frees the parsed command.

Replace printing with logic involving calls to two helper functions to be implemented below. Use the function shell_builtin to recognize and run built-in commands. Inspect its return value to determine if the command was built in. Use the function shell_run_job to run an executable command if the command is not built in. For now, pass NULL for the jobs argument to shell_run_job.

Built-in Commands

Specification

The shell accepts three built-in commands (more later).

• exit exits the shell process.
• help displays a message listing usage of all built-in commands your shell supports. Yes, this list. You will add more in Part 2)
• cd changes the working directory of the shell.
  • If a path is given as an argument, then cd uses the directory described by that path: cd cs240
  • If no argument is given, then cd uses the directory path given by the HOME environment variable.

Implementation

Implement a single function, shell_builtin, to handle all built-in commands directly in C code in the current process:

1. If the command is built in, do the command and return true.
2. If the command is not built in, return false.

Do not fork or exec. Feel free to create other helper functions and call them from here.

Documentation: strcmp(3) (mind the return value), exit(3), chdir(2), getenv(3).

Executable Commands

Specification

All non-built-in commands are executable commands that name executable programs on the filesystem to run in a separate process.

• The first word of the command line indicates the executable to run.
  • If the executable is given by name (e.g., ls) rather than by absolute or relative path (e.g., /bin/ls or ./runes), the shell finds the executable according to the PATH environment variable.
• The shell passes the entire command array as arguments to the executable.
• For foreground jobs (this part), the shell waits to print the next command prompt after the command terminates.

Example: given command ls cs240-shell, the shell executes the /bin/ls command in a new process, using the argument array containing "ls" followed by "cs240-shell". When the ls process has terminated, the shell prints a new prompt.

-> ls cs240-shell
Makefile    command.h   joblist.h   terminal.c
command.c   joblist.c   shell.c     terminal.h
->

Implementation

Implement a function, shell_run_job, to handle all executable commands. For now, ignore the jobs and foreground parameters. Implement a simple wrapper for waiting in shell_wait_fg.

• Fork a new child process in shell_run_job to execute the requested executable command.
  • In the parent process (the shell), wait for the child process to terminate using shell_wait_fg, then return.
  • In the child process, execute the requested executable with the entire command array as arguments.
• In shell_wait_fg, wait for the child process with the given PID to terminate. For now, shell_wait_fg is just an error-checking wrapper for a system call.
• Do error-checking for all system calls in the function that calls them. If the system call failed print an error and either exit the process with an error exit code.

Documentation: exit(3), fork(2), waitpid(2), execvp(3).

• Choose the exec variant that automatically finds the executable using PATH.
• Pay special attention to the form of arguments these functions expect and how errors manifest when calling these functions.

Review our discussion of the fork-exec-wait model from class (especially the shell loop and process management examples), plus the lab on processes. The textbook covers the same material, but it sometimes dives into details too quickly in this section.

Reference

Error-Checking

Remember to check the return values of functions like fork, exec, and waitpid to see if they succeeded or result in errors. There are no exceptions in C, so you must check for error return values explicitly. If one of these system calls results in an error, it sets a special global variable (errno) to indicate why. You can print a summary easily with the perror function. It takes a string, prints that string, and then prints a description of the error that occurred. In general, a system call failure means you should print the error and exit the current process immediately. For example:

pid_t pid = fork();
if (pid < 0) {
  // Fork system call failed.
  perror("fork");
  exit(-1);
} ...

Pay special attention to failures of the exec family of functions, especially if it seems like your shell requires you to type the exit command multiple times before finally exiting.

Memory Management

Both readline() and command_parse() allocate memory. You must be sure to free this memory when the code is done with it – think carefully about this. Try to balance timely freeing with centralized freeing: free this memory as soon as possible after the time it becomes obviously unneeded, but try to minimize the number of points in the code where freeing takes place. Avoid sprinkling free() calls around the program.

Use valgrind ./shell to check for memory errors. Valgrind will report memory accesses that fall outside the bounds of legal memory locations (local variables on the stack and allocated heap memory). It also prints a summary of memory leaks (allocated but unfreed memory) at program exit. Note that when your process forks, Valgrind goes with it – your process forks into two processes running under Valgrind. So if the child exits in error (e.g., trying to execute a nonexistent executable file), you may see an extra Valgrind exit message. Once you have successfully exec‘d, the new program will not be running under Valgrind.

Your shell should run without valgrind errors when you have finished each Part (with one exception). The one error that is OK is where some readline internals and Valgrind don’t see eye-to-eye. It will look something like this.

==1202== Syscall param sendmsg(msg.msg_name) points to uninitialised byte(s)
==1202==    at 0x362AAE9880: __sendmsg_nocancel (in /lib64/libc-2.12.so)
==1202==    by 0x362C215BF7: readline (in /lib64/libreadline.so.6.0)
...

Part 2: Background Jobs (Evanesco)

In this part, you add support for background jobs and a built-in command to list them.

Background Jobs

A job is a record of a process started by the shell.²

Specification

An executable command ending with & runs as a background command. Built-in commands are unaffected by &. The shell executes each background command in a new process like a foreground command, but unlike a foreground command:

1. The shell prints a summary of the background job, but does not wait for the child process to terminate before printing the next command prompt.
2. The shell remembers the child process and reaps the child process after it terminates.

To support these requirements for background jobs:

1. The shell saves each new background job in a list of pending jobs.
2. Before each command prompt, the shell reaps, reports, and removes any background jobs whose processes have terminated.

Example: the following shell interactions demonstrate background jobs.

-> sleep 30 &
[1]+ 4709  Running  sleep 30 &
-> sleep 55 &
[2]+ 4828  Running  sleep 55 &
-> echo she sells C shells by the C store
she sells C shells by the C store
-> echo world                    # ... >=30 seconds
world                            # after sleep 30 &
[1]  4709  Done     sleep 30 &
-> cd ..
-> man sleep
...
-> echo accio                    # ... >=55 seconds
accio                            # after sleep 55 &
[2]  4828  Done     sleep 55 &
->

Implementation

Immediately after reading this implementation guide, read the documentation of the provided JobList data structure and associated functions in joblist.h.

• Use a single JobList instance, created before the main shell loop begins.
• The JobList* parameters are for passing around a reference to this list. (Avoid global variables!)
• Save each new background job in a list of jobs. (See job_save.)
• Save every job, even foreground jobs. (Helps with Part 3.)
  • Remove foreground jobs from the job list immediately upon completion. (See job_delete.)
  • Report creation of background jobs only, not foreground jobs.
• Call a function at the end of the shell loop body to reap, report, and remove any background jobs whose processes have terminated.
  • See job_iter, job_set_status, job_print, and job_delete for the JobList data structure.
  • Use waitpid(2) to check if a process has terminated. Look up how to use the WNOHANG option and the return value of waitpid to allow waitpid to return even if the target process has not terminated.

System call documentation: waitpid(2). See WNOHANG.

jobs command

Specification

Built-in command jobs reports all background jobs (and stopped jobs in Part 3), along with their job ID, process ID, execution status, and command.

-> jobs
[1]  5498  Stopped  emacs shell.c
[3]  5502  Running  evince spells.pdf &
[4]  5504  Running  sleep 20 &

Implementation

• Reap completed jobs as part of the jobs command.
• Share code between two tasks:
  1. Job reaping/reporting done before command prompts.
  2. Explicit job reporting with jobs.
• See the provided job list code, especially job_iter, job_set_status, job_print, job_delete.

Job Lists

Use the provided data structures and functions declared and documented in joblist.h to save, track, and report jobs. There are two kinds of C structs comprising the job list data structure:

• A JobList structure stores a list of jobs. (You need exactly one JobList for the shell.)
• A Job structure stores information about a single job (an executable command that has been started by the shell):
  • job ID (jid field) – the shell’s short, memorable ID for this job;
  • process ID (pid field) – the operating system’s process ID for the process in which the job’s command was executed (pid≠jid);
  • command array (command field) – the command array used to start the job;
  • and job status (status field)
    • JOB_STATUS_FOREGROUND – process is running as a foreground job
    • JOB_STATUS_BACKGROUND – process is running as a background job
    • JOB_STATUS_STOPPED – process is stopped (paused, see Part 3)
    • JOB_STATUS_DONE – process has been reaped and the job is about to be deleted (transient state used only to affect job printing)

Both structures also track extra information used in managing linked lists, terminal interaction, keyboard interrupt signals, etc. (See Part 3.) Ignore any fields not listed above.

Do not create instances of these structures yourself. Do not read or manipulate fields of JobList structs directly. You may read fields of Job structs listed above (use the -> syntax), but any other operations on JobList or Job structs (including changes to job status) should be done via the provided functions.

Job list basics:

• joblist_create allocates and initializes a new JobList.
• joblist_empty returns 1 if the given list is empty and 0 otherwise.
• joblist_free frees a (presumed empty) JobList.

Managing individual jobs:

• job_save creates a new background Job with the given process ID, command, and status, assigns it the next available job ID, and saves it at the end of the list. If the job is not a foreground job, it also sets this Job as the “current” Job in the list. (More about “current” in Part 3.) The command array is saved by reference (not copied) as part of the job data structure.
  • Save a single command array in at most one job.
  • Do not free a command array after passing it to job_save. job_delete will handle that.
• job_get gets the Job for a given job ID.
• job_get_current gets the “current” Job in the list, if any.
• job_print prints a specific Job.
• job_set_status sets a Job’s status and sets the “current” Job in the list accordingly.
• job_delete removes a Job from the list and frees it and its command array (by calling command_free).
• job_iter iterates over a JobList, calling the given function (passed via function pointer) on each Job in the list.
  • A function pointer (K&R 5.11, p. 118) holds the address of a function, allowing functions to be passed as arguments to other functions. Note to those who have taken 251: function pointers are not closures. Any state used in the passed function must be passed explicitly as an argument.
  • job_iter allows you to pass a function (just give its name as an argument) for what to do with each Job, but it does not provide a way to build up any result by iterating over the list (because you should not need to do this!).

  • Example: prints each job in the list that has an even job ID.

    void printer(JobList* jobs, Job* job) {
      if ((job->jid % 2) == 0) {
        job_print(jobs, job);
      }
    }
    
    ... // somewhere in a function
    ... // where jobs is a JobList* ...
    job_iter(jobs, printer);

Extra Credit Part 3: Job Management (Accio)

This part requires a surface understanding of signals, which we likely did not cover in class. You implement built-in commands and other features to manage background, stopped, and foreground jobs, and support for keyboard interrupts.

1. Keyboard interrupts.
2. The built-in fg command.
3. The built-in bg command.
4. Polite exit.

Keyboard Interrupts

Control-C is used to send the SIGINT signal, which terminates a process by default. Control-Z sends the SIGTSTP signal, which causes a process to stop (a.k.a. pause) until explicitly resumed (continued).

Specification

In the shell, Control-C and Control-Z signals affect foreground commands only. They never cause the shell (or any background commands) to terminate or stop.

• If a foreground command is running:
  • Control-C aborts the foreground command. The shell return to a command prompt.
  • Control-Z stops (pauses) the foreground command. The shell reports that the command has been stopped, keeping it in the jobs list, and returns to a command prompt.
• If no foreground command is running:
  • Control-C has no effect.
  • Control-Z has no effect.

Implementation

Instead of writing a few complicated signal handlers yourself (this is error-prone), you will use provided code to “attach” the terminal (and the associated delivery of keyboard signals) to the current foreground process. Additionally, you will change how the shell waits for foreground jobs so that it can also notice when a job has been stopped via signals.

Terminals and Signals

The terminal (a.k.a. TTY) or terminal emulator (the window where you type to interact with the command line) is always attached to a particular foreground process or progress group. Keyboard input (including signals sent with Control-C and Control-Z) is sent to this process. The functions in terminal.h wrap up the necessary steps to manage which process receives these signals.

• term_shell_init sets up the shell’s interaction with the terminal and sets the shell process to ignore several signals, including SIGINT and SIGTSTP.

• term_child_init sets up a child process’s signal handlers and terminal interaction. The child process should call this function after being forked and before exec-ing the requested executable.

• term_give passes foreground status in the terminal from the shell to the new child process. The parent process should call this function after forking. The parent’s call to term_give and the child’s call to term_child_init cooperate to avoid timing problems. Both are necessary.

• term_take reclaims foreground status for the shell from the previous foreground process. The shell should call this function whenever it continues after waiting for a foreground job to finish or stop.

Updated Waiting

With signals attached to the foreground job, the shell’s existing behavior of waiting for the foreground process to finish in shell_wait_fg works as expected with minor modifications. shell_wait_fg should call waitpid such that it returns if the foreground process terminated or if it stopped.

• See the WUNTRACED option and use the macros described in waitpid(2) to determine what happened in the foreground process to allow waitpid to return.
• If the foreground process terminated by exiting normally or due to a signal, the shell should continue to the next command prompt as usual. Normal termination and termination by Control-C can be treated equivalently.
• If the foreground process was stopped instead of terminating, it was due to Control-Z. In this case, the shell should report the stopped job and retain it in the job list.

fg and bg

Specification

Built-in command fg brings a running background job to the foreground or resumes a stopped job by running it in the foreground, in addition to updating its status in the job list. Think about how this moving a job to the foreground is similar to starting a brand new job in the foreground. Try to share code accordingly.

• fg takes a job ID as an optional argument. If no job ID is given and there is a “current” job, fg should act on that job.
• If fg acts on the “current” job, then there is no longer a “current” job. (job_set_status implements this.)
• If no job with the given ID exists, an error should be printed.

Built-in command bg resumes a stopped job by running it in the background and updating its status in the job list.

• bg takes a job ID as an optional argument. If no job ID is given and there is a “current” job, bg should act on that job.
• bg prints a status message and sets its target job as the “current” job. (job_set_status implements this.)
• If the given job is already running in the background, the only effect is to set it as the “current” job.
• If no job with this ID exists, an error should be printed.

Implementation

• Tracking the “current” background job is handled automatically by job_set_status.
• You can get the current job (if any) by calling job_get_current on your jobs list.
• Sending the SIGCONT signal to a stopped process will cause it to continue executing.
  • Use the kill(2) function to do this.
  • Do not confuse job IDs and process IDs.
  • Instead of passing the desired process ID to kill, pass its negative (e.g., -pid) to send the signal to the entire process group root with that process.
  • Proper use of the functions from terminal.h ensures that each job’s process is the root of a process group with the same ID.

Polite Exit

Specification

When given the command exit or when the user types Control-D (EOF) at the prompt while any unfinished (and as yet unreapable) jobs remain running in the background or stopped, the shell should print the message There are unfinished jobs. and return to the command prompt without exiting.

Example

-> sleep 100
^Z[1]+ 16501  Stopped    sleep 100
-> sleep 20 &
[2]+ 16502  Running    sleep 20 &
-> jobs
[1]  16501  Stopped    sleep 100
[2]+ 16502  Running    sleep 20 &
-> bg 1
[1]+ 16501  Running    sleep 100
-> jobs
[1]+ 16501  Running    sleep 100 &
[2]  16502  Running    sleep 20 &
-> fg
sleep 100
^C-> exit
There are unfinished jobs.
[2]  16502  Running    sleep 20 &
-> jobs
[2]  16502  Done       sleep 20 &
-> exit

Implementation

Think about how to share code between this check and the case where you attempt to reap background jobs before each prompt. (See joblist_empty.) Note that the readline() function used in the main shell loop will return NULL (and hence control will leave the loop) when Control-D is entered at the prompt.

Getting Out of Trouble (Expelliarmus)

When building a shell (or other process-manipulating programs) it can be easy to end up in a tight spot. While building and debugging job control, chances are good that you will accidentally “lock yourself out” – your shell will get into a state where you can’t enter any commands and neither Control-C nor Control-Z will have any affect. Of course this should never happen… but it will. When disaster strikes, you can always just close your current terminal and open another one, but other tools might be more satisfying:

Open a second terminal and use these commands (not in your shell, in the normal shell…).

• top will show what processes are executing and using resources.
• ps ux will show all processes belonging to you, including their process IDs and execution status.
• kill lets you send signals to other processes you own. This can be useful for killing (or sending arbitrary signals to) your shell or processes you started from within your shell. Just be careful what you kill – don’t kill the instance of emacs where you are editing shell.c with many unsaved changes…
  • kill 12345 to politely terminate process with ID 12345
  • kill -9 12345 or kill -KILL 12345 to terminate it right now no matter what.
  • kill -INT 12345 to send the same signal Control-C sends.
  • kill -TSTP 12345 to send the same signal Control-Z sends.
  • kill -CONT 12345 to continue a stopped process.

Extra Credit Part 4: Open-Ended Extensions (Expecto Patronum)

The following are ideas for optional extensions to the shell if you just cannot stop. Talk to your instructor about ideas and extra credit.

• Customize the prompt to show the current working directory and/or time.

• A list of commands separated by semicolons should be executed in sequence.

    -> echo hello; echo world; echo hello
    hello
    world
    hello

• In addition to specifying that the preceding command should be launched in the background, an & acts like ;. Anything following & on the same command line is a separate command. For example: -> sleep 5 & ls should launch sleep 5 in the background, and then launch ls in the foreground.

    -> sleep 5 & sleep 10 & ls
    [1]+ 4123  Running  sleep 5 &
    [2]+ 4124  Running  sleep 10 &
    command.c shell.c
    -> jobs
    [1]  4123  Running  sleep 5 &
    [2]+ 4124  Running  sleep 10 &

• ~ expansion

  Most shells support the use of the ~ character as a shorthand for the current user’s home directory. Implement “tilde expansion” to emulate this behavior. The ~ should be expanded only if it appears at the beginning of a word. Use the getenv function to look up the value of the HOME environment

• quotes

  Most shells also support the use of quotes to delimit single “words” that contain spaces. For example, the command echo "hello... world" should be parsed into two words: echo and hello... world.

• The remaining extensions will require learning about file descriptors and, in some cases, changes to the Job and JobList data structure.

• Input and output redirection. For example:
  • -> cat < shell.c > shell.backup.c should cause the cat program to read its inputs from shell.c and write its output to the file shell.backup.c.
  • -> ls -l >> listings.txt should cause the output of ls -l to be appended to the end of the existing file listings.txt.
  • An individual command may only redirect input once and output once, but those redirections may be specified in any order.
    • -> > alines grep -i < Makefile a should be interpreted the same as the more usual -> grep -i a < Makefile > alines
• Pipes. For example:
  • -> cat shell.c | wc should cause the output of cat shell.c to be the input of wc.
  • The shell should support arbitrary length chains of pipes: -> ls -l *.c | grep "spells" | wc -l
  • Only the first command in a pipeline may have input redirection.
  • Only the last command in a pipeline may have output redirection.
  • Redirection of other commands should be reported as an ambiguous command line.
  • All of the processes in a pipeline should be treated as a single job, in a single process group.
• Build in a secret text adventure game.