crates/gunnar-wire/tests/connectivity_cost.rs
//! What a push costs the object store.
//!
//! `verify_connectivity`'s doc comment promised `O(newly pushed history)`. The
//! code walked the **full object closure of every pre-existing reference**
//! first, so a one-commit push onto an N-commit branch read every commit, tree
//! and blob in the repository. The claim and the code differed by the size of
//! the repository.
//!
//! # Why this test counts reads rather than timing anything
//!
//! A wall clock passes on a small fixture no matter what the complexity is, and
//! a single-N bound passes on anything if the bound is generous. So the
//! assertion here is **`cost(small N) == cost(large N)`**, exactly: a walk that
//! is linear in the repository cannot produce the same number twice, and a
//! stubbed-out check cannot produce a number greater than zero. Both halves are
//! asserted.
mod common;
use std::sync::Arc;
// The counting store lives in `common` because `negotiate_cost.rs` needs the
// same one (one implementation): two copies of a measuring instrument can drift, and a
// measuring instrument that drifts silently is worse than none.
use common::{validating_ingest, Counting, Fixture};
use gix_hash::Kind;
use gunnar_wire::receive_pack::AllowAll;
use gunnar_wire::{ReceivePack, RefStatus};
/// Push `pushed` commits onto a branch that already carries `history` commits,
/// and report how many objects the server had to touch to accept them.
fn touches_for_a_push(history: usize, pushed: usize) -> usize {
let fixture = Fixture::build(Kind::Sha1);
// A long, pre-existing branch. `refs/heads/main` is moved to its tip, so
// every one of these commits is reachable from a reference before the push
// and none of them is part of it.
let base = fixture.extend(fixture.four, history, "history");
fixture.force_ref("refs/heads/main", base);
// The push itself: `pushed` new commits, each with one new tree and one new
// blob.
let pushed = fixture.extend(base, pushed, "pushed");
let counting = Arc::new(Counting::new(fixture.git.inner.clone()));
counting.reset();
let receive = ReceivePack::new(counting.as_ref(), fixture.kind);
let input = push_bytes(
&base.to_string(),
&pushed.to_string(),
"refs/heads/main",
&gunnar_pack::empty_pack(Kind::Sha1).expect("an empty pack is legal"),
);
let mut input = std::io::Cursor::new(input);
let mut out = Vec::new();
let outcome = receive
.serve(
&mut input,
&mut out,
&validating_ingest::<gunnar_wire::Error>(Kind::Sha1),
&AllowAll,
)
.expect("serve the push")
.expect("a push was made");
// The push must actually have been accepted. A connectivity check that
// rejects everything is very cheap and completely useless.
assert_eq!(
outcome.statuses,
vec![RefStatus::Ok],
"the push was refused, so the cost measured is the cost of refusing it"
);
assert_eq!(
fixture.read_ref("refs/heads/main"),
Some(pushed),
"the reference did not move, so nothing was really accepted"
);
counting.touches()
}
fn push_bytes(old: &str, new: &str, ref_name: &str, pack: &[u8]) -> Vec<u8> {
let mut out = Vec::new();
let mut line = format!("{old} {new} {ref_name}").into_bytes();
line.push(0);
line.extend_from_slice(b"report-status object-format=sha1 agent=test/1");
gunnar_pktline::write_text(&mut out, &line).unwrap();
gunnar_pktline::write_flush(&mut out).unwrap();
out.extend_from_slice(pack);
out
}
/// Mirror-push `refs_pushed` references into a repository that holds **no
/// references at all**, and report how many objects the server touched.
///
/// This is the second axis, and the one the earlier fix never covered. That fix made a
/// single push cheap in the *history* behind it; the frontier it introduced is
/// built once for the whole push, and the comment says so. But the walk it
/// feeds was still run **once per reference command**, each with its own
/// `seen` set, so a push carrying N references over one shared line of history
/// paid for that history N times over.
///
/// A mirror push is exactly that shape and it is not an exotic one: it is what
/// `git push --mirror` and every forge import does, and `linux.git` does it
/// with 2 872 references over one history.
///
/// The references here are the newest `refs_pushed` commits of one chain, so
/// every one of them is an **ancestor of the newest**: the union of their
/// closures IS the closure of the newest, and a walk that shares its work
/// across the batch has essentially nothing extra to do for the other N−1.
fn touches_for_a_mirror_push(history: usize, refs_pushed: usize) -> usize {
let fixture = Fixture::build(Kind::Sha1);
let tip = fixture.extend(fixture.four, history, "history");
let tips = fixture.first_parent_haves(tip, refs_pushed);
assert_eq!(
tips.len(),
refs_pushed,
"the fixture is shorter than the push being measured"
);
// The receiving side holds the objects and **no references**, which is what
// a mirror push into a fresh repository is. An empty frontier is also the
// case with nothing to stop the commit walk, so this measures the walk
// rather than the frontier.
//
// It used to be a second, empty `MemRefStore` beside the shared object
// store. There is one store now (`GitServe`), so the same state is reached
// by emptying the namespace instead of by declining to share it — the
// objects stay, every name goes.
fixture.clear_refs();
let counting = Arc::new(Counting::new(fixture.git.inner.clone()));
counting.reset();
let receive = ReceivePack::new(counting.as_ref(), fixture.kind);
let mut input = Vec::new();
for (index, id) in tips.iter().enumerate() {
let mut line =
format!("{} {id} refs/heads/mirror-{index}", Kind::Sha1.null(),).into_bytes();
if index == 0 {
line.push(0);
line.extend_from_slice(b"report-status object-format=sha1 agent=test/1");
}
gunnar_pktline::write_text(&mut input, &line).unwrap();
}
gunnar_pktline::write_flush(&mut input).unwrap();
input.extend_from_slice(&gunnar_pack::empty_pack(Kind::Sha1).expect("an empty pack is legal"));
let mut input = std::io::Cursor::new(input);
let mut out = Vec::new();
let outcome = receive
.serve(
&mut input,
&mut out,
&validating_ingest::<gunnar_wire::Error>(Kind::Sha1),
&AllowAll,
)
.expect("serve the mirror push")
.expect("a push was made");
// Every reference must have landed. A connectivity check that rejects is
// cheap and useless, and so is one that never ran.
assert_eq!(
outcome.statuses,
vec![RefStatus::Ok; refs_pushed],
"the mirror push was refused, so the cost measured is the cost of refusing it"
);
for (index, id) in tips.iter().enumerate() {
assert_eq!(
fixture.read_ref(&format!("refs/heads/mirror-{index}")),
Some(*id),
"refs/heads/mirror-{index} did not land, so nothing was really accepted"
);
}
counting.touches()
}
#[test]
fn a_mirror_push_walks_the_shared_history_once_and_not_once_per_reference() {
const HISTORY: usize = 200;
let one = touches_for_a_mirror_push(HISTORY, 1);
let many = touches_for_a_mirror_push(HISTORY, 64);
assert!(
one > HISTORY,
"pushing one reference over {HISTORY} commits touched only {one} objects, so the \
connectivity walk did not happen and every ratio below is a ratio of nothing"
);
// Peeling each extra tip is one read, and the commit walk tests each tip
// against the frontier. Three per reference is generous for that and still
// an order of magnitude under one re-walk.
let allowance = one + 3 * 63;
assert!(
many <= allowance,
"a mirror push of 64 references over one shared {HISTORY}-commit history touched \
{many} objects where pushing the newest reference alone touched {one} — the \
connectivity walk is run once per reference command instead of once per push, so \
it costs O(references x history). Budget was {allowance}; the ratio is {:.1}x.",
many as f64 / one as f64
);
}
#[test]
fn a_one_commit_push_costs_the_same_on_a_long_branch_as_on_a_short_one() {
let small = touches_for_a_push(8, 1);
let large = touches_for_a_push(400, 1);
assert!(
small > 0,
"no object was touched at all, so nothing was verified"
);
assert_eq!(
small, large,
"accepting one commit cost {small} object touches against 8 commits of history \
and {large} against 400 — the connectivity walk is a function of the repository, \
not of the push"
);
}
/// The non-vacuity half of the test above, and it is **not** the `small > 0`
/// line in it.
///
/// That line was the intended one, and it is blind: `touches` also counts
/// `Frontier::new`, which peels the references the repository already had
/// before any walk happens. PROVEN 2026-08-05 by returning `Ok(0)` from
/// `verify_connectivity` before it reads anything — the connectivity check
/// gone entirely, and `a_one_commit_push_costs_the_same_on_a_long_branch_as_on_a_short_one`
/// stayed **green**: the frontier still cost something, so `small > 0` held,
/// and the frontier is one reference either way, so `small == large` held too.
/// A guard against an `O(repository)` walk that cannot tell the walk from no
/// walk at all.
///
/// What can only be true if the pushed objects are really being read: the cost
/// has to grow with the size of the **push**. Twenty commits carry twenty
/// commits, twenty trees and twenty blobs more than one does, and a check that
/// is not looking at them cannot charge for them.
#[test]
fn the_cost_of_a_push_grows_with_the_push_even_though_it_does_not_grow_with_the_repository() {
const HISTORY: usize = 8;
let one = touches_for_a_push(HISTORY, 1);
let twenty = touches_for_a_push(HISTORY, 20);
// 19 further commits, each with a distinct tree and a distinct blob: 57
// objects that only exist in the larger push. Asserting a strict floor
// rather than an exact figure, because how many times the walk touches one
// object is the walk's business; that it touches them at all is not.
assert!(
twenty >= one + 57,
"pushing 20 commits cost {twenty} object touches and pushing 1 cost {one} — a \
difference of {}, where the 19 extra commits carry 57 objects between them. The \
connectivity walk is not reading what is being pushed.",
twenty as i64 - one as i64
);
}
// ───────────────────────────────────────────────────────────────────────────
// 🔴 The serial closure walk, in `cargo test`
// ───────────────────────────────────────────────────────────────────────────
/// Push `pushed` commits onto `history`, and report **(commit reads, commits
/// in the walk)** for the connectivity check alone.
fn commit_reads_for_a_push(history: usize, pushed: usize) -> (usize, usize) {
let fixture = Fixture::build(Kind::Sha1);
let base = fixture.extend(fixture.four, history, "history");
fixture.force_ref("refs/heads/main", base);
let tip = fixture.extend(base, pushed, "pushed");
let counting = Arc::new(Counting::new(fixture.git.inner.clone()));
counting.reset();
let receive = ReceivePack::new(counting.as_ref(), fixture.kind);
let input = push_bytes(
&base.to_string(),
&tip.to_string(),
"refs/heads/main",
&gunnar_pack::empty_pack(Kind::Sha1).expect("an empty pack is legal"),
);
let mut input = std::io::Cursor::new(input);
let mut out = Vec::new();
let outcome = receive
.serve(
&mut input,
&mut out,
&validating_ingest::<gunnar_wire::Error>(Kind::Sha1),
&AllowAll,
)
.expect("serve the push")
.expect("a push was made");
assert_eq!(
outcome.statuses,
vec![RefStatus::Ok],
"the push was refused, so the cost measured is the cost of refusing it"
);
(counting.commit_read_count(), pushed)
}
/// **`commit_reads_per_commit` must be 1.000, asserted as an exact integer
/// slope rather than as a ratio.**
///
/// Every commit in the repository used to be read and decoded **twice** — once
/// for its parents and once for the root tree the first decode had already
/// parsed and thrown away. Removing that is the walk's one landed win: 1.295x on
/// `walk_1m`, 1.025x on `clone_large`, instructions retired. `Graph::load`'s
/// doc comment says *"it must read 1.000, never 2.000"* and names
/// `nornir-bench` as the guard.
///
/// A benchmark is the wrong place for that guard to live alone. It is a
/// separate target, it needs a million-commit fixture, and on 2026-08-10 it did
/// not build — so the only thing standing between the tree and a silent return
/// to 2.000 was a comment. This is the same number on a fixture `cargo test`
/// can afford.
///
/// # Why a slope and not `reads == pushed`
///
/// The first draft asserted the absolute equality and went red at **8 reads
/// for 1 pushed commit**. The seven extra are not the walk decoding anything
/// twice: they are `Frontier::new` peeling the two references the fixture holds
/// besides the one being pushed to, and they are the *same seven* whether the
/// branch behind the push is 8 commits long or 32 — measured, both. That
/// constant is the frontier's own subject and the three tests above are what hold it.
///
/// What the walk owns is the **marginal** cost, and a slope states it without
/// borrowing anything from the frontier: nineteen more commits in the push must
/// cost nineteen more commit reads. At two decodes per commit it costs
/// thirty-eight.
///
/// The connectivity walk is used rather than a clone because it is the **walk
/// on its own**: a clone would also read every commit a second time to copy it
/// into the pack, and a ratio of 2.000 that is *correct* cannot guard a ratio
/// of 2.000 that is not.
#[test]
fn the_connectivity_walk_reads_each_pushed_commit_exactly_once() {
const HISTORY: usize = 8;
let (one, _) = commit_reads_for_a_push(HISTORY, 1);
for pushed in [2usize, 20, 37] {
let (reads, commits) = commit_reads_for_a_push(HISTORY, pushed);
let marginal = reads as i64 - one as i64;
let extra = commits as i64 - 1;
assert_eq!(
marginal,
extra,
"{commits} pushed commits cost {reads} commit reads and 1 cost {one}: \
commit_reads_per_commit = {:.3} at the margin, and the walk requires 1.000. \
Two reads per commit is the regression this exists to catch — see \
`Graph::load`'s doc comment.",
marginal as f64 / extra as f64
);
}
}
/// The non-vacuity half. A slope of one is also what a counter stuck at a
/// constant would produce if the constant happened to move with the push for
/// some other reason, and a slope of one over *zero* reads is vacuous outright.
///
/// So: the walk must read **at least** every commit it was handed. That is the
/// floor the walk sits on — one read per commit is only a win if one read is
/// enough — and it is the half that fails if the connectivity check is stubbed
/// out, which is exactly how the `small > 0` guard above was proven blind on
/// 2026-08-05.
#[test]
fn the_commit_read_counter_is_not_stuck() {
let (few, _) = commit_reads_for_a_push(8, 1);
let (many, _) = commit_reads_for_a_push(8, 20);
assert!(
few >= 1,
"no commit was read at all, so the slope above is empty"
);
assert!(
many >= 20,
"the walk read {many} commits for a push of 20: it is not reading what it was given"
);
}