plugins/native/znippy-plugin-git/src/resolve.rs
//! Pack entries → **oids**, which is the one thing [`crate::pack_walk`] cannot
//! tell you and the `objects` table is keyed by.
//!
//! This is the **indexer's** work, not the ack path's (§13.9: "the index is built
//! after the ack, over a channel"). It inflates every entry, applies every delta
//! chain and hashes the result, which is what `git index-pack` does and what
//! makes it the expensive half of a push. Nothing here is called before a client
//! is told its push landed.
//!
//! # What it keeps and what it throws away
//!
//! Peak memory is deliberately not "the whole history inflated". **An object is
//! held only while an unresolved entry still has to read it**, and for nothing
//! else:
//!
//! | object | held | until |
//! |---|---|---|
//! | a delta base | yes | its **last** dependent has consumed it |
//! | everything else — blob, commit, tree, tag | **no** | it leaves through the [`PayloadSink`] and is dropped |
//!
//! The base set and, more to the point, **how many entries read each base** are
//! known before a byte is inflated: the walk already collected every delta base,
//! so the resolver starts with an exact reference count per base and drops a
//! payload the moment that count reaches zero. The last dependent gets the base
//! **moved** into it rather than cloned, so a linear delta chain — one base, one
//! dependent, the ordinary shape of real history — copies no payload at all.
//!
//! ## What this table said before 2026-08-11, and what it cost
//!
//! It said commits, trees and tags were kept "because the `graph` and `reach`
//! tables are built from them". They are not, and had not been since §14's
//! exploded table became the fold's input — `absorb_one` reads
//! `Resolved::index_entry()` and nothing else. Two copies of the object set were
//! being held for a reader that no longer existed:
//!
//! * `content` kept every base **and** every typed object for the whole call.
//! Nothing ever removed a row, so "held only while something still needs them"
//! described an intention, not the code.
//! * `Resolved::payload` kept a second copy of the same bytes, cloned in.
//!
//! MEASURED on oden 2026-08-11, `tests/resolve_peak_memory.rs`, peak **live**
//! heap over `resolve_walked` against the pack's own inflated payload:
//!
//! | pack | before | after |
//! |---|---:|---:|
//! | forge-year-8a-240b-12c, 28 893 objects, 111.0 MB | 2.03x | **0.03x** |
//! | stage-red-nobitmap, 12 328 objects, 343.5 MB | 1.34x (461.2 MB) | **0.02x** (5.9 MB) |
//! | facett, 7 232 objects, 72.8 MB | 1.20x | **0.42x** |
//! | znippy's own, 5 388 objects, 84.4 MB | 0.75x | **0.14x** |
//!
//! The worst pack in the corpus went 2.03x → 0.42x. It is `facett`, whose
//! delta chains fan out widely enough that a real base working set is genuinely
//! live at once — which is the bound behaving as intended rather than a residue.
//!
//! End to end, one `gunnar-server`, one `push --mirror`, anonymous RSS held
//! afterwards (not peak — this memory was never given back):
//!
//! | fixture | before | after |
//! |---|---:|---:|
//! | 36 172 objects, 290 MB inflated, 5.9 MB pack | 575.7 MB | **185.1 MB** |
//! | 352 396 objects, 2.89 GB inflated, 61.8 MB pack | 4480.1 MB | **439.9 MB** |
//!
//! The second row is the one that mattered: 10x the repository cost 10x the
//! memory before and 2.4x after, so the resolver's footprint stopped tracking
//! the history. What is left is bounded and named — redb's page cache
//! (`ZNIPPY_GIT_REDB_CACHE_BYTES`, 64 MiB by default, measured at 129.3 MB held
//! with an 8 MiB ceiling and 303.9 MB with 256 MiB), the exploded table's
//! [`FLUSH_BYTES`](crate::exploded::FLUSH_BYTES) write buffer, and
//! `Derived`'s in-memory graph, which is genuinely O(repository).
//!
//! # ⚠ The clone that got slower, and why it is not this code
//!
//! **Read this before "fixing" the reference counting.** `vs_forge_clone` on the
//! 352 396-object fixture reported this change as a **+78 % CPU regression on
//! every znippy arm**, and the natural reading — a base dropped at its "last
//! use" has to be re-resolved when something later wants it again — is wrong. It
//! is not even mechanically possible: an undercount cannot cause a re-resolve
//! here, because there is no re-resolve to fall into. `resolve_walked` fails the
//! whole pack by name.
//!
//! What it actually is, MEASURED on oden 2026-08-11, one gunnar-server, seed the
//! fixture then clone it, steady state (clones 2-3), quiet box, only the
//! allocator and this file varying:
//!
//! | resolver | allocator | clone CPU | anon after seed |
//! |---|---|---:|---:|
//! | before | glibc | 1.47 s | 4481 MB |
//! | **after** | glibc | **2.62 s** | **438 MB** |
//! | before | mimalloc | 1.18 s | 1767 MB |
//! | **after** | **mimalloc** | **1.17 s** | **701 MB** |
//!
//! With a competent allocator the two resolvers are **identical** (1.18 against
//! 1.17). The regression is entirely glibc `malloc`: the old resolver's retained
//! 4.5 GB was accidentally acting as a **pre-warmed pool**, so the clone's own
//! ~2 GB of allocations came off a free list instead of out of the kernel. Take
//! the leak away and glibc charges for the memory it should have been charging
//! for all along.
//!
//! Three independent measurements say the same thing, and none of them involve
//! this file being slower:
//!
//! 1. **Bisect.** A build with *only* `Resolved::payload` removed — the
//! reference counting NOT applied, `content` still never pruned — reproduces
//! the whole regression (2.56–2.62 s). Adding the reference counting on top
//! then costs **nothing** (2.55–2.65 s) and takes anon-after-seed from
//! 2350 MB to 438 MB. The counting is free; the *not leaking* is what glibc
//! punishes.
//! 2. **Restart.** Restart the server after seeding, so the derived tables are
//! folded onto a fresh heap: before 2.20–2.22 s, after 2.20–2.24 s —
//! identical to within 1 %. The old resolver's 1.47 s is the outlier, not the
//! new one's 2.62 s.
//! 3. **The resolver itself.** Over the same 6 real packs both revisions accept,
//! 1.058 s before against 0.975 s after: this code is ~8 % *faster*.
//!
//! So there is no cheaper trade to find inside this module, and an LRU over
//! bases would buy nothing. The lever, if the CPU is wanted back, is the
//! allocator — and `LD_PRELOAD=libmimalloc.so.3` is enough to get it with no
//! code change at all.
//!
//! # Where the payloads it throws away now go
//!
//! §14's exploded table is **eager** (decided 2026-08-08), so every object this
//! module resolves has to reach [`crate::exploded::ExplodedTable`] — including
//! the blobs the table above says are dropped. They still are: the payload
//! leaves through a [`PayloadSink`] as it is produced, rather than being
//! accumulated into the returned `Vec`. That is the difference between a peak
//! footprint of "the bases plus the typed objects" and one of "the whole pack
//! inflated at once", and eager resolution does not get to change it.
//!
//! A **thin** pack's `REF_DELTA` base is an object the client knows the server
//! already has, and it is usually a blob. Resolving it needs that blob's
//! *content*, which is exactly what the exploded table now holds — so the
//! [`BaseSource`] can answer from it in one point lookup instead of re-resolving
//! a whole pack. A thin pack whose external base is **still** not re-derivable
//! is refused by name ([`ResolveError::MissingBase`]) rather than resolved by
//! guesswork, unchanged.
//!
//! # The bounded base set (2026-08-30)
//!
//! The table above says a base is held until its last dependent. On
//! torvalds/linux that set is **unbounded in principle** — 11.2 M deltas over
//! 13.9 M objects, and nothing in the pack format promises a base's last
//! dependent is near it. On the 16 GB appliance the indexer grew past the box
//! and the kernel panicked (see [`crate::memguard`]). So the set now has a
//! **byte ceiling** ([`ResolveLimits::base_budget`], default 25 % of
//! `MemTotal`, `ZNIPPY_GIT_BASE_BUDGET_BYTES`):
//!
//! | event | what happens |
//! |---|---|
//! | a base would push the held bytes over the ceiling | the held base whose **next dependent is farthest** in the pack is dropped (Belady — the walk already lists every dependent's position, so "next use" is known, not guessed) |
//! | the new base itself is the farthest | it is not held at all |
//! | a dependent asks for a dropped base | it is **re-inflated from the mmapped pack** — its own chain re-applied — and counted in [`ResolveReport::reinflations`] |
//! | the watchdog says the box is short | **every** held base is dropped, the sink and the row batch are flushed, and the worker waits |
//!
//! Same output, hard ceiling. The ceiling is `max(budget, largest single
//! base)`: one object bigger than the budget is held while it is needed,
//! because the alternative is re-inflating it once per dependent.
//!
//! # What is preallocated
//!
//! Two scratch buffers live across the whole pass: the delta instruction
//! stream and the payload of an object nothing deltas against. An object that
//! is a base gets its own `Vec` because it outlives the iteration; every other
//! object — the overwhelming majority — is inflated into the reused buffer,
//! hashed in place ([`GitHashKind::oid_of_object`], no canonical copy) and
//! handed to the sink from there. Per object the hot path allocates the
//! 20-byte oid of its row and nothing else.
use std::collections::HashMap;
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
use anyhow::{Result, anyhow, bail};
use crate::exploded::{NoSink, PayloadSink};
use crate::forest::{DeltaForest, EntrySet};
use crate::index_layout::{IndexEntry, ObjType};
use crate::memguard::MemWatchdog;
use crate::object::{GitHashKind, GitObjectKind};
use crate::pack_walk::{DeltaBase, PackEntry, PackWalk, walk};
use crate::progress::{IndexProgress, Phase};
/// Where an entry that deltas against something outside the pack gets its base.
///
/// Implemented by the store, which may or may not be able to answer — see the
/// module docs on §14.
pub trait BaseSource: Sync {
/// The object's type and inflated payload.
///
/// `Ok(None)` means **this source does not hold that object** — the only
/// answer [`ResolveError::missing_base`] may be built from. `Err` means the
/// source *does* hold it and could not read it, and that is a different
/// fact with a different owner.
///
/// # 🔴 It returned a bare `Option`, and the difference was thrown away
///
/// `impl BaseSource for Absorber` ended in `.ok().flatten()`: a store that
/// failed to reconstruct a base it holds answered exactly like a store that
/// never had it, and the resolver then refused the *pushed pack* with *"this
/// repository genuinely does not have that object"*. MEASURED on oden
/// 2026-08-30 (lane AI): 21 of 140 ordinary pushes refused with that
/// sentence about an object sitting in an absorbed pack one lookup away —
/// see [`MAX_DELTA_LINKS`] for what was actually wrong and
/// `crate::thin_storm` for the red. A client cannot act on a diagnosis that
/// names the wrong party; neither can an operator.
fn content(&self, oid: &[u8]) -> Result<Option<(GitObjectKind, Vec<u8>)>>;
}
/// A source that has nothing. The right one for a self-contained pack, and it
/// makes "this pack was thin" an error rather than a silent success.
pub struct NoBases;
impl BaseSource for NoBases {
fn content(&self, _oid: &[u8]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
Ok(None)
}
}
/// One resolved object: **exactly what the `objects` table stores**, and no
/// payload.
///
/// It carried an `Option<Vec<u8>>` payload until 2026-08-11, for a reader that
/// stopped existing when §14's exploded table became the fold's input. Every
/// production caller uses [`index_entry`](Self::index_entry) and nothing else —
/// `absorb_one` builds index rows, and the one other caller discards the vector
/// entirely and reads its sink. Content has one home now
/// ([`PayloadSink`], LAW 5) and this struct is the row, so a 343 MB pack's rows
/// cost the length of the pack's entry list rather than the length of its
/// history.
#[derive(Debug, Clone)]
pub struct Resolved {
pub oid: Vec<u8>,
/// Byte extent of the **stored, verbatim** entry.
pub offset: u64,
pub len: u64,
/// The type the entry carries in the pack — which for a delta is
/// `OfsDelta` / `RefDelta`, exactly as `.idx` cannot tell you and this index
/// exists to record.
pub stored_type: ObjType,
/// The type the chain resolves to. Always one of the four real git types.
pub kind: GitObjectKind,
/// Inflated, **post-delta-resolution** size — the fact `.idx` and `.rev`
/// together still cannot answer.
pub uncompressed_size: u64,
/// The `objects.delta_base` column: an archive **offset**, `0` for none.
pub delta_base: u64,
}
impl Resolved {
/// The row [`crate::read_stack::ObjectReadStack::append`] takes.
///
/// `delta_base` now has a column of its own in [`IndexEntry`] and rides
/// across in it — it was carried on this struct alone until that column
/// existed, and was deliberately never smuggled into `uncompressed_size` or
/// any other field on the way. **This is the only place it is written into
/// an index row** (LAW 5): [`resolve_walked`] computes it once, in the
/// archive's coordinate space, and nothing downstream recomputes it from the
/// walk.
pub fn index_entry(&self) -> IndexEntry {
IndexEntry {
oid: self.oid.clone(),
offset: self.offset,
len: self.len,
obj_type: self.stored_type,
uncompressed_size: self.uncompressed_size,
delta_base: self.delta_base,
}
}
}
/// The one failure that is a *decision* rather than a corrupt pack.
#[derive(Debug)]
pub struct ResolveError;
impl ResolveError {
/// A thin pack's external base, named.
pub fn missing_base(oid: &[u8]) -> anyhow::Error {
anyhow!(
"this pack is thin: it deltas against {} which is not in it, and no base source could \
produce that object's content — §14's exploded table does not hold it and it could \
not be re-derived from the verbatim packs either, so this repository genuinely does \
not have that object. The pack is refused by name rather than half-resolved",
hex::encode(oid)
)
}
/// The worker was told to stop (the repository is being deleted).
pub fn cancelled() -> anyhow::Error {
anyhow!("index work cancelled: the repository is being deleted")
}
/// **This box cannot index this pack**, said out loud instead of waited out.
///
/// The memory watchdog paused, dropped everything droppable, and still could
/// not get back over its floor — either for
/// [`MemWatchdog::pause_deadline`](crate::memguard::MemWatchdog::pause_deadline)
/// or because the flush freed nothing three times running. Lane P2's rig
/// took the other branch, which was to wait forever: 1 pause, 0 resumes,
/// 1h45m41s, and a client that never got an ack. A refusal by name is a
/// worse outcome for this one push and a far better one for the operator,
/// who can now read the row and give the box more memory.
pub fn out_of_memory(reason: &str, available: u64, budget: u64, done: u64, total: u64) -> anyhow::Error {
anyhow!(
"this box cannot index this pack: the memory watchdog gave up ({reason}) with {} \
available against a {} floor, after {done} of {total} objects. Everything droppable \
was dropped and the floor was still breached — what holds the memory is the \
resolver's own per-object state, which is proportional to the pack. Give the box \
more RAM, lower ZNIPPY_GIT_MEM_BUDGET_PCT, or push a smaller pack. The pack's bytes \
are durable and untouched; nothing partial was indexed.",
crate::memguard::fmt_bytes(available),
crate::memguard::fmt_bytes(budget)
)
}
}
/// Default share of `MemTotal` the held base set may take.
pub const DEFAULT_BASE_BUDGET_PCT: u64 = 25;
/// Default rows per batch handed to the row sink.
pub const DEFAULT_ROW_BATCH: usize = 262_144;
/// **Ceiling on how far the workers may run ahead of the ordered stream**, in
/// bytes of rows and of the payloads the sink asked to be given. Past it a
/// worker waits for the emitter instead of buffering the pack — see
/// [`ResolveLimits::lookahead_bytes`].
pub const DEFAULT_LOOKAHEAD_BYTES: u64 = 32 << 20;
/// A ceiling on the worker count no environment variable may cross. A pack is
/// resolved by the box, not by a number somebody typed.
pub const MAX_WORKERS: usize = 256;
/// The knobs and hooks the indexer hands the resolver. [`ResolveLimits::none`]
/// is the old behaviour: unbounded bases, no watchdog, no progress.
#[derive(Clone)]
pub struct ResolveLimits<'a> {
/// Ceiling on held delta-base bytes; `0` = unbounded.
pub base_budget: u64,
/// Rows per batch to the row sink.
pub row_batch: usize,
/// **How many subtrees are walked at once.** `1` is the serial resolver and
/// the reference every other value is compared against; the output is the
/// same stream at any value (see `the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers`).
pub workers: usize,
/// Bytes of resolved-but-not-yet-emitted objects the workers may hold. `0`
/// takes [`DEFAULT_LOOKAHEAD_BYTES`].
pub lookahead_bytes: u64,
/// Objects between two checkpoints (cancel flag, watchdog).
pub check_every: u64,
pub watchdog: Option<Arc<MemWatchdog>>,
pub cancel: Option<&'a AtomicBool>,
pub progress: Option<&'a IndexProgress>,
/// Names the repository in log lines.
pub label: &'a str,
/// Called once per watchdog pause and again every re-flush: the owner drops
/// whatever it holds that can be rebuilt (the store's caches) and returns
/// **how much it dropped**. Zero means the owner had nothing to give, which
/// is the fact `index.spilled` reported 627 times and nobody acted on —
/// see [`crate::memguard::PauseEnd::NothingToGive`].
pub on_pause: Option<&'a (dyn Fn() -> u64 + Sync)>,
}
impl<'a> ResolveLimits<'a> {
/// Unbounded, unwatched, unreported — what a test or a one-off resolve uses.
pub fn none() -> Self {
Self {
base_budget: 0,
row_batch: DEFAULT_ROW_BATCH,
workers: 1,
lookahead_bytes: DEFAULT_LOOKAHEAD_BYTES,
check_every: crate::memguard::CHECK_EVERY_OBJECTS,
watchdog: None,
cancel: None,
progress: None,
label: "",
on_pause: None,
}
}
/// The indexer's: budget and batch from the environment (once per
/// process), the process-wide watchdog, this store's cancel flag and
/// progress counter.
pub fn for_indexer(
label: &'a str,
cancel: &'a AtomicBool,
progress: &'a IndexProgress,
watchdog: Arc<MemWatchdog>,
on_pause: &'a (dyn Fn() -> u64 + Sync),
) -> Self {
Self {
base_budget: base_budget_from_env(),
row_batch: row_batch_from_env(),
workers: workers_from_env(),
lookahead_bytes: lookahead_from_env(),
check_every: crate::memguard::CHECK_EVERY_OBJECTS,
watchdog: Some(watchdog),
cancel: Some(cancel),
progress: Some(progress),
label,
on_pause: Some(on_pause),
}
}
}
/// `ZNIPPY_GIT_BASE_BUDGET_BYTES`, else 25 % of `MemTotal`, else 1 GiB when
/// the box cannot be measured. Read once per process.
pub fn base_budget_from_env() -> u64 {
use std::sync::OnceLock;
static B: OnceLock<u64> = OnceLock::new();
*B.get_or_init(|| {
if let Some(b) = crate::arms::read_env(crate::arms::ENV_BASE_BUDGET_BYTES)
.and_then(|v| v.parse::<u64>().ok())
{
return b;
}
let total = crate::memguard::mem_total();
if total == 0 { 1 << 30 } else { total / 100 * DEFAULT_BASE_BUDGET_PCT }
})
}
/// `ZNIPPY_GIT_INDEX_BATCH_ROWS`, else [`DEFAULT_ROW_BATCH`]. Read once per process.
pub fn row_batch_from_env() -> usize {
use std::sync::OnceLock;
static B: OnceLock<usize> = OnceLock::new();
*B.get_or_init(|| {
crate::arms::read_env(crate::arms::ENV_INDEX_BATCH_ROWS)
.and_then(|v| v.parse::<usize>().ok())
.filter(|n| *n > 0)
.unwrap_or(DEFAULT_ROW_BATCH)
})
}
/// `ZNIPPY_GIT_RESOLVE_WORKERS`, else one per core. Read once per process.
///
/// **The forest is the parallelism** ([`crate::forest`]): a base and its
/// dependents are a tree, and two trees share nothing, so N workers is N
/// independent depth-first walks over one mmapped pack. It is not N copies of
/// the pack's O(pack) structures — the walk, the forest and the oid table are
/// read-only and shared — and it is not N base budgets either: the held-base
/// ceiling is one atomic across all of them (LAW 5).
pub fn workers_from_env() -> usize {
use std::sync::OnceLock;
// The ENVIRONMENT is read once (the read-once law); the embedder's default is
// live, because a box learns it is a twin AFTER this process started.
static W: OnceLock<Option<usize>> = OnceLock::new();
let from_env = *W.get_or_init(|| {
crate::arms::read_env(crate::arms::ENV_RESOLVE_WORKERS)
.and_then(|v| v.parse::<usize>().ok())
.filter(|n| *n > 0)
});
from_env
.unwrap_or_else(|| match RESOLVE_WORKERS_DEFAULT.load(Ordering::Relaxed) {
0 => std::thread::available_parallelism().map(|x| x.get()).unwrap_or(1),
n => n,
})
.clamp(1, MAX_WORKERS)
}
/// What [`workers_from_env`] answers when [`crate::arms::ENV_RESOLVE_WORKERS`] is unset.
/// `0` is "one per core" — the shipped default — and not a worker count, because
/// [`workers_from_env`] clamps to at least one and a zero-wide resolver is no resolver.
static RESOLVE_WORKERS_DEFAULT: AtomicUsize = AtomicUsize::new(0);
/// **Set the process-wide default resolver width** for every resolve started AFTER this call
/// (an explicit [`crate::arms::ENV_RESOLVE_WORKERS`] still wins). `0` restores one per core.
/// The twin of [`crate::arms::set_graph_cache_default`], for an embedder that learns its role
/// at runtime and cannot set the environment — edition 2024 makes `set_var` unsafe, and gunnar
/// forbids `unsafe`. MEASURED (gunnar `twin_snapshot_memory.rs`, 2026-09-15): one worker per
/// core, each inflating a whole blob, is +133 MiB of RssAnon for a 512 MiB snapshot install on
/// a many-core box; two workers with a 16 MiB lookahead is +36 MiB, under gunnar's 64 MiB
/// twin ceiling.
pub fn set_resolve_workers_default(workers: usize) {
RESOLVE_WORKERS_DEFAULT.store(workers, Ordering::Relaxed);
}
/// `ZNIPPY_GIT_RESOLVE_LOOKAHEAD_BYTES`, else [`DEFAULT_LOOKAHEAD_BYTES`].
/// Read once per process.
pub fn lookahead_from_env() -> u64 {
use std::sync::OnceLock;
// Read-once environment, live embedder default — see [`workers_from_env`].
static L: OnceLock<Option<u64>> = OnceLock::new();
let from_env = *L.get_or_init(|| {
crate::arms::read_env(crate::arms::ENV_RESOLVE_LOOKAHEAD_BYTES)
.and_then(|v| v.parse::<u64>().ok())
.filter(|n| *n > 0)
});
from_env.unwrap_or_else(|| match RESOLVE_LOOKAHEAD_DEFAULT.load(Ordering::Relaxed) {
0 => DEFAULT_LOOKAHEAD_BYTES,
n => n,
})
}
/// What [`lookahead_from_env`] answers when [`crate::arms::ENV_RESOLVE_LOOKAHEAD_BYTES`] is
/// unset. `0` is [`DEFAULT_LOOKAHEAD_BYTES`] and not "no lookahead", which is the same
/// reading the environment door gives a `0` there.
static RESOLVE_LOOKAHEAD_DEFAULT: AtomicU64 = AtomicU64::new(0);
/// **Set the process-wide default resolver lookahead**, in bytes, for every resolve started
/// AFTER this call (an explicit [`crate::arms::ENV_RESOLVE_LOOKAHEAD_BYTES`] still wins).
/// `0` restores [`DEFAULT_LOOKAHEAD_BYTES`]. The twin of
/// [`crate::arms::set_graph_cache_default`] — see [`set_resolve_workers_default`] for the
/// measurement the pair is for.
pub fn set_resolve_lookahead_default(bytes: u64) {
RESOLVE_LOOKAHEAD_DEFAULT.store(bytes, Ordering::Relaxed);
}
/// What one resolve did — the audit line's numbers, all applied output.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct ResolveReport {
pub rows: u64,
/// Bases dropped for the ceiling and inflated again for a later dependent.
pub reinflations: u64,
/// Bases dropped for the ceiling (each may cost 0..n re-inflations).
pub evictions: u64,
/// Bases dropped because the watchdog said the box was short.
pub watchdog_drops: u64,
/// Most bytes of bases held at once.
pub peak_base_bytes: u64,
/// Watchdog pauses inside this pass.
pub pauses: u64,
pub paused_ms: u64,
/// Row batches handed to the sink.
pub batches: u64,
/// Times a worker waited for the ordered stream instead of running further
/// ahead of it. A positive number is the lookahead ceiling doing its job;
/// a large one beside a poor speed-up is the ceiling being the bottleneck.
pub stalls: u64,
/// How many subtrees were walked at once. `1` is the serial resolver.
pub workers: u32,
/// Times a worker gave its core back because the box was short of memory
/// rather than pausing the whole pack. See `Round::checkpoint`.
pub shed: u64,
/// The watchdog gave up rather than resumed — the pass is being failed by
/// name. See [`ResolveError::out_of_memory`].
pub gave_up: bool,
}
impl ResolveReport {
/// Fold one round's numbers into the pack's. Sums, and the two extremes
/// taken as extremes — a merge that does not depend on which worker
/// produced what, so the audit line is the same at any worker count.
pub fn absorb(&mut self, r: ResolveReport) {
self.rows += r.rows;
self.reinflations += r.reinflations;
self.evictions += r.evictions;
self.watchdog_drops += r.watchdog_drops;
self.peak_base_bytes = self.peak_base_bytes.max(r.peak_base_bytes);
self.pauses += r.pauses;
self.paused_ms += r.paused_ms;
self.batches += r.batches;
self.stalls += r.stalls;
self.shed += r.shed;
self.workers = self.workers.max(r.workers);
self.gave_up |= r.gave_up;
}
}
/// Resolve every entry of `pack` to an oid, **keeping no payloads**.
///
/// `archive_offset` is where the pack's first byte lives in the archive, so the
/// offsets and `delta_base`s that come back are already in the archive's
/// coordinate space and no caller has to remember to shift them.
///
/// The indexer does **not** come through here — it calls
/// [`resolve_streaming`] with the exploded table as its sink, which is what
/// makes §14's side table fall out of the same pass rather than out of a second
/// walk.
pub fn resolve(
pack: &[u8],
hash: GitHashKind,
archive_offset: u64,
bases: &dyn BaseSource,
) -> Result<Vec<Resolved>> {
let w = walk(pack, hash.oid_len())?;
resolve_walked(pack, &w, hash, archive_offset, bases, &NoSink)
}
/// Same, for a caller that already walked the pack (`put` does, for the closure
/// check) and must not walk it twice — and for the one that wants the payloads.
///
/// `sink` is handed **every** object exactly once, in resolution order, with the
/// payload its chain resolves to. Pass [`NoSink`] to keep nothing. This is the
/// one pass §14's exploded table is built from: no second walk, no second
/// inflate, no second resolver (LAW 5).
///
/// Rows come back in **entry order**. Unbounded bases (the old behaviour): a
/// caller that wants the ceiling, the watchdog and streaming rows is the
/// indexer, and it uses [`resolve_streaming`].
pub fn resolve_walked(
pack: &[u8],
w: &PackWalk,
hash: GitHashKind,
archive_offset: u64,
bases: &dyn BaseSource,
sink: &dyn PayloadSink,
) -> Result<Vec<Resolved>> {
let mut out: Vec<Resolved> = Vec::with_capacity(w.entries.len());
let limits = ResolveLimits {
row_batch: w.entries.len().max(1),
..ResolveLimits::none()
};
resolve_streaming(pack, w, hash, archive_offset, bases, sink, limits, &mut |rows| {
out.extend(rows.drain(..));
Ok(())
})?;
// Resolution order is entry order except for the ref-deltas a later round
// picked up; offsets are unique and ascending in entry order, so this is
// exactly the order the old `out[i]` array had.
out.sort_unstable_by_key(|r| r.offset);
Ok(out)
}
/// **The resolver**: bounded bases, watchdog checkpoints, rows in batches.
///
/// `rows` is called with each full batch (and the final partial one) and may
/// drain the vector; the same allocation is reused for the next batch. Nothing
/// about the rows or the sink calls depends on the batch size — it is purely
/// how much the caller holds at once.
#[allow(clippy::too_many_arguments)]
pub fn resolve_streaming(
pack: &[u8],
w: &PackWalk,
hash: GitHashKind,
archive_offset: u64,
bases: &dyn BaseSource,
sink: &dyn PayloadSink,
limits: ResolveLimits<'_>,
rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
) -> Result<ResolveReport> {
let mut r = Resolver::new(pack, w, hash, archive_offset, bases, sink, limits)?;
r.run(rows)?;
Ok(r.report)
}
// ════════════════════════════════════════════════════════════════════════════
// THE FOREST DRIVER — one subtree per unit, N workers, ONE ordered stream out
// ════════════════════════════════════════════════════════════════════════════
/// How many objects one worker resolves before it hands them to the ordered
/// emitter: one lock per few thousand objects instead of one per object.
const HANDOVER_ROWS: usize = 4096;
/// …or this many bytes of them, whichever comes first.
const HANDOVER_BYTES: u64 = 1 << 20;
/// **How large a scratch buffer may stay between objects.**
///
/// `delta` and `leaf` are reused for the whole pass, which is what makes the
/// hot path allocate nothing — and a `Vec` never gives capacity back, so one
/// 90 MB blob leaves a 90 MB buffer standing for the remaining thirteen
/// million objects. Single-threaded that was one such buffer; with a worker per
/// core it is `2 x workers` of them, and on a 16 GB appliance that is the
/// difference between finishing a kernel mirror and pausing at 98 %.
const SCRATCH_KEEP_BYTES: usize = 1 << 20;
/// What one small heap block costs beyond the bytes asked for — header plus
/// size-class rounding. Deliberately generous: the lookahead ceiling is a
/// memory bound, and a memory bound that under-counts is not one.
const ALLOC_OVERHEAD: usize = 32;
/// How many objects one pass of the drain takes out of the emit buffer before
/// it lets the writers back in — the lock-hold bound.
const DRAIN_RUN: usize = 8192;
/// One frame of a worker's depth-first path: a resolved base, held **only**
/// while its own subtree is still being walked.
struct Frame {
entry: u32,
kind: GitObjectKind,
/// Empty when `evicted`.
payload: Vec<u8>,
evicted: bool,
next_child: u32,
}
/// One resolved object on its way out: the row always, the payload only when
/// the sink said it would read one ([`PayloadSink::wants`]).
struct Emit {
kind: GitObjectKind,
row: Resolved,
payload: Option<Vec<u8>>,
}
impl Emit {
/// What holding this costs, for the lookahead ceiling. A count of objects
/// cannot tell one commit from one 40 MB blob, so the ceiling is in bytes —
/// and the bytes are the ones the ALLOCATOR charges, not the ones the
/// struct declares. `ALLOC_OVERHEAD` is the rest of what a 20-byte oid
/// costs: the header and the size-class rounding of its own heap block,
/// plus this row's share of the `Vec` it sits in. Undercounting it is how a
/// 128 MiB ceiling holds half a gigabyte.
fn weight(&self) -> u64 {
(std::mem::size_of::<Emit>()
+ ALLOC_OVERHEAD
+ self.row.oid.len()
+ self.payload.as_ref().map_or(0, |p| p.len() + ALLOC_OVERHEAD)) as u64
}
}
/// A worker's own scratch: never shared, never locked, reused across the
/// subtrees one thread walks.
#[derive(Default)]
struct Scratch {
/// Which unit (root) of this round the worker is inside — the key its
/// output is handed over under.
unit: usize,
delta: Vec<u8>,
leaf: Vec<u8>,
stack: Vec<Frame>,
out: Vec<Emit>,
out_bytes: u64,
found_refs: Vec<(Vec<u8>, u64)>,
}
std::thread_local! {
/// Per **thread**, not per subtree: a kernel-sized pack has 2.7 M roots and
/// allocating two grown buffers for each of them is 2.7 M mallocs the walk
/// does not need.
static SCRATCH: std::cell::RefCell<Scratch> = std::cell::RefCell::new(Scratch::default());
}
/// What one root has produced and the drain has not yet handed on, in
/// depth-first order, and whether the walk of that root is finished.
///
/// **One `Vec`, not a queue of them.** The median subtree in a real pack is
/// ONE object (`examples/forest_stats` on torvalds/linux: p50 1, p90 5), so a
/// `VecDeque<Vec<Emit>>` per root was two heap allocations and a deque header
/// to carry a single 20-byte oid — the per-root bookkeeping cost more than the
/// object it carried, 2.7 M times.
#[derive(Default)]
struct RootOut {
rows: Vec<Emit>,
done: bool,
}
/// The emit buffer, keyed by **root index**.
///
/// # 🔴 It was keyed by ENTRY index, and on a real pack that was a serialiser
///
/// Emitting in entry order is the obvious way to make N workers produce the
/// stream one worker would have: the objects come out sorted by where they sit
/// in the pack, whoever resolved them. It is also unusable, and the pack says
/// why. MEASURED on `torvalds/linux` (`examples/forest_stats`), 13 948 244
/// entries, 2 732 372 roots:
///
/// | | subtree **size** | subtree **index span** |
/// |---|---:|---:|
/// | p50 | 1 | 0 |
/// | p90 | 5 | **5 251 404** |
/// | p99 | 70 | **11 511 634** |
/// | max | 11 789 | **12 434 450** |
///
/// The subtrees are tiny — perfect parallel work — but a five-object subtree
/// routinely **spans five million entries**, because `pack-objects` puts a base
/// near its first dependent and the rest of the dependents wherever they fall.
/// So an entry-ordered cursor is pinned by any subtree in flight whose span
/// reaches the top of the pack: every other worker's output buffers behind it,
/// the lookahead ceiling closes, and the workers wait. MEASURED, the kernel
/// pack at the appliance's 4-core shape: **1 worker 1454.7 s, 2 workers
/// 1572.9 s** — *slower*, at 1.24 cores of CPU, with 286 686 stalls.
///
/// Keyed by root, the cursor moves at the rate roots finish, and roots are
/// claimed in ascending order, so it follows the workers instead of pinning
/// them. The order is still fixed and still worker-count independent: roots
/// ascending, and inside a root the depth-first sequence the children lists
/// (ascending) determine.
#[derive(Default)]
struct Pending {
map: std::collections::BTreeMap<usize, RootOut>,
bytes: u64,
/// **The units a worker is inside right now.** The lookahead ceiling needs
/// it: gatling claims a unit *before* the worker runs, so "wait until the
/// stream catches up" would otherwise be said by the very worker the stream
/// is waiting for. See [`Round::backpressure`].
in_flight: std::collections::BTreeSet<usize>,
/// How many of those units belong to a worker that has **given its core
/// back** for the memory watchdog and is waiting rather than resolving.
/// `in_flight.len() - parked` is therefore how many cores this pack is
/// actually using, which is the number the last worker standing needs
/// before it decides that pausing is the only option left.
parked: usize,
}
/// The ordered end of the pipe. One worker at a time holds it, so the sink and
/// the row callback see exactly the sequence one worker would have made.
/// `cursor` is an index into this round's **roots**.
struct Drain<'r> {
cursor: usize,
batch: Vec<Resolved>,
rows: &'r mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
}
/// A base this round was promised from outside the pack, probed **once** while
/// the round was planned so that which entries the round covers is decided
/// before a byte is inflated.
struct RoundBases<'r, 'w, 'a> {
external: &'r HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
inner: &'a dyn BaseSource,
}
impl BaseSource for RoundBases<'_, '_, '_> {
fn content(&self, oid: &[u8]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
if let Some((k, p)) = self.external.get(oid) {
return Ok(Some((*k, p.clone())));
}
self.inner.content(oid)
}
}
/// **One round of the fixpoint, across N workers.**
///
/// Everything in here is either immutable for the length of the round or an
/// atomic/lock, because a `&Round` is what every worker holds.
struct Round<'p, 'w, 'a, 'r> {
pack: &'p [u8],
w: &'w PackWalk,
forest: &'r DeltaForest,
hash: GitHashKind,
oid_len: usize,
archive_offset: u64,
bases: &'a dyn BaseSource,
sink: &'a dyn PayloadSink,
limits: &'r ResolveLimits<'a>,
/// The oids some `REF_DELTA` in this pack names. Read-only here.
ref_wanted: &'r std::collections::HashSet<&'w [u8]>,
/// Where a named oid turned out to live, from the rounds **before** this one.
oid_to_offset: &'r HashMap<Vec<u8>, u64>,
external: &'r HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
roots: &'r [u32],
in_round: &'r EntrySet,
workers: usize,
lookahead: u64,
pend: std::sync::Mutex<Pending>,
cv: std::sync::Condvar,
drain: std::sync::Mutex<Drain<'r>>,
pause_gate: std::sync::Mutex<()>,
stop: AtomicBool,
err: std::sync::Mutex<Option<(usize, anyhow::Error)>>,
since_check: std::sync::atomic::AtomicU64,
rows: std::sync::atomic::AtomicU64,
reinflations: std::sync::atomic::AtomicU64,
evictions: std::sync::atomic::AtomicU64,
watchdog_drops: std::sync::atomic::AtomicU64,
/// **The whole job's** held base bytes, across every worker — lane Q's one
/// budget, not one per thread (LAW 5).
live_path: std::sync::atomic::AtomicU64,
peak_path: std::sync::atomic::AtomicU64,
pauses: std::sync::atomic::AtomicU64,
paused_ms: std::sync::atomic::AtomicU64,
batches: std::sync::atomic::AtomicU64,
stalls: std::sync::atomic::AtomicU64,
shed: std::sync::atomic::AtomicU64,
gave_up: AtomicBool,
found_refs: std::sync::Mutex<Vec<(Vec<u8>, u64)>>,
}
impl<'p, 'w, 'a, 'r> Round<'p, 'w, 'a, 'r> {
// ── one subtree ─────────────────────────────────────────────────────────
/// The unit of work: one root, its whole subtree, in a fixed depth-first
/// order.
fn run_root(&self, ri: usize, s: &mut Scratch) -> Result<()> {
// A previous unit that failed may have left a path standing; nothing
// else can, because a finished walk pops every frame.
if !s.stack.is_empty() {
self.drop_path(s);
s.stack.clear();
}
s.unit = ri;
let root = self.roots[ri];
let r = (|| {
let (kind, payload) = self.root_content(root)?;
self.emit(root, kind, &payload, s)?;
if self.forest.children(root).is_empty() {
drop(payload);
} else {
self.push_frame(root, kind, payload, s);
self.walk(s)?;
}
Ok(())
})();
// **The unit is closed even when it failed**, so the drain is never
// left waiting on a root that will never say it is finished.
self.flush_scratch(s, true)?;
r
}
/// A root's own content. `DeltaBase::None` inflates; a `REF_DELTA` root
/// applies its delta to a base this round already promised — either an
/// entry a previous round placed, or one the [`BaseSource`] answered for.
fn root_content(&self, root: u32) -> Result<(GitObjectKind, Vec<u8>)> {
let e = &self.w.entries[root as usize];
match &e.delta_base {
DeltaBase::None => {
let kind = whole_kind(e.obj_type)?;
let mut out = Vec::with_capacity(e.uncompressed_size as usize);
inflate_into(self.pack, e, self.oid_len, &mut out)?;
Ok((kind, out))
}
DeltaBase::Ref(oid) => {
let (kind, base) = match self.oid_to_offset.get(oid.as_slice()).copied() {
Some(o) => {
let be = self
.w
.entries
.binary_search_by_key(&o, |x| x.offset)
.map_err(|_| {
anyhow!("no entry starts at offset {o} — the pack is corrupt")
})?;
self.materialize(be as u32)?
}
None => match self.external.get(oid.as_slice()) {
Some((k, p)) => (*k, p.clone()),
None => return Err(ResolveError::missing_base(oid)),
},
};
let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
inflate_into(self.pack, e, self.oid_len, &mut delta)?;
let mut out = Vec::new();
apply_delta_into(&base, &delta, &mut out)?;
Ok((kind, out))
}
DeltaBase::Offset(_) => bail!(
"the entry at offset {} deltas against an offset, so it is not a root of a \
resolve round — the forest is inconsistent with the walk",
e.offset
),
}
}
/// **The walk.** An explicit stack, not recursion: a verbatim archive grows
/// one delta link per push ([`MAX_DELTA_LINKS`]), so a legitimate chain has
/// no depth this code may assume.
fn walk(&self, s: &mut Scratch) -> Result<()> {
while !s.stack.is_empty() {
let fi = s.stack.len() - 1;
let entry = s.stack[fi].entry;
let nkids = self.forest.children(entry).len();
let nc = s.stack[fi].next_child as usize;
if nc == nkids {
self.pop_frame(s);
continue;
}
let c = self.forest.children(entry)[nc];
s.stack[fi].next_child += 1;
let last = nc + 1 == nkids;
let kind = s.stack[fi].kind;
// The base for this child: moved out on the last one, cloned
// otherwise, re-inflated if the ceiling took it.
let base: Vec<u8> = if s.stack[fi].evicted {
let (_, p) = self.materialize(entry)?;
self.reinflations.fetch_add(1, Ordering::Relaxed);
if let Some(pr) = self.limits.progress {
pr.add_reinflations(1);
}
if !last {
let n = p.len() as u64;
let budget = self.limits.base_budget;
if budget == 0 || self.live_path.load(Ordering::Relaxed) + n <= budget {
// Room for it now: keep the re-inflated copy for the
// next child rather than paying again. No eviction to
// make room — that would thrash.
s.stack[fi].payload = p.clone();
s.stack[fi].evicted = false;
let live = self.live_path.fetch_add(n, Ordering::Relaxed) + n;
self.peak_path.fetch_max(live, Ordering::Relaxed);
}
}
p
} else if last {
let p = std::mem::take(&mut s.stack[fi].payload);
self.live_path
.fetch_sub(p.len() as u64, Ordering::Relaxed);
s.stack[fi].evicted = true;
p
} else {
s.stack[fi].payload.clone()
};
let ce = &self.w.entries[c as usize];
// The scratch buffers are taken out of `s` for the length of the
// call and put back on **every** path, error included: a bail that
// leaves them behind would make the next child allocate again.
let mut delta = std::mem::take(&mut s.delta);
let mut leaf = std::mem::take(&mut s.leaf);
let leafy = self.forest.children(c).is_empty();
let mut carried: Option<Vec<u8>> = None;
let r = (|| -> Result<()> {
inflate_into(self.pack, ce, self.oid_len, &mut delta)?;
if leafy {
// A leaf's payload outlives nothing: it is applied into the
// reused buffer, hashed in place and handed over from there.
apply_delta_into(&base, &delta, &mut leaf)?;
drop(base);
self.emit(c, kind, &leaf, s)
} else {
let mut out = Vec::with_capacity(ce.uncompressed_size as usize);
apply_delta_into(&base, &delta, &mut out)?;
drop(base);
self.emit(c, kind, &out, s)?;
carried = Some(out);
Ok(())
}
})();
// Give back what one big object borrowed: the buffers stay warm at
// `SCRATCH_KEEP_BYTES` and never carry the largest object in the
// pack for the rest of it.
delta.shrink_to(SCRATCH_KEEP_BYTES);
leaf.shrink_to(SCRATCH_KEEP_BYTES);
s.delta = delta;
s.leaf = leaf;
r?;
if let Some(out) = carried {
self.push_frame(c, kind, out, s);
}
}
Ok(())
}
fn push_frame(&self, entry: u32, kind: GitObjectKind, payload: Vec<u8>, s: &mut Scratch) {
let len = payload.len() as u64;
s.stack.push(Frame {
entry,
kind,
payload,
evicted: false,
next_child: 0,
});
self.live_path.fetch_add(len, Ordering::Relaxed);
// **The ceiling first, the high-water mark after.** Recording the peak
// before the eviction counted the base that was about to be dropped,
// so a one-byte budget reported two live bases and the report said the
// ceiling had leaked when it had not.
self.enforce_budget(s);
self.peak_path
.fetch_max(self.live_path.load(Ordering::Relaxed), Ordering::Relaxed);
}
fn pop_frame(&self, s: &mut Scratch) {
if let Some(f) = s.stack.pop()
&& !f.evicted
{
self.live_path
.fetch_sub(f.payload.len() as u64, Ordering::Relaxed);
}
}
/// **Belady on a depth-first path.** The walk returns to the shallowest
/// held frame only after every deeper subtree is finished, so the
/// shallowest is by construction the one whose next use is farthest away —
/// which is exactly the base the ceiling should drop. No `next_use` table
/// is needed to know it; the shape says so.
fn enforce_budget(&self, s: &mut Scratch) {
let budget = self.limits.base_budget;
if budget == 0 {
return;
}
let mut i = 0usize;
// The deepest frame is the one the next child reads from, so it is
// never the eviction candidate — dropping it would re-inflate it on the
// very next line.
while i + 1 < s.stack.len() && self.live_path.load(Ordering::Relaxed) > budget {
if !s.stack[i].evicted {
let n = s.stack[i].payload.len() as u64;
s.stack[i].payload = Vec::new();
s.stack[i].evicted = true;
self.live_path.fetch_sub(n, Ordering::Relaxed);
self.evictions.fetch_add(1, Ordering::Relaxed);
}
i += 1;
}
}
/// Every payload on this worker's path, dropped, and **how many bytes that
/// freed** — the number the watchdog compares with zero.
fn drop_path(&self, s: &mut Scratch) -> u64 {
let mut freed = 0u64;
for f in s.stack.iter_mut() {
if !f.evicted {
freed += f.payload.len() as u64;
f.payload = Vec::new();
f.evicted = true;
}
}
self.live_path.fetch_sub(freed, Ordering::Relaxed);
freed
}
/// Re-inflate an entry from the mmapped pack: its own chain, re-applied.
/// **The one chain walker** (LAW 5) — [`materialize_entry`], with this
/// round's promised external bases in front of the store's.
fn materialize(&self, entry: u32) -> Result<(GitObjectKind, Vec<u8>)> {
let rb = RoundBases {
external: self.external,
inner: self.bases,
};
let of = |oid: &[u8]| self.oid_to_offset.get(oid).copied();
materialize_entry(self.pack, self.w, entry as usize, self.oid_len, &of, &rb)
}
// ── the ordered end ─────────────────────────────────────────────────────
fn emit(&self, index: u32, kind: GitObjectKind, payload: &[u8], s: &mut Scratch) -> Result<()> {
let e = &self.w.entries[index as usize];
let oid = self.hash.oid_of_object(kind, payload);
// Only now is "does a REF_DELTA name this object" answerable, because it
// is keyed by the oid this line just computed.
if self.ref_wanted.contains(&oid.as_slice()) {
s.found_refs.push((oid.clone(), e.offset));
}
let want = self.sink.wants(kind);
let em = Emit {
kind,
row: Resolved {
oid,
offset: e.offset + self.archive_offset,
len: e.len,
stored_type: e.obj_type,
kind,
uncompressed_size: payload.len() as u64,
delta_base: match &e.delta_base {
DeltaBase::Offset(o) => o + self.archive_offset,
_ => 0,
},
},
payload: if want { Some(payload.to_vec()) } else { None },
};
s.out_bytes += em.weight();
s.out.push(em);
self.rows.fetch_add(1, Ordering::Relaxed);
if let Some(p) = self.limits.progress {
p.object_done(e.len);
}
if s.out.len() >= HANDOVER_ROWS || s.out_bytes >= HANDOVER_BYTES {
self.flush_scratch(s, false)?;
}
let n = self.since_check.fetch_add(1, Ordering::Relaxed) + 1;
if n >= self.limits.check_every {
self.since_check.store(0, Ordering::Relaxed);
self.checkpoint(s)?;
}
Ok(())
}
/// Hand this worker's finished objects to the ordered emitter, then try to
/// push the stream forward. Never blocks on the drain: whoever holds it is
/// already doing the work. `done` closes the unit — the drain may then step
/// past it to the next root.
fn flush_scratch(&self, s: &mut Scratch, done: bool) -> Result<()> {
if !s.out.is_empty() || done {
let mut bytes = 0u64;
for em in s.out.iter() {
bytes += em.weight();
}
let unit = s.unit;
{
let mut p = self.lock_pend()?;
let e = p.map.entry(unit).or_default();
if e.rows.is_empty() {
e.rows = std::mem::take(&mut s.out);
} else {
e.rows.append(&mut s.out);
}
e.done |= done;
p.bytes += bytes;
}
s.out.clear();
s.out.shrink_to(HANDOVER_ROWS);
s.out_bytes = 0;
}
self.try_drain(false)
}
fn lock_pend(&self) -> Result<std::sync::MutexGuard<'_, Pending>> {
self.pend
.lock()
.map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))
}
/// **The stream out.** This round's roots in ascending order, and inside
/// each root the depth-first sequence its children lists fix — to the sink
/// first, then to the row callback.
fn try_drain(&self, force: bool) -> Result<()> {
let mut guard = match self.drain.try_lock() {
Ok(g) => g,
Err(std::sync::TryLockError::WouldBlock) => {
if !force {
return Ok(());
}
self.drain
.lock()
.map_err(|_| anyhow!("the resolver's row drain is poisoned"))?
}
Err(std::sync::TryLockError::Poisoned(_)) => {
bail!("the resolver's row drain is poisoned")
}
};
let d = &mut *guard;
loop {
let mut run: Vec<Vec<Emit>> = Vec::new();
let mut held = 0usize;
let mut moved = false;
{
let mut p = self.lock_pend()?;
while d.cursor < self.roots.len() {
let (rows, done) = match p.map.get_mut(&d.cursor) {
Some(ro) => (std::mem::take(&mut ro.rows), ro.done),
None => break,
};
if !rows.is_empty() {
let n: u64 = rows.iter().map(Emit::weight).sum();
p.bytes = p.bytes.saturating_sub(n);
held += rows.len();
run.push(rows);
moved = true;
}
if !done {
break;
}
p.map.remove(&d.cursor);
d.cursor += 1;
moved = true;
if held >= DRAIN_RUN {
break;
}
}
if moved {
self.cv.notify_all();
}
}
if !moved {
return Ok(());
}
for chunk in run {
for em in chunk {
if let Some(pay) = &em.payload {
self.sink.explode(&em.row.oid, em.kind, pay)?;
}
d.batch.push(em.row);
if d.batch.len() >= self.limits.row_batch {
(d.rows)(&mut d.batch)?;
self.batches.fetch_add(1, Ordering::Relaxed);
d.batch.clear();
}
}
}
}
}
/// Everything left, in order, at the end of a round.
fn finish(&self) -> Result<()> {
self.try_drain(true)?;
let mut d = self
.drain
.lock()
.map_err(|_| anyhow!("the resolver's row drain is poisoned"))?;
if !d.batch.is_empty() {
let d = &mut *d;
(d.rows)(&mut d.batch)?;
self.batches.fetch_add(1, Ordering::Relaxed);
d.batch.clear();
}
let p = self.lock_pend()?;
if !p.map.is_empty() || d.cursor != self.roots.len() {
bail!(
"the resolver finished a round at root {} of {} with {} roots still unemitted — \
the round's roots and the walk disagree",
d.cursor,
self.roots.len(),
p.map.len()
);
}
Ok(())
}
/// **The lookahead ceiling, and the one worker it may never stop.**
///
/// A worker that has run far ahead of the ordered stream waits here rather
/// than buffering the pack. The rule for *who* waits is the whole
/// correctness argument: the worker holding the **lowest unit in flight**
/// never waits. Gatling hands its units out in ascending order, so every
/// lower unit is already finished, and the entry the ordered cursor is
/// stuck on therefore belongs either to a finished unit — already in the
/// buffer, and the drain will take it — or to the lowest unit in flight,
/// which is running. Progress is guaranteed either way.
///
/// 🔴 It said "one worker is never allowed to wait, whichever it is", and
/// that HUNG: gatling claims a unit *before* it calls the closure, so the
/// worker allowed to run on was frequently not the one the cursor was
/// waiting for. It then consumed every remaining unit while the worker
/// holding the cursor's own unit sat in `wait` forever, and the scope never
/// joined. Caught by
/// `the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers`, which
/// ran for over 60 s and had to be killed.
fn backpressure(&self, ri: usize) -> Result<()> {
self.try_drain(false)?;
let mut p = self.lock_pend()?;
while p.bytes > self.lookahead
&& !self.stop.load(Ordering::Relaxed)
&& p.in_flight.first().is_some_and(|lowest| *lowest < ri)
{
self.stalls.fetch_add(1, Ordering::Relaxed);
p = self
.cv
.wait(p)
.map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))?;
}
Ok(())
}
/// Enter and leave a unit. The set is what [`backpressure`](Self::backpressure)
/// reads, and leaving one is what lets a waiting worker re-decide.
fn enter(&self, ri: usize) -> Result<()> {
self.lock_pend()?.in_flight.insert(ri);
Ok(())
}
fn leave(&self, ri: usize) {
if let Ok(mut p) = self.pend.lock() {
p.in_flight.remove(&ri);
}
self.cv.notify_all();
}
// ── the checkpoints ─────────────────────────────────────────────────────
/// Every [`crate::memguard::CHECK_EVERY_OBJECTS`] objects **of the whole
/// job**: another worker's failure, the cancel flag, then the watchdog.
fn checkpoint(&self, s: &mut Scratch) -> Result<()> {
if self.stop.load(Ordering::Relaxed) {
bail!("this pack is being failed by another worker");
}
if self.limits.cancel.is_some_and(|c| c.load(Ordering::Relaxed)) {
return Err(ResolveError::cancelled());
}
let Some(dog) = self.limits.watchdog.clone() else {
return Ok(());
};
if dog.breached().is_none() {
return Ok(());
}
// My own share of the problem, dropped before anybody waits.
let mut freed = self.drop_path(s);
// ── GIVE THE CORE BACK BEFORE GIVING THE PACK UP ────────────────────
//
// **A short box wants fewer workers, not a refused pack.** MEASURED on
// the rig, the 16 GB appliance and the 8.12 GiB kernel mirror: one
// worker finishes it with 5.55 GiB to spare, two stop at 96 % and four
// at 86 %. The cost is not the resolver's own structures — peak RSS at
// four workers (13.7 GiB) is BELOW the single-threaded fixpoint's
// (14.04 GiB) — it is that four depth-first cursors over a pack whose
// subtrees span millions of entries keep far more of the 8.12 GiB
// mapping resident at once, and `MemAvailable` counts half of page
// cache.
//
// So a worker that finds the box short **stops being a worker**: it
// waits until it is the lowest unit in flight, which is exactly when
// every worker above it has drained, and the round finishes on one
// core instead of being refused on four. It never deadlocks for the
// same reason [`backpressure`](Self::backpressure) does not — the
// lowest unit in flight never waits, and gatling hands units out in
// ascending order, so the lowest always advances.
//
// The ordered emitter means this changes only WHEN work happens, never
// in what order it comes out: the stream is byte-identical either way.
{
let mut p = self.lock_pend()?;
let mut waited = false;
loop {
if self.stop.load(Ordering::Relaxed) {
break;
}
let lowest = p.in_flight.first().copied();
if lowest.is_some_and(|l| l < s.unit) {
// Somebody below me is still the one the ordered stream is
// waiting for: I am the expendable one. Park.
if !waited {
waited = true;
p.parked += 1;
self.shed.fetch_add(1, Ordering::Relaxed);
if let Some(pr) = self.limits.progress {
pr.add_shed();
pr.set_phase(Phase::Paused);
}
self.cv.notify_all();
}
p = self
.cv
.wait(p)
.map_err(|_| anyhow!("the resolver's emit buffer is poisoned"))?;
continue;
}
// I am the lowest unit in flight — the one that must carry on.
// **Do not pause while other workers are still resolving**:
// they are what the box cannot afford, and each of them will
// park at its own next checkpoint. Pausing here instead would
// stop the only worker that is allowed to make progress and
// then time out on a box that was about to have room.
if p.in_flight.len() > p.parked + 1 {
if waited {
waited = false;
p.parked -= 1;
}
drop(p);
if let Some(pr) = self.limits.progress {
pr.set_phase(Phase::Resolve);
}
return Ok(());
}
break;
}
if waited {
p.parked -= 1;
}
drop(p);
if waited {
if let Some(pr) = self.limits.progress {
pr.set_phase(Phase::Resolve);
}
if self.stop.load(Ordering::Relaxed) {
bail!("this pack is being failed by another worker");
}
// The box may well be fine now that everybody above me has
// stopped. Re-ask before waking the watchdog.
if dog.breached().is_none() {
return Ok(());
}
}
}
if let Some(p) = self.limits.progress {
p.set_phase(Phase::Paused);
p.add_pause();
}
// **Only one worker drives the pause**; the others block on this gate,
// which is the point — an indexer that keeps three threads allocating
// through a pause is not paused. They have already dropped their own
// bases on the way in.
let gate = self
.pause_gate
.lock()
.map_err(|_| anyhow!("the resolver's pause gate is poisoned"))?;
// 🔴 **A give-up is the whole pack's, not one worker's.** Without this
// line the workers queued on the gate each opened a pause of their own
// after the first had already given up. MEASURED on the rig, two
// workers: `gave up after 30681 ms (nothing-to-give)` at 00:59:33, then
// a second pause opened in the same millisecond and ran the FULL
// `PAUSE_DEADLINE` — `gave up after 300164 ms (deadline)` at 01:04:33.
// Five minutes of a client waiting for a verdict the box had already
// reached. One give-up stops the round.
if self.stop.load(Ordering::Relaxed) {
drop(gate);
bail!("this pack is being failed by another worker");
}
if dog.breached().is_none() {
drop(gate);
if let Some(p) = self.limits.progress {
p.set_phase(Phase::Resolve);
}
return Ok(());
}
let (cancel, on_pause, label) = (self.limits.cancel, self.limits.on_pause, self.limits.label);
let mut flush = || -> Result<u64> {
let mut f = std::mem::take(&mut freed);
self.watchdog_drops.fetch_add(1, Ordering::Relaxed);
self.sink.flush()?;
// `false`: the unit is mid-walk, so the drain must not step past
// this root — it is not finished, it is paused.
self.flush_scratch(s, false)?;
self.try_drain(true)?;
if let Some(g) = on_pause {
f = f.saturating_add(g());
}
Ok(f)
};
let paused = dog.pause_until_ok(label, cancel, &mut flush);
let ms = match &paused {
Ok(p) => p.ms,
Err(_) => 0,
};
self.pauses.fetch_add(1, Ordering::Relaxed);
self.paused_ms.fetch_add(ms, Ordering::Relaxed);
if let Some(p) = self.limits.progress {
p.set_phase(Phase::Resolve);
}
drop(gate);
let paused = paused?;
if self.limits.cancel.is_some_and(|c| c.load(Ordering::Relaxed)) {
return Err(ResolveError::cancelled());
}
// **A give-up is not a resume.** The pack is refused by name; its bytes
// stay durable and nothing partial is left indexed.
if paused.end.gave_up() {
self.gave_up.store(true, Ordering::Relaxed);
// Before the error is even built: every worker queued behind the
// gate must find the round already lost.
self.stop.store(true, Ordering::Relaxed);
if self.pend.lock().is_ok() {
self.cv.notify_all();
}
let (done, total) = match self.limits.progress {
Some(p) => {
let sn = p.snapshot();
(sn.objects_done, sn.objects_total)
}
None => (self.rows.load(Ordering::Relaxed), self.w.entries.len() as u64),
};
return Err(ResolveError::out_of_memory(
paused.end.as_str(),
paused.available,
paused.budget,
done,
total,
));
}
Ok(())
}
/// The first failure by **root index**, so a pack that two workers could
/// fail is refused with the same sentence every time.
fn fail(&self, ri: usize, e: anyhow::Error) {
self.stop.store(true, Ordering::Relaxed);
if let Ok(mut g) = self.err.lock() {
let take = match &*g {
Some((i, _)) => ri < *i,
None => true,
};
if take {
*g = Some((ri, e));
}
}
if self.pend.lock().is_ok() {
self.cv.notify_all();
}
}
fn take_err(&self) -> Option<anyhow::Error> {
self.err.lock().ok().and_then(|mut g| g.take()).map(|(_, e)| e)
}
fn report(&self) -> ResolveReport {
ResolveReport {
rows: self.rows.load(Ordering::Relaxed),
reinflations: self.reinflations.load(Ordering::Relaxed),
evictions: self.evictions.load(Ordering::Relaxed),
watchdog_drops: self.watchdog_drops.load(Ordering::Relaxed),
peak_base_bytes: self.peak_path.load(Ordering::Relaxed),
pauses: self.pauses.load(Ordering::Relaxed),
paused_ms: self.paused_ms.load(Ordering::Relaxed),
batches: self.batches.load(Ordering::Relaxed),
stalls: self.stalls.load(Ordering::Relaxed),
shed: self.shed.load(Ordering::Relaxed),
workers: self.workers as u32,
gave_up: self.gave_up.load(Ordering::Relaxed),
}
}
}
/// **The resolver.** One walk, one forest, one ordered stream out, and as many
/// workers as the box was told to use.
struct Resolver<'p, 'w, 'a> {
pack: &'p [u8],
w: &'w PackWalk,
hash: GitHashKind,
oid_len: usize,
archive_offset: u64,
bases: &'a dyn BaseSource,
sink: &'a dyn PayloadSink,
limits: ResolveLimits<'a>,
forest: DeltaForest,
/// The oids `REF_DELTA` entries in this pack name — the half of the
/// dependent set that is not knowable from an offset.
ref_wanted: std::collections::HashSet<&'w [u8]>,
/// …and where they turned out to live, as the rounds place them.
oid_to_offset: HashMap<Vec<u8>, u64>,
report: ResolveReport,
}
impl<'p, 'w, 'a> Resolver<'p, 'w, 'a> {
fn new(
pack: &'p [u8],
w: &'w PackWalk,
hash: GitHashKind,
archive_offset: u64,
bases: &'a dyn BaseSource,
sink: &'a dyn PayloadSink,
limits: ResolveLimits<'a>,
) -> Result<Self> {
// **The dependents, as the forest they always were.** Built from
// `PackWalk::entries` and nothing else (LAW 5): `parent`, the CSR child
// lists, and the roots.
let forest = DeltaForest::build(w)?;
let mut ref_wanted: std::collections::HashSet<&'w [u8]> = std::collections::HashSet::new();
for e in w.entries.iter() {
if let DeltaBase::Ref(oid) = &e.delta_base {
ref_wanted.insert(oid.as_slice());
}
}
Ok(Self {
pack,
w,
hash,
oid_len: hash.oid_len(),
archive_offset,
bases,
sink,
forest,
ref_wanted,
oid_to_offset: HashMap::new(),
report: ResolveReport::default(),
limits,
})
}
/// The fixpoint, one round at a time — and each round is a gatling fan-out
/// over its roots.
///
/// A round is planned before a byte of it is inflated: its roots are the
/// entries whose base is available *now*, and its entry set is the closure
/// of those roots over the forest. That is what lets the ordered emitter
/// know, for every index, whether to wait for it or step past it — and
/// therefore what makes the stream out of N workers the stream out of one.
fn run(&mut self, rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send)) -> Result<()> {
let n = self.w.entries.len();
if let Some(p) = self.limits.progress {
p.set_total(n as u64);
p.set_phase(Phase::Resolve);
}
if n == 0 {
return Ok(());
}
let w = self.w;
let mut done = EntrySet::new(n);
let mut round = 0usize;
while done.len() < n {
let mut roots: Vec<u32> = if round == 0 {
self.forest.whole_roots().to_vec()
} else {
Vec::new()
};
// A `REF_DELTA` names a base by oid. It is resolvable this round if
// an earlier round placed that oid inside the pack, or if the store
// can produce it — exactly the two answers the serial fixpoint
// asked for, asked once each, up front, so the round's membership
// is a fact rather than a race.
let mut external: HashMap<&'w [u8], (GitObjectKind, Vec<u8>)> = HashMap::new();
for &r in self.forest.ref_roots() {
if done.contains(r as usize) {
continue;
}
let DeltaBase::Ref(oid) = &w.entries[r as usize].delta_base else {
continue;
};
if self.oid_to_offset.contains_key(oid.as_slice())
|| external.contains_key(oid.as_slice())
{
roots.push(r);
continue;
}
if let Some(c) = self.bases.content(oid)? {
external.insert(oid.as_slice(), c);
roots.push(r);
}
}
if roots.is_empty() {
// Nothing can move: every remaining entry waits on a base
// nobody can supply. Name the first one — a thin pack is the
// ordinary reason.
for &r in self.forest.ref_roots() {
if !done.contains(r as usize)
&& let DeltaBase::Ref(oid) = &w.entries[r as usize].delta_base
{
return Err(ResolveError::missing_base(oid));
}
}
bail!(
"{} of {n} entries could not be resolved and none of them deltas against an \
oid — the pack is corrupt",
n - done.len()
);
}
roots.sort_unstable();
let in_round = self.forest.closure_of(&roots);
let (rep, found) = self.run_round(&roots, &in_round, &external, rows)?;
self.report.absorb(rep);
for (oid, off) in found {
self.oid_to_offset.insert(oid, off);
}
done.union_with(&in_round);
round += 1;
}
Ok(())
}
/// One round: **the gatling fan-out**. NEVER rayon (LAW 3) — every thread
/// in this constellation originates in `gatling`, and this is its fork-join
/// shape: a fixed `0..roots` of independent units, self-dispatched from one
/// atomic, no barrier between them.
fn run_round(
&self,
roots: &[u32],
in_round: &EntrySet,
external: &HashMap<&'w [u8], (GitObjectKind, Vec<u8>)>,
rows: &mut (dyn FnMut(&mut Vec<Resolved>) -> Result<()> + Send),
) -> Result<(ResolveReport, Vec<(Vec<u8>, u64)>)> {
let workers = self
.limits
.workers
.max(1)
.min(roots.len().max(1))
.min(MAX_WORKERS);
let round = Round {
pack: self.pack,
w: self.w,
forest: &self.forest,
hash: self.hash,
oid_len: self.oid_len,
archive_offset: self.archive_offset,
bases: self.bases,
sink: self.sink,
limits: &self.limits,
ref_wanted: &self.ref_wanted,
oid_to_offset: &self.oid_to_offset,
external,
roots,
in_round,
workers,
lookahead: self.limits.lookahead_bytes.max(1 << 20),
pend: std::sync::Mutex::new(Pending::default()),
cv: std::sync::Condvar::new(),
drain: std::sync::Mutex::new(Drain {
cursor: 0,
batch: Vec::with_capacity(self.limits.row_batch.min(1 << 20)),
rows,
}),
pause_gate: std::sync::Mutex::new(()),
stop: AtomicBool::new(false),
err: std::sync::Mutex::new(None),
since_check: std::sync::atomic::AtomicU64::new(0),
rows: std::sync::atomic::AtomicU64::new(0),
reinflations: std::sync::atomic::AtomicU64::new(0),
evictions: std::sync::atomic::AtomicU64::new(0),
watchdog_drops: std::sync::atomic::AtomicU64::new(0),
live_path: std::sync::atomic::AtomicU64::new(0),
peak_path: std::sync::atomic::AtomicU64::new(0),
pauses: std::sync::atomic::AtomicU64::new(0),
paused_ms: std::sync::atomic::AtomicU64::new(0),
batches: std::sync::atomic::AtomicU64::new(0),
stalls: std::sync::atomic::AtomicU64::new(0),
shed: std::sync::atomic::AtomicU64::new(0),
gave_up: AtomicBool::new(false),
found_refs: std::sync::Mutex::new(Vec::new()),
};
gatling_for_each_unit(roots.len(), workers, |ri| {
if round.stop.load(Ordering::Relaxed) {
return;
}
let r = SCRATCH.with(|cell| -> Result<()> {
let mut s = cell.borrow_mut();
round.enter(ri)?;
let r = (|| {
round.backpressure(ri)?;
if round.stop.load(Ordering::Relaxed) {
return Ok(());
}
round.run_root(ri, &mut s)
})();
if !s.found_refs.is_empty()
&& let Ok(mut g) = round.found_refs.lock()
{
g.append(&mut s.found_refs);
}
round.leave(ri);
r
});
if let Err(e) = r {
round.fail(ri, e);
}
});
if let Some(e) = round.take_err() {
// Everything this round did stays where it is; the caller refuses
// the pack by name and nothing partial is marked indexed.
return Err(e);
}
round.finish()?;
let mut found = round
.found_refs
.lock()
.map_err(|_| anyhow!("the resolver's ref table is poisoned"))?
.split_off(0);
// The order N workers found them in is not an order; sorting makes the
// map the same map at any worker count.
found.sort_unstable();
found.dedup();
Ok((round.report(), found))
}
}
/// The gatling fork-join, by its own name, with the one-worker case kept off
/// the thread pool entirely: `workers == 1` runs the units on the calling
/// thread, which is what makes a 1-worker run the reference a 2- and a
/// 4-worker run are compared against.
fn gatling_for_each_unit<F: Fn(usize) + Sync>(n: usize, workers: usize, f: F) {
znippy_zoomies::gatling_forkjoin::gatling_run(n, workers, f);
}
/// **One object's content from a pack and an entry, with only its chain
/// inflated** — the lazy read path. `offset_of_oid` answers a `REF_DELTA`
/// base that is inside the pack (its entry offset); `bases` answers one that is
/// not. Nothing is cached: a chain of depth d costs d inflates and d−1 delta
/// applications, and nothing else.
pub fn materialize_entry(
pack: &[u8],
w: &PackWalk,
entry: usize,
oid_len: usize,
offset_of_oid: &dyn Fn(&[u8]) -> Option<u64>,
bases: &dyn BaseSource,
) -> Result<(GitObjectKind, Vec<u8>)> {
let e = w
.entries
.get(entry)
.ok_or_else(|| anyhow!("entry {entry} is past the walk ({} entries)", w.entries.len()))?;
match &e.delta_base {
DeltaBase::None => {
let mut out = Vec::with_capacity(e.uncompressed_size as usize);
inflate_into(pack, e, oid_len, &mut out)?;
Ok((whole_kind(e.obj_type)?, out))
}
DeltaBase::Offset(o) => {
let base_entry = w
.entries
.binary_search_by_key(o, |x| x.offset)
.map_err(|_| anyhow!("no entry starts at offset {o} — the pack is corrupt"))?;
let (kind, base) = materialize_entry(pack, w, base_entry, oid_len, offset_of_oid, bases)?;
let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
inflate_into(pack, e, oid_len, &mut delta)?;
let mut out = Vec::new();
apply_delta_into(&base, &delta, &mut out)?;
Ok((kind, out))
}
DeltaBase::Ref(oid) => {
let (kind, base) = match offset_of_oid(oid) {
Some(o) => {
let base_entry = w
.entries
.binary_search_by_key(&o, |x| x.offset)
.map_err(|_| anyhow!("no entry starts at offset {o} — the pack is corrupt"))?;
materialize_entry(pack, w, base_entry, oid_len, offset_of_oid, bases)?
}
None => bases.content(oid)?.ok_or_else(|| ResolveError::missing_base(oid))?,
};
let mut delta = Vec::with_capacity(e.uncompressed_size as usize);
inflate_into(pack, e, oid_len, &mut delta)?;
let mut out = Vec::new();
apply_delta_into(&base, &delta, &mut out)?;
Ok((kind, out))
}
}
}
// ════════════════════════════════════════════════════════════════════════════
// The LAZY read path: one object, one chain, straight out of the archive
// ════════════════════════════════════════════════════════════════════════════
/// Bytes of the verbatim archive, addressed **absolutely**.
///
/// The mmap ([`crate::archive_map`]) answers without a syscall and without a
/// copy; a `pread` answers the tail a snapshot does not cover. Both are the
/// same bytes, which is why the chain walker below can take either and never
/// know which it got.
///
/// It exists so [`materialize_at`] can live here — beside the delta code it
/// reuses — without this module learning what a store is.
pub trait ArchiveBytes {
/// Up to `len` bytes at `at`. **Short is not an error**: a probe near the
/// end of the archive legitimately gets fewer, and the parsers below read a
/// grammar rather than a fixed width. Empty means "there is nothing there",
/// which every caller treats as a corrupt back-reference.
fn at(&self, at: u64, len: u64) -> Result<std::borrow::Cow<'_, [u8]>>;
}
/// A whole `&[u8]` as an archive — what a test and a single-pack caller use.
pub struct SliceArchive<'a>(pub &'a [u8]);
impl ArchiveBytes for SliceArchive<'_> {
fn at(&self, at: u64, len: u64) -> Result<std::borrow::Cow<'_, [u8]>> {
let start = usize::try_from(at).unwrap_or(usize::MAX).min(self.0.len());
let end = start.saturating_add(usize::try_from(len).unwrap_or(usize::MAX)).min(self.0.len());
Ok(std::borrow::Cow::Borrowed(&self.0[start..end]))
}
}
/// **What one read actually cost**, measured by the read rather than predicted.
///
/// The whole point of carrying it: the cache admission decision needs to know
/// whether an object was expensive to produce, and the reader that just
/// produced it is the only thing in the system that knows for certain. The
/// index could carry a depth column instead — git's `.idx` does not, but the
/// walk computes one — and it would still be a prediction of what a read will
/// cost, while this is the bill.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct ReadCost {
/// Delta links followed. `0` is a whole object: one inflate of one zlib
/// stream at one offset, which is what makes a direct read cheap enough
/// that caching it would be a waste of somebody's quota.
pub depth: u32,
/// Bytes the chain produced.
pub inflated: u64,
/// The chain bottomed out on an object this archive does not hold, so a
/// [`BaseSource`] paid for it. Rare, and never cheap.
pub external_base: bool,
}
/// git's own `pack.depth` ceiling doubled. **The depth at which a chain walk
/// stops assuming it will terminate and starts proving it** — see
/// [`CycleGuard`]. It is not a refusal any more, and the 🔴 below says why.
///
/// # 🔴 It WAS a refusal, and that refusal failed ordinary pushes
///
/// MEASURED, oden, 2026-08-30 (lane AI, reproducing lane AD's rig red): 140
/// sequential single-commit pushes of one file into one repository. Push #120
/// was refused with *"this pack is thin: it deltas against 509be6a7… which is
/// not in it, and no base source could produce that object's content … so this
/// repository genuinely does not have that object"* — and every one of the 20
/// pushes after it was refused too, forever. The object was **in the store, one
/// index lookup away, in a pack that had already been absorbed**. The sentence
/// was a lie, and the same red reproduces in this crate alone at push 100 of
/// 150 (`crate::thin_storm`).
///
/// The cause is what a verbatim archive does that stock git does not.
/// `git index-pack --fix-thin` *completes* a pushed thin pack by appending the
/// resolved base into it, so a stored pack's delta chains never leave it and
/// stay under the client's own `pack.depth`. §14 stores the client's bytes
/// **verbatim** — that is what makes a clone a byte-range copy — so a
/// `REF_DELTA` keeps naming a base in an *earlier pack*, and a repository
/// pushed one commit at a time grows a chain **one link per push, without
/// bound**. At the 101st link this ceiling turned a legitimate chain into
/// "corrupt pack", and [`crate::git_ops`]'s base lookup then reported the
/// object as ABSENT rather than as unreadable, which is how a store defect
/// wore a client's clothes.
///
/// A count cannot tell a deep chain from a loop. Revisiting an offset can, and
/// that is what [`CycleGuard`] does — so a cycle is caught *sooner* (the first
/// repeat, wherever it sits) and a legitimate chain is never refused. The
/// constant keeps its name and its value; only its job changed.
pub const MAX_DELTA_LINKS: usize = 100;
/// **A termination proof for a chain walk, paid for only by the chains that
/// need one.**
///
/// Under [`MAX_DELTA_LINKS`] links it is two integer operations and no
/// allocation — the shape every ordinary read has always had. Past that depth
/// it starts recording the archive offsets it has stood on, and a repeat is a
/// cycle *by definition* rather than by a guess about how deep is too deep.
/// The set is only ever entered on chains a corrupt pack or a long push history
/// produced, so the hot path is unchanged; a legitimate chain of `d` links
/// costs `d - MAX_DELTA_LINKS` `u64` slots and nothing else.
///
/// It is one guard for both walkers (LAW 5): [`materialize_at`] here and
/// `GitStore::resolved_type_at` in [`crate::serve`], which followed the same
/// links under a hand-written copy of the same ceiling.
pub struct CycleGuard {
links: usize,
seen: std::collections::HashSet<u64>,
}
impl Default for CycleGuard {
fn default() -> Self {
Self::new()
}
}
impl CycleGuard {
pub fn new() -> Self {
Self {
links: 0,
// Empty, so a chain shallower than the threshold allocates nothing.
seen: std::collections::HashSet::new(),
}
}
/// One link, standing at archive offset `at`. `Err` **only** when this walk
/// has already stood there, which no acyclic chain can do.
pub fn step(&mut self, at: u64) -> Result<()> {
self.links += 1;
if self.links <= MAX_DELTA_LINKS {
return Ok(());
}
if !self.seen.insert(at) {
bail!(
"the delta chain returns to archive offset {at} after {} links — the pack's \
back-references form a cycle, so the entry cannot be reconstructed. This is a \
corrupt pack and not a deep one: depth alone is never refused here, because a \
verbatim archive grows one link per push (see MAX_DELTA_LINKS)",
self.links
);
}
Ok(())
}
/// How many links this walk has taken.
pub fn links(&self) -> usize {
self.links
}
}
/// Enough of an entry to hold its type/size varint plus either an `OFS_DELTA`
/// distance or a `REF_DELTA` oid. 64 covers a sha256 oid and the widest varint.
const HEADER_PROBE: u64 = 64;
/// How much compressed stream is fetched per inflate step. The stream's length
/// is not written down anywhere the index keeps, so it is discovered by
/// inflating; a window means a 40-byte commit costs one probe rather than a
/// megabyte of page faults.
const INFLATE_WINDOW: u64 = 256 << 10;
/// One link of a delta chain, as the entry's own grammar states it.
struct Link {
/// The entry's own archive offset — the key a [`ChainCache`] stores it under.
entry_at: u64,
obj_type: ObjType,
/// The size the header declares: of the delta instruction stream for a
/// delta, of the object itself for a whole entry.
size: u64,
/// Where the zlib stream starts — header skipped.
data_at: u64,
}
/// **One object's content, with only its own chain inflated, addressed by
/// archive offset.**
///
/// This is the lazy-explode read path (`ideas/lazy-explode-index-only-at-push.md`).
/// The eager tier's alternative was to read the *whole containing pack* back and
/// re-resolve it — for `torvalds/linux` an 8.12 GiB read and a 13.9 M-object
/// resolve **per object served**, which is why the exploded tier had to be built
/// eagerly at push time and why that tier reached 141.7 GiB. Reading a chain
/// instead costs `d` inflates and `d − 1` delta applications and touches nothing
/// else in the pack.
///
/// * `at` — the entry's absolute archive offset, from the `objects` table's
/// `offset` column (or from a pending pack's scan).
/// * `offset_of_oid` — resolves a `REF_DELTA`'s base oid to an archive offset;
/// the `objects` index answers it.
/// * `bases` — answers a `REF_DELTA` base the index does not hold (a thin
/// pack's external base). `None` from it is
/// [`ResolveError::missing_base`], refused by name, never guessed.
///
/// Nothing is cached and nothing is written: the caller decides whether the
/// bytes are worth keeping. That separation is what lets the write-back happen
/// off the reader's path.
pub fn materialize_at(
archive: &dyn ArchiveBytes,
at: u64,
oid_len: usize,
offset_of_oid: &dyn Fn(&[u8]) -> Option<u64>,
bases: &dyn BaseSource,
) -> Result<(GitObjectKind, Vec<u8>, ReadCost)> {
materialize_at_with(archive, at, oid_len, offset_of_oid, bases, None)
}
/// **A bounded memo of materialised entries by archive offset**, for a reader
/// that walks many neighbouring chains — the reachability builder reads
/// (nearly) every tree of a repository once, and in a packed repository most
/// trees are deltas against the tree before them. Without it a chain of depth
/// d costs d inflates and d−1 delta applications per object, every time
/// (MEASURED, git.git on dwarf: 330 535 tree reads, 27 s of a 33 s build).
/// With it the outward walk stops at the first link already materialised.
///
/// FIFO by bytes, not LRU: the bases a packed chain reaches are the entries
/// written just before it, so recency of insertion is the right order. An
/// archive is append-only, so an offset's bytes never change under the memo;
/// a gc rewrites into a NEW generation, and this is never held across one.
pub struct ChainCache {
map: std::collections::HashMap<u64, (GitObjectKind, Vec<u8>)>,
order: std::collections::VecDeque<u64>,
bytes: usize,
cap: usize,
hits: u64,
misses: u64,
}
impl ChainCache {
pub fn new(cap_bytes: usize) -> Self {
Self {
map: std::collections::HashMap::new(),
order: std::collections::VecDeque::new(),
bytes: 0,
cap: cap_bytes,
hits: 0,
misses: 0,
}
}
fn get(&mut self, at: u64) -> Option<(GitObjectKind, &[u8])> {
match self.map.get(&at) {
Some((k, p)) => {
self.hits += 1;
Some((*k, p.as_slice()))
}
None => {
self.misses += 1;
None
}
}
}
fn put(&mut self, at: u64, kind: GitObjectKind, payload: &[u8]) {
if payload.len() > self.cap || self.map.contains_key(&at) {
return;
}
while self.bytes + payload.len() > self.cap {
let Some(old) = self.order.pop_front() else { break };
if let Some((_, p)) = self.map.remove(&old) {
self.bytes -= p.len();
}
}
self.bytes += payload.len();
self.order.push_back(at);
self.map.insert(at, (kind, payload.to_vec()));
}
/// `(hits, misses)` since the memo was made.
pub fn stats(&self) -> (u64, u64) {
(self.hits, self.misses)
}
pub fn bytes(&self) -> usize {
self.bytes
}
}
/// [`materialize_at`] with an optional [`ChainCache`]: the walk outward stops
/// at the first link the memo holds, and every link applied on the way back
/// down is put in it.
pub fn materialize_at_with(
archive: &dyn ArchiveBytes,
at: u64,
oid_len: usize,
offset_of_oid: &dyn Fn(&[u8]) -> Option<u64>,
bases: &dyn BaseSource,
mut cache: Option<&mut ChainCache>,
) -> Result<(GitObjectKind, Vec<u8>, ReadCost)> {
// ── walk the chain outward, deepest link last ──────────────────────────
let mut chain: Vec<Link> = Vec::new();
// Set when the chain bottoms out at an object this archive does not hold.
let mut external: Option<Vec<u8>> = None;
// Set when the chain bottoms out at an entry the memo already holds.
let mut memo_hit: Option<(GitObjectKind, Vec<u8>)> = None;
let mut cursor = at;
let mut guard = CycleGuard::new();
loop {
guard.step(cursor)?;
if let Some(c) = cache.as_deref_mut() {
if let Some((k, p)) = c.get(cursor) {
memo_hit = Some((k, p.to_vec()));
break;
}
}
let head = archive.at(cursor, HEADER_PROBE)?;
if head.is_empty() {
bail!("the archive holds no entry at offset {cursor}");
}
let (t, size, n) = crate::pack_walk::type_and_size_of(&head)?;
match t {
ObjType::Commit | ObjType::Tree | ObjType::Blob | ObjType::Tag => {
chain.push(Link { entry_at: cursor, obj_type: t, size, data_at: cursor + n as u64 });
break;
}
ObjType::OfsDelta => {
let (distance, d) = crate::pack_walk::ofs_distance_of(head.get(n..).unwrap_or(&[]))?;
let base = cursor.checked_sub(distance).ok_or_else(|| {
anyhow!(
"the ofs-delta at archive offset {cursor} names a base {distance} bytes \
back, which is before the start of the archive"
)
})?;
chain.push(Link { entry_at: cursor, obj_type: t, size, data_at: cursor + (n + d) as u64 });
cursor = base;
}
ObjType::RefDelta => {
let base_oid = head
.get(n..n + oid_len)
.ok_or_else(|| {
anyhow!(
"the ref-delta entry at archive offset {cursor} has no base oid after \
its header"
)
})?
.to_vec();
chain.push(Link { entry_at: cursor, obj_type: t, size, data_at: cursor + (n + oid_len) as u64 });
match offset_of_oid(&base_oid) {
Some(o) => cursor = o,
None => {
external = Some(base_oid);
break;
}
}
}
}
}
// ── the bottom of the chain: a whole object, or somebody else's ────────
let external_base = external.is_some();
let (kind, mut base) = match (memo_hit, external) {
(Some(hit), _) => hit,
(None, Some(oid)) => bases
.content(&oid)?
.ok_or_else(|| ResolveError::missing_base(&oid))?,
(None, None) => {
let last = chain.pop().expect("a chain that ended has a last link");
let mut out = Vec::new();
inflate_from(archive, last.data_at, last.size, &mut out)?;
let kind = whole_kind(last.obj_type)?;
if let Some(c) = cache.as_deref_mut() {
c.put(last.entry_at, kind, &out);
}
(kind, out)
}
};
// ── apply the deltas back down to the object that was asked for ────────
let depth = chain.len() as u32;
let mut delta = Vec::new();
let mut out = Vec::new();
while let Some(link) = chain.pop() {
inflate_from(archive, link.data_at, link.size, &mut delta)?;
out.clear();
apply_delta_into(&base, &delta, &mut out)?;
std::mem::swap(&mut base, &mut out);
if let Some(c) = cache.as_deref_mut() {
c.put(link.entry_at, kind, &base);
}
}
let cost = ReadCost {
depth,
inflated: base.len() as u64,
external_base,
};
Ok((kind, base, cost))
}
/// Inflate `expected` bytes of zlib starting at `data_at`, a window at a time.
///
/// The compressed length is **not** knowable from the index — `objects.len` is
/// the entry's stored extent only for an entry the walk measured, and a chain
/// base reached by back-reference was not measured here. So the stream is its
/// own terminator: inflate until it says `StreamEnd` or until exactly the
/// declared number of bytes have come out, and disagree loudly if the two
/// answers differ. `out` is reserved once at the declared size and never grows.
fn inflate_from(
archive: &dyn ArchiveBytes,
data_at: u64,
expected: u64,
out: &mut Vec<u8>,
) -> Result<()> {
let want = usize::try_from(expected).map_err(|_| anyhow!("object size overflows usize"))?;
out.clear();
out.reserve(want);
let mut d = flate2::Decompress::new(true);
let mut pos = data_at;
while out.len() < want {
let chunk = archive.at(pos, INFLATE_WINDOW)?;
if chunk.is_empty() {
bail!("the zlib stream at {data_at} runs past the end of the archive");
}
let before = d.total_in();
let status = d
.decompress_vec(&chunk, out, flate2::FlushDecompress::None)
.map_err(|e| anyhow!("inflating the entry at {data_at}: {e}"))?;
let consumed = d.total_in() - before;
pos += consumed;
if status == flate2::Status::StreamEnd {
break;
}
if consumed == 0 {
bail!(
"the zlib stream at {data_at} stalled after {} of {expected} bytes",
out.len()
);
}
}
if out.len() as u64 != expected {
bail!(
"the entry at {data_at} inflated to {} bytes, its header declared {expected}",
out.len()
);
}
Ok(())
}
/// The real git type of a non-delta entry.
fn whole_kind(t: ObjType) -> Result<GitObjectKind> {
Ok(match t {
ObjType::Commit => GitObjectKind::Commit,
ObjType::Tree => GitObjectKind::Tree,
ObjType::Blob => GitObjectKind::Blob,
ObjType::Tag => GitObjectKind::Tag,
ObjType::OfsDelta | ObjType::RefDelta => {
bail!("a delta entry has no type of its own — its base's type is the answer")
}
})
}
/// Inflate one entry's stream into `out` (cleared first). The walk already
/// proved the length, so this reserves exactly the declared size and never
/// grows; a reused `out` allocates nothing.
fn inflate_into(pack: &[u8], e: &PackEntry, oid_len: usize, out: &mut Vec<u8>) -> Result<()> {
let start = e.offset as usize;
let end = start + e.len as usize;
if end > pack.len() {
bail!("entry at {start} runs past the end of the pack");
}
// Skip the header the walk already parsed: the zlib stream is what is left
// after the type/size varint and any base reference.
let header = header_len(&pack[start..end], e, oid_len)?;
out.clear();
out.reserve(e.uncompressed_size as usize);
let mut d = flate2::Decompress::new(true);
d.decompress_vec(&pack[start + header..end], out, flate2::FlushDecompress::Finish)
.map_err(|err| anyhow!("inflating the entry at {start}: {err}"))?;
if out.len() as u64 != e.uncompressed_size {
bail!(
"the entry at {start} inflated to {} bytes, the walk measured {}",
out.len(),
e.uncompressed_size
);
}
Ok(())
}
/// Inflate one entry's stream into a fresh buffer. What a test or a one-off
/// caller wants; the resolver uses [`inflate_into`].
#[cfg(test)]
fn inflate(pack: &[u8], e: &PackEntry, oid_len: usize) -> Result<Vec<u8>> {
let mut out = Vec::new();
inflate_into(pack, e, oid_len, &mut out)?;
Ok(out)
}
/// How many bytes of an entry are header rather than zlib stream. Recomputed
/// from the bytes rather than remembered, so it cannot drift from the walk's own
/// reading of them — and the walk's `len` is what bounds it.
fn header_len(entry: &[u8], e: &PackEntry, oid_len: usize) -> Result<usize> {
let mut i = 0usize;
let mut cont = true;
while cont {
let b = *entry
.get(i)
.ok_or_else(|| anyhow!("the type/size header runs off the entry"))?;
cont = b & 0x80 != 0;
i += 1;
}
match e.obj_type {
ObjType::OfsDelta => {
let mut cont = true;
while cont {
let b = *entry
.get(i)
.ok_or_else(|| anyhow!("the ofs-delta distance runs off the entry"))?;
cont = b & 0x80 != 0;
i += 1;
}
}
ObjType::RefDelta => i += oid_len,
_ => {}
}
if i >= entry.len() {
bail!("the entry's header consumes all of it, leaving no stream");
}
Ok(i)
}
/// git's delta format: two sizes, then copy-from-base and insert-literal
/// instructions. Fresh-buffer form of [`apply_delta_into`].
#[cfg(test)]
fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>> {
let mut out = Vec::new();
apply_delta_into(base, delta, &mut out)?;
Ok(out)
}
/// git's delta format applied into `out` (cleared first, reserved to the
/// declared target size).
fn apply_delta_into(base: &[u8], delta: &[u8], out: &mut Vec<u8>) -> Result<()> {
let mut i = 0usize;
let base_size = delta_varint(delta, &mut i)?;
if base_size != base.len() as u64 {
bail!(
"the delta expects a base of {base_size} bytes, its base is {}",
base.len()
);
}
let target_size = delta_varint(delta, &mut i)?;
out.clear();
out.reserve(target_size as usize);
while i < delta.len() {
let op = delta[i];
i += 1;
if op & 0x80 != 0 {
// Copy from the base. Offset in up to 4 bytes, size in up to 3;
// a zero size means 0x10000, which is git's own special case.
let mut off = 0u64;
for bit in 0..4 {
if op & (1 << bit) != 0 {
off |= u64::from(*delta.get(i).ok_or_else(|| anyhow!("delta ends mid-copy"))?)
<< (bit * 8);
i += 1;
}
}
let mut size = 0u64;
for bit in 0..3 {
if op & (0x10 << bit) != 0 {
size |= u64::from(*delta.get(i).ok_or_else(|| anyhow!("delta ends mid-copy"))?)
<< (bit * 8);
i += 1;
}
}
if size == 0 {
size = 0x1_0000;
}
let from = off as usize;
let to = from
.checked_add(size as usize)
.ok_or_else(|| anyhow!("a delta copy range overflows"))?;
if to > base.len() {
bail!(
"a delta copies base[{from}..{to}] out of a {}-byte base",
base.len()
);
}
out.extend_from_slice(&base[from..to]);
} else {
// Insert literal. A zero-length insert is not a valid instruction.
let n = op as usize;
if n == 0 {
bail!("a delta carries a zero-length insert instruction");
}
let end = i
.checked_add(n)
.ok_or_else(|| anyhow!("a delta insert overflows"))?;
if end > delta.len() {
bail!("a delta insert of {n} bytes runs off the end");
}
out.extend_from_slice(&delta[i..end]);
i = end;
}
}
if out.len() as u64 != target_size {
bail!(
"the delta declares a {target_size}-byte result and produced {}",
out.len()
);
}
Ok(())
}
/// The delta header's little-endian 7-bit varint. Not the pack entry's varint.
fn delta_varint(b: &[u8], i: &mut usize) -> Result<u64> {
let mut v = 0u64;
let mut shift = 0u32;
loop {
let byte = *b
.get(*i)
.ok_or_else(|| anyhow!("a delta size varint runs off the end"))?;
*i += 1;
if shift >= 64 {
bail!("a delta size varint is longer than a u64");
}
v |= u64::from(byte & 0x7f) << shift;
shift += 7;
if byte & 0x80 == 0 {
return Ok(v);
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::object::canonical;
use std::path::{Path, PathBuf};
/// A label that answers `.display()`, so a source that is a generated pack
/// and one that is a path on disk name themselves the same way in a failure.
struct Named<'a>(&'a str);
impl Named<'_> {
fn display(&self) -> &str {
self.0
}
}
/// Parse a real `.idx` (v2) into `(oid, pack offset)` pairs. Twenty lines of
/// a frozen format, and it is git's own answer to the question this module
/// computes — which is what makes it a differential guard and not a
/// restatement of our own code.
fn read_idx(bytes: &[u8]) -> Vec<(Vec<u8>, u64)> {
assert_eq!(&bytes[0..4], b"\xfftOc", "not an idx v2");
assert_eq!(u32::from_be_bytes(bytes[4..8].try_into().unwrap()), 2);
let fanout_end = 8 + 256 * 4;
let n = u32::from_be_bytes(bytes[fanout_end - 4..fanout_end].try_into().unwrap()) as usize;
let oids = fanout_end;
let crcs = oids + n * 20;
let offs = crcs + n * 4;
let big = offs + n * 4;
let mut out = Vec::with_capacity(n);
for i in 0..n {
let oid = bytes[oids + i * 20..oids + i * 20 + 20].to_vec();
let raw = u32::from_be_bytes(bytes[offs + i * 4..offs + i * 4 + 4].try_into().unwrap());
let offset = if raw & 0x8000_0000 != 0 {
let j = (raw & 0x7fff_ffff) as usize;
u64::from_be_bytes(bytes[big + j * 8..big + j * 8 + 8].try_into().unwrap())
} else {
u64::from(raw)
};
out.push((oid, offset));
}
out
}
/// Real packs with their real indexes, from this machine's repositories.
fn real_pairs(cap: usize) -> Vec<(PathBuf, PathBuf)> {
let mut out = Vec::new();
let Ok(repos) = std::fs::read_dir(std::path::PathBuf::from(std::env::var_os("HOME").unwrap_or_default()).join("git")) else {
return out;
};
for repo in repos.flatten() {
let dir = repo.path().join(".git/objects/pack");
let Ok(files) = std::fs::read_dir(&dir) else {
continue;
};
for f in files.flatten() {
let p = f.path();
if p.extension().is_some_and(|e| e == "pack")
&& f.metadata().map(|m| m.len() < 32 << 20).unwrap_or(false)
{
let idx = p.with_extension("idx");
if idx.exists() {
out.push((p, idx));
if out.len() >= cap {
return out;
}
}
}
}
}
out
}
/// **Pack/index pairs to compare against, the generated corpus first.**
///
/// 🔴 This used to be [`real_pairs`] alone, and that made the guard's corpus
/// the developer's disk: it took the first six `.pack` files with an `.idx`
/// beside them under `~/git`, in `read_dir` order, and asserted
/// it had found at least one. On a fresh clone, on CI, or on anyone else's
/// machine it fails with *"no real pack found under ~/git — this
/// guard has nothing to compare"* — proven 2026-08-25 by running the suite
/// with a tmpfs over that directory.
///
/// The corpus from [`crate::pack_fixture`] leads the list, and stock git
/// writes its `.idx` — so the arbiter is still git and not us, but the pack
/// it arbitrates is one this repository states in source. Real packs still
/// follow when the machine has any: they are the only place a **thin** pack
/// turns up, and finding those in the wild is a fact this guard records.
fn sources() -> Vec<(String, Vec<u8>, Vec<u8>)> {
let mut out = Vec::new();
if std::process::Command::new("git")
.arg("--version")
.output()
.is_ok()
{
let pack = crate::pack_fixture::corpus().pack.clone();
let scratch = crate::store::tests::tmpdir("resolve-idx-oracle");
let idx = crate::git_oracle::git_idx_for(&scratch, "corpus.git", &pack)
.expect("stock git indexes the generated corpus");
out.push(("the generated corpus".to_string(), pack, idx));
}
for (pack_path, idx_path) in real_pairs(6) {
let (Ok(pack), Ok(idx)) = (std::fs::read(&pack_path), std::fs::read(&idx_path)) else {
continue;
};
out.push((pack_path.display().to_string(), pack, idx));
}
out
}
/// **git's own `.idx` is the arbiter.** For every real pack on this machine,
/// every oid we compute and the offset we computed it at must appear in
/// git's index, and the two sets must have the same size. A delta applier
/// that is subtly wrong produces a different hash and cannot pass this.
///
/// Seen RED by changing `size = 0x1_0000` to `size = 0x1_000` in
/// [`apply_delta`] — git's zero-size copy special case:
/// ".../facett/...pack-62582dd0…: the delta declares a 149392-byte result and
/// produced 87952". A single wrong constant in the delta applier and a real
/// repository's pack stops resolving.
///
/// MEASURED while writing it: **10 899 objects over 3 packs** match git's own
/// `.idx` oid for oid and offset for offset, and **3 of the 6 real packs on
/// this machine are thin** — they delta against objects that are not in them,
/// which is the §14 hole showing up in the wild rather than in theory.
#[test]
fn every_oid_we_compute_is_the_oid_git_wrote_in_its_idx() {
let pairs = sources();
assert!(
!pairs.is_empty(),
"neither stock git nor a real pack is available, so this guard has nothing to \
compare and must not pass silently"
);
let mut objects = 0usize;
let mut full = 0usize;
let mut thin = 0usize;
for (pack_path, pack, idx_bytes) in pairs {
let pack_path = Named(&pack_path);
let idx = read_idx(&idx_bytes);
// MEASURED, and a surprise worth recording: real packs on this
// machine DO delta against objects outside themselves. Such a pack
// cannot be compared here — resolving it is exactly what §14 leaves
// open — but it must not make the guard pass vacuously either, so it
// is counted and named and at least one pack has to compare in full.
let ours = match resolve(&pack, GitHashKind::Sha1, 0, &NoBases) {
Ok(r) => r,
Err(e) => {
assert!(
e.to_string().contains("thin"),
"{}: {e}",
pack_path.display()
);
eprintln!("{}: THIN, external base — skipped", pack_path.display());
thin += 1;
continue;
}
};
full += 1;
assert_eq!(
ours.len(),
idx.len(),
"{}: we resolved {} objects, git indexed {}",
pack_path.display(),
ours.len(),
idx.len()
);
let theirs: HashMap<Vec<u8>, u64> = idx.into_iter().collect();
for r in &ours {
match theirs.get(&r.oid) {
Some(&off) => assert_eq!(
off,
r.offset,
"{}: {} is at {} in git's idx and we put it at {}",
pack_path.display(),
hex::encode(&r.oid),
off,
r.offset
),
None => panic!(
"{}: we computed {} at offset {}, which git's idx does not contain — the \
resolution is wrong",
pack_path.display(),
hex::encode(&r.oid),
r.offset
),
}
}
eprintln!("{}: {} objects agree with git", pack_path.display(), ours.len());
objects += ours.len();
}
eprintln!("{objects} objects over {full} packs agree with git's own .idx; {thin} thin");
assert!(full > 0, "every pack compared was thin — nothing was compared");
assert!(objects > 1000, "only {objects} objects compared");
}
/// The three facts the objects table needs and `.idx` cannot supply: the
/// **stored** type (delta or not), the **resolved** type, and the
/// post-resolution size. Asserted against the pack's own delta structure, on
/// a real pack, so it cannot be satisfied by a store-and-echo.
///
/// Seen RED by resolving a delta to `GitObjectKind::Blob` instead of to its
/// base's kind: "a delta resolves to its base's type:
/// c6d50e761d025c179ffef1c3d68c56aae0a53270 vs base
/// 8e15741296ebe3a0508522b76fe2ec4982396b6d — left: Blob, right: Commit".
///
/// MEASURED on that pack: 4292 deltas, 2715 of them resolving to something
/// other than a blob, and **all 4292** carrying a resolved size unlike their
/// delta-stream size.
#[test]
fn a_delta_carries_its_stored_type_and_its_resolved_type_and_size() {
let pack = crate::pack_fixture::corpus().pack.clone();
let pack_path = Named("the generated corpus");
let ours = resolve(&pack, GitHashKind::Sha1, 0, &NoBases).unwrap();
// One walk, reused. Walking per entry turns this guard into an O(n^2)
// pass over a 7000-object pack and it stops finishing.
let stream_size: HashMap<u64, u64> = walk(&pack, 20)
.unwrap()
.entries
.iter()
.map(|e| (e.offset, e.uncompressed_size))
.collect();
let deltas: Vec<&Resolved> = ours
.iter()
.filter(|r| matches!(r.stored_type, ObjType::OfsDelta | ObjType::RefDelta))
.collect();
assert!(
!deltas.is_empty(),
"{} carries no deltas, so it proves nothing about resolution",
pack_path.display()
);
// A delta's resolved type is a real git type, never a delta code, and it
// matches its base's.
let by_offset: HashMap<u64, &Resolved> = ours.iter().map(|r| (r.offset, r)).collect();
let mut non_blob = 0usize;
for d in &deltas {
assert!(
matches!(
d.kind,
GitObjectKind::Blob
| GitObjectKind::Tree
| GitObjectKind::Commit
| GitObjectKind::Tag
),
"a resolved type must be a real git type"
);
if d.kind != GitObjectKind::Blob {
non_blob += 1;
}
if d.delta_base != 0 {
let base = by_offset[&d.delta_base];
assert_eq!(
d.kind,
base.kind,
"a delta resolves to its base's type: {} vs base {}",
hex::encode(&d.oid),
hex::encode(&base.oid)
);
// The delta_base column addresses BYTES, and those bytes are an
// entry we also resolved. An ordinal could not be checked like
// this at all.
assert!(
base.offset < d.offset,
"an ofs-delta base is always earlier in the pack"
);
}
}
assert!(
non_blob > 0,
"{} deltas and not one resolved to a tree/commit/tag — the resolved type is not being \
taken from the base",
deltas.len()
);
// The post-resolution size is the payload's real length, not the delta
// stream's. For a delta the two are almost never equal.
let differing = deltas
.iter()
.filter(|d| stream_size[&d.offset] != d.uncompressed_size)
.count();
assert!(
differing > 0,
"not one delta's resolved size differs from its delta-stream size, which cannot be \
true of a real pack — the resolved size is being copied from the header"
);
eprintln!(
"{}: {} deltas, {non_blob} non-blob, {differing} with a resolved size unlike the \
stream size",
pack_path.display(),
deltas.len()
);
}
/// A thin pack is refused **by name**, and the refusal says what decision is
/// missing. It is not resolved to a wrong oid and it is not silently dropped.
///
/// Seen RED by making the no-progress arm `bail!("stuck")` instead of
/// `ResolveError::missing_base`: "names the base: stuck".
#[test]
fn a_thin_pack_is_refused_by_name_and_says_what_is_missing() {
// One ref-delta against an oid nothing can supply.
let base_oid = vec![0x5a; 20];
let mut pack = b"PACK".to_vec();
pack.extend_from_slice(&2u32.to_be_bytes());
pack.extend_from_slice(&1u32.to_be_bytes());
// A delta whose base is 4 bytes and whose target is 4 bytes: copy all.
let delta = vec![0x04, 0x04, 0x90, 0x04];
pack.push(0x70 | (delta.len() as u8 & 0x0f)); // type 7, size 4
pack.extend_from_slice(&base_oid);
pack.extend_from_slice(&{
use std::io::Write;
let mut e = flate2::write::ZlibEncoder::new(Vec::new(), flate2::Compression::default());
e.write_all(&delta).unwrap();
e.finish().unwrap()
});
pack.extend_from_slice(&[0u8; 20]);
let err = resolve(&pack, GitHashKind::Sha1, 0, &NoBases)
.expect_err("a thin pack with no base source cannot resolve");
let msg = err.to_string();
assert!(msg.contains(&hex::encode(&base_oid)), "names the base: {msg}");
assert!(msg.contains("§14"), "says which decision is missing: {msg}");
// With a source that CAN supply it, the same pack resolves — so the
// refusal is about the missing content, not about ref-deltas.
struct One(Vec<u8>);
impl BaseSource for One {
fn content(&self, oid: &[u8]) -> Result<Option<(GitObjectKind, Vec<u8>)>> {
Ok((oid == self.0.as_slice()).then(|| (GitObjectKind::Blob, b"abcd".to_vec())))
}
}
let ok = resolve(&pack, GitHashKind::Sha1, 0, &One(base_oid)).expect("with a base it works");
assert_eq!(ok.len(), 1);
assert_eq!(ok[0].kind, GitObjectKind::Blob);
assert_eq!(ok[0].uncompressed_size, 4);
assert_eq!(
ok[0].oid,
GitHashKind::Sha1.oid_of(&canonical(GitObjectKind::Blob, b"abcd")),
"the resolved object is the base copied whole, so it hashes as `abcd`"
);
}
/// **The `delta_base` column, materialised — from a real pack, through all
/// three index layouts and the read stack, and back out again.**
///
/// This is the guard the column was added for. It asserts *applied output*:
/// resolve a real pack, build every arm over the rows, and for every
/// `OFS_DELTA` read the base offset **back out of the index** and require it
/// to land on an object the same index holds — earlier in the archive, and
/// with a byte extent that contains it. An ordinal in that column could not
/// satisfy this at all, which is §13's decision checked rather than quoted.
///
/// The three arms are compared row for row, because that is what caught a
/// swapped `len`/`size` write in the previous sweep while two of the three
/// stayed green.
///
/// Seen RED three times, each for a different way the column can be wrong
/// while every other fact stays right:
///
/// 1. **Never written.** `Resolved::index_entry` returning `delta_base: 0`:
/// "FourTables: b76687fbb34020672608bcb1a5e027c2d8b0346a is an ofs-delta
/// with no recorded base".
/// 2. **Written from the wrong field.** `delta_base: self.offset` — a
/// plausible archive offset that is non-zero, inside the pack, and lands
/// on a real entry boundary, so only the identity check catches it:
/// "FourTables: b76687fb… records base 91272 which is its own offset,
/// not its base's".
/// 3. **Written in the wrong coordinate space.** `resolve_walked` yielding
/// `*o` instead of `o + archive_offset`, i.e. pack-relative rather than
/// archive-relative — the bug that an *ordinal* column would have had no
/// way to express and no way to detect: "FourTables: b76687fb… records
/// base offset 86534, which starts no object in this index". This is why
/// the fixture resolves at `AT = 4096` rather than at 0; at 0 the two
/// spaces coincide and the guard would be blind.
///
/// All three restored.
#[test]
fn the_delta_base_column_survives_all_three_arms_over_the_corpus() {
use crate::index_layout::{
FourTables, IndexEntry, ObjType, ObjectIndex, OneTableFourColumns, PackedPayload,
};
use crate::read_stack::{ObjectReadStack, RebuildTriggers};
let pack = crate::pack_fixture::corpus().pack.clone();
// A non-zero archive offset on purpose: `delta_base` is in the archive's
// coordinate space, so a resolver that forgot to rebase it would give
// pack-relative values that no longer locate anything.
const AT: u64 = 4096;
let rows = resolve(&pack, GitHashKind::Sha1, AT, &NoBases).unwrap();
let entries: Vec<IndexEntry> = rows.iter().map(|r| r.index_entry()).collect();
let a = FourTables::build(&entries).unwrap();
let b = OneTableFourColumns::build(&entries).unwrap();
let c = PackedPayload::build(&entries).unwrap();
let stack = ObjectReadStack::<OneTableFourColumns>::in_memory(RebuildTriggers::manual())
.unwrap();
stack.append(&entries).unwrap();
stack.rebuild().unwrap();
// Every extent this pack's objects occupy, read back out of the index.
let extents: HashMap<u64, u64> = entries
.iter()
.map(|e| {
let r = a.lookup(&e.oid).expect("a stored oid resolves");
(r.offset, r.len)
})
.collect();
assert_eq!(extents.len(), entries.len(), "two objects share an offset");
let named: [(&str, &dyn ObjectIndex); 4] =
[("FourTables", &a), ("OneTableFourColumns", &b), ("PackedPayload", &c), ("ObjectReadStack", &stack)];
let mut ofs_deltas = 0usize;
for (name, idx) in named {
let mut with_base = 0usize;
for e in &entries {
let row = idx.lookup(&e.oid).expect("a stored oid resolves");
// All four layouts, row for row, on every fact.
assert_eq!(
row,
a.lookup(&e.oid).unwrap(),
"{name} disagrees with FourTables on {}",
hex::encode(&e.oid)
);
if row.obj_type != ObjType::OfsDelta {
continue;
}
with_base += 1;
assert_ne!(
row.delta_base, 0,
"{name}: {} is an ofs-delta with no recorded base",
hex::encode(&e.oid)
);
assert_ne!(
row.delta_base,
row.offset,
"{name}: {} records base {} which is its own offset, not its base's",
hex::encode(&e.oid),
row.delta_base
);
assert!(
row.delta_base >= AT,
"{name}: base {} is below the archive offset {AT} — it was never rebased",
row.delta_base
);
// The whole claim: it addresses an entry this index holds.
let base_len = extents.get(&row.delta_base).unwrap_or_else(|| {
panic!(
"{name}: {} records base offset {}, which starts no object in this index",
hex::encode(&e.oid),
row.delta_base
)
});
assert!(
row.delta_base + base_len <= row.offset,
"{name}: the base at {} (+{base_len}) overlaps the delta at {}",
row.delta_base,
row.offset
);
}
assert!(
with_base > 0,
"{name}: {} ofs-deltas resolved and 0 of them carry a base offset — the column \
is not being written",
entries
.iter()
.filter(|e| e.obj_type == ObjType::OfsDelta)
.count()
);
ofs_deltas = with_base;
}
assert!(
ofs_deltas > 100,
"the corpus carries only {ofs_deltas} ofs-deltas — too few to prove anything"
);
eprintln!(
"{ofs_deltas} ofs-delta base offsets located their base entry in all four layouts"
);
}
/// **A base that several entries delta against survives until the last one
/// has had it.**
///
/// This replaces `a_blob_that_is_nobodys_base_is_hashed_and_dropped`, which
/// read the retention policy off `Resolved::payload`. That field is gone
/// (see the struct's docs), and the property it stood for — peak memory is
/// the live base set, not the object set — is measured in bytes now by
/// `tests/resolve_peak_memory.rs` rather than inferred from a flag.
///
/// What is left here is the *risk* the reference counting introduced, and it
/// is the one that matters: an off-by-one that frees a base while a
/// dependent still needs it. That cannot be a silent wrong answer —
/// `resolve_walked` fails the whole pack by name — so the assertion is that
/// a pack full of shared bases resolves at all.
///
/// **The test refuses to run on a pack that could not expose the bug.** A
/// corpus of only single-dependent chains would pass this with the counting
/// deleted entirely, which is the blind-guard shape LAW 2 is about, so the
/// fan-out is asserted before the resolution is.
///
/// Seen RED by `*left -= 1;` → `*left = 0;` in [`consume`] (drop every base
/// on first use): "entry at offset 3141 deltas against offset 2724 which no
/// entry starts at — the pack is corrupt", on the first pack tried.
#[test]
fn a_base_many_entries_share_outlives_all_of_them() {
let mut checked = 0usize;
let mut widest = 0usize;
let mut corpora: Vec<(String, Vec<u8>)> =
vec![("the generated corpus".to_string(), crate::pack_fixture::corpus().pack.clone())];
for (pack_path, _) in real_pairs(4) {
if let Ok(bytes) = std::fs::read(&pack_path) {
corpora.push((pack_path.display().to_string(), bytes));
}
}
for (pack_path, pack) in corpora {
let pack_path = Named(&pack_path);
let w = walk(&pack, 20).unwrap();
// How many entries name each base. Anything above 1 is a base the
// counting has to hold across more than one consumer.
let mut uses: HashMap<u64, usize> = HashMap::new();
for e in &w.entries {
if let DeltaBase::Offset(o) = e.delta_base {
*uses.entry(o).or_default() += 1;
}
}
let shared = uses.values().filter(|n| **n > 1).count();
let fan_out = uses.values().copied().max().unwrap_or(0);
if shared == 0 {
continue;
}
widest = widest.max(fan_out);
let rows = resolve(&pack, GitHashKind::Sha1, 0, &NoBases)
.unwrap_or_else(|e| panic!("{}: {e}", pack_path.display()));
assert_eq!(
rows.len(),
w.entries.len(),
"{}: {} of {} entries resolved",
pack_path.display(),
rows.len(),
w.entries.len()
);
eprintln!(
"{}: {shared} bases shared by more than one entry, widest fan-out {fan_out}, all \
{} entries resolved",
pack_path.display(),
rows.len()
);
checked += 1;
}
assert!(
checked > 0 && widest > 2,
"no pack compared had a base shared by more than two entries (checked {checked}, \
widest {widest}) — this test cannot see an early free and must not report a pass"
);
}
/// The corpus plus whatever real packs the box has, as `(name, bytes)`.
fn corpora(cap: usize) -> Vec<(String, Vec<u8>)> {
let mut out: Vec<(String, Vec<u8>)> =
vec![("the generated corpus".to_string(), crate::pack_fixture::corpus().pack.clone())];
for (pack_path, _) in real_pairs(cap) {
if let Ok(bytes) = std::fs::read(&pack_path) {
out.push((pack_path.display().to_string(), bytes));
}
}
out
}
/// Every `(oid, offset, size, delta_base)` the resolver produced, sorted.
fn rows_of(rows: &[Resolved]) -> Vec<(Vec<u8>, u64, u64, u64)> {
let mut v: Vec<_> = rows
.iter()
.map(|r| (r.oid.clone(), r.offset, r.uncompressed_size, r.delta_base))
.collect();
v.sort();
v
}
fn stream(pack: &[u8], limits: ResolveLimits<'_>) -> (Vec<Resolved>, ResolveReport, u64) {
let w = walk(pack, 20).unwrap();
let mut out = Vec::new();
let mut calls = 0u64;
let report = resolve_streaming(
pack,
&w,
GitHashKind::Sha1,
0,
&NoBases,
&NoSink,
limits,
&mut |rows| {
calls += 1;
out.extend(rows.drain(..));
Ok(())
},
)
.unwrap();
(out, report, calls)
}
/// **The bounded base set: same rows, hard ceiling, re-inflations counted.**
///
/// A budget of one byte is the harshest ceiling the walk can be given: only
/// the base the very next delta reads is held, and every shallower one on
/// the path is dropped and inflated again from the pack. The oids, sizes
/// and delta bases must come out identical to the unbounded pass, the peak
/// must never exceed one base, and the count of re-inflations must be
/// positive — otherwise the ceiling was never hit and the test proved
/// nothing.
///
/// # What "the ceiling can bite here" means, and why the predicate changed
///
/// It used to be "some base has more than one dependent", which was the
/// shape the **fixpoint** evicted on: it held every base from its own entry
/// until its last dependent's, so two live bases needed only two bases.
/// The forest walk holds the *path*, so a second live base needs a path two
/// deep with work still to do above it — a node with at least two children
/// one of which is itself a base. A pack without that shape now genuinely
/// never evicts, and asserting that it does would be asserting the old
/// algorithm.
#[test]
fn a_bounded_base_set_yields_the_same_rows_under_a_hard_ceiling_and_counts_reinflations() {
let mut checked = 0;
for (name, pack) in corpora(4) {
let w = walk(&pack, 20).unwrap();
let mut uses: HashMap<u64, usize> = HashMap::new();
for e in &w.entries {
if let DeltaBase::Offset(o) = e.delta_base {
*uses.entry(o).or_default() += 1;
}
}
let forest = crate::forest::DeltaForest::build(&w).unwrap();
let two_deep = (0..w.entries.len() as u32).any(|i| {
let kids = forest.children(i);
kids.len() > 1 && kids[..kids.len() - 1].iter().any(|c| !forest.children(*c).is_empty())
});
if !uses.values().any(|n| *n > 1) || !two_deep {
continue;
}
let (free, free_report, _) = stream(&pack, ResolveLimits::none());
assert_eq!(free_report.reinflations, 0, "{name}: unbounded must never re-inflate");
assert_eq!(free_report.evictions, 0);
let largest_base = free
.iter()
.filter(|r| uses.contains_key(&r.offset))
.map(|r| r.uncompressed_size)
.max()
.unwrap();
let tight = ResolveLimits { base_budget: 1, ..ResolveLimits::none() };
let (bounded, report, _) = stream(&pack, tight);
assert_eq!(rows_of(&free), rows_of(&bounded), "{name}: the ceiling changed the output");
assert!(report.reinflations > 0, "{name}: no re-inflation — the ceiling never bit");
assert!(report.evictions > 0, "{name}: nothing evicted");
assert!(
report.peak_base_bytes <= largest_base,
"{name}: peak held {} > the largest single base {largest_base} — the ceiling leaked",
report.peak_base_bytes
);
assert!(
free_report.peak_base_bytes >= report.peak_base_bytes,
"{name}: the unbounded pass held less ({}) than the bounded one ({})",
free_report.peak_base_bytes,
report.peak_base_bytes
);
// A generous budget: same rows, fewer re-inflations than the
// harsh one — the eviction is Belady, so more room is never worse.
let mid = ResolveLimits { base_budget: largest_base * 3, ..ResolveLimits::none() };
let (mid_rows, mid_report, _) = stream(&pack, mid);
assert_eq!(rows_of(&free), rows_of(&mid_rows), "{name}: mid budget changed the output");
assert!(
mid_report.reinflations <= report.reinflations,
"{name}: more room, more re-inflations ({} > {})",
mid_report.reinflations,
report.reinflations
);
assert!(mid_report.peak_base_bytes <= largest_base * 3);
eprintln!(
"{name}: {} objects, unbounded peak {} B; budget 1 B → peak {} B, {} evictions, {} re-inflations; budget {} B → {} re-inflations",
free.len(),
free_report.peak_base_bytes,
report.peak_base_bytes,
report.evictions,
report.reinflations,
largest_base * 3,
mid_report.reinflations
);
checked += 1;
}
assert!(
checked > 0,
"no pack in the corpus has a path the ceiling can bite on — nothing was proven"
);
}
/// Rows arrive in batches of the size asked for, the last one partial, and
/// nothing is lost or doubled across the batch boundary.
#[test]
fn rows_are_handed_over_in_batches_and_the_union_is_the_whole_pack() {
let pack = crate::pack_fixture::corpus().pack.clone();
let n = walk(&pack, 20).unwrap().entries.len();
assert!(n > 7);
let (all, report, calls) = stream(&pack, ResolveLimits { row_batch: 7, ..ResolveLimits::none() });
assert_eq!(all.len(), n);
assert_eq!(calls, n.div_ceil(7) as u64, "batches of 7 over {n} rows");
assert_eq!(report.batches, calls);
assert_eq!(report.rows, n as u64);
let (one, _, calls1) = stream(&pack, ResolveLimits { row_batch: usize::MAX, ..ResolveLimits::none() });
assert_eq!(calls1, 1);
assert_eq!(rows_of(&all), rows_of(&one));
let mut oids: Vec<_> = all.iter().map(|r| r.oid.clone()).collect();
oids.sort();
oids.dedup();
assert_eq!(oids.len(), n, "a row was doubled across a batch boundary");
}
/// **The watchdog inside a pack**: with a fake meminfo under the floor the
/// resolver drops every held base, flushes, and waits until the fake says
/// memory is back — then finishes with identical rows.
#[test]
fn the_watchdog_pauses_a_resolve_mid_pack_drops_the_bases_and_the_rows_are_unchanged() {
use std::sync::Arc;
use std::time::Duration;
let dir = crate::store::tests::tmpdir("resolve-watchdog");
let meminfo = dir.join("meminfo");
let write = |avail_kib: u64| {
std::fs::write(
&meminfo,
format!("MemTotal: 16000000 kB\nMemAvailable: {avail_kib} kB\n"),
)
.unwrap()
};
write(1_000_000);
let dog = Arc::new(MemWatchdog::with(&meminfo, 3_200_000 * 1024, Duration::from_millis(5)));
let pack = crate::pack_fixture::corpus().pack.clone();
let (free, _, _) = stream(&pack, ResolveLimits::none());
let m2 = meminfo.clone();
// **Raise only once the pause is actually open.** Sleeping a flat 150 ms
// and hoping the resolver got there first is a race the loaded box
// loses: under a full parallel suite the first checkpoint can land at
// 140 ms, and the assertion below then reads a 10 ms pause. Wait for
// `is_paused`, then hold for the interval the assertion is about.
let d2 = dog.clone();
let raiser = std::thread::spawn(move || {
let deadline = std::time::Instant::now() + Duration::from_secs(30);
while !d2.is_paused() && std::time::Instant::now() < deadline {
std::thread::sleep(Duration::from_millis(2));
}
std::thread::sleep(Duration::from_millis(150));
std::fs::write(&m2, "MemTotal: 16000000 kB\nMemAvailable: 9000000 kB\n").unwrap();
});
let limits = ResolveLimits {
check_every: 3,
watchdog: Some(dog.clone()),
..ResolveLimits::none()
};
let (rows, report, _) = stream(&pack, limits);
raiser.join().unwrap();
assert_eq!(rows_of(&free), rows_of(&rows), "the pause changed the output");
assert_eq!(report.pauses, 1, "one pause: the floor was breached once and the raise ended it");
assert!(report.watchdog_drops >= 1, "the pause must drop the held bases");
assert!(report.paused_ms >= 100, "waited {} ms; must have waited for the raise", report.paused_ms);
assert_eq!(dog.pauses(), 1);
}
/// **A short box loses workers, not the pack.**
///
/// The watchdog says the floor is breached and never un-says it. With one
/// worker that is a pause and then a refusal by name. With four it must
/// first be a *shed*: every worker above the lowest unit in flight gives
/// its core back and waits, the round drains onto one core, and the pack
/// still comes out — byte for byte the same stream a one-worker run makes.
///
/// MEASURED on the rig and this is what it is for: the 16 GB appliance
/// finishes the 8.12 GiB kernel mirror at one worker with 5.55 GiB to
/// spare, and refuses it at 96 % with two and 86 % with four.
#[test]
fn a_short_box_sheds_its_workers_before_it_refuses_the_pack() {
use std::sync::Arc;
use std::time::Duration;
let dir = crate::store::tests::tmpdir("resolve-shed");
let meminfo = dir.join("meminfo");
// Breached from the first checkpoint, and raised only once a worker HAS
// been shed and the last one standing has opened a pause — which is
// the shape the rig measured: the box was short because of the extra
// workers, and giving them back is what makes room.
//
// 🔴 It raised on the first pause alone, and that was a race the test
// lost under load (2026-10-16, dwarf at load 20-30: 1 red in 5 runs of
// the module, never alone): a pause opens only when the lowest unit is
// the ONLY one in flight, so if the other three workers had not been
// scheduled onto a unit yet, the box was raised before any of them
// reached a checkpoint, nothing could ever be shed, and the guard said
// "NOTHING was shed". Shedding while the lowest is paused is legitimate
// (it drained before pausing, so the others may enter and then park),
// so the raise now waits for the shed it is there to prove. The
// watchdog's own 30 s bound is what fails a run that never sheds.
std::fs::write(&meminfo, "MemTotal: 16000000 kB\nMemAvailable: 1000000 kB\n").unwrap();
let pack = crate::pack_fixture::corpus().pack.clone();
let one = tape_of(&pack, 1, false).0;
let dog = Arc::new(
MemWatchdog::with(&meminfo, 3_200_000 * 1024, Duration::from_millis(2))
.bounded(1 << 20, Duration::from_secs(30)),
);
let progress = crate::progress::IndexProgress::detached();
let (m2, d2, p2) = (meminfo.clone(), dog.clone(), progress.clone());
let raiser = std::thread::spawn(move || {
let deadline = std::time::Instant::now() + Duration::from_secs(30);
while !(p2.sheds() > 0 && d2.is_paused()) && std::time::Instant::now() < deadline {
std::thread::sleep(Duration::from_millis(2));
}
std::fs::write(&m2, "MemTotal: 16000000 kB\nMemAvailable: 9000000 kB\n").unwrap();
});
let w = walk(&pack, 20).unwrap();
let tape = Tape::default();
let sink = TapeSink { tape: &tape, only_commits: false };
let limits = ResolveLimits {
workers: 4,
row_batch: 64,
lookahead_bytes: 1 << 16,
check_every: 2,
watchdog: Some(dog.clone()),
progress: Some(&progress),
..ResolveLimits::none()
};
let report = resolve_streaming(
&pack,
&w,
GitHashKind::Sha1,
0,
&NoBases,
&sink,
limits,
&mut |rows| {
tape.put(b'B', &[&(rows.len() as u64).to_le_bytes()]);
for r in rows.iter() {
tape.put(
b'R',
&[
&r.oid,
&r.offset.to_le_bytes(),
&r.len.to_le_bytes(),
&[r.stored_type as u8, r.kind as u8],
&r.uncompressed_size.to_le_bytes(),
&r.delta_base.to_le_bytes(),
],
);
}
rows.clear();
Ok(())
},
);
raiser.join().unwrap();
let report = report.expect("a shed must not refuse the pack");
assert!(
report.shed > 0,
"the box was short from the first checkpoint and NOTHING was shed — the guard \
proved nothing (workers {}, pauses {})",
report.workers,
report.pauses
);
assert_eq!(report.rows, w.entries.len() as u64, "every entry is still a row");
assert!(tape.take() == one, "the shed changed the stream");
}
/// A cancel flag set mid-pack aborts at the next checkpoint with the named
/// error — the pack is not finished and nothing pretends it was.
#[test]
fn a_cancel_aborts_the_pack_at_the_next_checkpoint() {
let cancel = AtomicBool::new(true);
let pack = crate::pack_fixture::corpus().pack.clone();
let w = walk(&pack, 20).unwrap();
let limits = ResolveLimits { check_every: 2, cancel: Some(&cancel), ..ResolveLimits::none() };
let mut got = 0usize;
let err = resolve_streaming(&pack, &w, GitHashKind::Sha1, 0, &NoBases, &NoSink, limits, &mut |rows| {
got += rows.len();
rows.clear();
Ok(())
})
.unwrap_err();
assert!(err.to_string().contains("cancelled"), "{err:#}");
assert!(got < w.entries.len(), "the cancel did not stop the pack ({got} rows)");
}
// ════════════════════════════════════════════════════════════════════════
// THE PARALLEL RESOLVER — one stream out, whatever the worker count
// ════════════════════════════════════════════════════════════════════════
/// **Everything the resolver hands out, as bytes.**
///
/// Not a set and not a sorted digest: the *sequence*, with the sink's calls
/// and the row callback's batches interleaved exactly as they happened. A
/// comparison over sorted rows would pass on any ordering at all, and
/// ordering is the whole thing a worker count could change.
#[derive(Default)]
struct Tape {
bytes: std::sync::Mutex<Vec<u8>>,
}
impl Tape {
fn put(&self, tag: u8, parts: &[&[u8]]) {
let mut b = self.bytes.lock().unwrap_or_else(|e| e.into_inner());
b.push(tag);
for p in parts {
b.extend_from_slice(&(p.len() as u64).to_le_bytes());
b.extend_from_slice(p);
}
}
fn take(&self) -> Vec<u8> {
std::mem::take(&mut self.bytes.lock().unwrap_or_else(|e| e.into_inner()))
}
}
/// A sink that records every call — and, on the second arm, one that says it
/// wants only commits, which is the shipped `ExplodePolicy::Commits` shape.
struct TapeSink<'t> {
tape: &'t Tape,
only_commits: bool,
}
impl crate::exploded::PayloadSink for TapeSink<'_> {
fn explode(&self, oid: &[u8], kind: GitObjectKind, payload: &[u8]) -> Result<()> {
self.tape.put(b'E', &[oid, &[kind as u8], payload]);
Ok(())
}
fn wants(&self, kind: GitObjectKind) -> bool {
!self.only_commits || matches!(kind, GitObjectKind::Commit | GitObjectKind::Tag)
}
}
/// One resolve, recorded. `workers` is the only thing that varies.
fn tape_of(pack: &[u8], workers: usize, only_commits: bool) -> (Vec<u8>, ResolveReport) {
let w = walk(pack, 20).unwrap();
let tape = Tape::default();
let sink = TapeSink { tape: &tape, only_commits };
let limits = ResolveLimits {
workers,
// Small enough that a real pack crosses it many times, so the
// batch boundaries are part of what is being compared.
row_batch: 64,
// …and small enough that the lookahead ceiling is actually reached,
// so the backpressure path is on the tape too.
lookahead_bytes: 1 << 16,
..ResolveLimits::none()
};
let report = resolve_streaming(
pack,
&w,
GitHashKind::Sha1,
0,
&NoBases,
&sink,
limits,
&mut |rows| {
tape.put(b'B', &[&(rows.len() as u64).to_le_bytes()]);
for r in rows.iter() {
tape.put(
b'R',
&[
&r.oid,
&r.offset.to_le_bytes(),
&r.len.to_le_bytes(),
&[r.stored_type as u8, r.kind as u8],
&r.uncompressed_size.to_le_bytes(),
&r.delta_base.to_le_bytes(),
],
);
}
rows.clear();
Ok(())
},
)
.expect("resolve");
(tape.take(), report)
}
/// **The determinism proof.** The same pack, resolved at 1, 2 and 4
/// workers, produces byte-identical output — the same rows, in the same
/// order, in the same batches, with the same sink calls between them.
#[test]
fn the_same_pack_resolves_to_the_same_bytes_at_1_2_and_4_workers() {
let mut proved = 0usize;
for (name, pack) in corpora(4) {
for only_commits in [false, true] {
let (one, r1) = tape_of(&pack, 1, only_commits);
let (two, r2) = tape_of(&pack, 2, only_commits);
let (four, r4) = tape_of(&pack, 4, only_commits);
assert!(!one.is_empty(), "{name}: the tape is empty, so it proves nothing");
assert_eq!(one.len(), two.len(), "{name}: 1 vs 2 workers, tape length");
assert!(one == two, "{name}: 1 vs 2 workers, byte for byte");
assert!(one == four, "{name}: 1 vs 4 workers, byte for byte");
assert_eq!(r1.rows, r2.rows, "{name}");
assert_eq!(r1.rows, r4.rows, "{name}");
assert_eq!(r1.batches, r4.batches, "{name}");
assert_eq!(r1.workers, 1, "{name}");
proved += 1;
}
}
assert!(proved >= 2, "no pack was compared — this guard proved nothing");
}
/// 🔴 **LAW 2: the comparison above can fail.** If the tape were blind to
/// order — a sorted digest, a set of oids, a row count — every one of those
/// assertions would pass on a resolver that emitted its objects in any
/// order at all. So: take the real 4-worker tape, move ONE row later in it,
/// and prove the comparison rejects it.
#[test]
fn the_determinism_tape_rejects_a_stream_whose_order_moved() {
let pack = corpora(2).into_iter().next().expect("a pack").1;
let (good, _) = tape_of(&pack, 4, false);
// Find the two `R` records the tape starts with and swap them. Nothing
// about the *contents* changes; only the order does.
let a = good.iter().position(|b| *b == b'R').expect("a row record");
let rec = 1 + 6 * 8 + 20 + 8 + 8 + 2 + 8 + 8; // tag + 6 lengths + fields
assert!(good.len() > a + 2 * rec, "the tape is too short to reorder");
let mut bad = good.clone();
for i in 0..rec {
bad.swap(a + i, a + rec + i);
}
assert_ne!(good, bad, "the two rows were identical — swapping them proved nothing");
assert!(good != bad, "an order-blind comparison would have called these equal");
}
/// A sink that answers `wants = false` is **not called** for that kind, and
/// the resolver still produces every row. This is what keeps the ordered
/// hand-over from buffering 90 % of a pack's bytes.
#[test]
fn a_sink_that_wants_nothing_is_never_handed_a_payload() {
for (name, pack) in corpora(3) {
let w = walk(&pack, 20).unwrap();
let tape = Tape::default();
let sink = TapeSink { tape: &tape, only_commits: true };
let mut rows = 0u64;
let report = resolve_streaming(
&pack,
&w,
GitHashKind::Sha1,
0,
&NoBases,
&sink,
ResolveLimits { workers: 4, ..ResolveLimits::none() },
&mut |r| {
rows += r.len() as u64;
r.clear();
Ok(())
},
)
.expect("resolve");
assert_eq!(rows, w.entries.len() as u64, "{name}: every entry is a row");
assert_eq!(report.rows, rows, "{name}");
let calls = tape
.take()
.chunks(1)
.filter(|c| c[0] == b'E')
.count();
// Every explode the sink DID get is a commit or a tag; and a pack
// with any blob or tree at all must have been spared some.
let non_commit = w
.entries
.iter()
.filter(|e| matches!(e.obj_type, ObjType::Blob | ObjType::Tree))
.count();
if non_commit > 0 {
assert!(
calls < w.entries.len(),
"{name}: the sink was handed all {} objects although it wanted only commits",
w.entries.len()
);
}
}
}
/// **A pack whose delta shape is CHOSEN, not found.** `roots` independent
/// whole blobs, each the root of a binary tree of `depth` levels of
/// `OFS_DELTA`s, every object exactly `body_bytes` long.
///
/// The shape is the whole point of the guard below: `roots` roots is what
/// gives the gatling fan-out `roots` independent units to hand four workers
/// (`run_round` takes `min(workers, roots)`), the branching is what keeps a
/// frame live while a deeper subtree runs — a base whose last child has not
/// been reached yet is held — and one uniform object size is what makes
/// "the largest single base" a number this source states rather than one a
/// found pack happens to have.
fn base_ceiling_pack(roots: usize, depth: u32, body_bytes: usize) -> Vec<u8> {
use crate::pack_fixture::{build_pack, Item};
// splitmix64, four lines, so the pack is byte-identical on every box:
// incompressible bodies, so the pack's shape is the constants above and
// not deflate's opinion of them.
let mut state = 0x5eed_0000_0000_0001u64;
let mut body = |n: usize| -> Vec<u8> {
let mut v = Vec::with_capacity(n + 8);
while v.len() < n {
state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
v.extend_from_slice(&(z ^ (z >> 31)).to_le_bytes());
}
v.truncate(n);
v
};
let mut items: Vec<Item> = Vec::new();
for _ in 0..roots {
let mut level = vec![items.len()];
items.push(Item::Whole(GitObjectKind::Blob, body(body_bytes)));
for _ in 1..depth {
let mut next = Vec::with_capacity(level.len() * 2);
for base in level {
for _ in 0..2 {
next.push(items.len());
items.push(Item::OfsDelta { base, body: body(body_bytes) });
}
}
level = next;
}
}
build_pack(&items)
}
/// **N workers get N walks, not N budgets.** The held-base ceiling is one
/// atomic across every worker ([`workers_from_env`]'s doc says so in as many
/// words: *"it is not N base budgets either"*), so four workers on the same
/// pack hold what one budget allows plus what the walk structurally cannot
/// drop — and nowhere near the four budgets a per-thread ceiling would give
/// them.
///
/// # 🔴 The two defects this replaces, both measured 2026-09-08
///
/// It read `corpora(4)`, i.e. **whatever `.pack` files sat under
/// `~/git` in `read_dir` order**, and asserted
/// `peak <= budget + biggest` with
///
/// ```text
/// let biggest = w.entries.iter().map(|e| e.uncompressed_size).max()
/// ```
///
/// ```text
/// ~/git/Njord/.git/objects/pack/pack-7edf01cd….pack:
/// arm 1 held 267014 bytes against a 65536 budget and a 176423-byte largest object
/// ```
///
/// * **`biggest` was not the largest base.** `PackEntry::uncompressed_size`
/// is the size field of the *pack entry*, and for an `OFS_DELTA` that is
/// the length of the **delta stream**, not of the object it reconstructs.
/// The peak is a sum of *resolved base payloads*, so the old assertion
/// compared a peak in one unit against a maximum in another and was
/// simply not about the same bytes. The sibling guard
/// [`a_bounded_base_set_costs_re_inflations_not_rows`] already had this
/// right: it takes the maximum over the **resolved rows** whose offset is
/// used as a base, and that is what this one takes now.
/// * **One base per worker, not one per pack.** `enforce_budget` never
/// drops a worker's *deepest* frame — it is the base the very next child
/// reads, and dropping it would re-inflate it on the following line — so
/// the floor under the ceiling is one held base **per walk**, and there
/// are `workers` walks. `budget + 1 × largest` was the serial arm's bound
/// applied to a four-worker arm. The bound that is actually promised is
/// `budget + workers × largest`: the shared ceiling, plus at most one
/// undroppable base per worker (which also absorbs the only race there
/// is — `live_path` is a relaxed atomic, so the peak one worker records
/// may include another worker's push that has not reached its own
/// `enforce_budget` yet).
///
/// Neither correction weakens the guard, because the guard's *point* is the
/// last assertion: `budget + workers × largest` is far below `workers ×
/// budget`, which is what a per-thread ceiling would have allowed. The
/// external corpus is gone with them — a test that needs another checkout
/// on the same disk is not a test, and the pack is built here instead, sized
/// so the ceiling demonstrably bites (`evictions > 0`, and the unbounded
/// pass holds more than the bounded one).
#[test]
fn four_workers_hold_no_more_bases_than_the_one_budget_allows() {
const ROOTS: usize = 4;
const DEPTH: u32 = 8;
const OBJECT: usize = 4 * 1024;
// 4 roots × (2^8 − 1) = 1020 objects of 4 KiB. One walk holds at most
// the seven bases above a leaf, so it wants 28 KiB and four walks want
// 112 KiB — while the budget is 20 KiB: more than `workers × largest`
// (16 KiB, so what binds is the ceiling and not the floor the walk
// cannot drop) and less than even ONE walk wants (so it binds on the
// serial arm too, and that arm is not a free pass).
const BUDGET: u64 = 20 * 1024;
let pack = base_ceiling_pack(ROOTS, DEPTH, OBJECT);
let w = walk(&pack, 20).unwrap();
// Which offsets are used as a base, so "the largest base" is a maximum
// over the objects the ceiling actually holds — resolved sizes, off the
// rows, not pack-entry size fields.
let mut is_base: std::collections::HashSet<u64> = std::collections::HashSet::new();
for e in &w.entries {
if let DeltaBase::Offset(o) = e.delta_base {
is_base.insert(o);
}
}
let mut four_worker_peak = 0u64;
for workers in [1usize, 4] {
// The unbounded pass **at the same worker count**, because that is
// the only thing the bounded one is comparable with: N walks hold N
// paths whether or not there is a ceiling, so a one-worker baseline
// would make the four-worker arm look like a leak.
let free_limits = ResolveLimits { workers, ..ResolveLimits::none() };
let (free, free_report, _) = stream(&pack, free_limits);
assert_eq!(free_report.evictions, 0, "{workers} workers: the unbounded pass evicted");
let largest = free
.iter()
.filter(|r| is_base.contains(&r.offset))
.map(|r| r.uncompressed_size)
.max()
.expect("the pack has bases");
assert_eq!(largest, OBJECT as u64, "every object in this pack is one size");
let limits = ResolveLimits { workers, base_budget: BUDGET, ..ResolveLimits::none() };
let mut rows = Vec::new();
let report = resolve_streaming(
&pack,
&w,
GitHashKind::Sha1,
0,
&NoBases,
&NoSink,
limits,
&mut |r| {
rows.extend(r.drain(..));
Ok(())
},
)
.expect("resolve");
assert_eq!(report.workers as usize, workers, "the fan-out took the worker count");
assert_eq!(
rows_of(&free),
rows_of(&rows),
"{workers} workers: the ceiling changed the output"
);
assert!(
report.evictions > 0,
"{workers} workers: nothing was evicted, so the ceiling never bit and this \
guard proves nothing"
);
assert!(
free_report.peak_base_bytes > report.peak_base_bytes,
"{workers} workers: unbounded held {} and bounded {} — the ceiling did nothing",
free_report.peak_base_bytes,
report.peak_base_bytes
);
let allowed = BUDGET + workers as u64 * largest;
assert!(
report.peak_base_bytes <= allowed,
"{workers} workers: held {} bytes against a {BUDGET}-byte budget plus {workers} × \
the {largest}-byte largest base = {allowed}",
report.peak_base_bytes
);
if workers == 4 {
four_worker_peak = report.peak_base_bytes;
// The whole claim, stated as the number a PER-THREAD ceiling
// would have produced: four walks each allowed the budget plus
// their own undroppable base.
let per_thread = workers as u64 * (BUDGET + largest);
assert!(
four_worker_peak < per_thread,
"four workers held {four_worker_peak} bytes, which is four ceilings of \
{BUDGET} + {largest} = {per_thread}: the budget is per thread, not per pack"
);
}
eprintln!(
"{workers} worker(s): peak {} B (unbounded {} B), budget {BUDGET} B, largest base \
{largest} B, {} evictions, {} re-inflations",
report.peak_base_bytes,
free_report.peak_base_bytes,
report.evictions,
report.reinflations
);
}
}
/// **The chain memo answers the same bytes as the chain, and a hit walks
/// nothing.** A whole tree, a delta on it and a delta on that: read the
/// deepest one through a memo twice. The second read is a hit at its own
/// offset (depth 0), and reading the middle one afterwards is a hit too —
/// every link applied on the way down was put in the memo. The bytes are
/// the uncached answer's, byte for byte.
#[test]
fn a_chain_memo_answers_the_chain_and_a_hit_walks_nothing() {
use crate::pack_fixture::{Item, build_pack};
let base = b"100644 a\0".iter().copied().chain([7u8; 20]).collect::<Vec<u8>>();
let mut mid = base.clone();
mid.extend_from_slice(b"100644 b\0");
mid.extend_from_slice(&[9u8; 20]);
let mut top = mid.clone();
top.extend_from_slice(b"100644 c\0");
top.extend_from_slice(&[11u8; 20]);
let pack = build_pack(&[
Item::Whole(GitObjectKind::Tree, base.clone()),
Item::OfsDelta { base: 0, body: mid.clone() },
Item::OfsDelta { base: 1, body: top.clone() },
]);
let w = crate::pack_walk::walk(&pack, 20).unwrap();
let archive = SliceArchive(&pack);
let none = |_: &[u8]| None;
let top_at = w.entries[2].offset;
let mid_at = w.entries[1].offset;
let (k0, plain, cost0) = materialize_at(&archive, top_at, 20, &none, &NoBases).unwrap();
assert_eq!((k0, plain.as_slice(), cost0.depth), (GitObjectKind::Tree, top.as_slice(), 2));
let mut memo = ChainCache::new(1 << 20);
let (k1, first, cost1) =
materialize_at_with(&archive, top_at, 20, &none, &NoBases, Some(&mut memo)).unwrap();
assert_eq!((k1, first.as_slice(), cost1.depth), (GitObjectKind::Tree, top.as_slice(), 2), "a cold memo is the chain");
let (k2, again, cost2) =
materialize_at_with(&archive, top_at, 20, &none, &NoBases, Some(&mut memo)).unwrap();
assert_eq!((k2, again.as_slice()), (GitObjectKind::Tree, top.as_slice()));
assert_eq!(cost2.depth, 0, "a hit at the asked offset walks no link");
let (k3, middle, cost3) =
materialize_at_with(&archive, mid_at, 20, &none, &NoBases, Some(&mut memo)).unwrap();
assert_eq!((k3, middle.as_slice(), cost3.depth), (GitObjectKind::Tree, mid.as_slice(), 0), "every link on the way down was memoised");
let (hits, misses) = memo.stats();
assert_eq!((hits, misses), (2, 3), "first read: 3 misses (top, mid, base); then 2 hits");
assert!(memo.bytes() == base.len() + mid.len() + top.len(), "three payloads held");
// Bounded: a memo too small for the base holds nothing of it and still
// answers the same bytes.
let mut tiny = ChainCache::new(mid.len());
let (_, b1, _) = materialize_at_with(&archive, top_at, 20, &none, &NoBases, Some(&mut tiny)).unwrap();
let (_, b2, _) = materialize_at_with(&archive, top_at, 20, &none, &NoBases, Some(&mut tiny)).unwrap();
assert_eq!((b1.as_slice(), b2.as_slice()), (top.as_slice(), top.as_slice()));
assert!(tiny.bytes() <= mid.len(), "never over its cap");
}
}