crates/gunnar-wire/src/negotiate.rs
//! Negotiation: deciding what the client already has.
//!
//! # Why this is the hard part
//!
//! A `have`/`want` loop that terminates on the happy path but never on a
//! divergent history is the classic git-server failure, and it does
//! not show up against a three-commit fixture: with a linear history the very
//! first `have` is common and the loop ends on round one. It only appears when
//! the client's branch has genuinely diverged, so that round after round of
//! `have`s are all unknown to the server.
//!
//! Two things make that safe here, and both are load-bearing:
//!
//! * **Termination does not depend on the server saying `ready`.** The client
//! stops when it runs out of its own commits and sends `done`; the server's
//! `ready` is only an early exit. So the worst case of a total divergence is
//! a longer negotiation, never a hang, provided the server keeps answering.
//! That is why an empty round answers `NAK` rather than nothing.
//! * **The walk is bounded twice**: by the oldest `have`'s commit date, and by
//! an object budget. Without the date bound, every round of a divergent fetch
//! walks to the root of the repository.
//!
//! The criterion for `ready` is git's own: *every want can reach at least one
//! commit the client claims to have*. Not "some want", which stops too early
//! and sends a pack the client cannot use, and not "the client has a want",
//! which is a different question entirely.
//!
//! # What a *round* costs, which is a separate question from what a walk costs
//!
//! Everything above is about one traversal. The thing that actually cost 154
//! seconds on the `negotiate_divergent` bench arm was none of it.
//!
//! A protocol-v2 client re-sends its **whole** `have` list on every
//! `command=fetch`. So if a round is answered purely from its own arguments,
//! round *n* redoes the work of rounds 1..n and a negotiation is `O(rounds²)`.
//! That is invisible in a three-round test and invisible on a wall clock at
//! fixture size, and it hid three separate redundancies at once: a linear
//! `Vec` scan to de-duplicate `common`, a reachability walk that read every
//! commit twice, and a date cutoff re-derived by re-reading every common commit
//! every round. MEASURED 2026-08-03: **197 s → 17.9 s**, and object reads
//! **18.9 M → 6.4 M**, with no change to what any round decides.
//!
//! [`HaveMemo`] is the answer to the third of those, and its doc explains why a
//! cache here is not negotiation state. The remaining `O(rounds²)` term is the
//! walk itself ([`Reachability`] is rebuilt per round), and the measurement says so
//! rather than pretending the shape is gone.
use std::collections::{HashMap, HashSet};
use std::sync::Mutex;
use gix_hash::ObjectId;
use gunnar_store::object;
use crate::graph::{Graph, Reachability};
use crate::Result;
/// What one round of negotiation concluded.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Negotiation {
/// The `have`s this repository actually holds, in the order they were sent.
///
/// **What the pack is computed against**, and therefore complete: this is
/// git's `have_obj`, not its `common`.
pub common: Vec<ObjectId>,
/// Of those, the ones the server did not already know the client held —
/// **what goes on the wire as `ACK`**.
///
/// # The difference, and what it is worth
///
/// A `have` that is common tells the server about that commit *and its
/// whole ancestry*: a client does not hold a commit without holding its
/// parents. So when the next `have` in the batch is the previous one's
/// parent — which is exactly what a client walking its own history back
/// from a tip sends — the server already knew, and `ACK`ing it says
/// nothing the client did not just say itself.
///
/// git has always done this. `upload-pack.c`'s `process_haves` marks every
/// common `have`'s parents `THEY_HAVE` and appends to the ACK array only
/// when `!we_knew_they_have`. gunnar `ACK`ed the whole of `common`.
///
/// MEASURED 2026-08-04, `bench/examples/fetchbytes-probe.rs`, one
/// negotiated fetch across the 500-commit `h2h-divergent-2000b-500d`
/// divergence, both servers reaching `ready` on the same round with the
/// same 1 008 `have`s: stock git sent **1** `ACK`, gunnar sent **508**, and
/// gunnar's 508 were a straight parent chain whose head was git's one.
/// At 45 payload bytes and 5 of pkt-line header that is **25 400 bytes** —
/// against a total server→client stream of 366 818, and against a
/// whole-fetch deficit to stock git of 73 875 on that fixture. **A third of
/// gunnar's fetch wire-byte loss was `ACK` lines.**
///
/// Fewer `ACK`s cannot make a negotiation worse: the client is told nothing
/// it did not derive, `ready` is decided from [`Negotiation::common`] which
/// is untouched, and the pack is computed from the same set as before.
pub ack: Vec<ObjectId>,
/// Whether the server has found a good enough cut point to send a pack.
pub ready: bool,
}
/// What one `have` turned out to be.
#[derive(Debug, Clone, Copy)]
enum HaveFact {
/// This repository does not hold it.
Absent,
/// It is here. `Some` carries its committer date; `None` means it is not a
/// readable commit, which is not an error (a `have` may name a tag, and a
/// damaged one names nothing useful) but has no date to bound a walk by.
Present(Option<i64>),
}
/// Everything this connection has already learned about the `have`s offered to
/// it.
///
/// # Why this exists, and why it is only a memo
///
/// A protocol-v2 `command=fetch` carries the client's **whole** `have` list
/// every round, and [`negotiate`] is a pure function of one round's arguments.
/// So without a memo, round *n* re-asks the object store the same two questions
/// about every `have` from rounds 1..n: *do you have this?* and *when was it
/// committed?* That is `O(rounds²)` store work over a negotiation, and it is
/// paid entirely on `have`s whose answer was settled long ago.
///
/// git does not do this. `upload-pack`'s `got_oid()` looks each `have` up once
/// as it arrives and folds its date into a running `oldest_have`; the value
/// this memo computes is the same `oldest_have`, kept the same way.
///
/// **It is a cache, not negotiation state.** Every entry is a fact about the
/// object store, which does not change under a connection, so the answers are
/// identical with the memo cold or warm; there is no round-to-round *decision*
/// remembered here, and `negotiate` still sees only the `have`s of the round it
/// was handed. The one race worth naming: if a concurrent push adds an object a
/// client already offered and was told nothing about, the memo keeps saying
/// `Absent`, and the server sends that object again. Sending more than
/// necessary is slow; sending less would be a bug. The failure direction is the
/// safe one.
///
/// **Memory** is one entry per *distinct* `have`, which is client-sized rather
/// than repository-sized — but it is client-sized **across the whole
/// connection**, not per round, and that is the part that used to be missing.
/// `crate::limits` bounds one round; a client that sends a fresh page of
/// invented `have`s every round stays under that ceiling every time and still
/// grows this map without end. So the map is capped as well, by
/// [`HaveMemo::with_capacity`].
///
/// A **full memo stops recording, and answers exactly the same**. Every entry
/// is a fact about the object store, so a miss is re-derived from the store
/// rather than guessed; the only thing lost past the cap is the speed-up. That
/// is what makes a cap safe here and would not make it safe on anything holding
/// a decision.
#[derive(Debug, Default)]
pub(crate) struct HaveMemo {
state: Mutex<MemoState>,
/// How many facts may be remembered, or `None` for no ceiling.
capacity: Option<usize>,
}
/// The two things one lock guards.
///
/// One mutex rather than two, because [`HaveMemo::resolve`] needs both in the
/// same pass and two locks in one function is a lock order waiting to be got
/// wrong by the next person to add a third.
#[derive(Debug, Default)]
struct MemoState {
facts: HashMap<ObjectId, HaveFact>,
/// Every commit this connection has been told the client holds, **plus
/// every parent of one**.
///
/// git's `THEY_HAVE` object flag, kept in a set because gunnar reads
/// objects rather than owning a struct per object to hang a bit on. It is
/// what makes [`Negotiation::ack`] git's ACK list rather than the whole of
/// `common`; see that field for what it is worth.
///
/// **Not negotiation state, for the same reason `facts` is not.** It only
/// ever suppresses an `ACK` for a commit the client itself just named or
/// implied, so a cold set produces more `ACK` lines and the identical pack.
/// That is why sharing the [`HaveMemo::capacity`] ceiling is safe: past the
/// cap the set stops growing, some redundant `ACK`s come back, and nothing
/// else changes.
implied: HashSet<ObjectId>,
}
impl HaveMemo {
/// A memo that remembers at most `capacity` distinct `have`s.
pub(crate) fn with_capacity(capacity: Option<usize>) -> Self {
HaveMemo {
state: Mutex::new(MemoState::default()),
capacity,
}
}
}
impl HaveMemo {
/// The `have`s this repository holds, deduplicated, in the order sent, plus
/// the oldest committer date among them, which bounds the reachability
/// walk.
///
/// Returns `i64::MIN` for the cutoff when not one common `have` had a
/// readable commit date, which is the "do not prune at all" value.
///
/// The date is looked up even on a round that will not walk (a `done` or
/// `wait-for-done` request returns before [`Reachability`] is built). That
/// is one extra read per *distinct* common `have` per connection, and it is
/// accepted rather than gated on a flag: `select_objects` peels every one of
/// those same commits moments later anyway, so on any fetch that sends a
/// pack the read is not extra at all, and a third `HaveFact` state to
/// distinguish "not a commit" from "not looked up yet" would buy only the
/// fetch that errors out before packing.
fn resolve(&self, graph: &Graph<'_>, haves: &[ObjectId]) -> Resolved {
let mut guard = self.state.lock().unwrap_or_else(|e| e.into_inner());
let state = &mut *guard;
let mut common = Vec::new();
let mut ack = Vec::new();
let mut cutoff = i64::MAX;
let mut round: HashSet<ObjectId> = HashSet::with_capacity(haves.len());
// One object buffer and one parent list for the whole round, not one
// pair per `have`. `Graph::commit_facts_into` records what this was
// measured to be worth, which is **not** the 7.6 ms it was reached for:
// the parent decode costs that, the allocation behind it does not.
let mut buf: Vec<u8> = Vec::new();
let mut parents: Vec<ObjectId> = Vec::new();
for have in haves {
// A `have` repeated inside one round is answered once. The memo
// stops the store being re-asked across rounds; this stops `common`
// carrying the same id twice within one.
if !round.insert(*have) {
continue;
}
// The parents come out of the read the date already needed, so
// git's `THEY_HAVE` marking costs this loop nothing it was not
// paying. A memo **hit** yields none, and must not: this connection
// marked that `have`'s parents when it first read it, and re-reading
// the commit to mark them again is the `O(rounds²)` store traffic
// the memo exists to remove.
// `fresh` says whether `parents` was filled by this iteration. A
// memo **hit** fills nothing, and must not: this connection marked
// that `have`'s parents when it first read it, and re-reading the
// commit to mark them again is the `O(rounds²)` store traffic the
// memo exists to remove.
let (fact, fresh) = match state.facts.get(have) {
Some(fact) => (*fact, false),
None => {
// `contains_have`, not `contains`: a `have` the server does
// not hold is the client naming its OWN commits, which is
// the majority outcome here and not a sign that this store's
// snapshot has gone stale. See
// `ObjectStore::contains_without_rescan` for why a stale
// `false` widens a pack and can never invalidate one — the
// same safe direction this memo's own doc already records
// for a concurrent push.
let (fact, fresh) = if graph.contains_have(have) {
match graph.commit_into(have, &mut buf, &mut parents) {
Ok(at) => (HaveFact::Present(Some(at)), true),
// Present but not a readable commit: a tag, or a
// damaged object. No date and no ancestry, and git
// `ACK`s such a `have` every time for the same
// reason — `we_knew_they_have` can only be set by
// the commit branch.
Err(_) => (HaveFact::Present(None), false),
}
} else {
(HaveFact::Absent, false)
};
// Past the cap the answer is still computed and still
// correct; only the remembering stops.
if self.capacity.is_none_or(|cap| state.facts.len() < cap) {
state.facts.insert(*have, fact);
}
(fact, fresh)
}
};
if let HaveFact::Present(committed_at) = fact {
common.push(*have);
if let Some(at) = committed_at {
cutoff = cutoff.min(at);
}
// `we_knew` is read **before** this `have`'s own parents go in.
// A client walking its history back from a tip sends a chain,
// and the order is what turns 508 `ACK`s into 1: each link is
// implied by the one before it, and only the head is news.
let we_knew = state.implied.contains(have);
if self.capacity.is_none_or(|cap| state.implied.len() < cap) {
state.implied.insert(*have);
if fresh {
state.implied.extend(parents.iter().copied());
}
}
if !we_knew {
ack.push(*have);
}
}
}
if cutoff == i64::MAX {
cutoff = i64::MIN;
}
Resolved {
common,
ack,
cutoff,
}
}
}
/// What one pass over a round's `have`s worked out.
struct Resolved {
/// Every `have` this repository holds. What the pack is computed against.
common: Vec<ObjectId>,
/// The subset that was news. What goes on the wire. See
/// [`Negotiation::ack`].
ack: Vec<ObjectId>,
/// The oldest committer date among `common`, or `i64::MIN`.
cutoff: i64,
}
/// Run one round.
///
/// `wait_for_done` suppresses `ready` entirely: the client has asked to drive
/// the negotiation to its own end, and a server that stops early anyway has
/// accepted a capability it does not honour.
///
/// `memo` lives for the connection; see [`HaveMemo`] for why, and for why it
/// cannot change what this function decides.
pub(crate) fn negotiate(
graph: &Graph<'_>,
wants: &[ObjectId],
haves: &[ObjectId],
wait_for_done: bool,
memo: &HaveMemo,
) -> Result<Negotiation> {
// Which `have`s are common, and the oldest commit the client claims, which
// bounds how far back a useful cut point can be. Without that bound
// a divergent fetch re-walks the whole repository on every round, the exact
// shape that turns a slow negotiation into an apparent hang.
//
// Both answers come from one pass and one memo. The shape this replaced
// built `common` with a linear `common.contains(have)` scan per `have` and
// then re-read every common commit from the store to re-derive the cutoff,
// both of which grow with the round number. MEASURED on the
// `negotiate_divergent` arm (2026-08-03, worktree `87524d6`): the
// linear scan alone was **81%** of a 197.2-second negotiation, and it cost
// that without touching the object store once.
let Resolved {
common,
ack,
cutoff,
} = memo.resolve(graph, haves);
if common.is_empty() || wait_for_done {
return Ok(Negotiation {
common,
ack,
ready: false,
});
}
let mut reach = Reachability::new(graph, &common, cutoff);
let mut ready = true;
for want in wants {
// Only commits take part: a `want` naming a tag is judged by what it
// peels to, and one naming a tree or a blob has no ancestry to cut at.
let start = match graph.peel(want) {
Ok(peeled) if peeled.kind == object::Kind::Commit => peeled.id,
Ok(_) => continue,
Err(err) => return Err(err),
};
if !reach.reaches_common(start)? {
ready = false;
break;
}
}
Ok(Negotiation { common, ack, ready })
}