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

grit_lib/
pack_reuse.rs
