Code coverage instrumentation

Deep dive

How it works

In: a function's CFG (N blocks, E edges), optionally with edge weights · Out: E-N+1 counter sites plus a counter-to-source mapping · State: one counter array per binary (1 or 8 bytes per counter), dumped at exit · Cost: E-N+1 increments per run; planning O(E log E)

1. Choose granularity: function, basic block, edge, or source region/line. Edge coverage is finer than block coverage: it sees which of several predecessors led into a block.
2. Split critical edges (multi-successor to multi-predecessor) so an edge has somewhere to hold its counter.
3. Pick counters: add a virtual edge exit -> entry, then grow a spanning tree over the undirected graph, hottest edges first. Tree edges get no counter; the E-N+1 chords do. A maximum-weight tree minimizes counter executions (Knuth and Stevenson 1973).
4. Run: each chord does counter[i] += 1 (or sets a flag); counters live in one contiguous data section the runtime dumps at exit or on a signal.
5. Recover: at each block sum(in) = sum(out). A block with exactly one unknown edge determines it; peel until the tree is solved.
6. Report: join counts with a static mapping (block/region -> file, line, column), emitted at compile time.

edges: 0>1 0>2 1>3 2>3 3>3 3>4 4>0 (virtual)
tree (derived): 0>1 0>2 3>4 4>0     chords (counted): 1>3 2>3 3>3

Variants of step 4: the compiler calls a callback (trace-pc-guard, one uint32_t guard per edge), increments an inline 8-bit counter (inline-8bit-counters), or stores true (inline-bool-flag); these are the SanitizerCoverage modes. GCC -fprofile-arcs instruments only edges off a spanning tree (gcc/profile.cc). LLVM source-based coverage stores counters plus a mapping where a region's count may be an expression (add or subtract of counters).

Code

// ---- 1. Minimal edge counters: instrument only the chords of a spanning tree ----

#[derive(Clone, Copy)]
pub struct Edge { pub from: usize, pub to: usize }

fn find(p: &mut [usize], mut x: usize) -> usize {
    while p[x] != x { p[x] = p[p[x]]; x = p[x]; }
    x
}

/// `edges` must include the virtual edge exit -> entry so flow is conserved at
/// every block. Returns `true` for edges that need a counter (the chords).
/// Heavier edges (`weight`, e.g. an estimated frequency) go into the tree first,
/// so the hottest edges stay uncounted.
pub fn pick_counters(n: usize, edges: &[Edge], weight: &[u32]) -> Vec<bool> {
    let mut order: Vec<usize> = (0..edges.len()).collect();
    order.sort_by_key(|&e| std::cmp::Reverse(weight[e]));
    let mut p: Vec<usize> = (0..n).collect();
    let mut counted = vec![true; edges.len()];
    for e in order {
        let (a, b) = (find(&mut p, edges[e].from), find(&mut p, edges[e].to));
        if a != b { p[a] = b; counted[e] = false; } // tree edge: derived, not counted
    }
    counted
}

/// Rebuild every edge count from the chord counters by flow conservation:
/// at each block, sum(in) == sum(out). Peel blocks that have one unknown edge.
pub fn recover(n: usize, edges: &[Edge], counted: &[bool], chord: &[u64]) -> Vec<i64> {
    let mut val: Vec<Option<i64>> = (0..edges.len())
        .map(|e| if counted[e] { Some(chord[e] as i64) } else { None })
        .collect();
    loop {
        let mut progress = false;
        for v in 0..n {
            let (mut unknown, mut net, mut cnt) = (0, 0i64, 0);
            for (e, ed) in edges.iter().enumerate() {
                if ed.to == v   { match val[e] { Some(c) => net += c, None => { unknown = e; cnt += 1 } } }
                if ed.from == v { match val[e] { Some(c) => net -= c, None => { unknown = e; cnt += 1 } } }
            }
            if cnt == 1 {
                // in - out = 0 with one unknown edge: sign depends on its direction at v
                val[unknown] = Some(if edges[unknown].to == v { -net } else { net });
                progress = true;
            }
        }
        if !progress { break; }
    }
    val.into_iter().map(|c| c.expect("tree edge not solvable")).collect()
}

// ---- 2. AFL-style edge-hash map: fixed memory however large the program ----

pub struct EdgeMap { pub map: Box<[u8; 1 << 16]>, prev: u16 }

impl EdgeMap {
    pub fn new() -> Self { EdgeMap { map: Box::new([0; 1 << 16]), prev: 0 } }
    /// Called at every basic block with its random compile-time id.
    #[inline(always)]
    pub fn hit(&mut self, cur: u16) {
        let i = (cur ^ self.prev) as usize;
        self.map[i] = self.map[i].wrapping_add(1); // may wrap to 0, as in AFL
        self.prev = cur >> 1; // keeps A->B distinct from B->A and A->A from B->B
    }
}

/// AFL hit-count buckets: 1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+.
pub fn bucket(c: u8) -> u8 {
    match c { 0 => 0, 1 => 1, 2 => 2, 3 => 4, 4..=7 => 8, 8..=15 => 16, 16..=31 => 32, 32..=127 => 64, _ => 128 }
}

/// True if `run` reaches a (tuple, bucket) that `virgin` has not seen; records it.
pub fn has_new_coverage(virgin: &mut [u8], run: &[u8]) -> bool {
    let mut new = false;
    for (v, &c) in virgin.iter_mut().zip(run) {
        let b = bucket(c);
        if b & !*v != 0 { *v |= b; new = true; }
    }
    new
}

Both halves ran under asserts: recover returns the exact per-edge counts of a simulated walk (with a self-loop) from the 3 chord counters, and the map distinguishes paths 10-20-30 and 10-30-20.

Complexity and constants

• Static: tree is O(E log E) (sort) plus near-linear union-find; production recovery peels leaves in O(E). The code above rescans every block per pass for brevity, O(N*E) per pass.
• Runtime: one load-add-store per instrumented edge. I measured 0.38 ns per EdgeMap::hit and 0.42 ns for a plain 64-bit counter with 4096 ids in an L1/L2-resident table on an Apple-silicon Mac, so this is throughput, not whole-program slowdown; real overhead comes from counter cache misses and code growth.
• Memory: 1 byte per edge for flags/8-bit counters, 8 bytes for 64-bit; AFL's map is 64 KiB. AFL documents collisions of about 0.75% of tuples at 1,000 branch points, 7% at 10,000 and 30% at 50,000.
• Scanning a 64 KiB map for new coverage with a byte loop took 57 us here (includes a 64 KiB clone); word-wise scans that skip zero words are faster.

Efficiency

• Cost: one load-add-store per instrumented edge: measured 0.38 ns per EdgeMap::hit and 0.42 ns per plain 64-bit counter in an L1/L2-resident table on an Apple-silicon Mac (see above). Memory is 1 byte per edge for flags and 8-bit counters, 8 bytes for 64-bit; the AFL map is 64 KiB. Whole-program overhead comes from counter cache misses, code growth and the dump, so the bound is memory traffic.
• Levers:
  • spanning tree — only E-N+1 counters instead of E (Knuth and Stevenson 1973) — any CFG; weight tree edges by estimated frequency so hot loop edges are derived
  • narrowest counter that answers the question — a flag is a store with no read-modify-write (inline-bool-flag); 8-bit suffices for fuzzer buckets — 64-bit only for exact reports
  • allowlist and ignorelist (-fsanitize-coverage-allowlist) — fewer counters, smaller binary, fewer cache lines — vendored and test code
  • per-thread tables instead of atomics — avoids a locked bus operation per hit — exact counts in multi-threaded code
  • fixed 64 KiB map — fits L2 and is scanned in microseconds (AFL technical details); collisions grow from 0.75% at 1,000 branch points to 7% at 10,000 — fuzzers
• Naive → standard → state of the art:
  • counter on every edge, atomic increment · locked bus operation per hit
  • spanning-tree counters, plain increments, one dump at exit · E-N+1 increments of about 0.4 ns (measured above)
  • region counters with counter expressions fixed before optimization, flag or 8-bit counters for fuzzing, per-thread tables · fewest counters; the optimizer cannot delete them

Implementation notes

• Section layout: put counters in one contiguous section so the runtime dumps it with one write or mmaps it; LLVM's %c in LLVM_PROFILE_FILE enables continuous mode, syncing counters to the file so a crash or _exit loses nothing.
• Multi-threaded code: plain increments race and lose counts. Accept it for flags and fuzzers; use per-thread tables or atomics when exact counts matter (atomics cost a locked bus operation per hit).
• AFL's counters can wrap to 0 (no cheap saturating add on x86); the shift prev = cur >> 1 makes A->B differ from B->A and A->A from B->B.
• Bucket 8-bit hit counts (1, 2, 3, 4-7, 8-15, 16-31, 32-127, 128+) so noise inside a bucket is not "new coverage".
• LLVM's counter-to-region mapping is fixed before optimization, so coverage builds can keep -O2; the optimizer cannot delete the counters. Reports then match the source, not the optimized code.
• Cost drivers: counter-section bytes, cache lines touched per hot loop, atomics, and dump syscalls (one write; fsync only if the profile must survive power loss).

Pitfalls

• Forgetting the virtual exit -> entry edge: flow conservation fails and recovery cannot terminate.
• Instrumenting a non-split critical edge: the counter lands on a block shared by other paths and over-counts.
• Counter overflow: 8-bit wraps, reads as "not covered" at exactly 256 hits.
• Fork servers and exec: child counters must be dumped or shared, or the parent sees nothing.
• A line executed is not a line checked; short-circuit conditions need branch (or MC/DC) coverage.
• Profile and mapping must come from the same build, or the report is nonsense.

Variants and alternatives

In production

• Compilers and test tooling: LLVM -fprofile-instr-generate -fcoverage-mapping (docs), including MC/DC in recent Clang; Rust -C instrument-coverage; GCC/gcov; Go go test -cover with -covermode set|count|atomic (blog).
• Fuzzing and security: SanitizerCoverage feeds libFuzzer (docs); AFL++ keeps an edge-hash map.
• Operating systems: Linux KCOV collects kernel coverage for fuzzers (docs).
• Browsers and JS engines: V8 counts function and block coverage natively for Chrome DevTools and Node (blog).
• Databases: SQLite reports 100% branch test coverage in an as-deployed configuration, measured with gcov (testing).
• Managed runtimes: JaCoCo for the JVM, coverage.py.

Implementations

Sources

• Donald E. Knuth, Francis R. Stevenson, Optimal measurement points for program frequency counts, BIT 13, 1973. paper
• Thomas Ball, James R. Larus, Optimally profiling and tracing programs, ACM TOPLAS 16(4), 1994. paper
• Thomas Ball, James R. Larus, Efficient path profiling, MICRO-29, 1996. paper
• LLVM, Source-based Code Coverage. docs and LLVM Code Coverage Mapping Format. docs
• LLVM, SanitizerCoverage. docs
• Michal Zalewski, AFL technical details. docs
• GCC, gcov. docs · profile.cc
• The Rust Reference for rustc, Instrument coverage. docs
• SQLite, How SQLite Is Tested (branch coverage with gcov). docs
• Linux kernel, KCOV: code coverage for fuzzing. docs