18-213/18-613: Computer Systems, Summer 2024, Shell Lab: Writing Your Own Linux Shell
18-213/18-613, Summer 2024
Shell Lab: Writing Your Own Linux Shell
1 Introduction
The purpose of this assignment is to help you become more familiar with the concepts of process control and signalling. You’ll do this by writing a simple Linux shell program, tsh (tiny shell), that supports a simple form of job control and I/O redirection. Please read the whole writeup before starting.
2 Logistics
This is an individual project. All handins are electronic. You must do this lab assignment on a class shark machine.
To get your lab materials, click "Download Handout" on Autolab. Clone your repository on a Shark machine by running:
3 Overview
Looking at the tsh.c file, you will see that it contains a skeleton of a simple Linux shell. It will not, of course, function as a shell if you compile and run it now. To help you get started, we’ve provided you with a helper file, tsh_helper.{c,h}, which contains the implementation of routines that manipulate a job list, and a command line parser. Read the header file carefully to understand how to use it in your shell.
Your assignment is to complete the remaining empty functions listed below.
• eval: Main routine that parses, interprets, and executes the command line.
• sigchld_handler: Handles SIGCHLD signals.
• sigint_handler: Handles SIGINT signals (sent by Ctrl-C).
• sigtstp_handler: Handles SIGTSTP signals (sent by Ctrl-Z).
When you wish to test your shell, type make to recompile it. To run it, type tsh to the command line: 1
linux> ./tsh
tsh> [type commands to your shell here]
4 General Guidelines for Writing Your Shell
This section provides an overview of how you can start writing your shell. You should read Section 4: The tsh Specification, for a list of everything your shell should support and the format of all shell output.
-
A shell is an interactive command-line interpreter that runs programs on behalf of the user. A shell repeatedly prints a prompt, waits for a command line on stdin, and then carries out some action, as directed by the contents of the command line.
Each command consists of one or more words, the first of which is the name of an action to perform. This may either be the path to an executable file (e.g., tsh> /bin/ls), or a built-in command— a word with special meaning to the shell—(e.g., tsh> quit). Following this are command-line arguments to be passed to the command.
-
Built-in commands run within the shell’s process. Looking at the handout code, you may notice that it’s difficult to exit the program. Try making it respond to the word quit.
-
The child processes created as a result of interpreting a single command line are known collectively as a job. We just saw one type of job, a foreground job. However, sometimes a user wants to do more than one thing at once: in this case, they can instruct the shell not to wait for a command to terminate by instead running it as a background job. Looking back at the sequence of calls you made to implement foreground jobs, what do you think you would do differently to spawn a background job?
-
Given that your shell will need to support both types of job, consider refactoring your existing code to minimize the amount of duplication that will be necessary.
-
When children of your shell die, they must be reaped within a bounded amount of time. This means that you should not wait for a running foreground process to finish or for a user input to be entered before reaping. The sigchld_handler might be a good place to reap all your child processes.
-
The shell might want to track in-flight jobs and provide an interface for switching their status i.e. background to foreground, etc. Now might be a good time to read the api in tsh_helper.{c,h} and start maintaining a job list.
-
Typing Ctrl-C or Ctrl-Z causes a SIGINT or SIGTSTP signal, respectively. Your shell should catch the signals and forward them to the entire process group that contains the foreground job. If there is no foreground job, then these signals should have no effect.
2
-
When you run your shell from the standard Linux 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 Ctrl-C sends a SIGINT to every process in the foreground group, typing Ctrl-C will send a SIGINT to your shell, as well as to every process created by your shell. Obviously, this isn’t correct.
Here is a possible workaround: After the fork, but before the execve, you may want to think of a way to put the child in a new process group whose group ID is identical to the child’s PID. This would ensure that there will be only one process, your shell, in the foreground process group. Hint: man setpgid. 1
-
Remember that signal handlers run concurrently with the program and can interrupt it anywhere, unless you explicitly block the receipt of the signals. Be very careful about race conditions on the job list. To avoid race conditions, you should block any signals that might cause a signal handler to run any time you access or modify the job list.
Aside from these guidelines, you should use the trace files to guide the development of your shell. The trace files are in order of difficulty so it might not be the best to attempt a trace before passing all traces up to it.
5 The tsh Specification
Your tsh shell should have the following features:
• Each job can be identified by either a process ID (PID) or a job ID (JID). The latter is a positive integer assigned by tsh. JIDs are denoted on the command line with the prefix “%”. For example, “%5” denotes a JID of 5, and “5” denotes a PID of 5.
• tsh should support the following built-in commands:
– The quit command terminates the shell.
– The jobs command lists all background jobs.
– The bg job command resumes job by sending it a SIGCONT signal, and then runs it in the background. The job argument can be either a PID or a JID.
– The fg job command resumes job by sending it a SIGCONT signal, and then runs it in the foreground. The job argument can be either a PID or a JID.
• If the command line ends with an ampersand (&), then tsh should run the job in the background. Otherwise, it should run the job in the foreground. When starting a background job, tsh should print out the command line, prepended with the job ID and the process ID. For example:
[1] (32757) /bin/ls &
• Your shell should be able to handle SIGINT and SIGTSTP appropriately. If there is no foreground job,
then these signals should have no effect.
1With a real shell, the kernel will send SIGINT or SIGTSTP directly to each child process in the terminal foreground process group. The shell manages the membership of this group using the tcsetpgrp function, and manages the attributes of the terminal using the tcsetattr function. These functions are outside of the scope of the class, and you should not use them, as they will break the autograding scheme.
-
tsh should reap all of its zombie children. If any job terminates or stops because it receives a signal that it didn’t catch, then tsh should recognize that event and print a message with the job’s JID and PID, and the offending signal number. For example,
Job [1] (1778) terminated by signal 2 Job [2] (1836) stopped by signal 20 -
tsh should support I/O redirection (See Appendix C for more details). For example: tsh> /bin/cat < foo > bar
Your shell must support both input and output redirection in the same command line.
• Your shell should be able to redirect the output from the built-in jobs command. For example,tsh> jobs > foo
should write the output of jobs to the foo file. The reference shell supports output redirection for allbuilt-ins, but you are only required to implement it for jobs. • Your shell does not need to support pipes.
Checking Your Work
Running your shell. The best way to check your work is to run your shell from the command line. Your initial testing should be done manually from the command line. Run your shell, type commands to it, and see if you can break it. Use it to run real programs!
Reference solution. The 64-bit Linux executable tshref is the reference solution for the shell. Run this program (on a 64-bit machine) to resolve any questions you have about how your shell should behave. Your shell should emit output that is identical to the reference solution — except for PIDs, which change from run to run. (See the Evaluation section.)
Once you are confident that your shell is working, then you can begin to use some tools that we have provided to help you check your work more thoroughly. These are the same tools that the autograder will use when you submit your work for credit.
Trace interpreter. We have provided a set of trace files (trace*.txt) that validate the correctness of your shell. Each trace file tests a different shell feature. For example, does your shell recognize a particular built-in command? Does it respond correctly to the user typing a Ctrl-C?
The runtrace program (the trace interpreter) interprets a set of shell commands in a single trace file:
linux> ./runtrace -h
Usage: runtrace -f <file> -s <shellprog> [-hV]
Options:
-h
-s <shell>
-f <file>
-V
Print this message
Shell program to test (default ./tsh)
Trace file
Be more verbose
The neat thing about the trace files is that they generate the same output you would have gotten had you run your shell interactively (except for an initial comment that identifies the trace). For example:
4
linux> ./runtrace -f trace05.txt -s ./tsh
#
# trace05.txt - Run a background job.
#
tsh> ./myspin1 &
[1] (15849) ./myspin1 &
tsh> quit
The lower-numbered trace files do very simple tests, while the higher-numbered trace files do increasingly more complicated tests. The appendix contains a description of each of the trace files, as well as each of the commands used in the trace files.
Please note that runtrace creates a temporary directory runtrace.tmp, which is used to store the output of redirecting commands, and deletes it afterwards. However, if for some reason the directory is not deleted, then runtrace will refuse to run. In this case, it may be necessary to delete this directory manually.
Shell driver. After you have used runtrace to test your shell on each trace file individually, then you are ready to test your shell with the shell driver. The sdriver program uses runtrace to run your shell on each trace file, compares its output to the output produced by the reference shell, and displays the diff if they differ.
linux> ./sdriver -h
Usage: sdriver [-hV] [-s <shell> -t <tracenum> -i <iters>]
Options
-h
-i <iters>
-s <shell>
-t <n>
-V
Print this message.
Run each trace <iters> times (default 4)
Name of test shell (default ./tsh)
Run trace <n> only (default all)
Be more verbose.
Running the driver without any arguments tests your shell on all of the trace files. To help detect race conditions in your code, the driver runs each trace multiple times. You will need to pass each of the runs to get credit for a particular trace:
linux> ./sdriver
Running 3 iters of trace00.txt
1. Running trace00.txt...
2. Running trace00.txt...
3. Running trace00.txt...
Running 3 iters of trace01.txt
1. Running trace01.txt...
2. Running trace01.txt...
3. Running trace01.txt... Running 3 iters of trace32.txt
1. Running trace32.txt...
2. Running trace32.txt...
3. Running trace32.txt...
Summary: 33/33 correct traces
Use the optional -i argument to control the number of times the driver runs each trace file:
linux> ./sdriver -i 1
Running trace00.txt...
Running trace01.txt...
Running trace02.txt...
...
Running trace31.txt...
Running trace32.txt...
Summary: 33/33 correct traces
Use the optional -t argument to test a single trace file:
linux> ./sdriver -t 06
Running trace06.txt...
Success: The test and reference outputs for trace06.txt matched!
Use the optional -V argument to get more information about the test:
linux> ./sdriver -t 06 -V
Running trace06.txt...
Success: The test and reference outputs for trace06.txt matched!
Test output:
#
# trace06.txt - Run a foreground job and a background job.
#
tsh> ./myspin1 &
[1] (10276) ./myspin1 &
tsh> ./myspin2 1
Reference output:
#
# trace06.txt - Run a foreground job and a background job.
#
tsh> ./myspin1 &
[1] (10285) ./myspin1 &
tsh> ./myspin2 1
7 Hints
• Start early! Leave yourself plenty of time to debug your solution, as subtle problems in your shell are hard to find and fix.
• There are a lot of helpful code snippets in the textbook. It is OK to use them into your program, but make sure you understand every line of code that you are using. Please do not build your shell on top of code you do not understand!
-
Read the manual pages for all system calls that you make. Be sure to understand what their arguments and return/error values are.
-
Busy-waiting. It is forbidden to spin in a tight loop while waiting for a signal (e.g. “while (1);”). Doing so is a waste of CPU cycles. Nor is it appropriate to get around this by calling sleep inside a tight loop. Instead, you should use the sigsuspend function, which will sleep until a signal is received. Refer to the textbook or lecture slides for more information.
-
Reaping child processes. You should not call waitpid in multiple places. This will set you up for many potential race conditions, and will make your shell needlessly complicated. The WUNTRACED and WNOHANG options to waitpid will also be useful. Use man and your textbook to learn more about each of these functions.
-
Saving/restoring errno. Signal handlers should always properly save/restore the global variable errno to ensure that it is not corrupted, as described in Section 8.5.5 of the textbook. The driver checks for this explicitly, and it will print a warning if errno has been corrupted.
-
For the printf function specifically, the CS:APP library provides sio_printf as an async-signal- safe replacement, which you may wish to use in your shell. (See Section 8.5.5 in the textbook for information on async-signal-safety, and see the appendix for information about the functions provided by the CS:APP library.)
-
Error Handling. Your shell needs to handle error conditions appropriately, which depends on the error being handled. For example, if malloc fails, then your shell might as well exit; on the other hand, your shell should not exit just because the user entered an invalid filename. (See the section on style grading.)
• Programs such as top, less, vi, and emacs do strange things with the terminal settings. Don’t run these programs from your shell. Stick with simple text-based programs such as /bin/cat, /bin/ls, /bin/ps, and /bin/echo.
• Don’t use any system calls that manipulate terminal groups (e.g. tcsetpgrp), which will break the autograder.
8 Evaluation
Your score will be computed out of a maximum of 103 points based on the following distribution:
99 Correctness: 33 trace files at 3 pts each. In addition, if your solution passes the traces but is not actually correct (you hacked a way to get it to pass the traces, or there are race conditions), we will deduct correctness points (up to 20 percent!) during our read through of your code.
The most common thing we will be looking for is race conditions that you have simply plastered over, often using the sleep call. In general, your code should not have races, even if we remove all sleep calls.
4 Style points. We expect you to follow the style guidelines posted on the course website. For example, we expect you to check the return value of system calls and library functions, and handle any error conditions appropriately (see Appendix B for exemptions).
We expect you to break up large functions such as eval into smaller helper functions, to enhance readability and avoid duplicating code. We also expect you to write good comments. Some advice about commenting:
• Do begin your program file with a descriptive block comment that describes your shell.
• Do begin each routine with a block comment describing its role at a high level.
• Do preface related lines of code with a block comment.
• Do keep your lines within 80 characters.
• Don’t comment every single line of code.
You should also follow other guidelines of good style, such as using a consistent indenting style (don’t mix spaces and tabs!), using descriptive variable names, and grouping logically related blocks of code with whitespace.
Your solution shell will be tested for correctness on a 64-bit shark machine (the Autolab server), using the same driver and trace files that were included in your handout directory. Your shell should produce identical output on these traces as the reference shell, with only two exceptions:
• The PIDs can (and will) be different.
• The output of the /bin/ps commands in trace26.txt and trace27.txt will be different from run to run. However, the running states of any mysplit processes in the output of the /bin/ps command should be identical.
The driver deals with all of these subtleties when it checks for correctness.
9 Hand In Instructions
To receive a score, you will need to upload your submission to Autolab. The Autolab servers will run the same driver program that is provided to you. There are two ways you can submit your code to Autolab.
1. Running the make command will generate a tar file, tshlab-handin.tar. You can upload this file to the Autolab website.
2. If you are running on the Shark machines, you can submit from the command line by typing:
$ make submit
Keep in mind the following:
• You may handin as often as you like until the due date. However, you will only be graded on the last version you hand in.
• After you hand in, it takes a minute or two for the driver to run through multiple iterations of each trace file.
• Do not assume your submission will succeed! You should ALWAYS check that you received the expected score on Autolab. You can also check if there were any problems in the autograder output, which you can see by clicking on your autograded score in blue.
• As with all our lab assignments, we’ll be using a sophisticated cheat checker. Please don’t copy another student’s code. Start early, and if you get stuck, come see your instructors for help.
