veridian_kernel/net/
tcp_sack.rs

1//! TCP Selective Acknowledgment (SACK) implementation
2//!
3//! Implements RFC 2018 TCP SACK option parsing, scoreboard tracking,
4//! and selective retransmission hole detection. Enables efficient
5//! recovery from multiple segment losses without retransmitting
6//! already-received data.
7
8#![allow(dead_code)]
9
10#[cfg(feature = "alloc")]
11use alloc::vec::Vec;
12
13// ============================================================================
14// Sequence Number Arithmetic (wrapping-safe)
15// ============================================================================
16
17/// Compare sequence numbers using signed 32-bit difference.
18/// Returns true if `a` is strictly less than `b` in sequence space.
19#[inline]
20pub fn seq_lt(a: u32, b: u32) -> bool {
21    (a.wrapping_sub(b) as i32) < 0
22}
23
24/// Returns true if `a <= b` in sequence space.
25#[inline]
26pub fn seq_le(a: u32, b: u32) -> bool {
27    (a.wrapping_sub(b) as i32) <= 0
28}
29
30/// Returns true if `a > b` in sequence space.
31#[inline]
32pub fn seq_gt(a: u32, b: u32) -> bool {
33    (a.wrapping_sub(b) as i32) > 0
34}
35
36/// Returns true if `a >= b` in sequence space.
37#[inline]
38pub fn seq_ge(a: u32, b: u32) -> bool {
39    (a.wrapping_sub(b) as i32) >= 0
40}
41
42// ============================================================================
43// SACK Option Constants
44// ============================================================================
45
46/// TCP option kind for SACK-Permitted (sent in SYN/SYN-ACK)
47pub const TCP_OPT_SACK_PERMITTED: u8 = 4;
48
49/// TCP option length for SACK-Permitted
50pub const TCP_OPT_SACK_PERMITTED_LEN: u8 = 2;
51
52/// TCP option kind for SACK blocks
53pub const TCP_OPT_SACK: u8 = 5;
54
55/// Maximum number of SACK blocks in a single TCP option (limited by option
56/// space)
57pub const MAX_SACK_BLOCKS: usize = 4;
58
59/// Size of a single SACK block (left_edge + right_edge = 4 + 4 bytes)
60const SACK_BLOCK_SIZE: usize = 8;
61
62/// TCP option End of Option List
63const TCP_OPT_EOL: u8 = 0;
64
65/// TCP option No-Operation (padding)
66const TCP_OPT_NOP: u8 = 1;
67
68// ============================================================================
69// SACK Block
70// ============================================================================
71
72/// A single SACK block representing a contiguous range of received bytes.
73///
74/// `left_edge` is the first sequence number in the block (inclusive).
75/// `right_edge` is one past the last sequence number (exclusive).
76#[derive(Debug, Clone, Copy, PartialEq, Eq)]
77pub struct SackBlock {
78    pub left_edge: u32,
79    pub right_edge: u32,
80}
81
82impl SackBlock {
83    /// Create a new SACK block.
84    pub const fn new(left_edge: u32, right_edge: u32) -> Self {
85        Self {
86            left_edge,
87            right_edge,
88        }
89    }
90
91    /// Returns true if this block contains the given sequence number.
92    pub fn contains(&self, seq: u32) -> bool {
93        seq_ge(seq, self.left_edge) && seq_lt(seq, self.right_edge)
94    }
95
96    /// Returns the length of this block in sequence space.
97    pub fn len(&self) -> u32 {
98        self.right_edge.wrapping_sub(self.left_edge)
99    }
100
101    /// Returns true if the block is empty (zero length).
102    pub fn is_empty(&self) -> bool {
103        self.left_edge == self.right_edge
104    }
105
106    /// Returns true if this block overlaps or is adjacent to `other`.
107    pub fn overlaps_or_adjacent(&self, other: &SackBlock) -> bool {
108        // Two blocks [a, b) and [c, d) overlap or are adjacent if
109        // a <= d AND c <= b (in sequence space).
110        seq_le(self.left_edge, other.right_edge) && seq_le(other.left_edge, self.right_edge)
111    }
112
113    /// Merge another block into this one (union of ranges).
114    /// Only valid if the blocks overlap or are adjacent.
115    pub fn merge(&mut self, other: &SackBlock) {
116        if seq_lt(other.left_edge, self.left_edge) {
117            self.left_edge = other.left_edge;
118        }
119        if seq_gt(other.right_edge, self.right_edge) {
120            self.right_edge = other.right_edge;
121        }
122    }
123}
124
125// ============================================================================
126// SACK Option Parsing and Serialization
127// ============================================================================
128
129/// Parse SACK blocks from TCP options bytes.
130///
131/// Scans the options field for kind=5 (SACK) and extracts up to 4 blocks.
132/// Returns an empty Vec if no SACK option is found.
133#[cfg(feature = "alloc")]
134pub fn parse_sack_blocks(options: &[u8]) -> Vec<SackBlock> {
135    let mut blocks = Vec::new();
136    let mut i = 0;
137
138    while i < options.len() {
139        match options[i] {
140            TCP_OPT_EOL => break,
141            TCP_OPT_NOP => {
142                i += 1;
143            }
144            TCP_OPT_SACK => {
145                // Kind = 5, next byte is length
146                if i + 1 >= options.len() {
147                    break;
148                }
149                let opt_len = options[i + 1] as usize;
150                if opt_len < 2 || i + opt_len > options.len() {
151                    break;
152                }
153                // Number of blocks = (length - 2) / 8
154                let num_blocks = (opt_len - 2) / SACK_BLOCK_SIZE;
155                let mut offset = i + 2;
156                for _ in 0..num_blocks.min(MAX_SACK_BLOCKS) {
157                    if offset + SACK_BLOCK_SIZE > i + opt_len {
158                        break;
159                    }
160                    let left = u32::from_be_bytes([
161                        options[offset],
162                        options[offset + 1],
163                        options[offset + 2],
164                        options[offset + 3],
165                    ]);
166                    let right = u32::from_be_bytes([
167                        options[offset + 4],
168                        options[offset + 5],
169                        options[offset + 6],
170                        options[offset + 7],
171                    ]);
172                    blocks.push(SackBlock::new(left, right));
173                    offset += SACK_BLOCK_SIZE;
174                }
175                i += opt_len;
176            }
177            _ => {
178                // Variable-length option: kind + length + data
179                if i + 1 >= options.len() {
180                    break;
181                }
182                let opt_len = options[i + 1] as usize;
183                if opt_len < 2 {
184                    break;
185                }
186                i += opt_len;
187            }
188        }
189    }
190
191    blocks
192}
193
194/// Check if SACK-Permitted option is present in TCP options.
195pub fn has_sack_permitted(options: &[u8]) -> bool {
196    let mut i = 0;
197
198    while i < options.len() {
199        match options[i] {
200            TCP_OPT_EOL => break,
201            TCP_OPT_NOP => {
202                i += 1;
203            }
204            TCP_OPT_SACK_PERMITTED => {
205                if i + 1 < options.len() && options[i + 1] == TCP_OPT_SACK_PERMITTED_LEN {
206                    return true;
207                }
208                // Malformed, skip
209                if i + 1 < options.len() {
210                    let opt_len = options[i + 1] as usize;
211                    i += if opt_len >= 2 { opt_len } else { 2 };
212                } else {
213                    break;
214                }
215            }
216            _ => {
217                if i + 1 >= options.len() {
218                    break;
219                }
220                let opt_len = options[i + 1] as usize;
221                if opt_len < 2 {
222                    break;
223                }
224                i += opt_len;
225            }
226        }
227    }
228
229    false
230}
231
232/// Serialize SACK-Permitted option (2 bytes, for SYN/SYN-ACK).
233#[cfg(feature = "alloc")]
234pub fn serialize_sack_permitted() -> Vec<u8> {
235    alloc::vec![TCP_OPT_SACK_PERMITTED, TCP_OPT_SACK_PERMITTED_LEN]
236}
237
238/// Serialize SACK blocks into TCP option bytes.
239///
240/// Produces kind(1) + length(1) + N * 8 bytes of block data.
241/// At most `MAX_SACK_BLOCKS` (4) blocks are serialized.
242#[cfg(feature = "alloc")]
243pub fn serialize_sack_blocks(blocks: &[SackBlock]) -> Vec<u8> {
244    if blocks.is_empty() {
245        return Vec::new();
246    }
247
248    let count = blocks.len().min(MAX_SACK_BLOCKS);
249    let opt_len = 2 + count * SACK_BLOCK_SIZE;
250    let mut out = Vec::with_capacity(opt_len);
251
252    out.push(TCP_OPT_SACK);
253    out.push(opt_len as u8);
254
255    for block in blocks.iter().take(count) {
256        out.extend_from_slice(&block.left_edge.to_be_bytes());
257        out.extend_from_slice(&block.right_edge.to_be_bytes());
258    }
259
260    out
261}
262
263// ============================================================================
264// SACK Scoreboard
265// ============================================================================
266
267/// Tracks selectively acknowledged ranges for a TCP connection.
268///
269/// Maintains a sorted, non-overlapping list of SACK blocks representing
270/// data the remote receiver has confirmed receiving out of order.
271#[cfg(feature = "alloc")]
272pub struct SackScoreboard {
273    /// Sorted list of non-overlapping SACK blocks (by left_edge in sequence
274    /// space).
275    blocks: Vec<SackBlock>,
276}
277
278#[cfg(feature = "alloc")]
279impl Default for SackScoreboard {
280    fn default() -> Self {
281        Self::new()
282    }
283}
284
285#[cfg(feature = "alloc")]
286impl SackScoreboard {
287    /// Create an empty scoreboard.
288    pub fn new() -> Self {
289        Self { blocks: Vec::new() }
290    }
291
292    /// Returns the number of tracked SACK blocks.
293    pub fn block_count(&self) -> usize {
294        self.blocks.len()
295    }
296
297    /// Returns a slice of all current SACK blocks.
298    pub fn blocks(&self) -> &[SackBlock] {
299        &self.blocks
300    }
301
302    /// Returns true if the given sequence number falls within a SACKed range.
303    pub fn is_sacked(&self, seq: u32) -> bool {
304        self.blocks.iter().any(|b| b.contains(seq))
305    }
306
307    /// Mark a range [left, right) as selectively acknowledged.
308    ///
309    /// Merges with any overlapping or adjacent existing blocks to maintain
310    /// the invariant that blocks are sorted and non-overlapping.
311    pub fn mark_sacked(&mut self, left: u32, right: u32) {
312        if seq_ge(left, right) {
313            return; // Empty or invalid range
314        }
315
316        let mut new_block = SackBlock::new(left, right);
317
318        // Collect indices of blocks that overlap or are adjacent
319        let mut merge_indices = Vec::new();
320        for (i, block) in self.blocks.iter().enumerate() {
321            if new_block.overlaps_or_adjacent(block) {
322                merge_indices.push(i);
323            }
324        }
325
326        // Merge all overlapping blocks into new_block
327        for &i in merge_indices.iter() {
328            new_block.merge(&self.blocks[i]);
329        }
330
331        // Remove merged blocks in reverse order to preserve indices
332        for &i in merge_indices.iter().rev() {
333            self.blocks.remove(i);
334        }
335
336        // Insert new_block in sorted order (by left_edge in sequence space)
337        let insert_pos = self
338            .blocks
339            .iter()
340            .position(|b| seq_gt(b.left_edge, new_block.left_edge))
341            .unwrap_or(self.blocks.len());
342
343        self.blocks.insert(insert_pos, new_block);
344    }
345
346    /// Remove all blocks (or portions) below the cumulative ACK.
347    ///
348    /// Data below `ack` has been cumulatively acknowledged, so SACK
349    /// blocks covering that range are no longer needed.
350    pub fn clear_below(&mut self, ack: u32) {
351        self.blocks.retain_mut(|block| {
352            if seq_le(block.right_edge, ack) {
353                // Entire block is below ack -- remove it
354                false
355            } else if seq_lt(block.left_edge, ack) {
356                // Partial overlap -- trim the left side
357                block.left_edge = ack;
358                true
359            } else {
360                true
361            }
362        });
363    }
364
365    /// Returns the highest SACKed sequence number, or None if empty.
366    pub fn highest_sacked(&self) -> Option<u32> {
367        self.blocks.last().map(|b| b.right_edge)
368    }
369
370    /// Returns the next hole (gap) that needs retransmission.
371    ///
372    /// Starting from `snd_una` (send unacknowledged), finds the first
373    /// gap between SACK blocks. Returns `(start_seq, length)` of the hole.
374    pub fn next_retransmit(&self, snd_una: u32) -> Option<(u32, u32)> {
375        if self.blocks.is_empty() {
376            return None;
377        }
378
379        // Check for hole between snd_una and first SACK block
380        let first = &self.blocks[0];
381        if seq_lt(snd_una, first.left_edge) {
382            let hole_len = first.left_edge.wrapping_sub(snd_una);
383            return Some((snd_una, hole_len));
384        }
385
386        // Check for holes between consecutive SACK blocks
387        for window in self.blocks.windows(2) {
388            let gap_start = window[0].right_edge;
389            let gap_end = window[1].left_edge;
390            if seq_lt(gap_start, gap_end) {
391                let hole_len = gap_end.wrapping_sub(gap_start);
392                return Some((gap_start, hole_len));
393            }
394        }
395
396        None
397    }
398
399    /// Returns all holes (gaps) between `snd_una` and the highest SACKed byte.
400    ///
401    /// Each hole is represented as `(start_seq, length)`.
402    pub fn holes(&self, snd_una: u32) -> Vec<(u32, u32)> {
403        let mut result = Vec::new();
404
405        if self.blocks.is_empty() {
406            return result;
407        }
408
409        // Hole before first block
410        let first = &self.blocks[0];
411        if seq_lt(snd_una, first.left_edge) {
412            let hole_len = first.left_edge.wrapping_sub(snd_una);
413            result.push((snd_una, hole_len));
414        }
415
416        // Holes between consecutive blocks
417        for window in self.blocks.windows(2) {
418            let gap_start = window[0].right_edge;
419            let gap_end = window[1].left_edge;
420            if seq_lt(gap_start, gap_end) {
421                let hole_len = gap_end.wrapping_sub(gap_start);
422                result.push((gap_start, hole_len));
423            }
424        }
425
426        result
427    }
428}
429
430// ============================================================================
431// Tests
432// ============================================================================
433
434#[cfg(test)]
435mod tests {
436    #[allow(unused_imports)]
437    use alloc::vec;
438
439    use super::*;
440
441    // -- Sequence number arithmetic --
442
443    #[test]
444    fn test_seq_lt_normal() {
445        assert!(seq_lt(100, 200));
446        assert!(!seq_lt(200, 100));
447        assert!(!seq_lt(100, 100));
448    }
449
450    #[test]
451    fn test_seq_lt_wrapping() {
452        // Near the wraparound point
453        let a = u32::MAX - 10;
454        let b = 10u32; // b is "after" a in sequence space
455        assert!(seq_lt(a, b));
456        assert!(!seq_lt(b, a));
457    }
458
459    #[test]
460    fn test_seq_le_ge() {
461        assert!(seq_le(100, 100));
462        assert!(seq_le(100, 200));
463        assert!(seq_ge(200, 100));
464        assert!(seq_ge(100, 100));
465        assert!(!seq_ge(100, 200));
466    }
467
468    #[test]
469    fn test_seq_gt_wrapping() {
470        let a = 5u32;
471        let b = u32::MAX - 5;
472        assert!(seq_gt(a, b)); // a is "after" b across the wrap
473    }
474
475    // -- SACK block --
476
477    #[test]
478    fn test_sack_block_contains() {
479        let block = SackBlock::new(1000, 2000);
480        assert!(block.contains(1000));
481        assert!(block.contains(1500));
482        assert!(block.contains(1999));
483        assert!(!block.contains(2000));
484        assert!(!block.contains(999));
485    }
486
487    #[test]
488    fn test_sack_block_len() {
489        let block = SackBlock::new(1000, 2000);
490        assert_eq!(block.len(), 1000);
491
492        let empty = SackBlock::new(500, 500);
493        assert!(empty.is_empty());
494    }
495
496    #[test]
497    fn test_sack_block_overlap_and_merge() {
498        let mut a = SackBlock::new(100, 200);
499        let b = SackBlock::new(150, 300);
500        assert!(a.overlaps_or_adjacent(&b));
501        a.merge(&b);
502        assert_eq!(a.left_edge, 100);
503        assert_eq!(a.right_edge, 300);
504    }
505
506    // -- Option parsing --
507
508    #[test]
509    fn test_parse_sack_blocks() {
510        // Build a SACK option with 2 blocks: [1000, 2000) and [3000, 4000)
511        let mut opts = vec![TCP_OPT_SACK, 18]; // kind=5, length=2+8*2=18
512        opts.extend_from_slice(&1000u32.to_be_bytes());
513        opts.extend_from_slice(&2000u32.to_be_bytes());
514        opts.extend_from_slice(&3000u32.to_be_bytes());
515        opts.extend_from_slice(&4000u32.to_be_bytes());
516
517        let blocks = parse_sack_blocks(&opts);
518        assert_eq!(blocks.len(), 2);
519        assert_eq!(blocks[0], SackBlock::new(1000, 2000));
520        assert_eq!(blocks[1], SackBlock::new(3000, 4000));
521    }
522
523    #[test]
524    fn test_has_sack_permitted() {
525        let opts = vec![
526            TCP_OPT_NOP,
527            TCP_OPT_SACK_PERMITTED,
528            TCP_OPT_SACK_PERMITTED_LEN,
529        ];
530        assert!(has_sack_permitted(&opts));
531
532        let no_sack = vec![TCP_OPT_NOP, TCP_OPT_EOL];
533        assert!(!has_sack_permitted(&no_sack));
534    }
535
536    #[test]
537    fn test_serialize_sack_blocks() {
538        let blocks = vec![SackBlock::new(1000, 2000), SackBlock::new(3000, 4000)];
539        let serialized = serialize_sack_blocks(&blocks);
540        assert_eq!(serialized[0], TCP_OPT_SACK);
541        assert_eq!(serialized[1], 18); // 2 + 2*8
542        let parsed = parse_sack_blocks(&serialized);
543        assert_eq!(parsed, blocks);
544    }
545
546    #[test]
547    fn test_serialize_sack_permitted() {
548        let opt = serialize_sack_permitted();
549        assert_eq!(opt.len(), 2);
550        assert!(has_sack_permitted(&opt));
551    }
552
553    // -- Scoreboard --
554
555    #[test]
556    fn test_scoreboard_mark_and_query() {
557        let mut sb = SackScoreboard::new();
558        sb.mark_sacked(1000, 2000);
559        sb.mark_sacked(3000, 4000);
560
561        assert!(sb.is_sacked(1500));
562        assert!(sb.is_sacked(3500));
563        assert!(!sb.is_sacked(2500));
564        assert_eq!(sb.block_count(), 2);
565    }
566
567    #[test]
568    fn test_scoreboard_merge_overlapping() {
569        let mut sb = SackScoreboard::new();
570        sb.mark_sacked(1000, 2000);
571        sb.mark_sacked(1500, 3000);
572
573        assert_eq!(sb.block_count(), 1);
574        assert_eq!(sb.blocks()[0], SackBlock::new(1000, 3000));
575    }
576
577    #[test]
578    fn test_scoreboard_merge_adjacent() {
579        let mut sb = SackScoreboard::new();
580        sb.mark_sacked(1000, 2000);
581        sb.mark_sacked(2000, 3000);
582
583        assert_eq!(sb.block_count(), 1);
584        assert_eq!(sb.blocks()[0], SackBlock::new(1000, 3000));
585    }
586
587    #[test]
588    fn test_scoreboard_merge_multiple() {
589        let mut sb = SackScoreboard::new();
590        sb.mark_sacked(1000, 2000);
591        sb.mark_sacked(3000, 4000);
592        sb.mark_sacked(5000, 6000);
593        // Now merge all three by inserting a spanning range
594        sb.mark_sacked(1500, 5500);
595
596        assert_eq!(sb.block_count(), 1);
597        assert_eq!(sb.blocks()[0], SackBlock::new(1000, 6000));
598    }
599
600    #[test]
601    fn test_scoreboard_clear_below() {
602        let mut sb = SackScoreboard::new();
603        sb.mark_sacked(1000, 2000);
604        sb.mark_sacked(3000, 4000);
605
606        // Cumulative ACK advances to 1500 -- trims first block
607        sb.clear_below(1500);
608        assert_eq!(sb.block_count(), 2);
609        assert_eq!(sb.blocks()[0].left_edge, 1500);
610
611        // Cumulative ACK advances to 2500 -- removes first block entirely
612        sb.clear_below(2500);
613        assert_eq!(sb.block_count(), 1);
614        assert_eq!(sb.blocks()[0], SackBlock::new(3000, 4000));
615    }
616
617    #[test]
618    fn test_scoreboard_highest_sacked() {
619        let mut sb = SackScoreboard::new();
620        assert_eq!(sb.highest_sacked(), None);
621
622        sb.mark_sacked(1000, 2000);
623        assert_eq!(sb.highest_sacked(), Some(2000));
624
625        sb.mark_sacked(5000, 6000);
626        assert_eq!(sb.highest_sacked(), Some(6000));
627    }
628
629    #[test]
630    fn test_scoreboard_holes() {
631        let mut sb = SackScoreboard::new();
632        sb.mark_sacked(2000, 3000);
633        sb.mark_sacked(4000, 5000);
634
635        let holes = sb.holes(1000);
636        assert_eq!(holes.len(), 2);
637        assert_eq!(holes[0], (1000, 1000)); // [1000, 2000)
638        assert_eq!(holes[1], (3000, 1000)); // [3000, 4000)
639    }
640
641    #[test]
642    fn test_scoreboard_next_retransmit() {
643        let mut sb = SackScoreboard::new();
644        sb.mark_sacked(2000, 3000);
645        sb.mark_sacked(4000, 5000);
646
647        // First hole: [1000, 2000)
648        let next = sb.next_retransmit(1000);
649        assert_eq!(next, Some((1000, 1000)));
650
651        // If snd_una is 2000, first hole is between blocks: [3000, 4000)
652        let next = sb.next_retransmit(3000);
653        assert_eq!(next, Some((3000, 1000)));
654    }
655
656    #[test]
657    fn test_scoreboard_no_holes() {
658        let mut sb = SackScoreboard::new();
659        sb.mark_sacked(1000, 3000);
660
661        // snd_una is at start of the single block -- no hole before it
662        let next = sb.next_retransmit(1000);
663        assert_eq!(next, None);
664
665        let holes = sb.holes(1000);
666        assert!(holes.is_empty());
667    }
668
669    #[test]
670    fn test_scoreboard_wrapping_sequence() {
671        let mut sb = SackScoreboard::new();
672        // Blocks near the u32 wraparound
673        let near_max = u32::MAX - 500;
674        let past_wrap = 500u32;
675
676        sb.mark_sacked(near_max, u32::MAX);
677        sb.mark_sacked(0, past_wrap);
678
679        // These are adjacent (MAX wraps to 0) -- should merge
680        // Actually u32::MAX and 0 differ by 1, so wrapping sub = 1
681        // But our overlaps_or_adjacent check: seq_le(near_max, past_wrap) && seq_le(0,
682        // u32::MAX) near_max..u32::MAX is [MAX-500, MAX), 0..500 is [0, 500)
683        // They are NOT adjacent because MAX != 0 in wrapping (gap of 1)
684        // However the gap is only 1 byte, so they won't auto-merge
685        assert_eq!(sb.block_count(), 2);
686
687        // Verify sequence arithmetic across the boundary
688        assert!(sb.is_sacked(near_max + 100));
689        assert!(sb.is_sacked(200));
690    }
691}
veridian_kernel/net/tcp_sack.rs

veridian_kernel/net/
tcp_sack.rs
