crates/storage-git-gix/src/bitmap/write.rs
//! Building the `.bitmap` a maintenance pass writes beside a pack — git's
//! `pack-bitmap-write.c`, and it lives here because here is where the object
//! database is.
//!
//! **Provenance.** Lifted from
//! `parked-gix-2/gunnar-store-gix/src/bitmap/write.rs` (546 lines). The
//! commit-selection windows, the topological fill and the tree closure are the
//! quarantine's, transcribed there from git. What changed on the lift is named
//! at the bottom of this header.
//!
//! # The split, and why the writer is not in `gunnar-bitmap`
//!
//! `gunnar-bitmap` is the format and the set algebra, and it is deliberately
//! blind (D21, so it stays liftable into gitoxide): it never opens a pack, never
//! resolves an object id and never walks a graph. Its [`Writer`] therefore takes
//! finished bitmaps and serialises them. Deciding *which* commits get one and
//! *what* is in each needs an object database, so it is here.
//!
//! # The honest refusal
//!
//! [`write_for_pack`] answers `Ok(None)` rather than writing a short file
//! whenever the pack cannot carry an exact answer: an empty pack, a pack with no
//! commits, a commit whose parent is in another pack, a tree reaching an object
//! that is not here. Every one of those means *"serve this one by walking"*,
//! which is what every pack did before this existed — and is why the read path
//! must keep the walk rather than trust that a `.bitmap` is always present.
//!
//! A bitmap that is quietly short is the failure this whole area is prone to: it
//! produces a pack of plausible size missing objects the client asked for, and
//! nothing — not `index-pack --strict`, not `fsck` — sees it.
//!
//! # Changed on the lift
//!
//! * `crate::Error`/`ObjectStore` → `anyhow` and `gix_object::Find`, which is
//! what this crate's walk already speaks.
//! * **Classification is a header probe, not a read.** The quarantine inflated
//! every object in the pack to learn its type. `gix_odb::Header::try_header`
//! walks entry headers only, so the type index now costs no inflation at all,
//! and [`fill_tree`] skips reading an object the classification pass already
//! proved is a blob. On a 352 396-object fixture that is the difference
//! between inflating the whole repository twice and inflating only its trees.
use std::collections::HashMap;
use std::path::{Path, PathBuf};
use anyhow::{anyhow, Context, Result};
use gix_hash::ObjectId;
use gix_object::{CommitRefIter, Kind, TagRefIter, TreeRefIter};
use gunnar_bitmap::{Bitmap, PackOrder, Writer, XorPolicy};
use super::path_for;
/// How many of the newest commits are stored unconditionally.
///
/// git's `MUST_REGION`, `pack-bitmap-write.c`. Below this depth the window width
/// is zero, so every commit is selected.
const MUST_REGION: usize = 100;
/// The window width ceiling between [`MUST_REGION`] and [`MIN_REGION`].
///
/// git's `MIN_COMMITS`, and also the floor on the width beyond `MIN_REGION`.
const MIN_COMMITS: usize = 100;
/// Where the window stops growing towards [`MIN_COMMITS`] and starts growing
/// towards [`MAX_COMMITS`]. git's `MIN_REGION`.
const MIN_REGION: usize = 20_000;
/// The widest window, reached deep in history. git's `MAX_COMMITS`.
const MAX_COMMITS: usize = 5_000;
/// One commit's place in the graph, in `.idx` position space.
struct CommitNode {
/// `.idx` position of this commit.
idx_pos: u32,
/// Committer time, for the selection sort. Seconds since the epoch.
when: i64,
/// `.idx` positions of the parents that are in this pack.
parents: Vec<u32>,
/// Whether the commit has more than one parent. Kept rather than derived
/// from `parents.len()`, which counts only the parents that are *present*.
merge: bool,
/// The root tree.
tree: ObjectId,
}
/// What the classification pass learned about every object in the pack, indexed
/// by `.idx` position.
///
/// One byte per object rather than a `HashMap`, because the only questions asked
/// of it are *"is this a blob"* (so [`fill_tree`] can skip a read) and *"which
/// type slot"*, both keyed by a position that is already in hand.
type Kinds = Vec<Kind>;
/// Write a reachability bitmap for the pack `index_path` indexes.
///
/// Returns the path written, or `Ok(None)` when no bitmap could honestly be
/// written. See the module doc: none of those cases is an error.
pub fn write_for_pack<T>(
index_path: &Path,
hash_kind: gix_hash::Kind,
odb: &T,
) -> Result<Option<PathBuf>>
where
T: gix_object::Find + gix_odb::Header,
{
let index = gix_pack::index::File::at(index_path, hash_kind)
.with_context(|| format!("open pack index {}", index_path.display()))?;
// ── positions ───────────────────────────────────────────────────────────
//
// Two position spaces, and confusing them returns a set of the right size
// made of the wrong objects. `.idx` position is rank by object id and is
// what a bitmap *entry* names; pack position is rank by offset in the
// `.pack` and is what the bits inside every bitmap mean. See
// `gunnar_bitmap::pack_order`.
let count = index.num_objects() as usize;
if count == 0 {
return Ok(None);
}
let mut offsets = vec![0u64; count];
let mut oids: Vec<ObjectId> = Vec::with_capacity(count);
for entry in index.iter() {
let at = index
.lookup(entry.oid.as_ref())
.ok_or_else(|| anyhow!("an object the index iterated could not be looked up in it"))?
as usize;
offsets[at] = entry.pack_offset;
oids.push(entry.oid);
}
// `.idx` order is by object id, and `iter()` yields it in that order — but
// sorting is what makes `oids[i]` the object at `.idx` position `i` a
// property of this code rather than of gix's iteration order.
oids.sort_unstable();
let order = PackOrder::from_index_offsets(&offsets);
let idx_of: HashMap<ObjectId, u32> = oids
.iter()
.enumerate()
.map(|(i, id)| (*id, i as u32))
.collect();
// `pack_position` is total over `0..count` by construction, so a failure
// here is a bug in `PackOrder`, not a property of the repository.
let pack_pos = |idx: u32| -> Result<u32> {
order
.pack_position(idx)
.ok_or_else(|| anyhow!(".idx position {idx} has no pack position; the index is short"))
};
// ── classify ────────────────────────────────────────────────────────────
//
// A header probe per object, never an inflation. `try_header` walks entry
// headers and resolves a delta chain's *types* without touching a payload.
let mut by_kind: [Vec<u32>; 4] = Default::default();
let mut kinds: Kinds = Vec::with_capacity(count);
{
for (i, id) in oids.iter().enumerate() {
let Some(header) = odb
.try_header(id)
.map_err(|e| anyhow!("header for {id}: {e}"))?
else {
// In the index but unreadable. Not this function's failure to
// report, but certainly not something to write a bitmap over.
return Ok(None);
};
let kind = header.kind();
kinds.push(kind);
by_kind[slot_of(kind)].push(pack_pos(i as u32)?);
}
}
// ── read the commit graph ───────────────────────────────────────────────
let mut commits: Vec<CommitNode> = Vec::new();
let mut buf = Vec::with_capacity(64 * 1024);
for (i, id) in oids.iter().enumerate() {
if kinds[i] != Kind::Commit {
continue;
}
let i = i as u32;
let Some(data) = find(odb, id, &mut buf)? else {
return Ok(None);
};
let mut iter = CommitRefIter::from_bytes(data.data, hash_kind);
let tree = iter
.tree_id()
.map_err(|e| anyhow!("commit {id} has no tree: {e}"))?;
let mut parents = Vec::new();
let mut n_parents = 0usize;
let mut when = 0i64;
let mut outside = false;
for token in iter {
match token {
Ok(gix_object::commit::ref_iter::Token::Parent { id: parent }) => {
n_parents += 1;
if let Some(p) = idx_of.get(&parent) {
parents.push(*p);
} else {
// A parent outside the pack means this commit's closure
// cannot be expressed in this pack's positions. Refuse
// the whole file rather than store a bitmap that is
// quietly short.
outside = true;
break;
}
}
Ok(gix_object::commit::ref_iter::Token::Committer { signature }) => {
// A committer line whose date does not parse is not worth
// failing a maintenance pass over; it sorts as the epoch,
// which puts it deep in history where the window is widest.
// Selection quality, not correctness.
when = signature.time().map(|t| t.seconds).unwrap_or(0);
break;
}
Ok(_) => {}
Err(e) => return Err(anyhow!("undecodable commit {id}: {e}")),
}
}
if outside {
return Ok(None);
}
commits.push(CommitNode {
idx_pos: i,
when,
parents,
merge: n_parents > 1,
tree,
});
}
if commits.is_empty() {
return Ok(None);
}
// ── which commits get a bitmap ──────────────────────────────────────────
let selected = select_commits(&commits);
// ── reachability, parents first ─────────────────────────────────────────
let Some(bitmaps) = fill_bitmaps(&commits, &selected, odb, &idx_of, &kinds, &pack_pos)? else {
return Ok(None);
};
// ── write ───────────────────────────────────────────────────────────────
let mut writer = Writer::new(hash_kind, index.pack_checksum());
for kind in gunnar_bitmap::Kind::ALL {
let mut positions = std::mem::take(&mut by_kind[kind.slot()]);
// `Ewah::from_set_bits` requires strictly ascending bits, and pack
// position is not the order `.idx` iteration produced them in.
positions.sort_unstable();
writer
.type_bitmap(kind, positions)
.map_err(|e| anyhow!("{e}"))?;
}
// Git's own choice for a fresh write: XOR against the immediately previous
// entry whenever that encodes smaller. Measured on this machine, 103 of 106
// entries in a stock-git fixture use exactly that offset.
writer.xor_policy(XorPolicy::PreviousIfSmaller);
for (idx_pos, bitmap) in bitmaps {
// Flag 1 is git's "reusable"; nothing here reuses a stored bitmap as a
// pack prefix, so claiming it would be a promise nothing keeps.
writer.push_commit(idx_pos, 0, bitmap);
}
let out = path_for(index_path);
let bytes = writer.to_vec().map_err(|e| anyhow!("{e}"))?;
// Written to a sibling and renamed, so a reader never sees a half-file. A
// `.bitmap` that parses over the first half of its entries is not a broken
// file to a reader — the object count is nowhere in it — it is a valid index
// describing fewer commits, which is exactly the quiet under-send this
// module refuses everywhere else.
let tmp = out.with_extension("bitmap.tmp");
std::fs::write(&tmp, &bytes).with_context(|| format!("write {}", tmp.display()))?;
std::fs::rename(&tmp, &out).with_context(|| format!("rename into {}", out.display()))?;
Ok(Some(out))
}
/// gix's decoded kind as a `.bitmap` type slot.
fn slot_of(kind: Kind) -> usize {
match kind {
Kind::Commit => gunnar_bitmap::Kind::Commit.slot(),
Kind::Tree => gunnar_bitmap::Kind::Tree.slot(),
Kind::Blob => gunnar_bitmap::Kind::Blob.slot(),
Kind::Tag => gunnar_bitmap::Kind::Tag.slot(),
}
}
/// One object, inflated, with the error flattened into `anyhow`.
fn find<'a, T: gix_object::Find>(
odb: &T,
id: &gix_hash::oid,
buf: &'a mut Vec<u8>,
) -> Result<Option<gix_object::Data<'a>>> {
odb.try_find(id, buf)
.map_err(|e| anyhow!("read object {id}: {e}"))
}
/// git's `bitmap_writer_select_commits`, over commits already read.
///
/// Returns the `.idx` positions to store, as a list in selection order. Kept
/// separate from the graph reading above so that it can be tested against the
/// constants without a repository.
fn select_commits(commits: &[CommitNode]) -> Vec<u32> {
// Newest first, which is what git's `date_compare` produces and what makes
// the window arithmetic below mean "depth into history".
let mut order: Vec<usize> = (0..commits.len()).collect();
order.sort_by(|&a, &b| {
commits[b]
.when
.cmp(&commits[a].when)
.then_with(|| commits[a].idx_pos.cmp(&commits[b].idx_pos))
});
// Under 100 commits git stores every one of them, and so does this.
if commits.len() < MUST_REGION {
return order.iter().map(|&i| commits[i].idx_pos).collect();
}
let mut selected = Vec::new();
let mut i = 0usize;
loop {
let next = next_commit_index(i);
if i + next >= order.len() {
break;
}
let chosen = if next == 0 {
order[i]
} else {
// git takes the last commit of the window unless a merge appears in
// it, and prefers the merge because its bitmap covers the most.
let mut chosen = order[i + next];
for j in 0..=next {
if commits[order[i + j]].merge {
chosen = order[i + j];
}
}
chosen
};
selected.push(commits[chosen].idx_pos);
i += next + 1;
}
selected
}
/// git's `next_commit_index`: how far past `idx` the next selected commit may
/// be, i.e. the window width at that depth.
///
/// Transcribed rather than invented. The final clamp to [`MIN_COMMITS`] is easy
/// to miss reading it — without it the window would *narrow* again just past
/// [`MIN_REGION`].
fn next_commit_index(idx: usize) -> usize {
if idx <= MUST_REGION {
return 0;
}
if idx <= MIN_REGION {
let offset = idx - MUST_REGION;
return offset.min(MIN_COMMITS);
}
let offset = idx - MIN_REGION;
offset.clamp(MIN_COMMITS, MAX_COMMITS)
}
/// git's `fill_bitmap_commit`, for every selected commit.
///
/// Processes parents-first so a commit's parents are always done before it, and
/// keeps a parent's bitmap only while a child still needs it. Returns `None`
/// when the closure leaves the pack.
#[allow(clippy::type_complexity)]
fn fill_bitmaps<T>(
commits: &[CommitNode],
selected: &[u32],
odb: &T,
idx_of: &HashMap<ObjectId, u32>,
kinds: &Kinds,
pack_pos: &dyn Fn(u32) -> Result<u32>,
) -> Result<Option<Vec<(u32, Bitmap)>>>
where
T: gix_object::Find,
{
let row_of: HashMap<u32, usize> = commits
.iter()
.enumerate()
.map(|(i, c)| (c.idx_pos, i))
.collect();
// Topological, parents first. Iterative rather than recursive: depth is the
// repository's history length, and a recursive walk blows the stack on any
// real project.
let mut order: Vec<usize> = Vec::with_capacity(commits.len());
let mut state = vec![0u8; commits.len()];
for start in 0..commits.len() {
if state[start] != 0 {
continue;
}
let mut stack = vec![(start, 0usize)];
while let Some((row, at)) = stack.pop() {
if at == 0 {
if state[row] == 2 {
continue;
}
state[row] = 1;
}
if at < commits[row].parents.len() {
stack.push((row, at + 1));
let p = row_of[&commits[row].parents[at]];
if state[p] == 0 {
stack.push((p, 0));
}
} else {
state[row] = 2;
order.push(row);
}
}
}
// How many children still need each commit's bitmap, so it can be dropped
// the moment the last one has taken it. Without this the peak is one bitmap
// per commit in the repository, which for a large project is gigabytes.
let mut needed = vec![0usize; commits.len()];
for c in commits {
for p in &c.parents {
needed[row_of[p]] += 1;
}
}
let want: std::collections::HashSet<u32> = selected.iter().copied().collect();
let mut live: HashMap<usize, Bitmap> = HashMap::new();
let mut out: Vec<(u32, Bitmap)> = Vec::with_capacity(selected.len());
let mut scratch = Vec::with_capacity(64 * 1024);
for &row in &order {
let c = &commits[row];
let mut bm = Bitmap::new();
for p in &c.parents {
let prow = row_of[p];
let parent = live.get(&prow).ok_or_else(|| {
anyhow!("a commit was reached before its parent; the topological order is wrong")
})?;
bm.or_with(parent);
}
bm.set(pack_pos(c.idx_pos)?);
if !fill_tree(&c.tree, &mut bm, odb, idx_of, kinds, pack_pos, &mut scratch)? {
return Ok(None);
}
for p in &c.parents {
let prow = row_of[p];
needed[prow] -= 1;
if needed[prow] == 0 {
live.remove(&prow);
}
}
if want.contains(&c.idx_pos) {
out.push((c.idx_pos, bm.clone()));
}
if needed[row] > 0 {
live.insert(row, bm);
}
}
// Entries must be ordered as the commits were selected, not as the
// topological walk produced them, because `XorPolicy::PreviousIfSmaller`
// encodes each against its predecessor and adjacency is what makes that pay.
let mut by_pos: HashMap<u32, Bitmap> = out.into_iter().collect();
let ordered: Vec<(u32, Bitmap)> = selected
.iter()
.filter_map(|p| by_pos.remove(p).map(|b| (*p, b)))
.collect();
if ordered.len() != selected.len() {
return Err(anyhow!("a selected commit produced no bitmap"));
}
Ok(Some(ordered))
}
/// git's `fill_bitmap_tree`: add everything under `tree` that is not already
/// set.
///
/// The early return on an already-set bit is the whole algorithm. A bitmap is
/// closed under reachability, so a set bit means this subtree was already walked
/// by an ancestor commit and re-walking it would be the difference between
/// linear and quadratic.
///
/// Returns `false` if anything reachable is not in the pack.
fn fill_tree<T: gix_object::Find>(
tree: &ObjectId,
bm: &mut Bitmap,
odb: &T,
idx_of: &HashMap<ObjectId, u32>,
kinds: &Kinds,
pack_pos: &dyn Fn(u32) -> Result<u32>,
buf: &mut Vec<u8>,
) -> Result<bool> {
let mut pending = vec![*tree];
while let Some(id) = pending.pop() {
let Some(&idx) = idx_of.get(&id) else {
return Ok(false);
};
let pos = pack_pos(idx)?;
if bm.get(pos) {
continue;
}
bm.set(pos);
// The classification pass already resolved every type in this pack, so
// a blob is known to have no outgoing edges without inflating it. Blobs
// are the overwhelming majority of a real pack, and this is the one line
// that keeps this walk off their payloads.
match kinds[idx as usize] {
Kind::Blob | Kind::Commit => continue,
Kind::Tree | Kind::Tag => {}
}
let Some(data) = find(odb, &id, buf)? else {
return Ok(false);
};
match data.kind {
Kind::Tree => {
for entry in TreeRefIter::from_bytes(data.data, id.kind()) {
let entry =
entry.map_err(|e| anyhow!("undecodable entry in tree {id}: {e}"))?;
// A gitlink names a commit in another repository, which is
// not in this pack and is not meant to be. Following one
// would make `idx_of` miss and refuse the whole bitmap for
// an ordinary repository with a submodule — the exact defect
// `crate::graph` records against the walk.
if entry.mode.is_commit() {
continue;
}
pending.push(entry.oid.to_owned());
}
}
Kind::Tag => {
let target = TagRefIter::from_bytes(data.data, id.kind())
.target_id()
.map_err(|e| anyhow!("tag {id} has no target: {e}"))?;
pending.push(target);
}
Kind::Blob | Kind::Commit => {}
}
}
Ok(true)
}
#[cfg(test)]
mod tests {
use super::*;
/// The window widths are git's, at the depths where git changes them.
///
/// Transcribed constants are exactly the kind of thing that is wrong by one
/// and never noticed, because a bitmap index with slightly the wrong commits
/// selected still works — it is just slower, invisibly.
#[test]
fn the_window_widths_are_gits() {
// Below and at MUST_REGION: every commit.
assert_eq!(next_commit_index(0), 0);
assert_eq!(next_commit_index(100), 0);
// Just past it the window opens one at a time.
assert_eq!(next_commit_index(101), 1);
assert_eq!(next_commit_index(150), 50);
// ...and saturates at MIN_COMMITS.
assert_eq!(next_commit_index(200), 100);
assert_eq!(next_commit_index(20_000), 100);
// Past MIN_REGION the final clamp keeps it from narrowing. Without
// git's `(next > MIN_COMMITS) ? next : MIN_COMMITS` this would be 1.
assert_eq!(next_commit_index(20_001), 100);
assert_eq!(next_commit_index(25_000), 5_000);
assert_eq!(next_commit_index(1_000_000), 5_000);
}
fn node(idx_pos: u32, when: i64, merge: bool) -> CommitNode {
CommitNode {
idx_pos,
when,
parents: Vec::new(),
merge,
tree: gix_hash::Kind::Sha1.null(),
}
}
/// Under 100 commits every one is stored, which is git's early return.
#[test]
fn a_small_repository_stores_every_commit() {
let commits: Vec<CommitNode> = (0..50).map(|i| node(i, i as i64, false)).collect();
assert_eq!(select_commits(&commits).len(), 50);
}
/// Past the threshold the newest 100 are all stored and history is thinned.
///
/// The two assertions are the ones that can each fail alone: storing
/// everything (no thinning) and storing only the tips (no history) both
/// produce a working bitmap file, and only the count tells them apart.
#[test]
fn a_large_repository_stores_every_recent_commit_and_thins_history() {
let n = 1_000u32;
let commits: Vec<CommitNode> = (0..n).map(|i| node(i, i as i64, false)).collect();
let selected = select_commits(&commits);
// Newest 100 by date are idx 900..1000, and all of them are stored.
for pos in 900..1000u32 {
assert!(
selected.contains(&pos),
"recent commit {pos} was not selected"
);
}
assert!(
selected.len() > MUST_REGION,
"nothing beyond the must-region was stored"
);
assert!(
selected.len() < commits.len(),
"every commit was stored, so the window never thinned"
);
}
/// A merge inside a window wins it, because its bitmap covers the most.
#[test]
fn a_merge_is_preferred_within_its_window() {
let n = 400u32;
let merge_at = n - MUST_REGION as u32 - 20;
let commits: Vec<CommitNode> = (0..n).map(|i| node(i, i as i64, i == merge_at)).collect();
let selected = select_commits(&commits);
assert!(
selected.contains(&merge_at),
"the merge at {merge_at} was not preferred; selected {selected:?}"
);
}
}