netstack3_base/tcp/
seqnum.rs

1// Copyright 2021 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//! TCP sequence numbers and operations on them.
6
7use core::convert::TryFrom as _;
8use core::num::TryFromIntError;
9use core::ops;
10
11use explicit::ResultExt as _;
12
13/// Sequence number of a transferred TCP segment.
14///
15/// Per https://tools.ietf.org/html/rfc793#section-3.3:
16///   This space ranges from 0 to 2**32 - 1. Since the space is finite, all
17///   arithmetic dealing with sequence numbers must be performed modulo 2**32.
18///   This unsigned arithmetic preserves the relationship of sequence numbers
19///   as they cycle from 2**32 - 1 to 0 again.  There are some subtleties to
20///   computer modulo arithmetic, so great care should be taken in programming
21///   the comparison of such values.
22///
23/// For any sequence number, there are 2**31 numbers after it and 2**31 - 1
24/// numbers before it.
25#[derive(Debug, PartialEq, Eq, Clone, Copy)]
26pub struct SeqNum(u32);
27
28impl ops::Add<i32> for SeqNum {
29    type Output = SeqNum;
30
31    fn add(self, rhs: i32) -> Self::Output {
32        let Self(lhs) = self;
33        Self(lhs.wrapping_add_signed(rhs))
34    }
35}
36
37impl ops::Sub<i32> for SeqNum {
38    type Output = SeqNum;
39
40    fn sub(self, rhs: i32) -> Self::Output {
41        let Self(lhs) = self;
42        Self(lhs.wrapping_add_signed(rhs.wrapping_neg()))
43    }
44}
45
46impl ops::Add<u32> for SeqNum {
47    type Output = SeqNum;
48
49    fn add(self, rhs: u32) -> Self::Output {
50        let Self(lhs) = self;
51        Self(lhs.wrapping_add(rhs))
52    }
53}
54
55impl ops::Sub<u32> for SeqNum {
56    type Output = SeqNum;
57
58    fn sub(self, rhs: u32) -> Self::Output {
59        let Self(lhs) = self;
60        Self(lhs.wrapping_sub(rhs))
61    }
62}
63
64impl ops::Sub<WindowSize> for SeqNum {
65    type Output = SeqNum;
66
67    fn sub(self, WindowSize(wnd): WindowSize) -> Self::Output {
68        // The conversion from u32 to i32 will never truncate because the
69        // maximum window size is less than 2^30, which will comfortably fit
70        // into an i32.
71        self - i32::try_from(wnd).unwrap()
72    }
73}
74
75impl ops::Add<usize> for SeqNum {
76    type Output = SeqNum;
77
78    fn add(self, rhs: usize) -> Self::Output {
79        // The following `as` coercion is sound because:
80        // 1. if `u32` is wider than `usize`, the unsigned extension will
81        //    result in the same number.
82        // 2. if `usize` is wider than `u32`, then `rhs` can be written as
83        //    `A * 2 ^ 32 + B`. Because of the wrapping nature of sequnce
84        //    numbers, the effect of adding `rhs` is the same as adding `B`
85        //    which is the number after the truncation, i.e., `rhs as u32`.
86        self + (rhs as u32)
87    }
88}
89
90impl ops::Sub for SeqNum {
91    // `i32` is more intuitive than `u32`, since subtraction may yield negative
92    // values.
93    type Output = i32;
94
95    fn sub(self, rhs: Self) -> Self::Output {
96        let Self(lhs) = self;
97        let Self(rhs) = rhs;
98        // The following `as` coercion is sound because:
99        // Rust uses 2's complement for signed integers [1], meaning when cast
100        // to an `i32, an `u32` >= 1<<32 becomes negative and an `u32` < 1<<32
101        // becomes positive. `wrapping_sub` ensures that if `rhs` is a `SeqNum`
102        // after `lhs`, the result will wrap into the `u32` space > 1<<32.
103        // Recall that `SeqNums` are only valid for a `WindowSize` < 1<<31; this
104        // prevents the difference of `wrapping_sub` from being so large that it
105        // wraps into the `u32` space < 1<<32.
106        // [1]: https://doc.rust-lang.org/reference/types/numeric.html
107        lhs.wrapping_sub(rhs) as i32
108    }
109}
110
111impl From<u32> for SeqNum {
112    fn from(x: u32) -> Self {
113        Self::new(x)
114    }
115}
116
117impl From<SeqNum> for u32 {
118    fn from(x: SeqNum) -> Self {
119        let SeqNum(x) = x;
120        x
121    }
122}
123
124impl SeqNum {
125    /// Creates a new sequence number.
126    pub const fn new(x: u32) -> Self {
127        Self(x)
128    }
129}
130
131impl SeqNum {
132    /// A predicate for whether a sequence number is before the other.
133    ///
134    /// Please refer to [`SeqNum`] for the defined order.
135    pub fn before(self, other: SeqNum) -> bool {
136        self - other < 0
137    }
138
139    /// A predicate for whether a sequence number is equal to or before the
140    /// other.
141    ///
142    /// Please refer to [`SeqNum`] for the defined order.
143    pub fn before_or_eq(self, other: SeqNum) -> bool {
144        self - other <= 0
145    }
146
147    /// A predicate for whether a sequence number is after the other.
148    ///
149    /// Please refer to [`SeqNum`] for the defined order.
150    pub fn after(self, other: SeqNum) -> bool {
151        self - other > 0
152    }
153
154    /// A predicate for whether a sequence number is equal to or after the
155    /// other.
156    ///
157    /// Please refer to [`SeqNum`] for the defined order.
158    pub fn after_or_eq(self, other: SeqNum) -> bool {
159        self - other >= 0
160    }
161
162    /// Returns the earliest sequence number between `self` and `other`.
163    ///
164    /// This is equivalent to [`Ord::min`], but keeps within the temporal
165    /// instead of numeric semantics.
166    pub fn earliest(self, other: SeqNum) -> SeqNum {
167        if self.before(other) { self } else { other }
168    }
169
170    /// Returns the latest sequence number between `self` and `other`.
171    ///
172    /// This is equivalent to [`Ord::max`], but keeps within the temporal
173    /// instead of numeric semantics.
174    pub fn latest(self, other: SeqNum) -> SeqNum {
175        if self.after(other) { self } else { other }
176    }
177}
178
179/// A witness type for TCP window size.
180///
181/// Per [RFC 7323 Section 2.3]:
182/// > ..., the above constraints imply that two times the maximum window size
183/// > must be less than 2^31, or
184/// >                    max window < 2^30
185///
186/// [RFC 7323 Section 2.3]: https://tools.ietf.org/html/rfc7323#section-2.3
187#[derive(Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
188pub struct WindowSize(u32);
189
190impl WindowSize {
191    /// The largest possible window size.
192    pub const MAX: WindowSize = WindowSize((1 << 30) - 1);
193    /// The smallest possible window size.
194    pub const ZERO: WindowSize = WindowSize(0);
195    /// A window size of 1, the smallest nonzero window size.
196    pub const ONE: WindowSize = WindowSize(1);
197
198    /// The Netstack3 default window size.
199    // TODO(https://github.com/rust-lang/rust/issues/67441): put this constant
200    // in the state module once `Option::unwrap` is stable.
201    pub const DEFAULT: WindowSize = WindowSize(65535);
202
203    /// Create a new `WindowSize` from the provided `u32`.
204    ///
205    /// If the provided window size is out of range, then `None` is returned.
206    pub const fn from_u32(wnd: u32) -> Option<Self> {
207        let WindowSize(max) = Self::MAX;
208        if wnd > max { None } else { Some(Self(wnd)) }
209    }
210
211    /// Add a `u32` to this WindowSize, saturating at [`WindowSize::MAX`].
212    pub fn saturating_add(self, rhs: u32) -> Self {
213        Self::from_u32(u32::from(self).saturating_add(rhs)).unwrap_or(Self::MAX)
214    }
215
216    /// Create a new [`WindowSize`], returning `None` if the argument is out of range.
217    pub fn new(wnd: usize) -> Option<Self> {
218        u32::try_from(wnd).ok_checked::<TryFromIntError>().and_then(WindowSize::from_u32)
219    }
220
221    /// Subtract `diff` from `self`, returning `None` if the result would be negative.
222    pub fn checked_sub(self, diff: usize) -> Option<Self> {
223        // The call to Self::new will never return None.
224        //
225        // If diff is larger than self, the checked_sub will return None. Otherwise the result must
226        // be less than Self::MAX, since the value of self before subtraction must be less than or
227        // equal to Self::MAX.
228        usize::from(self).checked_sub(diff).and_then(Self::new)
229    }
230
231    /// Subtract `diff` from `self` returning [`WindowSize::ZERO`] if the result
232    /// would be negative.
233    pub fn saturating_sub(self, diff: usize) -> Self {
234        self.checked_sub(diff).unwrap_or(WindowSize::ZERO)
235    }
236
237    /// The window scale that needs to be advertised during the handshake.
238    pub fn scale(self) -> WindowScale {
239        let WindowSize(size) = self;
240        let effective_bits = u8::try_from(32 - u32::leading_zeros(size)).unwrap();
241        let scale = WindowScale(effective_bits.saturating_sub(16));
242        scale
243    }
244
245    /// Returns this `WindowSize` with a halved value
246    pub fn halved(self) -> WindowSize {
247        let WindowSize(size) = self;
248        WindowSize(size >> 1)
249    }
250}
251
252impl ops::Add<WindowSize> for SeqNum {
253    type Output = SeqNum;
254
255    fn add(self, WindowSize(wnd): WindowSize) -> Self::Output {
256        self + wnd
257    }
258}
259
260impl From<WindowSize> for u32 {
261    fn from(WindowSize(wnd): WindowSize) -> Self {
262        wnd
263    }
264}
265
266#[cfg(any(target_pointer_width = "32", target_pointer_width = "64"))]
267impl From<WindowSize> for usize {
268    fn from(WindowSize(wnd): WindowSize) -> Self {
269        wnd as usize
270    }
271}
272
273#[derive(Debug, PartialEq, Eq, Clone, Copy, Default)]
274/// This type is a witness for a valid window scale exponent value.
275///
276/// Per RFC 7323 Section 2.2, the restriction is as follows:
277///   The maximum scale exponent is limited to 14 for a maximum permissible
278///   receive window size of 1 GiB (2^(14+16)).
279pub struct WindowScale(u8);
280
281impl WindowScale {
282    /// The largest possible [`WindowScale`].
283    pub const MAX: WindowScale = WindowScale(14);
284    /// The smallest possible [`WindowScale`].
285    pub const ZERO: WindowScale = WindowScale(0);
286
287    /// Creates a new `WindowScale`.
288    ///
289    /// Returns `None` if the input exceeds the maximum possible value.
290    pub fn new(ws: u8) -> Option<Self> {
291        (ws <= Self::MAX.get()).then_some(WindowScale(ws))
292    }
293
294    /// Returns the inner value.
295    pub fn get(&self) -> u8 {
296        let Self(ws) = self;
297        *ws
298    }
299}
300
301#[derive(Debug, PartialEq, Eq, Clone, Copy)]
302/// Window size that is used in the window field of a TCP segment.
303///
304/// For connections with window scaling enabled, the receiver has to scale this
305/// value back to get the real window size advertised by the peer.
306pub struct UnscaledWindowSize(u16);
307
308impl ops::Shl<WindowScale> for UnscaledWindowSize {
309    type Output = WindowSize;
310
311    fn shl(self, WindowScale(scale): WindowScale) -> Self::Output {
312        let UnscaledWindowSize(size) = self;
313        // `scale` is guaranteed to be <= 14, so the result must fit in a u32.
314        WindowSize::from_u32(u32::from(size) << scale).unwrap()
315    }
316}
317
318impl ops::Shr<WindowScale> for WindowSize {
319    type Output = UnscaledWindowSize;
320
321    fn shr(self, WindowScale(scale): WindowScale) -> Self::Output {
322        let WindowSize(size) = self;
323        UnscaledWindowSize(u16::try_from(size >> scale).unwrap_or(u16::MAX))
324    }
325}
326
327impl From<u16> for UnscaledWindowSize {
328    fn from(value: u16) -> Self {
329        Self(value)
330    }
331}
332
333impl From<UnscaledWindowSize> for u16 {
334    fn from(UnscaledWindowSize(value): UnscaledWindowSize) -> Self {
335        value
336    }
337}
338
339#[cfg(feature = "testutils")]
340mod testutils {
341    use super::*;
342
343    impl UnscaledWindowSize {
344        /// Create a new UnscaledWindowSize.
345        ///
346        /// Panics if `size` is not in range.
347        pub fn from_usize(size: usize) -> Self {
348            UnscaledWindowSize::from(u16::try_from(size).unwrap())
349        }
350
351        /// Create a new UnscaledWindowSize.
352        ///
353        /// Panics if `size` is not in range.
354        pub fn from_u32(size: u32) -> Self {
355            UnscaledWindowSize::from(u16::try_from(size).unwrap())
356        }
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    use alloc::format;
363
364    use proptest::arbitrary::any;
365    use proptest::strategy::{Just, Strategy};
366    use proptest::test_runner::Config;
367    use proptest::{prop_assert, prop_assert_eq, proptest};
368    use proptest_support::failed_seeds_no_std;
369    use test_case::test_case;
370
371    use super::super::segment::MAX_PAYLOAD_AND_CONTROL_LEN;
372    use super::*;
373
374    fn arb_seqnum() -> impl Strategy<Value = SeqNum> {
375        any::<u32>().prop_map(SeqNum::from)
376    }
377
378    // Generates a triple (a, b, c) s.t. a < b < a + 2^30 && b < c < a + 2^30.
379    // This triple is used to verify that transitivity holds.
380    fn arb_seqnum_trans_tripple() -> impl Strategy<Value = (SeqNum, SeqNum, SeqNum)> {
381        arb_seqnum().prop_flat_map(|a| {
382            (1..=MAX_PAYLOAD_AND_CONTROL_LEN).prop_flat_map(move |diff_a_b| {
383                let b = a + diff_a_b;
384                (1..=MAX_PAYLOAD_AND_CONTROL_LEN - diff_a_b).prop_flat_map(move |diff_b_c| {
385                    let c = b + diff_b_c;
386                    (Just(a), Just(b), Just(c))
387                })
388            })
389        })
390    }
391
392    #[test_case(WindowSize::new(1).unwrap() => (UnscaledWindowSize::from(1), WindowScale::default()))]
393    #[test_case(WindowSize::new(65535).unwrap() => (UnscaledWindowSize::from(65535), WindowScale::default()))]
394    #[test_case(WindowSize::new(65536).unwrap() => (UnscaledWindowSize::from(32768), WindowScale::new(1).unwrap()))]
395    #[test_case(WindowSize::new(65537).unwrap() => (UnscaledWindowSize::from(32768), WindowScale::new(1).unwrap()))]
396    fn window_scale(size: WindowSize) -> (UnscaledWindowSize, WindowScale) {
397        let scale = size.scale();
398        (size >> scale, scale)
399    }
400
401    proptest! {
402        #![proptest_config(Config {
403            // Add all failed seeds here.
404            failure_persistence: failed_seeds_no_std!(),
405            ..Config::default()
406        })]
407
408        #[test]
409        fn seqnum_ord_is_reflexive(a in arb_seqnum()) {
410            prop_assert_eq!(a, a)
411        }
412
413        #[test]
414        fn seqnum_ord_is_total(a in arb_seqnum(), b in arb_seqnum()) {
415            if a == b {
416                prop_assert!(!a.before(b) && !b.before(a))
417            } else {
418                prop_assert!(a.before(b) ^ b.before(a))
419            }
420        }
421
422        #[test]
423        fn seqnum_ord_is_transitive((a, b, c) in arb_seqnum_trans_tripple()) {
424            prop_assert!(a.before(b) && b.before(c) && a.before(c));
425        }
426
427        #[test]
428        fn seqnum_add_positive_greater(a in arb_seqnum(), b in 1..=i32::MAX) {
429            prop_assert!(a.before(a + b))
430        }
431
432        #[test]
433        fn seqnum_add_negative_smaller(a in arb_seqnum(), b in i32::MIN..=-1) {
434            prop_assert!(a.after(a + b))
435        }
436
437        #[test]
438        fn seqnum_sub_positive_smaller(a in arb_seqnum(), b in 1..=i32::MAX) {
439            prop_assert!(a.after(a - b))
440        }
441
442        #[test]
443        fn seqnum_sub_negative_greater(a in arb_seqnum(), b in i32::MIN..=-1) {
444            prop_assert!(a.before(a - b))
445        }
446
447        #[test]
448        fn seqnum_zero_identity(a in arb_seqnum()) {
449            prop_assert_eq!(a, a + 0)
450        }
451
452        #[test]
453        fn seqnum_before_after_inverse(a in arb_seqnum(), b in arb_seqnum()) {
454            prop_assert_eq!(a.after(b), b.before(a))
455        }
456
457        #[test]
458        fn seqnum_wraps_around_at_max_length(a in arb_seqnum()) {
459            prop_assert!(a.before(a + MAX_PAYLOAD_AND_CONTROL_LEN));
460            prop_assert!(a.after(a + MAX_PAYLOAD_AND_CONTROL_LEN + 1));
461        }
462
463        #[test]
464        fn window_size_less_than_or_eq_to_max(wnd in 0..=WindowSize::MAX.0) {
465            prop_assert_eq!(WindowSize::from_u32(wnd), Some(WindowSize(wnd)));
466        }
467
468        #[test]
469        fn window_size_greater_than_max(wnd in WindowSize::MAX.0+1..=u32::MAX) {
470            prop_assert_eq!(WindowSize::from_u32(wnd), None);
471        }
472    }
473
474    /// Verify that the maximum value for [`WindowSize`] corresponds to
475    /// appropriate values for [`UnscaledWindowSize`] and [`WindowScale`].
476    #[test]
477    fn max_window_size() {
478        // Verify that constructing a `WindowSize` from it's maximum
479        // constituents is valid.
480        let window_size = UnscaledWindowSize(u16::MAX) << WindowScale::MAX;
481        assert!(window_size <= WindowSize::MAX, "actual={window_size:?}");
482
483        // Verify that deconstructing a maximum `WindowSize` into it's
484        // constituents is valid.
485        assert_eq!(WindowSize::MAX.scale(), WindowScale::MAX);
486    }
487}
netstack3_base/tcp/seqnum.rs

netstack3_base/tcp/
seqnum.rs
