dengel / dengel-git

Public
Star on GitHubFork on GitHub
Clone

git clone https://git.dengel.dev/dengel/dengel-git.git

Commit bb7110d
//! One pack entry read with positioned reads (NMA-2243 latency).
//!
//! `ObjectStore` used to read a whole pack file into memory on the first
//! lookup it served from that pack (`rustgit::pack::pack::read_pack_file`),
//! so every query, clone and fetch paid O(pack size) time and memory per
//! request: about 600 ms and 1 GB of RSS on the 1 GB latency repository.
//! This reader fetches only the entry's header and its zlib stream from
//! the file, so a lookup costs O(entry), and returns `Err` (never panics)
//! on a malformed entry.
//!
//! Format (gitformat-pack): a size-and-type varint header; for an ofs-delta
//! a second varint with the negative offset to the base; for a ref-delta a
//! 20-byte base id; then a zlib stream that inflates to exactly the header's
//! size. The parse is equivalent to `rustgit::pack::pack::read_raw_entry`,
//! checked against it on real packs in `tests::matches_rustgit_on_every_entry`.

use std::fs::File;
use std::io::Read;
use std::os::unix::fs::FileExt;

use flate2::read::ZlibDecoder;
use rustgit::pack::pack::BaseRef;

use crate::objectstore::StoreError;

const OBJ_OFS_DELTA: u8 = 6;
const OBJ_REF_DELTA: u8 = 7;
/// Longest header we read up front: a 10-byte size varint, a 10-byte
/// offset varint or a 20-byte base id, with room to spare.
const HEADER_PROBE: usize = 64;

pub(crate) struct Entry {
    pub kind: u8,
    pub content: Vec<u8>,
    pub base: BaseRef,
}

fn malformed(detail: String) -> StoreError {
    StoreError::Malformed {
        what: "pack entry",
        detail,
    }
}

/// `Read` over a file from a position, by `read_at`; does not move any
/// shared cursor, so several entries of one `File` can be read in any order.
struct At<'a> {
    file: &'a File,
    pos: u64,
}

impl Read for At<'_> {
    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
        let n = self.file.read_at(buf, self.pos)?;
        self.pos += n as u64;
        Ok(n)
    }
}

/// Read and inflate the entry at `offset`. Deltas are not applied.
/// `max_size` bounds the declared inflated size.
pub(crate) fn read_entry(
    file: &File,
    offset: u64,
    max_size: usize,
    discard_blob: bool,
) -> Result<Entry, StoreError> {
    let mut head = [0u8; HEADER_PROBE];
    let mut got = 0;
    while got < HEADER_PROBE {
        let n = file.read_at(&mut head[got..], offset + got as u64)?;
        if n == 0 {
            break;
        }
        got += n;
    }
    let head = &head[..got];
    let byte = |i: usize| {
        head.get(i)
            .copied()
            .ok_or_else(|| malformed(format!("entry header at {offset} runs past the pack end")))
    };

    let mut i = 0;
    let mut c = byte(i)?;
    i += 1;
    let kind = (c >> 4) & 0x7;
    let mut size = u64::from(c & 0x0f);
    let mut shift = 4u32;
    while c & 0x80 != 0 {
        c = byte(i)?;
        i += 1;
        if shift > 60 {
            return Err(malformed(format!("size varint too long at {offset}")));
        }
        size |= u64::from(c & 0x7f) << shift;
        shift += 7;
    }

    let base = match kind {
        OBJ_OFS_DELTA => {
            let mut c = byte(i)?;
            i += 1;
            let mut rel = u64::from(c & 0x7f);
            while c & 0x80 != 0 {
                c = byte(i)?;
                i += 1;
                rel = rel
                    .checked_add(1)
                    .and_then(|r| r.checked_mul(128))
                    .map(|r| r | u64::from(c & 0x7f))
                    .ok_or_else(|| malformed(format!("ofs-delta offset overflows at {offset}")))?;
            }
            let base = offset.checked_sub(rel).filter(|_| rel > 0).ok_or_else(|| {
                malformed(format!(
                    "ofs-delta at {offset} points before the pack start"
                ))
            })?;
            BaseRef::Offset(base)
        }
        OBJ_REF_DELTA => {
            let mut oid = [0u8; 20];
            let end = i + 20;
            if head.len() < end {
                return Err(malformed(format!(
                    "ref-delta base id truncated at {offset}"
                )));
            }
            oid.copy_from_slice(&head[i..end]);
            i = end;
            BaseRef::Oid(oid)
        }
        1..=4 => BaseRef::None,
        other => return Err(malformed(format!("unknown entry type {other} at {offset}"))),
    };

    if size > max_size as u64 {
        return Err(malformed(format!(
            "entry at {offset} declares {size} bytes, more than {max_size}"
        )));
    }
    let reader = At {
        file,
        pos: offset + i as u64,
    };
    let mut decoder = ZlibDecoder::new(reader).take(size + 1);
    let discard = discard_blob && kind == rustgit::pack::pack::OBJ_BLOB;
    let mut content = Vec::new();
    let inflated = if discard {
        std::io::copy(&mut decoder, &mut std::io::sink())
    } else {
        decoder.read_to_end(&mut content).map(|count| count as u64)
    }
    .map_err(|e| malformed(format!("zlib stream at {offset}: {e}")))?;
    if inflated != size {
        return Err(malformed(format!(
            "entry at {offset} inflates to {inflated} bytes, header says {size}",
        )));
    }
    Ok(Entry {
        kind,
        content,
        base,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::process::Command;

    fn git(dir: &std::path::Path, args: &[&str]) {
        let ok = Command::new("git")
            .current_dir(dir)
            .env("GIT_CONFIG_GLOBAL", "/dev/null")
            .env("GIT_CONFIG_NOSYSTEM", "1")
            .env("GIT_AUTHOR_NAME", "A")
            .env("GIT_AUTHOR_EMAIL", "a@example.com")
            .env("GIT_COMMITTER_NAME", "A")
            .env("GIT_COMMITTER_EMAIL", "a@example.com")
            .args(args)
            .status()
            .unwrap()
            .success();
        assert!(ok, "git {args:?}");
    }

    /// Every entry of a real, delta-heavy pack (ofs-deltas from `gc`, and a
    /// ref-delta pack from `--no-delta-base-offset`) reads the same as
    /// rustgit's whole-file reader.
    #[test]
    fn matches_rustgit_on_every_entry() {
        for ofs in [true, false] {
            let tmp = tempfile::tempdir().unwrap();
            let w = tmp.path();
            git(w, &["init", "-q"]);
            let mut text = String::new();
            for i in 0..60 {
                text.push_str(&format!("line {i} {}\n", "x".repeat(i % 7)));
                std::fs::write(w.join("f.txt"), &text).unwrap();
                std::fs::write(
                    w.join(format!("g{}.txt", i % 5)),
                    format!("{i}\n").repeat(50),
                )
                .unwrap();
                git(w, &["add", "."]);
                git(w, &["commit", "-q", "-m", &format!("c{i}")]);
            }
            let offsets = format!("repack.useDeltaBaseOffset={ofs}");
            git(
                w,
                &[
                    "-c",
                    &offsets,
                    "repack",
                    "-adf",
                    "-q",
                    "--depth=50",
                    "--window=50",
                ],
            );
            let pack_dir = w.join(".git/objects/pack");
            let idx_path = std::fs::read_dir(&pack_dir)
                .unwrap()
                .map(|e| e.unwrap().path())
                .find(|p| p.extension().is_some_and(|e| e == "idx"))
                .unwrap();
            let parsed = rustgit::pack::idx::parse(&idx_path).unwrap();
            let pack_path = idx_path.with_extension("pack");
            let bytes = std::fs::read(&pack_path).unwrap();
            let file = File::open(&pack_path).unwrap();
            let mut deltas = 0;
            for e in parsed.entries {
                let theirs = rustgit::pack::pack::read_raw_entry(&bytes, e.offset);
                let ours = read_entry(&file, e.offset, usize::MAX, false).unwrap();
                assert_eq!(ours.kind, theirs.kind);
                assert_eq!(ours.content, theirs.content);
                match (&ours.base, &theirs.base) {
                    (BaseRef::None, BaseRef::None) => {}
                    (BaseRef::Offset(a), BaseRef::Offset(b)) => {
                        assert_eq!(a, b);
                        deltas += 1;
                    }
                    (BaseRef::Oid(a), BaseRef::Oid(b)) => {
                        assert_eq!(a, b);
                        deltas += 1;
                    }
                    _ => panic!("base kind differs at {}", e.offset),
                }
            }
            assert!(deltas > 10, "the fixture must exercise deltas ({deltas})");
        }
    }

    #[test]
    fn malformed_entries_are_errors_not_panics() {
        let tmp = tempfile::tempdir().unwrap();
        let p = tmp.path().join("bad.pack");
        // A blob header declaring 5 bytes followed by garbage, not zlib.
        std::fs::write(&p, [0x35, 0xff, 0xff, 0xff]).unwrap();
        let f = File::open(&p).unwrap();
        assert!(read_entry(&f, 0, 1 << 20, false).is_err());
        // Header past the end of the file.
        assert!(read_entry(&f, 100, 1 << 20, false).is_err());
        // Declared size over the bound.
        std::fs::write(&p, [0xbf, 0xff, 0x7f]).unwrap();
        let f = File::open(&p).unwrap();
        assert!(read_entry(&f, 0, 16, false).is_err());
        // An ofs-delta pointing before the start.
        std::fs::write(&p, [0x65, 0x05, 0x78, 0x9c]).unwrap();
        let f = File::open(&p).unwrap();
        assert!(read_entry(&f, 0, 1 << 20, false).is_err());
    }
}