code Build a shell to explore the process model.

• Checkpoint: complete Part 1 Friday, 29 April
• Due: 11:00pm Monday, 2 May
• Starter Code: fork wellesleycs240 / cs240-shell (just once!) and add bpw as admin. (Need help?)
• Submit:
  • Commit and push your final revision and double-check that you submitted the up-to-date version. (Need help?)
  • Do not submit a paper copy.
• Relevant Reference:
  • operating systems, process model
  • shells and signals
  • process lab
  • bash guide
  • C resources
  • debugging resources
  • Mercurial Team Workflow
  • Goshawk, M. Standard Book of Spells.
• Collaboration: Pair code assignment policy, as defined by the syllabus.

Contents

• Overview
  • Plan
  • Grading
  • Infrastructure
• Part 1: Wingardium Leviosa (Basics and Foreground Jobs)
  • Specification
  • Implementation
• Part 2: Evanesco (Background Jobs)
  • Background Jobs
  • jobs command
• (Optional Extra Credit) Part 3: Accio (Job Management)
  • Keyboard Interrupts
  • fg and bg
  • Polite Exit
• Expelliarmus: Getting Out of Trouble
• Expecto Patronum: OPTIONAL Shell Extensions

Overview

It’s time to build a shell! This is the first in a pair of core systems tools we will implement to wrap up 240: a shell and a memory allocator. You have been using the bash shell throughout this course and you now know enough to build a small shell yourself using C. 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 an interpreter for a small (or in the case of bash, not so small) command language as well as a prolific manager of processes. The goal of this assignment is to explore the process model, process management, and low-level systems programming. You have already implemented a parser for simple commands in the Pointer Potions assignment. In the course of completing your shell, you will:

• use process control features of the operating system (fork, execvp, waitpid, etc.)
• manage foreground and background processes
• use simple C data structures
• polish your 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

Plan

You will implement the shell in parts:

1. Wingardium Leviosa: basic built-in commands and foreground jobs.
2. Evanesco: background jobs.
3. (Optional, extra credit) Accio: built-in job management commands.

Grading

Please review notes returned with the Pointer Potions assignment before beginning to write code for this assignment. They contain valuable tips on designing clean, readable C code.

When grading, we will be looking for code that is:

• working according to the specifications given here – roughly 60%
• free of compiler warnings, memory errors, and memory leaks (run valgrind!) – roughly 15%
• well designed, well organized, and well documented – roughly 25%

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

Part 3 is worth up to 20% in extra credit. Optional extensions beyond may receive more extra credit. Talk to Ben if you are curious.

Infrastructure

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.

The starter code contains several files. You will modify shell.c.

• 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
• 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.

Part 1: Wingardium Leviosa (Basics and Foreground Jobs)

Like the shells you use daily, yours (surely you can think of a good name including “sh”) should issue a prompt (e.g., ->), at which it reads commands from the user and executes them. The top-level organization will be much like what we saw in class: a main loop that reads and executes commands in sequence.

The shell understands 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. One example is the exit command, which exits the shell.
• Executable commands are programs stored in the filesystem. Any command that is not built-in is assumed to refer to such a program. One example is the ls program, which lists the contents of the current working directory.

In this part, you will implement support for basic built-in shell commands and support for running arbitrary executable programs in the foreground. Advice for implementing these features and organizing your code follows.

Specification

Commands entered at the shell’s command prompt should behave as follows. Test out any of these in a regular shell for example behavior.

Built-in commands:

• exit exits the shell process
• help displays a message listing usage of all built-in shell commands
• cd changes the working directory of the shell to the path given as an argument or, if no argument is given, the directory path given by the HOME environment variable. Read man 2 chdir and man 3 getenv to get started.

Executable commands:

Typing any non-built-in command executes a program from the filesystem in a new foreground process using the functions for process management we have studied.

• The first word of the command line is the executable to run.
• The entire command array should become the arguments to this executable command.
• The executable should be located according to the PATH environment variable. Read the man page for the exec family of functions (run man 3 exec) to choose the variant of exec that will do this with minimal work.
• The argv passed to the exec function should be the entire command array from command_parse – it corresponds exactly to the argv you see in the main function of a C program.
• The shell should show the next command prompt when the command terminates.

For example: typing ls cs240-shell at the prompt should execute the /bin/ls command with the argument array containing "ls" followed by "cs240-shell". When the ls process has exited, the shell should print a new prompt.

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

Implementation

We highly recommend the following organization, to keep Part 2 simple. Some function arguments necessary for Part 2 appear in your starter code. Specifically, you will find some extra arguments (of type JobList*) in the provided function signatures. For now, ignore these, passing NULL in their place for any calls. They will be used later.

Shell Loop

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. It supports all of the command history and editing features you know from bash. Currently, the loop just parses the line, frees the line, prints the parsed command, and frees the parsed command. You will change this behavior to execute built-in and executable commands. The provided loop (and shell) exits only if the user types the Control-d key combination at a prompt, giving the special EOF (end-of-file or end-of-input) character. You will change this by implementing the explicit built-in exit command (and others).

Built-in Commands

Handle all built-in commands from within a single function, shell_builtin. (Feel free to create other helper functions and call them from here.) The main shell loop should call shell_builtin on a command to (a) determine if the command is built-in and (b) if so, do it.

If the given command is a built-in command, shell_builtin should execute that built-in command directly in the current process (by calling C code directly, not by forking or execing) and then return 1 (true). Otherwise it should return 0 (false). The strcmp function is useful (man strcmp, make sure to #include <string.h>).

Running Executables

If the command is not built-in, then the shell assumes it as an executable program. Put code to run an executable command in the function shell_run and helper function shell_wait_fg.

• shell_run should fork a new child process to execute the requested command. The parent (the shell) process should wait for the child process to terminate and then return to the next command prompt.

  The function should also do error-checking whenever using the system’s process management functions. You may find that additional helper functions used within shell_run are also useful. For now, you will implement only foreground processes, but later, you will grow this function to handle background processes as well.

• shell_wait_fg should wait for a foreground process with the given ID to exit. It should do error-checking and provide return values according to the specification given in the starter code comments. For now, this is mostly a thin wrapper around the standard functions for waiting. It will be convenient to have it wrapped up when we extend its functionality later.

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. The man pages (man 2 fork, man 3 execvp, man 2 waitpid, also available on the web) are a valuable resource for precise return values, etc. Pay special attention to the form of arguments these functions expect and how errors manifest when calling these functions.

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: Evanesco (Background Jobs)

In this part, you will add (A) support for launching and reaping background jobs and (B) a built-in command to list all jobs. Features in this part will use the provided JobList data structure and associated functions, documented in joblist.h and below. Read its documentation carefully and lean on its support as much as possible.

Background Jobs

Specification

An executable command followed by & should execute in the background (as reported by command_parse). Built-in commands are unaffected by &. Just as with foreground commands, a background executable command should be executed in a new child process. However, the behavior of the parent process after forking a background job differs in two ways:

1. The shell must print a summary of the background job and continue to the next command prompt immediately without waiting for the child process to complete. (See job_print.)

2. The shell must remember the background job (child process) and reap it after it terminates.

   • The shell must save each new background job in a list of jobs. (See job_save.)
     • Only background jobs should be reported on creation.
   • Before each command prompt, the shell should iterate through the saved jobs to reap, report, and remove any jobs that 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

• The shell should 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!)
• The shell must save each new background job in a list of jobs. (See job_save.)
• To simplify things for later, save every job, even foreground jobs.
  • Foreground jobs should be removed from the job list immediately upon completion. (See job_delete.)
  • Only background jobs should be reported on creation.
• Before each command prompt, the shell should reap, report, and remove any jobs that have terminated.
  • See job_iter, job_print, and job_delete for the JobList data structure.
  • Use the waitpid function to check to see if a process has exited. See the WNOHANG option and the return value of waitpid to allow waitpid to return even if the target process is not finished.

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 for the shell.)
• A Job structure stores information about a single job:
  • job ID (jid field);
  • process ID (pid field);
  • command array (command field);
  • and current execution status (status field).
    • JOB_STATUS_FOREGROUND – job is running in the foreground
    • JOB_STATUS_BACKGROUND – job is running in the background
    • JOB_STATUS_STOPPED – job is stopped (see Part 3)
    • JOB_STATUS_DONE – job has been reaped and 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. 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.)
• 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);

jobs command

Specification

Built-in command jobs reports all background and stopped jobs, 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) the job reaping/reporting done before command prompts, and (2) the explicit job reporting with jobs.
• See the provided job list code, especially job_iter, job_set_status, job_print, job_delete.

(Optional Extra Credit) Part 3: Accio (Job Management)

In this part, you will implement the following 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 should affect foreground commands only. They should never cause the shell (or any background commands) to terminate or stop.

• If a foreground command is running:
  • Control-C should abort the foreground command. The shell should return to a command prompt.
  • Control-Z should stop (pause) the foreground command. The shell should report that the command has been stopped, keep it in the jobs list, and return to a command prompt.
• If no foreground command is running:
  • Control-C should have no effect.
  • Control-Z should have 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 man 2 waitpid 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 to a stopped process will cause it to continue executing.
  • Use the kill function to do this. (man 2 kill)
  • 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.

Expelliarmus: Getting Out of Trouble

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.

Expecto Patronum: OPTIONAL Shell Extensions

The following are ideas for optional extensions to the shell if you just cannot stop.

• 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 < .c > -backup.c should cause the cat program to read its inputs from .c and write its output to the file .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 .c | wc should cause the output of cat .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.