atmos/kernel/net/
reassembly.rs

1//! TCP 受信側の順序外セグメント再構成バッファ。
2//!
3//! 仕様・実測データ・優先順位は `spec/tcp_receive.md` を参照。
4//! 典拠: RFC 9293 §3.10.7.4（Segment Receive）。
5//!
6//! ## なぜ必要か
7//! RFC 9293 は順序外セグメントの破棄を**許容**している（キューイングは実装の裁量）。
8//! したがって現行の「破棄 + RCV.NXT を載せた ACK」は RFC 違反ではない。
9//! しかし性能上は致命的で、実測では 660 セグメント中 33 個（5%）を破棄し、
10//! ソケットが ESTABLISHED のまま `rx_buf=0` で停止していた。
11//! 1 個の欠落で以降の到着分をすべて捨て、相手の再送を待つためである。
12//!
13//! ここに保持しておけば、欠けた 1 個が再送で埋まった瞬間に
14//! まとめて上位へ渡せる。
15//!
16//! グローバル状態にもハードウェアにも依存しない純粋ロジックのみで構成する。
17
18extern crate alloc;
19
20use alloc::vec::Vec;
21
22/// 保持できる順序外セグメントの最大数。超えた分は破棄する
23/// （破棄しても RFC 上は正しく、相手の再送で回復する）。
24pub const MAX_SEGMENTS: usize = 16;
25
26/// 保持できる合計バイト数の上限。メモリ枯渇を防ぐ。
27pub const MAX_BYTES: usize = 64 * 1024;
28
29/// 挿入結果。
30#[derive(Debug, PartialEq, Eq, Clone, Copy)]
31pub enum InsertOutcome {
32    /// 保持した。
33    Stored,
34    /// 既に同じ seq を保持しているので無視した（重複到着）。
35    Duplicate,
36    /// 容量超過のため破棄した。相手の再送に委ねる。
37    Dropped,
38}
39
40/// 引数が不正だった場合のエラー。
41#[derive(Debug, PartialEq, Eq, Clone, Copy)]
42pub enum ReassemblyError {
43    /// 空ペイロードを渡された。順序外バッファに入れる意味が無い。
44    EmptyPayload,
45}
46
47/// 順序外セグメントを seq 昇順で保持する。
48#[derive(Debug, Default)]
49pub struct Reassembler {
50    /// (seq, data) を seq 昇順で保持する。
51    segs: Vec<(u32, Vec<u8>)>,
52    bytes: usize,
53}
54
55impl Reassembler {
56    pub fn new() -> Self {
57        Self::default()
58    }
59
60    /// `static` 配列の初期化用（`const` 文脈で使える）。
61    pub const fn new_const() -> Self {
62        Self {
63            segs: Vec::new(),
64            bytes: 0,
65        }
66    }
67
68    /// 保持中のセグメント数。
69    pub fn len(&self) -> usize {
70        self.segs.len()
71    }
72
73    pub fn is_empty(&self) -> bool {
74        self.segs.is_empty()
75    }
76
77    /// 保持中の合計バイト数。
78    pub fn bytes(&self) -> usize {
79        self.bytes
80    }
81
82    /// 順序外セグメントを保持する。
83    ///
84    /// 空ペイロードは黙って戻らず、エラーログを出して `Err` を返す
85    /// （呼び出し側のバグを握り潰さないため）。
86    pub fn insert(&mut self, seq: u32, data: &[u8]) -> Result<InsertOutcome, ReassemblyError> {
87        if data.is_empty() {
88            crate::error!("[TCP][REASM] 空ペイロードは保持できません seq={}", seq);
89            return Err(ReassemblyError::EmptyPayload);
90        }
91        if self.segs.iter().any(|(s, _)| *s == seq) {
92            return Ok(InsertOutcome::Duplicate);
93        }
94        if self.segs.len() >= MAX_SEGMENTS || self.bytes + data.len() > MAX_BYTES {
95            return Ok(InsertOutcome::Dropped);
96        }
97        // seq 昇順を保って挿入する（後続の連結取り出しを単純にするため）。
98        let pos = self
99            .segs
100            .iter()
101            .position(|(s, _)| *s > seq)
102            .unwrap_or(self.segs.len());
103        self.segs.insert(pos, (seq, data.to_vec()));
104        self.bytes += data.len();
105        Ok(InsertOutcome::Stored)
106    }
107
108    /// `rcv_nxt` から連続する分を取り出し、新しい `rcv_nxt` とデータを返す。
109    ///
110    /// 欠落が埋まった瞬間に、そこから繋がる全セグメントをまとめて返す。
111    /// 連続していなければ空を返し `rcv_nxt` は据え置く。
112    pub fn pop_contiguous(&mut self, rcv_nxt: u32) -> (u32, Vec<u8>) {
113        let mut next = rcv_nxt;
114        let mut out: Vec<u8> = Vec::new();
115        loop {
116            // 【2026-09-26】先頭一致だけでなく、`next` を**含む**セグメント
117            // （seq <= next < seq + len）を探す。再送がまとめ直されて境界がずれると、
118            // 保持分が next の途中から始まることがあり、先頭一致だけでは永久に
119            // 取り出せず受信が止まっていた。複数あれば最も遠くまで届くものを使い、
120            // 重なり部分は捨てる（重複して出さない）。
121            let best = self
122                .segs
123                .iter()
124                .enumerate()
125                .filter_map(|(i, (s, d))| {
126                    let off = next.wrapping_sub(*s);
127                    // off < 2^31 かつ off < len なら s <= next < s+len。
128                    (off < 0x8000_0000 && (off as usize) < d.len())
129                        .then(|| (i, off as usize, d.len() - off as usize))
130                })
131                .max_by_key(|&(_, _, rest)| rest);
132            let Some((idx, off, _)) = best else {
133                break;
134            };
135            let (_, data) = self.segs.remove(idx);
136            self.bytes -= data.len();
137            let tail = data.get(off..).unwrap_or(&[]);
138            next = next.wrapping_add(tail.len() as u32);
139            out.extend_from_slice(tail);
140        }
141        // 取り出した範囲に完全に含まれる残り（重複分）は捨てる。
142        self.drop_before(next);
143        (next, out)
144    }
145
146    /// `rcv_nxt` より前（既に受信済み）のセグメントを捨て、捨てた数を返す。
147    /// 再送で重複到着したものが溜まり続けるのを防ぐ。
148    pub fn drop_before(&mut self, rcv_nxt: u32) -> usize {
149        let before = self.segs.len();
150        let mut freed = 0usize;
151        self.segs.retain(|(s, d)| {
152            // 折り返しを考慮し、rcv_nxt から見て「過去」なら捨てる。
153            let is_past = rcv_nxt.wrapping_sub(*s) < 0x8000_0000
154                && rcv_nxt.wrapping_sub(*s) >= d.len() as u32;
155            if is_past {
156                freed += d.len();
157            }
158            !is_past
159        });
160        self.bytes -= freed;
161        before - self.segs.len()
162    }
163
164    /// 全破棄（接続終了時など）。
165    pub fn clear(&mut self) {
166        self.segs.clear();
167        self.bytes = 0;
168    }
169}
atmos/kernel/net/reassembly.rs

atmos/kernel/net/
reassembly.rs
