crates/storage-git-gix/parked-gix-2/gunnar-store-gix/src/midx.rs
//! The **multi-pack index**: one sorted oid table across every pack, so a
//! lookup probes one index instead of `M` (`P-012`).
//!
//! # Why this and not an stree, a Bloom filter or a cuckoo filter
//!
//! `.nornir/TOTAL-PROMPT.md` §4.1/§4.2 intend an **stree** over oids for the
//! znippy cold tier, and `znippy-plugin-git` has one. LAW 5 says reuse a design
//! rather than twin it, but the measurement that justified stree also recorded
//! that its **serial** path is a wash against a binary search (0.99× at a
//! million keys) and that only the **batch** path wins, 1.5–2.6×. A miss on a
//! `want` line is a single serial lookup. There is no batch to win with, and
//! `P-003`'s batch seam does not exist yet.
//!
//! A Bloom or cuckoo filter per pack answers "definitely not here" in `O(1)`,
//! which sounds like exactly the shape of this problem. Measured, it is not
//! worth building: once the pack directory is no longer re-scanned on every miss
//! ([`crate::odb`]) a miss against one index over a million objects costs
//! **2.3 µs**, of which one `statx` and one loose-object `stat` are already
//! syscalls a filter cannot remove. A filter can at best delete the binary
//! search, and it would have to be built, persisted, invalidated on every push
//! and kept in agreement with the pack set, which is a second index with its own
//! staleness protocol: the twin LAW 5 forbids.
//!
//! The reuse that actually pays is git's own. `gix-pack` **already writes** a
//! multi-pack index and `gix-odb` **already reads** one. `use_multi_pack_index`
//! is on by default, and a `multi-pack-index` file collapses every index it
//! names into a single entry in the store's snapshot. So the whole `O(M)` term
//! disappears for zero new formats, zero new lookup code, and one file. What
//! this module adds is when to write it and how to keep it from going stale.
//!
//! # The trap, which was measured before it was believed
//!
//! Writing a multi-pack index **on its own makes the miss path worse.** Measured
//! on oden, 2026-08-03, over 64 packs, misses per second:
//!
//! | | no multi-pack index | with one |
//! |---|---|---|
//! | as this crate was before | 3 270 | 2 357 |
//! | pooled handles, no re-scan on miss | 60 337 | 415 392 |
//!
//! With `gix-odb`'s default refresh mode still on, adding the index costs a
//! further **28%**, because the per-miss disk consolidation now has one more
//! file to stat and validate. It only pays once the miss has stopped scanning
//! the directory at all, and then it is worth 6.9×. Shipping the "obvious" fix
//! by itself would have moved the benchmark in the wrong direction.
//!
//! (The first row is from the diagnostic probe recorded in `P-012`, taken over a
//! smaller corpus than the second; it is quoted for its *ratio*, which is the
//! only thing it is asked to show.)
//!
//! # Staleness is a correctness problem here, not a performance one
//!
//! A multi-pack index names its `.idx` files. If one of them is deleted while
//! the index still lists it, a lookup finds an entry pointing into a pack that
//! is not there. So [`crate::repack`] removes it **before** it unlinks the packs
//! it folded, and this module rewrites it from whatever is on disk rather than
//! amending it.
use std::path::{Path, PathBuf};
use std::sync::atomic::AtomicBool;
use crate::error::{Error, Result};
use crate::fs::FsStore;
use crate::odb::count_packs;
/// The file name git gives a multi-pack index, and the only one `gix-odb` looks
/// for (`gix-odb-0.83.0/src/store_impls/dynamic/load_index.rs:716`).
pub(crate) const MULTI_PACK_INDEX: &str = "multi-pack-index";
/// At how many packs a repository gets a multi-pack index without being asked.
///
/// Below this the `O(M)` probe is not what a miss is spending its time on, and
/// the index would be one more file to keep consistent for nothing. Above it,
/// every miss pays `M` binary searches, and `M` is unbounded on a forge that is
/// being pushed to between garbage collections, which is `P-012`'s whole point.
///
/// # This number is also a corruption cliff, and the floor underneath it is 2
///
/// A multi-pack index holds **one deduplicated oid table** across every pack it
/// spans, so an object stored in two packs is recorded against exactly one of
/// them. Any reader that asks it "what does pack `P` hold" gets a list that is
/// short by the objects it attributed elsewhere. `gunnar_pack`'s `PackExtents`
/// asked exactly that and sized entries by the distance between neighbouring
/// offsets, so a short list measured one entry across the object the index hid
/// and the served pack carried surplus bytes both receivers reject —
/// `pack is corrupted (SHA1 mismatch)` from stock git, a trailer mismatch from
/// gitoxide. `gunnar_pack::copy`'s completeness check closes it by holding the
/// list to the pack's own header count.
///
/// **The floor is two packs, not sixteen**, and the two numbers are different
/// things:
///
/// * **2** is the structural floor: the fewest packs a multi-pack index can span
/// at all, and MEASURED oden 2026-08-05 the defect reproduces there —
/// `crates/gunnar-pack/tests/pack_extents.rs` corrupts a 287 691-byte pack by
/// 48 bytes over **two** overlapping packs. No larger pack count is needed and
/// none makes it worse.
/// * **This constant** is what turns that floor into a production floor, because
/// it is the only thing that writes an index nobody asked for. It is why
/// `bench/year` reaches **1139** packs and clones clean — its packs share no
/// object — and why the cliff moved from 16 packs to 8 exactly when this was
/// set to 8.
///
/// So pack count is not the trigger; **an object in two packs** is, and this
/// constant only decides when a store starts having the index that exposes it.
/// MEASURED oden 2026-08-05, the 19 workspace_nordisk repositories rebuilt in the
/// production shape (12 pushes, 12 packs, no `.bitmap`): **19 of 19** hold at
/// least one object in two packs, from 1 (`funnel-core`) to 380 (`nornir`). The
/// shape is not exotic; only the index was missing, at 12 packs against this 16.
pub const MULTI_PACK_INDEX_THRESHOLD: usize = 16;
/// What writing a multi-pack index turned out to do.
///
/// Every field is an applied output, something that is on disk now, rather
/// than a restatement of the request (LAW 2). `written == false` with a nonzero
/// `packs` is the ordinary "there was nothing worth indexing" answer, and it is
/// distinguishable from a failure because a failure is an `Err`.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct MultiPackIndexOutcome {
/// `true` if a `multi-pack-index` file is now in place.
pub written: bool,
/// How many packs it spans; 0 when nothing was written.
pub packs: usize,
/// How many object entries it holds, read back out of the file that landed.
pub objects: u32,
/// Its size on disk.
pub bytes: u64,
/// A previous index was removed, either because it was replaced or because
/// there is no longer enough to index.
pub replaced: bool,
}
impl FsStore {
/// Write (or rewrite) this repository's multi-pack index.
///
/// This is maintenance, not a read-path repair: it costs one pass over every
/// object in every pack (about 100 ms for a million objects across 64 packs
/// on oden), so it belongs to `gunnar gc` and to [`FsStore::repack`], the
/// same places `git multi-pack-index write` belongs in git. Nothing in
/// [`crate::ObjectStore`] ever calls it.
///
/// Fewer than two packs is a no-op that **removes** any index that was
/// there: a single pack has its own `.idx`, and an index left behind after a
/// repack names files that no longer exist.
///
/// The store's own view is refreshed before this returns, so the next lookup
/// goes through the new index rather than through the packs it replaced.
pub fn write_multi_pack_index(&self) -> Result<MultiPackIndexOutcome> {
// The same lock a repack takes: both rewrite the contents of
// `objects/pack`, and a multi-pack index written across a set of packs
// that is being deleted underneath it would name files that are gone.
let _one_writer = self
.repack_lock
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
self.write_multi_pack_index_locked()
}
/// [`FsStore::write_multi_pack_index`] without taking the repack lock, for
/// the one caller that is already holding it, the tail of
/// [`FsStore::repack`]. `std::sync::Mutex` is not reentrant, so calling the
/// public form from in there would deadlock rather than fail.
pub(crate) fn write_multi_pack_index_locked(&self) -> Result<MultiPackIndexOutcome> {
let pack_dir = self.git_dir().join("objects").join("pack");
let existing = pack_dir.join(MULTI_PACK_INDEX);
let indices = indices_in(&pack_dir)?;
if indices.len() < 2 {
let replaced = remove_multi_pack_index(&pack_dir)?;
if replaced {
self.objects().refresh();
}
return Ok(MultiPackIndexOutcome {
written: false,
packs: 0,
objects: 0,
bytes: 0,
replaced,
});
}
let packs = indices.len();
// Named with `repack`'s scratch prefix on purpose, so that a run killed
// between creating this and renaming it leaves its leftover where
// `repack`'s existing sweep already looks (LAW 5).
let scratch = pack_dir.join(format!(
"{}{MULTI_PACK_INDEX}.tmp",
crate::repack::TMP_PREFIX
));
let _ = std::fs::remove_file(&scratch);
{
let file = std::fs::File::create(&scratch)?;
let mut out = std::io::BufWriter::new(&file);
gix_pack::multi_index::write_from_index_paths(
indices,
&mut out,
&mut gix_features::progress::Discard,
&AtomicBool::new(false),
gix_pack::multi_index::write::Options {
object_hash: self.hash_kind(),
},
)
.map_err(|err| Error::Backend(anyhow::Error::new(err)))?;
use std::io::Write as _;
out.flush()?;
drop(out);
// Durable before the rename, or a power cut leaves a truncated index
// in the place readers look first.
file.sync_all()?;
}
// Assert the file that landed, not the call that wrote it. A writer that
// silently produced an empty or short index would leave every one of
// this repository's objects unfindable, and a byte count cannot tell.
let replaced = existing.is_file();
std::fs::rename(&scratch, &existing)?;
let (objects, spanned) = verify_multi_pack_index(&existing, self.hash_kind())?;
if spanned != packs {
return Err(Error::backend(format!(
"the multi-pack index that landed spans {spanned} packs, not the {packs} it was \
written from"
)));
}
// `Option`, and NOT `unwrap_or(0)`. A `stat` that fails renders as
// "0 bytes", which is a size, and an operator reading it has no way to
// tell a multi-pack index that could not be measured from one that came
// out empty. `PushFacts::pack_bytes` carries the same `Option` for the
// same reason and it is the same trap: an absence rendered as a value.
let measured = std::fs::metadata(&existing).map(|m| m.len()).ok();
let bytes = measured.unwrap_or(0);
crate::repack::sync_dir(&pack_dir)?;
self.objects().refresh();
tracing::info!(
// `gunnar::store`, not `gunnar_store::midx`: the module header of
// `gunnar_core::observe` tells an operator that `RUST_LOG=gunnar::store=info`
// selects repack and ref transactions, and this line is one of them.
target: crate::repack::gunnar_core_target::STORE,
packs,
objects,
// `?measured`, so a failed `stat` prints `None` and not `0`.
bytes = ?measured,
"wrote the multi-pack index"
);
Ok(MultiPackIndexOutcome {
written: true,
packs,
objects,
bytes,
replaced,
})
}
/// Write a multi-pack index only if this repository has accumulated enough
/// packs to be paying for it, and report whether one was written.
///
/// Errors are **not** propagated: this runs from [`FsStore::open_or_init`],
/// and a repository on read-only media, or one whose packs another tool is
/// mid-way through rewriting, must still open. A missing index costs speed
/// and nothing else.
pub(crate) fn write_multi_pack_index_if_worthwhile(&self) -> bool {
let pack_dir = self.git_dir().join("objects").join("pack");
if count_packs(&pack_dir) < MULTI_PACK_INDEX_THRESHOLD {
return false;
}
if pack_dir.join(MULTI_PACK_INDEX).is_file() {
// One is already there. Whether it is current is decided by
// `repack()`, which removes it when it invalidates it, not here,
// because "is it current" costs the same as rewriting it.
return false;
}
match self.write_multi_pack_index() {
Ok(outcome) => outcome.written,
Err(err) => {
tracing::warn!(
error = %err,
"could not write the multi-pack index; lookups stay O(packs)"
);
false
}
}
}
}
/// Delete `objects/pack/multi-pack-index` if it is there; report whether it was.
pub(crate) fn remove_multi_pack_index(pack_dir: &Path) -> Result<bool> {
match std::fs::remove_file(pack_dir.join(MULTI_PACK_INDEX)) {
Ok(()) => Ok(true),
Err(err) if err.kind() == std::io::ErrorKind::NotFound => Ok(false),
Err(err) => Err(Error::Io(err)),
}
}
/// Every `.idx` in `pack_dir` whose `.pack` is also present, sorted.
fn indices_in(pack_dir: &Path) -> Result<Vec<PathBuf>> {
let entries = match std::fs::read_dir(pack_dir) {
Ok(entries) => entries,
Err(err) if err.kind() == std::io::ErrorKind::NotFound => return Ok(Vec::new()),
Err(err) => return Err(Error::Io(err)),
};
let mut out = Vec::new();
for entry in entries {
let path = entry?.path();
if path.extension().and_then(|e| e.to_str()) != Some("idx") {
continue;
}
// A `.idx` without its `.pack` is a half-written pack. Naming it would
// put entries in the index that point at a file nobody can open.
if path.with_extension("pack").is_file() {
out.push(path);
}
}
out.sort();
Ok(out)
}
/// Reopen the index that landed and report `(objects, packs spanned)`.
fn verify_multi_pack_index(path: &Path, hash_kind: gix_hash::Kind) -> Result<(u32, usize)> {
let file = gix_pack::multi_index::File::at(path, None)
.map_err(|err| Error::Backend(anyhow::Error::new(err)))?;
if file.object_hash() != hash_kind {
return Err(Error::backend(format!(
"the multi-pack index that landed is {}, not {hash_kind}",
file.object_hash()
)));
}
if file.num_objects() == 0 {
return Err(Error::backend(
"the multi-pack index that landed holds no objects",
));
}
Ok((file.num_objects(), file.num_indices() as usize))
}
// `sync_dir` used to live here too, with a body that dropped an unexpected
// `open` failure the `repack` copy reported. Two writers for one durability
// primitive, already disagreeing (`S-030`, LAW 5); there is one now, in
// `repack`, and this module calls it.