crates/storage-git-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`).
//!
//! **Provenance.** Lifted from `parked-gix-2/gunnar-store-gix/src/midx.rs`
//! (338 lines). The logic is the quarantine's. What changed on the lift is
//! named at the bottom of this header — nothing else.
//!
//! # Why it earns its filesystem
//!
//! The `.idx` files this folds together *are* this arm's storage format, so a
//! file that indexes them is not a coupling this backend could shed. The
//! no-filesystem rule (`R1`) binds the Arrow arm, which has no `.idx` to index.
//!
//! # 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 (`gix-odb-0.83.0/src/store_impls/dynamic/init.rs:38`, and
//! [`crate::GixStore::open_or_init`] takes that 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 — quoted as history,
//! not as a result on this machine:
//!
//! | | no multi-pack index | with one |
//! |---|---|---|
//! | as that 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.
//!
//! **This ordering is why the lift happens now and not earlier.** [`crate::odb`]
//! landed the `refresh_never()` pool first; this file is the second half, and on
//! its own it would have been a regression.
//!
//! # 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. In the quarantine, `crate::repack` removed it **before** it
//! unlinked the packs it folded. This crate has no `repack`; the equivalent
//! deleter is [`crate::GixStore::gc`], and it takes the same order — see
//! [`remove_multi_pack_index`]'s caller there. This module rewrites the index
//! from whatever is on disk rather than amending it.
//!
//! # The corruption cliff, and why it is closed here
//!
//! 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. A reader that asks it "what does pack `P` hold" gets a list that is
//! short by the objects it attributed elsewhere; sizing entries by the distance
//! between neighbouring offsets then measures one entry *across* the hidden
//! object and the served pack carries surplus bytes both receivers reject —
//! `pack is corrupted (SHA1 mismatch)` from stock git, a trailer mismatch from
//! gitoxide. The floor is **two** packs, not sixteen.
//!
//! That defect is closed in this workspace, in the crate that had it:
//! `gunnar_pack::copy` holds the entry list to the pack's own header count
//! (`crates/gunnar-pack/src/copy.rs:404`, `:463-513`). `examples/git-store-serve.rs`
//! serves through exactly that function, which is why turning this on is safe
//! here and was not safe before that check existed.
//!
//! # Changed on the lift, exhaustively
//!
//! * `FsStore` → [`crate::GixStore`]; `crate::error::{Error, Result}` →
//! `anyhow::Result`; `self.objects().refresh()` → `self.odb.refresh()`.
//! * `self.repack_lock` → [`crate::GixStore::maint_lock`], which [`crate::GixStore::gc`]
//! also takes. Same role, one writer over `objects/pack`.
//! * `crate::repack::TMP_PREFIX` and `crate::repack::sync_dir` do not exist here;
//! both are carried in this file, and [`sweep_stale_scratch`] is what makes the
//! prefix mean something without a `repack` sweep to find the leftovers.
//! * `tracing` target `"gunnar::store"` dropped. This crate is not gunnar and a
//! log line claiming that target would route a lie into an operator's filter.
use std::path::{Path, PathBuf};
use std::sync::atomic::AtomicBool;
use anyhow::{anyhow, Context, Result};
use crate::odb::count_packs;
use crate::GixStore;
/// 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:267`).
pub const MULTI_PACK_INDEX: &str = "multi-pack-index";
/// The prefix every scratch file this crate writes into `objects/pack` carries.
///
/// It is the quarantine's `repack::TMP_PREFIX` verbatim, kept rather than
/// renamed: a store that was written by that code and is now read by this one
/// must have its leftovers recognised by whichever of the two sweeps runs next.
pub(crate) const TMP_PREFIX: &str = "gunnar-repack-";
/// 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.
///
/// MEASURED oden 2026-08-05, quoted as history: the 19 `workspace_nordisk`
/// repositories rebuilt in the production shape (12 pushes, 12 packs, no
/// `.bitmap`) hold, **19 of 19**, at least one object in two packs — from 1
/// (`funnel-core`) to 380 (`nornir`). Pack count is not what exposes the
/// deduplication cliff; an object in two packs is. This constant only decides
/// when a store starts having the index that exposes it, and the cliff itself is
/// closed by `gunnar_pack::copy`'s completeness check (see the module header).
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, or `None` if the `stat` after the rename failed.
///
/// `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.
/// This is the quarantine's own note and it is kept as the field's type
/// rather than as a comment above a `u64`.
pub bytes: Option<u64>,
/// A previous index was removed, either because it was replaced or because
/// there is no longer enough to index.
pub replaced: bool,
}
impl GixStore {
/// 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, so it belongs beside [`GixStore::gc`], the same
/// place `git multi-pack-index write` belongs in git. Nothing on the
/// `GitOps` read path 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
/// sweep 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 `gc` takes: both rewrite the contents of `objects/pack`,
// and an index written across a set of packs that is being deleted
// underneath it would name files that are gone.
let _one_writer = self
.maint_lock
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner);
self.write_multi_pack_index_locked()
}
/// [`GixStore::write_multi_pack_index`] without taking the maintenance lock,
/// for the callers that are already holding it. `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.odb.refresh();
}
return Ok(MultiPackIndexOutcome {
written: false,
packs: 0,
objects: 0,
bytes: None,
replaced,
});
}
let packs = indices.len();
// Named with the scratch prefix on purpose, so that a run killed between
// creating this and renaming it leaves its leftover where
// `sweep_stale_scratch` already looks (LAW 5).
sweep_stale_scratch(&pack_dir);
let scratch = pack_dir.join(format!("{TMP_PREFIX}{MULTI_PACK_INDEX}.tmp"));
let _ = std::fs::remove_file(&scratch);
{
let file = std::fs::File::create(&scratch)
.with_context(|| format!("create {}", scratch.display()))?;
let mut out = std::io::BufWriter::new(&file);
gix_pack::multi_index::write_from_index_paths(
indices,
&mut out,
&mut gix_utils::progress::Discard,
&AtomicBool::new(false),
gix_pack::multi_index::write::Options {
object_hash: self.hash_kind(),
},
)
.map_err(anyhow::Error::new)
.context("write the multi-pack index")?;
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)
.with_context(|| format!("rename into {}", existing.display()))?;
let (objects, spanned) = verify_multi_pack_index(&existing, self.hash_kind())?;
if spanned != packs {
return Err(anyhow!(
"the multi-pack index that landed spans {spanned} packs, not the {packs} it was \
written from"
));
}
let bytes = std::fs::metadata(&existing).map(|m| m.len()).ok();
sync_dir(&pack_dir)?;
// Every pooled handle is `refresh_never()`, so nothing else would ever
// tell them the index appeared. This is the whole point of the write:
// without it the next lookup still probes `M` indices.
self.odb.refresh();
tracing::info!(
packs,
objects,
// `?bytes`, so a failed `stat` prints `None` and not `0`.
bytes = ?bytes,
"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 [`GixStore::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 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 whoever
// deletes packs — `gc` 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
}
}
}
/// Does a `multi-pack-index` exist, and how many packs does it span?
///
/// **A count, not a clock** (§6). It is the only thing that distinguishes a
/// store whose miss path is one binary search from one whose miss path is
/// `M`, and both answer identically — so without it the switch is invisible,
/// which is the `fanout16` mistake this crate has already made once.
pub fn midx_span(&self) -> Option<usize> {
let path = self.git_dir().join("objects").join("pack").join(MULTI_PACK_INDEX);
gix_pack::multi_index::File::at(&path, None)
.ok()
.map(|f| f.num_indices() as usize)
}
}
/// Delete `objects/pack/multi-pack-index` if it is there; report whether it was.
///
/// Called **before** packs are unlinked, never after. See the module header.
pub 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(anyhow::Error::new(err).context("remove the multi-pack index")),
}
}
/// 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(anyhow::Error::new(err).context("read objects/pack")),
};
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(anyhow::Error::new)
.context("reopen the multi-pack index that landed")?;
if file.object_hash() != hash_kind {
return Err(anyhow!(
"the multi-pack index that landed is {}, not {hash_kind}",
file.object_hash()
));
}
if file.num_objects() == 0 {
return Err(anyhow!("the multi-pack index that landed holds no objects"));
}
Ok((file.num_objects(), file.num_indices() as usize))
}
/// fsync a directory, so a rename into it survives a power cut.
///
/// # One writer, because the quarantine had two and they had already diverged
///
/// `repack.rs` and `midx.rs` each carried a copy, and they disagreed: one
/// reported an unexpected `open` failure and the other dropped it, so the same
/// fault was a hard error when a repack renamed a pack into `objects/pack` and
/// nothing at all when the multi-pack index was renamed into the same directory
/// (`S-030`, LAW 5). There is one here. When a `repack` lands in this crate it
/// calls this, it does not grow a second copy.
pub(crate) fn sync_dir(dir: &Path) -> Result<()> {
match std::fs::File::open(dir) {
Ok(file) => {
// Some filesystems refuse to fsync a directory handle. That is a
// durability weakening, not a correctness one (the swap is still
// ordered), so it is not worth failing over — but it is worth
// SAYING, because a systemic one means every rename in the tree is
// unordered against a power cut and nothing else would mention it.
if let Err(err) = file.sync_all() {
tracing::debug!(
dir = %dir.display(),
%err,
"the directory could not be fsynced, so a rename into it is not durable \
against a power cut"
);
}
Ok(())
}
Err(err) if err.kind() == std::io::ErrorKind::NotFound => Ok(()),
Err(err) => Err(anyhow::Error::new(err).context("open the directory to fsync it")),
}
}
/// Remove scratch files a killed run left behind.
///
/// In the quarantine this lived in `repack` and ran on every repack, which is
/// what made writing the scratch under `TMP_PREFIX` mean anything. There is no
/// `repack` here, so the sweep runs at the top of the write that creates the
/// scratch — the leftover is still found by the next run, which is the property
/// the prefix was chosen for.
pub(crate) fn sweep_stale_scratch(pack_dir: &Path) {
let Ok(entries) = std::fs::read_dir(pack_dir) else {
return;
};
for entry in entries.flatten() {
let path = entry.path();
let is_scratch = path
.file_name()
.and_then(|n| n.to_str())
.is_some_and(|n| n.starts_with(TMP_PREFIX));
if is_scratch {
let _ = std::fs::remove_file(&path);
}
}
}