crates/storage-git-gix/src/packs.rs
//! The pack set: every `.idx`/`.pack` pair under `objects/pack`, with the one
//! table that makes a **verbatim** read possible.
//!
//! # Why this is not `gix-odb`
//!
//! `GitOps::get` promises *"the pack entry, header and all, byte for byte as the
//! client sent them"*. `gix-odb` cannot answer that question. Its `Find` returns
//! a **decoded** object, and the only way it knows how long an entry is, is to
//! run the entry's zlib stream to its end — which is `P-025` in the charred
//! record, *"the serve path inflated every object in the repository to find out
//! how long its entry was"*. The gunnar-side triage files `P-025` as
//! `DEAD — gix` because the Arrow store no longer calls that API. This crate
//! **does** link gix, so the finding is live here, and this module is the answer
//! to it.
//!
//! The answer is the same one `gunnar-pack`'s `PackExtents` reaches for, and it
//! is arithmetic rather than decompression: a packfile's entries are contiguous,
//! so **the successor of an offset is where its entry ends**. `.idx` gives every
//! offset; sorting them gives every length; the last entry ends at
//! `pack_end()`. One sort per pack per open, then `get` is two binary searches
//! and a slice of an mmap. Nothing inflates.
//!
//! The contiguity is checked rather than assumed — `install` refuses a pack
//! whose offsets are not **strictly** ascending, because a duplicate offset
//! would yield a zero-length entry and put a truncated deflate stream on the
//! wire.
use std::path::{Path, PathBuf};
use anyhow::{Context, Result};
use git_storage_trait::{Extent, ObjType};
use crate::fanout::Fanout16;
/// One `.idx` + `.pack` pair, plus the sorted-offset table read off the index.
pub struct Pack {
/// Dense id, assigned in load order. Stable only within one `PackSet`.
pub id: u64,
pub index: gix_pack::index::File,
pub data: gix_pack::data::File,
/// Every entry offset in this pack, **strictly** ascending. The successor of
/// an offset is where that entry ends; the last one ends at `data.pack_end()`.
offsets: Vec<u64>,
/// The 16-bit fanout, when this pack is over [`Fanout16::MIN_OBJECTS`] and
/// the caller asked for one. `None` means every lookup here goes through
/// `.idx`'s own 8-bit fanout, which is the default — see [`crate::fanout`]
/// for why the default is off.
fanout16: Option<Fanout16>,
pub idx_path: PathBuf,
pub data_path: PathBuf,
}
/// Where one object's bytes are and what they are, without inflating anything.
pub struct Located {
pub pack_id: u64,
pub extent: Extent,
pub obj_type: ObjType,
/// The entry header's own size field. For a base type that **is** the
/// object's size; for a delta it is the size of the delta instructions, and
/// the caller must resolve the chain to learn the real one.
pub header_size: u64,
pub is_delta: bool,
}
/// What one entry names as its delta base, if anything.
///
/// The two spellings are not interchangeable and the difference is the whole
/// reason [`crate::serve`] exists in the shape it does: an `OFS_DELTA` names a
/// **position** — valid only inside the pack it was written into — and a
/// `REF_DELTA` names an **object**, which survives being copied anywhere.
pub enum BaseRef {
/// Not a delta.
None,
/// An absolute offset **into the same pack**. Already resolved from the
/// stored backwards distance, because a distance is meaningless once the
/// entry is copied somewhere else.
Ofs(u64),
/// A base named by object id, which may live in another pack or nowhere.
Ref(gix_hash::ObjectId),
}
/// One entry in the terms a pack **emitter** needs, borrowed out of the mmap.
///
/// Nothing here is inflated and nothing is copied: `stored` and `payload` are
/// slices of the mapped `.pack`, and `stated_size` is read off the entry's own
/// header rather than out of a neighbouring column — for a delta those are
/// different numbers (the header carries the length of the delta stream, the
/// index carries the size after the chain is applied), and re-encoding a delta
/// header with the resolved size produces a pack `git index-pack --strict`
/// rejects with `inflate returned 1`.
pub struct EmitParts<'a> {
/// This entry's offset in its own pack — the key other entries name it by.
pub offset: u64,
/// The type **as stored**, so a delta is `OfsDelta`/`RefDelta`.
pub obj_type: ObjType,
/// The size this entry's own header states.
pub stated_size: u64,
pub base: BaseRef,
/// Header and payload, verbatim.
pub stored: &'a [u8],
/// The compressed payload alone — everything after the entry header.
pub payload: &'a [u8],
}
impl Pack {
fn open(idx_path: PathBuf, hash: gix_hash::Kind, fanout16: bool) -> Result<Option<Self>> {
let data_path = idx_path.with_extension("pack");
if !data_path.exists() {
// An `.idx` with no `.pack` is not an error — `index_pack` writes the
// pack first and a crash between the two leaves exactly this. It is
// a pack that holds nothing reachable, so skipping it is correct.
return Ok(None);
}
let index = gix_pack::index::File::at(&idx_path, hash)
.with_context(|| format!("open pack index {}", idx_path.display()))?;
let data = gix_pack::data::File::at(&data_path, hash)
.with_context(|| format!("open pack data {}", data_path.display()))?;
let mut offsets = index.sorted_offsets();
offsets.sort_unstable();
// STRICTLY ascending, or the length arithmetic below is wrong. See the
// module doc: a duplicate offset means a zero-length entry.
if offsets.windows(2).any(|w| w[0] >= w[1]) {
anyhow::bail!(
"pack {} has non-strictly-ascending entry offsets; \
its entry lengths cannot be derived and a verbatim read of it \
would emit truncated deflate streams",
data_path.display()
);
}
let fanout16 = fanout16.then(|| Fanout16::build(&index)).flatten();
Ok(Some(Pack {
id: 0,
index,
data,
offsets,
fanout16,
idx_path,
data_path,
}))
}
/// This pack's entry index for `id`, through the widest fanout it has.
///
/// **The single seam the A/B runs through.** Both searches are defined to
/// return the same index — that is [`crate::fanout::equivalent`]'s whole
/// job — so nothing downstream can tell the arms apart, and a `Fanout16`
/// that is built and never consulted is invisible. Routing every lookup
/// through one function is what stops that: there is no second place a
/// `.idx` lookup happens.
#[inline]
pub fn entry_index(&self, id: &gix_hash::oid) -> Option<u32> {
match &self.fanout16 {
Some(f) => f.lookup(&self.index, id),
None => self.index.lookup(id),
}
}
/// Does this pack carry a 16-bit fanout? Observable because nothing else
/// about it is.
pub fn uses_fanout16(&self) -> bool {
self.fanout16.is_some()
}
/// Bytes the 16-bit fanout occupies here — 256 KiB, or 0.
pub fn fanout16_resident_bytes(&self) -> usize {
self.fanout16.as_ref().map_or(0, Fanout16::resident_bytes)
}
/// Lookups answered through the 16-bit fanout. **Debug builds only** —
/// always 0 in release. See [`crate::fanout::Fanout16`]'s field docs.
pub fn fanout16_probes(&self) -> u64 {
self.fanout16.as_ref().map_or(0, Fanout16::probes)
}
/// Where `id`'s entry starts and ends, in this pack. `None` if absent.
///
/// Two binary searches and no I/O beyond the mmap already faulted in.
fn range(&self, id: &gix_hash::oid) -> Option<std::ops::Range<u64>> {
self.range_at(self.offset_of(id)?)
}
/// Where the entry that **starts at** `start` ends.
///
/// The offset-keyed half of [`Pack::range`], for the one caller that has an
/// offset and no object id: an `OFS_DELTA`'s base is named by position, and
/// resolving it through an id would need a reverse index this does not keep.
/// `None` if `start` is not an entry boundary, which is the check that keeps
/// a corrupt backwards distance from slicing the middle of a deflate stream.
fn range_at(&self, start: u64) -> Option<std::ops::Range<u64>> {
let ord = self.offsets.binary_search(&start).ok()?;
let end = match self.offsets.get(ord + 1) {
Some(next) => *next,
// The last entry runs to the start of the trailing hash.
None => self.data.pack_end() as u64,
};
Some(start..end)
}
/// Where `id`'s entry starts in this pack.
pub fn offset_of(&self, id: &gix_hash::oid) -> Option<u64> {
Some(self.index.pack_offset_at_index(self.entry_index(id)?))
}
/// Everything [`crate::serve`]'s emitter needs about the entry at `offset`.
///
/// Keyed by offset rather than by id on purpose — see [`Pack::range_at`].
pub fn emit_parts_at(&self, offset: u64) -> Option<EmitParts<'_>> {
use gix_pack::data::entry::Header as H;
let r = self.range_at(offset)?;
let entry = self.data.entry(offset).ok()?;
let (obj_type, _) = map_kind(&entry.header)?;
let base = match &entry.header {
// Resolved here, once, into an absolute offset. A backwards distance
// that underflows is a corrupt entry and `checked_sub` says so by
// refusing rather than by wrapping into a plausible offset.
H::OfsDelta { base_distance } => BaseRef::Ofs(offset.checked_sub(*base_distance)?),
H::RefDelta { base_id } => BaseRef::Ref(*base_id),
_ => BaseRef::None,
};
Some(EmitParts {
offset,
obj_type,
stated_size: entry.decompressed_size,
base,
stored: self.data.entry_slice(r.clone())?,
payload: self.data.entry_slice(entry.data_offset..r.end)?,
})
}
/// Every entry offset in this pack, paired with the object at it.
///
/// The reverse of the `.idx`, which only maps id → offset. Built on demand
/// and never kept: it costs one pass over the index and `num_objects()`
/// entries of memory, and the only caller is the emitter, which needs it
/// exactly when an `OFS_DELTA` base has to be de-duplicated against an
/// object the caller named by id. See [`crate::serve`] for why that
/// duplicate is real here rather than theoretical.
pub fn offset_to_oid(&self) -> std::collections::HashMap<u64, gix_hash::ObjectId> {
self.index.iter().map(|e| (e.pack_offset, e.oid)).collect()
}
/// The verbatim entry bytes, borrowed straight out of the mmap.
///
/// Borrowed, not cloned — `GitOps::get` has to own them because `Stored`
/// owns a `Vec<u8>`, but everything up to that final copy is zero-copy, and
/// `has`/`size`/`extents` never make it.
pub fn entry_bytes(&self, id: &gix_hash::oid) -> Option<(&[u8], Extent)> {
let r = self.range(id)?;
let extent = (r.start, r.end - r.start);
self.data.entry_slice(r).map(|b| (b, extent))
}
pub fn locate(&self, id: &gix_hash::oid) -> Option<Located> {
let r = self.range(id)?;
let entry = self.data.entry(r.start).ok()?;
let (obj_type, is_delta) = map_kind(&entry.header)?;
Some(Located {
pack_id: self.id,
extent: (r.start, r.end - r.start),
obj_type,
header_size: entry.decompressed_size,
is_delta,
})
}
pub fn contains(&self, id: &gix_hash::oid) -> bool {
self.entry_index(id).is_some()
}
pub fn num_objects(&self) -> u32 {
self.index.num_objects()
}
/// Every oid in this pack, in index order.
pub fn oids(&self) -> impl Iterator<Item = gix_hash::ObjectId> + '_ {
(0..self.index.num_objects()).map(|i| self.index.oid_at_index(i).to_owned())
}
/// `.pack` + `.idx` bytes on disk.
pub fn disk_bytes(&self) -> u64 {
let f = |p: &Path| std::fs::metadata(p).map(|m| m.len()).unwrap_or(0);
f(&self.data_path) + f(&self.idx_path)
}
}
/// gix's pack entry header, mapped onto the contract's six codes.
///
/// `None` for a header the contract has no code for. There is no such header in
/// pack v2 — the mapping is total — but returning `Option` rather than a default
/// keeps the "a wrong type in an index is worse than an honest failure" rule the
/// trait states on `ObjType::from_code`.
fn map_kind(h: &gix_pack::data::entry::Header) -> Option<(ObjType, bool)> {
use gix_pack::data::entry::Header as H;
Some(match h {
H::Commit => (ObjType::Commit, false),
H::Tree => (ObjType::Tree, false),
H::Blob => (ObjType::Blob, false),
H::Tag => (ObjType::Tag, false),
H::OfsDelta { .. } => (ObjType::OfsDelta, true),
H::RefDelta { .. } => (ObjType::RefDelta, true),
})
}
/// Every pack under one `objects/pack` directory.
pub struct PackSet {
pub packs: Vec<Pack>,
}
/// Whether [`PackSet::load`] builds 16-bit fanouts, read from the environment.
///
/// **Off unless `GIX_FANOUT16=on`.** The lifted module's own record says the
/// micro-win did not survive to the wire (see [`crate::fanout`]), and a 256 KiB
/// per-pack table that buys nothing measurable is not a default. The switch
/// exists so a bench arm can move it; nothing else reads it.
fn fanout16_default() -> bool {
std::env::var_os("GIX_FANOUT16").is_some_and(|v| v == "on" || v == "1")
}
impl PackSet {
/// Scan `pack_dir` and open every `.idx` in it.
///
/// A pack with a `.keep` beside it is opened like any other — `.keep` guards
/// it from *collection*, not from *reading*, and an object that just arrived
/// must be readable before the ref pointing at it is applied.
pub fn load(pack_dir: &Path, hash: gix_hash::Kind) -> Result<Self> {
Self::load_with(pack_dir, hash, fanout16_default())
}
/// [`PackSet::load`], with the 16-bit fanout forced on or off.
///
/// The A/B seam. A benchmark arm that wants the wide fanout says so here
/// rather than through the environment, so the two arms can exist in one
/// process and be compared without a re-exec.
pub fn load_with(pack_dir: &Path, hash: gix_hash::Kind, fanout16: bool) -> Result<Self> {
let mut idx_paths: Vec<PathBuf> = Vec::new();
if pack_dir.is_dir() {
for entry in std::fs::read_dir(pack_dir)
.with_context(|| format!("read {}", pack_dir.display()))?
{
let p = entry?.path();
if p.extension().is_some_and(|e| e == "idx") {
idx_paths.push(p);
}
}
}
// Load order decides pack ids, so it has to be deterministic across
// opens or a `TxId.pack_id` handed out before a restart would name a
// different pack after it.
idx_paths.sort();
let mut packs = Vec::with_capacity(idx_paths.len());
for (i, p) in idx_paths.into_iter().enumerate() {
if let Some(mut pack) = Pack::open(p, hash, fanout16)? {
pack.id = i as u64;
packs.push(pack);
}
}
Ok(PackSet { packs })
}
/// Packs in this set carrying a 16-bit fanout, and the bytes they cost.
pub fn fanout16_footprint(&self) -> (usize, usize) {
(
self.packs.iter().filter(|p| p.uses_fanout16()).count(),
self.packs.iter().map(Pack::fanout16_resident_bytes).sum(),
)
}
/// The first pack holding `id`, searched in pack-id order.
///
/// O(packs) on a **miss**, which is `P-012`'s first half and is live in this
/// crate the way it is not in the Arrow one. It is bounded by
/// `packs.len()` binary searches over mmapped fanout tables and costs no
/// syscall; the finding's real teeth were the loose-object `statx` and the
/// pack-directory rescan (`P-028`, `P-029`), and neither happens here
/// because this set is loaded once and never watches the directory.
pub fn find(&self, id: &gix_hash::oid) -> Option<&Pack> {
self.packs.iter().find(|p| p.contains(id))
}
/// [`PackSet::find`], answering with the entry offset the same search
/// already computed.
///
/// One `.idx` binary search instead of two. `find(..)` followed by
/// `offset_of(..)` walks the fanout twice for the same object, and the
/// emitter asks this question once per object in a clone.
pub fn find_entry(&self, id: &gix_hash::oid) -> Option<(&Pack, u64)> {
self.packs.iter().find_map(|p| Some((p, p.offset_of(id)?)))
}
pub fn total_objects(&self) -> u64 {
self.packs.iter().map(|p| u64::from(p.num_objects())).sum()
}
pub fn disk_bytes(&self) -> u64 {
self.packs.iter().map(Pack::disk_bytes).sum()
}
}