qualia_core_db/net/qdnf/route/
flood.rs1use 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#[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
19pub struct FloodTable {
21 slots: [Option<LsaRecord>; MAX_SLOTS],
22}
23
24impl FloodTable {
25 pub const fn new() -> Self {
27 Self {
28 slots: [None; MAX_SLOTS],
29 }
30 }
31
32 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 pub fn is_reachable(&self, origin: u8, now_unix: u64) -> bool {
65 self.has_path(origin, now_unix)
66 }
67
68 pub fn has_path(&self, origin: u8, now_unix: u64) -> bool {
70 self.count_live_origin(origin, now_unix) > 0
71 }
72
73 pub const fn missing_record_invents_reachability() -> bool {
75 false
76 }
77
78 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}