crates/storage-git-gix/parked-gix-2/gunnar-store-gix/src/bitmap/write.rs
//! Building the `.bitmap` `repack()` writes, which is git's
//! `pack-bitmap-write.c` and lives here because here is where the object
//! database is.
//!
//! Split from the reader half rather than sharing a file with it because the
//! writer needs a filesystem to write to and the reader does not: the reader
//! is behind [`crate::ObjectStore::bitmap`], which is on the trait
//! unconditionally, and a `mem`-only build must not pay for a repack it cannot
//! run. See the parent module for what git does and what this does.
use std::collections::HashMap;
use gix_hash::ObjectId;
use gix_object::{CommitRefIter, Kind, TagRefIter, TreeRefIter};
use gunnar_bitmap::{Bitmap, PackOrder, Writer, XorPolicy};
use std::path::{Path, PathBuf};
use super::path_for;
use crate::object::ObjectStore;
use crate::{Error, Result};
/// 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,
}
/// Write a reachability bitmap for the pack `index_path` indexes.
///
/// Returns the path written, or `Ok(None)` when no bitmap could honestly be
/// written — an empty pack, a pack with no commits, or a closure that reaches
/// outside the pack. None of those is an error: they mean "serve this one by
/// walking", which is what happens today for every pack.
pub(crate) fn write_for_pack(
index_path: &Path,
hash_kind: gix_hash::Kind,
objects: &dyn ObjectStore,
) -> Result<Option<PathBuf>> {
let index = gix_pack::index::File::at(index_path, hash_kind)
.map_err(|err| Error::Backend(anyhow::Error::new(err)))?;
// ── 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(|| {
Error::backend("an object the index iterated could not be looked up in it")
})? as usize;
offsets[at] = entry.pack_offset;
oids.push(entry.oid);
}
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(|| {
Error::backend(format!(
".idx position {idx} has no pack position; the index is short"
))
})
};
// ── classify, and read the commit graph ─────────────────────────────────
let mut by_kind: [Vec<u32>; 4] = Default::default();
let mut commits: Vec<CommitNode> = Vec::new();
let mut buf = Vec::with_capacity(64 * 1024);
for (i, id) in oids.iter().enumerate() {
let i = i as u32;
let Some(data) = objects.read(id, &mut buf)? else {
// In the index but unreadable. Not this function's failure to
// report — `verify_pack_holds` runs before it — but it is certainly
// not something to write a bitmap over.
return Ok(None);
};
let slot = match data.kind {
Kind::Commit => 0,
Kind::Tree => 1,
Kind::Blob => 2,
Kind::Tag => 3,
};
by_kind[slot].push(pack_pos(i)?);
if data.kind == Kind::Commit {
let mut iter = CommitRefIter::from_bytes(data.data, data.object_hash);
let tree = iter.tree_id().map_err(|err| Error::CorruptObject {
oid: *id,
reason: format!("commit has no tree: {err}"),
})?;
let mut parents = Vec::new();
let mut n_parents = 0usize;
let mut when = 0i64;
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.
return Ok(None);
}
}
Ok(gix_object::commit::ref_iter::Token::Committer { signature }) => {
// A committer line whose date does not parse is not
// worth failing a repack 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(err) => {
return Err(Error::CorruptObject {
oid: *id,
reason: format!("undecodable commit: {err}"),
})
}
}
}
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, oldest first ──────────────────────────────────────────
let bitmaps = match fill_bitmaps(&commits, &selected, objects, &idx_of, &pack_pos, &mut buf)? {
Some(b) => b,
None => return Ok(None),
};
// ── write ───────────────────────────────────────────────────────────────
let pack_checksum = index.pack_checksum();
let mut writer = Writer::new(hash_kind, pack_checksum);
for (slot, kind) in [Kind::Commit, Kind::Tree, Kind::Blob, Kind::Tag]
.into_iter()
.enumerate()
{
let mut positions = std::mem::take(&mut by_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(|err| Error::Backend(err.into()))?;
}
// 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"; gunnar does not yet reuse 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(|err| Error::Backend(err.into()))?;
std::fs::write(&out, &bytes)?;
Ok(Some(out))
}
/// git's `bitmap_writer_select_commits`, over commits already read.
///
/// Returns the `.idx` positions to store, as a set. 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;
// `clamp` rather than `min().max()`: identical here because
// MIN_COMMITS (100) < MAX_COMMITS (5000) are constants, and clippy's
// `manual_clamp` is denied by `xtask ci`.
offset.clamp(MIN_COMMITS, MAX_COMMITS)
}
/// git's `fill_bitmap_commit`, for every selected commit.
///
/// Processes oldest-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(
commits: &[CommitNode],
selected: &[u32],
objects: &dyn ObjectStore,
idx_of: &HashMap<ObjectId, u32>,
pack_pos: &dyn Fn(u32) -> Result<u32>,
buf: &mut Vec<u8>,
) -> Result<Option<Vec<(u32, Bitmap)>>> {
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());
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(|| {
Error::backend(
"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, objects, idx_of, pack_pos, buf)? {
return Ok(None);
}
for p in &c.parents {
let prow = row_of[p];
needed[prow] -= 1;
if needed[prow] == 0 && !live.contains_key(&prow) {
continue;
}
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(Error::backend("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(
tree: &ObjectId,
bm: &mut Bitmap,
objects: &dyn ObjectStore,
idx_of: &HashMap<ObjectId, u32>,
pack_pos: &dyn Fn(u32) -> Result<u32>,
buf: &mut Vec<u8>,
) -> Result<bool> {
let mut pending = vec![*tree];
let mut scratch = Vec::with_capacity(16 * 1024);
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);
let Some(data) = objects.read(&id, &mut scratch)? else {
return Ok(false);
};
match data.kind {
Kind::Tree => {
for entry in TreeRefIter::from_bytes(data.data, data.object_hash) {
let entry = entry.map_err(|err| Error::CorruptObject {
oid: id,
reason: format!("undecodable tree entry: {err}"),
})?;
// A gitlink names a commit in another repository, which is
// not in this pack and is not meant to be.
if entry.mode.is_commit() {
continue;
}
pending.push(entry.oid.to_owned());
}
}
Kind::Tag => {
let target = TagRefIter::from_bytes(data.data, data.object_hash)
.target_id()
.map_err(|err| Error::CorruptObject {
oid: id,
reason: format!("tag has no target: {err}"),
})?;
pending.push(target);
}
Kind::Blob | Kind::Commit => {}
}
}
let _ = buf;
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();
let selected = select_commits(&commits);
assert_eq!(selected.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;
// One merge, placed inside the first window past the must-region.
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:?}"
);
}
}