crates/storage-git-gix/parked-gix-2/gunnar-store-gix/src/bitmap.rs
//! The `.bitmap` reachability index: reading one on the serve path, and
//! writing one beside a freshly repacked pack.
//!
//! `crates/gunnar-bitmap` is the format and the set algebra, and it is
//! deliberately blind: it never opens a pack, never resolves an object id and
//! never walks a graph (D21, so it stays liftable into gitoxide). Everything it
//! cannot do is here, because here is where the object database is.
//!
//! # Reading: [`PackBitmap`]
//!
//! Being blind, `gunnar-bitmap` can say what bit 4711 is set to and not what
//! object that is. [`PackBitmap`] is the pairing that gives the bits names: the
//! parsed `.bitmap`, the `.idx` beside it, and the permutation between the two
//! position spaces. It is what [`crate::ObjectStore::bitmap`] hands the serve
//! path, and `gunnar_wire::graph` is what turns it into a `want`/`have` answer.
//!
//! # Writing: [`write`]
//!
//! git's `pack-bitmap-write.c`, transcribed, in its own file because it needs a
//! filesystem to write to and the reader does not. See that module.
use std::collections::HashMap;
use std::path::{Path, PathBuf};
use gix_hash::ObjectId;
use gunnar_bitmap::{Bitmap, PackOrder};
use crate::{Error, Result};
/// git's `pack-bitmap-write.c`. `repack` only, so `fs` only.
#[cfg(feature = "fs")]
pub(crate) mod write;
/// Whether to build a [`crate::fanout::Fanout16`] over a pack's `.idx`.
///
/// **`false` unless `GUNNAR_FANOUT16=on`, and that default is the finding.**
/// The wider fanout makes `pack_position` 3.2–4.4x faster on hits and
/// 7.7–8.6x on misses (MEASURED oden 2026-08-04, seven of the nineteen
/// `workspace_nordisk` mirrors, release, shuffled query order) and moves a
/// negotiated fetch by **1.0016x**, against a within-arm spread of 1.009–1.028.
/// It is a real 3x on a seam that is under a percent of a request, and 256 KiB
/// per open pack is not free on a forge that holds thousands. The whole working
/// is in `.nornir/fanout16-reasoning.md`.
///
/// So this is off by design rather than by omission — the distinction
/// [`crate::ObjectStore::packed`]'s own documentation draws — and the variable
/// exists so the measurement can be retaken in one command rather than rebuilt
/// in a day. It is read per [`PackBitmap::at`] rather than cached, so one
/// process can serve both arms and the A/B rows can be interleaved.
fn fanout16_enabled() -> bool {
matches!(
std::env::var("GUNNAR_FANOUT16").as_deref(),
Ok("on") | Ok("1")
)
}
/// Where a `.bitmap` goes for a given `.idx`.
///
/// `pack-<id>.bitmap`, beside the pack and named for it, which is what
/// `gix-odb` and stock git both look for. `repack`'s own sidecar sweep already
/// lists the `bitmap` extension, so a stale one is unlinked with its pack for
/// free.
pub(crate) fn path_for(index_path: &Path) -> PathBuf {
index_path.with_extension("bitmap")
}
/// A pack's `.bitmap`, paired with the `.idx` that gives its bits names.
///
/// # Why the pairing is the type
///
/// A bitmap on its own answers nothing a server can use. Its bits are pack
/// positions, its entry headers are `.idx` positions, and the object ids live
/// in neither — they are in the `.idx`. Handing the serve path a bare
/// [`gunnar_bitmap::Index`] would push that three-way translation into every
/// caller, and getting it wrong is silent: `pack_order`'s module documentation
/// records a set of the right size made of the wrong objects.
///
/// # Two checks at open, and both of them can fail on a live repository
///
/// * the trailing checksum, because a truncated `.bitmap` parses clean — the
/// object count is nowhere in the file, so lopping the tail off yields a
/// valid-looking index over fewer objects;
/// * the **pack checksum**, because a `.bitmap` names the pack it describes and
/// nothing stops a stale one sitting beside a rewritten pack. Positions would
/// then resolve against the wrong `.idx`, which is the same failure as
/// confusing the two position spaces and just as quiet. `repack` unlinks the
/// sidecar with its pack, so this guards against everything *else* that
/// writes into `objects/pack` — stock git included.
///
/// Either failure is `Ok(None)`: no bitmap, serve by walking, which is what
/// every repository did before this existed.
pub struct PackBitmap {
index: gunnar_bitmap::Index,
idx: gix_pack::index::File,
/// The 16-bit fanout over `idx`, when the pack is big enough to earn its
/// 256 KiB (`crate::fanout::Fanout16::MIN_OBJECTS`).
///
/// Built here rather than per lookup and rather than on disk: `BitmapCache`
/// already re-stats the `.bitmap` on every call and rebuilds this whole type
/// when it moves, so the derived table inherits an invalidation rule that is
/// already known to be right. A sidecar file would need its own, and a stale
/// oid index answers with a *wrong* pack offset rather than a slow one.
fanout: Option<crate::fanout::Fanout16>,
order: PackOrder,
/// `.idx` position → row in [`gunnar_bitmap::Index::entries`].
///
/// `Index::entry_index_of_commit` is a linear scan over the entries, and it
/// says so; a fetch asks it once per want and once per have, so a map built
/// once at open is the difference between `O(wants × entries)` and
/// `O(wants)`.
entry_of: HashMap<u32, usize>,
}
impl std::fmt::Debug for PackBitmap {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("PackBitmap")
.field("objects", &self.idx.num_objects())
.field("stored_bitmaps", &self.index.entries().len())
.finish()
}
}
impl PackBitmap {
/// Open the `.bitmap` beside `index_path`, if there is a usable one.
///
/// `Ok(None)` covers every "no bitmap here" case — absent, damaged, or
/// describing a different pack — because none of them is an error for a
/// server that can always walk instead.
pub fn at(index_path: &Path, hash_kind: gix_hash::Kind) -> Result<Option<Self>> {
Self::at_with(index_path, hash_kind, fanout16_enabled())
}
/// The same, with the 16-bit fanout decided by the caller rather than by the
/// environment.
///
/// It exists because the two searches are **defined** to return the same
/// entry index, so no wire byte, object count or wall clock can tell them
/// apart, and a test that reached the choice by setting an environment
/// variable would be testing `std::env` in a process it shares with every
/// other test. The A/B measurement goes through [`PackBitmap::at`] and
/// asserts [`PackBitmap::uses_fanout16`]; this is how a test names the arm.
pub fn at_with(
index_path: &Path,
hash_kind: gix_hash::Kind,
fanout16: bool,
) -> Result<Option<Self>> {
let bitmap_path = path_for(index_path);
if !bitmap_path.exists() {
return Ok(None);
}
let idx = gix_pack::index::File::at(index_path, hash_kind)
.map_err(|err| Error::Backend(anyhow::Error::new(err)))?;
let data = std::fs::read(&bitmap_path)?;
let index = match gunnar_bitmap::Index::from_bytes(&data, hash_kind) {
Ok(index) => index,
Err(err) => {
tracing::warn!(
error = %err,
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack could not be parsed; serving by walking"
);
return Ok(None);
}
};
if let Err(err) = index.verify_checksum() {
tracing::warn!(
error = %err,
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack failed its own checksum; serving by walking"
);
return Ok(None);
}
if index.pack_checksum() != idx.pack_checksum() {
tracing::warn!(
bitmap = %bitmap_path.display(),
"a .bitmap beside this pack describes a different pack; serving by walking"
);
return Ok(None);
}
let count = idx.num_objects() as usize;
let mut offsets = vec![0u64; count];
for entry in idx.iter() {
let at = idx.lookup(entry.oid.as_ref()).ok_or_else(|| {
Error::backend("an object the index iterated could not be looked up in it")
})? as usize;
offsets[at] = entry.pack_offset;
}
let order = PackOrder::from_index_offsets(&offsets);
let entry_of = index
.entries()
.iter()
.enumerate()
.map(|(row, e)| (e.commit_index_pos, row))
.collect();
let fanout = if fanout16 {
crate::fanout::Fanout16::build(&idx)
} else {
None
};
Ok(Some(PackBitmap {
index,
idx,
fanout,
order,
entry_of,
}))
}
/// Objects in the pack this bitmap describes.
///
/// Also the first position an out-of-pack object may be given: see
/// `gunnar_wire`'s extended index.
pub fn num_objects(&self) -> u32 {
self.idx.num_objects()
}
/// How many commits have a stored bitmap.
pub fn stored_bitmaps(&self) -> usize {
self.index.entries().len()
}
/// Pack position of `id`, or `None` when it is not in this pack.
pub fn pack_position(&self, id: &gix_hash::oid) -> Option<u32> {
gunnar_pack::oidprobe::bump(&gunnar_pack::oidprobe::BITMAP_PACK_POSITION);
self.order.pack_position(self.entry_index(id)?)
}
/// The `.idx` entry index of `id`, through the 16-bit fanout when there is
/// one and through git's own 8-bit one when there is not.
///
/// The single place either search is chosen, so the two callers cannot come
/// to disagree about which one a repository is being served with.
#[inline]
fn entry_index(&self, id: &gix_hash::oid) -> Option<u32> {
match &self.fanout {
Some(f) => f.lookup(&self.idx, id),
None => self.idx.lookup(id),
}
}
/// Whether this pack is being served through the 16-bit fanout.
///
/// Exposed because "the fanout is on" is not observable from a wire byte or
/// a wall clock — both paths are defined to return the same entry index —
/// so an A/B measurement that did not assert this would be two runs of the
/// same arm (LAW 2).
pub fn uses_fanout16(&self) -> bool {
self.fanout.is_some()
}
/// Lookups answered through the 16-bit fanout since this bitmap was opened.
///
/// **Debug builds only**, and `0` everywhere else — see
/// [`crate::fanout::Fanout16::probes`] for why the counter cannot be paid
/// for in release. It is the only evidence that the table built at open is
/// the one the serve path reads, because the two searches are defined to
/// return the same entry index and therefore agree on every observable
/// output.
pub fn fanout16_probes(&self) -> u64 {
self.fanout
.as_ref()
.map_or(0, crate::fanout::Fanout16::probes)
}
/// Bytes the 16-bit fanout occupies for this pack, zero when there is none.
pub fn fanout16_resident_bytes(&self) -> usize {
self.fanout
.as_ref()
.map_or(0, crate::fanout::Fanout16::resident_bytes)
}
/// The `.idx` this bitmap is paired with, for a test that wants to hold the
/// two searches to the same answers over the whole table.
pub fn index_file(&self) -> &gix_pack::index::File {
&self.idx
}
/// The object at pack position `pos`.
///
/// `None` for a position past the end of the pack: a bitmap's last word can
/// carry trailing bits that address nothing.
pub fn oid_at_pack_position(&self, pos: u32) -> Option<ObjectId> {
let index_pos = self.order.index_position(pos)?;
(index_pos < self.idx.num_objects()).then(|| self.idx.oid_at_index(index_pos).to_owned())
}
/// The stored bitmap for `id`, if it has one.
///
/// The returned bitmap is addressed by **pack** position and is closed under
/// reachability: a set bit means everything beneath that object is set too,
/// which is what lets a walk stop the moment it reaches a commit that has
/// one.
pub fn bitmap_for_commit(&self, id: &gix_hash::oid) -> Option<Bitmap> {
gunnar_pack::oidprobe::bump(&gunnar_pack::oidprobe::BITMAP_FOR_COMMIT);
let index_pos = self.entry_index(id)?;
self.index.resolve(*self.entry_of.get(&index_pos)?)
}
/// The objects in `set` that are of `kind`.
///
/// Not one object is opened: which of a selection's positions are commits
/// is a fact the `.bitmap`'s four type indexes already carry, which is what
/// lets a caller name the commits in a pack it decided on by set algebra.
/// Positions past the end of the pack — the caller's extended index — are
/// dropped, because the type indexes say nothing about them.
pub fn of_type(&self, set: &Bitmap, kind: gix_object::Kind) -> Vec<ObjectId> {
gunnar_bitmap::Reachability::new(&self.index)
.of_type(set, kind)
.iter_set_bits()
.filter_map(|pos| self.oid_at_pack_position(pos))
.collect()
}
}
/// The one [`PackBitmap`] a store hands out, reloaded when the file on disk
/// changes.
///
/// # Why a cache at all
///
/// Opening one means mapping the `.idx`, reading and parsing the whole
/// `.bitmap`, and building the pack-order permutation — `O(objects)` work, and
/// on a million-object repository that is tens of megabytes touched. A fetch
/// asks once. Paying it per fetch would make the bitmap path *slower* than the
/// walk it replaces on everything but a clone, which is the shape of
/// optimisation that ships and then gets reverted.
///
/// # Why it cannot go stale
///
/// The key is `(path, mtime, len)` of the `.bitmap` itself, re-stat'ed on every
/// call. A repack writes a new pack under a new name, so the path changes; a
/// `gc` that rewrites in place changes both other fields. A stale bitmap is not
/// a slow answer, it is a **wrong** one — positions resolving against the wrong
/// `.idx` — so the cheap check is not optional. [`PackBitmap::at`] then checks
/// the pack checksum as well, which is the same question asked of the content
/// rather than of the metadata.
///
/// A `None` is cached too. A repository with no bitmap, or with a damaged one,
/// must not re-`read_dir` and re-parse on every request to rediscover that.
#[derive(Debug, Default)]
pub struct BitmapCache {
inner: std::sync::RwLock<Option<Cached>>,
}
#[derive(Debug)]
struct Cached {
key: Key,
/// `None` means "there is no usable bitmap here", cached deliberately.
bitmap: Option<std::sync::Arc<PackBitmap>>,
}
#[derive(Debug, PartialEq, Eq)]
struct Key {
index_path: PathBuf,
mtime: Option<std::time::SystemTime>,
len: u64,
}
impl BitmapCache {
/// The bitmap for the pack directory `pack_dir`, loading or reloading it if
/// what is on disk has changed.
///
/// `None` when there is not exactly one `.bitmap` in the directory. Zero is
/// the ordinary case for a repository that has never been repacked. More
/// than one is a repository whose packs were bitmapped separately, and
/// choosing between them is a decision with no right answer here: the two
/// address different position spaces and neither covers the other's
/// objects, which is what a multi-pack index exists to fix.
pub fn get(
&self,
pack_dir: &Path,
hash_kind: gix_hash::Kind,
) -> Option<std::sync::Arc<PackBitmap>> {
let mut found: Option<PathBuf> = None;
for entry in std::fs::read_dir(pack_dir).ok()?.flatten() {
let path = entry.path();
if path.extension().is_some_and(|x| x == "bitmap") {
if found.is_some() {
return None;
}
found = Some(path);
}
}
let bitmap_path = found?;
let meta = std::fs::metadata(&bitmap_path).ok()?;
let key = Key {
index_path: bitmap_path.with_extension("idx"),
mtime: meta.modified().ok(),
len: meta.len(),
};
if let Ok(guard) = self.inner.read() {
if let Some(cached) = guard.as_ref() {
if cached.key == key {
return cached.bitmap.clone();
}
}
}
let loaded = PackBitmap::at(&key.index_path, hash_kind)
.map_err(|err| {
tracing::warn!(
error = %err,
pack = %key.index_path.display(),
"a .bitmap beside this pack could not be opened; serving by walking"
);
})
.ok()
.flatten()
.map(std::sync::Arc::new);
if let Ok(mut guard) = self.inner.write() {
*guard = Some(Cached {
key,
bitmap: loaded.clone(),
});
}
loaded
}
}