linux shell代写 15-213/18-213/15-513, Summer 2018 Shell Lab: Writing Your Own Linux Shell

15-213/18-213/15-513, Summer 2018 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 Hand Out Instructions

Set up your GitHub Classroom repository at https://classroom.github.com/a/c-sCEDBs. Then do the following on a Shark machine:

• Clone the repository you just created with the command
linux> git@github.com:cmu15213m/tshlab-m18-<YOUR USERNAME>.git

• Type your name and Andrew ID in the header comment at the top of tsh.c.
• Type the command make to compile and link the driver, the trace interpreter, and the test routines.

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.

tsh helper.h contains the public interface of these functions, and tsh helper.c contains the imple- mentation with some private implementation details like the exact definition of the job t struct. You may not copy the definition of this struct in tsh.c to circumvent the API exposed by tsh helper.c. (See the appendix for more details.)

Your assignment is to complete the remaining empty functions listed below. As a sanity check for you, we’ve listed the approximate number of lines of code for each of these functions in our reference solution (which includes lots of comments — that’s a good thing).

• eval: Main routine that parses, interprets, and executes the command line. [300 lines, including helper functions]

1

• sigchld handler: Handles SIGCHLD signals. [80 lines]
• sigint handler: Handles SIGINT signals (sent by Ctrl-C). [15 lines]
• sigtstp handler: Handles SIGTSTP signals (sent by Ctrl-Z). [15 lines]

When you wish to test your shell, type make to recompile it. To run it, type tsh to the command line: linux> ./tsh

tsh> [type commands to your shell here]

3 General Overview of Linux Shells

A shell is an interactive command-line interpreter that runs programs on behalf of the user. A shell repeat- edly 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.

The command line is a sequence of ASCII text words delimited by whitespace. The first word in the command line is either the name of a built-in command or the pathname of an executable file. The remaining words are command-line arguments:

• If the first word is a built-in command, the shell immediately executes the command in the current process.
• Otherwise, the word is assumed to be the pathname of an executable program. In this case, the shell forks a child process, then loads and runs the program in the context of the child.

  The child processes created as a result of interpreting a single command line are known collectively as a job. In general, a job can consist of multiple child processes connected by Linux pipes. However, the shell you write in this lab need not support pipes.

  If the command line ends with an ampersand “&”, then the job runs in the background, which means that the shell does not wait for the job to terminate before printing the prompt and awaiting the next command line. Otherwise, the job runs in the foreground, which means that the shell waits for the job to terminate before awaiting the next command line. Thus, at any point in time, at most one job can be running in the foreground. However, an arbitrary number of jobs can run in the background.

  For example, typing the command line

  tsh> jobs
  causes the shell to execute the built-in jobs command. Typing the command line

  tsh> /bin/ls -l -d
  runs the /bin/ls program in the foreground. By convention, the shell will ensure that when /bin/ls

  begins executing its main routine

  int main(int argc, char *argv[])
  the argc and argv arguments have the following values:

2

  argc == 3
  argv[0] == "/bin/ls"
  argv[1] == "-l"
  argv[2] == "-d"

On the other hand, typing the command line

tsh> /bin/ls -l -d &
runs the /bin/ls program in the background.

Linux shells support the notion of job control, which allows users to move jobs back and forth between background and foreground, and to change the process state (running, stopped, or terminated) of the pro- cesses in a job. For example,

• Typing Ctrl-C causes a SIGINT signal to be delivered to each process in the foreground job. The default action for SIGINT is to terminate the process.
• Similarly,typingCtrl-ZcausesaSIGTSTPsignaltobedeliveredtoeachprocessintheforeground job. The default action for SIGTSTP is to place a process in the stopped state, where it remains until it is awakened by the receipt of a SIGCONT signal.

  Linux shells also provide various built-in commands that support job control. For example:

• jobs: List the running and stopped background jobs.
• bg job: Change a stopped background job into a running background job.
• fg job: Change a stopped or running background job into a running foreground job.

  Linux shells also support the notion of I/O redirection, which allows users to redirect stdin and stdout to files. For example, typing the command line

  tsh> /bin/ls > foo
  redirects the output of ls to a file called foo. Similarly,

  tsh> /bin/cat < foo
  will redirect the input of the /bin/cat command to the foo command, which will print the contents of

  the file foo.

4 The tsh Specification
Your tsh shell should have the following features:

• The prompt should be the string “tsh> ”.

3

• The command line typed by the user should consist of a name and zero or more arguments, all sepa- rated by one or more spaces. If name is a built-in command, then tsh should handle it immediately.

  Otherwise, tsh should assume that name is the path of an executable file, which it should load and run in the context of an initial child process. (In this context, the term job refers to this initial child process). If you are running system programs like ls, you will need to enter the full path (in this case /bin/ls), because your shell will not support search paths.

• tsh need not support pipes (|), but MUST support I/O redirection (“<” and “>”). For example: tsh> /bin/cat < foo > bar

  Your shell must support both input and output redirection in the same command line.

• TypingCtrl-CorCtrl-ZshouldcauseyourshelltosendaSIGINTorSIGTSTPsignal,respec- tively, 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 the signal should have no effect.
• 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.
• 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 &

• tsh should support the following built-in commands:
  • –  Thequitcommandterminatestheshell.
  • –  Thejobscommandlistsallbackgroundjobs.
  • –  The bg job command restarts 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 restarts 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.

• Your
tsh> jobs > foo

shell should be able to redirect the output from the built-in jobs command. For example,

should write the output of jobs to the foo file.

• 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

4

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

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
Options:

  -h
  -s <shell>
  -f <file>
  -V

-f <file> -s <shellprog> [-hV]

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:

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

5

Usage: sdriver [-hV]
Options

-h
-i <iters>

19. -s  <shell>
20. -t  <n>

-V

[-s <shell> -t <tracenum> -i <iters>]

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 trace02.txt 1. Running trace02.txt…
2. Running trace02.txt…
3. Running trace02.txt…

…

Running 3 iters of trace28.txt 1. Running trace28.txt…
2. Running trace28.txt…
3. Running trace28.txt… Running 3 iters of trace29.txt 1. Running trace29.txt…

  2. Running trace29txt...
  3. Running trace29.txt...

Summary: 30/30 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 trace28.txt...
  Running trace29.txt...

Summary: 30/30 correct
Use the optional -t argument to test a single trace file:

traces

6

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

6 Warnings

• Start early! Leave yourself plenty of time to debug your solution, as subtle problems in your shell are hard to find and fix.
• Remember that you cannot make any assumptions about the order of execution of the parent and child after forking. In particular, you cannot assume that the child will still be running when the parent returns from the fork. In fact, our driver has code that purposely introduces non-determinism in the order that the parent and child execute after forking.
• Also, remember that signal handlers run concurrently with the program and can interrupt it anywhere, unless you explicitly block the receipt of the signals. The driver uses techniques to amplify the occur- rence of incorrect behaviour caused by race conditions.
• Be especially 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. To enforce this, we have built checking code into the helper functions in tsh helper.c to make sure these signals are blocked.
• Remember that simply passing the tests multiple times does not prove the correctness of your shell. We will deduct correctness points (up to 20 percent!) if there are race conditions in your code, so it is in your best interest to find them before we do, through thorough inspection.
• 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.

7

• When children of your shell die, they must be reaped within a bounded amount of time. This means that you should wait for a running foreground process to finish or for a user input to be entered before reaping.
• You should not call waitpid in multiple places. This will set you up for many potential race condi- tions, and will make your shell needlessly complicated.
• Many commonly used functions, including printf, are not async-signal-safe; i.e., they should not be invoked from within signal handlers. Within your signal handlers, you must ensure that you only call syscalls and library functions that are async-signal-safe. (See Section 8.5.5 in the textbook for more details, and see the appendix on CS:APP functions.)
• Don’t use any system calls that manipulate terminal groups (e.g. tcsetpgrp), which will break the autograder.

  7 Hints

• Read and understand every word of Chapter 8 (Exceptional Control Flow) and Chapter 10 (System- level I/O) in the textbook.
• Read the code in tsh.c and tsh helper.h carefully before you start. Understand the high-level control flow; get familiar with the defined global variables and the helper routines. The tsh helper maintains a job list, which you should use, but does not expose its implementation. You should use the provided functions to access the job list and the job t struct. See the appendix for details.
• Play with your shell by typing in commands directly. Don’t make the mistake of running the trace generator and driver immediately. Develop some familiarity and intuition about how your shell works before testing it with the automated tools.
• Only after you have tested your shell directly from the command line and are fairly confident that it is correct should you start testing with runtrace and the driver programs.
• Use the trace files to guide the development of your shell. Starting with trace00.txt, make sure that your shell produces identical output as the reference shell. Then move on to trace file trace01.txt, and so on.
• Thewaitpid,kill,fork,execve,setpgid,sigprocmask,andsigsuspendfunctions will come in handy. The WUNTRACED and WNOHANG options to waitpid will also be useful. Use man and your textbook to learn more about each of these functions.
• When you implement your signal handlers, be sure to send SIGINT and SIGTSTP signals to the en- tire foreground process group, using “-pid” instead of “pid” in the argument to the kill function. The driver program specifically tests for this error.
• One of the tricky parts of the assignment is deciding on the allocation of work between the eval and sigchld handler functions when the shell is waiting for a foreground job to finish.
• Ineval,theparentmustusesigprocmasktoblockSIGCHLD,SIGINT,andSIGTSTPsignals before it forks the child, and then unblock these signals, again using sigprocmask after it adds the child to the job list by calling add job. Since children inherit the blocked vectors of their parents,

8

the child must be sure to then unblock these signals before it execs the new program. The child should also restore the default handlers for the signals that are ignored by the shell.

The parent needs to block signals in this way in order to avoid race conditions. For example, the child could be reaped by sigchld handler (and thus removed from the job list) before the parent calls add job). Section 8.5.6 explains some possible race conditions and how to avoid them by blocking signals explicitly.

• 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.
• WhenyourunyourshellfromthestandardLinuxshell,yourshellisrunningintheforegroundprocess 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 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 be only one process, your shell, in the foreground process group. When you type Ctrl-C, the shell should catch the resulting SIGINT and then forward it to the process group that contains the foreground job. 1

• Some traces looking for race conditions can actually detect output buffering in printf. You should use fflush(stdout) to flush any buffered output so that lines are printed in the correct order.

  (The convention on Unix is that by default, stdin and stdout are line-buffered when associated with a terminal, but fully-buffered (or block-buffered) otherwise. stderr is unbuffered by default. In our case, autograding causes stdout to be fully buffered.)

  8 Evaluation

  Your score will be computed out of a maximum of 100 points based on the following distribution:

  90 Correctness: 30 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), we will deduct correctness points 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.

  10 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 EVERY system call and library function, and handle any error conditions appropriately. (See the appendix on CS:APP functions.)

  1

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

9

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 simply comment each line.

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 trace19.txt, trace20.txt, and trace21.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

• Make sure you have included your name and Andrew ID in the header comment of tsh.c.
• Hand in your tsh.c file for credit by uploading it to Autolab. You may hand in as often as you like.

  You will be graded on the last version you hand in.
  (You should upload your tsh.c file directly to Autolab. Do not submit a handin.tar file for this

  lab.)

• After you hand in, it takes a minute or two for the driver to run through multiple iterations of each trace file.
• 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.

Good luck!

10

Appendix: Trace Files

The trace driver runs an instance of your shell in a child process and communicates with the shell interac- tively in a way that mimics the behavior of a user. To test the behavior of your shell, the trace driver reads in trace files that specify shell line commands that are actually sent to the shell, as well as a few special synchronization commands that are interpreted by the driver when handling the shell process. The trace files may also reference a number of shell test programs to perform various functions, and you may refer to the code and comments of these test programs for more information.

The format of the trace files is as follows:

• The comment character is #. Everything to the right of it on a line is ignored.
• Each trace file is written so that the output from the shell shows exactly what the user typed. We do this by using the /bin/echo program, which not only tests the shell’s ability to run programs, but also shows what the user typed. For example:

  /bin/echo -e tsh\076 ./myspin1 \046

  Note: \076 is the octal representation of >, and \046 is the octal representation of &. These are special shell metacharacters that need to be escaped in order to be passed to /bin/echo. This command will echo the string tsh> ./myspin1 &.

• There are also a few special commands which are used to synchronize the job (your shell) and the parent process (the driver) and to send Linux signals from the parent to the job. These are handled in your shell by the wrapper functions in wrapper.c.

  A wrapper is a function injected at link time around calls to a function. For instance, where your code calls fork, the linker will replace this call with an invocation of wrap fork, which in turn calls the real fork function. Some of those wrappers are configured to signal the driver and resume execution only when signaled.

11

The following table describes what each trace file tests on your shell against the reference solution.

NOTE: this table is provided so that you can quickly get a high level picture about the testing traces. The explanation here is over-simplified. To understand what exactly each trace file does, you need to read the trace files.

12

Appendix: CS:APP functions

The csapp.c file contains a number of useful functions described in the textbook. This code will be linked with your code, and so you can make use of any of these functions.

One useful type of function in csapp.c is wrapped versions of many of the functions you will use. These are named with an upper-case character as the first letter. For example, Fork is the wrapped version of the fork syscall. A wrapped function calls its core function and checks for errors. If any error is detected, it prints an error message and exits the program.

This exit-on-failure behavior is acceptable for most, but not all, of the code you will be writing. In particular, if running a certain command in your shell fails, then that should not terminate your entire shell. You must decide when it is appropriate to use the wrapped functions, and make sure to handle errors appropriately when necessary.

Another use of csapp.c is that it provides the SIO series of functions, which are async-signal-safe func- tions you can use to print output. In addition, the sio printf.c file provides an sio printf function that you can use to print formatted output. See the corresponding header files for more information.

Appendix: Opaque job t (as seen from tsh.c)

The job struct used in this lab, struct job t, is declared but not defined in tsh helper.h. That’s because for tsh.c, the definition of this struct is considered an implementation detail. Consequently, Consequently, although you may use pointers to a struct job t in tsh.c, you may not access the members of the struct.

On the other hand, the full definition of the struct is visible in tsh helper.c, which contains the imple- mentation of the functions declared in tsh helper.h. As a user, you should use those functions that take a pointer to a struct job t, instead of attempting to access the struct directly.

Cultural information: This sort of technique is often used in C libraries to encapsulate implementation details. For instance, since tsh.c does not need to know the layout of the struct, we can change it without needing to recompile tsh.c. All we need to do is link it with an updated tsh helper.o object file.

This is slightly pointless for this lab, since we are using static linking. But imagine updating a structure in a system provided library: this technique means that you don’t have to recompile all the programs (whose source you don’t always have), as long as the layout of a struct was not exposed to the library user.

Alternatively, we could have provided you with only the compiled version of tsh helper.o for this lab, which wouldn’t make the lab any more any more difficult. Though we have included the source file, tsh helper.c, for your perusal, you don’t need to examine its contents at all.

13