gunnar-wire 1.5.1

//! The fetch path's allocation ceilings.
//!
//! # Why this module exists
//!
//! `gunnar-pack`'s [`IndexOptions::alloc_limit_bytes`] guards the **receive**
//! path against a hostile pack claiming an enormous object. Nothing guarded the
//! **serve** path, and the serve path has the same two sources of
//! attacker-chosen size:
//!
//! * **the request** — a v2 argument section and a v0 `want`/`have` exchange are
//!   read until the peer sends a flush-pkt, into a `Vec` that grows with every
//!   line. Nothing said how many lines that could be. A client that opens a
//!   connection and sends `have <oid>` forever makes the server allocate
//!   forever, and it does so *before* any repository is touched, so no
//!   traversal budget is in the way;
//! * **an object** — the whole-object writer materialises each object's
//!   inflated content before it deflates it, so peak memory is the largest
//!   object in the transfer. That size is not chosen by this request, but it was
//!   chosen by whoever pushed it.
//!
//! # The principle, restated because it is the same one
//!
//! `gunnar-pack`'s [`read`] module puts it as: **a guard that is off by default
//! is not a guard.** Both ceilings here default to `Some`, and both are
//! expressible as `None` by a caller that asks — [`Limits::no_alloc_limit`] —
//! which is the shape that made the pack indexer's guard real rather than
//! optional.
//!
//! # What each ceiling actually prevents
//!
//! [`Limits::request_bytes`] is **preventive**: the bytes are counted as they
//! are framed, and the read stops at the ceiling. Nothing above it is ever held.
//!
//! [`Limits::object_bytes`] is **preventive too, and that is why it is applied
//! where it is**. It is enforced in the object *selection* walk, from the
//! object's header, before any content is read — not in the pack writer, which
//! only ever sees an object that has already been materialised. A ceiling
//! checked after `gix_object::Find::try_find` has filled a buffer is a report,
//! not a guard: the allocation it exists to stop has already happened by the
//! time it can fire.
//!
//! An object over the ceiling is **refused, not skipped**. Skipping it would
//! produce a pack whose closure does not hold, which is a corrupt clone rather
//! than a refused one — the same judgement `gunnar-store`'s `write_stream`
//! makes about an oversized declared size.
//!
//! # What is still `O(repository)`, said plainly
//!
//! These ceilings bound the two sizes gunnar does not choose. They do **not**
//! make a fetch constant-memory, and the remaining terms are all the same shape
//! — one machine word or one object id per object in the transfer — so they are
//! listed with what they cost at ten million sha256 objects rather than left as
//! "some overhead":
//!
//! | | where | ~bytes/object | at 10M |
//! |---|---|---|---|
//! | the selection | `graph::Selection::objects` | 32 | 320 MB |
//! | the client's closure | `graph::select_objects` step 5 | ~51 | 510 MB |
//! | the writer's de-duplicated copy | `gunnar_pack::write::prepare_ids` | 32 + ~51 transient | 830 MB |
//! | gix's count list | `gunnar_pack::copy::write_pack_copy` | ~48 | 480 MB |
//! | the `ofs-delta` offset table | `gunnar_pack::copy::write_pack_copy` | 16 | 160 MB |
//!
//! And one term whose denominator is **the pack**, not the transfer, so it is
//! listed apart rather than added to the column above:
//!
//! | | where | ~bytes/object **in the pack** | at a 10M-object pack |
//! |---|---|---|---|
//! | The entry-extent table | `gunnar_pack::copy::PackExtents` | 48 (sha256) / 36 (sha1) | 480 MB |
//!
//! It buys the removal of one full inflate per object served — MEASURED
//! 2026-08-04 over the 19-repository corpus, **1.97× less server CPU on a clone
//! at the median** and 21.4% less peak RSS on `znippy.git` — and it is built
//! once per request and shared across `iter_from_counts`'s clones rather than
//! per worker. Two thirds of it (`Vec<(Offset, ObjectId)>`) is a table
//! `iter_from_counts` already builds for itself whenever a **thin** fetch has to
//! resolve a delta base, so on that path the new term is the 8-byte offset
//! column alone. It is also **one pack's** table and not the store's: only the
//! pack `gix-odb` searched most recently is consulted, so a repository with many
//! small packs holds one table per pack it actually touched rather than one per
//! pack it has. A repository whose pack dwarfs the transfer is where this costs
//! most and where it saves least, and `.rev`-file support in `gix-pack` — which
//! would let the table be read rather than built — is the answer if that ever
//! shows up.
//!
//! Since the thin-pack ruling the client's-closure row is **live for longer**
//! rather than larger. It used to die at the end of `select_objects`; it is
//! now carried out as `graph::Selection::client_has`, because vouching for the
//! base of a thin delta is what lets a fetch ship the deltas it already had
//! instead of expanding them. There is no second copy — the same set is moved,
//! and `graph::tests::a_fetch_holds_the_clients_object_closure_once` still
//! holds the peak to one — but it now overlaps the last three rows instead of
//! preceding them.
//!
//! What bounds it is `Exclusion::Edges`, the shipping default: that walk opens
//! up the frontier rather than the client's history, so the set carried to the
//! writer is frontier-sized. The same test asserts it, as live ids, against the
//! `Exclusion::Full` figure. Under `GUNNAR_EXCLUSION=full` the row is the
//! client's whole closure and does overlap the write.
//!
//! `crate::DEFAULT_BUDGET` bounds all of them at once, but it bounds them in
//! **objects**, and ten million objects of that bookkeeping is on the order of a
//! gigabyte before a single byte of content is read. That is the honest reading
//! of the budget, and the `git` package's reachability bitmaps are what removes the first two
//! rows rather than caps them.
//!
//! [`IndexOptions::alloc_limit_bytes`]: gunnar_pack::IndexOptions::alloc_limit_bytes
//! [`read`]: gunnar_pack::DEFAULT_ALLOC_LIMIT_BYTES

/// Ceiling on the bytes held for one peer-supplied request: 8 MiB.
///
/// The size being guarded is **the peer's to choose** and costs it one pkt-line
/// header per 65 516 bytes, so the ratio between what an attacker spends and
/// what the server spends is about 1:1 — which is why the ceiling has to be an
/// absolute number rather than a multiple of anything.
///
/// 8 MiB is roughly 200 000 object ids at v2's `want <oid>` / `have <oid>`
/// line width. Stock `git` sends its `have`s in windows and gives up after 256
/// unproductive rounds, so a real negotiation is three orders of magnitude
/// under this; a partial clone's lazy fetch, the largest legitimate `want` list
/// gunnar can be shown, batches its requests and is two orders under.
pub const DEFAULT_REQUEST_LIMIT_BYTES: usize = 8 << 20;

/// Ceiling on a single object gunnar will materialise while serving: 1 GiB.
///
/// The **same number** `gunnar-pack` applies to an entry decoded out of an
/// untrusted pack. It is stated once, in [`crate::pack`], rather than twice
/// here and there (one implementation) — and because a `pub const` naming
/// `gunnar_pack` is enough on its own to link the whole pack pipeline into the
/// appliance, which is what [`crate::pack`]'s header is about. The two are
/// held equal by
/// `pack::tests::the_allocation_ceiling_matches_the_one_gunnar_pack_enforces`,
/// where `gunnar-pack` is a dev-dependency and costs the shipping graph
/// nothing. An object that could not be received cannot usefully be served.
pub const DEFAULT_OBJECT_LIMIT_BYTES: usize = crate::pack::DEFAULT_ALLOC_LIMIT_BYTES;

/// What one object id held by a traversal costs in resident bytes: 384.
///
/// # It is measured, and it is a rate, not a struct size
///
/// The tempting number is `size_of::<ObjectId>()`, which is 33. It is wrong by
/// an order of magnitude, because one id in flight is not one id: it is an
/// entry in the walk's `seen` set, a slot in the selection vector, the pack
/// writer's de-duplicated copy of that vector, gix's count list and its
/// `ofs-delta` offset table — the five rows this module's own table above
/// lists, plus hashbrown's load-factor slack on the two that are sets.
///
/// So it is measured end to end instead: `VmHWM` for a process that serves
/// exactly one bitmap-less clone and does nothing else, divided by the objects
/// it sent. `bench/examples/walkbudget-probe.rs`, 2026-08-05:
///
/// | corpus | objects | wire | B/object |
/// |---|---|---|---|
/// | `h2h-linear-sha1-2048c` | 36 172 | 6.2 MB | 791.1 |
/// | `h2h-linear-sha256-2048c` | 36 172 | 6.8 MB | 808.9 |
/// | `forge-year-8a-240b-12c` | 28 893 | 24.5 MB | 1 572.9 |
/// | `h2h-linear-sha1-20480c` | 352 396 | 64.9 MB | 627.6 |
/// | `kernelscale` (14M, past the kernel) | 14 042 000 | 599.0 MB | **393.8** |
///
/// **The rate falls as the corpus grows, and this constant is the value at the
/// scale the ceiling is about.** The small-corpus rows are dominated by a fixed
/// intercept — the process, the mmap'd pack index, gix's caches — which does
/// not repeat per request-object and would make the charge nonsense if it were
/// baked in. Fitting the two largest rows gives a marginal cost of ~390 B and
/// the largest row's whole-process rate is 393.8, so 384 (a multiple of 64
/// under both) is the charge.
///
/// # Two things it does not claim
///
/// **It is not hash-dependent.** sha1 and sha256 at the same object count
/// measured 791.1 and 808.9 B/object — 2.2% apart, where `size_of` reasoning
/// predicts 47%. The id is a third of one row of five and the rest do not
/// change width, so charging two rates would be precision the measurement does
/// not support.
///
/// **It does not cover content.** `forge-year-8a-240b-12c` sits at 1 572.9
/// B/object, 4× this rate, and the reason is in its wire column: 848 bytes per
/// object of content against `h2h-linear-sha1-20480c`'s 184. That term is the
/// source pack resident under gix's mmap and the writer's per-object buffer,
/// and it is bounded by [`Limits::object_bytes`] and by the fact that the
/// writer streams — not by counting ids. Fitting the ladder as
/// `a + 390·objects + 1.05·wire_bytes` predicts every row within 13%, which is
/// the honest statement of what an id-counted ceiling can and cannot bound.
pub const WALK_BYTES_PER_OBJECT: usize = 384;

/// Ceiling on the object bookkeeping **one fetch** may hold: 8 GiB.
///
/// # Why this is in bytes when the thing it replaces counted objects
///
/// `crate::DEFAULT_BUDGET` counted objects, and an operator sizing a machine
/// does not have an object count — they have `free -g`. Worse, an object count
/// cannot be *pooled*: adding one request's ten million to another's ten
/// million produces a number that means nothing about the box, which is why the
/// server-wide half of this ([`WalkPool`]) could not exist until the unit
/// changed.
///
/// # Why 8 GiB and not less
///
/// Because the bar is that the kernel clones. MEASURED 2026-08-05,
/// `bench/examples/walkbudget-probe.rs --scale` on a 14 042 000-object fixture
/// with no `.bitmap` — 1.6% past the kernel's 13 816 503 — the whole clone was
/// served in **5 460 816 kB** of `VmHWM` and 64 seconds. At
/// [`WALK_BYTES_PER_OBJECT`] this ceiling admits 22.4M objects, which is that
/// repository with 60% to spare, and the same run establishes that
/// `DEFAULT_BUDGET`'s ten million **refuses** it.
///
/// # Why 8 GiB is not, by itself, a bound on the server
///
/// It is a per-*request* ceiling, and `gunnar serve` admits 256 concurrent
/// transfers by default. 256 × 8 GiB is 2 TB, so this number on its own bounds
/// nothing that matters; [`WalkPool`] is the half that does.
pub const DEFAULT_WALK_LIMIT_BYTES: usize = 8 << 30;

/// The ceilings one connection serves under.
///
/// Every field defaults to `Some`. See the module docs for why that is the
/// whole point.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Limits {
    /// Bytes of pkt-line payload gunnar will hold for one request before it
    /// refuses. `None` removes the ceiling.
    pub request_bytes: Option<usize>,
    /// Bytes of a single object gunnar will put in a pack. `None` removes the
    /// ceiling.
    pub object_bytes: Option<usize>,
    /// Bytes of object bookkeeping one traversal may hold. `None` removes the
    /// ceiling.
    ///
    /// Charged at [`WALK_BYTES_PER_OBJECT`] against the ids **live** in the
    /// walk, which is not the same as the ids it has emitted — see
    /// [`crate::DEFAULT_BUDGET`] for the three separate accumulators the object
    /// count used to charge and the fourth it charged not at all.
    pub walk_bytes: Option<usize>,
}

impl Default for Limits {
    fn default() -> Self {
        Limits {
            request_bytes: Some(DEFAULT_REQUEST_LIMIT_BYTES),
            object_bytes: Some(DEFAULT_OBJECT_LIMIT_BYTES),
            walk_bytes: Some(DEFAULT_WALK_LIMIT_BYTES),
        }
    }
}

impl Limits {
    /// The defaults — both ceilings on.
    pub fn new() -> Self {
        Limits::default()
    }

    /// Cap the bytes held for one peer-supplied request.
    pub fn request_bytes(mut self, limit: usize) -> Self {
        self.request_bytes = Some(limit);
        self
    }

    /// Cap a single object's size.
    pub fn object_bytes(mut self, limit: usize) -> Self {
        self.object_bytes = Some(limit);
        self
    }

    /// Cap the object bookkeeping one traversal may hold.
    pub fn walk_bytes(mut self, limit: usize) -> Self {
        self.walk_bytes = Some(limit);
        self
    }

    /// Remove **all** the ceilings entirely.
    ///
    /// Only for a peer whose bytes are trusted and a repository whose contents
    /// are known: a local `gunnar mirror` between two directories on the same
    /// box, or a benchmark that is measuring what the ceiling costs.
    /// **Never on a path that answers the network.** Both sizes this guards are
    /// chosen by somebody other than the server — one by the peer framing the
    /// request, one by whoever pushed the object — which is the same reason
    /// `gunnar_pack::IndexOptions::no_alloc_limit` carries the same warning.
    pub fn no_alloc_limit(mut self) -> Self {
        self.request_bytes = None;
        self.object_bytes = None;
        self.walk_bytes = None;
        self
    }
}

/// **The ceiling on what the whole server holds at once**, in bytes of walk
/// bookkeeping, shared by every in-flight transfer.
///
/// # Why a per-request ceiling was never a bound on the box
///
/// [`DEFAULT_WALK_LIMIT_BYTES`] is generous on purpose: the bar is that a
/// kernel-sized repository with no `.bitmap` clones, and that costs 5.59 GB
/// (MEASURED, see the constant). `gunnar serve`'s admission gate then admits
/// **256** concurrent transfers by default — a number chosen against CPU, in
/// `gunnar_ssh::admission`, with nothing in it about memory. Multiply them and
/// the shipped server will cheerfully begin 256 clones that between them need
/// two terabytes, on a box that has not got it. The failure is the OOM killer
/// picking a victim, which is the one refusal an operator cannot read.
///
/// So the ceiling has to be spent from a **shared** purse, and that is the
/// reason the unit had to become bytes: object counts from two differently
/// shaped repositories do not add up to anything.
///
/// # It admits by size, so small transfers never queue behind a big one
///
/// A reservation is taken as the walk grows, not at the door, so a request is
/// only ever charged for what it is actually holding. A clone of a small
/// repository never reaches [`WalkPool::FLOOR_BYTES`] and so never touches the
/// pool at all — the atomic is left for the transfers that can hurt the
/// machine. Above it, reservations move in [`WalkPool::CHUNK_BYTES`] steps, so
/// a fourteen-million-object clone costs about 700 atomic operations across
/// sixty seconds rather than one per object.
///
/// # What happens at the ceiling
///
/// [`crate::Error::WalkPoolFull`], which reaches the client through
/// `UploadPack::serve_session`'s error seam as a sentence naming both numbers.
/// A refusal a client can read and retry is the whole difference between this
/// and the accidental ceiling it replaces.
///
/// # What it does, MEASURED
///
/// `bench/examples/walkpool-probe.rs`, 2026-08-05, thirty-two concurrent
/// bitmap-less clones of a 352 396-object repository in one process, three runs:
///
/// | | `VmHWM` | served | refused |
/// |---|---|---|---|
/// | one clone alone | 219 MB | 1 | — |
/// | 32 at once, no pool | **4.66–4.73 GB** | 32 | — |
/// | 32 at once, ~900 MB pool | **1.09–1.33 GB** | 3–5 | 27–29 |
///
/// 21.2–21.6× one clone against 4.97–6.09×, so the fan-out's peak comes down
/// 3.5–4.3× and every refusal was `WalkPoolFull`. The pooled peak is above the
/// purse because the purse charges the **walk**: the two or three clones that
/// got in are also running a pack writer, and the twenty-nine that did not each
/// held up to [`WalkPool::FLOOR_BYTES`] before being refused.
///
/// # This alone does not guarantee progress, and the reason is not fixable here
///
/// A walk's size is not known at the door, so reservations are taken **as it
/// grows**. A purse that is tight against a single walk therefore lets every
/// walk in a fan-out climb together and then refuses all of them with nobody
/// finished. MEASURED the same day: four concurrent 14 042 000-object clones
/// against a purse of two served **zero**, where thirty-two 352 396-object
/// clones against the same ratio served two — thirty-two threads on
/// thirty-two cores do not advance in lockstep and four do.
///
/// That is bin-packing without knowing the sizes. Three alternative reservation
/// policies — coarser bites, doubling bites, and refusing a *first* reservation
/// above a fraction of the purse — were each worked through on paper against
/// the four-clone case above and each still has a fan-out that jams it; none
/// was implemented and measured, which is why that is written as reasoning and
/// not as a result.
/// The answer is the architecture gunnar already has. **This is the backstop
/// and `--max-concurrent-transfers` is the primary gate**: the slot cap keeps
/// the fan-out narrow enough that the purse is not tight against it, and the
/// purse is what stops N admitted slots from meaning N times the largest
/// repository. [`WalkPool::for_this_machine`] sizing the purse to `MemTotal`
/// rather than to a constant is the other half of keeping that true on a box
/// nobody measured in advance.
#[derive(Debug)]
pub struct WalkPool {
    limit: usize,
    in_flight: std::sync::atomic::AtomicUsize,
    peak: std::sync::atomic::AtomicUsize,
    refusals: std::sync::atomic::AtomicU64,
}

impl WalkPool {
    /// Below this much held bookkeeping a request does not touch the pool.
    ///
    /// 8 MiB is about 21 800 objects at [`WALK_BYTES_PER_OBJECT`]. Every
    /// repository in gunnar's own bench corpus except the two largest sits under
    /// it, which is the point: metering an ordinary clone would put an atomic in
    /// front of a transfer that could not exhaust anything.
    pub const FLOOR_BYTES: usize = 8 << 20;

    /// How much a growing walk reserves at a time, above [`Self::FLOOR_BYTES`].
    pub const CHUNK_BYTES: usize = 8 << 20;

    /// A pool of `limit_bytes`.
    pub fn new(limit_bytes: usize) -> std::sync::Arc<Self> {
        std::sync::Arc::new(WalkPool {
            limit: limit_bytes,
            in_flight: std::sync::atomic::AtomicUsize::new(0),
            peak: std::sync::atomic::AtomicUsize::new(0),
            refusals: std::sync::atomic::AtomicU64::new(0),
        })
    }

    /// Half of this machine's `MemTotal`, or [`DEFAULT_WALK_LIMIT_BYTES`] if
    /// `/proc/meminfo` cannot be read.
    ///
    /// Half rather than all: the pool bounds *one* of the things a git server
    /// holds. The pack writer's buffers, the receive path's index, the page
    /// cache the mmap'd packs live in and whatever else shares the box are not
    /// in it, and a memory ceiling set to the whole machine is a ceiling that
    /// fires after the machine is already in trouble.
    ///
    /// The fallback is deliberately the *per-request* number, so a machine whose
    /// size cannot be read gets a pool that admits exactly one large clone
    /// rather than an accidentally unbounded one.
    pub fn for_this_machine() -> std::sync::Arc<Self> {
        WalkPool::new(Self::half_of_memtotal().unwrap_or(DEFAULT_WALK_LIMIT_BYTES))
    }

    fn half_of_memtotal() -> Option<usize> {
        let text = std::fs::read_to_string("/proc/meminfo").ok()?;
        let kb: usize = text
            .lines()
            .find_map(|l| l.strip_prefix("MemTotal:")?.trim().strip_suffix(" kB"))
            .and_then(|v| v.trim().parse().ok())?;
        kb.checked_mul(1024).map(|bytes| bytes / 2)
    }

    /// The ceiling this pool was built with.
    pub fn limit_bytes(&self) -> usize {
        self.limit
    }

    /// Bytes reserved by transfers in flight right now.
    pub fn in_flight_bytes(&self) -> usize {
        self.in_flight.load(std::sync::atomic::Ordering::Relaxed)
    }

    /// The most this pool has ever had reserved at once.
    pub fn peak_bytes(&self) -> usize {
        self.peak.load(std::sync::atomic::Ordering::Relaxed)
    }

    /// How many walks this pool has refused. Monotonic.
    pub fn refusals(&self) -> u64 {
        self.refusals.load(std::sync::atomic::Ordering::Relaxed)
    }

    /// Take `bytes` from the pool, or refuse.
    ///
    /// A compare-and-swap loop rather than `fetch_add` and a check: adding first
    /// would let two transfers that each fit push the total past the ceiling and
    /// then both back it out, which is a pool that is briefly over its own limit
    /// exactly when it is busiest.
    pub(crate) fn try_reserve(&self, bytes: usize) -> crate::Result<()> {
        use std::sync::atomic::Ordering;
        let mut current = self.in_flight.load(Ordering::Relaxed);
        loop {
            let Some(next) = current.checked_add(bytes).filter(|n| *n <= self.limit) else {
                self.refusals.fetch_add(1, Ordering::Relaxed);
                return Err(crate::Error::WalkPoolFull {
                    wanted: bytes,
                    in_flight: current,
                    limit: self.limit,
                });
            };
            match self.in_flight.compare_exchange_weak(
                current,
                next,
                Ordering::AcqRel,
                Ordering::Relaxed,
            ) {
                Ok(_) => {
                    self.peak.fetch_max(next, Ordering::Relaxed);
                    return Ok(());
                }
                Err(seen) => current = seen,
            }
        }
    }

    /// Give `bytes` back.
    ///
    /// Saturating, and that is not defensiveness: a release that underflowed
    /// would wrap to `usize::MAX` and permanently close a pool that is supposed
    /// to be self-healing. `walk_pool_never_goes_negative` is the guard.
    pub(crate) fn release(&self, bytes: usize) {
        use std::sync::atomic::Ordering;
        let _ = self
            .in_flight
            .fetch_update(Ordering::AcqRel, Ordering::Relaxed, |current| {
                Some(current.saturating_sub(bytes))
            });
    }
}

/// A byte budget that is spent as a request is framed.
///
/// One of these per request rather than a per-line check, because the shape
/// being guarded is a **million small lines**, not one large one — pkt-line
/// framing already caps a single line at 65 520 bytes, so a per-line ceiling
/// would have nothing left to catch.
#[derive(Debug)]
pub(crate) struct Budget {
    remaining: Option<usize>,
    limit: Option<usize>,
}

impl Budget {
    pub(crate) fn new(limit: Option<usize>) -> Self {
        Budget {
            remaining: limit,
            limit,
        }
    }

    /// Charge `bytes` against the budget, or fail.
    pub(crate) fn spend(&mut self, bytes: usize, what: &'static str) -> crate::Result<()> {
        let (Some(remaining), Some(limit)) = (self.remaining.as_mut(), self.limit) else {
            return Ok(());
        };
        match remaining.checked_sub(bytes) {
            Some(left) => {
                *remaining = left;
                Ok(())
            }
            None => Err(crate::Error::RequestTooLarge { limit, what }),
        }
    }
}