use std::path::{Path, PathBuf};
use flate2::{Decompress, FlushDecompress, Status};
use gix_pack::data::{Entry, entry::Header};
use knot_types::Oid;
use super::BitPosition;
use super::revindex::Order;
use knot_git::GitError;
/// git stops at 4095 deep (50 by default), which makes a chain this long a loop.
const MAX_CHAIN: usize = 10_000;
const CACHE_SLOTS: usize = 64;
pub(crate) struct Packs {
maps: Vec<memmap2::Mmap>,
kind: gix::hash::Kind,
}
impl Packs {
pub(crate) fn of_index(index: &Path, kind: gix::hash::Kind) -> Result<Self, GitError> {
Self::open([index.with_extension("pack")], kind)
}
pub(crate) fn of_midx(
midx: &gix_pack::multi_index::File,
kind: gix::hash::Kind,
) -> Result<Self, GitError> {
let dir = midx.path().parent().unwrap_or(Path::new("."));
let paths = midx
.index_names()
.iter()
.map(|name| dir.join(name).with_extension("pack"));
Self::open(paths, kind)
}
fn open(
paths: impl IntoIterator<Item = PathBuf>,
kind: gix::hash::Kind,
) -> Result<Self, GitError> {
let maps = paths
.into_iter()
.map(|path| {
let failed = |error: std::io::Error| {
GitError::Backend(format!("map {}: {error}", path.display()))
};
let file = std::fs::File::open(&path).map_err(failed)?;
// packs are not rewritten once an index names them, and the mapped bytes stay put.
let map = unsafe { memmap2::Mmap::map(&file) }.map_err(failed)?;
if !map.starts_with(b"PACK") {
return Err(GitError::Backend(format!(
"{} isn't a pack",
path.display()
)));
}
Ok(map)
})
.collect::<Result<_, _>>()?;
Ok(Self { maps, kind })
}
/// a delta takes its base's kind, and an ofs-delta's base comes earlier in bit order.
pub(crate) fn kinds<R: Order>(
&self,
rev: &R,
kinds: &mut [Option<gix::object::Kind>],
) -> Result<(), GitError> {
let unknown = kinds.iter().filter(|kind| kind.is_none()).count();
if unknown == 0 {
return Ok(());
}
let len = kinds.len();
let place_at = |bit: usize| rev.placement_at_bit(BitPosition::new(bit as u32));
// many unknowns are cheaper with a places table than a search for each.
let places: Option<Vec<(u32, u64)>> =
(unknown > len / 64).then(|| (0..len).map(place_at).collect());
let place = |bit: usize| {
places
.as_ref()
.map_or_else(|| place_at(bit), |places| places[bit])
};
let bit_of = |wanted: (u32, u64)| {
let bit = partition(len, |bit| place(bit) < wanted);
(bit < len && place(bit) == wanted).then_some(bit)
};
let mut chain = Vec::new();
for bit in 0..kinds.len() {
let corrupt = |message: String| GitError::Corrupt {
oid: rev.oid_at_bit(BitPosition::new(bit as u32)),
message,
};
// an ofs-delta base can be a copy the midx took from another pack, which has no bit.
let (mut at, mut here) = (Some(bit), place(bit));
chain.clear();
let mut steps = 0;
let kind = loop {
if let Some(at) = at {
if let Some(kind) = kinds[at] {
break kind;
}
chain.push(at);
}
steps += 1;
if steps > MAX_CHAIN {
return Err(corrupt("delta chain loops".to_string()));
}
match self.entry(rev, here).map_err(corrupt)? {
(_, Some(base)) => (at, here) = (bit_of(base), base),
(entry, None) => {
break entry
.header
.as_kind()
.ok_or_else(|| corrupt("an entry of no kind".to_string()))?;
}
}
};
for at in &chain {
kinds[*at] = Some(kind);
}
}
Ok(())
}
fn entry<R: Order>(
&self,
rev: &R,
(pack, offset): (u32, u64),
) -> Result<(Entry, Option<(u32, u64)>), String> {
let header = self
.map(pack)?
.get(usize::try_from(offset).map_err(|_| "offset past the pack")?..)
.ok_or("offset past the pack")?;
let entry = Entry::from_bytes(header, offset, self.kind.len_in_bytes())
.map_err(|error| error.to_string())?;
let base = match entry.header {
Header::OfsDelta { base_distance } => Some((
pack,
entry
.checked_base_pack_offset(base_distance)
.ok_or("ofs-delta base before the pack")?,
)),
Header::RefDelta { base_id } => {
let position = rev
.index_of(Oid::from(base_id))
.ok_or_else(|| format!("ref-delta base {base_id} isn't indexed"))?;
Some(rev.placement(position))
}
_ => None,
};
Ok((entry, base))
}
fn map(&self, pack: u32) -> Result<&[u8], String> {
self.maps
.get(pack as usize)
.map(|map| &map[..])
.ok_or_else(|| format!("pack {pack} isn't indexed"))
}
}
/// `below` must be true for a prefix of `0..len`, the search relies on it.
fn partition(len: usize, below: impl Fn(usize) -> bool) -> usize {
let (mut low, mut high) = (0, len);
while low < high {
let mid = low + (high - low) / 2;
if below(mid) {
low = mid + 1;
} else {
high = mid;
}
}
low
}
struct Cached {
pack: u32,
offset: u64,
kind: gix::object::Kind,
data: Vec<u8>,
}
pub(crate) struct Reader<'a, R> {
packs: &'a Packs,
rev: &'a R,
inflate: Decompress,
chain: Vec<(u32, u64, u64)>,
delta: Vec<u8>,
scratch: Vec<u8>,
cache: Vec<Option<Cached>>,
}
impl<'a, R: Order> Reader<'a, R> {
pub(crate) fn new(packs: &'a Packs, rev: &'a R) -> Self {
Self {
packs,
rev,
inflate: Decompress::new(true),
chain: Vec::new(),
delta: Vec::new(),
scratch: Vec::new(),
cache: (0..CACHE_SLOTS).map(|_| None).collect(),
}
}
pub(crate) fn packs(&self) -> &'a Packs {
self.packs
}
pub(crate) fn rev(&self) -> &'a R {
self.rev
}
pub(crate) fn kind(&self) -> gix::hash::Kind {
self.packs.kind
}
pub(crate) fn tree(&mut self, bit: BitPosition, out: &mut Vec<u8>) -> Result<(), GitError> {
let rev = self.rev;
let (pack, offset) = rev.placement_at_bit(bit);
let corrupt = |message: String| GitError::Corrupt {
oid: rev.oid_at_bit(bit),
message,
};
match self.object((pack, offset), out) {
Ok(gix::object::Kind::Tree) => Ok(()),
Ok(kind) => Err(corrupt(format!("a {kind} where a tree was named"))),
Err(message) => Err(corrupt(message)),
}
}
fn object(
&mut self,
wanted: (u32, u64),
out: &mut Vec<u8>,
) -> Result<gix::object::Kind, String> {
let (mut pack, mut offset) = wanted;
self.chain.clear();
let kind = loop {
if self.chain.len() > MAX_CHAIN {
return Err("delta chain loops".to_string());
}
if let Some(kind) = self.cached(pack, offset, out) {
break kind;
}
let (entry, base) = self.packs.entry(self.rev, (pack, offset))?;
if let Some(base) = base {
self.chain
.push((pack, entry.data_offset, entry.decompressed_size));
(pack, offset) = base;
continue;
}
let kind = entry.header.as_kind().ok_or("an entry of no kind")?;
let map = self.packs.map(pack)?;
inflate(
&mut self.inflate,
map,
entry.data_offset,
entry.decompressed_size,
out,
)?;
break kind;
};
if self.chain.is_empty() {
return Ok(kind);
}
for index in (0..self.chain.len()).rev() {
let (pack, at, size) = self.chain[index];
let map = self.packs.map(pack)?;
inflate(&mut self.inflate, map, at, size, &mut self.delta)?;
apply(out, &self.delta, &mut self.scratch)?;
std::mem::swap(out, &mut self.scratch);
}
self.keep(wanted, kind, out);
Ok(kind)
}
fn slot(pack: u32, offset: u64) -> usize {
let mixed = (offset ^ u64::from(pack).rotate_left(40)).wrapping_mul(0x9e37_79b9_7f4a_7c15);
(mixed >> 58) as usize % CACHE_SLOTS
}
fn cached(&self, pack: u32, offset: u64, out: &mut Vec<u8>) -> Option<gix::object::Kind> {
let cached = self.cache[Self::slot(pack, offset)].as_ref()?;
if cached.pack != pack || cached.offset != offset {
return None;
}
out.clear();
out.extend_from_slice(&cached.data);
Some(cached.kind)
}
fn keep(&mut self, (pack, offset): (u32, u64), kind: gix::object::Kind, object: &[u8]) {
let slot = &mut self.cache[Self::slot(pack, offset)];
let mut data = slot.take().map(|cached| cached.data).unwrap_or_default();
data.clear();
data.extend_from_slice(object);
*slot = Some(Cached {
pack,
offset,
kind,
data,
});
}
}
fn inflate(
inflate: &mut Decompress,
map: &[u8],
at: u64,
size: u64,
out: &mut Vec<u8>,
) -> Result<(), String> {
let input = usize::try_from(at)
.ok()
.and_then(|at| map.get(at..))
.ok_or("entry data past the pack")?;
let size = usize::try_from(size).map_err(|_| "entry too large")?;
out.clear();
out.try_reserve(size).map_err(|error| error.to_string())?;
out.resize(size, 0);
inflate.reset(true);
let status = inflate
.decompress(input, out, FlushDecompress::Finish)
.map_err(|error| error.to_string())?;
if status != Status::StreamEnd || inflate.total_out() != size as u64 {
return Err("entry inflates to another size".to_string());
}
Ok(())
}
fn apply(base: &[u8], delta: &[u8], out: &mut Vec<u8>) -> Result<(), String> {
let (base_len, delta) = delta_size(delta)?;
if base_len != base.len() {
return Err("delta base of another size".to_string());
}
let (result_len, mut delta) = delta_size(delta)?;
out.clear();
out.try_reserve(result_len)
.map_err(|error| error.to_string())?;
while let Some((&op, rest)) = delta.split_first() {
delta = rest;
if op & 0x80 != 0 {
let mut field = |bits: std::ops::Range<u8>| -> Result<usize, String> {
let mut value = 0;
for bit in bits.clone() {
if op & (1 << bit) != 0 {
let (&byte, rest) = delta.split_first().ok_or("truncated delta copy")?;
delta = rest;
value |= usize::from(byte) << (8 * (bit - bits.start));
}
}
Ok(value)
};
let start = field(0..4)?;
let size = match field(4..7)? {
0 => 0x10000,
size => size,
};
let copied = start
.checked_add(size)
.and_then(|end| base.get(start..end))
.ok_or("delta copy past its base")?;
out.extend_from_slice(copied);
} else if op != 0 {
let (inserted, rest) = delta
.split_at_checked(usize::from(op))
.ok_or("truncated delta insert")?;
out.extend_from_slice(inserted);
delta = rest;
} else {
return Err("delta opcode 0".to_string());
}
}
if out.len() != result_len {
return Err("delta result of another size".to_string());
}
Ok(())
}
fn delta_size(delta: &[u8]) -> Result<(usize, &[u8]), String> {
let mut size = 0usize;
for (index, byte) in delta.iter().enumerate() {
let shift = 7 * index;
if shift >= usize::BITS as usize {
return Err("delta size overflows".to_string());
}
size |= usize::from(byte & 0x7f) << shift;
if byte & 0x80 == 0 {
return Ok((size, &delta[index + 1..]));
}
}
Err("truncated delta size".to_string())
}
#[cfg(test)]
mod tests {
use std::io::Write as _;
use std::path::Path;
use std::process::Stdio;
use super::*;
use crate::bitmap::revindex::OrderTable;
use crate::midx_rev::tests::git;
use knot_git::Repo;
fn transfer(source: &Path, target: &Path, revs: &str, by_id: bool, thin: bool) -> String {
let mut pack = crate::test_git()
.current_dir(source)
.args(["pack-objects", "--revs", "--stdout", "-q"])
.arg(if by_id {
"--no-delta-base-offset"
} else {
"--delta-base-offset"
})
.args(thin.then_some("--thin"))
.stdin(Stdio::piped())
.stdout(Stdio::piped())
.spawn()
.unwrap();
pack.stdin
.take()
.unwrap()
.write_all(revs.as_bytes())
.unwrap();
let indexed = crate::test_git()
.current_dir(target)
.args(["index-pack", "--stdin"])
.args(thin.then_some("--fix-thin"))
.stdin(pack.stdout.take().unwrap())
.output()
.unwrap();
assert!(
pack.wait().unwrap().success() && indexed.status.success(),
"{revs}"
);
let name = String::from_utf8(indexed.stdout).unwrap();
format!("pack-{}.pack", name.trim().trim_start_matches("pack\t"))
}
fn reads_by_place(target: &Path, format: &str, indices: u32) {
let repo = Repo::open(target).unwrap();
let kind = repo.object_format().kind();
let midx =
gix_pack::multi_index::File::at(repo.objects_dir().join("pack/multi-pack-index"), None)
.unwrap();
assert_eq!(midx.num_indices(), indices);
let packs = Packs::of_midx(&midx, kind).unwrap();
let rev = OrderTable::from_file(midx);
let mut reader = Reader::new(&packs, &rev);
let listed = git(
target,
&[
"cat-file",
"--batch-all-objects",
"--batch-check=%(objecttype) %(objectname)",
],
"",
);
let (mut by_id, mut by_offset, mut out) = (0, 0, Vec::new());
for line in listed.lines().filter_map(|line| line.strip_prefix("tree ")) {
let oid = gix::ObjectId::from_hex(line.as_bytes()).unwrap();
let position = rev.index_of(Oid::from(oid)).unwrap();
let (pack, offset) = rev.placement(position);
let header = &packs.maps[pack as usize][offset as usize..];
match Entry::from_bytes(header, offset, kind.len_in_bytes())
.unwrap()
.header
{
Header::RefDelta { .. } => by_id += 1,
Header::OfsDelta { .. } => by_offset += 1,
_ => {}
}
reader.tree(rev.bit_at_index(position), &mut out).unwrap();
let gix = repo.git().find_object(oid).unwrap();
assert_eq!(out, gix.data, "{format} tree {oid}");
}
assert!(
by_id > 0 && by_offset > 0,
"{format}: {by_id} ref, {by_offset} ofs deltas"
);
let mut git_kinds = vec![None; rev.len()];
for line in listed.lines() {
let (kind, oid) = line.split_once(' ').unwrap();
let oid = gix::ObjectId::from_hex(oid.as_bytes()).unwrap();
let bit = rev.bit_at_index(rev.index_of(Oid::from(oid)).unwrap());
git_kinds[bit.get() as usize] = gix::object::Kind::from_bytes(kind.as_bytes()).ok();
}
let mut every = vec![None; rev.len()];
packs.kinds(&rev, &mut every).unwrap();
assert_eq!(every, git_kinds, "{format}: every kind read");
let mut few = git_kinds.clone();
for kind in few.iter_mut().skip(1).step_by(97) {
*kind = None;
}
packs.kinds(&rev, &mut few).unwrap();
assert_eq!(few, git_kinds, "{format}: a few kinds read");
}
#[test]
fn trees_read_by_place_match_gix() {
for format in ["sha1", "sha256"] {
let dir = tempfile::tempdir().unwrap();
let (source, target) = (dir.path().join("source"), dir.path().join("target"));
for path in [&source, &target] {
std::fs::create_dir(path).unwrap();
let object_format = format!("--object-format={format}");
git(
path,
&["init", "--bare", "-q", "-b", "main", &object_format],
"",
);
}
let history: String = (0..90)
.map(|n| {
let from = if n == 0 {
String::new()
} else {
format!("from :{n}\n")
};
format!(
"commit refs/heads/main\nmark :{}\ncommitter a <a@a> {} +0000\n\
data 0\n{from}M 100644 inline d{}/s{}/f{}\ndata <<END\n{n}\nEND\n",
n + 1,
1_000_000_000 + n,
n % 3,
n % 5,
n % 7
)
})
.collect();
git(&source, &["fast-import", "--quiet"], &history);
let first = transfer(&source, &target, "main~60\n", true, false);
transfer(&source, &target, "main~30\n^main~60\n", true, true);
transfer(&source, &target, "main\n^main~30\n", false, false);
let tip = git(&source, &["rev-parse", "main"], "");
git(&target, &["update-ref", "refs/heads/main", &tip], "");
git(&target, &["multi-pack-index", "write"], "");
reads_by_place(&target, format, 3);
// the midx copies ofs-delta bases out of the preferred pack, the first one.
transfer(&source, &target, "main\n", false, false);
let preferred = format!("--preferred-pack={first}");
git(&target, &["multi-pack-index", "write", &preferred], "");
reads_by_place(&target, format, 4);
}
}
}