Timestamp-Based Incrementality and Its Failure Modes

The first incremental build system was probably an accident of the file interface: every attempt to rebuild everything is wasteful, and the operating system already records when each file was last written. Comparing those records gives a cheap predicate for staleness, requiring no bookkeeping beyond what the filesystem maintains for other reasons. That predicate is still the default in most build tools, and understanding where it is wrong explains most of the strange behaviour that arises when a build is worked around rather than fixed.

The staleness predicate

The rule, stated normatively in the POSIX specification for make, is that a target is out of date if it does not exist or if any of its prerequisites was modified at a later time than the target. Implementation is a pair of stat calls per edge and a comparison of the resulting timestamps. A rebuild then rewrites the target, whose timestamp becomes later than its prerequisites, and the process moves up the graph toward the requested outputs.

Two details matter more than they appear. First, the comparison is over the timestamps recorded by the filesystem, not over content. Two files with identical bytes but different write times are treated as different, and a file whose bytes changed while its timestamp stayed the same is treated as unchanged. Second, the predicate is evaluated per edge but the decision propagates transitively: an intermediate that was rebuilt becomes newer than its own consumers, so they are stale too. This is the mechanism by which a single source edit can trigger a long chain of rebuilds even though only one object file’s content actually changed.

# The predicate expressed directly: rebuild when the object is missing or
# when any prerequisite has a later modification time.
if [ ! -e app.o ] || [ app.c -nt app.o ] || [ util.h -nt app.o ]; then
    cc -c app.c -o app.o
fi

Note that the shell test compares timestamps with whatever resolution the filesystem reports, so the comparison inherits every property of the metadata the kernel stores.

Granularity: the unit of time

Timestamps are not continuous. Historically tar archives stored modification times with one-second resolution, and some filesystems stored modification times with two-second resolution on FAT. Linux ext3 recorded seconds; ext4 and most modern Linux filesystems record nanoseconds, and the stat structure exposes both whole seconds and a nanosecond field. The practical consequence is that on a filesystem with one-second granularity, a source edit and the subsequent compile can land within the same second, and the comparison cannot distinguish them.

Tools respond to this in different ways. Some compare with a small tolerance, treating files whose timestamps differ by less than a threshold as equal. That converts a false staleness into a missed rebuild, which is the more dangerous direction: the build silently produces an artefact from stale inputs. GNU Make’s manual notes the general problem with the timestamp model and provides options to force unconditional rebuilding of named targets, which is a way to escape the ambiguity for targets where correctness matters most.

The failure is easy to construct without any exotic filesystem. Write a source file, invoke the build, and have the whole thing complete in well under the filesystem’s timestamp resolution. Whether the next invocation rebuilds depends on details of how the timestamps were rounded, not on whether the content changed.

Clock skew and the direction of comparison

The predicate compares two timestamps, and nothing requires them to come from the same clock. A file on a network filesystem is timestamped by the server; a file in a build directory is timestamped by the client. If the two clocks disagree by more than the build’s duration, the comparison is decided by the skew rather than by the order of events.

The typical symptom is a build that never stops rebuilding. If the object files are written by a machine whose clock runs behind the source tree’s server, the objects are consistently older than their prerequisites and the same actions run every time. The opposite skew produces a build that never rebuilds a target it should: the target appears newer than the source that changed. Both are invisible in the build output, because the tool is reporting a comparison it believes.

The usual mitigation is to make one machine the authority for timestamps, by building on the same host as the sources or mounting with the server’s clock as the reference, but this does not generalise to build farms, where the inputs may be materialised on a worker that has never seen the original tree.

Restoration invalidates the signal

Any operation that rewrites a file’s timestamp without changing its content confuses the predicate in the safe direction, and any operation that changes content while preserving the timestamp confuses it in the unsafe direction.

Version control checkouts set every file’s modification time to the moment of checkout, so a freshly cloned tree is uniformly “newer” than any pre-existing build output and everything rebuilds once. Archive extraction is worse: tar restores the stored modification times, so extracting an archive of old sources produces files that are older than the build outputs derived from them, and those outputs are considered current even though they were built from different content. The same effect appears with cp -p, with filesystem snapshots, and with synchronisation tools that preserve times.

The safe direction is easier to live with. touch on a header that did not change forces rebuilds of everything that includes it, which is exactly what a conservative system should do, but on a project where a widely included header is touched it invalidates a large fraction of the graph. This is the cost axis of the design: the predicate is cheap to evaluate and imposes no storage beyond the filesystem’s own metadata, and it pays for that economy by being unable to distinguish “newer and different” from “newer and identical”.

Tools that use the timestamp predicate often add a second, independent check for the case that matters most. Ninja records each edge’s command line in a log file alongside the build; if the command line for an edge differs from the logged one, the edge is dirty regardless of timestamps. This catches the common case of a build file edited to add a flag, where the source files are unchanged and no timestamp comparison would notice. Ninja also supports an edge attribute that compares output timestamps before and after running an action, so that an action which rewrites a file with identical content can stop the rebuild from propagating further up the graph.

What the alternatives cost

Replacing the timestamp with a content digest removes every failure above. The staleness predicate becomes “the hash of the inputs differs from the hash recorded when the output was produced”, which is insensitive to clocks, to granularity, to file restoration, and to identical rewrites. The price is that evaluating the predicate requires reading every input, or maintaining a cache of path, size, and modification-time triples that is revalidated against the digest on suspicion, which is the same trick used by version control index files and by synchronisation tools.

The trade is storage and I/O against correctness and precision. On a tree of a few thousand small files the difference is not visible. On a tree where the inputs total tens of gigabytes, hashing every input on every invocation is more expensive than the compilation the build is trying to avoid, which is why hybrid schemes dominate in practice: timestamps for the cheap screen, digests for the decision that matters. The mechanism that makes digests useful beyond staleness, skipping the rebuild entirely when the new output is byte-identical to the old one, is the subject of Content-Hash Caching and Early Cutoff, and the way the resulting digests are used as keys in a shared store is covered in Action Cache Keys and Shared Build Caches.

One further consequence of the timestamp model deserves mention because it constrains the whole design: because staleness is evaluated on the filesystem rather than on a recorded decision, a build can be started on a tree that another process is editing. The graph is read once, but the timestamps are read again as the build proceeds, and an edit that lands between the two produces a build that is internally inconsistent, part old, part new. This is not a defect in the comparison but in the assumption that the tree is quiescent, and it is analysed in Incremental Correctness Under Source Mutation.