s2n_quic_core/packet/number/
sliding_window.rs

1// Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0
3
4use crate::{packet::number::PacketNumber, varint::VarInt};
5use core::mem;
6
7#[derive(Clone, Default, Debug)]
8pub struct SlidingWindow {
9    /// Bitfield representing each packet number less than
10    /// the right edge up to the window width.
11    window: Window,
12    /// The highest packet number seen so far, which is the
13    /// right edge of the window.
14    right_edge: Option<PacketNumber>,
15}
16
17#[derive(Clone, Copy, Debug, PartialEq)]
18pub enum SlidingWindowError {
19    Duplicate,
20    TooOld,
21}
22
23/// 128-bit wide window allowing for 128 packets, plus the highest
24/// packet representing the right edge to be tracked.
25type Window = u128;
26
27/// The total width of the window = the size of the 128-bit bitfield + 1 more bit
28/// representing the right edge, which is always set.
29const WINDOW_WIDTH: u64 = 1 + mem::size_of::<Window>() as u64 * 8;
30
31#[derive(Debug, PartialEq, Eq)]
32enum WindowPosition {
33    /// Left of the window, assumed to be a duplicate.
34    Left,
35    /// Right of the window, the value is the offset from the right edge.
36    Right(u64),
37    /// Equal to the highest value tracked by the window.
38    RightEdge,
39    /// Within the window, the value is the offset from the right edge.
40    Within(u64),
41    /// The window is empty.
42    Empty,
43}
44
45/// A set with entries that were removed/slid past from SlidingWindow during insertion.
46#[derive(Default, Clone)]
47pub struct EvictedSet {
48    /// Bitfield representing each packet number less than
49    /// the right edge up to the window width.
50    ///
51    /// Bits are 1 if they are returned by next().
52    window: Window,
53    /// The highest packet number seen so far, which is the
54    /// right edge of the window.
55    ///
56    /// This number is never included in this set.
57    right_edge: PacketNumber,
58}
59
60impl core::fmt::Debug for EvictedSet {
61    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
62        f.debug_set().entries(self.clone()).finish()
63    }
64}
65
66impl PartialEq for EvictedSet {
67    fn eq(&self, other: &Self) -> bool {
68        self.clone().eq(other.clone())
69    }
70}
71
72impl Iterator for EvictedSet {
73    type Item = PacketNumber;
74
75    fn next(&mut self) -> Option<PacketNumber> {
76        loop {
77            // If the window is empty, there is nothing in the set.
78            if self.window == 0 {
79                return None;
80            }
81
82            let shift = self.window.leading_zeros() + 1;
83
84            // Shift the right edge to the right such that the first set bit is in the leftmost
85            // position. If we have a leading 1, then this is a shift by 1.
86            //
87            // That set bit represents the smallest included bit.
88            self.right_edge = PacketNumber::from_varint(
89                PacketNumber::as_varint(self.right_edge) + VarInt::from_u32(shift),
90                self.right_edge.space(),
91            );
92
93            // We shift in zeros, which are not in the set.
94            if shift == Window::BITS {
95                self.window = 0;
96            } else {
97                self.window <<= shift;
98            }
99
100            if let Some(left_edge) = PacketNumber::as_varint(self.right_edge)
101                .checked_sub(VarInt::from_u32(WINDOW_WIDTH as u32))
102            {
103                return Some(PacketNumber::from_varint(
104                    left_edge,
105                    self.right_edge.space(),
106                ));
107            } else {
108                // If the bit is set, but it's less than zero in value, then that's a spuriously set
109                // bit.
110                continue;
111            }
112        }
113    }
114}
115
116//= https://www.rfc-editor.org/rfc/rfc4303#section-3.4.3
117//# Duplicates are rejected through the use of a sliding receive window.
118//# How the window is implemented is a local matter, but the following
119//# text describes the functionality that the implementation must
120//# exhibit.
121//#
122//# The "right" edge of the window represents the highest, validated
123//# Sequence Number value received on this SA.  Packets that contain
124//# sequence numbers lower than the "left" edge of the window are
125//# rejected.  Packets falling within the window are checked against a
126//# list of received packets within the window.
127impl SlidingWindow {
128    /// Inserts the `packet_number` into the sliding window, returning
129    /// a SlidingWindowError::Duplicate if the `packet_number` has already
130    /// been inserted into the sliding window or a SlidingWindowError::TooOld
131    /// if the `packet_number` is beyond the capacity of the sliding window and
132    /// thus cannot be determined if it is a duplicate.
133    pub fn insert(&mut self, packet_number: PacketNumber) -> Result<(), SlidingWindowError> {
134        self.insert_with_evicted(packet_number).map(|_| ())
135    }
136
137    /// Inserts the `packet_number` into the sliding window, returning
138    /// a SlidingWindowError::Duplicate if the `packet_number` has already
139    /// been inserted into the sliding window or a SlidingWindowError::TooOld
140    /// if the `packet_number` is beyond the capacity of the sliding window and
141    /// thus cannot be determined if it is a duplicate.
142    ///
143    /// Returns Ok(None) if insert didn't slide past an entry that would have returned Ok(...) had it
144    /// been inserted prior to this insert, and Ok(entries) for those we did slide past.
145    pub fn insert_with_evicted(
146        &mut self,
147        packet_number: PacketNumber,
148    ) -> Result<EvictedSet, SlidingWindowError> {
149        #[cfg(debug_assertions)]
150        let initial = self.clone();
151
152        let res = self.insert_with_evicted_inner(packet_number);
153
154        #[cfg(debug_assertions)]
155        self.check_insert_result(packet_number, initial, &res);
156
157        res
158    }
159
160    fn insert_with_evicted_inner(
161        &mut self,
162        packet_number: PacketNumber,
163    ) -> Result<EvictedSet, SlidingWindowError> {
164        match self.window_position(packet_number) {
165            WindowPosition::Left => Err(SlidingWindowError::TooOld),
166            WindowPosition::RightEdge => Err(SlidingWindowError::Duplicate),
167            WindowPosition::Right(delta) => {
168                let removed = if delta < WINDOW_WIDTH {
169                    // Keep only the bits that we would have shifted out.
170                    let removed_mask = if delta == 128 {
171                        u128::MAX
172                    } else {
173                        !u128::MAX.wrapping_shr(delta as u32)
174                    };
175                    let removed = !self.window & removed_mask;
176                    // Shift by delta.
177                    self.window = self.window.checked_shl(delta as u32).unwrap_or(0);
178                    // Set the bit for the current right edge
179                    self.window |= 1 << (delta - 1);
180                    removed
181                } else {
182                    // The delta is too large, reset the window
183                    let removed = self.window;
184                    self.window = 0;
185                    // Invert the bits, since we want the not present bits.
186                    // Our mask is the full window since it's all getting evicted.
187                    !removed
188                };
189                if let Some(prev_right_edge) = self.right_edge.replace(packet_number) {
190                    Ok(EvictedSet {
191                        window: removed,
192                        right_edge: prev_right_edge,
193                    })
194                } else {
195                    // If there was not a right edge, we should not have any bits set.
196                    assert!(removed == 0);
197                    Ok(EvictedSet::default())
198                }
199            }
200            WindowPosition::Within(delta) => {
201                let mask = 1 << (delta - 1); // Shift by the delta - 1 to account for the right edge
202                let duplicate = self.window & mask != 0;
203                self.window |= mask;
204                if duplicate {
205                    Err(SlidingWindowError::Duplicate)
206                } else {
207                    Ok(EvictedSet::default())
208                }
209            }
210            WindowPosition::Empty => {
211                self.right_edge = Some(packet_number);
212                Ok(EvictedSet::default())
213            }
214        }
215    }
216
217    #[cfg_attr(not(debug_assertions), allow(dead_code))]
218    fn check_insert_result(
219        &self,
220        packet_number: PacketNumber,
221        initial: Self,
222        res: &Result<EvictedSet, SlidingWindowError>,
223    ) {
224        let evicted = match res {
225            Ok(evicted) => evicted,
226            Err(_) => {
227                // On error we should not have changed ourselves.
228                assert_eq!(self.window, initial.window);
229                assert_eq!(self.right_edge, initial.right_edge);
230                return;
231            }
232        };
233
234        {
235            for pn in evicted.clone() {
236                // If we are returning it as evicted it should be in the initial set.
237                assert_eq!(initial.check(pn), Ok(()), "{pn:?}");
238                // ... and unknown in the new set, since we've slid past it.
239                assert_eq!(self.check(pn), Err(SlidingWindowError::TooOld), "{pn:?}");
240            }
241        }
242
243        for pn in initial
244            .right_edge
245            .map_or(0, |e| e.as_u64())
246            .saturating_sub(WINDOW_WIDTH)
247            ..initial.right_edge.map_or(WINDOW_WIDTH, |e| e.as_u64())
248        {
249            let pn = PacketNumber::from_varint(VarInt::new(pn).unwrap(), packet_number.space());
250
251            match self.check(pn) {
252                // If we still have this, it must not be in evicted.
253                Ok(()) => assert!(evicted.clone().all(|e| e != pn)),
254                Err(SlidingWindowError::TooOld) => {
255                    // If it's too old after insert, but was previously OK *and in the set*,
256                    // then it must be in evicted.
257                    if initial.check(pn).is_ok()
258                        // An Empty set is fine, but isn't meaningful to track evictions for
259                        // (FIXME: Maybe we should evict some range of 129 PNs?)
260                        && initial.window_position(pn) != WindowPosition::Empty
261                    {
262                        assert!(
263                            evicted.clone().any(|e| e == pn),
264                            "{pn:?} expected in evicted after insert of {packet_number:?}"
265                        );
266                    }
267                }
268                Err(SlidingWindowError::Duplicate) => {
269                    // If a duplicate after, then it must not be in evicted.
270                    assert!(evicted.clone().all(|e| e != pn))
271                }
272            }
273        }
274    }
275
276    /// Determines if the given packet number has already been inserted or
277    /// is too old to determine if it has already been inserted.
278    pub fn check(&self, packet_number: PacketNumber) -> Result<(), SlidingWindowError> {
279        match self.window_position(packet_number) {
280            WindowPosition::Left => Err(SlidingWindowError::TooOld),
281            WindowPosition::RightEdge => Err(SlidingWindowError::Duplicate),
282            WindowPosition::Right(_) | WindowPosition::Empty => Ok(()),
283            WindowPosition::Within(delta) => {
284                let mask = 1 << (delta - 1); // Shift by the delta - 1 to account for the right edge
285                if self.window & mask != 0 {
286                    Err(SlidingWindowError::Duplicate)
287                } else {
288                    Ok(())
289                }
290            }
291        }
292    }
293
294    /// Gets the position of the `packet_number` relative to the window.
295    fn window_position(&self, packet_number: PacketNumber) -> WindowPosition {
296        if let Some(right_edge) = self.right_edge {
297            match right_edge.checked_distance(packet_number) {
298                Some(0) => WindowPosition::RightEdge,
299                Some(delta) if delta >= WINDOW_WIDTH => WindowPosition::Left,
300                Some(delta) => WindowPosition::Within(delta),
301                None => WindowPosition::Right(
302                    packet_number
303                        .checked_distance(right_edge)
304                        .expect("packet_number must be greater than right_edge"),
305                ),
306            }
307        } else {
308            WindowPosition::Empty
309        }
310    }
311}
312
313#[cfg(test)]
314mod test {
315    use super::*;
316    use crate::{packet::number::PacketNumberSpace, varint::VarInt};
317    use bolero::{check, generator::*};
318    use SlidingWindowError::*;
319
320    /// This macro asserts that the output of inserting the given packet number,
321    /// the window, and the right edge match the expected values.
322    macro_rules! assert_window {
323        (
324            $window:expr, $to_insert:expr, $duplicate:expr, $expected_window:expr, $right_edge:expr
325        ) => {{
326            assert_eq!($window.check($to_insert), $duplicate);
327            assert_eq!($window.insert($to_insert), $duplicate);
328            assert_eq!(
329                $window.window, $expected_window,
330                "Expected: {:b}, Actual: {:b}",
331                $expected_window, $window.window
332            );
333            assert_eq!($window.right_edge.unwrap(), $right_edge);
334        }};
335    }
336
337    #[test]
338    #[allow(clippy::cognitive_complexity)] // several operations are needed to get the desired state
339    fn insert() {
340        let space = PacketNumberSpace::ApplicationData;
341        let mut window = SlidingWindow::default();
342
343        let zero = space.new_packet_number(VarInt::from_u8(0));
344        let one = space.new_packet_number(VarInt::from_u8(1));
345        let two = space.new_packet_number(VarInt::from_u8(2));
346        let three = space.new_packet_number(VarInt::from_u8(3));
347        let four = space.new_packet_number(VarInt::from_u8(4));
348        let five = space.new_packet_number(VarInt::from_u8(5));
349        let six = space.new_packet_number(VarInt::from_u8(6));
350        let seven = space.new_packet_number(VarInt::from_u8(7));
351        let eight = space.new_packet_number(VarInt::from_u8(8));
352        let large = space.new_packet_number(VarInt::MAX);
353
354        assert_eq!(window.window, Window::default());
355        assert_eq!(window.right_edge, None);
356
357        assert_window!(window, zero, Ok(()), Window::default(), zero);
358        assert_window!(window, zero, Err(Duplicate), Window::default(), zero);
359        assert_window!(window, one, Ok(()), 0b1, one);
360        assert_window!(window, one, Err(Duplicate), 0b1, one);
361        assert_window!(window, two, Ok(()), 0b11, two);
362        assert_window!(window, five, Ok(()), 0b11100, five);
363        assert_window!(window, eight, Ok(()), 0b1110_0100, eight);
364        assert_window!(window, seven, Ok(()), 0b1110_0101, eight);
365        assert_window!(window, three, Ok(()), 0b1111_0101, eight);
366        assert_window!(window, six, Ok(()), 0b1111_0111, eight);
367        assert_window!(window, four, Ok(()), 0b1111_1111, eight);
368        assert_window!(window, seven, Err(Duplicate), 0b1111_1111, eight);
369        assert_window!(window, two, Err(Duplicate), 0b1111_1111, eight);
370        assert_window!(window, eight, Err(Duplicate), 0b1111_1111, eight);
371        assert_window!(window, large, Ok(()), Window::default(), large);
372        assert_window!(window, five, Err(TooOld), Window::default(), large);
373    }
374
375    #[test]
376    #[cfg_attr(miri, ignore)] // this test is too expensive for miri
377    fn incremental_insert() {
378        let mut window = SlidingWindow::default();
379        let space = PacketNumberSpace::ApplicationData;
380        for right_edge in 0..1000 {
381            let pn = space.new_packet_number(VarInt::from_u32(right_edge));
382            assert_eq!(window.check(pn), Ok(()));
383            assert_eq!(window.insert(pn), Ok(()));
384            assert_eq!(window.right_edge.unwrap(), pn);
385            for dup in 0..=right_edge {
386                let expected_error = if right_edge - dup < WINDOW_WIDTH as u32 {
387                    Err(Duplicate)
388                } else {
389                    Err(TooOld)
390                };
391                let dup_pn = space.new_packet_number(VarInt::from_u32(dup));
392                assert_eq!(window.check(dup_pn), expected_error);
393                assert_eq!(window.insert(dup_pn), expected_error);
394            }
395        }
396    }
397
398    #[test]
399    #[allow(clippy::cognitive_complexity)] // several comparisons are needed
400    fn insert_at_edge() {
401        let mut window = SlidingWindow::default();
402        let space = PacketNumberSpace::ApplicationData;
403        let zero = space.new_packet_number(VarInt::from_u8(0));
404        let window_width_minus_1 = space.new_packet_number(VarInt::new(WINDOW_WIDTH - 1).unwrap());
405        let window_width = window_width_minus_1.next().unwrap();
406
407        assert_window!(window, zero, Ok(()), Window::default(), zero);
408        assert_window!(
409            window,
410            window_width_minus_1,
411            Ok(()),
412            (1_u128) << 127,
413            window_width_minus_1
414        );
415        assert_window!(
416            window,
417            window_width_minus_1,
418            Err(Duplicate),
419            (1_u128) << 127,
420            window_width_minus_1
421        );
422        assert_window!(window, window_width, Ok(()), 0b1, window_width);
423
424        window = SlidingWindow::default();
425        assert_window!(window, zero, Ok(()), Window::default(), zero);
426        assert_window!(
427            window,
428            window_width,
429            Ok(()),
430            Window::default(),
431            window_width
432        );
433        assert_window!(
434            window,
435            window_width,
436            Err(Duplicate),
437            Window::default(),
438            window_width
439        );
440    }
441
442    #[test]
443    fn delta_larger_than_32_bits() {
444        let mut window = SlidingWindow::default();
445        let space = PacketNumberSpace::ApplicationData;
446        let zero = space.new_packet_number(VarInt::from_u8(0));
447        let large = space.new_packet_number(VarInt::new((1 << 32) + 1).unwrap());
448        assert_eq!(window.check(zero), Ok(()));
449        assert_eq!(window.insert(zero), Ok(()));
450        assert_eq!(window.check(large), Ok(()));
451        assert_eq!(window.insert(large), Ok(()));
452        assert_eq!(window.check(large), Err(Duplicate));
453        assert_eq!(window.insert(large), Err(Duplicate));
454        assert_eq!(window.window, 0b0);
455    }
456
457    // Inserting into an empty set shouldn't trigger eviction errors.
458    //
459    // Found via fuzzing, but extracting as a dedicated test case.
460    #[test]
461    fn insert_into_empty() {
462        let pn = VarInt::from_u32(256);
463        let mut window = SlidingWindow::default();
464        let space = PacketNumberSpace::ApplicationData;
465        let packet_number = space.new_packet_number(pn);
466        assert!(window.insert(packet_number).is_ok());
467    }
468
469    #[test]
470    #[cfg_attr(kani, kani::proof, kani::unwind(130), kani::solver(kissat))]
471    #[cfg_attr(miri, ignore)] // this test is too expensive for miri
472    fn insert_test() {
473        // Make sure the two packet numbers are not the same
474        let gen = produce::<(VarInt, VarInt)>().filter_gen(|(a, b)| a != b);
475
476        check!()
477            .with_generator(gen)
478            .cloned()
479            .for_each(|(pn, other_pn)| {
480                let mut window = SlidingWindow::default();
481                let space = PacketNumberSpace::ApplicationData;
482                let packet_number = space.new_packet_number(pn);
483                let other_packet_number = space.new_packet_number(other_pn);
484                assert!(window.insert(packet_number).is_ok());
485                assert_eq!(Err(Duplicate), window.check(packet_number));
486                assert_ne!(Err(Duplicate), window.check(other_packet_number));
487            });
488    }
489
490    // This is a basic test to make sure it mostly works.
491    //
492    // We also do fairly exhaustive checking as part of every insert that the evicted set we've
493    // returned matches our expectations.
494    #[test]
495    #[allow(clippy::cognitive_complexity)] // several operations are needed to get the desired state
496    fn insert_evicted() {
497        let space = PacketNumberSpace::ApplicationData;
498        let mut window = SlidingWindow::default();
499
500        let zero = space.new_packet_number(VarInt::from_u8(0));
501        let one = space.new_packet_number(VarInt::from_u8(1));
502        let two = space.new_packet_number(VarInt::from_u8(2));
503        let three = space.new_packet_number(VarInt::from_u8(3));
504        let four = space.new_packet_number(VarInt::from_u8(4));
505        let five = space.new_packet_number(VarInt::from_u8(5));
506        let six = space.new_packet_number(VarInt::from_u8(6));
507        let seven = space.new_packet_number(VarInt::from_u8(7));
508        let eight = space.new_packet_number(VarInt::from_u8(8));
509        let large = space.new_packet_number(VarInt::MAX);
510
511        assert!(window.insert(zero).is_ok());
512        assert!(window.insert(two).is_ok());
513        assert!(window.insert(four).is_ok());
514        assert!(window.insert(five).is_ok());
515        assert!(window.insert(seven).is_ok());
516        assert!(window.insert(eight).is_ok());
517
518        let mut evicted = window.insert_with_evicted(large).unwrap();
519        assert_eq!(evicted.next(), Some(one));
520        assert_eq!(evicted.next(), Some(three));
521        assert_eq!(evicted.next(), Some(six));
522        assert_eq!(evicted.next(), None);
523    }
524}
s2n_quic_core/packet/number/sliding_window.rs

s2n_quic_core/packet/number/
sliding_window.rs
