Skip to main content

qualia_core_db/net/qdnf/route/
flood.rs

1//! Bounded LSA flood admission. Missing/expired records never invent reachability.
2
3use crate::net::qdnf::errors::QdnfError;
4
5pub const MAX_ORIGINS: usize = 16;
6pub const MAX_LSA_PER_ORIGIN: usize = 4;
7const MAX_SLOTS: usize = MAX_ORIGINS * MAX_LSA_PER_ORIGIN;
8
9/// Authenticated link-state advertisement held in the flood table.
10#[repr(C)]
11#[derive(Clone, Copy, Debug, PartialEq, Eq)]
12pub struct LsaRecord {
13    pub origin: u8,
14    pub sequence: u32,
15    pub expiry_unix: u64,
16    pub digest: [u8; 32],
17}
18
19/// 16 origins × 4 sequence slots. Admission is fail-closed at Capacity.
20pub struct FloodTable {
21    slots: [Option<LsaRecord>; MAX_SLOTS],
22}
23
24impl FloodTable {
25    /// Creates a default `FloodTable`.
26    pub const fn new() -> Self {
27        Self {
28            slots: [None; MAX_SLOTS],
29        }
30    }
31
32    /// Admit `rec` at `now_unix`.
33    ///
34    /// Expired input → [`QdnfError::Expired`]. Same origin+sequence with a
35    /// different digest → [`QdnfError::Conflict`] (authenticated conflict,
36    /// before quarantine). Same digest → [`QdnfError::ReservationUnchanged`].
37    pub fn admit(&mut self, rec: LsaRecord, now_unix: u64) -> Result<(), QdnfError> {
38        if now_unix >= rec.expiry_unix {
39            return Err(QdnfError::Expired);
40        }
41        if let Some(existing) = self.live_match(rec.origin, rec.sequence, now_unix) {
42            if existing.digest == rec.digest {
43                return Err(QdnfError::ReservationUnchanged);
44            }
45            return Err(QdnfError::Conflict);
46        }
47        let live_for_origin = self.count_live_origin(rec.origin, now_unix);
48        if live_for_origin >= MAX_LSA_PER_ORIGIN {
49            return Err(QdnfError::Capacity);
50        }
51        if self.origin_is_new(rec.origin, now_unix)
52            && self.count_live_origins(now_unix) >= MAX_ORIGINS
53        {
54            return Err(QdnfError::Capacity);
55        }
56        let slot = self
57            .free_slot(rec.origin, now_unix)
58            .ok_or(QdnfError::Capacity)?;
59        self.slots[slot] = Some(rec);
60        Ok(())
61    }
62
63    /// True only when an admitted, unexpired record exists for `origin`.
64    pub fn is_reachable(&self, origin: u8, now_unix: u64) -> bool {
65        self.has_path(origin, now_unix)
66    }
67
68    /// Missing records do not invent a path.
69    pub fn has_path(&self, origin: u8, now_unix: u64) -> bool {
70        self.count_live_origin(origin, now_unix) > 0
71    }
72
73    /// `FloodTable::missing_record_invents_reachability`.
74    pub const fn missing_record_invents_reachability() -> bool {
75        false
76    }
77
78    /// `true` when `default_route` present.
79    pub const fn has_default_route() -> bool {
80        false
81    }
82
83    fn live_match(&self, origin: u8, sequence: u32, now_unix: u64) -> Option<LsaRecord> {
84        let mut i = 0usize;
85        while i < MAX_SLOTS {
86            if let Some(rec) = self.slots[i] {
87                if rec.origin == origin && rec.sequence == sequence && now_unix < rec.expiry_unix {
88                    return Some(rec);
89                }
90            }
91            i += 1;
92        }
93        None
94    }
95
96    fn count_live_origin(&self, origin: u8, now_unix: u64) -> usize {
97        let mut n = 0usize;
98        let mut i = 0usize;
99        while i < MAX_SLOTS {
100            if let Some(rec) = self.slots[i] {
101                if rec.origin == origin && now_unix < rec.expiry_unix {
102                    n += 1;
103                }
104            }
105            i += 1;
106        }
107        n
108    }
109
110    fn count_live_origins(&self, now_unix: u64) -> usize {
111        let mut seen = [false; 256];
112        let mut n = 0usize;
113        let mut i = 0usize;
114        while i < MAX_SLOTS {
115            if let Some(rec) = self.slots[i] {
116                if now_unix < rec.expiry_unix {
117                    let idx = rec.origin as usize;
118                    if !seen[idx] {
119                        seen[idx] = true;
120                        n += 1;
121                    }
122                }
123            }
124            i += 1;
125        }
126        n
127    }
128
129    fn origin_is_new(&self, origin: u8, now_unix: u64) -> bool {
130        self.count_live_origin(origin, now_unix) == 0
131    }
132
133    fn free_slot(&self, origin: u8, now_unix: u64) -> Option<usize> {
134        let mut expired_same = None;
135        let mut expired_any = None;
136        let mut empty = None;
137        let mut i = 0usize;
138        while i < MAX_SLOTS {
139            match self.slots[i] {
140                None => {
141                    if empty.is_none() {
142                        empty = Some(i);
143                    }
144                }
145                Some(rec) => {
146                    if now_unix >= rec.expiry_unix {
147                        if rec.origin == origin && expired_same.is_none() {
148                            expired_same = Some(i);
149                        } else if expired_any.is_none() {
150                            expired_any = Some(i);
151                        }
152                    }
153                }
154            }
155            i += 1;
156        }
157        expired_same.or(empty).or(expired_any)
158    }
159}
160
161impl Default for FloodTable {
162    fn default() -> Self {
163        Self::new()
164    }
165}
166
167#[cfg(test)]
168mod tests {
169    use super::*;
170
171    fn rec(origin: u8, sequence: u32, expiry_unix: u64, digest_byte: u8) -> LsaRecord {
172        LsaRecord {
173            origin,
174            sequence,
175            expiry_unix,
176            digest: [digest_byte; 32],
177        }
178    }
179
180    #[test]
181    fn missing_record_does_not_invent_reachability() {
182        let table = FloodTable::new();
183        assert!(!FloodTable::missing_record_invents_reachability());
184        assert!(!table.is_reachable(0, 10));
185        assert!(!table.has_path(3, 10));
186        assert!(!FloodTable::has_default_route());
187    }
188
189    #[test]
190    fn admit_then_reachable_until_expiry() {
191        let mut table = FloodTable::new();
192        table.admit(rec(2, 1, 100, 7), 10).unwrap();
193        assert!(table.is_reachable(2, 10));
194        assert!(table.has_path(2, 99));
195        assert!(!table.is_reachable(2, 100));
196        assert!(!table.has_path(1, 10));
197    }
198
199    #[test]
200    fn expired_input_is_rejected() {
201        let mut table = FloodTable::new();
202        assert_eq!(table.admit(rec(0, 1, 10, 1), 10), Err(QdnfError::Expired));
203        assert!(!table.is_reachable(0, 10));
204    }
205
206    #[test]
207    fn same_origin_sequence_different_digest_is_conflict() {
208        let mut table = FloodTable::new();
209        table.admit(rec(4, 8, 50, 1), 1).unwrap();
210        assert_eq!(table.admit(rec(4, 8, 50, 2), 1), Err(QdnfError::Conflict));
211        assert!(table.is_reachable(4, 1));
212    }
213
214    #[test]
215    fn same_digest_is_suppressed() {
216        let mut table = FloodTable::new();
217        table.admit(rec(1, 3, 50, 9), 1).unwrap();
218        assert_eq!(
219            table.admit(rec(1, 3, 50, 9), 1),
220            Err(QdnfError::ReservationUnchanged)
221        );
222        assert!(table.is_reachable(1, 1));
223    }
224
225    #[test]
226    fn per_origin_slot_capacity() {
227        let mut table = FloodTable::new();
228        for seq in 0..MAX_LSA_PER_ORIGIN as u32 {
229            table.admit(rec(0, seq, 100, seq as u8), 1).unwrap();
230        }
231        assert_eq!(
232            table.admit(rec(0, 99, 100, 99), 1),
233            Err(QdnfError::Capacity)
234        );
235        table.admit(rec(1, 0, 100, 1), 1).unwrap();
236        assert!(table.is_reachable(0, 1));
237        assert!(table.is_reachable(1, 1));
238    }
239
240    #[test]
241    fn expired_slot_can_be_reused() {
242        let mut table = FloodTable::new();
243        table.admit(rec(0, 1, 5, 1), 1).unwrap();
244        assert!(!table.is_reachable(0, 5));
245        table.admit(rec(0, 2, 50, 2), 5).unwrap();
246        assert!(table.is_reachable(0, 5));
247    }
248}