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

netstack3_base/tcp/
seqnum.rs
