crates/gunnar-wire/tests/negotiate_cost.rs
//! What **one negotiation round** costs the object store.
//!
//! A protocol-v2 client re-sends its whole `have` list on every
//! `command=fetch`, so round *n* carries the `have`s of rounds 1..n. If the
//! server answers each round from scratch, the cost of a round grows with the
//! round number and a negotiation costs `O(rounds²)` store work. Nothing about
//! that is visible in a three-round test, or in a wall clock on a small
//! fixture, which is why it survived until a 20 000-commit bench arm measured
//! **154 seconds** for one divergent fetch.
//!
//! # The shape of these assertions, and why it is not a bound
//!
//! Every test here asserts **`cost(round 5) == cost(round 20)`, exactly**, on a
//! fixture built so that the honest per-round cost really is constant. A single
//! generous bound (`< 10_000`) passes on anything, and a wall clock passes on
//! everything at this size. A round whose cost is a function of how many
//! rounds came before it cannot produce the same number twice.
//!
//! And the other half, which matters just as much: **a floor is asserted
//! separately**. A negotiation that stopped touching the store altogether would
//! satisfy `equal(5, 20)` perfectly, report zero, and look exactly like a fix.
//! That is the `commits_visited = 0` trap the `negotiate_divergent` bench arm
//! carries its own red switch for, in test form.
//!
//! The floor is `>= WINDOW`, **not `> 0`**, and that distinction was earned the
//! hard way: `> 0` passed against a deliberately broken memo that answered
//! every miss "absent" without asking the store at all, because `fetch` probes
//! the *want* once per round and that single unrelated probe was enough to
//! clear it. A floor a guard can reach without doing the work under test is not
//! a guard. `>= WINDOW` says every newly offered `have` was actually resolved.
mod common;
use common::{Counting, Fixture};
use gix_hash::{Kind, ObjectId};
use gunnar_wire::{FetchRequest, UploadPack};
/// Commits offered per round. git's own v2 client starts at 16 and doubles;
/// a fixed window is what makes "round 5 versus round 20" a clean comparison.
const WINDOW: usize = 20;
const ROUNDS: usize = 20;
/// Drive `ROUNDS` cumulative negotiation rounds against **one** `UploadPack`,
/// returning what each round cost the store.
///
/// One `UploadPack` because that is what a connection is: `gunnar-cli`'s
/// transport builds exactly one per `git-upload-pack` invocation
/// (`server/transport.rs`), and the whole question here is what the second
/// round costs given the first.
fn cost_per_round(
store: &Counting,
kind: Kind,
want: ObjectId,
haves: &[ObjectId],
measure: fn(&Counting) -> usize,
) -> (Vec<usize>, Vec<bool>) {
let upload = UploadPack::new(store, kind);
let mut costs = Vec::new();
let mut readies = Vec::new();
for round in 1..=ROUNDS {
let offered = (round * WINDOW).min(haves.len());
let request = FetchRequest {
wants: vec![want],
haves: haves[..offered].to_vec(),
done: false,
..Default::default()
};
store.reset();
let mut out = Vec::new();
let outcome = upload.fetch(&request, &mut out).expect("a fetch round");
costs.push(measure(store));
readies.push(outcome.ready);
}
(costs, readies)
}
/// A `have` the server has already answered "no" about is not asked about
/// again.
///
/// The client's whole branch is foreign (a separate repository's commits), so
/// every `have` is absent and the answer for each is settled the first time it
/// is seen. Before the fix the server re-probed the entire accumulated list every
/// round: round 20 cost twenty times round 1 for twenty times nothing.
#[test]
fn an_absent_have_is_probed_once_per_connection_not_once_per_round() {
let fixture = Fixture::build(Kind::Sha1);
// A different repository entirely. Its commits exist nowhere in `fixture`.
let theirs = Fixture::build(Kind::Sha1);
let tip = theirs.extend(theirs.four, WINDOW * ROUNDS, "mine");
let haves = theirs.first_parent_haves(tip, WINDOW * ROUNDS);
assert_eq!(
haves.len(),
WINDOW * ROUNDS,
"the fixture is the wrong size"
);
let store = Counting::new(fixture.git.inner.clone());
let (costs, readies) = cost_per_round(
&store,
fixture.kind,
fixture.four,
&haves,
Counting::contains_count,
);
// Not one `have` was common, so the server can never be ready. If it is,
// the negotiation ended early and the later rounds never happened.
assert!(
readies.iter().all(|ready| !ready),
"a fetch declared itself ready against a client that shares nothing: {readies:?}"
);
assert!(
costs[4] >= WINDOW,
"round 5 probed the store {} times for {WINDOW} newly offered `have`s — \
fewer probes than new `have`s means they were not resolved at all, and \
a constant cost that comes from doing nothing is not a fix. \
Per-round costs: {costs:?}",
costs[4]
);
assert_eq!(
costs[4], costs[19],
"round 20 cost the store {} probes and round 5 cost {} — a round is \
paying for the rounds before it, which is O(rounds²) over a \
negotiation. Per-round costs: {costs:?}",
costs[19], costs[4]
);
}
/// The `have` date bound is not re-derived from every common `have` every
/// round.
///
/// The reachability walk is bounded by the oldest `have`'s committer date. The
/// server used to compute that by **re-reading every common commit from the
/// store on every round**, which is the same `O(rounds²)` shape one layer down,
/// and it is invisible to the test above, because it is reads rather than
/// probes.
///
/// The fixture is built so the walk itself costs the same every round: the
/// offered branch is dated far *newer* than `refs/heads/main`, so the cutoff is
/// constant and the walk from the want stops on its very first commit. What is
/// left growing, if anything grows, is the cutoff derivation.
#[test]
fn the_have_date_bound_is_not_re_derived_from_every_common_have_every_round() {
let fixture = Fixture::build(Kind::Sha1);
// Present in the store, and uniformly newer than everything on `main`.
// A constant date is the point: an ascending one would move the cutoff
// every round and make the walk's cost grow for an honest reason, which
// would mask the dishonest one.
let tip = fixture.extend_dated(fixture.one, WINDOW * ROUNDS, "aside", |_| 1_700_000_500);
let haves = fixture.first_parent_haves(tip, WINDOW * ROUNDS);
assert_eq!(
haves.len(),
WINDOW * ROUNDS,
"the fixture is the wrong size"
);
fixture.force_ref("refs/heads/main", fixture.four);
let store = Counting::new(fixture.git.inner.clone());
let (costs, readies) = cost_per_round(
&store,
fixture.kind,
fixture.four,
&haves,
Counting::read_count,
);
// Every `have` IS common here (that is what makes the cutoff loop run at
// all), but none of them is an ancestor of the want, so no cut point
// exists and the negotiation keeps going. If this ever flips to `ready`
// the later rounds stop happening and the comparison is meaningless.
assert!(
readies.iter().all(|ready| !ready),
"the server found a cut point it should not have: {readies:?}"
);
assert!(
costs[4] >= WINDOW,
"round 5 read {} objects for {WINDOW} newly offered common `have`s — \
fewer reads than new `have`s means their dates were never looked up, \
so the constant cost below is the cost of doing nothing. \
Per-round costs: {costs:?}",
costs[4]
);
assert_eq!(
costs[4], costs[19],
"round 20 read {} objects and round 5 read {} — the oldest-`have` date \
bound is being re-derived from the whole accumulated `have` list every \
round. Per-round costs: {costs:?}",
costs[19], costs[4]
);
}
/// Remembering across rounds must not change a single answer.
///
/// The speed-up above is a **cache of facts about the object store**, not
/// negotiation state, so a warm one must decide exactly what a cold one
/// decides. This drives the same divergent negotiation twice and compares
/// every round's answer: once on a reused `UploadPack`, which is what a
/// connection does, and once on a fresh `UploadPack` per round, which is a
/// cache that never gets warm.
///
/// The fixture is genuinely divergent and ends in a real cut point, so the
/// comparison covers `NAK` rounds, the `ready` round and the packfile it
/// carries. A run where nothing ever became common would compare two identical
/// piles of nothing.
/// **Un-ignored 2026-08-10.** It was skipped because "MemStore cannot emit a
/// pack", and that stopped being true: `MemGitServe::emit_pack` is a genuine
/// pack copy, checked against `gunnar_pack::index_pack` as an outside oracle in
/// `gunnar-store`'s own conformance suite. The negotiation this drives now
/// reaches the served pack it always needed, so the `ready` round and its
/// bytes are compared rather than skipped.
#[test]
fn a_warm_have_memo_answers_exactly_as_a_cold_one() {
let fixture = Fixture::build(Kind::Sha1);
let server_tip = fixture.extend(fixture.four, 40, "theirs");
fixture.force_ref("refs/heads/main", server_tip);
let theirs = Fixture::build(Kind::Sha1);
let their_tip = theirs.extend(theirs.four, 40, "mine");
let mut haves = theirs.first_parent_haves(their_tip, 40);
// ...and then, last, the commit both sides share. Without it nothing is
// ever common and this test compares two negotiations that did nothing.
haves.push(fixture.four);
let warm = UploadPack::new(&fixture.git, fixture.kind);
let mut saw_ready = false;
let mut saw_nak = false;
for offered in 1..=haves.len() {
let request = FetchRequest {
wants: vec![server_tip],
haves: haves[..offered].to_vec(),
done: false,
..Default::default()
};
let mut warm_out = Vec::new();
let warm_outcome = warm.fetch(&request, &mut warm_out).expect("a warm round");
let cold = UploadPack::new(&fixture.git, fixture.kind);
let mut cold_out = Vec::new();
let cold_outcome = cold.fetch(&request, &mut cold_out).expect("a cold round");
assert_eq!(
warm_outcome.common, cold_outcome.common,
"after {offered} have(s) a warm memo reported different common commits"
);
assert_eq!(
(
warm_outcome.ready,
warm_outcome.sent_pack,
warm_outcome.objects_sent
),
(
cold_outcome.ready,
cold_outcome.sent_pack,
cold_outcome.objects_sent
),
"after {offered} have(s) a warm memo reached a different verdict"
);
assert_eq!(
warm_out, cold_out,
"after {offered} have(s) a warm memo put different bytes on the wire"
);
saw_ready |= warm_outcome.ready;
saw_nak |= !warm_outcome.ready;
}
assert!(
saw_ready && saw_nak,
"the fixture produced only one kind of round (ready={saw_ready}, \
nak={saw_nak}), so the comparison never covered both"
);
}