Lab: Linux Shell

A Linux shell is a command line interpreter. A shell is a utility program that allows a user to enter commands such as cd, ls, cat, more, and gcc. The beauty of Unix/Linux is that a shell is a regular user program. It it not part of the OS. Some popular shells are bash, Z, and cshell. A shell uses the Unix/Linux API of fork, exec, pipes, and redirecting I/O. Most of the commands executed by a shell are simply programs that the shell runs via fork and exec system calls. Some of the commands are executed by the shell are internal code that is part of the shell.

All of the sections are so the label is not included on each section.

$ gcc -o redirect redirect.c
$ echo "hello redirect" > input.txt
$ ./redirect input.txt output.txt
$ cat output.txt
hello redirect

Starting the Lab

To start the lab, switch to the riscv branch:

  $ git fetch
  $ git checkout riscv
  $ cd shell
  

OS I/O API

The are various APIs for performing I/O. The I/O API provided by programming languages (e.g., C's fopen, fread, fwrite) are built on top of the OS I/O API. The OS I/O API consists of a few well defined interface functions. The Xv6 I/O API is the following. Linux has a few more (e.g. dup2), but for the most part the API is the same as it was 50 years ago.

int pipe(int*);
int write(int, const void*, int);
int read(int, void*, int);
int close(int);
int open(const char*, int);
int mknod(const char*, short, short);
int unlink(const char*);
int fstat(int fd, struct stat*);
int link(const char*, const char*);
int mkdir(const char*);
int chdir(const char*);
int dup(int);

open and pipe return integer file descriptors. read, write, and close use the file descriptors to manipulate the files/pipes.

File Descriptors and ofile Array

Xv6 creates a struct proc for each process. Xv6 uses the struct proc to manage the creation, execution, and termination of processes. Processes (or user programs) have an array, ofile, of pointers to open files in their struct proc. Whenever a process opens a file, the OS creates file information data structures, places a pointer to the file information in an element of the ofile array, and the index is returned to the user program as a file descriptor. See kernel/proc.h to examine the ofile array in struct proc.

This means that file descriptors are little integers like 0, 1, 2, up to the number of elements in the array. Processes use file descriptors to perform operations like read, write and close.

When a process opens a file, the OS sequentially searches for a free entry in the ofile array beginning at ofile[0] The following shows an open-read-close scenario of using file descriptors.

int fd1 = open("Gusty","r");       // file descriptor
char buf[25];
int numread = read(fd1, buf, 25);  // read using fd
int fd2 = open("Coletta", "r");
close(fd1);
int fd3 = open("Opal", "r");

In this scenario,

• The variable fd1 will have the value 3 because ofile[3] is the first free entry in ofile.
• The variable fd2 will have the value 4 because ofile[4] is the first free entry in ofile.
• The variable fd3 will have the value 3 because closing fd1 frees up ofile[3] to be reused.

When a process is created, three files are automatically opened - standard input, standard output, and standard error - and their file information pointers are placed in the ofile array in index positions 0, 1, and 2. This means file descriptors 0, 1, and 2 are allocated to STDIN, STDOUT, and STDERR. By default standard input is the user's typed commands, standard output consists of prints to the terminal window, and standard error consists of errors to the terminal window. This means when a process is created it can used file descriptors 0, 1, and 2 to read/write to the terminal's keyboard/window. The following simple program demonstrates reading from standard input and writing to standard output. Notice how printf and fgets calls do not require the user program to open standard input and standard output. They are already open. The code is provided in shell0.c.

#include <stdio.h>
#include <string.h>

#define MAX_BUF 100
char buf[MAX_BUF];

int main(int argc, char **argv) {
    while (1) {
        printf("$ ");                      // write to standard output
        memset(buf, 0, MAX_BUF);
        if (!(fgets(buf, MAX_BUF, stdin))) // read from standard input
            return -1;
        printf("You typed: %s\n", buf);
    }
}

#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>

#define MAX_BUF 100
char buf[MAX_BUF];

int main(int argc, char **argv) {
    while (1) {
        write(1, "$ ", 2);
        memset(buf, 0, MAX_BUF);
        int numread = read(1, buf, MAX_BUF);
        if (numread == -1)
            return -1;
        else if (numread == 0)
            return 0;
        write(1, "You typed: ", 11);
        write(1, buf, numread);
    }
}

File Descriptors and fork

Shell and I/O Redirection

A shell (such as bash) runs user programs such as cat, grep, and ls as child processes. These user programs typically read from standard input and write to standard output. For example, cat file.c displays the contents of file.c in the terminal window, which is STDOUT. With user programs writing to STDOUT (file descriptor 1), the shell can redirect the output of the user program to another file by closing file descriptor 1 (STDOUT) and opening another file, which will be allocated file descriptor 1. Likewise a shell can redirect the input to a user program by closing file descriptor 0 (STDIN) and opening another file, which will be allocated file descriptor 0. The same user program that normall reads/writes from/to STDIN/STDOUT now reads/writes to files. The following code demonstrates this concept, where the program is run with argument 1 as an input filename and argument 2 as an output filename. The code is provided in redirect.c.

int main(int argc, char **argv) {
    close(0);
    open(argv[1], O_RDONLY, 0644);
    close(1);
    open(argv[2], O_CREAT|O_TRUNC|O_WRONLY, 0644);
    char line[100];
    fgets(line, 100, stdin);
    printf("%s\n", line);
}

$ gcc -o redirect redirect.c
$ echo "hello redirect" > input.txt
$ ./redirect input.txt output.txt
$ cat output.txt
hello redirect

dup and dup2 System Calls

The dup and dup2 system calls can be used to redirect STDIN and STDOUT to other files.

int dup(int oldfd);
int dup2(int oldfd, int newfd);

Let's first understand the dup function. The dup system call creates a copy of the file descriptor oldfd, using the lowest-numbered unused file descriptor for the new descriptor. After a successful return, the old and new file descriptors may be used interchangeably. They refer to the same open file description (see open) and thus share file offset and file status flags; for example, if the file offset is modified by using lseek on one of the file descriptors, the offset is also changed for the other.

The dup2 system call performs the same task as dup, but instead of using the lowest-numbered unused file descriptor, it uses the file descriptor number specified in newfd. If the file descriptor newfd was previously open, it is silently closed before being reused. The steps of closing and reusing the file descriptor newfd are performed atomically. This is important, because trying to implement equivalent functionality using close and dup could be subject to race conditions when used in threaded processes, whereby newfd might be reused between the two steps. Such reuse could happen because the main program is interrupted by a signal handler that allocates a file descriptor, or because a parallel thread allocates a file descriptor.

The following code shows how to use dup2 to redirect STDIN and STDOUT from/to files. The code is provided in redirect_dup.c.

#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

int main(int argc, char **argv) {
    int pid, status;
    int infd, outfd;

    infd = open(argv[1], O_RDONLY, 0644);
    outfd = open(argv[2], O_CREAT|O_TRUNC|O_WRONLY, 0644);
    dup2(infd,  0);
    dup2(outfd, 1);
    char line[100];
    fgets(line, 100, stdin);
    printf("%s\n", line);
}

Note this sample uses argc and argv to get the redirection files. It does not use the redirect arrows like a shell. The following is an example of redirection of output using the shell.

$ cat test.txt > cat.txt

Linux Pipes and Shell's Use of Them

A shell supports piping the output of one program to the input of another. You can pipe the output of ls to grep as follows.

$ ls | grep redirect
redirect_input.txt
redirect_output.txt
redirect_stdout
redirect_stdout.c

In the above example, my directory had several files with redirect as part of their names. A shell achieves piping by using the system call pipe along with fork and exec.

A Linux pipe is a buffer that allows processes to exchange information. The pipe has two ends - processes can write to one end and can read from the other end. The pipe system call creates a pipe and returns two file descriptors in a two-element integer array.

int p[2];
int status = pipe(p); // p has pipe FDs

The input file descriptor is in p[0] and the output file descriptor is in p[1]. Notice that STDIN is file descriptor 0 and p[0] is the input end of the pipe. Likewise, STDOUT is file descriptor 1 and p[1] is the output end of the pipe.

The following code shows creating a pipe, writing to the output file descriptor, and reading from the input file descriptor. The code is provided in file simple_pipe.c.

// Code from https://www.geeksforgeeks.org/pipe-system-call/
#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h>
#define MSGSIZE 16 
char* msg1 = "hello, world #1"; 
char* msg2 = "hello, world #2"; 
char* msg3 = "hello, world #3"; 
  
int main() { 
    char inbuf[MSGSIZE]; 
    int p[2], i; 
    if (pipe(p) < 0) 
        exit(1); 
    write(p[1], msg1, MSGSIZE); 
    write(p[1], msg2, MSGSIZE); 
    write(p[1], msg3, MSGSIZE); 
    for (i = 0; i < 3; i++) { 
        read(p[0], inbuf, MSGSIZE); 
        printf("%s\n", inbuf); 
    } 
    return 0; 
} 

The following code connects two processes (parent and child) with two pipes. The code is provided in file parent_child_pipe.c. The parent writes to the first pipe and the child reads from the first pipe. The child writes to the second pipe and the parent reads from the second pipe. Notice how a process closes the ends of pipes that are not used.

#include <stdio.h> 
#include <stdlib.h> 
#include <unistd.h> 
#include <sys/types.h> 
#include <string.h> 
#include <sys/wait.h> 

int main() { 
    // First pipe to send input string from parent to child
    // Second pipe to send concatenated string from child to parent
    int fd1[2]; // Used to store two ends of first pipe 
    int fd2[2]; // Used to store two ends of second pipe 
    char fixed_str[] = " CPSC 405";
    char input_str[100]; 
    pid_t p; 
    if (pipe(fd1)==-1) { 
        fprintf(stderr, "Pipe Failed" ); 
        return 1; 
    } 
    if (pipe(fd2)==-1) { 
        fprintf(stderr, "Pipe Failed" ); 
        return 1; 
    } 
    scanf("%s", input_str); 
    p = fork(); 
    if (p < 0) { 
        fprintf(stderr, "fork Failed" ); 
        return 1; 
    } else if (p > 0) { // Parent process 
        char concat_str[100]; 
        close(fd1[0]); // Close read end of first pipe 
        write(fd1[1], input_str, strlen(input_str)+1); // write input string
        close(fd1[1]); // close write end of first pipe
        wait(NULL);    // Wait for child to send a string 
        close(fd2[1]); // Close write end of second pipe 

        read(fd2[0], concat_str, 100); // Read from child
        printf("Concatenated string: %s \n", concat_str); 
        close(fd2[0]);  // close reading end
    } else { // child process 
        close(fd1[1]); // Close write end of first pipe 
        char concat_str[100]; 
        read(fd1[0], concat_str, 100); // Read string using first pipe 

        int k = strlen(concat_str); // Concatenate a fixed string with it 
        for (int i=0; i < strlen(fixed_str); i++) 
            concat_str[k++] = fixed_str[i]; 
        concat_str[k] = '\0'; // string ends with '\0' 

        close(fd1[0]); // Close both reading ends 
        close(fd2[0]); 
        write(fd2[1], concat_str, strlen(concat_str)+1); // write concatenated string 
        close(fd2[1]); // Close write end of second pipe
        exit(0); 
    } 
} 

It it important to close the ends of the pipe that a process is not using. You can see this in the above code and also in the codes shell2.c, shell3.c, and shell4.c. Suppose you have two processes where one is writing to the pipe and the other is reading. The pipe reader will read until there is no more data in the pipe, which is equivalent to an end of file in a regular file. Note that when two processes are connected via a pipe, both processes have both ends of the pipe open. If the pipe writer does not close the read end of the pipe, the pipe reader will never get the end of file.

Consider a shell that executes cat file | grep hello. The shell created two processes connected by a pipe. The cat file process dups STDOUT onto the write end of the pipe and closes both ends of the pipe. The grep hello process dups STDIN onto the read end of the pipe and cloasses both ends of the pipe. grep will read from STDIN until an end of file is encountered, which occurs when cat has finished copying file to STDOUT.

The following shows running parent_child_pipe. I typed Hello, which is read by the parent, which writes it to a pipe, which is read by the child, which concatenates it to CPSC 405, which writes it to a pipe, which is read by the parent, which prints the final string to STDOUT.

$ ./parent_child_pipe
Hello
Concatenated string: Hello CPSC 405

Shell Commands - Native and Local

NOTE: I use the generic exec in the following paragraphs. Linux has a family of exec functions.

When you type a command in a Linux shell, the shell performs a fork followed by and exec of the command. For example, if you entered the ls command, the shell would do an exec(ls). The exec uses the environment variables established by the shell. One of the environment variables is PATH, which contains a comma separated list of directories to search for programs. The PATH variable contains directories such as /bin and /usr/bin. This means exec(ls) executes the ls program located in the /bin directory. The ls program is a C program whose executable has been placed in the /bin directory. We have a simple version of ls in our Xv6 user directory.

Many Linux utility programs have been created and placed in /bin and /usr/bin for you. I refer to these programs as native. When you want to run a local program in the current directory, you enter ./program. The nomenclature ./ selects the current directory, which is the dot directory.

You can add your own programs to a directory such as ~/bin and then add ~/bin to your PATH variable. Then you can add your own programs. If you add a program named ls to your ~/bin, the search order of your PATH variable determines which one runs. If /bin is first in your PATH, then the native ls runs.

The following shows running a native ls and a local ls.

$ ls -slag
ls -slag
total 160
 0 drwxr-xr-x   9 staff    288 Dec 17 21:11 .
 0 drwxr-xr-x  18 staff    576 Dec 20 17:11 ..
16 -rw-r--r--@  1 staff   6148 Dec 17 20:42 .DS_Store
32 -rwxr-xr-x   1 staff  13948 Dec 17 20:41 cat
16 -rw-r--r--   1 staff   4754 Dec 10 20:30 cat.c
40 -rwxr-xr-x   1 staff  18860 Dec 17 20:41 ls
24 -rw-r--r--@  1 staff  10767 Dec  9 21:46 ls.c
32 -rwxr-xr-x   1 staff  14572 Dec 17 21:10 mainshell
 0 drwxr-xr-x@  9 staff    288 Dec 17 21:11 simple-shell-master
$ ./ls -l
-rwxr-xr-x 1      gusty      staff     13948 Dec 17 20:41 cat
-rw-r--r-- 1      gusty      staff      4754 Dec 10 20:30 cat.c
-rwxr-xr-x 1      gusty      staff     18860 Dec 17 20:41 ls
-rw-r--r-- 1      gusty      staff     10767 Dec  9 21:46 ls.c
-rwxr-xr-x 1      gusty      staff     14572 Dec 17 21:10 mainshell
drwxr-xr-x 9      gusty      staff       288 Dec 17 21:11 simple-shell-master

You could place the dot directory in your path. Then you can run local programs without the ./ prefix. I do not do this because I want to explicitly select my current directory and not accidently run a local program when I meant to run a native program.

Pipes and Redirection

The following shows piping a local ls program into the Linux grep command.

$ ./ls | grep sim
simple-shell-master
simple_pipe
simple_pipe.c

The following shows piping a local ls program into the Linux grep command and redirecting the output to a file.

$ ./ls | grep sim > localls_grep.txt
 grep sim > localls_grep.txt
$ cat localls_grep.txt
cat localls_grep.txt
simple-shell-master
simple_pipe
simple_pipe.c

Background Processes

Shells allow users to run a program as a background process. When doing this, the program is run as a process in the background and the shell continues. To run programs in the foreground, the shell performs a fork followed by exec followed by wait to wait for the command to finish before continugin. In the case of a background process, the shell does not call wait, which means the execed process runs in the backgroud. In this case, the shell starts the program as a process in the background and returns a prompt for more user input. The following shows running parent_child_pipe as a background process.

$ ./parent_child_pipe &
[1] 15725
Gustys-iMac:ShellProject gusty$ ps
  PID TTY           TIME CMD
15717 ttys000    0:00.03 -bash
15725 ttys000    0:00.00 ./parent_child_pipe
  438 ttys001    0:00.01 -bash
  459 ttys002    0:00.02 -bash
 5271 ttys002    0:00.12 python
 3451 ttys003    0:00.21 -bash

Reading Commands

A shell program is in an endless loop that terminates when the user enters Ctl-D or exit. On each iteration of the loop, the shell reads a line that has several strings separated by whitespace. For example, the user may enter

$ ls     > out.txt. 

#include <stdio.h> 
#include <string.h> 

char buf[100]; // buffer for line
char whitespace[] = " \t\r\n\v";
char *words_on_line[10]; // 10 words on a line

int main(int argc, char **argv) {
    int stop = 0;
    while (1) {
        fgets(buf, 100, stdin);
        char *s = buf;
        char *end_buf = buf + strlen(buf);
        int eol = 0, i = 0;
        while (1) {
            while (s < end_buf && strchr(whitespace, *s))
                s++;
            if (*s == 0) // eol - done
                break;
            words_on_line[i++] = s;
            while (s < end_buf && !strchr(whitespace, *s))
                s++;
            *s = 0;
        }
        for (int j = 0; j < i; j++)
            printf("words_on_line[%d]: %s\n", j, words_on_line[j]);
        if (strcmp(words_on_line[0],"stop") == 0)
            break;
    }
}

Stepwise Development of Shells

You have been provided with five iterations of developing a shell. shell0.c is the simplest and shell4.c is the most complete. Note that shell4.c is still a long ways from being a real shell, which has environment variables, shell scripts, tab completion, the ability to string multiple pipes on a line, and more.

By the time you study shell4.c, you will encouter a shell that has the following features.

• The shell runs programs (both native and local) via fork and exec.
• The shell implements I/O redirection with < and >. The shell only supports either output redirection or input redirection on a line - not both on the same line.
• The shell allows connecting two commands with a pipe (|) charactoer. A typical Linux shell allows stringing pipes together - for example, ls | grep toy | grep cup. Processing an arbitrary number of pipes complicates the design. Our shell supports one pipe.
• The shell allows running a command in the background - for example $ ls &.
• The shell has a signal handler for Ctl-C. Ctl-C terminates a foreground process, but it does not terminate the shell.
• Ctl-D is equivalent to an exit command. The shell exits when a Ctl-D is entered. Note that fgets returns 0 when a Ctl-D is entered.

Submit the lab