Tiny Shell Lab

In this lab, you will implement a shell terminal that supports forking processes and manages both foreground and background processes. A total of 32 tests are provided, with the first part focusing on implementing the functionality to pass the first 23 tests.

Part I

First, look at the initialization section of the main function.

char cmdline[MAXLINE_TSH]; defines a character array that can be written to.

init_job_list(); initializes a linked list.

void init_job_list(void) {
    init = true;
    for (jid_t jid = 1; jid <= MAXJOBS; jid++) {
        struct job_t *job = get_job(jid);
        clearjob(job);
        job->cmdline = NULL;
    }
    nextjid = 1;
}

nextjid is a static variable used for assigning new job IDs.

Next, signal handlers are set up for different signals by calling the Signal() function.

// Install the signal handlers
Signal(SIGINT, sigint_handler);   // Handles Ctrl-C
Signal(SIGTSTP, sigtstp_handler); // Handles Ctrl-Z
Signal(SIGCHLD, sigchld_handler); // Handles terminated or stopped child

Signal(SIGTTIN, SIG_IGN);
Signal(SIGTTOU, SIG_IGN);

Signal(SIGQUIT, sigquit_handler);

SIGINT typically represents a keyboard interrupt (i.e., the user presses Ctrl+C) and is a common way to terminate a program. A custom sigint_handler function is used here to catch and handle this signal.

SIGTSTP is the signal sent when the user presses Ctrl+Z, typically used to suspend (pause) a process. The custom handler sigtstp_handler will process this signal.

SIGCHLD is sent to the parent process when a child process terminates or is suspended, and is often used for the parent to clean up finished child processes (e.g., by calling wait() or waitpid() to handle zombie processes).

SIGTTIN is sent when a background process tries to read from the terminal. If not ignored, this signal will pause the background process.

SIGTTOU is sent when a background process tries to write to the terminal. Like SIGTTIN, ignoring this signal can prevent the background process from being paused.

SIGQUIT typically indicates the user presses Ctrl+\, and causes the program to generate a core dump and terminate. The sigquit_handler function alters its default behavior.

The sigint_handler, sigtstp_handler, sigchld_handler, and sigquit_handler functions will be introduced later.

After obtaining the cmdline, the next step is to parse it.

eval()

parse_result = parseline(cmdline, &token);

struct cmdline_tokens {
    int argc;               ///< Number of arguments passed
    char *argv[MAXARGS];    ///< The arguments list
    char *infile;           ///< The filename for input redirection, or NULL
    char *outfile;          ///< The filename for output redirection, or NULL
    builtin_state builtin;  ///< Indicates if argv[0] is a builtin command
    char _buf[MAXLINE_TSH]; ///< Internal backing buffer (do not use)
};

buildin_cmd()

There are two types of commands: built-in and others. Built-in commands include:

• quit: If quit is used, exit(0); will terminate the tsh process.

• jobs: Since accessing jobs requires obtaining the global jobs list, signals need to be blocked first.

  sigset_t mask, prev;
  sigemptyset(&mask);
  sigaddset(&mask, SIGCHLD);
  sigaddset(&mask, SIGINT);
  sigaddset(&mask, SIGTSTP);
  sigprocmask(SIG_BLOCK, &mask, &prev);       // block
  list_jobs(STDOUT_FILENO);
  sigprocmask(SIG_SETMASK, &prev, NULL);      // unblock
  return 1;

  In the second part, the list_jobs function, which currently writes to the terminal output file descriptor (fd), will be modified to write to a file descriptor (fd) instead.

• bg/fg: Move a process from the foreground to the background or vice versa.

  if (!strcmp(bg_or_fg, "bg") || !strcmp(bg_or_fg, "fg"))
      {   
          if(!strcmp(bg_or_fg, "bg")){         // ST -> BG
              convert_to_bg(&token);
          }else if (!strcmp(bg_or_fg, "fg"))   // ST -> FG
          {
              convert_to_fg(&token);
          }
          return 1;
      }

  Functions convert_to_bg and convert_to_fg will be explained in detail in the second part.

Other Commands

When it is not a buildin_cmd, a valid command is one that intends to run an executable program. For such a command, we fork a new process and execute it using execve().

    else if (!buildin_cmd(cmdline))
    {       
        pid_t pid;
        sigset_t mask, prev;
        sigemptyset(&mask);
        sigaddset(&mask, SIGCHLD);
        sigaddset(&mask, SIGINT);
        sigaddset(&mask, SIGTSTP);
        sigprocmask(SIG_BLOCK, &mask, &prev);
        pid = fork();
        if(pid == 0){       //child process
            sigprocmask(SIG_SETMASK, &prev, NULL);
            setpgid(pid, pid);
            if(execve(token.argv[0], token.argv, environ) < 0){
                perror("fialed to execve\n");
                exit(-1);
            }
        }else{
            if(parse_result == PARSELINE_FG){     // forground job
                fg_pid = pid;
                fg_running = 1;
                add_job(pid, FG, cmdline);
                while(fg_running == 1){     // while the fg job is still running
                    sigsuspend(&prev);
                }
                sigprocmask(SIG_SETMASK, &prev, NULL);
            }else if (parse_result == PARSELINE_BG)       // background job
            {
                add_job(pid, BG, cmdline);
                jid_t jid = job_from_pid(pid);
                printf("[%d] (%d) %s\n", jid, pid, cmdline);
                sigprocmask(SIG_SETMASK, &prev, NULL);
            }
        }
    }

If the command is to be executed in the foreground (PARSELINE_FG), the global variable fg_pid will be set to the pid of the current child process.

sigsuspend(&prev);

This temporarily replaces the process's signal mask with prev and suspends the parent process until a signal is received. Its purpose is to wait for the foreground process to finish (e.g., by receiving a child process termination signal via SIGCHLD), preventing the parent process from continuing execution before the foreground job ends. Changes in the fg_running state will be explained in the upcoming sigchld_handler().

If the command is to be executed in the background (PARSELINE_BG), a new jid and pid will be assigned, and a message indicating background execution will be printed. Signals will be unblocked, and the prompt will be ready for the next command.

sigchld_handler()

The sigchld_handler function handles the SIGCHLD signal, which is sent to the parent process when the state of a child process changes. This signal handler checks the status of the child process and updates the job status based on its exit status, termination signal, or stop status.

void sigchld_handler(int sig) {
    int olderrno = errno;
    sigset_t mask, prev;
    sigemptyset(&mask);
    sigaddset(&mask, SIGINT);
    sigaddset(&mask, SIGTSTP);
    sigprocmask(SIG_BLOCK, &mask, &prev);
    int wstate;
    pid_t pid = waitpid(-1, &wstate, WUNTRACED | WNOHANG | WCONTINUED);
    while(pid > 0){
        if(WIFCONTINUED(wstate)){
            jid_t jid = job_from_pid(pid);
            job_state jstate = job_get_state(jid);      // get the state of the job
            if(jstate == ST){           // ST -> BG
                job_set_state(jid, BG);
            }
        }else{
            jid_t jid = job_from_pid(pid);
            if(WIFEXITED(wstate)){  // normally exit
                delete_job(jid);
                if(pid == fg_pid){  // if a forground job
                    fg_running = 0;     // stop running the job
                }
            }
            if(WIFSIGNALED(wstate)){    // SIGINT
                delete_job(jid);
                int signum = WTERMSIG(wstate);
                sio_printf("Job [%d] (%d) terminated by signal %d\n", jid, pid, signum);
                if(pid == fg_pid){
                    fg_running = 0;
                }
            }
            if(WIFSTOPPED(wstate)){     // SIGTSTP
                fg_running = 0;
                job_set_state(jid, ST);
                int signum = WSTOPSIG(wstate);
                sio_printf("Job [%d] (%d) stopped by signal %d\n", jid, pid, signum);
            }
        }
        pid = waitpid(-1, &wstate, WUNTRACED | WNOHANG | WCONTINUED);
    }
    sigprocmask(SIG_SETMASK, &prev, NULL);
    errno = olderrno;
    return;
}

Create an empty signal set mask. Add SIGINT and SIGTSTP to the signal set mask. Use sigprocmask to block these signals to prevent them from being received during processing; prev saves the old signal mask.

Use waitpid to wait for changes in the status of child processes. The -1 argument indicates waiting for any child process:

• WUNTRACED reports if a child process has been stopped,

• WNOHANG returns immediately if there are no status changes for child processes,

• WCONTINUED reports the continuation status of a child process.

In the while loop, as long as there are child processes with status changes:

• Use WIFCONTINUED to check if a child process has resumed execution. If it has, and the previous state was stopped (ST), change the state to background running (BG).

If the process is not stopped:

• Use WIFCONTINUED to check if a child process has resumed execution. If so, and the previous state was stopped (ST), change the state to background running (BG).

• Use WIFEXITED to check if a child process exited normally. Remove the job, and if it was a foreground job, update the fg_running flag.

• Use WIFSIGNALED to check if a child process was terminated by a signal. Remove the job, print the information, and if it was a foreground job, update the fg_running flag.

• Use WIFSTOPPED to check if a child process was stopped by a signal. Update the job status to stopped and print the signal information.

sigint_handler()

void sigint_handler(int sig) {
    int _errno = errno;
    if(fg_pid > 0){
        killpg(fg_pid, sig);
    }
    errno = _errno;
}

Note that killpg does not kill processes but rather sends signals. The function killpg(fg_pid, sig) is used to send a signal to all processes in the foreground process group. Here, sig represents the type of signal passed to sigint_handler (in this case, SIGINT). killpg is a higher-level function for sending signals to a process group, which is more efficient than sending signals individually. Blocking signals is not necessary when merely sending a signal.

sigtstp_handler()

void sigtstp_handler(int sig) {
    int _errno = errno;
    if(fg_pid > 0){
        killpg(fg_pid, sig);
    }
    errno = _errno;
}

It is similar to the code above.

Part II

After implementing the basic buildin_cmd commands and handling foreground (fg) and background (bg) operations, as well as managing signal blocking and the job list, the second part will involve implementing job state transitions (st), foreground (fg), and background (bg) transformations, as well as handling I/O redirection (fd).

First, we'll review convert_to_bg and convert_to_fg, which were not explained in Part I.

convert_to_bg()

static void convert_to_bg(struct cmdline_tokens *token){
    if(token->argc == 2){       // correct number to parse
        const char *id = token->argv[1];
        sigset_t mask, prev;
        sigemptyset(&mask);
        sigaddset(&mask, SIGCHLD);
        sigaddset(&mask, SIGINT);
        sigaddset(&mask, SIGTSTP);
        sigprocmask(SIG_BLOCK, &mask, &prev);       // block
        pid_t pid = 0;
        jid_t jid = 0;
        if(id == NULL || id[0] == '\0'){            // the id is nothing...
            printf("bg command requires PID or %%jobid argument\n");
        }else{
            if(id[0] == '%'){                               // jid
                jid = (jid_t)atoi(&id[1]);
                if(job_exists(jid) == false){
                    printf("%%%d: No such job\n", jid);
                    sigprocmask(SIG_SETMASK, &prev, NULL);      // unblock
                    return;
                }
                pid = job_get_pid(jid);
            }else if ('0' <= id[0] && '9' >= id[0])         // pid
            {
                pid = (pid_t)atoi(id);
                jid = job_from_pid(pid);
            }else{                                          // bg xxx, not pid or %jid
                printf("bg: argument must be a PID or %%jobid\n");
            }
        }
        if(pid != 0){
            const char *cmdline = job_get_cmdline(jid);
            printf("[%d] (%d) %s\n", jid, pid, cmdline);
            st_fgbg = 2;
            killpg(pid, SIGCONT);                           // send comtinue
        }
        sigprocmask(SIG_SETMASK, &prev, NULL);      // unblock

    }else{  // bg input error more than 2 argv...
        printf("bg command requires PID or %%jobid argument\n");
        return;
    }
}

st_fgbg is a global variable. A value of 0 represents transitioning from background to foreground, 1 represents transitioning from stopped to foreground (ST → fg), and 2 represents transitioning from stopped to background (ST → bg). There is no direct transition from foreground to background because, during foreground execution, only signals like Ctrl+C and Ctrl+Z can stop or end the foreground process.

killpg(pid, SIGCONT); will continue the execution of processes that are in the stopped state (ST).

This will trigger sigchld_handler. We need to modify sigchld_handler from Part I to handle the transition from stopped to background (ST → bg).

convert_to_fg()

static void convert_to_fg(struct cmdline_tokens *token){
    if(token->argc != 2){
        printf("fg command requires PID or %%jobid argument\n");
        return;
    }
    const char *id = token->argv[1];
    pid_t pid = 0;
    pid_t jid = 0;
    sigset_t mask, prev;
    sigemptyset(&mask);
    sigaddset(&mask, SIGCHLD);
    sigaddset(&mask, SIGINT);
    sigaddset(&mask, SIGTSTP);
    sigprocmask(SIG_BLOCK, &mask, &prev);       // block
    if(id == NULL || id[0] == '\0'){            // the id is nothing...
        printf("fg command requires PID or %%jobid argument\n");
    }else{
        if(id[0] == '%'){                               // jid
            jid = (jid_t)atoi(&id[1]);
            if(job_exists(jid) == false){
                printf("%%%d: No such job\n", jid);
                sigprocmask(SIG_SETMASK, &prev, NULL);      // unblock
                return;
            }
            pid = job_get_pid(jid);
        }else if ('0' <= id[0] && '9' >= id[0])         // pid
        {
            pid = (pid_t)atoi(id);
            jid = job_from_pid(pid);
        }else{                                          // bg xxx, not pid or %jid
            printf("fg: argument must be a PID or %%jobid\n");
        }
    }
    if(pid != 0){
        // different from background job things from here
        job_state jstate = job_get_state(jid);
        fg_pid = pid;
        fg_running = 1;
        if(jstate == ST){
            st_fgbg = 1;
            killpg(pid, SIGCONT);       // send continue
        }else if(jstate == BG){
            st_fgbg = 0;
            job_set_state(jid, FG);     // BG -> FG
        }
        while(fg_running == 1){
            sigsuspend(&prev);
        }
    }
    sigprocmask(SIG_SETMASK, &prev, NULL);      // unblock
}

The only difference from bg is that after setting fg_running = 1;, you need to wait for the foreground process to finish.

• When a job is in the stopped state (ST), you need to send the signal SIGCONT.

• When a job is in the background (BG), you do not need to send SIGCONT because it is already running.

4o mini

FG/BG/ST Status Convert

void sigchld_handler(int sig) {
    int olderrno = errno;
    sigset_t mask, prev;
    ...
    while(pid > 0){
        if(WIFCONTINUED(wstate)){
            jid_t jid = job_from_pid(pid);
            job_state jstate = job_get_state(jid);      // get the state of the job
            if(jstate == ST){           // ST -> BG
                if(st_fgbg == 1){
                    job_set_state(jid, FG);
                }else if(st_fgbg == 2){
                    job_set_state(jid, BG);
                }
            }
        }else{
            ...
        }
        pid = waitpid(-1, &wstate, WUNTRACED | WNOHANG | WCONTINUED);
    }
    sigprocmask(SIG_SETMASK, &prev, NULL);
    errno = olderrno;
    return;
}

The modification is as follows: if a SIGCONT signal is received, use WIFCONTINUED(wstate) to check if the child process has resumed execution. If it has, and the current job status is stopped (ST), update the job status to foreground (FG) or background (BG) based on the value of st_fgbg.

File Redirection

In eval(), modifications are also needed to change the input and output I/O by altering stdin and stdout.

void eval(const char *cmdline) {
    parseline_return parse_result;
    ...
    else if (!buildin_cmd(cmdline))
    {
        ...
        if(pid == 0){       //child process
            sigprocmask(SIG_SETMASK, &prev, NULL);
            // pid = getpid(pid, pid);
            setpgid(pid, pid);
            if(token.infile != NULL){              // '<' ST_INFILE
                int fd = open(token.infile, O_RDONLY, 0664);
                if (fd == -1) {
                    fprintf(stderr, "%s: No such file or directory\n", token.infile);
                    return;
                }    
                if (dup2(fd, STDIN_FILENO) == -1) {
                    fprintf(stderr, "%s: No such file or directory\n", token.infile);
                    close(fd);
                    return;
                }            
            }
            if (token.outfile != NULL)       // '>' ST_OUTFILE
            {
                int fd = open(token.outfile, O_WRONLY | O_CREAT | O_TRUNC, 0664);
                if (fd == -1) {
                    fprintf(stderr, "%s: No such file or directory\n", token.outfile);
                    return;
                }
                if (dup2(fd, STDOUT_FILENO) == -1) {
                    fprintf(stderr, "%s: No such file or directory\n", token.outfile);
                    close(fd);
                    return;
                }
            }
            int exe_fd = open(token.argv[0], O_RDONLY, 0664);
            if(exe_fd == -1){
                if (errno == ENOENT) {
                    fprintf(stderr, "%s: No such file or directory\n", token.argv[0]);
                } else if (errno == EACCES) {
                    fprintf(stderr, "%s: Permission denied\n", token.argv[0]);
                } else {
                    fprintf(stderr, "Error opening file: %s\n", strerror(errno));
                }            
                exit(-1);
            }
            ...
}

Input Redirection:

• If token.infile is not empty, it indicates that input redirection is specified in the command.

• Use open to open the specified input file and check if the file exists.

• Use dup2 to copy the input file descriptor to standard input (STDIN_FILENO), ensuring that subsequent read operations will read from this file.

• If open or dup2 fails, report the error and return.

Output Redirection:

• If token.outfile is not empty, it indicates that output redirection is specified in the command.

• Use open to open the specified output file, creating the file if it does not exist. O_TRUNC indicates that if the file exists, its content will be truncated.

• Use dup2 to copy the output file descriptor to standard output (STDOUT_FILENO), ensuring that subsequent write operations will write to this file.

• If open or dup2 fails, report the error and return.

Executable File Check:

• Attempt to open the specified executable file (token.argv[0]).

• Check if the file exists (ENOENT), if it has permissions (EACCES), or report other errors.

• If the file cannot be opened, report the error and exit the child process.

With this, the tshlab is complete.