329 lines
12 KiB
Markdown
329 lines
12 KiB
Markdown
# 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:
|
||
|
||
```cpp
|
||
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
|
||
|
||
```json
|
||
{
|
||
"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:
|
||
```cpp
|
||
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.
|