netstack3_tcp/
sack_scoreboard.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! Implements the selective acknowledgement scoreboard data structure as
6//! described in [RFC 6675].
7//!
8//! [RFC 6675]: https://datatracker.ietf.org/doc/html/rfc6675
9
10use netstack3_base::{Mss, SackBlocks, SeqNum};
11
12use crate::internal::congestion::DUP_ACK_THRESHOLD;
13use crate::internal::seq_ranges::{SeqRange, SeqRanges};
14
15#[derive(Debug, Default)]
16#[cfg_attr(test, derive(PartialEq, Eq))]
17pub(crate) struct SackScoreboard {
18    /// The ranges for which we've received selective acknowledgements.
19    ///
20    /// Each range is tagged with a boolean that caches the result of [IsLost] for
21    /// the un-sacked range before it.
22    ///
23    /// [IsLost]: https://datatracker.ietf.org/doc/html/rfc6675#section-4
24    acked_ranges: SeqRanges<bool>,
25    /// Stores the number of bytes assumed to be in transit according to the definition of Pipe
26    /// defined in [RFC 6675 section 4].
27    ///
28    /// [RFC 6675 section 4]: https://datatracker.ietf.org/doc/html/rfc6675#section-4
29    pipe: u32,
30}
31
32impl SackScoreboard {
33    /// Processes an incoming ACK and updates the scoreboard.
34    ///
35    /// - `ack` is the cumulative acknowledgement in the received segment.
36    /// - `snd_nxt` is the value of SND.NXT or the highest sequence number that
37    ///   has been sent out.
38    /// - `high_rxt` is the equivalent to the HighRxt value defined in [RFC 6675
39    ///   section 2], but we define it as the next available sequence number for
40    ///   retransmission (off by one from the RFC definition). It is expected to
41    ///   only be available if loss recovery is initiated.
42    /// - `sack_blocks` are the selective ack blocks informed by the peer in the
43    ///   segment.
44    /// - `smss` is the send size mss.
45    ///
46    /// Any blocks referencing data before `ack` or after `snd_nxt` are
47    /// *ignored* as bad data. We chose to ignore any blocks after `snd_nxt`
48    /// here so the SACK recovery algorithm works as described in [RFC 6675].
49    /// Note that [RFC 6675 section 5.1] calls out that the algorithm described
50    /// in the RFC is not suited to deal with a retransmit timeout, so to avoid
51    /// an improper pipe calculation we ignore any blocks past SND.NXT.
52    ///
53    /// Returns `true` if this segment should be considered a duplicate as per
54    /// the definition in [RFC 6675 section 2].
55    ///
56    /// [RFC 6675]: https://datatracker.ietf.org/doc/html/rfc6675
57    /// [RFC 6675 section 5.1]:
58    ///     https://datatracker.ietf.org/doc/html/rfc6675#section-5.1
59    /// [RFC 6675 Section 2]:
60    ///     https://datatracker.ietf.org/doc/html/rfc6675#section-2
61    pub(crate) fn process_ack(
62        &mut self,
63        ack: SeqNum,
64        snd_nxt: SeqNum,
65        high_rxt: Option<SeqNum>,
66        sack_blocks: &SackBlocks,
67        smss: Mss,
68    ) -> bool {
69        let Self { acked_ranges, pipe } = self;
70
71        // If we receive an ACK that is after SND.NXT, this must be a very
72        // delayed acknowledgement post a retransmission event. The state
73        // machine will eventually move SND.NXT to account for this, but this
74        // violates the scoreboard's expectations.
75        //
76        // Because we need to ensure the pipe is updated accordingly and any
77        // previous SACK ranges are cleared, process this as if it was a full
78        // cumulative ack.
79        let snd_nxt = snd_nxt.latest(ack);
80
81        // Fast exit if there's nothing interesting to do.
82        if acked_ranges.is_empty() && sack_blocks.is_empty() {
83            // Ack must not be after snd_nxt.
84            *pipe = u32::try_from(snd_nxt - ack).unwrap();
85            return false;
86        }
87
88        // Update the scoreboard with the cumulative acknowledgement.
89        //
90        // A note here: we discard all the sacked ranges that start at or after
91        // the acknowledged number. If there is intersection we must assume that
92        // the peer reneged the block.
93        acked_ranges.discard_starting_at_or_before(ack);
94
95        // Insert each valid block in acked ranges.
96        let new = sack_blocks.iter_skip_invalid().fold(false, |new, sack_block| {
97            // NB: SackBlock type here ensures this is a valid non-empty range.
98            let (start, end) = sack_block.into_parts();
99            if start.before_or_eq(ack) || end.after(snd_nxt) {
100                // Ignore block that is not in the expected range [ack, snd_nxt].
101                return new;
102            }
103            // Insert with an arbitrary metadata value, we'll update it with the
104            // IsLost value afterwards.
105            let is_lost = false;
106            let changed = acked_ranges.insert(start..end, is_lost);
107
108            new || changed
109        });
110
111        let sacked_byte_threshold = sacked_bytes_threshold(smss);
112        let high_rxt = high_rxt.unwrap_or(ack);
113        let get_pipe_increment = |hole: SeqRange<bool>| {
114            // From RFC 6675, where S1 is a single
115            // sequence number:
116            //
117            // (a) If IsLost (S1) returns false: Pipe is incremented by 1
118            // octet.
119            // (b) If S1 <= HighRxt: Pipe is incremented by 1 octet.
120            let mut pipe = 0u32;
121            let is_lost = *(hole.meta());
122            if !is_lost {
123                pipe = pipe.saturating_add(hole.len());
124            }
125
126            if let Some(hole) = hole.cap_right(high_rxt) {
127                pipe = pipe.saturating_add(hole.len());
128            }
129            pipe
130        };
131
132        // Recalculate pipe and update IsLost in the collection.
133        //
134        // We iterate acked_ranges in reverse order so we can fold over the
135        // total number of ranges and SACKed bytes that come *after* the range we
136        // operate on at each point.
137        let (new_pipe, _sacked, _count, later_start, later_is_lost) =
138            acked_ranges.iter_mut().rev().fold(
139                (0u32, 0, 0, snd_nxt, false),
140                |(pipe, sacked, count, later_start, later_is_lost), acked_range| {
141                    // IsLost is kept for the hole to the left of this block. So the
142                    // block we're currently iterating on counts as part of is_lost,
143                    // as well as the the total number of sacked bytes.
144                    let count = count + 1;
145                    let sacked = sacked + acked_range.len();
146                    // From RFC 6675, IsLost is defined as:
147                    //
148                    //  The routine returns true when either DupThresh discontiguous
149                    //  SACKed sequences have arrived above 'SeqNum' or more than
150                    //  (DupThresh - 1) * SMSS bytes with sequence numbers greater
151                    //  than 'SeqNum' have been SACKed
152                    let is_lost = count >= DUP_ACK_THRESHOLD || sacked > sacked_byte_threshold;
153                    acked_range.set_meta(is_lost);
154
155                    // Increment pipe. From RFC 6675:
156                    //
157                    //  After initializing pipe to zero, the following steps are
158                    //  taken for each octet 'S1' in the sequence space between
159                    //  HighACK and HighData that has not been SACKed[...]
160                    //
161                    // So pipe is only calculated for the gaps between the acked
162                    // ranges, i.e., from the current end to the start of the
163                    // later block.
164                    let pipe = if let Some(hole) =
165                        SeqRange::new(acked_range.end()..later_start, later_is_lost)
166                    {
167                        pipe.saturating_add(get_pipe_increment(hole))
168                    } else {
169                        // An empty hole can only happen in the first iteration,
170                        // when the right edge is SND.NXT.
171                        assert_eq!(later_start, snd_nxt);
172                        pipe
173                    };
174
175                    (pipe, sacked, count, acked_range.start(), is_lost)
176                },
177            );
178        // Add the final hole between cumulative ack and first sack block
179        // and finalize the pipe value.
180        *pipe = match SeqRange::new(ack..later_start, later_is_lost) {
181            Some(first_hole) => new_pipe.saturating_add(get_pipe_increment(first_hole)),
182            None => {
183                // An empty first hole can only happen if we don't have any
184                // sack blocks, and ACK is equal to SND.NXT.
185                assert_eq!(ack, snd_nxt);
186                new_pipe
187            }
188        };
189
190        new
191    }
192}
193
194/// Returns the threshold over which a sequence number is considered lost per
195/// the definition of `IsLost` in [RFC 6675 section 4].
196///
197/// [RFC 6675 section 4]:
198///     https://datatracker.ietf.org/doc/html/rfc6675#section-4
199fn sacked_bytes_threshold(mss: Mss) -> u32 {
200    u32::from(DUP_ACK_THRESHOLD - 1) * u32::from(mss)
201}
202
203#[cfg(test)]
204mod test {
205    use core::num::NonZeroU16;
206    use core::ops::Range;
207
208    use netstack3_base::SackBlock;
209
210    use super::*;
211    use crate::internal::seq_ranges::SeqRange;
212
213    const TEST_MSS: Mss = Mss(NonZeroU16::new(50).unwrap());
214
215    fn sack_blocks(iter: impl IntoIterator<Item = Range<u32>>) -> SackBlocks {
216        iter.into_iter()
217            .map(|Range { start, end }| {
218                SackBlock::try_new(SeqNum::new(start), SeqNum::new(end)).unwrap()
219            })
220            .collect()
221    }
222
223    fn seq_ranges(iter: impl IntoIterator<Item = (Range<u32>, bool)>) -> SeqRanges<bool> {
224        iter.into_iter()
225            .map(|(Range { start, end }, is_lost)| {
226                SeqRange::new(SeqNum::new(start)..SeqNum::new(end), is_lost).unwrap()
227            })
228            .collect()
229    }
230
231    impl SackScoreboard {
232        fn sacked_bytes(&self) -> u32 {
233            self.acked_ranges.iter().map(|seq_range| seq_range.len()).sum()
234        }
235    }
236
237    #[test]
238    fn process_ack_noop_if_empty() {
239        let mut sb = SackScoreboard::default();
240        let ack = SeqNum::new(1);
241        let snd_nxt = SeqNum::new(100);
242        let high_rxt = None;
243        assert!(!sb.process_ack(ack, snd_nxt, high_rxt, &SackBlocks::default(), TEST_MSS));
244        assert!(sb.acked_ranges.is_empty());
245        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap());
246    }
247
248    #[test]
249    fn process_ack_ignores_bad_blocks() {
250        let mut sb = SackScoreboard::default();
251        let ack = SeqNum::new(5);
252        let snd_nxt = SeqNum::new(100);
253        let high_rxt = None;
254        // Ignores everything that doesn't match the cumulative ack.
255        assert!(!sb.process_ack(
256            ack,
257            snd_nxt,
258            high_rxt,
259            &sack_blocks([0..1, 4..6, 5..10]),
260            TEST_MSS
261        ));
262        assert!(sb.acked_ranges.is_empty());
263
264        // Ignores everything past snd_nxt.
265        assert!(!sb.process_ack(
266            ack,
267            snd_nxt,
268            high_rxt,
269            &sack_blocks([100..200, 50..150]),
270            TEST_MSS
271        ));
272        assert!(sb.acked_ranges.is_empty());
273    }
274
275    #[test]
276    fn process_ack_cumulative_ack() {
277        let mut sb = SackScoreboard::default();
278        let ack = SeqNum::new(5);
279        let snd_nxt = SeqNum::new(100);
280        let high_rxt = None;
281        let blocks = sack_blocks([20..30]);
282        assert!(sb.process_ack(ack, snd_nxt, high_rxt, &blocks, TEST_MSS));
283        let expect_ranges = seq_ranges([(20..30, false)]);
284        assert_eq!(sb.acked_ranges, expect_ranges);
285        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap() - sb.sacked_bytes());
286
287        let ack = SeqNum::new(10);
288        assert!(!sb.process_ack(ack, snd_nxt, high_rxt, &blocks, TEST_MSS));
289        assert_eq!(sb.acked_ranges, expect_ranges);
290        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap() - sb.sacked_bytes());
291    }
292
293    #[test]
294    fn process_ack_is_lost_dup_thresh() {
295        let mut sb = SackScoreboard::default();
296        let ack = SeqNum::new(5);
297        let snd_nxt = SeqNum::new(100);
298        let high_rxt = None;
299
300        let block1 = 20..30;
301        let block2 = 35..40;
302        let block3 = 45..50;
303
304        assert!(sb.process_ack(
305            ack,
306            snd_nxt,
307            high_rxt,
308            &sack_blocks([block1.clone(), block2.clone(), block3.clone()]),
309            TEST_MSS
310        ));
311        assert_eq!(
312            sb.acked_ranges,
313            seq_ranges([(block1.clone(), true), (block2, false), (block3, false)])
314        );
315        assert_eq!(
316            sb.pipe,
317            u32::try_from(snd_nxt - ack).unwrap()
318                - sb.sacked_bytes()
319                - (block1.start - u32::from(ack))
320        );
321    }
322
323    #[test]
324    fn process_ack_pipe_rule_a() {
325        let mut sb = SackScoreboard::default();
326        let ack = SeqNum::new(5);
327        let snd_nxt = SeqNum::new(500);
328        let high_rxt = None;
329        let small_block = 20..30;
330        let large_block_start = 35;
331        let large_block = large_block_start..(large_block_start + sacked_bytes_threshold(TEST_MSS));
332
333        assert!(sb.process_ack(
334            ack,
335            snd_nxt,
336            high_rxt,
337            &sack_blocks([small_block.clone(), large_block.clone()]),
338            TEST_MSS
339        ));
340        // Large block is exactly at the limit of the hole to its left being
341        // considered lost as well.
342        assert_eq!(
343            sb.acked_ranges,
344            seq_ranges([(small_block.clone(), true), (large_block.clone(), false)])
345        );
346        assert_eq!(
347            sb.pipe,
348            u32::try_from(snd_nxt - ack).unwrap()
349                - sb.sacked_bytes()
350                - (small_block.start - u32::from(ack))
351        );
352
353        // Now increase the large block by one.
354        let large_block = large_block.start..(large_block.end + 1);
355        assert!(sb.process_ack(
356            ack,
357            snd_nxt,
358            high_rxt,
359            &sack_blocks([small_block.clone(), large_block.clone()]),
360            TEST_MSS
361        ));
362        // Now the hole to the left of large block is also considered lost.
363        assert_eq!(
364            sb.acked_ranges,
365            seq_ranges([(small_block.clone(), true), (large_block.clone(), true)])
366        );
367        assert_eq!(
368            sb.pipe,
369            u32::try_from(snd_nxt - ack).unwrap()
370                - sb.sacked_bytes()
371                - (small_block.start - u32::from(ack))
372                - (large_block.start - small_block.end)
373        );
374    }
375
376    #[test]
377    fn process_ack_pipe_rule_b() {
378        let ack = SeqNum::new(5);
379        let snd_nxt = SeqNum::new(500);
380        let first_block = 20..30;
381        let second_block = 40..50;
382
383        let blocks = sack_blocks([first_block.clone(), second_block.clone()]);
384
385        // Extract the baseline pipe that if we receive an ACK with the
386        // parameters above but without a HighRxt value.
387        let baseline = {
388            let mut sb = SackScoreboard::default();
389            assert!(sb.process_ack(ack, snd_nxt, None, &blocks, TEST_MSS));
390            sb.pipe
391        };
392
393        // Drive HighRxt across the entire possible sequence number range that
394        // we expect to see it and check the pipe value is changing accordingly.
395        let hole1 = (u32::from(ack)..first_block.start).map(|seq| (seq, true));
396        let block1 = first_block.clone().map(|seq| (seq, false));
397        let hole2 = (first_block.end..second_block.start).map(|seq| (seq, true));
398        let block2 = second_block.map(|seq| (seq, false));
399        // Shift expecting an increment one over because HighRxt starting at
400        // HighAck is expected to be a zero contribution. This aligns the
401        // off-by-one in the expectations.
402        let iter =
403            hole1.chain(block1).chain(hole2).chain(block2).scan(false, |prev, (seq, sacked)| {
404                let expect_increment = core::mem::replace(prev, sacked);
405                Some((seq, expect_increment))
406            });
407
408        let _: u32 = iter.fold(0u32, |total, (seq, expect_increment)| {
409            let total = total + u32::from(expect_increment);
410            let mut sb = SackScoreboard::default();
411            assert!(sb.process_ack(ack, snd_nxt, Some(SeqNum::new(seq)), &blocks, TEST_MSS));
412            assert_eq!(sb.pipe - baseline, total, "at {seq}");
413            total
414        });
415    }
416
417    #[test]
418    fn process_ack_simple() {
419        let mut sb = SackScoreboard::default();
420        let ack = SeqNum::new(5);
421        let snd_nxt = SeqNum::new(500);
422        let high_rxt = None;
423
424        // Receive a single cumulative ack up to ack.
425        assert!(!sb.process_ack(ack, snd_nxt, high_rxt, &SackBlocks::default(), TEST_MSS));
426        assert_eq!(sb.acked_ranges, SeqRanges::default(),);
427        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap());
428
429        // Cumulative ack doesn't move, 1 SACK range signaling loss is received.
430        let sack1 = 10..(10 + sacked_bytes_threshold(TEST_MSS) + 1);
431        assert!(sb.process_ack(ack, snd_nxt, high_rxt, &sack_blocks([sack1.clone()]), TEST_MSS));
432        assert_eq!(sb.acked_ranges, seq_ranges([(sack1.clone(), true)]),);
433        assert_eq!(
434            sb.pipe,
435            u32::try_from(snd_nxt - ack).unwrap()
436                - sb.sacked_bytes()
437                - (sack1.start - u32::from(ack))
438        );
439
440        // Another SACK range comes in, at the end of this transmission block.
441        let sack2 = (u32::from(snd_nxt) - u32::from(TEST_MSS))..u32::from(snd_nxt);
442        assert!(sb.process_ack(
443            ack,
444            snd_nxt,
445            high_rxt,
446            &sack_blocks([sack1.clone(), sack2.clone()]),
447            TEST_MSS
448        ));
449        assert_eq!(sb.acked_ranges, seq_ranges([(sack1.clone(), true), (sack2.clone(), false)]));
450        assert_eq!(
451            sb.pipe,
452            u32::try_from(snd_nxt - ack).unwrap()
453                - sb.sacked_bytes()
454                - (sack1.start - u32::from(ack))
455        );
456
457        // Cumulative acknowledge the first SACK range.
458        let ack = SeqNum::new(sack1.end);
459        assert!(!sb.process_ack(ack, snd_nxt, high_rxt, &sack_blocks([sack2.clone()]), TEST_MSS));
460        assert_eq!(sb.acked_ranges, seq_ranges([(sack2, false)]));
461        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap() - sb.sacked_bytes());
462
463        // Cumulative acknowledge all the transmission.
464        assert!(!sb.process_ack(snd_nxt, snd_nxt, high_rxt, &SackBlocks::default(), TEST_MSS));
465        assert_eq!(sb.acked_ranges, SeqRanges::default());
466        assert_eq!(sb.pipe, 0);
467    }
468
469    #[test]
470    fn ack_after_snd_nxt() {
471        let mut sb = SackScoreboard::default();
472        let ack = SeqNum::new(5);
473        let snd_nxt = SeqNum::new(500);
474        let high_rxt = None;
475        let block = 10..20;
476        assert!(sb.process_ack(ack, snd_nxt, high_rxt, &sack_blocks([block.clone()]), TEST_MSS));
477        assert_eq!(sb.acked_ranges, seq_ranges([(block.clone(), false)]));
478        assert_eq!(sb.pipe, u32::try_from(snd_nxt - ack).unwrap() - sb.sacked_bytes());
479
480        // SND.NXT rewinds after RTO.
481        let snd_nxt = ack;
482        // But we receive an ACK post the kept block.
483        let ack = SeqNum::new(block.end);
484        assert!(ack.after(snd_nxt));
485        assert!(!sb.process_ack(ack, snd_nxt, high_rxt, &SackBlocks::default(), TEST_MSS));
486        assert_eq!(sb.acked_ranges, SeqRanges::default());
487        assert_eq!(sb.pipe, 0);
488    }
489}
netstack3_tcp/sack_scoreboard.rs

netstack3_tcp/
sack_scoreboard.rs
