Processes

A process is a program in execution, together with everything the kernel keeps for it: its memory, its open files, its identity for permission checks, and its place in the scheduler. The kernel represents each process by a record, struct task_struct, and identifies it by a number, the process ID or pid.

In this chapter, we will follow a process through its whole life: how it is created, how it comes to run a different program, how it ends, and how the process that created it learns the result. We will read the kernel’s record of a process field by field and find the same information under /proc. Then we will write procfacts, which measures each step on a running kernel, and proctable, a model of the kernel’s process table.

A shell runs a command

When we type ls in a shell, 4 system calls do the work, 2 in the shell and 2 in a new process.

1. The shell calls fork. The kernel creates a second process that is a copy of the shell: the same program, the same memory contents, the same open files. The new process is the child, and the shell is its parent. fork returns in both processes. In the parent it returns the pid of the child, and in the child it returns 0, which is how each of them knows which one it is.
2. The child calls exec with the path of the ls program. The kernel discards the memory of the child, loads ls in its place, and starts it. The pid does not change. It is the same process running a different program.
3. ls does its work and calls exit with a status, 0 for success.
4. Meanwhile the parent has called wait, which puts it to sleep until a child ends. wait now returns the pid of the child and its status, and the shell prints the next prompt.

Creating a process and loading a program are separate calls, and that is deliberate. Between fork and exec the child is still running the shell’s code, with the shell’s descriptors. The shell uses that interval to prepare the environment of the new program: it redirects descriptors with dup2, changes the working directory, or adjusts signal handling. Then it calls exec. The new program starts in the prepared environment and contains no code for the preparation. The redirections of chapter 2 are performed in this interval, and chapter 4 builds a shell that does it.

The kernel’s record of a process

Every process has a struct task_struct. It is one of the largest structures in the kernel, about 700 lines in include/linux/sched.h. These are the fields that this chapter and the following chapters use, as they appear in Linux 5.15.

struct task_struct {
        unsigned int __state;                  /* running, sleeping, stopped, ... */
        struct sched_entity se;                /* scheduling data, chapter 6 */
        struct mm_struct *mm;                  /* the address space, chapter 7 */
        int exit_state;                        /* EXIT_ZOMBIE after exit */
        int exit_code;                         /* the status for the parent */
        pid_t pid;                             /* the number of this task */
        pid_t tgid;                            /* the number of its process */
        struct task_struct *real_parent;       /* the process that created it */
        struct list_head children;             /* its children */
        struct list_head sibling;              /* its place in the parent's list */
        const struct cred *cred;               /* user and group, capabilities */
        char comm[TASK_COMM_LEN];              /* the name of the program */
        struct files_struct *files;            /* the descriptor table, chapter 2 */
        struct nsproxy *nsproxy;               /* its namespaces, chapter 11 */
        struct signal_struct *signal;          /* signal state, chapter 5 */
        struct sighand_struct *sighand;        /* signal handlers, chapter 5 */
        struct css_set *cgroups;               /* its control groups, chapter 12 */
        /* ... */
};

The resources are separate structures reached through pointers, and this is what makes fork and threads possible with the same code. A new task can receive a copy of a resource or a pointer to the same one, resource by resource.

Reading the record from /proc

The kernel publishes the record of every process as text files in /proc/<pid>. This is a sleep started from a shell with pid 565533:

$ ps -o pid,ppid,stat,comm
    PID    PPID STAT COMMAND
 565533  565532 S    sh
 565534  565533 S    sleep
$ grep -E 'Name|State|Tgid|Pid|PPid|Threads' /proc/565534/status
Name:	sleep
State:	S (sleeping)
Tgid:	565534
Pid:	565534
PPid:	565533
Threads:	1

Name is comm, Pid and Tgid are pid and tgid, and PPid is the pid of real_parent. State is a letter derived from __state and exit_state.

Most processes on a system are in state S at any moment. A process in state R uses CPU time, and chapter 6 describes how the kernel divides the CPUs among them.

fork

fork creates a new struct task_struct and decides, for each resource of the parent, whether the child gets a copy.

A way to remember the table: the child starts as a photograph of the parent, taken at the moment of the call. Everything that is true of the parent at that moment is true of the child, with 2 differences that let them tell each other apart: the pid, and the return value of fork. From then on they are separate processes, and a change in one is invisible to the other, except through the open files they still share.

The copy of the memory is what makes fork look expensive and why it is cheap in practice. The kernel copies the page table and leaves the pages themselves shared and read-only. A page is copied only when one of the processes writes to it. A child that calls exec immediately, the usual case, discards the address space before it has written to more than a few pages.

On Linux, fork is a special case of a more general call, clone, which takes a flag for each resource: with the flag, the child shares the parent’s structure, and without it the child gets a copy. fork is clone with no sharing flags.

exec

exec keeps the task_struct and replaces what the process runs. The kernel reads the header of the program file, which is in the ELF format on Linux, to learn which parts of the file to map into memory and at which address execution starts. It builds a new address space, places the arguments and the environment variables on a new stack, and sets the processor to the entry point.

The table explains why the preparation between fork and exec works. Everything the shell arranges in that interval is in the left column.

exit and wait

A process ends by calling exit with a status, or because a signal ends it. In both cases the kernel releases its memory and closes its descriptors at once. The task_struct remains, with exit_state set to EXIT_ZOMBIE and the result in exit_code, because the parent has not yet asked for the result. A process in this condition is a zombie. It uses no memory and no CPU. It occupies a task_struct and a pid.

The parent collects the result with wait or waitpid, and the kernel then frees the task_struct. This is called reaping the child. wait delivers both kinds of ending in a single integer.

The exit status has 8 bits. A program that calls exit(300) is reported with status 44, the low 8 bits of 300. A shell folds the integer into its own $?: the exit status itself, or 128 + n for a process ended by signal n, so a process ended by SIGTERM, signal 15, appears as 143.

A parent that does not call wait leaves a zombie for each child that ends. The zombies disappear when the parent itself ends, for the reason given next.

Orphans

A zombie can be reaped only by its parent, so every process needs a living parent. When a process ends before its children, the children are orphans, and the kernel gives them a new parent at once. The new parent is process 1, the first process of the system, unless a closer ancestor has asked for the role: a process can declare itself a subreaper with prctl(PR_SET_CHILD_SUBREAPER), and it then adopts the orphans among its descendants. Process 1 and every subreaper call wait in a loop for exactly this purpose.

Processes and threads

task_struct has 2 numbers, pid and tgid, because the kernel schedules tasks, and a process can consist of several. A thread is a task that shares the address space, the descriptor table and the signal handlers of another task. It is created by clone with the sharing flags set, where fork sets none.

All threads of a process have the same tgid, the thread group ID, and each has its own pid. The number that getpid returns, and that we call the pid of a process, is the tgid. The number of each thread is visible under /proc/<pid>/task, and the Threads line of /proc/<pid>/status counts them. The sleep above has 1. A Go program always has several, because the Go runtime starts threads of its own to run goroutines.

Measuring processes

procfacts starts child processes with the standard libraries, os/exec in Go and std::process in Rust. Both perform the creation of the child and the exec in a single call, since a program with several threads cannot safely run arbitrary code between fork and exec. The Rust version uses the nix crate with the signal feature to send a signal.

$ cargo new procfacts
$ cargo add -p procfacts nix --features signal

field reads a field of /proc/<pid>/stat, a single line with the same information as status in a fixed order. Field 3 is the state letter and field 4 is the parent’s pid.

Listing 3.1 The imports of procfacts, in Go. code/go/procfacts/main.go

import (
	"errors"
	"fmt"
	"log"
	"os"
	"os/exec"
	"strconv"
	"strings"
	"syscall"
	"time"
)

Listing 3.2 The imports of procfacts, in Rust. code/rust/procfacts/src/main.rs

use std::fs;
use std::io;
use std::os::unix::process::ExitStatusExt;
use std::path::Path;
use std::process::{self, Command};
use std::thread;
use std::time::Duration;

use nix::sys::signal::{Signal, kill};
use nix::unistd::Pid;

Listing 3.3 Reading a field of a process's record, in Go. code/go/procfacts/main.go

// field returns one field of /proc/<pid>/stat, counted from 1. The second
// field, the command name, is in parentheses and may contain spaces, so the
// fields after it are counted from the closing parenthesis.
func field(pid, n int) (string, error) {
	stat, err := os.ReadFile(fmt.Sprintf("/proc/%d/stat", pid))

	if err != nil {
		return "", err
	}

	end := strings.LastIndexByte(string(stat), ')')
	rest := strings.Fields(string(stat[end+1:]))

	return rest[n-3], nil
}

// output runs a shell command and returns what it printed, without the final
// newline.
func output(script string) (string, error) {
	text, err := exec.Command("sh", "-c", script).Output()

	return strings.TrimSpace(string(text)), err
}

Listing 3.4 Reading a field of a process's record, in Rust. code/rust/procfacts/src/main.rs

/// Returns one field of `/proc/<pid>/stat`, counted from 1. The second field,
/// the command name, is in parentheses and may contain spaces, so the fields
/// after it are counted from the closing parenthesis.
fn field(pid: u32, n: usize) -> io::Result<String> {
    let stat = fs::read_to_string(format!("/proc/{pid}/stat"))?;
    let rest = stat.rsplit_once(')').map_or("", |(_, rest)| rest);

    rest.split_whitespace()
        .nth(n - 3)
        .map(str::to_owned)
        .ok_or_else(|| io::ErrorKind::InvalidData.into())
}

/// Runs a shell command and returns what it printed, without the final
/// newline.
fn output(script: &str) -> io::Result<String> {
    let output = Command::new("sh").args(["-c", script]).output()?;

    Ok(String::from_utf8_lossy(&output.stdout).trim().to_owned())
}

parent runs a shell that prints $PPID, the pid of its parent, and compares it with the pid of the program.

Listing 3.5 The parent of a child, in Go. code/go/procfacts/main.go

// parent asks a child for the number of its parent process.
func parent() error {
	text, err := output("echo $PPID")

	if err != nil {
		return err
	}

	fmt.Printf("the child's parent is this process: %v\n", text == strconv.Itoa(os.Getpid()))

	return nil
}

Listing 3.6 The parent of a child, in Rust. code/rust/procfacts/src/main.rs

/// Asks a child for the number of its parent process.
fn parent() -> io::Result<()> {
    let text = output("echo $PPID")?;

    println!(
        "the child's parent is this process: {}",
        text == process::id().to_string()
    );

    Ok(())
}

status runs a script and reports how it ended. The program calls it with exit 7, with exit 300, and with a script that sends itself SIGTERM.

Listing 3.7 Exit status and signal, in Go. code/go/procfacts/main.go

// status runs a script and reports how it terminated.
func status(script string) error {
	err := exec.Command("sh", "-c", script).Run()

	var exit *exec.ExitError

	if !errors.As(err, &exit) {
		return fmt.Errorf("%s: %v", script, err)
	}

	wait, ok := exit.Sys().(syscall.WaitStatus)

	switch {
	case ok && wait.Signaled():
		fmt.Printf("%s: killed by signal %d\n", script, wait.Signal())
	default:
		fmt.Printf("%s: exited with status %d\n", script, exit.ExitCode())
	}

	return nil
}

Listing 3.8 Exit status and signal, in Rust. code/rust/procfacts/src/main.rs

/// Runs a script and reports how it terminated.
fn status(script: &str) -> io::Result<()> {
    let status = Command::new("sh").args(["-c", script]).status()?;

    match (status.signal(), status.code()) {
        (Some(signal), _) => println!("{script}: killed by signal {signal}"),
        (None, Some(code)) => println!("{script}: exited with status {code}"),
        (None, None) => println!("{script}: {status}"),
    }

    Ok(())
}

execKeepsPid runs a shell that prints its pid, replaces itself with another shell by exec, and prints the pid again.

Listing 3.9 The pid before and after exec, in Go. code/go/procfacts/main.go

// execKeepsPid prints the process number of a shell before and after the
// shell replaces its program with exec.
func execKeepsPid() error {
	text, err := output(`echo $$; exec sh -c 'echo $$'`)

	if err != nil {
		return err
	}

	pids := strings.Fields(text)

	fmt.Printf("pid before and after exec: equal %v\n", len(pids) == 2 && pids[0] == pids[1])

	return nil
}

Listing 3.10 The pid before and after exec, in Rust. code/rust/procfacts/src/main.rs

/// Prints the process number of a shell before and after the shell replaces
/// its program with exec.
fn exec_keeps_pid() -> io::Result<()> {
    let text = output("echo $$; exec sh -c 'echo $$'")?;
    let pids: Vec<&str> = text.split_whitespace().collect();

    println!(
        "pid before and after exec: equal {}",
        pids.len() == 2 && pids[0] == pids[1]
    );

    Ok(())
}

zombie starts true, which exits immediately, and polls the state field until the child has ended. Then it waits for the child and checks whether the /proc entry still exists.

Listing 3.11 A child between exit and wait, in Go. code/go/procfacts/main.go

// zombie starts a child that exits at once, and reads its state before and
// after waiting for it.
func zombie() error {
	child := exec.Command("true")

	if err := child.Start(); err != nil {
		return err
	}

	pid := child.Process.Pid
	state, err := field(pid, 3)

	for err == nil && state != "Z" {
		time.Sleep(time.Millisecond)
		state, err = field(pid, 3)
	}

	if err != nil {
		return err
	}

	if err := child.Wait(); err != nil {
		return err
	}

	_, err = os.Stat(fmt.Sprintf("/proc/%d", pid))

	fmt.Printf("exited child: state %s before wait, /proc entry present after wait: %v\n", state, err == nil)

	return nil
}

Listing 3.12 A child between exit and wait, in Rust. code/rust/procfacts/src/main.rs

/// Starts a child that exits at once, and reads its state before and after
/// waiting for it.
fn zombie() -> io::Result<()> {
    let mut child = Command::new("true").spawn()?;
    let pid = child.id();

    let mut state = field(pid, 3)?;

    while state != "Z" {
        thread::sleep(Duration::from_millis(1));
        state = field(pid, 3)?;
    }

    child.wait()?;

    let present = Path::new(&format!("/proc/{pid}")).exists();
    println!("exited child: state {state} before wait, /proc entry present after wait: {present}");

    Ok(())
}

orphan runs a shell that starts sleep 30 in the background, prints the pid of the sleep, and exits. The sleep is then an orphan. The program reads the pid of its new parent and the name of that process.

Listing 3.13 The new parent of an orphan, in Go. code/go/procfacts/main.go

// orphan starts a shell that starts a background sleep and exits. The sleep
// outlives its parent, and the kernel gives it a new one.
func orphan() error {
	text, err := output("sleep 30 >/dev/null 2>&1 & echo $!")

	if err != nil {
		return err
	}

	pid, err := strconv.Atoi(text)

	if err != nil {
		return err
	}

	defer syscall.Kill(pid, syscall.SIGKILL)

	adopter, err := field(pid, 4)

	if err != nil {
		return err
	}

	name, err := os.ReadFile("/proc/" + adopter + "/comm")

	if err != nil {
		return err
	}

	fmt.Printf("orphan adopted by: %s\n", strings.TrimSpace(string(name)))

	return nil
}

Listing 3.14 The new parent of an orphan, in Rust. code/rust/procfacts/src/main.rs

/// Starts a shell that starts a background sleep and exits. The sleep
/// outlives its parent, and the kernel gives it a new one.
fn orphan() -> io::Result<()> {
    let text = output("sleep 30 >/dev/null 2>&1 & echo $!")?;

    let pid: u32 = text
        .parse()
        .map_err(|_| io::Error::from(io::ErrorKind::InvalidData))?;

    let adopter = field(pid, 4);
    kill(Pid::from_raw(pid as i32), Signal::SIGKILL)?;

    let name = fs::read_to_string(format!("/proc/{}/comm", adopter?))?;
    println!("orphan adopted by: {}", name.trim());

    Ok(())
}

the child's parent is this process: true
exit 7: exited with status 7
exit 300: exited with status 44
kill -TERM $$: killed by signal 15
pid before and after exec: equal true
exited child: state Z before wait, /proc entry present after wait: false
orphan adopted by: systemd

The process named systemd in the last line is the service manager of the user’s session, which has registered as a subreaper. On a system without one, the line would name process 1.

Modelling the process table

proctable is a model of the part of the kernel that this chapter describes: the table of processes, the allocation of pids, the zombie state, and the adoption of orphans.

The table maps a pid to an entry. last remembers the pid allocated most recently.

Listing 3.15 The imports of proctable, in Go. code/go/proctable/main.go

import (
	"errors"
	"fmt"
	"log"
	"slices"
	"strings"
)

Listing 3.16 The imports of proctable, in Rust. code/rust/proctable/src/main.rs

use std::collections::BTreeMap;
use std::fmt;

Listing 3.17 The process table, in Go. code/go/proctable/main.go

// The errors carry the names of the kernel's error codes for the same cases.
var (
	errAgain   = errors.New("EAGAIN: no process number is free")
	errNoChild = errors.New("ECHILD: the caller has no child to wait for")
	errSearch  = errors.New("ESRCH: no such process")
)

// initPid is the process that adopts orphans.
const initPid = 1

type state byte

const (
	running state = 'R'
	zombie  state = 'Z'
)

// A process is one entry of the table.
type process struct {
	parent int
	state  state
	status int
}

// A table maps process numbers to entries. last is the number given out most
// recently, and pidMax is the largest number allowed.
type table struct {
	procs  map[int]*process
	last   int
	pidMax int
}

func newTable(pidMax int) *table {
	return &table{
		procs:  map[int]*process{initPid: {state: running}},
		last:   initPid,
		pidMax: pidMax,
	}
}

Listing 3.18 The process table, in Rust. code/rust/proctable/src/main.rs

/// The errors carry the names of the kernel's error codes for the same cases.
#[derive(Debug)]
enum Error {
    Again,
    NoChild,
    Search,
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match self {
            Error::Again => "EAGAIN: no process number is free",
            Error::NoChild => "ECHILD: the caller has no child to wait for",
            Error::Search => "ESRCH: no such process",
        })
    }
}

impl std::error::Error for Error {}

/// The process that adopts orphans.
const INIT_PID: u32 = 1;

#[derive(Clone, Copy, PartialEq)]
enum State {
    Running,
    Zombie,
}

/// One entry of the table.
struct Process {
    parent: u32,
    state: State,
    status: i32,
}

/// Maps process numbers to entries. `last` is the number given out most
/// recently, and `pid_max` is the largest number allowed.
struct Table {
    procs: BTreeMap<u32, Process>,
    last: u32,
    pid_max: u32,
}

impl Table {
    fn new(pid_max: u32) -> Table {
        let init = Process {
            parent: 0,
            state: State::Running,
            status: 0,
        };

        Table {
            procs: BTreeMap::from([(INIT_PID, init)]),
            last: INIT_PID,
            pid_max,
        }
    }
}

allocate searches upward from last and wraps around at pidMax. A pid that has been freed is therefore reused only after all higher numbers have been tried. The delay protects programs that hold a pid: a process that stored the pid of another, to send it a signal later, would otherwise reach an unrelated new process if the number were reused quickly. /proc/sys/kernel/pid_max sets the limit, 4194304 on this machine.

Listing 3.19 Allocating a pid and creating a child, in Go. code/go/proctable/main.go

// allocate returns the first free number after last, wrapping around from
// pidMax to the number after initPid.
func (t *table) allocate() (int, error) {
	pid := t.last

	for range t.pidMax {
		pid++

		if pid > t.pidMax {
			pid = initPid + 1
		}

		if _, used := t.procs[pid]; !used {
			t.last = pid

			return pid, nil
		}
	}

	return 0, errAgain
}

// fork creates a child of parent and returns the child's number.
func (t *table) fork(parent int) (int, error) {
	if _, ok := t.procs[parent]; !ok {
		return 0, errSearch
	}

	pid, err := t.allocate()

	if err != nil {
		return 0, err
	}

	t.procs[pid] = &process{parent: parent, state: running}

	return pid, nil
}

Listing 3.20 Allocating a pid and creating a child, in Rust. code/rust/proctable/src/main.rs

impl Table {
    /// Returns the first free number after `last`, wrapping around from
    /// `pid_max` to the number after `INIT_PID`.
    fn allocate(&mut self) -> Result<u32, Error> {
        let mut pid = self.last;

        for _ in 0..self.pid_max {
            pid += 1;

            if pid > self.pid_max {
                pid = INIT_PID + 1;
            }

            if !self.procs.contains_key(&pid) {
                self.last = pid;

                return Ok(pid);
            }
        }

        Err(Error::Again)
    }

    /// Creates a child of `parent` and returns the child's number.
    fn fork(&mut self, parent: u32) -> Result<u32, Error> {
        if !self.procs.contains_key(&parent) {
            return Err(Error::Search);
        }

        let pid = self.allocate()?;

        let child = Process {
            parent,
            state: State::Running,
            status: 0,
        };

        self.procs.insert(pid, child);

        Ok(pid)
    }
}

exit keeps the entry and changes its state. It then gives every child of the ended process to process 1.

Listing 3.21 Ending a process, in Go. code/go/proctable/main.go

// exit ends a process. The entry stays in the table as a zombie that holds
// the exit status, and the children of the process become children of init.
func (t *table) exit(pid, status int) error {
	p, ok := t.procs[pid]

	if !ok {
		return errSearch
	}

	p.state, p.status = zombie, status

	for _, child := range t.procs {
		if child.parent == pid {
			child.parent = initPid
		}
	}

	return nil
}

Listing 3.22 Ending a process, in Rust. code/rust/proctable/src/main.rs

impl Table {
    /// Ends a process. The entry stays in the table as a zombie that holds
    /// the exit status, and the children of the process become children of
    /// init.
    fn exit(&mut self, pid: u32, status: i32) -> Result<(), Error> {
        let process = self.procs.get_mut(&pid).ok_or(Error::Search)?;

        process.state = State::Zombie;
        process.status = status;

        for child in self.procs.values_mut() {
            if child.parent == pid {
                child.parent = INIT_PID;
            }
        }

        Ok(())
    }
}

wait has 3 outcomes. A zombie child exists, and it is removed and returned. Children exist and none has ended, where the kernel would put the caller to sleep. Or the caller has no children, which is the error ECHILD.

Listing 3.23 Collecting a child, in Go. code/go/proctable/main.go

// wait removes a zombie child of parent from the table and returns its number
// and exit status. ok is false when parent has children and none of them has
// exited, the case in which the kernel suspends the caller.
func (t *table) wait(parent int) (pid, status int, ok bool, err error) {
	children := 0

	for _, pid := range t.pids() {
		child := t.procs[pid]

		if child.parent != parent {
			continue
		}

		children++

		if child.state == zombie {
			delete(t.procs, pid)

			return pid, child.status, true, nil
		}
	}

	if children == 0 {
		return 0, 0, false, errNoChild
	}

	return 0, 0, false, nil
}

// pids returns the process numbers in use, in increasing order.
func (t *table) pids() []int {
	pids := make([]int, 0, len(t.procs))

	for pid := range t.procs {
		pids = append(pids, pid)
	}

	slices.Sort(pids)

	return pids
}

Listing 3.24 Collecting a child, in Rust. code/rust/proctable/src/main.rs

impl Table {
    /// Removes a zombie child of `parent` from the table and returns its
    /// number and exit status. The result is `None` when `parent` has
    /// children and none of them has exited, the case in which the kernel
    /// suspends the caller.
    fn wait(&mut self, parent: u32) -> Result<Option<(u32, i32)>, Error> {
        let mut children = self
            .procs
            .iter()
            .filter(|(_, child)| child.parent == parent)
            .peekable();

        if children.peek().is_none() {
            return Err(Error::NoChild);
        }

        let Some((&pid, child)) = children.find(|(_, child)| child.state == State::Zombie) else {
            return Ok(None);
        };

        let status = child.status;
        self.procs.remove(&pid);

        Ok(Some((pid, status)))
    }
}

The program applies a sequence of calls to a table with pidMax set to 6 and prints the table after each call. An entry is printed as pid(parent)state.

Listing 3.25 The trace, in Go. code/go/proctable/main.go

// String renders the table as pid(parent)state for each entry.
func (t *table) String() string {
	var cells []string

	for _, pid := range t.pids() {
		p := t.procs[pid]
		cells = append(cells, fmt.Sprintf("%d(%d)%c", pid, p.parent, p.state))
	}

	return strings.Join(cells, " ")
}

// A call is one step of the trace: an operation, the process it applies to,
// and for exit the status.
type call struct {
	op     string
	pid    int
	status int
}

// apply performs a call and describes its result.
func (t *table) apply(c call) (string, error) {
	switch c.op {
	case "fork":
		child, err := t.fork(c.pid)

		return fmt.Sprintf("fork by %d: pid %d", c.pid, child), err

	case "exit":
		return fmt.Sprintf("exit of %d, status %d", c.pid, c.status), t.exit(c.pid, c.status)

	default:
		child, status, ok, err := t.wait(c.pid)

		if !ok {
			return fmt.Sprintf("wait by %d: would block", c.pid), err
		}

		return fmt.Sprintf("wait by %d: pid %d, status %d", c.pid, child, status), nil
	}
}

func main() {
	t := newTable(6)

	calls := []call{
		{op: "fork", pid: 1},
		{op: "fork", pid: 2},
		{op: "fork", pid: 3},
		{op: "wait", pid: 2},
		{op: "exit", pid: 3},
		{op: "wait", pid: 2},
		{op: "fork", pid: 2},
		{op: "exit", pid: 4, status: 7},
		{op: "wait", pid: 1},
		{op: "fork", pid: 2},
		{op: "fork", pid: 2},
	}

	fmt.Printf("%-30s %s\n", "start", t)

	for _, c := range calls {
		result, err := t.apply(c)

		if err != nil {
			log.Fatal(err)
		}

		fmt.Printf("%-30s %s\n", result, t)
	}
}

Listing 3.26 The trace, in Rust. code/rust/proctable/src/main.rs

/// Renders the table as pid(parent)state for each entry.
impl fmt::Display for Table {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let cells: Vec<String> = self
            .procs
            .iter()
            .map(|(pid, process)| {
                let state = match process.state {
                    State::Running => 'R',
                    State::Zombie => 'Z',
                };

                format!("{pid}({}){state}", process.parent)
            })
            .collect();

        f.write_str(&cells.join(" "))
    }
}

/// One step of the trace.
enum Call {
    Fork(u32),
    Exit(u32, i32),
    Wait(u32),
}

impl Table {
    /// Performs a call and describes its result.
    fn apply(&mut self, call: &Call) -> Result<String, Error> {
        match *call {
            Call::Fork(parent) => {
                let child = self.fork(parent)?;

                Ok(format!("fork by {parent}: pid {child}"))
            }
            Call::Exit(pid, status) => {
                self.exit(pid, status)?;

                Ok(format!("exit of {pid}, status {status}"))
            }
            Call::Wait(parent) => match self.wait(parent)? {
                Some((child, status)) => {
                    Ok(format!("wait by {parent}: pid {child}, status {status}"))
                }
                None => Ok(format!("wait by {parent}: would block")),
            },
        }
    }
}

fn main() -> Result<(), Error> {
    let mut table = Table::new(6);

    let calls = [
        Call::Fork(1),
        Call::Fork(2),
        Call::Fork(3),
        Call::Wait(2),
        Call::Exit(3, 0),
        Call::Wait(2),
        Call::Fork(2),
        Call::Exit(4, 7),
        Call::Wait(1),
        Call::Fork(2),
        Call::Fork(2),
    ];

    println!("{:<30} {table}", "start");

    for call in &calls {
        let result = table.apply(call)?;
        println!("{result:<30} {table}");
    }

    Ok(())
}

start                          1(0)R
fork by 1: pid 2               1(0)R 2(1)R
fork by 2: pid 3               1(0)R 2(1)R 3(2)R
fork by 3: pid 4               1(0)R 2(1)R 3(2)R 4(3)R
wait by 2: would block         1(0)R 2(1)R 3(2)R 4(3)R
exit of 3, status 0            1(0)R 2(1)R 3(2)Z 4(1)R
wait by 2: pid 3, status 0     1(0)R 2(1)R 4(1)R
fork by 2: pid 5               1(0)R 2(1)R 4(1)R 5(2)R
exit of 4, status 7            1(0)R 2(1)R 4(1)Z 5(2)R
wait by 1: pid 4, status 7     1(0)R 2(1)R 5(2)R
fork by 2: pid 6               1(0)R 2(1)R 5(2)R 6(2)R
fork by 2: pid 3               1(0)R 2(1)R 3(2)R 5(2)R 6(2)R

Inspecting processes on a live system

A zombie cannot be removed with kill, since it has already ended. The last command gives the pid of the parent, and the remedy is there: the parent has to call wait, or end.

The complete programs

Listing 3.27 The complete procfacts, in Go. code/go/procfacts/main.go

// Command procfacts measures the life cycle of a process: who its parent is,
// how its termination is reported, what exec keeps, what remains of a child
// that has exited and has not been waited for, and who becomes the parent of
// an orphan.
//
// Run it from code/go with:
//
//	go run ./procfacts
package main

import (
	"errors"
	"fmt"
	"log"
	"os"
	"os/exec"
	"strconv"
	"strings"
	"syscall"
	"time"
)


// field returns one field of /proc/<pid>/stat, counted from 1. The second
// field, the command name, is in parentheses and may contain spaces, so the
// fields after it are counted from the closing parenthesis.
func field(pid, n int) (string, error) {
	stat, err := os.ReadFile(fmt.Sprintf("/proc/%d/stat", pid))

	if err != nil {
		return "", err
	}

	end := strings.LastIndexByte(string(stat), ')')
	rest := strings.Fields(string(stat[end+1:]))

	return rest[n-3], nil
}

// output runs a shell command and returns what it printed, without the final
// newline.
func output(script string) (string, error) {
	text, err := exec.Command("sh", "-c", script).Output()

	return strings.TrimSpace(string(text)), err
}


// parent asks a child for the number of its parent process.
func parent() error {
	text, err := output("echo $PPID")

	if err != nil {
		return err
	}

	fmt.Printf("the child's parent is this process: %v\n", text == strconv.Itoa(os.Getpid()))

	return nil
}


// status runs a script and reports how it terminated.
func status(script string) error {
	err := exec.Command("sh", "-c", script).Run()

	var exit *exec.ExitError

	if !errors.As(err, &exit) {
		return fmt.Errorf("%s: %v", script, err)
	}

	wait, ok := exit.Sys().(syscall.WaitStatus)

	switch {
	case ok && wait.Signaled():
		fmt.Printf("%s: killed by signal %d\n", script, wait.Signal())
	default:
		fmt.Printf("%s: exited with status %d\n", script, exit.ExitCode())
	}

	return nil
}


// execKeepsPid prints the process number of a shell before and after the
// shell replaces its program with exec.
func execKeepsPid() error {
	text, err := output(`echo $$; exec sh -c 'echo $$'`)

	if err != nil {
		return err
	}

	pids := strings.Fields(text)

	fmt.Printf("pid before and after exec: equal %v\n", len(pids) == 2 && pids[0] == pids[1])

	return nil
}


// zombie starts a child that exits at once, and reads its state before and
// after waiting for it.
func zombie() error {
	child := exec.Command("true")

	if err := child.Start(); err != nil {
		return err
	}

	pid := child.Process.Pid
	state, err := field(pid, 3)

	for err == nil && state != "Z" {
		time.Sleep(time.Millisecond)
		state, err = field(pid, 3)
	}

	if err != nil {
		return err
	}

	if err := child.Wait(); err != nil {
		return err
	}

	_, err = os.Stat(fmt.Sprintf("/proc/%d", pid))

	fmt.Printf("exited child: state %s before wait, /proc entry present after wait: %v\n", state, err == nil)

	return nil
}


// orphan starts a shell that starts a background sleep and exits. The sleep
// outlives its parent, and the kernel gives it a new one.
func orphan() error {
	text, err := output("sleep 30 >/dev/null 2>&1 & echo $!")

	if err != nil {
		return err
	}

	pid, err := strconv.Atoi(text)

	if err != nil {
		return err
	}

	defer syscall.Kill(pid, syscall.SIGKILL)

	adopter, err := field(pid, 4)

	if err != nil {
		return err
	}

	name, err := os.ReadFile("/proc/" + adopter + "/comm")

	if err != nil {
		return err
	}

	fmt.Printf("orphan adopted by: %s\n", strings.TrimSpace(string(name)))

	return nil
}


func main() {
	experiments := []func() error{
		parent,
		func() error { return status("exit 7") },
		func() error { return status("exit 300") },
		func() error { return status("kill -TERM $$") },
		execKeepsPid,
		zombie,
		orphan,
	}

	for _, experiment := range experiments {
		if err := experiment(); err != nil {
			log.Fatal(err)
		}
	}
}

Listing 3.28 The complete procfacts, in Rust. code/rust/procfacts/src/main.rs

//! Measures the life cycle of a process: who its parent is, how its
//! termination is reported, what exec keeps, what remains of a child that has
//! exited and has not been waited for, and who becomes the parent of an
//! orphan.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p procfacts
//! ```

use std::fs;
use std::io;
use std::os::unix::process::ExitStatusExt;
use std::path::Path;
use std::process::{self, Command};
use std::thread;
use std::time::Duration;

use nix::sys::signal::{Signal, kill};
use nix::unistd::Pid;

/// Returns one field of `/proc/<pid>/stat`, counted from 1. The second field,
/// the command name, is in parentheses and may contain spaces, so the fields
/// after it are counted from the closing parenthesis.
fn field(pid: u32, n: usize) -> io::Result<String> {
    let stat = fs::read_to_string(format!("/proc/{pid}/stat"))?;
    let rest = stat.rsplit_once(')').map_or("", |(_, rest)| rest);

    rest.split_whitespace()
        .nth(n - 3)
        .map(str::to_owned)
        .ok_or_else(|| io::ErrorKind::InvalidData.into())
}

/// Runs a shell command and returns what it printed, without the final
/// newline.
fn output(script: &str) -> io::Result<String> {
    let output = Command::new("sh").args(["-c", script]).output()?;

    Ok(String::from_utf8_lossy(&output.stdout).trim().to_owned())
}

/// Asks a child for the number of its parent process.
fn parent() -> io::Result<()> {
    let text = output("echo $PPID")?;

    println!(
        "the child's parent is this process: {}",
        text == process::id().to_string()
    );

    Ok(())
}

/// Runs a script and reports how it terminated.
fn status(script: &str) -> io::Result<()> {
    let status = Command::new("sh").args(["-c", script]).status()?;

    match (status.signal(), status.code()) {
        (Some(signal), _) => println!("{script}: killed by signal {signal}"),
        (None, Some(code)) => println!("{script}: exited with status {code}"),
        (None, None) => println!("{script}: {status}"),
    }

    Ok(())
}

/// Prints the process number of a shell before and after the shell replaces
/// its program with exec.
fn exec_keeps_pid() -> io::Result<()> {
    let text = output("echo $$; exec sh -c 'echo $$'")?;
    let pids: Vec<&str> = text.split_whitespace().collect();

    println!(
        "pid before and after exec: equal {}",
        pids.len() == 2 && pids[0] == pids[1]
    );

    Ok(())
}

/// Starts a child that exits at once, and reads its state before and after
/// waiting for it.
fn zombie() -> io::Result<()> {
    let mut child = Command::new("true").spawn()?;
    let pid = child.id();

    let mut state = field(pid, 3)?;

    while state != "Z" {
        thread::sleep(Duration::from_millis(1));
        state = field(pid, 3)?;
    }

    child.wait()?;

    let present = Path::new(&format!("/proc/{pid}")).exists();
    println!("exited child: state {state} before wait, /proc entry present after wait: {present}");

    Ok(())
}

/// Starts a shell that starts a background sleep and exits. The sleep
/// outlives its parent, and the kernel gives it a new one.
fn orphan() -> io::Result<()> {
    let text = output("sleep 30 >/dev/null 2>&1 & echo $!")?;

    let pid: u32 = text
        .parse()
        .map_err(|_| io::Error::from(io::ErrorKind::InvalidData))?;

    let adopter = field(pid, 4);
    kill(Pid::from_raw(pid as i32), Signal::SIGKILL)?;

    let name = fs::read_to_string(format!("/proc/{}/comm", adopter?))?;
    println!("orphan adopted by: {}", name.trim());

    Ok(())
}

fn main() -> io::Result<()> {
    parent()?;
    status("exit 7")?;
    status("exit 300")?;
    status("kill -TERM $$")?;
    exec_keeps_pid()?;
    zombie()?;
    orphan()
}

Listing 3.29 The complete proctable, in Go. code/go/proctable/main.go

// Command proctable models the kernel's process table: process numbers handed
// out in a cycle, a parent for every process, a zombie state between exit and
// wait, and a new parent for orphans. It applies a sequence of calls and
// prints the table after each.
//
// Run it from code/go with:
//
//	go run ./proctable
package main

import (
	"errors"
	"fmt"
	"log"
	"slices"
	"strings"
)


// The errors carry the names of the kernel's error codes for the same cases.
var (
	errAgain   = errors.New("EAGAIN: no process number is free")
	errNoChild = errors.New("ECHILD: the caller has no child to wait for")
	errSearch  = errors.New("ESRCH: no such process")
)

// initPid is the process that adopts orphans.
const initPid = 1

type state byte

const (
	running state = 'R'
	zombie  state = 'Z'
)

// A process is one entry of the table.
type process struct {
	parent int
	state  state
	status int
}

// A table maps process numbers to entries. last is the number given out most
// recently, and pidMax is the largest number allowed.
type table struct {
	procs  map[int]*process
	last   int
	pidMax int
}

func newTable(pidMax int) *table {
	return &table{
		procs:  map[int]*process{initPid: {state: running}},
		last:   initPid,
		pidMax: pidMax,
	}
}


// allocate returns the first free number after last, wrapping around from
// pidMax to the number after initPid.
func (t *table) allocate() (int, error) {
	pid := t.last

	for range t.pidMax {
		pid++

		if pid > t.pidMax {
			pid = initPid + 1
		}

		if _, used := t.procs[pid]; !used {
			t.last = pid

			return pid, nil
		}
	}

	return 0, errAgain
}

// fork creates a child of parent and returns the child's number.
func (t *table) fork(parent int) (int, error) {
	if _, ok := t.procs[parent]; !ok {
		return 0, errSearch
	}

	pid, err := t.allocate()

	if err != nil {
		return 0, err
	}

	t.procs[pid] = &process{parent: parent, state: running}

	return pid, nil
}


// exit ends a process. The entry stays in the table as a zombie that holds
// the exit status, and the children of the process become children of init.
func (t *table) exit(pid, status int) error {
	p, ok := t.procs[pid]

	if !ok {
		return errSearch
	}

	p.state, p.status = zombie, status

	for _, child := range t.procs {
		if child.parent == pid {
			child.parent = initPid
		}
	}

	return nil
}


// wait removes a zombie child of parent from the table and returns its number
// and exit status. ok is false when parent has children and none of them has
// exited, the case in which the kernel suspends the caller.
func (t *table) wait(parent int) (pid, status int, ok bool, err error) {
	children := 0

	for _, pid := range t.pids() {
		child := t.procs[pid]

		if child.parent != parent {
			continue
		}

		children++

		if child.state == zombie {
			delete(t.procs, pid)

			return pid, child.status, true, nil
		}
	}

	if children == 0 {
		return 0, 0, false, errNoChild
	}

	return 0, 0, false, nil
}

// pids returns the process numbers in use, in increasing order.
func (t *table) pids() []int {
	pids := make([]int, 0, len(t.procs))

	for pid := range t.procs {
		pids = append(pids, pid)
	}

	slices.Sort(pids)

	return pids
}


// String renders the table as pid(parent)state for each entry.
func (t *table) String() string {
	var cells []string

	for _, pid := range t.pids() {
		p := t.procs[pid]
		cells = append(cells, fmt.Sprintf("%d(%d)%c", pid, p.parent, p.state))
	}

	return strings.Join(cells, " ")
}

// A call is one step of the trace: an operation, the process it applies to,
// and for exit the status.
type call struct {
	op     string
	pid    int
	status int
}

// apply performs a call and describes its result.
func (t *table) apply(c call) (string, error) {
	switch c.op {
	case "fork":
		child, err := t.fork(c.pid)

		return fmt.Sprintf("fork by %d: pid %d", c.pid, child), err

	case "exit":
		return fmt.Sprintf("exit of %d, status %d", c.pid, c.status), t.exit(c.pid, c.status)

	default:
		child, status, ok, err := t.wait(c.pid)

		if !ok {
			return fmt.Sprintf("wait by %d: would block", c.pid), err
		}

		return fmt.Sprintf("wait by %d: pid %d, status %d", c.pid, child, status), nil
	}
}

func main() {
	t := newTable(6)

	calls := []call{
		{op: "fork", pid: 1},
		{op: "fork", pid: 2},
		{op: "fork", pid: 3},
		{op: "wait", pid: 2},
		{op: "exit", pid: 3},
		{op: "wait", pid: 2},
		{op: "fork", pid: 2},
		{op: "exit", pid: 4, status: 7},
		{op: "wait", pid: 1},
		{op: "fork", pid: 2},
		{op: "fork", pid: 2},
	}

	fmt.Printf("%-30s %s\n", "start", t)

	for _, c := range calls {
		result, err := t.apply(c)

		if err != nil {
			log.Fatal(err)
		}

		fmt.Printf("%-30s %s\n", result, t)
	}
}

Listing 3.30 The complete proctable, in Rust. code/rust/proctable/src/main.rs

//! Models the kernel's process table: process numbers handed out in a cycle,
//! a parent for every process, a zombie state between exit and wait, and a
//! new parent for orphans. It applies a sequence of calls and prints the
//! table after each.
//!
//! Run it from code/rust with:
//!
//! ```text
//! cargo run -p proctable
//! ```

use std::collections::BTreeMap;
use std::fmt;

/// The errors carry the names of the kernel's error codes for the same cases.
#[derive(Debug)]
enum Error {
    Again,
    NoChild,
    Search,
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str(match self {
            Error::Again => "EAGAIN: no process number is free",
            Error::NoChild => "ECHILD: the caller has no child to wait for",
            Error::Search => "ESRCH: no such process",
        })
    }
}

impl std::error::Error for Error {}

/// The process that adopts orphans.
const INIT_PID: u32 = 1;

#[derive(Clone, Copy, PartialEq)]
enum State {
    Running,
    Zombie,
}

/// One entry of the table.
struct Process {
    parent: u32,
    state: State,
    status: i32,
}

/// Maps process numbers to entries. `last` is the number given out most
/// recently, and `pid_max` is the largest number allowed.
struct Table {
    procs: BTreeMap<u32, Process>,
    last: u32,
    pid_max: u32,
}

impl Table {
    fn new(pid_max: u32) -> Table {
        let init = Process {
            parent: 0,
            state: State::Running,
            status: 0,
        };

        Table {
            procs: BTreeMap::from([(INIT_PID, init)]),
            last: INIT_PID,
            pid_max,
        }
    }
}

impl Table {
    /// Returns the first free number after `last`, wrapping around from
    /// `pid_max` to the number after `INIT_PID`.
    fn allocate(&mut self) -> Result<u32, Error> {
        let mut pid = self.last;

        for _ in 0..self.pid_max {
            pid += 1;

            if pid > self.pid_max {
                pid = INIT_PID + 1;
            }

            if !self.procs.contains_key(&pid) {
                self.last = pid;

                return Ok(pid);
            }
        }

        Err(Error::Again)
    }

    /// Creates a child of `parent` and returns the child's number.
    fn fork(&mut self, parent: u32) -> Result<u32, Error> {
        if !self.procs.contains_key(&parent) {
            return Err(Error::Search);
        }

        let pid = self.allocate()?;

        let child = Process {
            parent,
            state: State::Running,
            status: 0,
        };

        self.procs.insert(pid, child);

        Ok(pid)
    }
}

impl Table {
    /// Ends a process. The entry stays in the table as a zombie that holds
    /// the exit status, and the children of the process become children of
    /// init.
    fn exit(&mut self, pid: u32, status: i32) -> Result<(), Error> {
        let process = self.procs.get_mut(&pid).ok_or(Error::Search)?;

        process.state = State::Zombie;
        process.status = status;

        for child in self.procs.values_mut() {
            if child.parent == pid {
                child.parent = INIT_PID;
            }
        }

        Ok(())
    }
}

impl Table {
    /// Removes a zombie child of `parent` from the table and returns its
    /// number and exit status. The result is `None` when `parent` has
    /// children and none of them has exited, the case in which the kernel
    /// suspends the caller.
    fn wait(&mut self, parent: u32) -> Result<Option<(u32, i32)>, Error> {
        let mut children = self
            .procs
            .iter()
            .filter(|(_, child)| child.parent == parent)
            .peekable();

        if children.peek().is_none() {
            return Err(Error::NoChild);
        }

        let Some((&pid, child)) = children.find(|(_, child)| child.state == State::Zombie) else {
            return Ok(None);
        };

        let status = child.status;
        self.procs.remove(&pid);

        Ok(Some((pid, status)))
    }
}

/// Renders the table as pid(parent)state for each entry.
impl fmt::Display for Table {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let cells: Vec<String> = self
            .procs
            .iter()
            .map(|(pid, process)| {
                let state = match process.state {
                    State::Running => 'R',
                    State::Zombie => 'Z',
                };

                format!("{pid}({}){state}", process.parent)
            })
            .collect();

        f.write_str(&cells.join(" "))
    }
}

/// One step of the trace.
enum Call {
    Fork(u32),
    Exit(u32, i32),
    Wait(u32),
}

impl Table {
    /// Performs a call and describes its result.
    fn apply(&mut self, call: &Call) -> Result<String, Error> {
        match *call {
            Call::Fork(parent) => {
                let child = self.fork(parent)?;

                Ok(format!("fork by {parent}: pid {child}"))
            }
            Call::Exit(pid, status) => {
                self.exit(pid, status)?;

                Ok(format!("exit of {pid}, status {status}"))
            }
            Call::Wait(parent) => match self.wait(parent)? {
                Some((child, status)) => {
                    Ok(format!("wait by {parent}: pid {child}, status {status}"))
                }
                None => Ok(format!("wait by {parent}: would block")),
            },
        }
    }
}

fn main() -> Result<(), Error> {
    let mut table = Table::new(6);

    let calls = [
        Call::Fork(1),
        Call::Fork(2),
        Call::Fork(3),
        Call::Wait(2),
        Call::Exit(3, 0),
        Call::Wait(2),
        Call::Fork(2),
        Call::Exit(4, 7),
        Call::Wait(1),
        Call::Fork(2),
        Call::Fork(2),
    ];

    println!("{:<30} {table}", "start");

    for call in &calls {
        let result = table.apply(call)?;
        println!("{result:<30} {table}");
    }

    Ok(())
}

References

• fork(2), clone(2), execve(2), wait(2), prctl(2) and proc(5), Linux manual pages: https://man7.org/linux/man-pages/man2/fork.2.html
• M. Kerrisk, The Linux Programming Interface, No Starch Press, 2010, chapters 6 and 24 to 28.
• include/linux/sched.h, kernel/fork.c, kernel/exit.c and kernel/pid.c, Linux 5.15: https://elixir.bootlin.com/linux/v5.15/source/kernel/fork.c