Project 5: Pipeline System

Create a pipeline system that wires multiple commands with pipes and manages their processes.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced (The Engineer)
Time Estimate 1 week
Main Programming Language C
Alternative Programming Languages Rust, Zig, Go
Coolness Level Level 4: Hardcore Tech Flex
Business Potential 1. The “Resume Gold” (Educational/Personal Brand)
Prerequisites pipe/dup2, fork/exec, basic parsing
Key Topics pipes, process groups, fd management

1. Learning Objectives

By completing this project, you will:

  1. Explain and implement pipes in the context of a shell.
  2. Build a working pipeline system that matches the project specification.
  3. Design tests that validate correctness and edge cases.
  4. Document design decisions, trade-offs, and limitations.

2. All Theory Needed (Per-Concept Breakdown)

Pipes, Pipelines, and Dataflow

Fundamentals Pipes connect the stdout of one process to the stdin of another, allowing command composition. A pipeline like ls | grep foo | wc -l is not a single process but a set of processes connected by pipe file descriptors. The shell is responsible for creating the pipes, forking each process, wiring their file descriptors with dup2(), and closing unused pipe ends so that EOF is delivered correctly. Pipelines are the heart of Unix composition, so their correctness affects nearly every interactive session and script.

Deep Dive into the concept A pipeline of N commands requires N-1 pipes. Each pipe is a pair of file descriptors: a read end and a write end. The shell typically creates all pipes before forking, or it creates one pipe at a time in a loop. For each command in the pipeline, the shell forks a child and then duplicates the appropriate pipe ends to STDIN_FILENO or STDOUT_FILENO. The first command gets its stdout connected to the write end of pipe 0, the last command gets its stdin from the read end of the last pipe, and middle commands connect both stdin and stdout to adjacent pipes. After dup2(), the child must close all unused pipe ends; otherwise, pipes will stay open and readers will never see EOF.

Pipeline execution also involves process groups and job control. In an interactive shell, all processes in a pipeline should belong to the same process group so that terminal signals (like Ctrl+C) affect the entire pipeline. This means the shell must set a process group ID (PGID) for the pipeline, typically using the PID of the first process. If the pipeline runs in the foreground, the shell should hand terminal control to that process group using tcsetpgrp(), then wait for the pipeline to finish. If the pipeline runs in the background, the shell should not give terminal control and should immediately return to the prompt.

There are subtle ordering constraints. The shell should fork children in left-to-right order to preserve the expected behavior of commands that immediately read from stdin. If a later command starts before the earlier one has connected its output, you can get unexpected hangs. Similarly, if the parent closes pipe ends too early, children may inherit invalid descriptors. A robust implementation closes pipe ends in the parent after forking each child; the parent only needs to keep track of PIDs and perhaps the read end for the next iteration.

Error propagation in pipelines is nuanced. If a command in the middle fails to execute, the pipeline may still produce output or may break. Some shells choose to terminate the entire pipeline when a child fails to exec, while others allow remaining children to run and report their own errors. You should document and test your chosen behavior. For exit status, most shells report the status of the last command in the pipeline, while “pipefail” mode reports a non-zero status if any command fails. Even if you do not implement pipefail, your implementation should be structured so it can be added later.

Pipelines also create a performance consideration: each command becomes a separate process with its own address space. The shell must avoid heavy work in the pipeline setup path, as this is in the interactive hot loop. Efficient pipeline setup uses simple loops, avoids unnecessary heap allocations, and ensures pipes are created only as needed.

How this fits on projects Pipelines are a core shell feature and interact with redirection, job control, and signal handling.

Definitions & key terms

  • Pipe: Kernel buffer connecting a write end to a read end.
  • Pipeline: A sequence of commands connected by pipes.
  • Process group: A set of processes treated as a unit for signals.
  • EOF: End-of-file signaled when all write ends are closed.

Mental model diagram

cmd1 stdout -> [pipe] -> cmd2 stdout -> [pipe] -> cmd3

How it works (step-by-step)

  1. Parse pipeline into an ordered list of commands.
  2. Create a pipe for each adjacent pair.
  3. Fork each command; in child, wire stdin/stdout with dup2.
  4. Close unused pipe ends in both child and parent.
  5. Set process group for the pipeline if job control is enabled.
  6. Wait for foreground pipeline or record background job.

Minimal concrete example

pipe(p);
if (fork()==0) { dup2(p[1], 1); execvp("ls", argv1); }
if (fork()==0) { dup2(p[0], 0); execvp("wc", argv2); }

Common misconceptions

  • “Pipelines run in one process” -> each command is its own process.
  • “EOF happens when a command exits” -> only when all writers close.
  • “Pipelines are just redirections” -> they require process orchestration.

Check-your-understanding questions

  1. Why must unused pipe ends be closed in every child?
  2. Why should pipeline processes share a process group?
  3. What happens if the parent keeps a write end open?

Check-your-understanding answers

  1. Otherwise readers never see EOF and may hang.
  2. So signals like Ctrl+C affect the entire pipeline.
  3. The reader will block forever because the pipe never closes.

Real-world applications

  • Unix shell pipelines (ps aux | grep, etc.).
  • Data processing in build systems.
  • Streaming log processing tools.

Where you’ll apply it

References

  • “Advanced Programming in the UNIX Environment” (pipes and process groups).
  • POSIX Shell Command Language (pipeline semantics).

Key insights A pipeline is process orchestration plus careful file descriptor wiring.

Summary Pipelines turn individual commands into composable dataflow networks and require precise pipe management to avoid deadlocks.

Homework/Exercises to practice the concept

  1. Build a two-command pipeline and print PIDs.
  2. Add a third command and verify EOF behavior.
  3. Experiment with leaving a pipe open to observe hanging behavior.

Solutions to the homework/exercises

  1. Use pipe, fork, dup2, and exec in a loop.
  2. Add an extra pipe and wire it between the second and third commands.
  3. Skip closing a write end and observe the reader blocking.

Process Creation and Exec Lifecycle

Fundamentals A Unix shell is a long-running parent process that repeatedly creates child processes to run external commands. The split between fork() and execve() is the foundation: fork() clones the current process so the child inherits memory, file descriptors, environment, and current working directory, while execve() replaces the child image with a new program. This separation is why a shell can set up redirections, pipelines, and signal dispositions before launching a program. It is also why built-ins must run in the parent: only the parent can change the shell’s own state (like its directory or variables). If you understand when the parent waits, when it does not, and what the child inherits, you can predict how any shell command behaves. This concept is the root of process orchestration and almost every other shell feature.

Deep Dive into the concept The process lifecycle in a shell is a choreography between parent and child processes that must be deterministic, observable, and correct under failure. When the shell reads a command, it first decides whether the command is a built-in or an external program. Built-ins execute in the parent and therefore can mutate shell state. For external commands, the shell calls fork(). Internally, fork() creates a new task by duplicating the parent’s address space, file descriptor table, signal dispositions, and working directory. Modern kernels implement this with copy-on-write, so the child’s memory is not physically copied until it changes. From the shell’s perspective, fork() returns twice: once in the parent with the child PID, and once in the child with return value 0. This dual return is what allows the same code path to branch into parent logic versus child logic.

Once in the child, the shell must prepare the execution environment. This is where file descriptor wiring happens: dup2() to connect pipes or redirected files onto STDIN_FILENO, STDOUT_FILENO, and STDERR_FILENO; close() to remove unused descriptors; and chdir() if the command is a subshell with a different working directory. The child must also reset signal handlers to default for signals like SIGINT and SIGTSTP if the parent shell ignores them. Failure to do this leaves child programs “immune” to Ctrl+C because they inherit the shell’s ignored handlers. The child may also join or create a process group when pipelines or job control are involved, which matters for terminal control and signal delivery. Only after the environment is correct does the child call execve() (or execvp() for PATH lookup). At that point, the program image is replaced; the child’s memory, stack, and code become the new program, but the file descriptor table and environment remain as you configured them.

The parent does not disappear. It either waits for the child (foreground execution) or returns immediately (background execution). Waiting is done with waitpid(), which reports how the child finished: a normal exit (WIFEXITED) with an exit code, or a signal termination (WIFSIGNALED) with the terminating signal. Shells interpret these status codes to update $? and to print diagnostic messages like “Terminated by signal 9”. A robust shell handles interrupted waits (EINTR) and reaps all children to avoid zombies. In interactive shells, a SIGCHLD handler often records child state changes and wakes the main loop so that completed background jobs are announced promptly.

Failure handling is a central part of the lifecycle. If fork() fails (out of memory or process limit), the shell must report an error and continue running. If execve() fails, the child must print an error and exit with a defined status (commonly 127 for “command not found” and 126 for “found but not executable”). This behavior is relied upon by scripts, so the shell must be consistent. The parent should not attempt to recover from a failed exec by continuing in the child; the child must exit to avoid running shell code in an unexpected state.

Finally, remember that the execution environment is more than variables: it includes umask, current directory, signal mask, resource limits, and open file descriptors. A shell that incorrectly preserves or resets any of these will behave differently from the system shells you are comparing against. For example, if you forget to set close-on-exec on internal file descriptors, a child process might inherit unexpected descriptors, causing hangs (pipes never closing) or security leaks (files exposed). These subtle lifecycle details distinguish toy shells from robust ones.

How this fits on projects This concept is central to command execution, pipelines, redirection, and job control, so it appears in almost every project that launches external programs.

Definitions & key terms

  • fork(): Clone the current process into a child process.
  • execve(): Replace the current process image with a new program.
  • waitpid(): Wait for a child process to change state.
  • Zombie: A terminated child that has not been reaped.
  • Copy-on-write: Memory optimization where pages are copied only when written.

Mental model diagram

Parent Shell
   |
   | fork()
   v
Child Shell -- set fds/signals -- execve("/bin/ls")
   |
   | exit(status)
   v
Parent waits -> collects status -> updates $?

How it works (step-by-step)

  1. Parse the command into a simple command node.
  2. Classify: built-in/function vs external.
  3. Fork a child if external. Invariant: parent must not block unless foreground.
  4. Child setup: apply redirections, reset signals, set process group if needed.
  5. Exec the program image. Failure mode: execve returns with errno.
  6. Parent waits for foreground child or records job for background.
  7. Update $? and job table; reap zombies. Failure mode: missed waitpid().

Minimal concrete example

pid_t pid = fork();
if (pid == 0) {
// Child: replace image
execlp("ls", "ls", "-l", NULL);
perror("exec failed");
_exit(127);
}
int status;
waitpid(pid, &status, 0);
printf("status=%d\n", WEXITSTATUS(status));

Common misconceptions

  • “fork runs the program” -> fork() only clones; exec() runs the program.
  • “exit status is boolean” -> only 0 is success; non-zero encodes errors.
  • “child changes affect parent” -> changes are isolated after fork().

Check-your-understanding questions

  1. Why must a shell use fork() before execve() for external commands?
  2. What happens if a parent never calls waitpid() for a child?
  3. Why do shells reset signal handlers in the child before exec()?

Check-your-understanding answers

  1. The shell must keep running; execve() replaces the current process.
  2. The child becomes a zombie until it is reaped.
  3. Otherwise the child inherits ignored signals and cannot be controlled.

Real-world applications

  • Interactive shells (bash, dash, zsh).
  • Process supervisors and daemons that spawn workers.
  • Build systems that run many external commands.

Where you’ll apply it

References

  • “Advanced Programming in the UNIX Environment” (Process Control).
  • “The Linux Programming Interface” (Process and exec chapters).
  • POSIX Shell Command Language (execution environment).

Key insights A shell is primarily a process orchestrator, not a program runner.

Summary Understanding the fork/exec lifecycle gives you the ability to predict how shell commands behave and why the shell can keep control while running external programs.

Homework/Exercises to practice the concept

  1. Write a launcher that runs a command and prints the exit status.
  2. Add a flag to run the command in the background without waiting.
  3. Use strace -f or dtruss to observe fork/exec/wait.

Solutions to the homework/exercises

  1. Use fork(), execvp(), waitpid(), and WEXITSTATUS.
  2. Skip waitpid() for background and add a SIGCHLD reaper.
  3. Trace system calls and confirm the sequence matches your mental model.

File Descriptors and Redirection Semantics

Fundamentals Redirection is how a shell reconfigures where a command reads input and writes output. It works by manipulating file descriptors, usually 0 (stdin), 1 (stdout), and 2 (stderr). Redirections like >, >>, <, and 2> open files with specific flags and then use dup2() to rewire the command’s standard streams. The order of redirections matters, and redirections can appear anywhere in the command line. A correct redirection engine is essential for scripts, pipelines, and error handling.

Deep Dive into the concept At the kernel level, every process has a file descriptor table. Redirection changes entries in this table before the command runs. For > the shell opens (or creates) the target file with flags like O_WRONLY | O_CREAT | O_TRUNC and permissions derived from umask, then duplicates that descriptor onto STDOUT_FILENO. For >>, O_APPEND is used so writes append rather than truncate. For <, the file is opened with O_RDONLY and duplicated to STDIN_FILENO. For 2>, the target file is duplicated to STDERR_FILENO. The shell can also duplicate descriptors directly using syntax like 2>&1, which means “make fd 2 a duplicate of fd 1.” This is not the same as 2>file and must be handled by the parser as a special redirection form.

Order is critical. In cmd >out 2>&1, stderr is redirected to the new stdout (the file), because stdout was already redirected when 2>&1 is evaluated. In cmd 2>&1 >out, stderr is duplicated to the old stdout (the terminal), and then stdout is redirected to the file, so stderr remains on the terminal. The shell must apply redirections left-to-right to match this behavior. This ordering rule is a common source of confusion and bugs in novice shells.

Redirections can also target existing descriptors. The >& and <& forms allow the user to duplicate or close file descriptors. For example, exec 3>log.txt opens a file and assigns it to fd 3, while exec 3>&- closes fd 3. Implementing these forms requires careful handling of fd lifetimes and close-on-exec flags. If your shell leaks file descriptors, child processes may inherit unexpected open files, leading to security or correctness issues.

Here-documents (<<) add another layer. They provide inline input text to a command, typically by writing the content into a pipe or temporary file and then redirecting stdin to that file. Here-docs can be quoted or unquoted, and quoting affects whether parameter expansion is performed inside the heredoc body. Even if you postpone heredoc support, your redirection engine should be designed to accommodate it later.

How this fits on projects Redirection is foundational for pipelines, scripting, and error handling. Every shell feature that touches I/O depends on correct fd manipulation.

Definitions & key terms

  • File descriptor (fd): Integer handle for open files or pipes.
  • dup2(): Duplicate one fd onto another, closing the target first.
  • umask: Mask that restricts permissions on newly created files.
  • Here-doc: Inline input redirected into stdin.

Mental model diagram

stdout (fd 1) -> open("out.txt") -> dup2(fd_out, 1)

How it works (step-by-step)

  1. Parse redirection tokens and targets.
  2. For each redirection, open or select the target fd.
  3. Apply redirections in left-to-right order.
  4. Use dup2() to rewire standard fds.
  5. Close unused descriptors to avoid leaks.

Minimal concrete example

int fd = open("out.txt", O_WRONLY|O_CREAT|O_TRUNC, 0644);
dup2(fd, STDOUT_FILENO);
close(fd);

Common misconceptions

  • “Order does not matter” -> it does; redirections are sequential.
  • “2>&1 is the same as >file 2>&1” -> order changes meaning.
  • “Redirection only applies to external commands” -> built-ins can be redirected too.

Check-your-understanding questions

  1. Why does 2>&1 >out leave stderr on the terminal?
  2. What does exec 3>&- do?
  3. Why must redirections be applied before exec()?

Check-your-understanding answers

  1. Because stderr is duplicated before stdout is redirected.
  2. It closes file descriptor 3 in the shell process.
  3. The child’s fd table must be ready before program start.

Real-world applications

  • Shell scripting and logging.
  • Daemon output redirection.
  • Build systems capturing errors.

Where you’ll apply it

References

  • POSIX Shell Command Language (redirection rules).
  • “The Linux Programming Interface” (file descriptors).

Key insights Redirection is fd table surgery; order and duplication rules are everything.

Summary A correct redirection engine uses open and dup2 in a precise order to rewire stdin/stdout/stderr and support scripts reliably.

Homework/Exercises to practice the concept

  1. Implement > and >> redirections and test with echo.
  2. Add 2>&1 and demonstrate the difference between the two orders.
  3. Track open fds and ensure none leak into child processes.

Solutions to the homework/exercises

  1. Use open with O_TRUNC and O_APPEND, then dup2.
  2. Apply redirections left-to-right and compare outputs.
  3. Close all non-needed descriptors after dup2.

3. Project Specification

3.1 What You Will Build

A pipeline executor that can run cmd1 | cmd2 | cmd3 with correct fd wiring.

Included:

  • Core feature set described above
  • Deterministic CLI behavior and exit codes

Excluded:

  • No job control UI; focus on execution correctness.

3.2 Functional Requirements

  1. Requirement 1: Parse pipeline sequences and launch all processes.
  2. Requirement 2: Create N-1 pipes and wire stdin/stdout with dup2.
  3. Requirement 3: Close unused pipe ends in both parent and child.
  4. Requirement 4: Return correct exit status for the pipeline.
  5. Requirement 5: Support pipelines with built-ins or document limitations.

3.3 Non-Functional Requirements

  • Performance: Interactive latency under 50ms for typical inputs; pipeline setup should scale linearly.
  • Reliability: No crashes on malformed input; errors reported clearly with non-zero status.
  • Usability: Clear prompts, deterministic behavior, and predictable error messages.

3.4 Example Usage / Output

$ ./mysh
mysh> seq 1 5 | awk '{print $1*2}' | tail -n 2
8
10
mysh> yes | head -n 3
y
y
y
mysh> echo $?
0

3.5 Data Formats / Schemas / Protocols

  • Pipeline node containing an ordered list of command nodes.

3.6 Edge Cases

  • Single-command pipeline
  • Large pipeline length
  • Exec failure in middle

3.7 Real World Outcome

This is the exact behavior you should be able to demonstrate.

3.7.1 How to Run (Copy/Paste)

  • make
  • ./mysh

3.7.2 Golden Path Demo (Deterministic)

$ ./mysh
mysh> seq 1 5 | awk '{print $1*2}' | tail -n 2
8
10
mysh> yes | head -n 3
y
y
y
mysh> echo $?
0

3.7.3 Failure Demo (Deterministic)

$ ./mysh
mysh> not_a_command
mysh> echo $?
127

4. Solution Architecture

4.1 High-Level Design

[Input] -> [Parser/Lexer] -> [Core Engine] -> [Executor/Output]

4.2 Key Components

Component Responsibility Key Decisions
Pipeline Builder Creates pipe fds and process groups Keep in a single loop.
Child Setup dup2 and close fds Correct EOF behavior.
Wait Manager Collects statuses for pipeline Clear status policy.

4.4 Data Structures (No Full Code)

struct Pipeline { struct Command **cmds; size_t count; };

4.4 Algorithm Overview

Key Algorithm: Pipe Wiring

  1. Create pipes
  2. Fork each command
  3. Dup fds

Complexity Analysis:

  • Time: O(n) time
  • Space: O(n) space

5. Implementation Guide

5.1 Development Environment Setup

# install dependencies (if any)
# build
make

5.2 Project Structure

project-root/
├── src/
│   ├── main.c
│   ├── lexer.c
│   └── executor.c
├── tests/
│   └── test_basic.sh
├── Makefile
└── README.md

5.3 The Core Question You’re Answering

How do multiple processes communicate safely and concurrently through pipes?

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. pipe() and fd tables
  2. Process groups
  3. Exit status rules

5.5 Questions to Guide Your Design

5.6 Thinking Exercise

The “Hanging Pipeline” Problem

Why does this hang if you forget to close pipe ends?

yes | head -n 1

5.7 The Interview Questions They’ll Ask

5.8 Hints in Layers

Hint 1: N-1 pipes If you have 3 commands, you need 2 pipes.

Hint 2: Fork all children Create all children before waiting.

Hint 3: Close unused fds Close read/write ends you don’t use in each process.

Hint 4: Track last PID Use the last command’s PID for $?.

5.9 Books That Will Help

Topic Book Chapter
Pipes “The Linux Programming Interface” Ch. 44
Process groups “Advanced Programming in the UNIX Environment” Ch. 9
Pipeline semantics POSIX Shell Command Language Pipeline section

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

  • Define data structures and interfaces
  • Build a minimal end-to-end demo

Tasks:

  1. Implement the core data structures
  2. Build a tiny CLI or harness for manual tests

Checkpoint: A demo command runs end-to-end with clear logging.

Phase 2: Core Functionality (1 week)

Goals:

  • Implement full feature set
  • Validate with unit tests

Tasks:

  1. Implement core requirements
  2. Add error handling and edge cases

Checkpoint: All functional requirements pass basic tests.

Phase 3: Polish & Edge Cases (2-4 days)

Goals:

  • Harden for weird inputs
  • Improve UX and documentation

Tasks:

  1. Add edge-case tests
  2. Document design decisions

Checkpoint: Deterministic golden demo and clean error output.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Parsing depth Minimal vs full Incremental Start small, expand safely
Error policy Silent vs verbose Verbose Debuggability for learners

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Test individual components Tokenizer, matcher, env builder
Integration Tests Test component interactions Full command lines
Edge Case Tests Handle boundary conditions Empty input, bad args

6.2 Critical Test Cases

  1. Golden Path: Run the canonical demo and verify output.
  2. Failure Path: Provide invalid input and confirm error status.
  3. Stress Path: Run repeated commands to detect leaks or state corruption.

6.3 Test Data

input: echo hello
output: hello

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Misordered redirection Output goes to wrong place Apply redirections left-to-right
Leaked file descriptors Commands hang waiting for EOF Close unused fds in parent/child
Incorrect exit status &&/|| behave wrong Use waitpid macros correctly

7.2 Debugging Strategies

  • Trace syscalls: Use strace/dtruss to verify fork/exec/dup2 order.
  • Log state transitions: Print parser states and job table changes in debug mode.
  • Compare with dash: Run the same input in a reference shell.

7.3 Performance Traps

  • Avoid O(n^2) behavior in hot paths like line editing.
  • Minimize allocations inside the REPL loop.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a help built-in with usage docs.
  • Add colored prompt themes.

8.2 Intermediate Extensions

  • Add a simple profiling mode for command timing.
  • Implement a which built-in using PATH lookup.

8.3 Advanced Extensions

  • Add programmable completion or plugin system.
  • Add a scriptable test harness with golden outputs.

9. Real-World Connections

9.1 Industry Applications

  • Build systems: shells orchestrate compilation and test pipelines.
  • DevOps automation: scripts manage deployments and infrastructure.
  • bash: The most common interactive shell.
  • dash: Minimal POSIX shell often used as /bin/sh.
  • zsh: Feature-rich interactive shell.

9.3 Interview Relevance

  • Process creation and lifecycle questions.
  • Parsing and system programming design trade-offs.

10. Resources

10.1 Essential Reading

  • “The Linux Programming Interface” by Michael Kerrisk - focus on the chapters relevant to this project.
  • “Advanced Programming in the UNIX Environment” - process control and pipes.

10.2 Video Resources

  • Unix process model lectures (any OS course).
  • Compiler front-end videos for lexing/parsing projects.

10.3 Tools & Documentation

  • strace/dtruss: inspect syscalls.
  • man pages: fork, execve, waitpid, pipe, dup2.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain the core concept without notes.
  • I can trace a command through my subsystem.
  • I understand at least one key design trade-off.

11.2 Implementation

  • All functional requirements are met.
  • All critical tests pass.
  • Edge cases are handled cleanly.

11.3 Growth

  • I documented lessons learned.
  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Core feature works for the golden demo.
  • Errors are handled with non-zero status.
  • Code is readable and buildable.

Full Completion:

  • All functional requirements met.
  • Tests cover edge cases and failures.

Excellence (Going Above & Beyond):

  • Performance benchmarks and clear documentation.
  • Behavior compared against a reference shell.