Skip to main content

prolink_capture/
sparse.rs

1// SPDX-License-Identifier: GPL-3.0-only
2
3//! Bytes that arrive at offsets, with the holes between them kept as holes.
4//!
5//! Two of this crate's jobs are the same job: an IP datagram arrives as
6//! fragments carrying a byte offset, and a TCP flow arrives as segments
7//! carrying a sequence number. Both can arrive out of order, both can arrive
8//! twice, and in both a piece can simply never arrive. The one thing neither
9//! may do is close the hole up, because the protocols above have no framing
10//! that would let a reader notice: a dbserver message is delimited by nothing
11//! but its own contents, so concatenating across a gap does not fail, it
12//! decodes the following bytes as a field and every message after that is one
13//! position out.
14//!
15//! So [`Sparse`] never concatenates. It holds a list of [`Run`]s — maximal
16//! stretches that did arrive contiguously — and a caller that needs the whole
17//! thing asks [`Sparse::contiguous`], which answers `None` when there is a
18//! hole rather than answering with bytes that are not what was sent.
19//!
20//! # Overlaps
21//!
22//! A retransmission normally repeats bytes already held. The policy here is
23//! **first writer wins**: bytes already in a run are kept and the arriving
24//! copy is used only where nothing is held yet. That is what a receiving TCP
25//! stack does, so it reconstructs what the peer above the wire actually saw.
26//! It also makes a capture recorded on two interfaces of one bridge — which is
27//! what most of this project's corpus is — collapse to a single copy for free.
28
29/// A stretch of bytes that arrived contiguously, and where it starts.
30#[derive(Clone, PartialEq, Eq)]
31pub struct Run {
32    offset: u64,
33    data: Vec<u8>,
34}
35
36impl Run {
37    /// Offset of the first byte, from the start of the reassembled whole.
38    pub fn offset(&self) -> u64 {
39        self.offset
40    }
41
42    /// One past the last byte.
43    pub fn end(&self) -> u64 {
44        self.offset
45            .saturating_add(self.data.len().try_into().unwrap_or(u64::MAX))
46    }
47
48    /// The bytes.
49    pub fn data(&self) -> &[u8] {
50        &self.data
51    }
52}
53
54impl std::fmt::Debug for Run {
55    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56        write!(
57            f,
58            "Run({}..{}, {} bytes)",
59            self.offset,
60            self.end(),
61            self.data.len()
62        )
63    }
64}
65
66/// A stretch that never arrived.
67#[derive(Clone, Copy, PartialEq, Eq, Debug)]
68pub struct Gap {
69    /// Offset of the first missing byte.
70    pub offset: u64,
71    /// How many bytes are missing.
72    pub len: u64,
73}
74
75/// Bytes placed at offsets, with the holes between them preserved.
76///
77/// The runs are kept sorted by offset, never overlapping and never merely
78/// touching — two runs in the list always have a real hole between them, which
79/// is what makes `runs.len() == 1` a proof of completeness rather than a hint.
80#[derive(Clone, Default)]
81pub(crate) struct Sparse {
82    runs: Vec<Run>,
83}
84
85impl Sparse {
86    /// An empty buffer.
87    pub(crate) fn new() -> Self {
88        Self { runs: Vec::new() }
89    }
90
91    /// Place `data` at `offset`, keeping any bytes already held there.
92    pub(crate) fn insert(&mut self, offset: u64, data: &[u8]) {
93        if data.is_empty() {
94            return;
95        }
96        let len: u64 = data.len().try_into().unwrap_or(u64::MAX);
97        let end = offset.saturating_add(len);
98
99        // Runs are sorted and disjoint, so the ones that overlap or touch
100        // `offset..=end` form one contiguous window of the list.
101        let first = self.runs.partition_point(|run| run.end() < offset);
102        let last = self.runs.partition_point(|run| run.offset <= end);
103        let Some(window) = self.runs.get(first..last) else {
104            return;
105        };
106
107        let mut merged_start = offset;
108        let mut merged_end = end;
109        for run in window {
110            merged_start = merged_start.min(run.offset);
111            merged_end = merged_end.max(run.end());
112        }
113        let Ok(size) = usize::try_from(merged_end.saturating_sub(merged_start)) else {
114            // A single run larger than this platform's address space cannot be
115            // built, so there is nothing honest to do but leave it out.
116            return;
117        };
118
119        let mut merged = vec![0u8; size];
120        // The arriving bytes go down first and the bytes already held go on
121        // top of them, which is what makes the policy first-writer-wins.
122        copy_into(&mut merged, offset.saturating_sub(merged_start), data);
123        for run in window {
124            copy_into(
125                &mut merged,
126                run.offset.saturating_sub(merged_start),
127                &run.data,
128            );
129        }
130        self.runs.splice(
131            first..last,
132            [Run {
133                offset: merged_start,
134                data: merged,
135            }],
136        );
137    }
138
139    /// Shift every run forward by `amount`, to make room below offset zero.
140    ///
141    /// Needed when the first bytes seen on a TCP flow turn out not to be its
142    /// earliest: the base has to move, and everything already held moves with
143    /// it. See [`crate::tcp`].
144    pub(crate) fn shift(&mut self, amount: u64) {
145        for run in &mut self.runs {
146            run.offset = run.offset.saturating_add(amount);
147        }
148    }
149
150    /// The runs, in offset order.
151    pub(crate) fn runs(&self) -> &[Run] {
152        &self.runs
153    }
154
155    /// Everything, as one slice — or `None` when a hole splits it.
156    ///
157    /// Also `None` when the buffer starts above offset zero, because a missing
158    /// prefix is a hole like any other.
159    pub(crate) fn contiguous(&self) -> Option<&[u8]> {
160        match self.runs.as_slice() {
161            [only] if only.offset == 0 => Some(&only.data),
162            _ => None,
163        }
164    }
165
166    /// The holes, in offset order, including a leading one.
167    pub(crate) fn gaps(&self) -> Vec<Gap> {
168        let mut gaps = Vec::new();
169        let mut cursor = 0u64;
170        for run in &self.runs {
171            if run.offset > cursor {
172                gaps.push(Gap {
173                    offset: cursor,
174                    len: run.offset.saturating_sub(cursor),
175                });
176            }
177            cursor = run.end();
178        }
179        gaps
180    }
181
182    /// How many bytes are held, not counting the holes.
183    pub(crate) fn len(&self) -> u64 {
184        self.runs
185            .iter()
186            .map(|run| run.end().saturating_sub(run.offset))
187            .sum()
188    }
189
190    /// True when nothing has been placed yet.
191    pub(crate) fn is_empty(&self) -> bool {
192        self.runs.is_empty()
193    }
194}
195
196impl std::fmt::Debug for Sparse {
197    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
198        f.debug_list().entries(&self.runs).finish()
199    }
200}
201
202/// Write `source` into `target` at `at`, dropping anything past the end.
203fn copy_into(target: &mut [u8], at: u64, source: &[u8]) {
204    let Ok(start) = usize::try_from(at) else {
205        return;
206    };
207    let Some(end) = start.checked_add(source.len()) else {
208        return;
209    };
210    if let Some(slot) = target.get_mut(start..end) {
211        slot.copy_from_slice(source);
212    }
213}
214
215#[cfg(test)]
216mod tests {
217    use super::*;
218
219    fn runs(sparse: &Sparse) -> Vec<(u64, Vec<u8>)> {
220        sparse
221            .runs()
222            .iter()
223            .map(|run| (run.offset(), run.data().to_vec()))
224            .collect()
225    }
226
227    #[test]
228    fn pieces_arriving_in_order_become_one_run() {
229        let mut sparse = Sparse::new();
230        sparse.insert(0, b"abc");
231        sparse.insert(3, b"def");
232        assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
233        assert!(sparse.gaps().is_empty());
234    }
235
236    #[test]
237    fn pieces_arriving_backwards_still_become_one_run() {
238        let mut sparse = Sparse::new();
239        sparse.insert(6, b"ghi");
240        sparse.insert(0, b"abc");
241        sparse.insert(3, b"def");
242        assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
243    }
244
245    #[test]
246    fn a_hole_is_reported_rather_than_closed_up() {
247        let mut sparse = Sparse::new();
248        sparse.insert(0, b"abc");
249        sparse.insert(10, b"xyz");
250        assert_eq!(
251            sparse.contiguous(),
252            None,
253            "concatenating across a hole would be a lie"
254        );
255        assert_eq!(
256            runs(&sparse),
257            vec![(0, b"abc".to_vec()), (10, b"xyz".to_vec())]
258        );
259        assert_eq!(sparse.gaps(), vec![Gap { offset: 3, len: 7 }]);
260        assert_eq!(sparse.len(), 6);
261    }
262
263    #[test]
264    fn a_missing_prefix_is_a_hole_too() {
265        let mut sparse = Sparse::new();
266        sparse.insert(4, b"abc");
267        assert_eq!(sparse.contiguous(), None);
268        assert_eq!(sparse.gaps(), vec![Gap { offset: 0, len: 4 }]);
269    }
270
271    #[test]
272    fn a_hole_closes_when_the_missing_piece_arrives() {
273        let mut sparse = Sparse::new();
274        sparse.insert(0, b"abc");
275        sparse.insert(6, b"ghi");
276        sparse.insert(3, b"def");
277        assert_eq!(sparse.contiguous(), Some(b"abcdefghi".as_slice()));
278        assert_eq!(sparse.runs().len(), 1);
279    }
280
281    #[test]
282    fn a_retransmission_does_not_disturb_bytes_already_held() {
283        let mut sparse = Sparse::new();
284        sparse.insert(0, b"abcdef");
285        // The same segment again, but corrupt. A receiver would have kept the
286        // first copy, so this must too.
287        sparse.insert(2, b"ZZ");
288        assert_eq!(sparse.contiguous(), Some(b"abcdef".as_slice()));
289    }
290
291    #[test]
292    fn an_overlapping_segment_contributes_only_its_new_bytes() {
293        let mut sparse = Sparse::new();
294        sparse.insert(0, b"abc");
295        sparse.insert(2, b"ZZZZ"); // covers 2..6; only 3..6 is new
296        assert_eq!(sparse.contiguous(), Some(b"abcZZZ".as_slice()));
297    }
298
299    #[test]
300    fn a_segment_spanning_several_runs_fills_only_the_holes() {
301        let mut sparse = Sparse::new();
302        sparse.insert(0, b"ab");
303        sparse.insert(6, b"gh");
304        sparse.insert(0, b"ZZZZZZZZ");
305        assert_eq!(sparse.contiguous(), Some(b"abZZZZgh".as_slice()));
306    }
307
308    #[test]
309    fn a_segment_between_two_runs_does_not_merge_them_when_it_reaches_neither() {
310        let mut sparse = Sparse::new();
311        sparse.insert(0, b"ab");
312        sparse.insert(10, b"kl");
313        sparse.insert(5, b"f");
314        assert_eq!(sparse.runs().len(), 3);
315        assert_eq!(
316            sparse.gaps(),
317            vec![Gap { offset: 2, len: 3 }, Gap { offset: 6, len: 4 }]
318        );
319    }
320
321    #[test]
322    fn duplicate_inserts_cost_nothing() {
323        let mut sparse = Sparse::new();
324        for _ in 0..5 {
325            sparse.insert(0, b"abc");
326        }
327        assert_eq!(sparse.runs().len(), 1);
328        assert_eq!(sparse.len(), 3);
329    }
330
331    #[test]
332    fn shifting_moves_every_run() {
333        let mut sparse = Sparse::new();
334        sparse.insert(0, b"abc");
335        sparse.insert(10, b"xyz");
336        sparse.shift(4);
337        assert_eq!(
338            runs(&sparse),
339            vec![(4, b"abc".to_vec()), (14, b"xyz".to_vec())]
340        );
341    }
342
343    #[test]
344    fn an_empty_insert_is_not_a_run() {
345        let mut sparse = Sparse::new();
346        sparse.insert(7, b"");
347        assert!(sparse.is_empty());
348        assert_eq!(sparse.contiguous(), None);
349    }
350}