gunnar_wire/

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 })
}