crates/storage-git-gix/src/delta_cache.rs
//! The delta base cache every pooled `gix-odb` handle reads through.
//!
//! **Lifted verbatim** from `parked-gix-2/gunnar-store-gix/src/delta_cache.rs`;
//! only the doc cross-references changed. Every number below was **MEASURED on
//! oden** by the code this came from. `locked_on_target.md` §7 forbids comparing
//! across machines, and nothing in this session re-took any of them on t14s, so
//! read them as the reasoning that produced the design, not as this crate's
//! results.
//!
//! # Why gunnar has one at all
//!
//! A packed object that is a delta is stored as instructions against a base,
//! which may itself be a delta, up to git's default depth of 50. Resolving one
//! means inflating the whole object at the bottom of that chain and applying
//! every patch back up. Do that for object *k* of a chain and then for object
//! *k+1*, with nothing remembered in between, and the root gets inflated twice
//! and the first *k* patches applied twice — `O(depth²)` over a range where
//! `O(depth)` would do.
//!
//! git's answer is a hash map keyed on `(pack, base offset)` with an LRU list,
//! `packfile.c:1167-1325`, into which `unpack_entry` inserts **every**
//! intermediate result on the way back up (`:1715-1719`), 96 MiB per process by
//! default (`core.deltaBaseCacheLimit`).
//!
//! gunnar had none. `gix-odb`'s `new_pack_cache` defaults to `None` and its
//! `try_find` then hands `gix_pack::cache::Never` to the decoder
//! (`gix-odb-0.83.0/src/cache.rs:102` and `:228`), so every read through a bare
//! handle re-resolves from the root. [`crate::odb::OdbPool`] attaches one of
//! these to every handle it builds, which is why this type is in this crate.
//!
//! # Why this is written here rather than taken from `gix-pack`
//!
//! `gix-pack` ships `cache::lru::MemoryCappedHashmap`, which is what
//! [`crate::odb`] would otherwise use — but it lives behind the
//! `pack-cache-lru-dynamic` feature, and that feature pulls `clru`, which pulls
//! `hashbrown`, `allocator-api2`, `equivalent` and `foldhash`. MEASURED with
//! `cargo xtask guard` on oden, 2026-08-04: the appliance graph went **280 →
//! 283 crates (267 → 270 third-party)** and `S:gunnar-store` **103 → 107**.
//!
//! That is a poor trade for a data structure this small, against a §2 guard the
//! project treats as a law. [`DeltaBaseCache`] is `std` only and adds nothing to
//! any graph. It is not a copy of gunnar code — LAW 5 is about not twinning
//! *our* logic — it is an implementation of an upstream trait that gunnar cannot
//! otherwise reach for free.
//!
//! # What it does differently from git, deliberately
//!
//! * **FIFO, not LRU.** The access pattern that matters is a walk, where the
//! entry a read needs was almost always produced by the read just before it,
//! so recency and insertion order coincide. Dropping the LRU list drops the
//! only part that needs intrusive links. MEASURED against `gix-pack`'s real
//! LRU at the same 4 MiB cap, whole-pack sweep, oden 2026-08-04
//! (`bench/examples/deltachain-probe.rs`): nornir 0.350 s LRU / 0.340 s this,
//! facett 0.085 / 0.085, knut 0.022 / 0.022 — **0.995× to 1.027×**, i.e. this
//! is at worst a wash and twice out of three slightly ahead, the LRU
//! bookkeeping costing more than the extra hits it buys.
//! * **It has admission control.** git adds an entry's size *before* evicting
//! (`packfile.c:1303-1311`), so an object larger than the whole limit is
//! admitted and then evicts everything else. Here an entry that cannot fit is
//! simply not stored, and the rest of the cache survives it.
use std::collections::{HashMap, VecDeque};
use gix_object::Kind;
/// One cached, fully decoded object.
struct Slot {
kind: Kind,
data: Vec<u8>,
}
/// A byte-bounded FIFO cache of decoded pack objects, keyed on
/// `(pack id, pack offset)`.
///
/// Constructed empty and grown on demand: the cap is a ceiling, never a
/// reservation, so an idle handle holding one costs its two empty containers
/// and nothing else.
pub struct DeltaBaseCache {
cap_bytes: usize,
bytes: usize,
slots: HashMap<(u32, u64), Slot>,
/// Insertion order, for eviction. A key appears here at most once: a `put`
/// of a key already present replaces the value in `slots` and leaves the
/// order alone, because re-recording it would let the queue grow without
/// bound on a repeated write.
order: VecDeque<(u32, u64)>,
}
impl DeltaBaseCache {
/// A cache holding at most `cap_bytes` of decoded object data.
pub fn new(cap_bytes: usize) -> Self {
DeltaBaseCache {
cap_bytes,
bytes: 0,
slots: HashMap::new(),
order: VecDeque::new(),
}
}
/// Decoded bytes currently held. Exists so a test can prove the bound is
/// enforced rather than asserted.
#[cfg(test)]
pub(crate) fn bytes(&self) -> usize {
self.bytes
}
/// How many objects are held.
#[cfg(test)]
pub(crate) fn len(&self) -> usize {
self.slots.len()
}
}
impl gix_pack::cache::DecodeEntry for DeltaBaseCache {
fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: Kind, _compressed_size: usize) {
// Admission control, which git does not have. An entry that cannot fit
// is refused outright rather than admitted and then made to evict the
// entire cache to make room for itself.
if data.len() > self.cap_bytes {
return;
}
let key = (pack_id, offset);
if let Some(slot) = self.slots.get_mut(&key) {
// Same object, decoded again. Replace in place; the queue already
// names this key exactly once and must keep naming it once.
self.bytes -= slot.data.len();
self.bytes += data.len();
slot.kind = kind;
slot.data.clear();
slot.data.extend_from_slice(data);
} else {
self.slots.insert(
key,
Slot {
kind,
data: data.to_vec(),
},
);
self.order.push_back(key);
self.bytes += data.len();
}
while self.bytes > self.cap_bytes {
let Some(old) = self.order.pop_front() else {
// Unreachable while `slots` and `order` agree, and if they ever
// stop agreeing the alternative is spinning here for ever.
debug_assert!(self.slots.is_empty(), "eviction queue lost a live key");
self.bytes = 0;
break;
};
if let Some(slot) = self.slots.remove(&old) {
self.bytes -= slot.data.len();
}
}
}
fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec<u8>) -> Option<(Kind, usize)> {
let slot = self.slots.get(&(pack_id, offset))?;
out.clear();
out.extend_from_slice(&slot.data);
Some((slot.kind, slot.data.len()))
}
}
#[cfg(test)]
mod tests {
use super::*;
use gix_pack::cache::DecodeEntry;
#[test]
fn a_stored_entry_comes_back_with_its_kind_and_bytes() {
let mut c = DeltaBaseCache::new(1024);
c.put(1, 40, b"a tree, notionally", Kind::Tree, 9);
let mut out = vec![0xAA; 7];
let got = c.get(1, 40, &mut out);
assert_eq!(got, Some((Kind::Tree, 18)));
assert_eq!(out, b"a tree, notionally");
}
#[test]
fn a_different_pack_at_the_same_offset_is_a_different_object() {
// The whole reason the key is a pair. A cache keyed on offset alone
// would serve pack 2's bytes for pack 1's object and the decoder would
// apply a delta to the wrong base — a wrong answer, not a slow one.
let mut c = DeltaBaseCache::new(1024);
c.put(1, 40, b"one", Kind::Blob, 3);
c.put(2, 40, b"two", Kind::Blob, 3);
let mut out = Vec::new();
assert_eq!(c.get(1, 40, &mut out), Some((Kind::Blob, 3)));
assert_eq!(out, b"one");
assert_eq!(c.get(2, 40, &mut out), Some((Kind::Blob, 3)));
assert_eq!(out, b"two");
}
#[test]
fn the_byte_bound_is_enforced_and_the_oldest_goes_first() {
let mut c = DeltaBaseCache::new(30);
c.put(1, 0, &[0u8; 10], Kind::Blob, 1);
c.put(1, 1, &[1u8; 10], Kind::Blob, 1);
c.put(1, 2, &[2u8; 10], Kind::Blob, 1);
assert_eq!(c.bytes(), 30);
assert_eq!(c.len(), 3);
c.put(1, 3, &[3u8; 10], Kind::Blob, 1);
assert!(c.bytes() <= 30, "the cap was exceeded: {} bytes", c.bytes());
let mut out = Vec::new();
assert!(
c.get(1, 0, &mut out).is_none(),
"the oldest entry survived eviction, so this is not FIFO"
);
assert!(c.get(1, 3, &mut out).is_some(), "the newest entry was lost");
}
#[test]
fn an_entry_larger_than_the_whole_cache_is_refused_rather_than_admitted() {
// git admits it and then evicts everything else to pay for it. This is
// the assertion that gunnar does not.
let mut c = DeltaBaseCache::new(30);
c.put(1, 0, &[0u8; 10], Kind::Blob, 1);
c.put(1, 1, &[9u8; 100], Kind::Blob, 1);
let mut out = Vec::new();
assert!(
c.get(1, 1, &mut out).is_none(),
"an over-sized entry was admitted"
);
assert!(
c.get(1, 0, &mut out).is_some(),
"an over-sized entry evicted the entry that did fit"
);
}
#[test]
fn re_putting_a_key_does_not_grow_the_eviction_queue() {
// If it did, a hot object rewritten N times would push N keys and the
// queue would evict N-1 live entries chasing ghosts.
let mut c = DeltaBaseCache::new(1000);
for _ in 0..50 {
c.put(1, 7, &[0u8; 10], Kind::Blob, 1);
}
assert_eq!(c.len(), 1);
assert_eq!(c.bytes(), 10);
assert_eq!(
c.order.len(),
1,
"the eviction queue accumulated duplicates"
);
}
}