grit_lib/
pack_reuse.rs

1//! Verbatim pack reuse for bitmap-accelerated upload-pack (streaming PACK v2).
2//!
3//! Pack reuse is internal to upload-pack; there is no separate public embedder API.
4
5use std::collections::{HashMap, HashSet};
6use std::io::Write;
7use std::path::Path;
8use std::sync::Arc;
9
10use crate::bitmap_walk::ReachableSet;
11use crate::error::{Error, Result};
12use crate::ewah_bitmap::Bitmap;
13use crate::midx::{read_midx_btmp_ranges, read_midx_pack_idx_names, read_midx_preferred_idx_name};
14use crate::objects::ObjectId;
15use crate::pack::{
16    parse_pack_object_header, read_local_pack_indexes_cached, read_pack_bytes_cached,
17    read_packed_delta_dependency, PackedDeltaDependency, PackedType,
18};
19use crate::pack_index::PackIndex;
20use crate::pack_map::PackData;
21use crate::pack_object_select::{
22    included_tag_chains, try_bitmap_reachable_for_upload, TagCandidate,
23};
24use crate::pack_objects::{write_delta_pack_stream, PackBuildOptions, PackProgress, PackStats};
25use crate::repo::Repository;
26use crate::rev_list::ObjectFilter;
27
28struct BitmappedPack {
29    idx: Arc<PackIndex>,
30    pack_bytes: Arc<PackData>,
31    bitmap_pos: u32,
32    bitmap_nr: u32,
33}
34
35/// Counters updated while streaming reused pack bytes.
36#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
37pub struct ReuseWriteStats {
38    /// Pack body bytes copied verbatim from an existing on-disk pack.
39    pub verbatim_reuse_bytes: u64,
40    /// Objects emitted via verbatim pack reuse.
41    pub verbatim_reuse_objects: u32,
42    /// Reused OFS deltas with remapped base offsets.
43    pub pack_ofs_fixup_objects: u32,
44    /// OFS deltas converted to REF deltas for thin packs.
45    pub pack_ref_from_ofs_objects: u32,
46}
47
48/// Active verbatim reuse context while streaming a pack body.
49pub struct StreamingReuse {
50    pack: BitmappedPack,
51    reuse_bits: Bitmap,
52    index: Arc<crate::pack_bitmap::BitmapIndex>,
53    stats: ReuseWriteStats,
54}
55
56impl StreamingReuse {
57    #[must_use]
58    pub(crate) fn take_stats(&mut self) -> ReuseWriteStats {
59        std::mem::take(&mut self.stats)
60    }
61
62    fn note_verbatim(&mut self, bytes: u64) {
63        self.stats.verbatim_reuse_bytes += bytes;
64        self.stats.verbatim_reuse_objects += 1;
65    }
66
67    fn note_ofs_fixup(&mut self) {
68        self.stats.pack_ofs_fixup_objects += 1;
69        self.stats.verbatim_reuse_objects += 1;
70    }
71
72    pub(crate) fn record_ofs_fixup(&mut self) {
73        self.note_ofs_fixup();
74    }
75
76    pub(crate) fn record_verbatim_zlib(&mut self, zlib_bytes: u64) {
77        self.stats.verbatim_reuse_bytes += zlib_bytes;
78    }
79}
80
81impl StreamingReuse {
82    fn new(pack: BitmappedPack, reuse_bits: Bitmap, send_set: &ReachableSet) -> Self {
83        Self {
84            pack,
85            reuse_bits,
86            index: Arc::clone(send_set.bitmap_index()),
87            stats: ReuseWriteStats::default(),
88        }
89    }
90
91    fn marks_reuse(&self, oid: &ObjectId) -> bool {
92        self.index
93            .position_of(oid)
94            .is_some_and(|pos| self.reuse_bits.get(pos as usize))
95    }
96
97    /// Stream a whole packed object to `w` when marked reusable.
98    pub(crate) fn try_write_whole(
99        &mut self,
100        w: &mut dyn Write,
101        oid: &ObjectId,
102        opts: &PackBuildOptions,
103    ) -> Result<Option<u64>> {
104        if !opts.reuse_objects || !self.marks_reuse(oid) {
105            return Ok(None);
106        }
107        let objects_dir = self
108            .pack
109            .idx
110            .idx_path
111            .parent()
112            .and_then(|p| p.parent())
113            .ok_or_else(|| Error::CorruptObject("pack path layout".to_owned()))?;
114        let Some((bytes, start, end)) = crate::pack::packed_full_object_range(objects_dir, oid)?
115        else {
116            return Ok(None);
117        };
118        let n = write_whole_reused(w, &bytes[start..end])?;
119        self.note_verbatim(n);
120        Ok(Some(n))
121    }
122}
123
124/// Write a PACK stream to `w` using bitmap reachability and verbatim reuse when possible.
125///
126/// Returns [`None`] when reuse is unavailable (caller should stream via [`crate::pack_objects::PackObjects`]).
127#[allow(clippy::too_many_arguments)]
128pub fn try_write_streaming_pack(
129    repo: &Repository,
130    wants: &[ObjectId],
131    haves: &[ObjectId],
132    source_shallow: &HashSet<ObjectId>,
133    have_shallow: &HashSet<ObjectId>,
134    filter: Option<&ObjectFilter>,
135    opts: &PackBuildOptions,
136    progress: &mut dyn FnMut(PackProgress),
137    w: &mut dyn Write,
138) -> Result<Option<PackStats>> {
139    try_write_streaming_pack_including_tags(
140        repo,
141        wants,
142        haves,
143        source_shallow,
144        have_shallow,
145        filter,
146        &[],
147        opts,
148        progress,
149        w,
150        &crate::progress::CancelSignal::never(),
151    )
152}
153
154/// [`try_write_streaming_pack`] that also packs each of `include_tags` whose peeled
155/// object the bitmap send set holds (`include-tag`).
156///
157/// Added tags are planned like any object outside the reuse bitmap, so they are
158/// written whole and never duplicate an object the client asked for.
159#[allow(clippy::too_many_arguments)]
160pub(crate) fn try_write_streaming_pack_including_tags(
161    repo: &Repository,
162    wants: &[ObjectId],
163    haves: &[ObjectId],
164    source_shallow: &HashSet<ObjectId>,
165    have_shallow: &HashSet<ObjectId>,
166    filter: Option<&ObjectFilter>,
167    include_tags: &[TagCandidate],
168    opts: &PackBuildOptions,
169    progress: &mut dyn FnMut(PackProgress),
170    w: &mut dyn Write,
171    stop: &crate::progress::CancelSignal<'_>,
172) -> Result<Option<PackStats>> {
173    if !source_shallow.is_empty() || !have_shallow.is_empty() {
174        return Ok(None);
175    }
176    stop.poll()?;
177    let Some((send_set, peer_held)) =
178        try_bitmap_reachable_for_upload(repo.odb(), wants, haves, filter, source_shallow)?
179    else {
180        return Ok(None);
181    };
182    stop.poll()?;
183    let have_tips: HashSet<ObjectId> = haves.iter().copied().collect();
184    let index = send_set.bitmap_index();
185    let objects_dir = repo.odb().objects_dir();
186    let packs = resolve_bitmapped_packs(objects_dir, index, allow_multi_pack_reuse(repo))?;
187    if packs.is_empty() {
188        return Ok(None);
189    }
190    let Some(pack) = packs.into_iter().next() else {
191        return Ok(None);
192    };
193    let mut send: Vec<ObjectId> = send_set.iter_grouped_by_kind().collect();
194    send.extend(included_tag_chains(repo.odb(), include_tags, |oid| {
195        send_set.contains(oid)
196    })?);
197    progress(PackProgress::Enumerated { total: send.len() });
198
199    let send_bits = send_set.reuse_send_bits();
200    let reuse_bits = compute_reuse_bits(&pack, send_bits, &send_set, opts)?;
201
202    let blob_name_hashes =
203        crate::pack_object_select::name_hashes_for_send(index, &send, &HashSet::new());
204    let plan = crate::pack_objects::plan_deltas(
205        repo.odb(),
206        &send,
207        &have_tips,
208        Some(&peer_held),
209        opts,
210        &blob_name_hashes,
211        None,
212        stop,
213    )?;
214    progress(PackProgress::PlannedDeltas);
215    stop.poll()?;
216
217    let mut reuse = StreamingReuse::new(pack, reuse_bits, &send_set);
218    let stats = write_delta_pack_stream(repo.odb(), &plan, opts, w, Some(&mut reuse))?;
219    Ok(Some(stats))
220}
221
222fn allow_multi_pack_reuse(_repo: &Repository) -> bool {
223    false
224}
225
226fn resolve_bitmapped_packs(
227    objects_dir: &Path,
228    index: &crate::pack_bitmap::BitmapIndex,
229    multi: bool,
230) -> Result<Vec<BitmappedPack>> {
231    let pack_dir = objects_dir.join("pack");
232    let btmp = read_midx_btmp_ranges(objects_dir)?;
233    let idx_names = read_midx_pack_idx_names(objects_dir).unwrap_or_default();
234    let indexes: HashMap<String, Arc<PackIndex>> = read_local_pack_indexes_cached(objects_dir)?
235        .into_iter()
236        .map(|idx| {
237            let stem = idx
238                .idx_path
239                .file_stem()
240                .and_then(|s| s.to_str())
241                .unwrap_or("")
242                .to_owned();
243            (stem, idx)
244        })
245        .collect();
246
247    if !btmp.is_empty() {
248        let mut ranges: Vec<_> = btmp.into_iter().filter(|r| r.bitmap_nr > 0).collect();
249        if !multi {
250            if let Ok(pref) = read_midx_preferred_idx_name(objects_dir) {
251                let stem = pref.strip_suffix(".idx").unwrap_or(&pref);
252                if let Some(pos) = idx_names.iter().position(|n| n == &pref) {
253                    ranges.retain(|r| r.pack_id == pos as u32);
254                } else if indexes.contains_key(stem) {
255                    ranges.retain(|r| {
256                        idx_names
257                            .get(r.pack_id as usize)
258                            .is_some_and(|n| n.strip_suffix(".idx").unwrap_or(n) == stem)
259                    });
260                } else {
261                    ranges.truncate(1);
262                }
263            } else {
264                ranges.truncate(1);
265            }
266        }
267        let mut out = Vec::new();
268        for range in ranges {
269            let Some(name) = idx_names.get(range.pack_id as usize) else {
270                continue;
271            };
272            let stem = name.strip_suffix(".idx").unwrap_or(name);
273            let Some(idx) = indexes.get(stem) else {
274                continue;
275            };
276            let pack_bytes = read_pack_bytes_cached(&idx.pack_path)?;
277            out.push(BitmappedPack {
278                idx: Arc::clone(idx),
279                pack_bytes,
280                bitmap_pos: range.bitmap_pos,
281                bitmap_nr: range.bitmap_nr,
282            });
283        }
284        if !out.is_empty() {
285            return Ok(out);
286        }
287    }
288
289    let count = index.object_count();
290    if count == 0 {
291        return Ok(Vec::new());
292    }
293    if let Some(idx) = index.backing_pack_index() {
294        let pack_bytes = read_pack_bytes_cached(&idx.pack_path)?;
295        return Ok(vec![BitmappedPack {
296            idx,
297            pack_bytes,
298            bitmap_pos: 0,
299            bitmap_nr: count,
300        }]);
301    }
302    let mut with_bitmap: Vec<Arc<PackIndex>> = indexes
303        .values()
304        .filter(|idx| {
305            idx.idx_path
306                .file_stem()
307                .and_then(|s| s.to_str())
308                .is_some_and(|stem| pack_dir.join(format!("{stem}.bitmap")).is_file())
309        })
310        .cloned()
311        .collect();
312    with_bitmap.sort_by_key(|idx| std::cmp::Reverse(idx.len()));
313    if let Some(idx) = with_bitmap.into_iter().next() {
314        let pack_bytes = read_pack_bytes_cached(&idx.pack_path)?;
315        return Ok(vec![BitmappedPack {
316            idx,
317            pack_bytes,
318            bitmap_pos: 0,
319            bitmap_nr: count,
320        }]);
321    }
322    Ok(Vec::new())
323}
324
325fn compute_reuse_bits(
326    pack: &BitmappedPack,
327    send_bits: &Bitmap,
328    send_set: &ReachableSet,
329    opts: &PackBuildOptions,
330) -> Result<Bitmap> {
331    let mut reuse = Bitmap::new();
332    let pack_bytes = pack.pack_bytes.as_ref();
333    let hb = pack.idx.hash_bytes();
334    let pack_range = pack.bitmap_pos as usize..(pack.bitmap_pos + pack.bitmap_nr) as usize;
335    let send_positions: Vec<u32> = send_bits
336        .set_bits()
337        .filter(|pos| pack_range.contains(pos))
338        .map(|pos| pos as u32)
339        .collect();
340    loop {
341        let mut changed = false;
342        for &pos in &send_positions {
343            if reuse.get(pos as usize) {
344                continue;
345            }
346            let Ok(oid) = send_set.bitmap_index().oid_at(pos) else {
347                continue;
348            };
349            let Some(entry_off) = pack.idx.find_offset(&oid)? else {
350                continue;
351            };
352            if !entry_crc_ok(&pack.idx, &pack.pack_bytes, entry_off)? {
353                continue;
354            }
355            let mut p = entry_off as usize;
356            let (ty, _) = parse_pack_object_header(pack_bytes, &mut p)?;
357            match ty {
358                PackedType::Commit | PackedType::Tree | PackedType::Blob | PackedType::Tag => {
359                    reuse.set(pos as usize);
360                    changed = true;
361                }
362                PackedType::OfsDelta | PackedType::RefDelta => {
363                    // Streaming delta reuse is only enabled for thin packs; incremental
364                    // OFS fixups use on-disk zlib reuse during planning instead.
365                    if !opts.thin {
366                        continue;
367                    }
368                    let Some(base_oid) = delta_base_oid(&pack.idx, pack_bytes, entry_off, hb)?
369                    else {
370                        continue;
371                    };
372                    let Some(base_pos) = send_set.bitmap_index().position_of(&base_oid) else {
373                        continue;
374                    };
375                    if !reuse.get(base_pos as usize) {
376                        continue;
377                    }
378                    let Some(base_off) = pack.idx.find_offset(&base_oid)? else {
379                        continue;
380                    };
381                    let mut bp = base_off as usize;
382                    let Ok((base_ty, _)) = parse_pack_object_header(pack_bytes, &mut bp) else {
383                        continue;
384                    };
385                    if matches!(base_ty, PackedType::OfsDelta | PackedType::RefDelta) {
386                        continue;
387                    }
388                    reuse.set(pos as usize);
389                    changed = true;
390                }
391            }
392        }
393        if !changed {
394            break;
395        }
396    }
397    Ok(reuse)
398}
399
400fn entry_crc_ok(
401    idx: &PackIndex,
402    pack_bytes: &crate::pack::PackData,
403    entry_off: u64,
404) -> Result<bool> {
405    crate::pack::packed_entry_matches_index_crc(idx, pack_bytes, entry_off)
406}
407
408fn delta_base_oid(
409    idx: &PackIndex,
410    pack_bytes: &[u8],
411    entry_off: u64,
412    _hb: usize,
413) -> Result<Option<ObjectId>> {
414    let hb = idx.oid_at(0).len();
415    let Some(dep) = read_packed_delta_dependency(pack_bytes, entry_off, hb)? else {
416        return Ok(None);
417    };
418    Ok(Some(match dep {
419        PackedDeltaDependency::RefBase { base_oid } => base_oid,
420        PackedDeltaDependency::OfsBase { base_offset } => {
421            let Some(row) = idx.find_position_by_offset_sorted(base_offset)? else {
422                return Ok(None);
423            };
424            ObjectId::from_bytes(idx.oid_at(row))?
425        }
426    }))
427}
428
429fn write_whole_reused(w: &mut dyn Write, entry: &[u8]) -> Result<u64> {
430    for chunk in entry.chunks(64 * 1024) {
431        w.write_all(chunk).map_err(Error::Io)?;
432    }
433    Ok(entry.len() as u64)
434}
grit_lib/pack_reuse.rs

grit_lib/
pack_reuse.rs
