Struct git_pack::data::Entry

source · 
pub struct Entry {
    pub header: Header,
    pub decompressed_size: u64,
    pub data_offset: Offset,
}
Expand description

An representing an full- or delta-object within a pack

Fields§

§header: Header

The entry’s header

§decompressed_size: u64

The decompressed size of the entry in bytes.

Note that for non-delta entries this will be the size of the object itself.

§data_offset: Offset

absolute offset to compressed object data in the pack, just behind the entry’s header

Implementations§

source§

impl Entry

Decoding

Decode an entry from the given entry data d, providing the pack_offset to allow tracking the start of the entry data section.

Panics

If we cannot understand the header, garbage data is likely to trigger this.

Examples found in repository?
src/data/file/decode/entry.rs (line 113)
107
108
109
110
111
112
113
114

    pub fn entry(&self, offset: data::Offset) -> data::Entry {
        self.assure_v2();
        let pack_offset: usize = offset.try_into().expect("offset representable by machine");
        assert!(pack_offset <= self.data.len(), "offset out of bounds");

        let object_data = &self.data[pack_offset..];
        data::Entry::from_bytes(object_data, offset, self.hash_len)
    }
More examples
Hide additional examples
src/data/output/entry/mod.rs (line 77)
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

    pub fn from_pack_entry(
        mut entry: find::Entry,
        count: &output::Count,
        potential_bases: &[output::Count],
        bases_index_offset: usize,
        pack_offset_to_oid: Option<impl FnMut(u32, u64) -> Option<ObjectId>>,
        target_version: crate::data::Version,
    ) -> Option<Result<Self, Error>> {
        if entry.version != target_version {
            return None;
        };

        let pack_offset_must_be_zero = 0;
        let pack_entry =
            crate::data::Entry::from_bytes(&entry.data, pack_offset_must_be_zero, count.id.as_slice().len());

        use crate::data::entry::Header::*;
        match pack_entry.header {
            Commit => Some(output::entry::Kind::Base(git_object::Kind::Commit)),
            Tree => Some(output::entry::Kind::Base(git_object::Kind::Tree)),
            Blob => Some(output::entry::Kind::Base(git_object::Kind::Blob)),
            Tag => Some(output::entry::Kind::Base(git_object::Kind::Tag)),
            OfsDelta { base_distance } => {
                let pack_location = count.entry_pack_location.as_ref().expect("packed");
                let base_offset = pack_location
                    .pack_offset
                    .checked_sub(base_distance)
                    .expect("pack-offset - distance is firmly within the pack");
                potential_bases
                    .binary_search_by(|e| {
                        e.entry_pack_location
                            .as_ref()
                            .expect("packed")
                            .pack_offset
                            .cmp(&base_offset)
                    })
                    .ok()
                    .map(|idx| output::entry::Kind::DeltaRef {
                        object_index: idx + bases_index_offset,
                    })
                    .or_else(|| {
                        pack_offset_to_oid
                            .and_then(|mut f| f(pack_location.pack_id, base_offset))
                            .map(|id| output::entry::Kind::DeltaOid { id })
                    })
            }
            RefDelta { base_id: _ } => None, // ref deltas are for thin packs or legacy, repack them as base objects
        }
        .map(|kind| {
            Ok(output::Entry {
                id: count.id.to_owned(),
                kind,
                decompressed_size: pack_entry.decompressed_size as usize,
                compressed_data: {
                    entry.data.copy_within(pack_entry.data_offset as usize.., 0);
                    entry.data.resize(
                        entry.data.len()
                            - usize::try_from(pack_entry.data_offset).expect("offset representable as usize"),
                        0,
                    );
                    entry.data
                },
            })
        })
    }
src/cache/delta/traverse/resolve.rs (line 48)
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

pub(crate) fn deltas<T, F, P, MBFN, S, E>(
    object_counter: Option<git_features::progress::StepShared>,
    size_counter: Option<git_features::progress::StepShared>,
    node: &mut crate::cache::delta::Item<T>,
    (bytes_buf, ref mut progress, state, resolve, modify_base, child_items): &mut (
        Vec<u8>,
        P,
        S,
        F,
        MBFN,
        ItemSliceSend<Item<T>>,
    ),
    hash_len: usize,
) -> Result<(), Error>
where
    T: Send,
    F: for<'r> Fn(EntryRange, &'r mut Vec<u8>) -> 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<u8>), 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,
        Some(unit::dynamic(unit::Human::new(
            unit::human::Formatter::new(),
            "objects",
        ))),
    );

    // 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<dyn std::error::Error + Send + Sync>)?;
            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<dyn std::error::Error + Send + Sync>)?;
                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(())
}

Instantiate an Entry from the reader r, providing the pack_offset to allow tracking the start of the entry data section.

Examples found in repository?
src/cache/delta/from_offsets.rs (line 89)
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

    pub fn from_offsets_in_pack(
        pack_path: impl AsRef<std::path::Path>,
        data_sorted_by_offsets: impl Iterator<Item = T>,
        get_pack_offset: impl Fn(&T) -> data::Offset,
        resolve_in_pack_id: impl Fn(&git_hash::oid) -> Option<data::Offset>,
        mut progress: impl Progress,
        should_interrupt: &AtomicBool,
        object_hash: git_hash::Kind,
    ) -> Result<Self, Error> {
        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 anticpiated_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(anticpiated_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::<u64>;

        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)
    }
More examples
Hide additional examples
src/data/input/bytes_to_entries.rs (line 100)
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

    fn next_inner(&mut self) -> Result<input::Entry, input::Error> {
        self.objects_left -= 1; // even an error counts as objects

        // Read header
        let entry = match self.hash.take() {
            Some(hash) => {
                let mut read = read_and_pass_to(
                    &mut self.read,
                    hash::Write {
                        inner: io::sink(),
                        hash,
                    },
                );
                let res = crate::data::Entry::from_read(&mut read, self.offset, self.hash_len);
                self.hash = Some(read.write.hash);
                res
            }
            None => crate::data::Entry::from_read(&mut self.read, self.offset, self.hash_len),
        }
        .map_err(input::Error::from)?;

        // Decompress object to learn its compressed bytes
        let mut decompressor = self
            .decompressor
            .take()
            .unwrap_or_else(|| Box::new(Decompress::new(true)));
        let compressed_buf = self.compressed_buf.take().unwrap_or_else(|| Vec::with_capacity(4096));
        decompressor.reset(true);
        let mut decompressed_reader = ReadBoxed {
            inner: read_and_pass_to(
                &mut self.read,
                if self.compressed.keep() {
                    Vec::with_capacity(entry.decompressed_size as usize)
                } else {
                    compressed_buf
                },
            ),
            decompressor,
        };

        let bytes_copied = io::copy(&mut decompressed_reader, &mut io::sink())?;
        if bytes_copied != entry.decompressed_size {
            return Err(input::Error::IncompletePack {
                actual: bytes_copied,
                expected: entry.decompressed_size,
            });
        }

        let pack_offset = self.offset;
        let compressed_size = decompressed_reader.decompressor.total_in();
        self.offset += entry.header_size() as u64 + compressed_size;
        self.decompressor = Some(decompressed_reader.decompressor);

        let mut compressed = decompressed_reader.inner.write;
        debug_assert_eq!(
            compressed_size,
            compressed.len() as u64,
            "we must track exactly the same amount of bytes as read by the decompressor"
        );
        if let Some(hash) = self.hash.as_mut() {
            hash.update(&compressed);
        }

        let crc32 = if self.compressed.crc32() {
            let mut header_buf = [0u8; 12 + git_hash::Kind::longest().len_in_bytes()];
            let header_len = entry.header.write_to(bytes_copied, header_buf.as_mut())?;
            let state = git_features::hash::crc32_update(0, &header_buf[..header_len]);
            Some(git_features::hash::crc32_update(state, &compressed))
        } else {
            None
        };

        let compressed = if self.compressed.keep() {
            Some(compressed)
        } else {
            compressed.clear();
            self.compressed_buf = Some(compressed);
            None
        };

        // Last objects gets trailer (which is potentially verified)
        let trailer = self.try_read_trailer()?;
        Ok(input::Entry {
            header: entry.header,
            header_size: entry.header_size() as u16,
            compressed,
            compressed_size,
            crc32,
            pack_offset,
            decompressed_size: bytes_copied,
            trailer,
        })
    }
source§

impl Entry

Access

Compute the pack offset to the base entry of the object represented by this entry.

Examples found in repository?
src/data/file/decode/header.rs (line 63)
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

    pub fn decode_header(
        &self,
        mut entry: data::Entry,
        resolve: impl Fn(&git_hash::oid) -> Option<ResolvedBase>,
    ) -> Result<Outcome, Error> {
        use crate::data::entry::Header::*;
        let mut num_deltas = 0;
        let mut first_delta_decompressed_size = None::<u64>;
        loop {
            match entry.header {
                Tree | Blob | Commit | Tag => {
                    return Ok(Outcome {
                        kind: entry.header.as_kind().expect("always valid for non-refs"),
                        object_size: first_delta_decompressed_size.unwrap_or(entry.decompressed_size),
                        num_deltas,
                    });
                }
                OfsDelta { base_distance } => {
                    num_deltas += 1;
                    if first_delta_decompressed_size.is_none() {
                        first_delta_decompressed_size = Some(self.decode_delta_object_size(&entry)?);
                    }
                    entry = self.entry(entry.base_pack_offset(base_distance))
                }
                RefDelta { base_id } => {
                    num_deltas += 1;
                    if first_delta_decompressed_size.is_none() {
                        first_delta_decompressed_size = Some(self.decode_delta_object_size(&entry)?);
                    }
                    match resolve(base_id.as_ref()) {
                        Some(ResolvedBase::InPack(base_entry)) => entry = base_entry,
                        Some(ResolvedBase::OutOfPack {
                            kind,
                            num_deltas: origin_num_deltas,
                        }) => {
                            return Ok(Outcome {
                                kind,
                                object_size: first_delta_decompressed_size.unwrap_or(entry.decompressed_size),
                                num_deltas: origin_num_deltas.unwrap_or_default() + num_deltas,
                            })
                        }
                        None => return Err(Error::DeltaBaseUnresolved(base_id)),
                    }
                }
            };
        }
    }
More examples
Hide additional examples
src/data/file/decode/entry.rs (line 235)
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407

    fn resolve_deltas(
        &self,
        last: data::Entry,
        resolve: impl Fn(&git_hash::oid, &mut Vec<u8>) -> Option<ResolvedBase>,
        out: &mut Vec<u8>,
        cache: &mut impl cache::DecodeEntry,
    ) -> Result<Outcome, Error> {
        // all deltas, from the one that produces the desired object (first) to the oldest at the end of the chain
        let mut chain = SmallVec::<[Delta; 10]>::default();
        let first_entry = last.clone();
        let mut cursor = last;
        let mut base_buffer_size: Option<usize> = None;
        let mut object_kind: Option<git_object::Kind> = None;
        let mut consumed_input: Option<usize> = None;

        // Find the first full base, either an undeltified object in the pack or a reference to another object.
        let mut total_delta_data_size: u64 = 0;
        while cursor.header.is_delta() {
            if let Some((kind, packed_size)) = cache.get(self.id, cursor.data_offset, out) {
                base_buffer_size = Some(out.len());
                object_kind = Some(kind);
                // If the input entry is a cache hit, keep the packed size as it must be returned.
                // Otherwise, the packed size will be determined later when decompressing the input delta
                if total_delta_data_size == 0 {
                    consumed_input = Some(packed_size);
                }
                break;
            }
            total_delta_data_size += cursor.decompressed_size;
            let decompressed_size = cursor
                .decompressed_size
                .try_into()
                .expect("a single delta size small enough to fit a usize");
            chain.push(Delta {
                data: Range {
                    start: 0,
                    end: decompressed_size,
                },
                base_size: 0,
                result_size: 0,
                decompressed_size,
                data_offset: cursor.data_offset,
            });
            use crate::data::entry::Header;
            cursor = match cursor.header {
                Header::OfsDelta { base_distance } => self.entry(cursor.base_pack_offset(base_distance)),
                Header::RefDelta { base_id } => match resolve(base_id.as_ref(), out) {
                    Some(ResolvedBase::InPack(entry)) => entry,
                    Some(ResolvedBase::OutOfPack { end, kind }) => {
                        base_buffer_size = Some(end);
                        object_kind = Some(kind);
                        break;
                    }
                    None => return Err(Error::DeltaBaseUnresolved(base_id)),
                },
                _ => unreachable!("cursor.is_delta() only allows deltas here"),
            };
        }

        // This can happen if the cache held the first entry itself
        // We will just treat it as an object then, even though it's technically incorrect.
        if chain.is_empty() {
            return Ok(Outcome::from_object_entry(
                object_kind.expect("object kind as set by cache"),
                &first_entry,
                consumed_input.expect("consumed bytes as set by cache"),
            ));
        };

        // First pass will decompress all delta data and keep it in our output buffer
        // [<possibly resolved base object>]<delta-1..delta-n>...
        // so that we can find the biggest result size.
        let total_delta_data_size: usize = total_delta_data_size.try_into().expect("delta data to fit in memory");

        let chain_len = chain.len();
        let (first_buffer_end, second_buffer_end) = {
            let delta_start = base_buffer_size.unwrap_or(0);
            out.resize(delta_start + total_delta_data_size, 0);

            let delta_range = Range {
                start: delta_start,
                end: delta_start + total_delta_data_size,
            };
            let mut instructions = &mut out[delta_range.clone()];
            let mut relative_delta_start = 0;
            let mut biggest_result_size = 0;
            for (delta_idx, delta) in chain.iter_mut().rev().enumerate() {
                let consumed_from_data_offset = self.decompress_entry_from_data_offset(
                    delta.data_offset,
                    &mut instructions[..delta.decompressed_size],
                )?;
                let is_last_delta_to_be_applied = delta_idx + 1 == chain_len;
                if is_last_delta_to_be_applied {
                    consumed_input = Some(consumed_from_data_offset);
                }

                let (base_size, offset) = delta::decode_header_size(instructions);
                let mut bytes_consumed_by_header = offset;
                biggest_result_size = biggest_result_size.max(base_size);
                delta.base_size = base_size.try_into().expect("base size fits into usize");

                let (result_size, offset) = delta::decode_header_size(&instructions[offset..]);
                bytes_consumed_by_header += offset;
                biggest_result_size = biggest_result_size.max(result_size);
                delta.result_size = result_size.try_into().expect("result size fits into usize");

                // the absolute location into the instructions buffer, so we keep track of the end point of the last
                delta.data.start = relative_delta_start + bytes_consumed_by_header;
                relative_delta_start += delta.decompressed_size;
                delta.data.end = relative_delta_start;

                instructions = &mut instructions[delta.decompressed_size..];
            }

            // Now we can produce a buffer like this
            // [<biggest-result-buffer, possibly filled with resolved base object data>]<biggest-result-buffer><delta-1..delta-n>
            // from [<possibly resolved base object>]<delta-1..delta-n>...
            let biggest_result_size: usize = biggest_result_size
                .try_into()
                .expect("biggest result size small enough to fit into usize");
            let first_buffer_size = biggest_result_size;
            let second_buffer_size = first_buffer_size;
            out.resize(first_buffer_size + second_buffer_size + total_delta_data_size, 0);

            // Now 'rescue' the deltas, because in the next step we possibly overwrite that portion
            // of memory with the base object (in the majority of cases)
            let second_buffer_end = {
                let end = first_buffer_size + second_buffer_size;
                if delta_range.start < end {
                    // …this means that the delta size is even larger than two uncompressed worst-case
                    // intermediate results combined. It would already be undesirable to have it bigger
                    // then the target size (as you could just store the object in whole).
                    // However, this just means that it reuses existing deltas smartly, which as we rightfully
                    // remember stand for an object each. However, this means a lot of data is read to restore
                    // a single object sometimes. Fair enough - package size is minimized that way.
                    out.copy_within(delta_range, end);
                } else {
                    let (buffers, instructions) = out.split_at_mut(end);
                    instructions.copy_from_slice(&buffers[delta_range]);
                }
                end
            };

            // If we don't have a out-of-pack object already, fill the base-buffer by decompressing the full object
            // at which the cursor is left after the iteration
            if base_buffer_size.is_none() {
                let base_entry = cursor;
                debug_assert!(!base_entry.header.is_delta());
                object_kind = base_entry.header.as_kind();
                self.decompress_entry_from_data_offset(base_entry.data_offset, out)?;
            }

            (first_buffer_size, second_buffer_end)
        };

        // From oldest to most recent, apply all deltas, swapping the buffer back and forth
        // TODO: once we have more tests, we could optimize this memory-intensive work to
        //       analyse the delta-chains to only copy data once - after all, with 'copy-from-base' deltas,
        //       all data originates from one base at some point.
        // `out` is: [source-buffer][target-buffer][max-delta-instructions-buffer]
        let (buffers, instructions) = out.split_at_mut(second_buffer_end);
        let (mut source_buf, mut target_buf) = buffers.split_at_mut(first_buffer_end);

        let mut last_result_size = None;
        for (
            delta_idx,
            Delta {
                data,
                base_size,
                result_size,
                ..
            },
        ) in chain.into_iter().rev().enumerate()
        {
            let data = &mut instructions[data];
            if delta_idx + 1 == chain_len {
                last_result_size = Some(result_size);
            }
            delta::apply(&source_buf[..base_size], &mut target_buf[..result_size], data);
            // use the target as source for the next delta
            std::mem::swap(&mut source_buf, &mut target_buf);
        }

        let last_result_size = last_result_size.expect("at least one delta chain item");
        // uneven chains leave the target buffer after the source buffer
        // FIXME(Performance) If delta-chains are uneven, we know we will have to copy bytes over here
        //      Instead we could use a different start buffer, to naturally end up with the result in the
        //      right one.
        //      However, this is a bit more complicated than just that - you have to deal with the base
        //      object, which should also be placed in the second buffer right away. You don't have that
        //      control/knowledge for out-of-pack bases, so this is a special case to deal with, too.
        //      Maybe these invariants can be represented in the type system though.
        if chain_len % 2 == 1 {
            // this seems inverted, but remember: we swapped the buffers on the last iteration
            target_buf[..last_result_size].copy_from_slice(&source_buf[..last_result_size]);
        }
        out.resize(last_result_size, 0);

        let object_kind = object_kind.expect("a base object as root of any delta chain that we are here to resolve");
        let consumed_input = consumed_input.expect("at least one decompressed delta object");
        cache.put(
            self.id,
            first_entry.data_offset,
            out.as_slice(),
            object_kind,
            consumed_input,
        );
        Ok(Outcome {
            kind: object_kind,
            // technically depending on the cache, the chain size is not correct as it might
            // have been cut short by a cache hit. The caller must deactivate the cache to get
            // actual results
            num_deltas: chain_len as u32,
            decompressed_size: first_entry.decompressed_size,
            compressed_size: consumed_input,
            object_size: last_result_size as u64,
        })
    }

The pack offset at which this entry starts

The amount of bytes used to describe this entry in the pack. The header starts at Self::pack_offset()

Examples found in repository?
src/data/entry/mod.rs (line 35)
34
35
36
37
38
39
40
41

    pub fn base_pack_offset(&self, distance: u64) -> data::Offset {
        let pack_offset = self.data_offset - self.header_size() as u64;
        pack_offset.checked_sub(distance).expect("in-bound distance of deltas")
    }
    /// The pack offset at which this entry starts
    pub fn pack_offset(&self) -> data::Offset {
        self.data_offset - self.header_size() as u64
    }
More examples
Hide additional examples
src/bundle/find.rs (line 35)
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

    pub fn get_object_by_index<'a>(
        &self,
        idx: u32,
        out: &'a mut Vec<u8>,
        cache: &mut impl crate::cache::DecodeEntry,
    ) -> Result<(git_object::Data<'a>, crate::data::entry::Location), crate::data::decode::Error> {
        let ofs = self.index.pack_offset_at_index(idx);
        let pack_entry = self.pack.entry(ofs);
        let header_size = pack_entry.header_size();
        self.pack
            .decode_entry(
                pack_entry,
                out,
                |id, _out| {
                    self.index.lookup(id).map(|idx| {
                        crate::data::decode::entry::ResolvedBase::InPack(
                            self.pack.entry(self.index.pack_offset_at_index(idx)),
                        )
                    })
                },
                cache,
            )
            .map(move |r| {
                (
                    git_object::Data {
                        kind: r.kind,
                        data: out.as_slice(),
                    },
                    crate::data::entry::Location {
                        pack_id: self.pack.id,
                        pack_offset: ofs,
                        entry_size: r.compressed_size + header_size,
                    },
                )
            })
    }
src/cache/delta/from_offsets.rs (line 93)
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

    pub fn from_offsets_in_pack(
        pack_path: impl AsRef<std::path::Path>,
        data_sorted_by_offsets: impl Iterator<Item = T>,
        get_pack_offset: impl Fn(&T) -> data::Offset,
        resolve_in_pack_id: impl Fn(&git_hash::oid) -> Option<data::Offset>,
        mut progress: impl Progress,
        should_interrupt: &AtomicBool,
        object_hash: git_hash::Kind,
    ) -> Result<Self, Error> {
        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 anticpiated_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(anticpiated_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::<u64>;

        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)
    }
src/data/input/bytes_to_entries.rs (line 137)
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

    fn next_inner(&mut self) -> Result<input::Entry, input::Error> {
        self.objects_left -= 1; // even an error counts as objects

        // Read header
        let entry = match self.hash.take() {
            Some(hash) => {
                let mut read = read_and_pass_to(
                    &mut self.read,
                    hash::Write {
                        inner: io::sink(),
                        hash,
                    },
                );
                let res = crate::data::Entry::from_read(&mut read, self.offset, self.hash_len);
                self.hash = Some(read.write.hash);
                res
            }
            None => crate::data::Entry::from_read(&mut self.read, self.offset, self.hash_len),
        }
        .map_err(input::Error::from)?;

        // Decompress object to learn its compressed bytes
        let mut decompressor = self
            .decompressor
            .take()
            .unwrap_or_else(|| Box::new(Decompress::new(true)));
        let compressed_buf = self.compressed_buf.take().unwrap_or_else(|| Vec::with_capacity(4096));
        decompressor.reset(true);
        let mut decompressed_reader = ReadBoxed {
            inner: read_and_pass_to(
                &mut self.read,
                if self.compressed.keep() {
                    Vec::with_capacity(entry.decompressed_size as usize)
                } else {
                    compressed_buf
                },
            ),
            decompressor,
        };

        let bytes_copied = io::copy(&mut decompressed_reader, &mut io::sink())?;
        if bytes_copied != entry.decompressed_size {
            return Err(input::Error::IncompletePack {
                actual: bytes_copied,
                expected: entry.decompressed_size,
            });
        }

        let pack_offset = self.offset;
        let compressed_size = decompressed_reader.decompressor.total_in();
        self.offset += entry.header_size() as u64 + compressed_size;
        self.decompressor = Some(decompressed_reader.decompressor);

        let mut compressed = decompressed_reader.inner.write;
        debug_assert_eq!(
            compressed_size,
            compressed.len() as u64,
            "we must track exactly the same amount of bytes as read by the decompressor"
        );
        if let Some(hash) = self.hash.as_mut() {
            hash.update(&compressed);
        }

        let crc32 = if self.compressed.crc32() {
            let mut header_buf = [0u8; 12 + git_hash::Kind::longest().len_in_bytes()];
            let header_len = entry.header.write_to(bytes_copied, header_buf.as_mut())?;
            let state = git_features::hash::crc32_update(0, &header_buf[..header_len]);
            Some(git_features::hash::crc32_update(state, &compressed))
        } else {
            None
        };

        let compressed = if self.compressed.keep() {
            Some(compressed)
        } else {
            compressed.clear();
            self.compressed_buf = Some(compressed);
            None
        };

        // Last objects gets trailer (which is potentially verified)
        let trailer = self.try_read_trailer()?;
        Ok(input::Entry {
            header: entry.header,
            header_size: entry.header_size() as u16,
            compressed,
            compressed_size,
            crc32,
            pack_offset,
            decompressed_size: bytes_copied,
            trailer,
        })
    }
src/cache/delta/traverse/resolve.rs (line 49)
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

pub(crate) fn deltas<T, F, P, MBFN, S, E>(
    object_counter: Option<git_features::progress::StepShared>,
    size_counter: Option<git_features::progress::StepShared>,
    node: &mut crate::cache::delta::Item<T>,
    (bytes_buf, ref mut progress, state, resolve, modify_base, child_items): &mut (
        Vec<u8>,
        P,
        S,
        F,
        MBFN,
        ItemSliceSend<Item<T>>,
    ),
    hash_len: usize,
) -> Result<(), Error>
where
    T: Send,
    F: for<'r> Fn(EntryRange, &'r mut Vec<u8>) -> 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<u8>), 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,
        Some(unit::dynamic(unit::Human::new(
            unit::human::Formatter::new(),
            "objects",
        ))),
    );

    // 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<dyn std::error::Error + Send + Sync>)?;
            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<dyn std::error::Error + Send + Sync>)?;
                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(())
}

Trait Implementations§

source§

impl Clone for Entry

Returns a copy of the value. Read more
Performs copy-assignment from source. Read more
source§

impl Debug for Entry

Formats the value using the given formatter. Read more
source§

impl<'de> Deserialize<'de> for Entry

Deserialize this value from the given Serde deserializer. Read more
source§

impl Hash for Entry

Feeds this value into the given Hasher. Read more
Feeds a slice of this type into the given Hasher. Read more
source§

impl Ord for Entry

This method returns an Ordering between self and other. Read more
Compares and returns the maximum of two values. Read more
Compares and returns the minimum of two values. Read more
Restrict a value to a certain interval. Read more
source§

impl PartialEq<Entry> for Entry

This method tests for self and other values to be equal, and is used by ==.
This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
source§

impl PartialOrd<Entry> for Entry

This method returns an ordering between self and other values if one exists. Read more
This method tests less than (for self and other) and is used by the < operator. Read more
This method tests less than or equal to (for self and other) and is used by the <= operator. Read more
This method tests greater than (for self and other) and is used by the > operator. Read more
This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more
source§

impl Serialize for Entry

Serialize this value into the given Serde serializer. Read more
source§

impl Eq for Entry

source§

impl StructuralEq for Entry

source§

impl StructuralPartialEq for Entry

Auto Trait Implementations§

§

impl RefUnwindSafe for Entry

§

impl Send for Entry

§

impl Sync for Entry

§

impl Unpin for Entry

§

impl UnwindSafe for Entry

Blanket Implementations§

source§

impl<T> Any for Twhere
    T: 'static + ?Sized,

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere
    T: ?Sized,

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere
    T: ?Sized,

Mutably borrows from an owned value. Read more
§

impl<Q, K> Equivalent<K> for Qwhere
    Q: Eq + ?Sized,
    K: Borrow<Q> + ?Sized,

Checks if this value is equivalent to the given key. Read more
source§

impl<T> From<T> for T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere
    U: From<T>,

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere
    T: Clone,

The resulting type after obtaining ownership.
Creates owned data from borrowed data, usually by cloning. Read more
Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere
    U: Into<T>,

The type returned in the event of a conversion error.
Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere
    U: TryFrom<T>,

The type returned in the event of a conversion error.
Performs the conversion.
source§

impl<T> DeserializeOwned for Twhere
    T: for<'de> Deserialize<'de>,