This chapter is from the book
This chapter is from the book
This chapter is from the book
10.7 Introduction to ladsh
To help illustrate many ideas discussed in this book, we develop a subset of a Unix command shell as the book progresses. At the end of the book, the shell will support
- Simple built-in commands
- Command execution
- I/O redirection (>, |, and so on)
- Job control
The full source code of the final version of this shell, called ladsh4.c, appears in Appendix B. As new features are added to ladsh, the changes to the source code are described in the text. To reduce the number of changes made between the versions, some early versions of the shell are a bit more complicated than they need to be. These extra complications make it easier to develop the shell later in the book, however, so please be patient. Just take those pieces on faith for now; we explain them all to you later in the book.
10.7.1 Running External Programs with ladsh
Here is the first (and simplest) version of ladsh, called ladsh1:
1: /* ladsh1.c */
2:
3: #include <ctype.h>
4: #include <errno.h>
5: #include <fcntl.h>
6: #include <signal.h>
7: #include <stdio.h>
8: #include <stdlib.h>
9: #include <string.h>
10: #include <sys/ioctl.h>
11: #include <sys/wait.h>
12: #include <unistd.h>
13:
14: #define MAX_COMMAND_LEN 250 /* max length of a single command
15: string */
16: #define JOB_STATUS_FORMAT "[%d] %-22s %.40s\n"
17:
18: struct jobSet {
19: struct job * head; /* head of list of running jobs */
20: struct job * fg; /* current foreground job */
21: };
22:
23: struct childProgram {
24: pid_t pid; /* 0 if exited */
25: char ** argv; /* program name and arguments */
26: };
27:
28: struct job {
29: int jobId; /* job number */
30: int numProgs; /* total number of programs in job */
31: int runningProgs; /* number of programs running */
32: char * text; /* name of job */
33: char * cmdBuf; /* buffer various argv's point into */
34: pid_t pgrp; /* process group ID for the job */
35: struct childProgram * progs; /* array of programs in job */
36: struct job * next; /* to track background commands */
37: };
38:
39: void freeJob(struct job * cmd) {
40: int i;
41:
42: for (i = 0; i < cmd->numProgs; i++) {
43: free(cmd->progs[i].argv);
44: }
45: free(cmd->progs);
46: if (cmd->text) free(cmd->text);
47: free(cmd->cmdBuf);
48: }
49:
50: int getCommand(FILE * source, char * command) {
51: if (source == stdin) {
52: printf("# ");
53: fflush(stdout);
54: }
55:
56: if (!fgets(command, MAX_COMMAND_LEN, source)) {
57: if (source == stdin) printf("\n");
58: return 1;
59: }
60:
61: /* remove trailing newline */
62: command[strlen(command) - 1] = '\0';
63:
64: return 0;
65: }
66:
67: /* Return cmd->numProgs as 0 if no command is present (e.g. an empty
68: line). If a valid command is found, commandPtr is set to point to
69: the beginning of the next command (if the original command had
70: more than one job associated with it) or NULL if no more
71: commands are present. */
72: int parseCommand(char ** commandPtr, struct job * job, int * isBg) {
73: char * command;
74: char * returnCommand = NULL;
75: char * src, * buf;
76: int argc = 0;
77: int done = 0;
78: int argvAlloced;
79: char quote = '\0';
80: int count;
81: struct childProgram * prog;
82:
83: /* skip leading white space */
84: while (**commandPtr && isspace(**commandPtr)) (*commandPtr)++;
85:
86: /* this handles empty lines and leading '#' characters */
87: if (!**commandPtr || (**commandPtr=='#')) {
88: job->numProgs = 0;
89: *commandPtr = NULL;
90: return 0;
91: }
92:
93: *isBg = 0;
94: job->numProgs = 1;
95: job->progs = malloc(sizeof(*job->progs));
96:
97: /* We set the argv elements to point inside of this string. The
98: memory is freed by freeJob().
99:
100: Getting clean memory relieves us of the task of NULL
101: terminating things and makes the rest of this look a bit
102: cleaner (though it is, admittedly, a tad less efficient) */
103: job->cmdBuf = command = calloc(1, strlen(*commandPtr) + 1);
104: job->text = NULL;
105:
106: prog = job->progs;
107:
108: argvAlloced = 5;
109: prog->argv = malloc(sizeof(*prog->argv) * argvAlloced);
110: prog->argv[0] = job->cmdBuf;
111:
112: buf = command;
113: src = *commandPtr;
114: while (*src && !done) {
115: if (quote == *src) {
116: quote = '\0';
117: } else if (quote) {
118: if (*src == '\\') {
119: src++;
120: if (!*src) {
121: fprintf(stderr,
122: "character expected after \\\n");
123: freeJob(job);
124: return 1;
125: }
126:
127: /* in shell, "\'" should yield \' */
128: if (*src != quote) *buf++ = '\\';
129: }
130: *buf++ = *src;
131: } else if (isspace(*src)) {
132: if (*prog->argv[argc]) {
133: buf++, argc++;
134: /* +1 here leaves room for the NULL which
135: ends argv */
136: if ((argc + 1) == argvAlloced) {
137: argvAlloced += 5;
138: prog->argv = realloc(prog->argv,
139: sizeof(*prog->argv) * argvAlloced);
140: }
141: prog->argv[argc] = buf;
142: }
143: } else switch (*src) {
144: case '"':
145: case '\'':
146: quote = *src;
147: break;
148:
149: case '#': /* comment */
150: done = 1;
151: break;
152:
153: case '&': /* background */
154: *isBg = 1;
155: case ';': /* multiple commands */
156: done = 1;
157: returnCommand = *commandPtr + (src - *commandPtr) + 1;
158: break;
159:
160: case '\\':
161: src++;
162: if (!*src) {
163: freeJob(job);
164: fprintf(stderr, "character expected after \\\n");
165: return 1;
166: }
167: /* fallthrough */
168: default:
169: *buf++ = *src;
170: }
171:
172: src++;
173: }
174:
175: if (*prog->argv[argc]) {
176: argc++;
177: }
178: if (!argc) {
179: freeJob(job);
180: return 0;
181: }
182: prog->argv[argc] = NULL;
183:
184: if (!returnCommand) {
185: job->text = malloc(strlen(*commandPtr) + 1);
186: strcpy(job->text, *commandPtr);
187: } else {
188: /* This leaves any trailing spaces, which is a bit sloppy */
189:
190: count = returnCommand - *commandPtr;
191: job->text = malloc(count + 1);
192: strncpy(job->text, *commandPtr, count);
193: job->text[count] = '\0';
194: }
195:
196: *commandPtr = returnCommand;
197:
198: return 0;
199: }
200:
201: int runCommand(struct job newJob, struct jobSet * jobList,
202: int inBg) {
203: struct job * job;
204:
205: /* handle built-ins here -- we don't fork() so we
206: can't background these very easily */
207: if (!strcmp(newJob.progs[0].argv[0], "exit")) {
208: /* this should return a real exit code */
209: exit(0);
210: } else if (!strcmp(newJob.progs[0].argv[0], "jobs")) {
211: for (job = jobList->head; job; job = job->next)
212: printf(JOB_STATUS_FORMAT, job->jobId, "Running",
213: job->text);
214: return 0;
215: }
216:
217: /* we only have one program per child job right now, so this is
218: easy */
219: if (!(newJob.progs[0].pid = fork())) {
220: execvp(newJob.progs[0].argv[0], newJob.progs[0].argv);
221: fprintf(stderr, "exec() of %s failed: %s\n",
222: newJob.progs[0].argv[0],
223: strerror(errno));
224: exit(1);
225: }
226:
227: /* put our child in its own process group */
228: setpgid(newJob.progs[0].pid, newJob.progs[0].pid);
229:
230: newJob.pgrp = newJob.progs[0].pid;
231:
232: /* find the ID for the job to use */
233: newJob.jobId = 1;
234: for (job = jobList->head; job; job = job->next)
235: if (job->jobId >= newJob.jobId)
236: newJob.jobId = job->jobId + 1;
237:
238: /* add the job to the list of running jobs */
239: if (!jobList->head) {
240: job = jobList->head = malloc(sizeof(*job));
241: } else {
242: for (job = jobList->head; job->next; job = job->next);
243: job->next = malloc(sizeof(*job));
244: job = job->next;
245: }
246:
247: *job = newJob;
248: job->next = NULL;
249: job->runningProgs = job->numProgs;
250:
251: if (inBg) {
252: /* we don't wait for background jobs to return -- append it
253: to the list of backgrounded jobs and leave it alone */
254:
255: printf("[%d] %d\n", job->jobId,
256: newJob.progs[newJob.numProgs - 1].pid);
257: } else {
258: jobList->fg = job;
259:
260: /* move the new process group into the foreground */
261:
262: if (tcsetpgrp(0, newJob.pgrp))
263: perror("tcsetpgrp");
264: }
265:
266: return 0;
267: }
268:
269: void removeJob(struct jobSet * jobList, struct job * job) {
270: struct job * prevJob;
271:
272: freeJob(job);
273: if (job == jobList->head) {
274: jobList->head = job->next;
275: } else {
276: prevJob = jobList->head;
277: while (prevJob->next != job) prevJob = prevJob->next;
278: prevJob->next = job->next;
279: }
280:
281: free(job);
282: }
283:
284: /* Checks to see if any background processes have exited -- if they
285: have, figure out why and see if a job has completed */
286: void checkJobs(struct jobSet * jobList) {
287: struct job * job;
288: pid_t childpid;
289: int status;
290: int progNum;
291:
292: while ((childpid = waitpid(-1, &status, WNOHANG)) > 0) {
293: for (job = jobList->head; job; job = job->next) {
294: progNum = 0;
295: while (progNum < job->numProgs &&
296: job->progs[progNum].pid != childpid)
297: progNum++;
298: if (progNum < job->numProgs) break;
299: }
300:
301: job->runningProgs--;
302: job->progs[progNum].pid = 0;
303:
304: if (!job->runningProgs) {
305: printf(JOB_STATUS_FORMAT, job->jobId, "Done",
306: job->text);
307: removeJob(jobList, job);
308: }
309: }
310:
311: if (childpid == -1 && errno != ECHILD)
312: perror("waitpid");
313: }
314:
315: int main(int argc, const char ** argv) {
316: char command[MAX_COMMAND_LEN + 1];
317: char * nextCommand = NULL;
318: struct jobSet jobList = { NULL, NULL };
319: struct job newJob;
320: FILE * input = stdin;
321: int i;
322: int status;
323: int inBg;
324:
325: if (argc > 2) {
326: fprintf(stderr, "unexpected arguments; usage: ladsh1 "
327: "<commands>\n");
328: exit(1);
329: } else if (argc == 2) {
330: input = fopen(argv[1], "r");
331: if (!input) {
332: perror("fopen");
333: exit(1);
334: }
335: }
336:
337: /* don't pay any attention to this signal; it just confuses
338: things and isn't really meant for shells anyway */
339: signal(SIGTTOU, SIG_IGN);
340:
341: while (1) {
342: if (!jobList.fg) {
343: /* no job is in the foreground */
344:
345: /* see if any background processes have exited */
346: checkJobs(&jobList);
347:
348: if (!nextCommand) {
349: if (getCommand(input, command)) break;
350: nextCommand = command;
351: }
352:
353: if (!parseCommand(&nextCommand, &newJob, &inBg) &&
354: newJob.numProgs) {
355: runCommand(newJob, &jobList, inBg);
356: }
357: } else {
358: /* a job is running in the foreground; wait for it */
359: i = 0;
360: while (!jobList.fg->progs[i].pid) i++;
361:
362: waitpid(jobList.fg->progs[i].pid, &status, 0);
363:
364: jobList.fg->runningProgs--;
365: jobList.fg->progs[i].pid = 0;
366:
367: if (!jobList.fg->runningProgs) {
368: /* child exited */
369:
370: removeJob(&jobList, jobList.fg);
371: jobList.fg = NULL;
372:
373: /* move the shell to the foreground */
374: if (tcsetpgrp(0, getpid()))
375: perror("tcsetpgrp");
376: }
377: }
378: }
379:
380: return 0;
381: }
This version does nothing more than run external programs with arguments, support # comments (everything after a # is ignored), and allow programs to be run in the background. It works as a shell script interpreter for simple scripts written using the #! notation, but it does not do much else. It is designed to mimic the usual shell interpreter used on Linux systems, although it is necessarily simplified.
First of all, let's look at the data structures it uses. Figure 10.2 illustrates the data structures ladsh1.c uses to keep track of child processes it runs, using a shell running grep in the background and links in the foreground as an example. struct jobSet describes a set of jobs that are running. It contains a linked list of jobs and a pointer to the job that is currently running in the foreground. If there is no foreground job, the pointer is NULL. ladsh1.c uses struct jobSet to keep track of all the jobs that are currently running as background tasks.
)
Figure 10.2 Job Data Structures for ladsh1.c
struct childProgram describes a single program being executed. This is not quite the same as a job; eventually, we will allow each job to be multiple programs tied together with pipes. For each child program, ladsh keeps track of the child's pid, the program that was run, and the command-line arguments. The first element of argv, argv[0], holds the name of the program that was run, which is also passed as the first argument to the child.
Multiple commands are tied into a single job by struct job. Each job has a job ID unique within the shell, an arbitrary number of programs that constitute the job (stored through progs, a pointer to an array of struct childProgram), and a pointer to another (next) job, which allows the jobs to be tied together in a linked list (which struct jobSet relies on). The job also keeps track of how many individual programs originally comprised the job and how many of those programs are still running (as all of a job's component processes may not quit at the same time). The remaining two members, text and cmdBuf, are used as buffers that contain various strings used in the struct childProgram structures contained by the job.
Much of struct jobSet is made up of dynamically allocated memory that should be freed when the job is complete. The first function in ladsh1.c, freeJob(), frees the memory used by a job.
The next function, getCommand(), reads a command from the user and returns the string. If the commands are being read from a file, no prompting is done (which is why the code compares the input file stream against stdin).
parseCommand() breaks a command string into a struct job for ladsh to use. The first argument is a pointer to a pointer to the command. If there are multiple commands in the string, this pointer is advanced to the beginning of the second command. It is set to NULL once the final command from the string has been parsed. This allows parseCommand() to parse only a single command on each invocation and allows the caller to easily parse the entire string through multiple calls. Note that multiple programs piped together do not count as separate commands—only programs separated by ; or & are independent of each other. As parseCommand() is simply an exercise in string parsing, we shall not go over it in any detail.
The runCommand() function is responsible for running a single job. It takes a struct job describing the job to run, the list of jobs that are currently running, and a flag telling it whether the job should be run in the foreground or the background.
For now, ladsh does not support pipes, so each job may consist of only a single program (although much of the infrastructure for supporting pipes is already present in ladsh1.c). If the user runs exit, we exit the program immediately. This is an example of a built-in command that must be run by the shell itself to get the proper behavior. Another built-in, jobs, is also implemented here.
If the command is not a built-in, we need to execute a child command. As each job can consist only of a single program (until we implement pipes), this is pretty straightforward.
219: if (!(newJob.progs[0].pid = fork())) {
220: execvp(newJob.progs[0].argv[0], newJob.progs[0].argv);
221: fprintf(stderr, "exec() of %s failed: %s\n",
222: newJob.progs[0].argv[0],
223: strerror(errno));
224: exit(1);
225: }
First of all, we fork() off the child process. The parent stores the child's pid in newJob.progs[0].pid, whereas the child process places a 0 there (remember, the parent and child have different memory images, although they are initially filled with the same values). This results in the child going into the body of the if statement while the parent skips the body. The child immediately runs the new program via execvp(). If the execvp() call fails, the child prints an error message and then exits. That is all that is necessary for spawning a simple child process.
After forking the child, the parent places the child into its own process group and records the job in the list of running jobs. If the process is meant to run in the foreground, the parent makes the new process group the foreground process group for the shell's controlling terminal.
The next function, checkJobs(), looks for background jobs that have exited and cleans up the list of running jobs as appropriate. For each process that has exited (remember waitpid() returns only information on exited processes unless WUNTRACED is specified), the shell
- Finds the job the process was a part of
- Marks the program as completed (by setting the stored pid for the program to 0) and reduces the number of running programs for the job by one
If the job containing the deceased process has no more running processes, which is always the case in this version of ladsh, the shell prints a message telling the user the process completed and removes the job from the list of background processes.
The main() routine for ladsh1.c controls the shell's execution flow. If an argument was passed to the shell when it was invoked, it treats that as a file name and reads subsequent commands from that file. Otherwise, stdin is used as the source of commands. The program then ignores the SIGTTOU signal. This is a bit of job-control magic that keeps things going smoothly, and it will make sense once you get to Chapter 15. Job control is not fully implemented, however, and when you are experimenting with ladsh1.c do not try job-control activities (especially those activities that involve suspending programs ladsh1.c has run); they simply will not work. A complete job-control implementation is added in Chapter 15; the setup here is only skeletal.
The remainder of main() is the main loop of the program. There is no exit condition for this loop; the program ends by calling exit() inside the runCommand() function.
The nextCommand variable points to the original (unparsed) string representation of the next command that should be run, or is NULL if the next command should be read from the input file, which is usually stdin. When no job is running in the foreground, ladsh calls checkJobs() to check for background jobs that have exited, reads the next command from the input file if nextCommand is NULL, and then parses and executes the next command.
When a foreground job is executing, ladsh1.c instead waits for one of the processes in the foreground job to terminate. Once all the processes in the foreground job have exited, the job is removed from the list of running jobs and ladsh1.c reads the next command as described previously.