From 10ee2acdd26a7f1298c6f6d6b7af9b469fe29b87 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 4 May 2024 14:41:41 +0200 Subject: Merging upstream version 1.70.0+dfsg2. Signed-off-by: Daniel Baumann --- vendor/gix-pack/src/cache/delta/from_offsets.rs | 161 +++++++++++++++ vendor/gix-pack/src/cache/delta/mod.rs | 216 +++++++++++++++++++++ vendor/gix-pack/src/cache/delta/traverse/mod.rs | 177 +++++++++++++++++ .../gix-pack/src/cache/delta/traverse/resolve.rs | 154 +++++++++++++++ vendor/gix-pack/src/cache/delta/traverse/util.rs | 63 ++++++ vendor/gix-pack/src/cache/lru.rs | 165 ++++++++++++++++ vendor/gix-pack/src/cache/mod.rs | 55 ++++++ vendor/gix-pack/src/cache/object.rs | 123 ++++++++++++ 8 files changed, 1114 insertions(+) create mode 100644 vendor/gix-pack/src/cache/delta/from_offsets.rs create mode 100644 vendor/gix-pack/src/cache/delta/mod.rs create mode 100644 vendor/gix-pack/src/cache/delta/traverse/mod.rs create mode 100644 vendor/gix-pack/src/cache/delta/traverse/resolve.rs create mode 100644 vendor/gix-pack/src/cache/delta/traverse/util.rs create mode 100644 vendor/gix-pack/src/cache/lru.rs create mode 100644 vendor/gix-pack/src/cache/mod.rs create mode 100644 vendor/gix-pack/src/cache/object.rs (limited to 'vendor/gix-pack/src/cache') diff --git a/vendor/gix-pack/src/cache/delta/from_offsets.rs b/vendor/gix-pack/src/cache/delta/from_offsets.rs new file mode 100644 index 000000000..8acb4a802 --- /dev/null +++ b/vendor/gix-pack/src/cache/delta/from_offsets.rs @@ -0,0 +1,161 @@ +use std::{ + convert::TryFrom, + fs, io, + io::{BufRead, Read, Seek, SeekFrom}, + sync::atomic::{AtomicBool, Ordering}, + time::Instant, +}; + +use gix_features::progress::{self, Progress}; + +use crate::{cache::delta::Tree, data}; + +/// Returned by [`Tree::from_offsets_in_pack()`] +#[derive(thiserror::Error, Debug)] +#[allow(missing_docs)] +pub enum Error { + #[error("{message}")] + Io { source: io::Error, message: &'static str }, + #[error(transparent)] + Header(#[from] crate::data::header::decode::Error), + #[error("Could find object with id {id} in this pack. Thin packs are not supported")] + UnresolvedRefDelta { id: gix_hash::ObjectId }, + #[error(transparent)] + Tree(#[from] crate::cache::delta::Error), + #[error("Interrupted")] + Interrupted, +} + +const PACK_HEADER_LEN: usize = 12; + +/// Generate tree from certain input +impl Tree { + /// Create a new `Tree` from any data sorted by offset, ascending as returned by the `data_sorted_by_offsets` iterator. + /// * `get_pack_offset(item: &T`) -> data::Offset` is a function returning the pack offset of the given item, which can be used + /// for obtaining the objects entry within the pack. + /// * `pack_path` is the path to the pack file itself and from which to read the entry data, which is a pack file matching the offsets + /// returned by `get_pack_offset(…)`. + /// * `progress` is used to track progress when creating the tree. + /// * `resolve_in_pack_id(gix_hash::oid) -> Option` takes an object ID and tries to resolve it to an object within this pack if + /// possible. Failing to do so aborts the operation, and this function is not expected to be called in usual packs. It's a theoretical + /// possibility though as old packs might have referred to their objects using the 20 bytes hash, instead of their encoded offset from the base. + /// + /// Note that the sort order is ascending. The given pack file path must match the provided offsets. + pub fn from_offsets_in_pack( + pack_path: impl AsRef, + data_sorted_by_offsets: impl Iterator, + get_pack_offset: impl Fn(&T) -> data::Offset, + resolve_in_pack_id: impl Fn(&gix_hash::oid) -> Option, + mut progress: impl Progress, + should_interrupt: &AtomicBool, + object_hash: gix_hash::Kind, + ) -> Result { + let mut r = io::BufReader::with_capacity( + 8192 * 8, // this value directly corresponds to performance, 8k (default) is about 4x slower than 64k + fs::File::open(pack_path).map_err(|err| Error::Io { + source: err, + message: "open pack path", + })?, + ); + + let anticipated_num_objects = if let Some(num_objects) = data_sorted_by_offsets.size_hint().1 { + progress.init(Some(num_objects), progress::count("objects")); + num_objects + } else { + 0 + }; + let mut tree = Tree::with_capacity(anticipated_num_objects)?; + + { + // safety check - assure ourselves it's a pack we can handle + let mut buf = [0u8; PACK_HEADER_LEN]; + r.read_exact(&mut buf).map_err(|err| Error::Io { + source: err, + message: "reading header buffer with at least 12 bytes failed - pack file truncated?", + })?; + crate::data::header::decode(&buf)?; + } + + let then = Instant::now(); + + let mut previous_cursor_position = None::; + + let hash_len = object_hash.len_in_bytes(); + for (idx, data) in data_sorted_by_offsets.enumerate() { + let pack_offset = get_pack_offset(&data); + if let Some(previous_offset) = previous_cursor_position { + Self::advance_cursor_to_pack_offset(&mut r, pack_offset, previous_offset)?; + }; + let entry = crate::data::Entry::from_read(&mut r, pack_offset, hash_len).map_err(|err| Error::Io { + source: err, + message: "EOF while parsing header", + })?; + previous_cursor_position = Some(pack_offset + entry.header_size() as u64); + + use crate::data::entry::Header::*; + match entry.header { + Tree | Blob | Commit | Tag => { + tree.add_root(pack_offset, data)?; + } + RefDelta { base_id } => { + resolve_in_pack_id(base_id.as_ref()) + .ok_or(Error::UnresolvedRefDelta { id: base_id }) + .and_then(|base_pack_offset| { + tree.add_child(base_pack_offset, pack_offset, data).map_err(Into::into) + })?; + } + OfsDelta { base_distance } => { + let base_pack_offset = pack_offset + .checked_sub(base_distance) + .expect("in bound distance for deltas"); + tree.add_child(base_pack_offset, pack_offset, data)?; + } + }; + progress.inc(); + if idx % 10_000 == 0 && should_interrupt.load(Ordering::SeqCst) { + return Err(Error::Interrupted); + } + } + + progress.show_throughput(then); + Ok(tree) + } + + fn advance_cursor_to_pack_offset( + r: &mut io::BufReader, + pack_offset: u64, + previous_offset: u64, + ) -> Result<(), Error> { + let bytes_to_skip: u64 = pack_offset + .checked_sub(previous_offset) + .expect("continuously ascending pack offsets"); + if bytes_to_skip == 0 { + return Ok(()); + } + let buf = r.fill_buf().map_err(|err| Error::Io { + source: err, + message: "skip bytes", + })?; + if buf.is_empty() { + // This means we have reached the end of file and can't make progress anymore, before we have satisfied our need + // for more + return Err(Error::Io { + source: io::Error::new( + io::ErrorKind::UnexpectedEof, + "ran out of bytes before reading desired amount of bytes", + ), + message: "index file is damaged or corrupt", + }); + } + if bytes_to_skip <= u64::try_from(buf.len()).expect("sensible buffer size") { + // SAFETY: bytes_to_skip <= buf.len() <= usize::MAX + r.consume(bytes_to_skip as usize); + } else { + r.seek(SeekFrom::Start(pack_offset)).map_err(|err| Error::Io { + source: err, + message: "seek to next entry", + })?; + } + Ok(()) + } +} diff --git a/vendor/gix-pack/src/cache/delta/mod.rs b/vendor/gix-pack/src/cache/delta/mod.rs new file mode 100644 index 000000000..f4c1b6fc6 --- /dev/null +++ b/vendor/gix-pack/src/cache/delta/mod.rs @@ -0,0 +1,216 @@ +/// Returned when using various methods on a [`Tree`] +#[derive(thiserror::Error, Debug)] +#[allow(missing_docs)] +pub enum Error { + #[error("Pack offsets must only increment. The previous pack offset was {last_pack_offset}, the current one is {pack_offset}")] + InvariantIncreasingPackOffset { + /// The last seen pack offset + last_pack_offset: crate::data::Offset, + /// The invariant violating offset + pack_offset: crate::data::Offset, + }, +} + +/// +pub mod traverse; + +/// +pub mod from_offsets; + +/// An item stored within the [`Tree`] +pub struct Item { + /// The offset into the pack file at which the pack entry's data is located. + pub offset: crate::data::Offset, + /// The offset of the next item in the pack file. + pub next_offset: crate::data::Offset, + /// Data to store with each Item, effectively data associated with each entry in a pack. + pub data: T, + /// Indices into our Tree's `items`, one for each pack entry that depends on us. + /// + /// Limited to u32 as that's the maximum amount of objects in a pack. + children: Vec, +} + +/// Identify what kind of node we have last seen +enum NodeKind { + Root, + Child, +} + +/// A tree that allows one-time iteration over all nodes and their children, consuming it in the process, +/// while being shareable among threads without a lock. +/// It does this by making the guarantee that iteration only happens once. +pub struct Tree { + /// The root nodes, i.e. base objects + root_items: Vec>, + /// The child nodes, i.e. those that rely a base object, like ref and ofs delta objects + child_items: Vec>, + /// The last encountered node was either a root or a child. + last_seen: Option, + /// Future child offsets, associating their offset into the pack with their index in the items array. + /// (parent_offset, child_index) + future_child_offsets: Vec<(crate::data::Offset, usize)>, +} + +impl Tree { + /// Instantiate a empty tree capable of storing `num_objects` amounts of items. + pub fn with_capacity(num_objects: usize) -> Result { + Ok(Tree { + root_items: Vec::with_capacity(num_objects / 2), + child_items: Vec::with_capacity(num_objects / 2), + last_seen: None, + future_child_offsets: Vec::new(), + }) + } + + fn num_items(&self) -> usize { + self.root_items.len() + self.child_items.len() + } + + fn assert_is_incrementing_and_update_next_offset(&mut self, offset: crate::data::Offset) -> Result<(), Error> { + let items = match &self.last_seen { + Some(NodeKind::Root) => &mut self.root_items, + Some(NodeKind::Child) => &mut self.child_items, + None => return Ok(()), + }; + let item = &mut items.last_mut().expect("last seen won't lie"); + if offset <= item.offset { + return Err(Error::InvariantIncreasingPackOffset { + last_pack_offset: item.offset, + pack_offset: offset, + }); + } + item.next_offset = offset; + Ok(()) + } + + fn set_pack_entries_end_and_resolve_ref_offsets( + &mut self, + pack_entries_end: crate::data::Offset, + ) -> Result<(), traverse::Error> { + if !self.future_child_offsets.is_empty() { + for (parent_offset, child_index) in self.future_child_offsets.drain(..) { + if let Ok(i) = self.child_items.binary_search_by_key(&parent_offset, |i| i.offset) { + self.child_items[i].children.push(child_index as u32); + } else if let Ok(i) = self.root_items.binary_search_by_key(&parent_offset, |i| i.offset) { + self.root_items[i].children.push(child_index as u32); + } else { + return Err(traverse::Error::OutOfPackRefDelta { + base_pack_offset: parent_offset, + }); + } + } + } + + self.assert_is_incrementing_and_update_next_offset(pack_entries_end) + .expect("BUG: pack now is smaller than all previously seen entries"); + Ok(()) + } + + /// Add a new root node, one that only has children but is not a child itself, at the given pack `offset` and associate + /// custom `data` with it. + pub fn add_root(&mut self, offset: crate::data::Offset, data: T) -> Result<(), Error> { + self.assert_is_incrementing_and_update_next_offset(offset)?; + self.last_seen = NodeKind::Root.into(); + self.root_items.push(Item { + offset, + next_offset: 0, + data, + children: Default::default(), + }); + Ok(()) + } + + /// Add a child of the item at `base_offset` which itself resides at pack `offset` and associate custom `data` with it. + pub fn add_child( + &mut self, + base_offset: crate::data::Offset, + offset: crate::data::Offset, + data: T, + ) -> Result<(), Error> { + self.assert_is_incrementing_and_update_next_offset(offset)?; + + let next_child_index = self.child_items.len(); + if let Ok(i) = self.child_items.binary_search_by_key(&base_offset, |i| i.offset) { + self.child_items[i].children.push(next_child_index as u32); + } else if let Ok(i) = self.root_items.binary_search_by_key(&base_offset, |i| i.offset) { + self.root_items[i].children.push(next_child_index as u32); + } else { + self.future_child_offsets.push((base_offset, next_child_index)); + } + + self.last_seen = NodeKind::Child.into(); + self.child_items.push(Item { + offset, + next_offset: 0, + data, + children: Default::default(), + }); + Ok(()) + } +} + +#[cfg(test)] +mod tests { + mod tree { + mod from_offsets_in_pack { + use std::sync::atomic::AtomicBool; + + use crate as pack; + + const SMALL_PACK_INDEX: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.idx"; + const SMALL_PACK: &str = "objects/pack/pack-a2bf8e71d8c18879e499335762dd95119d93d9f1.pack"; + + const INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.idx"; + const PACK_FOR_INDEX_V1: &str = "objects/pack/pack-c0438c19fb16422b6bbcce24387b3264416d485b.pack"; + + use gix_testtools::fixture_path; + + #[test] + fn v1() -> Result<(), Box> { + tree(INDEX_V1, PACK_FOR_INDEX_V1) + } + + #[test] + fn v2() -> Result<(), Box> { + tree(SMALL_PACK_INDEX, SMALL_PACK) + } + + fn tree(index_path: &str, pack_path: &str) -> Result<(), Box> { + let idx = pack::index::File::at(fixture_path(index_path), gix_hash::Kind::Sha1)?; + crate::cache::delta::Tree::from_offsets_in_pack( + fixture_path(pack_path), + idx.sorted_offsets().into_iter(), + |ofs| *ofs, + |id| idx.lookup(id).map(|index| idx.pack_offset_at_index(index)), + gix_features::progress::Discard, + &AtomicBool::new(false), + gix_hash::Kind::Sha1, + )?; + Ok(()) + } + } + } + + #[test] + fn size_of_pack_tree_item() { + use super::Item; + assert_eq!(std::mem::size_of::<[Item<()>; 7_500_000]>(), 300_000_000); + } + + #[test] + fn size_of_pack_verify_data_structure() { + use super::Item; + pub struct EntryWithDefault { + _index_entry: crate::index::Entry, + _kind: gix_object::Kind, + _object_size: u64, + _decompressed_size: u64, + _compressed_size: u64, + _header_size: u16, + _level: u16, + } + + assert_eq!(std::mem::size_of::<[Item; 7_500_000]>(), 840_000_000); + } +} diff --git a/vendor/gix-pack/src/cache/delta/traverse/mod.rs b/vendor/gix-pack/src/cache/delta/traverse/mod.rs new file mode 100644 index 000000000..bfe2ec687 --- /dev/null +++ b/vendor/gix-pack/src/cache/delta/traverse/mod.rs @@ -0,0 +1,177 @@ +use std::sync::atomic::{AtomicBool, Ordering}; + +use gix_features::{ + parallel::in_parallel_with_slice, + progress::{self, Progress}, + threading::{lock, Mutable, OwnShared}, +}; + +use crate::{ + cache::delta::{traverse::util::ItemSliceSend, Item, Tree}, + data::EntryRange, +}; + +mod resolve; +pub(crate) mod util; + +/// Returned by [`Tree::traverse()`] +#[derive(thiserror::Error, Debug)] +#[allow(missing_docs)] +pub enum Error { + #[error("{message}")] + ZlibInflate { + source: gix_features::zlib::inflate::Error, + message: &'static str, + }, + #[error("The resolver failed to obtain the pack entry bytes for the entry at {pack_offset}")] + ResolveFailed { pack_offset: u64 }, + #[error("One of the object inspectors failed")] + Inspect(#[from] Box), + #[error("Interrupted")] + Interrupted, + #[error( + "The base at {base_pack_offset} was referred to by a ref-delta, but it was never added to the tree as if the pack was still thin." + )] + OutOfPackRefDelta { + /// The base's offset which was from a resolved ref-delta that didn't actually get added to the tree + base_pack_offset: crate::data::Offset, + }, +} + +/// Additional context passed to the `inspect_object(…)` function of the [`Tree::traverse()`] method. +pub struct Context<'a, S> { + /// The pack entry describing the object + pub entry: &'a crate::data::Entry, + /// The offset at which `entry` ends in the pack, useful to learn about the exact range of `entry` within the pack. + pub entry_end: u64, + /// The decompressed object itself, ready to be decoded. + pub decompressed: &'a [u8], + /// Custom state known to the function + pub state: &'a mut S, + /// The depth at which this object resides in the delta-tree. It represents the amount of base objects, with 0 indicating + /// an 'undeltified' object, and higher values indicating delta objects with the given amount of bases. + pub level: u16, +} + +/// Options for [`Tree::traverse()`]. +pub struct Options<'a, P1, P2> { + /// is a progress instance to track progress for each object in the traversal. + pub object_progress: P1, + /// is a progress instance to track the overall progress. + pub size_progress: P2, + /// If `Some`, only use the given amount of threads. Otherwise, the amount of threads to use will be selected based on + /// the amount of available logical cores. + pub thread_limit: Option, + /// Abort the operation if the value is `true`. + pub should_interrupt: &'a AtomicBool, + /// specifies what kind of hashes we expect to be stored in oid-delta entries, which is viable to decoding them + /// with the correct size. + pub object_hash: gix_hash::Kind, +} + +/// The outcome of [`Tree::traverse()`] +pub struct Outcome { + /// The items that have no children in the pack, i.e. base objects. + pub roots: Vec>, + /// The items that children to a root object, i.e. delta objects. + pub children: Vec>, +} + +impl Tree +where + T: Send, +{ + /// Traverse this tree of delta objects with a function `inspect_object` to process each object at will. + /// + /// * `should_run_in_parallel() -> bool` returns true if the underlying pack is big enough to warrant parallel traversal at all. + /// * `resolve(EntrySlice, &mut Vec) -> Option<()>` resolves the bytes in the pack for the given `EntrySlice` and stores them in the + /// output vector. It returns `Some(())` if the object existed in the pack, or `None` to indicate a resolution error, which would abort the + /// operation as well. + /// * `pack_entries_end` marks one-past-the-last byte of the last entry in the pack, as the last entries size would otherwise + /// be unknown as it's not part of the index file. + /// * `new_thread_state() -> State` is a function to create state to be used in each thread, invoked once per thread. + /// * `inspect_object(node_data: &mut T, progress: Progress, context: Context) -> Result<(), CustomError>` is a function + /// running for each thread receiving fully decoded objects along with contextual information, which either succeeds with `Ok(())` + /// or returns a `CustomError`. + /// Note that `node_data` can be modified to allow storing maintaining computation results on a per-object basis. + /// + /// This method returns a vector of all tree items, along with their potentially modified custom node data. + /// + /// _Note_ that this method consumed the Tree to assure safe parallel traversal with mutation support. + pub fn traverse( + mut self, + resolve: F, + pack_entries_end: u64, + new_thread_state: impl Fn() -> S + Send + Clone, + inspect_object: MBFN, + Options { + thread_limit, + object_progress, + mut size_progress, + should_interrupt, + object_hash, + }: Options<'_, P1, P2>, + ) -> Result, Error> + where + F: for<'r> Fn(EntryRange, &'r mut Vec) -> Option<()> + Send + Clone, + P1: Progress, + P2: Progress, + MBFN: Fn(&mut T, &mut ::SubProgress, Context<'_, S>) -> Result<(), E> + Send + Clone, + E: std::error::Error + Send + Sync + 'static, + { + self.set_pack_entries_end_and_resolve_ref_offsets(pack_entries_end)?; + let object_progress = OwnShared::new(Mutable::new(object_progress)); + + let num_objects = self.num_items(); + let object_counter = { + let mut progress = lock(&object_progress); + progress.init(Some(num_objects), progress::count("objects")); + progress.counter() + }; + size_progress.init(None, progress::bytes()); + let size_counter = size_progress.counter(); + let child_items = self.child_items.as_mut_slice(); + + let start = std::time::Instant::now(); + in_parallel_with_slice( + &mut self.root_items, + thread_limit, + { + let object_progress = object_progress.clone(); + let child_items = ItemSliceSend(child_items as *mut [Item]); + move |thread_index| { + ( + Vec::::with_capacity(4096), + lock(&object_progress) + .add_child_with_id(format!("thread {thread_index}"), gix_features::progress::UNKNOWN), + new_thread_state(), + resolve.clone(), + inspect_object.clone(), + ItemSliceSend(child_items.0), + ) + } + }, + { + move |node, state| { + resolve::deltas( + object_counter.clone(), + size_counter.clone(), + node, + state, + object_hash.len_in_bytes(), + ) + } + }, + || (!should_interrupt.load(Ordering::Relaxed)).then(|| std::time::Duration::from_millis(50)), + |_| (), + )?; + + lock(&object_progress).show_throughput(start); + size_progress.show_throughput(start); + + Ok(Outcome { + roots: self.root_items, + children: self.child_items, + }) + } +} diff --git a/vendor/gix-pack/src/cache/delta/traverse/resolve.rs b/vendor/gix-pack/src/cache/delta/traverse/resolve.rs new file mode 100644 index 000000000..fc94d87ef --- /dev/null +++ b/vendor/gix-pack/src/cache/delta/traverse/resolve.rs @@ -0,0 +1,154 @@ +use std::{cell::RefCell, collections::BTreeMap, sync::atomic::Ordering}; + +use gix_features::{progress::Progress, zlib}; + +use crate::{ + cache::delta::{ + traverse::{ + util::{ItemSliceSend, Node}, + Context, Error, + }, + Item, + }, + data::EntryRange, +}; + +pub(crate) fn deltas( + object_counter: Option, + size_counter: Option, + node: &mut crate::cache::delta::Item, + (bytes_buf, ref mut progress, state, resolve, modify_base, child_items): &mut ( + Vec, + P, + S, + F, + MBFN, + ItemSliceSend>, + ), + hash_len: usize, +) -> Result<(), Error> +where + T: Send, + F: for<'r> Fn(EntryRange, &'r mut Vec) -> Option<()>, + P: Progress, + MBFN: Fn(&mut T, &mut P, Context<'_, S>) -> Result<(), E>, + E: std::error::Error + Send + Sync + 'static, +{ + let mut decompressed_bytes_by_pack_offset = BTreeMap::new(); + let bytes_buf = RefCell::new(bytes_buf); + let decompress_from_resolver = |slice: EntryRange| -> Result<(crate::data::Entry, u64, Vec), Error> { + let mut bytes_buf = bytes_buf.borrow_mut(); + bytes_buf.resize((slice.end - slice.start) as usize, 0); + resolve(slice.clone(), &mut bytes_buf).ok_or(Error::ResolveFailed { + pack_offset: slice.start, + })?; + let entry = crate::data::Entry::from_bytes(&bytes_buf, slice.start, hash_len); + let compressed = &bytes_buf[entry.header_size()..]; + let decompressed_len = entry.decompressed_size as usize; + Ok((entry, slice.end, decompress_all_at_once(compressed, decompressed_len)?)) + }; + + // Traverse the tree breadth first and loose the data produced for the base as it won't be needed anymore. + progress.init(None, gix_features::progress::count_with_decimals("objects", 2)); + + // each node is a base, and its children always start out as deltas which become a base after applying them. + // These will be pushed onto our stack until all are processed + let root_level = 0; + let mut nodes: Vec<_> = vec![( + root_level, + Node { + item: node, + child_items: child_items.0, + }, + )]; + while let Some((level, mut base)) = nodes.pop() { + let (base_entry, entry_end, base_bytes) = if level == root_level { + decompress_from_resolver(base.entry_slice())? + } else { + decompressed_bytes_by_pack_offset + .remove(&base.offset()) + .expect("we store the resolved delta buffer when done") + }; + + // anything done here must be repeated further down for leaf-nodes. + // This way we avoid retaining their decompressed memory longer than needed (they have no children, + // thus their memory can be released right away, using 18% less peak memory on the linux kernel). + { + modify_base( + base.data(), + progress, + Context { + entry: &base_entry, + entry_end, + decompressed: &base_bytes, + state, + level, + }, + ) + .map_err(|err| Box::new(err) as Box)?; + object_counter.as_ref().map(|c| c.fetch_add(1, Ordering::SeqCst)); + size_counter + .as_ref() + .map(|c| c.fetch_add(base_bytes.len(), Ordering::SeqCst)); + } + + for mut child in base.into_child_iter() { + let (mut child_entry, entry_end, delta_bytes) = decompress_from_resolver(child.entry_slice())?; + let (base_size, consumed) = crate::data::delta::decode_header_size(&delta_bytes); + let mut header_ofs = consumed; + assert_eq!( + base_bytes.len(), + base_size as usize, + "recorded base size in delta does not match" + ); + let (result_size, consumed) = crate::data::delta::decode_header_size(&delta_bytes[consumed..]); + header_ofs += consumed; + + let mut fully_resolved_delta_bytes = bytes_buf.borrow_mut(); + fully_resolved_delta_bytes.resize(result_size as usize, 0); + crate::data::delta::apply(&base_bytes, &mut fully_resolved_delta_bytes, &delta_bytes[header_ofs..]); + + // FIXME: this actually invalidates the "pack_offset()" computation, which is not obvious to consumers + // at all + child_entry.header = base_entry.header; // assign the actual object type, instead of 'delta' + if child.has_children() { + decompressed_bytes_by_pack_offset.insert( + child.offset(), + (child_entry, entry_end, fully_resolved_delta_bytes.to_owned()), + ); + nodes.push((level + 1, child)); + } else { + modify_base( + child.data(), + progress, + Context { + entry: &child_entry, + entry_end, + decompressed: &fully_resolved_delta_bytes, + state, + level: level + 1, + }, + ) + .map_err(|err| Box::new(err) as Box)?; + object_counter.as_ref().map(|c| c.fetch_add(1, Ordering::SeqCst)); + size_counter + .as_ref() + .map(|c| c.fetch_add(base_bytes.len(), Ordering::SeqCst)); + } + } + } + + Ok(()) +} + +fn decompress_all_at_once(b: &[u8], decompressed_len: usize) -> Result, Error> { + let mut out = Vec::new(); + out.resize(decompressed_len, 0); + zlib::Inflate::default() + .once(b, &mut out) + .map_err(|err| Error::ZlibInflate { + source: err, + message: "Failed to decompress entry", + })?; + Ok(out) +} diff --git a/vendor/gix-pack/src/cache/delta/traverse/util.rs b/vendor/gix-pack/src/cache/delta/traverse/util.rs new file mode 100644 index 000000000..e7caf2ff5 --- /dev/null +++ b/vendor/gix-pack/src/cache/delta/traverse/util.rs @@ -0,0 +1,63 @@ +use crate::cache::delta::Item; + +pub struct ItemSliceSend(pub *mut [T]) +where + T: Send; + +impl Clone for ItemSliceSend +where + T: Send, +{ + fn clone(&self) -> Self { + ItemSliceSend(self.0) + } +} + +// SAFETY: T is `Send`, and we only ever access one T at a time. And, ptrs need that assurance, I wonder if it's always right. +#[allow(unsafe_code)] +unsafe impl Send for ItemSliceSend where T: Send {} + +/// An item returned by `iter_root_chunks`, allowing access to the `data` stored alongside nodes in a [`Tree`]. +pub struct Node<'a, T> { + pub item: &'a mut Item, + pub child_items: *mut [Item], +} + +impl<'a, T> Node<'a, T> { + /// Returns the offset into the pack at which the `Node`s data is located. + pub fn offset(&self) -> u64 { + self.item.offset + } + + /// Returns the slice into the data pack at which the pack entry is located. + pub fn entry_slice(&self) -> crate::data::EntryRange { + self.item.offset..self.item.next_offset + } + + /// Returns the node data associated with this node. + pub fn data(&mut self) -> &mut T { + &mut self.item.data + } + + /// Returns true if this node has children, e.g. is not a leaf in the tree. + pub fn has_children(&self) -> bool { + !self.item.children.is_empty() + } + + /// Transform this `Node` into an iterator over its children. + /// + /// Children are `Node`s referring to pack entries whose base object is this pack entry. + pub fn into_child_iter(self) -> impl Iterator> + 'a { + let children = self.child_items; + self.item.children.iter().map(move |&index| { + // SAFETY: The children array is alive by the 'a lifetime. + // SAFETY: The index is a valid index into the children array. + // SAFETY: The resulting mutable pointer cannot be yielded by any other node. + #[allow(unsafe_code)] + Node { + item: unsafe { &mut *(children as *mut Item).add(index as usize) }, + child_items: children, + } + }) + } +} diff --git a/vendor/gix-pack/src/cache/lru.rs b/vendor/gix-pack/src/cache/lru.rs new file mode 100644 index 000000000..bba4f5d33 --- /dev/null +++ b/vendor/gix-pack/src/cache/lru.rs @@ -0,0 +1,165 @@ +use super::DecodeEntry; + +#[cfg(feature = "pack-cache-lru-dynamic")] +mod memory { + use std::num::NonZeroUsize; + + use clru::WeightScale; + + use super::DecodeEntry; + + struct Entry { + data: Vec, + kind: gix_object::Kind, + compressed_size: usize, + } + + type Key = (u32, u64); + struct CustomScale; + + impl WeightScale for CustomScale { + fn weight(&self, _key: &Key, value: &Entry) -> usize { + value.data.len() + } + } + + /// An LRU cache with hash map backing and an eviction rule based on the memory usage for object data in bytes. + pub struct MemoryCappedHashmap { + inner: clru::CLruCache, + free_list: Vec>, + debug: gix_features::cache::Debug, + } + + impl MemoryCappedHashmap { + /// Return a new instance which evicts least recently used items if it uses more than `memory_cap_in_bytes` + /// object data. + pub fn new(memory_cap_in_bytes: usize) -> MemoryCappedHashmap { + MemoryCappedHashmap { + inner: clru::CLruCache::with_config( + clru::CLruCacheConfig::new(NonZeroUsize::new(memory_cap_in_bytes).expect("non zero")) + .with_scale(CustomScale), + ), + free_list: Vec::new(), + debug: gix_features::cache::Debug::new(format!("MemoryCappedHashmap({memory_cap_in_bytes}B)")), + } + } + } + + impl DecodeEntry for MemoryCappedHashmap { + fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: gix_object::Kind, compressed_size: usize) { + self.debug.put(); + if let Ok(Some(previous_entry)) = self.inner.put_with_weight( + (pack_id, offset), + Entry { + data: self + .free_list + .pop() + .map(|mut v| { + v.clear(); + v.resize(data.len(), 0); + v.copy_from_slice(data); + v + }) + .unwrap_or_else(|| Vec::from(data)), + kind, + compressed_size, + }, + ) { + self.free_list.push(previous_entry.data) + } + } + + fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec) -> Option<(gix_object::Kind, usize)> { + let res = self.inner.get(&(pack_id, offset)).map(|e| { + out.resize(e.data.len(), 0); + out.copy_from_slice(&e.data); + (e.kind, e.compressed_size) + }); + if res.is_some() { + self.debug.hit() + } else { + self.debug.miss() + } + res + } + } +} + +#[cfg(feature = "pack-cache-lru-dynamic")] +pub use memory::MemoryCappedHashmap; + +#[cfg(feature = "pack-cache-lru-static")] +mod _static { + use super::DecodeEntry; + struct Entry { + pack_id: u32, + offset: u64, + data: Vec, + kind: gix_object::Kind, + compressed_size: usize, + } + + /// A cache using a least-recently-used implementation capable of storing the `SIZE` most recent objects. + /// The cache must be small as the search is 'naive' and the underlying data structure is a linked list. + /// Values of 64 seem to improve performance. + pub struct StaticLinkedList { + inner: uluru::LRUCache, + free_list: Vec>, + debug: gix_features::cache::Debug, + } + + impl Default for StaticLinkedList { + fn default() -> Self { + StaticLinkedList { + inner: Default::default(), + free_list: Vec::new(), + debug: gix_features::cache::Debug::new(format!("StaticLinkedList<{SIZE}>")), + } + } + } + + impl DecodeEntry for StaticLinkedList { + fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: gix_object::Kind, compressed_size: usize) { + self.debug.put(); + if let Some(previous) = self.inner.insert(Entry { + offset, + pack_id, + data: self + .free_list + .pop() + .map(|mut v| { + v.clear(); + v.resize(data.len(), 0); + v.copy_from_slice(data); + v + }) + .unwrap_or_else(|| Vec::from(data)), + kind, + compressed_size, + }) { + self.free_list.push(previous.data) + } + } + + fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec) -> Option<(gix_object::Kind, usize)> { + let res = self.inner.lookup(|e: &mut Entry| { + if e.pack_id == pack_id && e.offset == offset { + out.resize(e.data.len(), 0); + out.copy_from_slice(&e.data); + Some((e.kind, e.compressed_size)) + } else { + None + } + }); + if res.is_some() { + self.debug.hit() + } else { + self.debug.miss() + } + res + } + } +} + +#[cfg(feature = "pack-cache-lru-static")] +pub use _static::StaticLinkedList; diff --git a/vendor/gix-pack/src/cache/mod.rs b/vendor/gix-pack/src/cache/mod.rs new file mode 100644 index 000000000..cf4b94df8 --- /dev/null +++ b/vendor/gix-pack/src/cache/mod.rs @@ -0,0 +1,55 @@ +use std::ops::DerefMut; + +use gix_object::Kind; + +/// A trait to model putting objects at a given pack `offset` into a cache, and fetching them. +/// +/// It is used to speed up [pack traversals][crate::index::File::traverse()]. +pub trait DecodeEntry { + /// Store a fully decoded object at `offset` of `kind` with `compressed_size` and `data` in the cache. + /// + /// It is up to the cache implementation whether that actually happens or not. + fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: gix_object::Kind, compressed_size: usize); + /// Attempt to fetch the object at `offset` and store its decoded bytes in `out`, as previously stored with [`DecodeEntry::put()`], and return + /// its (object `kind`, `decompressed_size`) + fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec) -> Option<(gix_object::Kind, usize)>; +} + +/// A cache that stores nothing and retrieves nothing, thus it _never_ caches. +#[derive(Default)] +pub struct Never; + +impl DecodeEntry for Never { + fn put(&mut self, _pack_id: u32, _offset: u64, _data: &[u8], _kind: gix_object::Kind, _compressed_size: usize) {} + fn get(&mut self, _pack_id: u32, _offset: u64, _out: &mut Vec) -> Option<(gix_object::Kind, usize)> { + None + } +} + +impl DecodeEntry for Box { + fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: Kind, compressed_size: usize) { + self.deref_mut().put(pack_id, offset, data, kind, compressed_size) + } + + fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec) -> Option<(Kind, usize)> { + self.deref_mut().get(pack_id, offset, out) + } +} + +/// A way of storing and retrieving entire objects to and from a cache. +pub trait Object { + /// Put the object going by `id` of `kind` with `data` into the cache. + fn put(&mut self, id: gix_hash::ObjectId, kind: gix_object::Kind, data: &[u8]); + + /// Try to retrieve the object named `id` and place its data into `out` if available and return `Some(kind)` if found. + fn get(&mut self, id: &gix_hash::ObjectId, out: &mut Vec) -> Option; +} + +/// Various implementations of [`DecodeEntry`] using least-recently-used algorithms. +#[cfg(any(feature = "pack-cache-lru-dynamic", feature = "pack-cache-lru-static"))] +pub mod lru; + +pub mod object; + +/// +pub(crate) mod delta; diff --git a/vendor/gix-pack/src/cache/object.rs b/vendor/gix-pack/src/cache/object.rs new file mode 100644 index 000000000..e64f47a8c --- /dev/null +++ b/vendor/gix-pack/src/cache/object.rs @@ -0,0 +1,123 @@ +//! # Note +//! +//! This module is a bit 'misplaced' if spelled out like 'gix_pack::cache::object::*' but is best placed here for code re-use and +//! general usefulness. +use crate::cache; + +#[cfg(feature = "object-cache-dynamic")] +mod memory { + use std::num::NonZeroUsize; + + use clru::WeightScale; + + use crate::cache; + + struct Entry { + data: Vec, + kind: gix_object::Kind, + } + + type Key = gix_hash::ObjectId; + + struct CustomScale; + + impl WeightScale for CustomScale { + fn weight(&self, key: &Key, value: &Entry) -> usize { + value.data.len() + std::mem::size_of::() + key.as_bytes().len() + } + } + + /// An LRU cache with hash map backing and an eviction rule based on the memory usage for object data in bytes. + pub struct MemoryCappedHashmap { + inner: clru::CLruCache, + free_list: Vec>, + debug: gix_features::cache::Debug, + } + + impl MemoryCappedHashmap { + /// The amount of bytes we can hold in total, or the value we saw in `new(…)`. + pub fn capacity(&self) -> usize { + self.inner.capacity() + } + /// Return a new instance which evicts least recently used items if it uses more than `memory_cap_in_bytes` + /// object data. + pub fn new(memory_cap_in_bytes: usize) -> MemoryCappedHashmap { + MemoryCappedHashmap { + inner: clru::CLruCache::with_config( + clru::CLruCacheConfig::new(NonZeroUsize::new(memory_cap_in_bytes).expect("non zero")) + .with_hasher(gix_hashtable::hash::Builder::default()) + .with_scale(CustomScale), + ), + free_list: Vec::new(), + debug: gix_features::cache::Debug::new(format!("MemoryCappedObjectHashmap({memory_cap_in_bytes}B)")), + } + } + } + + impl cache::Object for MemoryCappedHashmap { + /// Put the object going by `id` of `kind` with `data` into the cache. + fn put(&mut self, id: gix_hash::ObjectId, kind: gix_object::Kind, data: &[u8]) { + self.debug.put(); + if let Ok(Some(previous_entry)) = self.inner.put_with_weight( + id, + Entry { + data: self + .free_list + .pop() + .map(|mut v| { + v.clear(); + v.resize(data.len(), 0); + v.copy_from_slice(data); + v + }) + .unwrap_or_else(|| Vec::from(data)), + kind, + }, + ) { + self.free_list.push(previous_entry.data) + } + } + + /// Try to retrieve the object named `id` and place its data into `out` if available and return `Some(kind)` if found. + fn get(&mut self, id: &gix_hash::ObjectId, out: &mut Vec) -> Option { + let res = self.inner.get(id).map(|e| { + out.resize(e.data.len(), 0); + out.copy_from_slice(&e.data); + e.kind + }); + if res.is_some() { + self.debug.hit() + } else { + self.debug.miss() + } + res + } + } +} +#[cfg(feature = "object-cache-dynamic")] +pub use memory::MemoryCappedHashmap; + +/// A cache implementation that doesn't do any caching. +pub struct Never; + +impl cache::Object for Never { + /// Noop + fn put(&mut self, _id: gix_hash::ObjectId, _kind: gix_object::Kind, _data: &[u8]) {} + + /// Noop + fn get(&mut self, _id: &gix_hash::ObjectId, _out: &mut Vec) -> Option { + None + } +} + +impl cache::Object for Box { + fn put(&mut self, id: gix_hash::ObjectId, kind: gix_object::Kind, data: &[u8]) { + use std::ops::DerefMut; + self.deref_mut().put(id, kind, data) + } + + fn get(&mut self, id: &gix_hash::ObjectId, out: &mut Vec) -> Option { + use std::ops::DerefMut; + self.deref_mut().get(id, out) + } +} -- cgit v1.2.3