plugins/native/znippy-plugin-git/src/oid_index.rs
//! `__gunnar_oid__` — the reserved oid index.
//!
//! A raw (non-Arrow) section holding an **`stree`** keyspace over the first eight
//! bytes of every object id, plus, per entry, the full oid, the first lookup row
//! of that object's chunk run, and its object ordinal.
//!
//! ## Why stree and not the stock fst trie
//!
//! Git oids are fixed-width and uniformly random, so they share no prefixes: an
//! fst gets no prefix compression, still walks its automaton byte by byte, and
//! has **no batch path**. `stree` (`znippy-zoomies/src/stree.rs`) is built for
//! sorted fixed-width keys — one cache-line node, branchless AVX2 compare, and a
//! software-pipelined batch traversal. Serving one git pack is thousands of
//! lookups, so the batch path is the whole point.
//!
//! ## The 8-byte prefix is NOT a key — it is a filter
//!
//! Two distinct oids can share their first eight bytes. It is vanishingly
//! unlikely and it is **not impossible**, so the key is treated as what it is: a
//! filter that narrows to a short candidate run, after which the **full oid is
//! compared**. `lookup` is only ever correct because of that comparison;
//! [`GitOidIndex::candidate_run`] exposes the unverified run precisely so a test
//! can prove the verify step is load-bearing rather than decoration.
//!
//! ## Section layout (little-endian)
//!
//! ```text
//! 0 magic b"ZNPYGOID" 8
//! 8 u32 version 4
//! 12 u8 hash code (1=sha1, 2=sha256) 1
//! 13 u8 oid_len (20 or 32) 1
//! 14 u16 header_len (24 or 64) 2 ← was `reserved`, see OidLayout
//! 16 u64 count 8
//! 24 u8 pad [header_len - 24] ← zero, only when header_len > 24
//! HL i64 keys [count] 8*count ← sorted ascending, the stree keyspace
//! u64 rows [count] 8*count ← first lookup row of that oid
//! u32 ords [count] 4*count ← object ordinal (oid-lexicographic)
//! u8 oids [count * oid_len] ← full oid, for the verify step
//! ```
//!
//! ## Where the keyspace sits against the cache line — [`OidLayout`]
//!
//! `header_len` exists because the header offset decides the *cache-line phase*
//! of the key array, and the key array is what `stree`'s leaf scan reads. See
//! [`OidLayout`] for what each value means, what it costs, and — importantly —
//! what it cannot reach.
//!
//! ### Measured: alignment buys 5% fewer cache misses and no time at all
//!
//! oden, 32-core Threadripper PRO 3975WX, 2026-08-07,
//! `--release --no-default-features`, sha1 oids, `examples/oid_align_bench.rs`,
//! three arms, arm order rotated so each is timed first exactly once,
//! `/proc/loadavg` 1-min 0.58–1.30 throughout.
//!
//! **The hypothesis this tested was half right, and the half that was right does
//! not pay.** The prediction was that a 24-byte header makes every `stree` node
//! straddle two lines, "two misses per level instead of one". Two corrections
//! fell out of reading the source before measuring:
//!
//! 1. **The internal nodes are not in this section.** `STree64Mmap` builds them
//! into its own `Vec<[i64; 8]>`; the section holds only the *leaf* layer. So
//! the header can move **one** access per lookup, not one per level.
//! 2. **A 64-byte header alone does nothing.** `Vec<u8>` is align-1 by type.
//! Measured `Compact` phases at 4e6 objects were 40 and 56 on different runs
//! — glibc's 16-mod-64 chunk base plus the header. The allocation has to move
//! too, which is why [`OidLayout::Compact64Alloc`] exists as the control.
//!
//! Counters attributable to the `ordinals_batch` loop alone (a `dry` run with
//! only the lookup call removed is subtracted, so query construction and chunk
//! iteration cancel), 4e6 objects, 6e6 lookups per run, median of four passes,
//! per 1e6 lookups:
//!
//! | counter | compact24 | compact24+align | aligned64 | aligned/compact |
//! |---|---:|---:|---:|---:|
//! | instructions | 838 617 005 | 838 610 396 | 838 561 628 | 1.000 |
//! | cache-references | 31 853 436 | 32 191 979 | 31 976 234 | 1.004 |
//! | **cache-misses** | **14 981 126** | 14 752 419 | **14 206 088** | **0.948** |
//! | dTLB-load-misses | 4 624 378 | 4 620 465 | 4 615 620 | 0.998 |
//! | cycles | 1 390 271 493 | 1 286 488 175 | 1 280 146 067 | 0.921 |
//!
//! The identical `instructions` count is the guard that the three arms really
//! are one code path. The **5.2% cache-miss reduction reproduced in all four
//! passes** (0.944 / 0.947 / 0.953 / 0.956) and the three arms order themselves
//! by phase — 40 → 24 → 0 — exactly as the mechanism predicts. `dTLB` does not
//! move, which it should not: alignment changes lines, not pages. `cycles`
//! points the same way but its per-pass ratios scatter 0.849–0.998, so it is
//! reported and not claimed.
//!
//! **And none of it is visible in time.** 24 cells (4 sizes × 2 hit mixes ×
//! 3 batch sizes), 100 000 queries, 5 runs, 3 rotations: **noise band median
//! 8.2%, p90 30.2%**, and `aligned/compact` geomean **0.998**, range
//! 0.855–1.109 — **0 of 24 cells clear their own band**. Re-run at 4e6 with
//! 1 000 000 queries and 9 runs to tighten the band to **median 5.0%, p90 8.5%**:
//! ratios 0.999–1.052, still 0 of 6 clearing, and the direction is now
//! consistently *against* the aligned arm by ~1%.
//!
//! The 0.77-fewer-misses-per-lookup is real and is worth about 60 ns if it were
//! ever exposed. It is not exposed, and the reason is the thing `stree` was
//! chosen for: `lookup_batch_pipeline` keeps eight queries in flight and
//! prefetches the next level, so the leaf touch overlaps with seven others. A
//! miss that the machine was already hiding does not become time when you
//! remove it.
//!
//! **So the default stays [`OidLayout::Compact`]** — the 40 extra bytes per
//! section and the parse-time copy into an aligned buffer buy a counter, not a
//! latency. The apparatus stays because it is cheap, guarded, and the answer
//! would otherwise have to be re-derived. What this does settle is that the
//! 72–91% of a full-row lookup that [`crate::index_layout`] attributes to the
//! oid step is **not** the header offset, and the next attempt on that step has
//! to look elsewhere — `STree64Mmap`'s own internal-node `Vec<[i64; 8]>` is at
//! glibc's mercy exactly the way this section was, and that one *is* a node per
//! level rather than one leaf touch. It lives in `znippy-zoomies` and is not
//! answerable from this crate.
//!
//! ## The key is order-preserving, and the sign bit is why
//!
//! `i64::from_be_bytes(oid[..8])` — the literal reading of "the first eight bytes
//! as an i64" — is **not** order-preserving over oid bytes: an oid whose first
//! byte is `0x80` or higher goes negative and sorts before every oid starting
//! `0x00..0x7f`, which is roughly half the keyspace on the wrong side. The key
//! here therefore flips the top bit, `(u64::from_be_bytes(first8) ^ (1 << 63)) as
//! i64`, which maps unsigned order onto signed order exactly. Key rank is then
//! oid-lexicographic rank.
//!
//! ## …and the parallel arrays are still not redundant
//!
//! With an order-preserving key it is tempting to drop both parallel arrays and
//! read them off the rank. Only one of the two can go:
//!
//! * `ords` equals the rank for every index [`crate::sections::GitIndexBuilder`]
//! builds, because that is where the ordinal is defined and it numbers the same
//! oid-lexicographic sequence. It is still stored, because [`build_section`] is
//! the lower-level API and its contract does **not** require the caller's
//! ordinal to be a rank — the ordinal is the `__gunnar_reach__` bitmap space,
//! and a caller indexing a subset of a larger archive has ordinals from the
//! larger space. Dropping the array is 4 bytes per object and a narrower
//! contract; it is not free, and it is not done here.
//! * `rows` is **not** the rank and cannot become it. A lookup row is a *chunk*
//! row: an object above `file_split_block_size` occupies several consecutive
//! rows, and the lookup covers **every** path in the archive, not only git
//! objects — an archive holding anything besides the object store has git rows
//! that are not contiguous at all. `rows` is monotonic in rank and equal to it
//! only in the special case of a single-chunk, git-only archive.
use std::alloc::{Layout, alloc, dealloc};
use std::ops::Deref;
use std::path::Path;
use std::ptr::NonNull;
use anyhow::{Result, bail, ensure};
use znippy_common::read_reserved_section_bytes;
use znippy_common::GUNNAR_OID_MODULE;
use znippy_zoomies::stree::STree64Mmap;
use crate::object::GitHashKind;
pub const GIT_OID_MAGIC: [u8; 8] = *b"ZNPYGOID";
/// Bumped 1 → 2 when the key became order-preserving. A v1 section holds the same
/// bytes in the same places but sorted on a different key, so a v2 reader walking
/// it would return wrong rows rather than fail — which is why the reader below
/// requires an **exact** match instead of `<=`.
///
/// Bumped 2 → 3 when byte 14 stopped being `reserved` and became `header_len`.
/// A v2 section has `0` there, which a v3 reader would read as a zero-length
/// header and then walk the magic as keys, so again: exact match, not `<=`.
pub const GIT_OID_VERSION: u32 = 3;
/// The fixed part of the header — magic through `count`. A section's real header
/// is `header_len` bytes and is never shorter than this.
const HEADER_FIXED: usize = 24;
/// Where the key array starts, and therefore how the `stree` keyspace sits
/// against the 64-byte cache line.
///
/// ## What this actually controls, and what it does not
///
/// `stree`'s internal B-tree nodes are 8 × `i64` = one cache line each, but they
/// do **not** live in this section: `STree64Mmap` builds them into its own
/// `Vec<[i64; 8]>`. Nothing in this header can move them. What the section owns
/// is the **leaf layer** — the sorted key array that `find_exact` and
/// `lookup_batch_pipeline` linear-scan (up to `B + 1` = 9 keys) once the tree has
/// routed them to a block. So this enum moves exactly one memory access per
/// lookup: the leaf touch, which is also the coldest one.
///
/// A leaf block is `8 * 8` = 64 bytes. Its phase against the line is
/// `keyspace_base mod 64`, and `keyspace_base` is
/// `allocation_base + header_len` — which is why one arm is not enough to
/// separate the two terms:
///
/// | variant | header | allocation | keyspace phase | leaf lines touched |
/// |---|---:|---|---:|---:|
/// | [`Compact`](OidLayout::Compact) | 24 | `Vec<u8>`, align-1 by type | unknown, not 0 | 2, sometimes 3 |
/// | [`Compact64Alloc`](OidLayout::Compact64Alloc) | 24 | 64-aligned | 24 | 2, sometimes 3 |
/// | [`Aligned64`](OidLayout::Aligned64) | 64 | 64-aligned | **0** | 1, plus the overflow key |
///
/// `Compact64Alloc` is the control that makes the experiment readable: it holds
/// the allocator constant and moves only the offset, so a difference between it
/// and `Compact` is the allocator and a difference between it and `Aligned64` is
/// the phase.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
pub enum OidLayout {
/// 24-byte header, plain `Vec<u8>`. What every section written before this
/// enum existed looks like, and the arm every other arm is measured against.
///
/// `Vec<u8>` is `align_of::<u8>() == 1` *by type*. Large allocations happen
/// to come back 16-byte aligned from glibc, but that is allocator behaviour
/// and not a guarantee — which is exactly why the aligned arms below cannot
/// be built by hoping.
#[default]
Compact,
/// 24-byte header, 64-aligned allocation. Keyspace at phase 24.
Compact64Alloc,
/// 64-byte header, 64-aligned allocation. Keyspace at phase 0 — every
/// `stree` leaf block is exactly one cache line.
Aligned64,
}
impl OidLayout {
pub const fn header_len(self) -> usize {
match self {
OidLayout::Compact | OidLayout::Compact64Alloc => 24,
OidLayout::Aligned64 => 64,
}
}
/// Whether [`GitOidIndex::parse`] must re-home the bytes into a 64-aligned
/// allocation. Not recorded in the section: it is a property of the reader's
/// heap, not of the bytes, and a section written by any arm parses correctly
/// under any of them.
const fn wants_aligned_alloc(self) -> bool {
!matches!(self, OidLayout::Compact)
}
pub const fn name(self) -> &'static str {
match self {
OidLayout::Compact => "compact24",
OidLayout::Compact64Alloc => "compact24+align",
OidLayout::Aligned64 => "aligned64",
}
}
pub const ALL: [OidLayout; 3] =
[OidLayout::Compact, OidLayout::Compact64Alloc, OidLayout::Aligned64];
}
/// A heap buffer whose base address is a multiple of 64.
///
/// `Vec<u8>` cannot promise this — its type alignment is 1 — so an arm that
/// wants a cache-line-phased keyspace has to own its allocation. One `alloc`
/// with an explicit 64-byte `Layout`, one `memcpy`, one `dealloc`.
struct Aligned64Bytes {
ptr: NonNull<u8>,
len: usize,
}
// The buffer is immutable after construction and owned solely by the index.
unsafe impl Send for Aligned64Bytes {}
unsafe impl Sync for Aligned64Bytes {}
impl Aligned64Bytes {
/// Zero-length input still allocates one 64-byte-aligned byte, so the
/// pointer is never dangling and `% 64 == 0` holds unconditionally.
fn copy_of(src: &[u8]) -> Self {
let len = src.len();
let layout = Layout::from_size_align(len.max(1), 64).expect("64-aligned layout");
// SAFETY: `layout` has non-zero size; the null return is checked.
let raw = unsafe { alloc(layout) };
let Some(ptr) = NonNull::new(raw) else {
std::alloc::handle_alloc_error(layout);
};
// SAFETY: `raw` owns `len.max(1)` bytes and `src` is a distinct slice.
unsafe { std::ptr::copy_nonoverlapping(src.as_ptr(), raw, len) };
Self { ptr, len }
}
}
impl Deref for Aligned64Bytes {
type Target = [u8];
fn deref(&self) -> &[u8] {
// SAFETY: `ptr` owns at least `len` initialised bytes for our lifetime.
unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
}
}
impl Drop for Aligned64Bytes {
fn drop(&mut self) {
let layout = Layout::from_size_align(self.len.max(1), 64).expect("64-aligned layout");
// SAFETY: same layout the allocation was made with.
unsafe { dealloc(self.ptr.as_ptr(), layout) };
}
}
/// The section's bytes, however the reader chose to hold them.
enum SectionBytes {
Plain(Vec<u8>),
Aligned(Aligned64Bytes),
}
impl Deref for SectionBytes {
type Target = [u8];
fn deref(&self) -> &[u8] {
match self {
SectionBytes::Plain(v) => v,
SectionBytes::Aligned(a) => a,
}
}
}
/// Number of queries the batch walk keeps in flight. Swept 2026-08-10 on t14s
/// (znippy-zoomies `examples/stree_lab.rs`, 8e6 keys × 200k queries): the
/// fused walk runs 58.2 ns/q at P=8 → 21.9 ns/q at P=64, flat to P=128. The
/// old value 8 came from the historical sweep of the *call* batch size
/// (1/100/1000/10000, saturating at 100) — that sweep never varied this
/// const-generic, and the two had been conflated.
const BATCH_P: usize = 64;
/// One object as the index records it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct OidEntry {
/// Raw object id.
pub oid: Vec<u8>,
/// First row of this object's contiguous chunk run in the sorted lookup
/// sub-index.
pub lookup_row: u64,
/// Position of this object in the archive's oid-lexicographic ordering —
/// the ordinal space `__gunnar_reach__` bitmaps address.
pub ordinal: u32,
}
/// The key an oid maps into: its first eight bytes as a big-endian unsigned
/// integer, with the top bit flipped so that unsigned order becomes signed order.
///
/// The flip is the whole point — `stree` compares `i64`, and without it every oid
/// starting `0x80` or higher sorts before every oid starting `0x00..0x7f`. See the
/// module docs.
///
/// Oids shorter than eight bytes cannot occur (sha1 is 20), but the function is
/// total anyway: it zero-pads rather than panicking.
pub fn key_for_oid(oid: &[u8]) -> i64 {
let mut b = [0u8; 8];
let n = oid.len().min(8);
b[..n].copy_from_slice(&oid[..n]);
(u64::from_be_bytes(b) ^ (1u64 << 63)) as i64
}
/// Serialize the `__gunnar_oid__` section in the default layout. `entries` may
/// be in any order; they are sorted by key here, which is what `stree` requires.
pub fn build_section(entries: &[OidEntry], hash: GitHashKind) -> Result<Vec<u8>> {
build_section_with_layout(entries, hash, OidLayout::default())
}
/// [`build_section`] with the header offset chosen explicitly. The only thing
/// `layout` changes is `header_len` and the zero padding after it — the key,
/// row, ordinal and oid arrays are byte-identical in every layout, which is what
/// makes the arms comparable and what
/// `aligned_and_compact_are_the_same_index_byte_for_byte` asserts.
pub fn build_section_with_layout(
entries: &[OidEntry],
hash: GitHashKind,
layout: OidLayout,
) -> Result<Vec<u8>> {
let header_len = layout.header_len();
let oid_len = hash.oid_len();
for e in entries {
ensure!(
e.oid.len() == oid_len,
"oid length {} does not match hash kind {:?}",
e.oid.len(),
hash
);
}
let mut order: Vec<usize> = (0..entries.len()).collect();
// Sort by (key, full oid) so a duplicate-key run has a deterministic layout.
order.sort_by(|&a, &b| {
key_for_oid(&entries[a].oid)
.cmp(&key_for_oid(&entries[b].oid))
.then_with(|| entries[a].oid.cmp(&entries[b].oid))
});
let n = entries.len();
let mut out = Vec::with_capacity(header_len + n * (8 + 8 + 4 + oid_len));
out.extend_from_slice(&GIT_OID_MAGIC);
out.extend_from_slice(&GIT_OID_VERSION.to_le_bytes());
out.push(hash.code());
out.push(oid_len as u8);
out.extend_from_slice(&(header_len as u16).to_le_bytes());
out.extend_from_slice(&(n as u64).to_le_bytes());
debug_assert_eq!(out.len(), HEADER_FIXED);
out.resize(header_len, 0);
for &i in &order {
out.extend_from_slice(&key_for_oid(&entries[i].oid).to_le_bytes());
}
for &i in &order {
out.extend_from_slice(&entries[i].lookup_row.to_le_bytes());
}
for &i in &order {
out.extend_from_slice(&entries[i].ordinal.to_le_bytes());
}
for &i in &order {
out.extend_from_slice(&entries[i].oid);
}
Ok(out)
}
/// What a successful lookup resolved to.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct OidHit {
/// Index of the entry within the index (its position in key order).
pub entry: usize,
/// First lookup row of the object's chunk run.
pub lookup_row: u64,
/// Object ordinal (the `__gunnar_reach__` bitmap space).
pub ordinal: u32,
}
/// Reader over a `__gunnar_oid__` section.
pub struct GitOidIndex {
bytes: SectionBytes,
header_len: usize,
count: usize,
oid_len: usize,
hash: GitHashKind,
/// `None` for an empty index — `STree64Mmap` requires `count > 0`.
tree: Option<STree64Mmap>,
}
impl GitOidIndex {
/// Parse a section produced by [`build_section`].
///
/// The header width comes out of the section's own `header_len`. Whether the
/// bytes are re-homed into a 64-aligned allocation does **not** — that is a
/// property of this reader's heap, not of the bytes, and it is not
/// recorded anywhere. `parse` infers it: a 64-byte header exists only to put
/// the keyspace on a line boundary, which an arbitrary base would undo, so a
/// `header_len` of 64 implies the aligned allocation. See
/// [`parse_as`](Self::parse_as) for the third arm, whose whole point is that
/// the two are separable.
pub fn parse(bytes: Vec<u8>) -> Result<Self> {
Self::parse_inner(bytes, None)
}
/// [`parse`](Self::parse) with the reader's allocation choice forced to
/// `layout`'s, and the section's own header width checked against it.
///
/// This exists for [`OidLayout::Compact64Alloc`], which is a 24-byte header
/// over a 64-aligned base — indistinguishable on disk from
/// [`OidLayout::Compact`], because the difference is in the heap. It is the
/// control arm of the alignment experiment: it holds the allocator fixed and
/// moves only the header offset.
pub fn parse_as(bytes: Vec<u8>, layout: OidLayout) -> Result<Self> {
Self::parse_inner(bytes, Some(layout))
}
fn parse_inner(bytes: Vec<u8>, want: Option<OidLayout>) -> Result<Self> {
ensure!(bytes.len() >= HEADER_FIXED, "__gunnar_oid__ section truncated");
ensure!(bytes[..8] == GIT_OID_MAGIC, "__gunnar_oid__ bad magic");
let version = u32::from_le_bytes(bytes[8..12].try_into().unwrap());
ensure!(
version == GIT_OID_VERSION,
"__gunnar_oid__ is version {version}, this reader speaks {GIT_OID_VERSION} \
only — v1 sorted its keys on a non-order-preserving key and v2 had no \
header_len, so reading one here would return wrong rows instead of failing"
);
let Some(hash) = GitHashKind::from_code(bytes[12]) else {
bail!("__gunnar_oid__ unknown hash code {}", bytes[12]);
};
let oid_len = bytes[13] as usize;
ensure!(
oid_len == hash.oid_len(),
"__gunnar_oid__ oid_len {oid_len} disagrees with hash {hash:?}"
);
let header_len = u16::from_le_bytes(bytes[14..16].try_into().unwrap()) as usize;
// Only the widths an `OidLayout` can produce. An arbitrary value here
// would silently shift the whole keyspace, which reads as wrong rows
// rather than as an error.
let Some(inferred) = OidLayout::ALL.into_iter().find(|l| l.header_len() == header_len)
else {
bail!(
"__gunnar_oid__ header_len {header_len} is not a layout this reader knows \
(24 or 64)"
);
};
let layout = match want {
Some(w) => {
ensure!(
w.header_len() == header_len,
"__gunnar_oid__ was written with a {header_len}-byte header, cannot be read \
as {} ({} bytes)",
w.name(),
w.header_len()
);
w
}
None => inferred,
};
let count = u64::from_le_bytes(bytes[16..24].try_into().unwrap()) as usize;
let need = header_len
.checked_add(count.checked_mul(8 + 8 + 4 + oid_len).unwrap_or(usize::MAX))
.unwrap_or(usize::MAX);
ensure!(
bytes.len() >= need,
"__gunnar_oid__ declares {count} entries but section is {} bytes (needs {need})",
bytes.len()
);
// A 64-byte header only pays off if the allocation under it is
// 64-aligned too; `Vec<u8>` cannot promise that, so the aligned arms
// re-home the bytes once, at parse.
let bytes = if layout.wants_aligned_alloc() {
SectionBytes::Aligned(Aligned64Bytes::copy_of(&bytes))
} else {
SectionBytes::Plain(bytes)
};
let tree = if count == 0 {
None
} else {
let keys = &bytes[header_len..header_len + count * 8];
Some(STree64Mmap::new_with_stride(keys, count, 8))
};
Ok(Self { bytes, header_len, count, oid_len, hash, tree })
}
/// The layout this section was written in.
pub fn layout(&self) -> OidLayout {
OidLayout::ALL
.into_iter()
.find(|l| l.header_len() == self.header_len && l.wants_aligned_alloc() == self.is_aligned_alloc())
.unwrap_or(OidLayout::Compact)
}
fn is_aligned_alloc(&self) -> bool {
matches!(self.bytes, SectionBytes::Aligned(_))
}
/// Base address of the `stree` keyspace, modulo the cache line.
///
/// This is the whole variable of the alignment experiment, exposed so a
/// guard can assert the arm it thinks it built is the arm it got — a
/// timing difference between two arms that turned out to share a phase
/// would be noise wearing a conclusion's clothes.
pub fn keyspace_phase(&self) -> usize {
self.keys().as_ptr() as usize % 64
}
/// Read the section out of a sealed archive. `Ok(None)` when the archive
/// carries no oid index (i.e. it is not a `git`-format archive).
pub fn open(archive: &Path) -> Result<Option<Self>> {
match read_reserved_section_bytes(archive, GUNNAR_OID_MODULE)? {
Some(b) => Ok(Some(Self::parse(b)?)),
None => Ok(None),
}
}
pub fn len(&self) -> usize {
self.count
}
pub fn is_empty(&self) -> bool {
self.count == 0
}
pub fn hash_kind(&self) -> GitHashKind {
self.hash
}
fn keys(&self) -> &[u8] {
&self.bytes[self.header_len..self.header_len + self.count * 8]
}
/// The key of entry `i`.
pub fn key_at(&self, i: usize) -> i64 {
let off = self.header_len + i * 8;
i64::from_le_bytes(self.bytes[off..off + 8].try_into().unwrap())
}
/// The full oid of entry `i`.
pub fn oid_at(&self, i: usize) -> &[u8] {
let base = self.header_len + self.count * (8 + 8 + 4) + i * self.oid_len;
&self.bytes[base..base + self.oid_len]
}
fn row_at(&self, i: usize) -> u64 {
let off = self.header_len + self.count * 8 + i * 8;
u64::from_le_bytes(self.bytes[off..off + 8].try_into().unwrap())
}
fn ordinal_at(&self, i: usize) -> u32 {
let off = self.header_len + self.count * 16 + i * 4;
u32::from_le_bytes(self.bytes[off..off + 4].try_into().unwrap())
}
/// The **unverified** candidate run for a key: every entry sharing that
/// 8-byte prefix, as `start..end`. Normally length 1; length > 1 is a real
/// prefix collision.
///
/// Exposed so a test can assert that a collision actually produces a run of
/// two and that the verify step is what tells the two oids apart. A caller
/// resolving an oid should use [`lookup`](Self::lookup), never this.
pub fn candidate_run(&self, key: i64) -> std::ops::Range<usize> {
let Some(tree) = self.tree.as_ref() else { return 0..0 };
let Some(pos) = tree.find_exact(key, self.keys()) else { return 0..0 };
self.expand_run(pos, key)
}
/// Widen a hit to the whole run of equal keys. `stree` routes to *a* member
/// of the run; which member is an implementation detail, so both directions
/// are walked rather than assumed.
fn expand_run(&self, pos: usize, key: i64) -> std::ops::Range<usize> {
let mut lo = pos;
while lo > 0 && self.key_at(lo - 1) == key {
lo -= 1;
}
let mut hi = pos + 1;
while hi < self.count && self.key_at(hi) == key {
hi += 1;
}
lo..hi
}
/// Resolve a raw oid. `None` when absent.
///
/// stree narrows to a candidate run; the full oid is then compared against
/// every candidate. Skipping that comparison would return a *different*
/// object's row whenever two oids share their first eight bytes.
pub fn lookup(&self, oid: &[u8]) -> Option<OidHit> {
if oid.len() != self.oid_len {
return None;
}
let tree = self.tree.as_ref()?;
let key = key_for_oid(oid);
let pos = tree.find_exact(key, self.keys())?;
self.verify(pos, key, oid)
}
/// Resolve a hex oid.
pub fn lookup_hex(&self, hex_oid: &str) -> Option<OidHit> {
if hex_oid.len() != self.oid_len * 2 {
return None;
}
let raw = hex::decode(hex_oid).ok()?;
self.lookup(&raw)
}
fn verify(&self, pos: usize, key: i64, oid: &[u8]) -> Option<OidHit> {
for i in self.expand_run(pos, key) {
if self.oid_at(i) == oid {
return Some(OidHit {
entry: i,
lookup_row: self.row_at(i),
ordinal: self.ordinal_at(i),
});
}
}
None
}
/// Resolve many oids at once through stree's software-pipelined batch
/// traversal. This is the path that matters: serving one pack is hundreds to
/// thousands of lookups, and the pipelined walk overlaps their memory
/// latency instead of paying it serially.
///
/// Results are positional — `out[i]` corresponds to `oids[i]`. Every hit is
/// full-oid verified, exactly as in [`lookup`](Self::lookup).
pub fn lookup_batch(&self, oids: &[&[u8]]) -> Vec<Option<OidHit>> {
let Some(tree) = self.tree.as_ref() else { return vec![None; oids.len()] };
let keys: Vec<i64> = oids.iter().map(|o| key_for_oid(o)).collect();
// `lookup_batch_fused`, not `lookup_batch_pipeline`: the pipeline's
// route-sort-scan shape exists for a cold 144 GB OSM mmap, where the
// sort converts random page faults into sequential readahead. This
// keyspace is an in-RAM section, where the sort was measured as a
// ~40 ns/query tax and the leaf misses sat outside the pipeline
// (2026-08-10, stree_lab: pipeline::<8> ~100 ns/q vs fused::<64>
// 21.9 ns/q at 8e6 keys).
let raw = tree.lookup_batch_fused::<BATCH_P>(&keys, self.keys());
// The verify loop below needs no software prefetch — tried and
// reverted 2026-08-10: a 32-query prefetch lag over `oid_at`/`row_at`/
// `ordinal_at` measured 110.0 → 108.5 ns on git_oid_lookup_8m, inside
// noise. The iterations are independent, so the out-of-order window
// already overlaps their three loads across ~10 queries; the misses
// this loop pays were never serial.
raw.into_iter()
.zip(oids.iter())
.enumerate()
.map(|(i, (pos, oid))| {
if oid.len() != self.oid_len {
return None;
}
self.verify(pos?, keys[i], oid)
})
.collect()
}
/// The **baseline** the stree keyspace has to beat: `std::binary_search` over
/// the very same sorted key array, followed by the very same full-oid verify.
///
/// It exists only under `bench-kernels`, and it exists so the choice of stree
/// is a measurement rather than an argument. Anything cheaper than this would
/// not be the same question: it derives the key the same way, expands the
/// equal-key run the same way, and compares the same 20 or 32 bytes — the
/// only difference is how it finds the run.
#[cfg(feature = "bench-kernels")]
pub fn lookup_binary_search(&self, oid: &[u8]) -> Option<OidHit> {
if oid.len() != self.oid_len || self.count == 0 {
return None;
}
let key = key_for_oid(oid);
// The keys live little-endian in `bytes`; read them through `key_at` so
// there is one decoder, not two.
let mut lo = 0usize;
let mut hi = self.count;
while lo < hi {
let mid = lo + (hi - lo) / 2;
if self.key_at(mid) < key { lo = mid + 1 } else { hi = mid }
}
if lo >= self.count || self.key_at(lo) != key {
return None;
}
self.verify(lo, key, oid)
}
/// Hex convenience over [`lookup_batch`](Self::lookup_batch).
pub fn lookup_batch_hex(&self, hex_oids: &[&str]) -> Vec<Option<OidHit>> {
let raw: Vec<Vec<u8>> = hex_oids.iter().map(|h| hex::decode(h).unwrap_or_default()).collect();
let refs: Vec<&[u8]> = raw.iter().map(|v| v.as_slice()).collect();
self.lookup_batch(&refs)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn oid(bytes: &[u8], len: usize) -> Vec<u8> {
let mut v = bytes.to_vec();
v.resize(len, 0);
v
}
fn idx(entries: Vec<OidEntry>, hash: GitHashKind) -> GitOidIndex {
GitOidIndex::parse(build_section(&entries, hash).unwrap()).unwrap()
}
#[test]
fn resolves_every_entry_it_was_built_from() {
// 300 entries → tall enough that stree has real internal layers.
let n = 300usize;
let entries: Vec<OidEntry> = (0..n)
.map(|i| {
let mut o = [0u8; 32];
o[..8].copy_from_slice(&(i as u64).wrapping_mul(0x0123_4567_89ab_cdef).to_be_bytes());
o[8] = (i % 251) as u8;
OidEntry { oid: o.to_vec(), lookup_row: (i * 3) as u64, ordinal: i as u32 }
})
.collect();
let index = idx(entries.clone(), GitHashKind::Sha256);
assert_eq!(index.len(), n);
for e in &entries {
let hit = index.lookup(&e.oid).unwrap_or_else(|| panic!("miss for {}", hex::encode(&e.oid)));
assert_eq!(hit.lookup_row, e.lookup_row);
assert_eq!(hit.ordinal, e.ordinal);
}
// And an oid that is NOT in the index must miss.
let mut absent = entries[0].oid.clone();
absent[31] ^= 0xff;
assert!(index.lookup(&absent).is_none());
}
/// LAW 2 — the collision case, constructed rather than hoped for.
///
/// Two oids that agree on their first eight bytes and differ after. They
/// share one stree key, so the tree alone cannot tell them apart; only the
/// full-oid comparison can. The assertions below are on the *applied
/// output* (the two rows resolved), so an implementation that dropped the
/// verify and returned the first candidate would return the same row twice
/// and fail here.
#[test]
fn eight_byte_prefix_collision_is_resolved_by_the_full_oid() {
let prefix = [0xde, 0xad, 0xbe, 0xef, 0x01, 0x02, 0x03, 0x04];
let mut a = oid(&prefix, 32);
let mut b = oid(&prefix, 32);
a[8] = 0xaa;
b[8] = 0xbb;
assert_eq!(key_for_oid(&a), key_for_oid(&b), "test premise: keys must collide");
assert_ne!(a, b);
// Some filler so the tree is not a single leaf block.
let mut entries = vec![
OidEntry { oid: a.clone(), lookup_row: 100, ordinal: 7 },
OidEntry { oid: b.clone(), lookup_row: 200, ordinal: 9 },
];
for i in 0..64u64 {
let mut o = [0u8; 32];
o[..8].copy_from_slice(&i.wrapping_mul(0x1111_1111_1111_1111).to_be_bytes());
o[9] = 1;
entries.push(OidEntry { oid: o.to_vec(), lookup_row: 900 + i, ordinal: 100 + i as u32 });
}
let index = idx(entries, GitHashKind::Sha256);
// The collision is real in the built index: one key, two candidates.
let run = index.candidate_run(key_for_oid(&a));
assert_eq!(run.len(), 2, "expected a 2-entry candidate run, got {run:?}");
assert_eq!(index.key_at(run.start), index.key_at(run.start + 1));
// Applied output: the two oids resolve to their OWN rows.
let ha = index.lookup(&a).expect("a must resolve");
let hb = index.lookup(&b).expect("b must resolve");
assert_eq!(ha.lookup_row, 100);
assert_eq!(hb.lookup_row, 200);
assert_eq!(ha.ordinal, 7);
assert_eq!(hb.ordinal, 9);
assert_ne!(ha.lookup_row, hb.lookup_row);
// A third oid on the same prefix that was never inserted must MISS —
// a verify-less lookup would happily hand back a candidate's row.
let mut c = oid(&prefix, 32);
c[8] = 0xcc;
assert!(index.lookup(&c).is_none(), "unstored oid on a colliding prefix must miss");
}
#[test]
fn batch_path_agrees_with_the_serial_path_including_on_a_collision() {
let prefix = [0x7f, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff];
let mut a = oid(&prefix, 20);
let mut b = oid(&prefix, 20);
a[8] = 1;
b[8] = 2;
let mut entries = vec![
OidEntry { oid: a.clone(), lookup_row: 11, ordinal: 1 },
OidEntry { oid: b.clone(), lookup_row: 22, ordinal: 2 },
];
for i in 0..200u64 {
let mut o = [0u8; 20];
o[..8].copy_from_slice(&(i.wrapping_mul(0x9e37_79b9_7f4a_7c15)).to_be_bytes());
o[10] = (i % 97) as u8;
entries.push(OidEntry { oid: o.to_vec(), lookup_row: 1000 + i, ordinal: 500 + i as u32 });
}
let index = idx(entries.clone(), GitHashKind::Sha1);
let mut queries: Vec<&[u8]> = entries.iter().map(|e| e.oid.as_slice()).collect();
let absent = oid(&[0xab, 0xcd, 0xef, 0x00, 0x11, 0x22, 0x33, 0x44], 20);
queries.push(&absent);
let batched = index.lookup_batch(&queries);
assert_eq!(batched.len(), queries.len());
for (i, q) in queries.iter().enumerate() {
assert_eq!(batched[i], index.lookup(q), "batch/serial disagree at {i}");
}
assert!(batched.last().unwrap().is_none(), "absent oid must miss in the batch path too");
assert_eq!(batched[0].unwrap().lookup_row, 11);
assert_eq!(batched[1].unwrap().lookup_row, 22);
}
#[test]
fn empty_index_is_a_clean_miss_not_a_panic() {
let index = idx(Vec::new(), GitHashKind::Sha256);
assert!(index.is_empty());
assert!(index.lookup(&oid(&[1], 32)).is_none());
assert_eq!(index.lookup_batch(&[&oid(&[1], 32)[..]]), vec![None]);
}
#[test]
fn truncated_or_mislabelled_sections_are_rejected() {
let entries = vec![OidEntry { oid: oid(&[9], 20), lookup_row: 0, ordinal: 0 }];
let good = build_section(&entries, GitHashKind::Sha1).unwrap();
assert!(GitOidIndex::parse(good.clone()).is_ok());
let mut bad_magic = good.clone();
bad_magic[0] = b'X';
assert!(GitOidIndex::parse(bad_magic).is_err());
let mut newer = good.clone();
newer[8..12].copy_from_slice(&(GIT_OID_VERSION + 1).to_le_bytes());
assert!(GitOidIndex::parse(newer).is_err());
assert!(GitOidIndex::parse(good[..HEADER_FIXED + 4].to_vec()).is_err());
assert!(GitOidIndex::parse(Vec::new()).is_err());
// A header_len no layout can produce would shift the entire keyspace and
// return wrong rows rather than fail, so it is refused by name.
//
// Seen RED by relaxing the reader's `header_len() == header_len` to
// `>=`, which accepts 40 as "close enough to 64" and then reads the
// keyspace 24 bytes past where it was written: the panic below,
// "a header_len no layout can produce must be refused".
let mut bad_header = good.clone();
bad_header[14..16].copy_from_slice(&40u16.to_le_bytes());
let err = match GitOidIndex::parse(bad_header) {
Ok(_) => panic!("a header_len no layout can produce must be refused"),
Err(e) => e.to_string(),
};
assert!(err.contains("header_len 40"), "error must name the width: {err}");
}
/// LAW 2 — the sign-bit trap, asserted on applied output.
///
/// Half of all oids start `0x80..0xff`. Under the literal
/// `i64::from_be_bytes` key those sort *before* every oid starting
/// `0x00..0x7f`, so entry order is not oid order. This asserts entry `i` holds
/// the `i`-th oid lexicographically — which is exactly what fails if the top-
/// bit flip in [`key_for_oid`] is removed, and which a test built only from
/// low-byte oids could never see.
#[test]
fn entry_order_is_oid_lexicographic_across_the_sign_boundary() {
let firsts: [u8; 8] = [0x00, 0x7f, 0x80, 0xff, 0x01, 0xfe, 0x81, 0x7e];
let entries: Vec<OidEntry> = firsts
.iter()
.enumerate()
.map(|(i, &f)| {
let mut o = [0u8; 32];
o[0] = f;
o[1] = i as u8;
OidEntry { oid: o.to_vec(), lookup_row: i as u64, ordinal: i as u32 }
})
.collect();
let index = idx(entries.clone(), GitHashKind::Sha256);
let mut want: Vec<Vec<u8>> = entries.iter().map(|e| e.oid.clone()).collect();
want.sort();
for (i, w) in want.iter().enumerate() {
assert_eq!(
index.oid_at(i),
w.as_slice(),
"entry {i} is {} but the {i}-th oid lexicographically is {}",
hex::encode(index.oid_at(i)),
hex::encode(w)
);
}
// And the keys themselves must be ascending — stree requires it, and an
// unsorted keyspace is the failure that would otherwise surface as an
// occasional wrong row rather than an error.
for i in 1..index.len() {
assert!(
index.key_at(i - 1) < index.key_at(i),
"keys not ascending at {i}: {} then {}",
index.key_at(i - 1),
index.key_at(i)
);
}
// Every oid still resolves to its own row, sign bit or not.
for e in &entries {
assert_eq!(index.lookup(&e.oid).unwrap().lookup_row, e.lookup_row);
}
}
/// A v1 section must be refused, not silently misread: the layout is
/// identical and only the key ordering changed, so a `<=` version check would
/// hand back wrong rows without erroring.
#[test]
fn a_v1_section_is_refused_rather_than_misread() {
let entries = vec![OidEntry { oid: oid(&[0x80], 20), lookup_row: 3, ordinal: 0 }];
let mut v1 = build_section(&entries, GitHashKind::Sha1).unwrap();
v1[8..12].copy_from_slice(&1u32.to_le_bytes());
let err = match GitOidIndex::parse(v1) {
Ok(_) => panic!("a v1 section must be refused"),
Err(e) => e.to_string(),
};
assert!(err.contains("version 1"), "error must name the version: {err}");
}
/// `n` deterministic sha1-width entries with uniformly-spread oids — enough
/// of them that the `stree` has several internal layers and the leaf scan is
/// a real random touch rather than the whole index sitting in one line.
fn spread_entries(n: usize) -> Vec<OidEntry> {
(0..n)
.map(|i| {
let mut o = [0u8; 20];
let mut z = (i as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
o[..8].copy_from_slice(&(z ^ (z >> 31)).to_be_bytes());
o[8..12].copy_from_slice(&(i as u32).to_be_bytes());
OidEntry { oid: o.to_vec(), lookup_row: (i as u64) * 7 + 1, ordinal: i as u32 }
})
.collect()
}
/// LAW 2 — the arm is the arm it says it is, asserted on the **address the
/// hardware sees**, not on the header field that was supposed to produce it.
///
/// A `header_len` of 64 over a `Vec<u8>` is not an aligned keyspace; it is a
/// 64-byte header over whatever the allocator felt like. Asserting
/// `header_len == 64` would pass in that world and the whole experiment
/// would be two arms sharing a cache-line phase.
///
/// Seen RED by making `OidLayout::wants_aligned_alloc` return `false` (so
/// every arm falls back to `Vec<u8>`): "compact24+align keyspace must sit at
/// phase 24 (64-aligned base + 24-byte header), got 40" — 40 being glibc's
/// 16-mod-64 chunk base plus the 24-byte header, which is also what the
/// shipping `Compact` arm gets and precisely the straddle under test.
#[test]
fn each_layout_puts_the_keyspace_where_it_claims() {
let entries = spread_entries(5_000);
let mut phases = Vec::new();
for layout in OidLayout::ALL {
let section = build_section_with_layout(&entries, GitHashKind::Sha1, layout).unwrap();
let index = GitOidIndex::parse_as(section, layout).unwrap();
let phase = index.keyspace_phase();
match layout {
OidLayout::Aligned64 => assert_eq!(
phase, 0,
"aligned64 keyspace must sit at phase 0, got {phase}"
),
OidLayout::Compact64Alloc => assert_eq!(
phase, 24,
"compact24+align keyspace must sit at phase 24 (64-aligned base + 24-byte \
header), got {phase}"
),
// `Compact` is at the allocator's mercy by construction — the
// only thing that can be asserted is that it is not the aligned
// arm, which the pairwise check below does.
OidLayout::Compact => {}
}
assert_eq!(index.layout(), layout);
phases.push(phase);
}
assert_ne!(
phases[0], phases[2],
"compact and aligned64 landed on the same cache-line phase ({}), so there is no \
experiment left to run",
phases[0]
);
assert_ne!(phases[1], phases[2]);
}
/// LAW 2 — the identity guard the alignment experiment stands on.
///
/// Byte-identical payload arrays, and byte-identical **applied output**: the
/// full `(entry, lookup_row, ordinal)` triple for a workload of hits *and*
/// misses, serial and batched, in all three layouts. A faster arm that
/// answered differently would not be a faster arm.
///
/// Seen RED twice, once per half:
///
/// * **the byte-identity half**, by deleting `out.resize(header_len, 0)` from
/// the writer (a header that declares 64 but pads to 24 — the obvious way
/// to get this wrong): "aligned64 moved a payload byte; it is supposed to
/// move only the header".
/// * **the applied-output half**, by building the `stree` from
/// `&bytes[HEADER_FIXED..]` instead of `&bytes[header_len..]` — a leftover
/// constant, which leaves every section byte identical and only misroutes
/// the tree: "aligned64 disagrees with compact24 on the serial path at 8",
/// `None` against `Some(OidHit { entry: 19421, lookup_row: 29, ordinal: 4 })`.
#[test]
fn aligned_and_compact_are_the_same_index_byte_for_byte() {
let entries = spread_entries(20_000);
let hash = GitHashKind::Sha1;
let sections: Vec<Vec<u8>> = OidLayout::ALL
.iter()
.map(|&l| build_section_with_layout(&entries, hash, l).unwrap())
.collect();
// The payload after the header is the same bytes in the same order —
// only the header width differs.
for (i, l) in OidLayout::ALL.iter().enumerate() {
assert_eq!(
§ions[i][l.header_len()..],
§ions[0][OidLayout::Compact.header_len()..],
"{} moved a payload byte; it is supposed to move only the header",
l.name()
);
}
// A workload that is half misses, so the miss path through the tree is
// covered too — a `have` negotiation is mostly misses.
let mut queries: Vec<Vec<u8>> = Vec::new();
for (i, e) in entries.iter().enumerate() {
queries.push(e.oid.clone());
let mut absent = e.oid.clone();
absent[19] ^= 0x5a;
absent[0] ^= if i % 2 == 0 { 0x80 } else { 0x00 };
queries.push(absent);
}
let refs: Vec<&[u8]> = queries.iter().map(|q| q.as_slice()).collect();
let indices: Vec<GitOidIndex> = sections
.into_iter()
.zip(OidLayout::ALL)
.map(|(s, l)| GitOidIndex::parse_as(s, l).unwrap())
.collect();
let base_serial: Vec<Option<OidHit>> = refs.iter().map(|o| indices[0].lookup(o)).collect();
let base_batch = indices[0].lookup_batch(&refs);
assert_eq!(base_serial, base_batch);
let hits = base_serial.iter().filter(|h| h.is_some()).count();
assert_eq!(hits, entries.len(), "premise: every present oid must resolve");
assert!(base_serial.iter().any(|h| h.is_none()), "premise: some queries must miss");
for (i, l) in OidLayout::ALL.iter().enumerate().skip(1) {
for (q, want) in base_serial.iter().enumerate() {
assert_eq!(
&indices[i].lookup(refs[q]),
want,
"{} disagrees with compact24 on the serial path at {q}",
l.name()
);
}
assert_eq!(
indices[i].lookup_batch(&refs),
base_batch,
"{} disagrees with compact24 on the batch path",
l.name()
);
for e in 0..entries.len() {
assert_eq!(indices[i].key_at(e), indices[0].key_at(e));
assert_eq!(indices[i].oid_at(e), indices[0].oid_at(e));
}
}
}
#[test]
fn build_rejects_an_oid_of_the_wrong_width() {
let entries = vec![OidEntry { oid: oid(&[1], 20), lookup_row: 0, ordinal: 0 }];
assert!(build_section(&entries, GitHashKind::Sha256).is_err());
}
}