Software Engineering Implementation

every build system — make, ninja, bazel, cargo, even npm scripts pretending otherwise — is the same machine: a directed acyclic graph of files and commands, plus a policy for deciding which part of the graph is stale. everything else is syntax.

the model: a dag of targets#

• a target is a file the build can produce; a rule says how (a command) and from what (its dependencies).
• dependencies point from outputs to inputs; because outputs of one rule are inputs to another, the whole thing is a dag — a cycle would mean “to build a you must first build a”.
• a build is then two steps:
  1. mark dirty: a target is dirty if it is missing, if any dependency is dirty, or if the staleness policy (timestamps or hashes, below) says an input changed. dirtiness propagates along edges — one flipped source poisons its whole downstream cone.
  2. evaluate in topological order: run each dirty target’s command after all its dependencies are up to date (Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford, 2009). independent dirty targets can run in parallel (-j8) — the dag is the parallelism plan, which is why builds are embarrassingly parallel until the link step serialises everything.
• the entire correctness contract: the graph must be complete. every undeclared dependency is a future “works after make clean” bug — the build system faithfully skips rebuilding things it was never told could change.

make: the actual semantics#

make’s whole rebuild rule fits in one sentence: a target is rebuilt if it does not exist, or if any prerequisite’s mtime is newer than the target’s mtime. everything else is macro expansion.

concurrency is structure: many logical tasks in flight, interleaved on however many cpus you have (possibly one). parallelism is hardware: tasks literally executing at the same instant. a single-core machine juggling 400 socket connections is concurrent, not parallel; a gpu multiplying matrices is parallel, barely concurrent. you design concurrency; you buy parallelism (Tanenbaum, Andrew S., 2008).

threads and shared memory#

a thread is an independent stream of execution inside one address space: own stack and registers, shared everything else. the sharing is the point — and the disease.

a container is not a small virtual machine. it is an ordinary linux process (tree) that the kernel has been told to lie to — about what processes exist, what the filesystem looks like, what the network is, who root is — plus an accountant capping what it may consume. the lying is namespaces, the accounting is cgroups, and everything else (images, registries, orchestrators) is packaging around those two syscall families (Tanenbaum, Andrew S., 2008).