fold/docs/internal/perf-audit/cross-tu-cache-persistence.md

CrossTUCache persistence — design

Why

The detect::CrossTUCache (include/fold/detect/cross_tu_cache.hpp) is repopulated from scratch on every scan via a priming pass that walks every TU's AST before detectors run (src/cli/scan_runner.cpp:1112-1129). The priming walk is ~one full extra AST traversal per TU per scan. Measured cost on the curl baseline: 30–60s out of 455s total (~7–13% wall).

For warm runs (same source, same flags), the priming pass produces identical entries every time. Persisting and reloading the cache across scans eliminates this redundant work entirely when nothing has changed, and partial-invalidates per TU when only a subset has.

What's cached

CalleeProperties per function-qualified-name:

struct CalleeProperties {
    std::set<unsigned> derefed_params;
    std::set<unsigned> divisor_params;
    std::set<unsigned> bounds_params;
    std::set<unsigned> arithmetic_params;
    bool returns_null = false;
};

Populated by prime*CrossTUCache(ctx) helpers in each detector (null_deref.cpp:871, div_by_zero.cpp:606, int_overflow.cpp:907, oob_access.cpp:?). Each priming function iterates getTranslationUnitDecl()->decls(), filters via isMainFileDecl, and inserts one entry per FunctionDecl defined in that TU.

Provenance: every entry written during TU-X's priming "belongs to" TU-X (the TU where the definition lives). This matters because invalidating a single TU's cache should drop only that TU's contributed entries from the in-memory singleton.

Persistence design

Cache key (per-TU)

(absolute_tu_path, flags_hash) where:

• absolute_tu_path — canonical path of the TU (avoids ./ vs absolute mismatch)
• flags_hash — sha256 of the compile_db entry's argument list, canonicalized (sort -I/-isystem paths to absorb ordering noise, strip output-affecting flags like -o, -MD, -MF, -MMD, -MT)

Source change is detected via source_mtime_ns (stored in cache file header). Mtime alone misses header-graph changes — see Risks below.

Storage layout

~/.cache/fold/cross_tu/
    <db_hash>/                          # sha256(canonical compile_db path)
        manifest.json                   # format version, last-scan-timestamp
        <tu_hash>.json                  # one file per TU, tu_hash = sha256(absolute_tu_path)

Per-TU files chosen over single shadow file because:

• partial invalidation is just file deletion
• corruption affects one TU at most
• concurrent fold-scans against same db can write disjoint files without locking
• file enumeration cost is O(num-TUs) — already paid by compile_db iteration

File format

{
  "version": 1,
  "tu_path": "/abs/path/to/altsvc.c",
  "source_mtime_ns": 1747938472123456789,
  "flags_hash": "ab12...",
  "entries": [
    {
      "name": "Curl_altsvc_init",
      "derefed_params": [0, 1],
      "divisor_params": [],
      "bounds_params": [],
      "arithmetic_params": [],
      "returns_null": false
    },
    ...
  ]
}

JSON over msgpack because:

• entries are small (few hundred bytes per function on average)
• debuggability matters more than 2x size delta
• already have JSON serialization in the codebase
• atomic write via write tmp → rename is trivial

Scan-time flow

1. Load phase (before priming pass starts): For each TU in compile_db:

   • Compute tu_hash = sha256(absolute_tu_path)
   • Read <cache_dir>/<tu_hash>.json if exists
   • Validate: version matches, flags_hash matches, source mtime has not advanced past stored source_mtime_ns
   • On hit: insert all entries into CrossTUCache::instance(), mark TU as "primed-from-cache"
   • On miss: queue TU for fresh priming

2. Prime phase (existing pass, narrowed): Only walk TUs that missed cache. Each walked TU writes:

   • Its entries to CrossTUCache::instance() (existing behavior)
   • A new <cache_dir>/<tu_hash>.json snapshot

3. No change to detector phase — detectors still read from CrossTUCache::instance().

Invalidation

Per-TU invalidation triggers:

• File mtime > stored mtime
• Flags hash mismatch
• Schema version mismatch
• Manual: fold scan --no-cross-tu-cache skips load entirely

Whole-cache invalidation triggers:

• fold binary version change (stored in manifest, compared at load)
• compile_db path change (different db_hash → fresh directory)

CLI surface

• --no-cross-tu-cache — bypass load + save (force fresh prime). Default: cache enabled when scan target is on local filesystem.
• --cross-tu-cache-dir <path> — override default ~/.cache/fold/cross_tu/. For sandboxed/CI environments.
• --profile JSON gains cross_tu_cache_hit_ratio and cross_tu_cache_load_ms so regressions are visible.

Risks

Header-graph mtime gap

A change to a header included by TU-X advances the header's mtime but not TU-X's source mtime. The cache would falsely-hit. Three options:

• v1 (proposed): ignore — same risk model as make without proper dep tracking. Document the caveat. User can --no-cross-tu-cache after large header refactors.
• v2: during priming, snapshot the include-set returned by the SourceManager; store with cache file; on load, stat every included header and invalidate if any is newer. Cost: O(num-includes) stat calls per TU at load. ~50-200 includes per curl TU = noise.
• v3: use clang's own -MD-style depfile output. More precise but requires actually generating the depfile during priming, which we don't currently do.

Recommendation: ship v1, instrument cache miss ratio in --profile, decide v2/v3 based on whether silent staleness becomes a measured problem.

Concurrent writers

Two fold scan instances against the same project would race on <tu_hash>.json writes. Mitigation: atomic write-tmp-then-rename (POSIX rename is atomic). Last-writer-wins is fine here since the content is deterministic for a given (source, flags) tuple.

Schema evolution

version: 1 in every file. Bump on schema change. Old version → cache miss → re-prime → re-save with new version. No special migration path needed.

Disk usage

Estimate: curl has ~150 functions × ~200 bytes/entry × 49 TUs ≈ 1.5 MB per project. Negligible. Add a manifest-tracked last-access timestamp and a lazy "delete entries older than 30 days" sweep on load to prevent unbounded growth across many projects.

Implementation phases

Each landing as an independently revertable commit.

Phase 1 — serializer + tests (no wiring)

• New file: src/detect/cross_tu_cache_io.cpp / include/fold/detect/cross_tu_cache_io.hpp
• API:

  struct CrossTUCacheEntry {
      std::string name;
      CalleeProperties props;
  };
  struct CrossTUCacheSnapshot {
      std::string tu_path;
      std::int64_t source_mtime_ns;
      std::string flags_hash;
      std::vector<CrossTUCacheEntry> entries;
  };
  
  bool saveSnapshot(const std::filesystem::path& cache_file,
                    const CrossTUCacheSnapshot& snap);
  std::optional<CrossTUCacheSnapshot>
  loadSnapshot(const std::filesystem::path& cache_file);
  std::string canonicalizeFlagsHash(
      const std::vector<std::string>& argv);
  

• New test: tests/unit/test_cross_tu_cache_io.cpp — round-trip, schema-version mismatch handling, malformed JSON tolerance.

Phase 2 — provenance tracking in CrossTUCache

• Extend CrossTUCache with insertFromTU(tu_path, name, props). Existing insert(name, props) continues to work but doesn't track provenance (used by the singleton-only test paths).
• Internal map: tu_path → vector<entry> alongside the existing flat qualified_name → props lookup table.
• API: entriesForTU(tu_path) -> vector<CrossTUCacheEntry>.
• New test: round-trip a multi-TU prime and assert each TU's entries come back intact.

Phase 3 — wiring into scan_runner

• New helper in scan_runner: loadCrossTUCacheFromDisk(compile_db, cache_dir) — runs at scan start, before the priming consumer. Returns the set of TUs that hit cache (to skip in the priming loop).
• Modify the priming consumer at scan_runner.cpp:1112-1129 to skip TUs in the hit-set, and to write a snapshot for each TU it does walk.
• Add --no-cross-tu-cache and --cross-tu-cache-dir CLI flags.
• Profile fields: cross_tu_cache_hit_count, cross_tu_cache_miss_count, cross_tu_cache_load_ms, cross_tu_cache_save_ms.
• New integration test: tests/integration/test_cross_tu_cache_warm.cpp — run scan, run again, assert second run reports >0 cache hits and finding-count parity.

Phase 4 — measurement + tune

• Capture bench/perf_audit_run.py runs:
  • Cold: cache empty → expected: same as today's baseline
  • Warm: cache full, no source changes → expected: 30-60s savings
  • Partial: touch 1 source file → expected: only that TU re-primes
• Update docs/internal/perf-audit.md with measured numbers.

Measured outcome

Two implementations landed: v1 saves snapshots but still parses cached TUs (so call_graph stays populated); v2 persists the call_graph alongside the property cache so cached TUs skip ClangTool entirely.

Metric	v1 Cold	v1 Warm	v2 Cold	v2 Warm
Cache hits	0	296	0	348 (100%)
Cache misses	348	52	348	0
Findings	7182	7123	7112	7112 (exact parity)
Wall	6:32	6:31	6:29	6:21
Wall savings	—	1s	—	8s

v2 reaches 100% hit rate, exact finding-count parity (the call_graph replay is semantically equivalent to a live walk), and ~2% wall savings on this workload. The wall win is well below the audit's original "30–60s priming" estimate; v1's logs put curl priming at ~9s total, and v2 saves essentially all of it. The remaining ~380s of total scan wall is detector-side symbolic execution, which the cache does not touch.

The cache should be read as a correctness invariant for incremental scans + a small wall win + infrastructure that will compound with future per-scan caching (e.g. --incremental + --processes>1), not as a primary performance lever.

Out of scope for this design

• Header-graph invalidation (v2 above) — defer until measured silent-staleness incidents.
• Cross-machine cache sharing — paths are absolute by design; not portable.
• Cross-fold-version compatibility — invalidate on version mismatch; no migration.
• Encrypted / signed cache — not a security boundary; cache contains only callee-property metadata derived from already- readable source.

Verification

After all four phases land:

• meson test -C build/release — 45+N green where N = new tests
• bench/perf_audit_run.py median total_wall_ms drops by 30–60s on warm runs of curl baseline (cite delta in docs/internal/perf-audit.md)
• Cache-hit ratio reported by --profile is ≥95% on a warm second run with no source changes
• Touching one source file and re-running shows that TU's hash is the only miss in the next scan

Open questions for review

1. Cache directory default — ~/.cache/fold/ (XDG) or <compile_db_dir>/.fold-cache/ (sibling to build dir)? XDG is friendlier for multi-project users but invisible from find/git status; sibling is discoverable but pollutes build trees. Lean XDG.
2. Manifest as separate file vs per-TU header — kept as separate manifest.json here so per-TU files don't need a round-trip lock when only the manifest's last-scan-timestamp updates.
3. What to do on partial read failure — one corrupt <tu_hash>.json shouldn't poison the whole load. Proposed: log + treat as miss + re-prime that TU + overwrite the file.

If any of those want a different choice, raise before Phase 1 starts so the serializer doesn't get rebuilt later.