1use crate::net::qdnf::errors::QdnfError;
4use crate::net::qdnf::types::Generation;
5
6use super::forwarding::ForwardingGeneration;
7use super::spf::SpfTable;
8use super::validate::ValidatedEdge;
9
10pub const MAX_ADMITTED_EDGES: usize = 64;
12
13#[repr(C)]
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15struct Tombstone {
16 origin: u8,
17 from: u8,
18 to: u8,
19 sequence: u32,
20}
21
22pub struct AdjacencyIndex {
24 scope: u64,
25 slots: [Option<ValidatedEdge>; MAX_ADMITTED_EDGES],
26 tombs: [Option<Tombstone>; MAX_ADMITTED_EDGES],
27 last_seq: [u32; 256],
28 seq_present: [bool; 256],
29 dirty: bool,
30 topology_gen: Generation,
31 live: ForwardingGeneration,
32 draft: ForwardingGeneration,
33}
34
35impl AdjacencyIndex {
36 pub const fn new(scope: u64) -> Self {
38 Self {
39 scope,
40 slots: [None; MAX_ADMITTED_EDGES],
41 tombs: [None; MAX_ADMITTED_EDGES],
42 last_seq: [0; 256],
43 seq_present: [false; 256],
44 dirty: false,
45 topology_gen: Generation(1),
46 live: ForwardingGeneration::empty(0),
47 draft: ForwardingGeneration::empty(0),
48 }
49 }
50
51 #[inline]
52 pub const fn scope(&self) -> u64 {
54 self.scope
55 }
56
57 #[inline]
58 pub const fn is_dirty(&self) -> bool {
60 self.dirty
61 }
62
63 #[inline]
64 pub const fn topology_generation(&self) -> Generation {
66 self.topology_gen
67 }
68
69 #[inline]
70 pub const fn published(&self) -> &ForwardingGeneration {
72 &self.live
73 }
74
75 #[inline]
76 pub const fn draft(&self) -> &ForwardingGeneration {
78 &self.draft
79 }
80
81 pub fn last_sequence(&self, origin: u8) -> Option<u32> {
83 if self.seq_present[origin as usize] {
84 Some(self.last_seq[origin as usize])
85 } else {
86 None
87 }
88 }
89
90 pub fn live_count(&self, now_unix: u64) -> usize {
92 let mut n = 0usize;
93 let mut i = 0usize;
94 while i < MAX_ADMITTED_EDGES {
95 if let Some(e) = self.slots[i] {
96 if !e.withdrawn && now_unix < e.expiry_unix {
97 n += 1;
98 }
99 }
100 i += 1;
101 }
102 n
103 }
104
105 pub fn is_withdrawn(&self, from: u8, to: u8) -> bool {
107 let mut i = 0usize;
108 while i < MAX_ADMITTED_EDGES {
109 if let Some(t) = self.tombs[i] {
110 if (t.from == from && t.to == to) || (t.from == to && t.to == from) {
111 return true;
112 }
113 }
114 i += 1;
115 }
116 false
117 }
118
119 pub fn live_edges(&self, now_unix: u64, out: &mut [ValidatedEdge]) -> usize {
121 let mut n = 0usize;
122 let mut i = 0usize;
123 while i < MAX_ADMITTED_EDGES && n < out.len() {
124 if let Some(e) = self.slots[i] {
125 if !e.withdrawn && now_unix < e.expiry_unix {
126 out[n] = e;
127 n += 1;
128 }
129 }
130 i += 1;
131 }
132 n
133 }
134
135 pub fn edge_at(&self, slot: usize) -> Option<ValidatedEdge> {
137 if slot >= MAX_ADMITTED_EDGES {
138 return None;
139 }
140 self.slots[slot]
141 }
142
143 pub fn store_recompute(&mut self, table: SpfTable) -> Result<(), QdnfError> {
145 self.draft = ForwardingGeneration::empty(self.topology_gen.0);
146 self.draft.table = table;
147 self.draft.published = false;
148 self.dirty = false;
149 Ok(())
150 }
151
152 pub fn publish_recompute(&mut self) -> Result<(), QdnfError> {
154 self.live.publish(self.draft.table)?;
155 self.live.id = self.draft.id;
156 self.draft = ForwardingGeneration::empty(0);
157 Ok(())
158 }
159
160 fn bump(&mut self) -> Result<(), QdnfError> {
161 self.topology_gen = self.topology_gen.next()?;
162 self.dirty = true;
163 Ok(())
164 }
165
166 fn remember_seq(&mut self, origin: u8, sequence: u32) {
167 self.last_seq[origin as usize] = sequence;
168 self.seq_present[origin as usize] = true;
169 }
170
171 fn find_live(&self, from: u8, to: u8) -> Option<usize> {
172 let mut i = 0usize;
173 while i < MAX_ADMITTED_EDGES {
174 if let Some(e) = self.slots[i] {
175 if !e.withdrawn && same_undirected(e.from, e.to, from, to) {
176 return Some(i);
177 }
178 }
179 i += 1;
180 }
181 None
182 }
183
184 fn find_tomb(&self, origin: u8, from: u8, to: u8) -> Option<usize> {
185 let mut i = 0usize;
186 while i < MAX_ADMITTED_EDGES {
187 if let Some(t) = self.tombs[i] {
188 if t.origin == origin && same_undirected(t.from, t.to, from, to) {
189 return Some(i);
190 }
191 }
192 i += 1;
193 }
194 None
195 }
196
197 fn free_slot(&self) -> Option<usize> {
198 let mut i = 0usize;
199 while i < MAX_ADMITTED_EDGES {
200 if self.slots[i].is_none() {
201 return Some(i);
202 }
203 i += 1;
204 }
205 None
206 }
207
208 fn free_tomb(&self) -> Option<usize> {
209 let mut i = 0usize;
210 while i < MAX_ADMITTED_EDGES {
211 if self.tombs[i].is_none() {
212 return Some(i);
213 }
214 i += 1;
215 }
216 None
217 }
218
219 fn clear_tomb(&mut self, origin: u8, from: u8, to: u8) {
220 if let Some(i) = self.find_tomb(origin, from, to) {
221 self.tombs[i] = None;
222 }
223 }
224}
225
226fn same_undirected(a: u8, b: u8, c: u8, d: u8) -> bool {
227 (a == c && b == d) || (a == d && b == c)
228}
229
230pub fn insert_edge(index: &mut AdjacencyIndex, rec: ValidatedEdge) -> Result<(), QdnfError> {
232 if rec.origin == 0 {
233 return Err(QdnfError::Range);
234 }
235 if let Some(prev) = index.last_sequence(rec.origin) {
236 if rec.sequence <= prev {
237 return Err(QdnfError::StaleGeneration);
238 }
239 }
240 if rec.withdrawn {
241 return withdraw(index, rec);
242 }
243 if let Some(ti) = index.find_tomb(rec.origin, rec.from, rec.to) {
244 let t = index.tombs[ti].unwrap();
245 if rec.sequence <= t.sequence {
246 return Err(QdnfError::StaleGeneration);
247 }
248 index.tombs[ti] = None;
249 } else if index.is_withdrawn(rec.from, rec.to) {
250 return Err(QdnfError::Conflict);
251 }
252 if let Some(slot) = index.find_live(rec.from, rec.to) {
253 let existing = index.slots[slot].unwrap();
254 if existing.origin != rec.origin {
255 return Err(QdnfError::Conflict);
256 }
257 if existing.cost != rec.cost
258 && existing.sequence == rec.sequence
259 && existing.origin == rec.origin
260 {
261 return Err(QdnfError::Conflict);
262 }
263 index.slots[slot] = Some(rec);
264 index.remember_seq(rec.origin, rec.sequence);
265 index.bump()?;
266 return Ok(());
267 }
268 let slot = index.free_slot().ok_or(QdnfError::Capacity)?;
269 index.slots[slot] = Some(rec);
270 index.remember_seq(rec.origin, rec.sequence);
271 index.bump()
272}
273
274fn withdraw(index: &mut AdjacencyIndex, rec: ValidatedEdge) -> Result<(), QdnfError> {
275 if let Some(slot) = index.find_live(rec.from, rec.to) {
276 let existing = index.slots[slot].unwrap();
277 if existing.origin != rec.origin {
278 return Err(QdnfError::Conflict);
279 }
280 index.slots[slot] = None;
281 }
282 index.clear_tomb(rec.origin, rec.from, rec.to);
283 let ti = index.free_tomb().ok_or(QdnfError::Capacity)?;
284 index.tombs[ti] = Some(Tombstone {
285 origin: rec.origin,
286 from: rec.from,
287 to: rec.to,
288 sequence: rec.sequence,
289 });
290 index.remember_seq(rec.origin, rec.sequence);
291 index.bump()
292}
293
294#[cfg(test)]
295mod tests {
296 use super::*;
297 use crate::net::qdnf::route::spf::{compute_spf, LinkMetric, MAX_NODES};
298 use crate::net::qdnf::route::validate::{insert, TopologyRecord, PROFILE_P0};
299 use crate::net::qdnf::types::StrongDigest;
300
301 fn rec(origin: u8, from: u8, to: u8, seq: u32) -> TopologyRecord {
302 TopologyRecord {
303 origin,
304 origin_digest: {
305 let mut d = StrongDigest::ZERO;
306 d.0[0] = origin;
307 d.0[47] = 1;
308 d
309 },
310 scope: 1,
311 from,
312 to,
313 sequence: seq,
314 expiry_unix: 100,
315 withdrawn: false,
316 bidirectional: true,
317 cost: 1,
318 latency_ms: 1,
319 energy_uj: 1,
320 energy_known: true,
321 realm_bit: 0,
322 profile: PROFILE_P0,
323 failure_domain: origin,
324 digest: StrongDigest::ZERO,
325 }
326 }
327
328 #[test]
329 fn route_a_seventeenth_edge_admitted_spf_still_range() {
330 let mut index = AdjacencyIndex::new(1);
331 let mut seq = 1u32;
332 for i in 0..16u8 {
333 let from = i + 1;
334 let to = i + 2;
335 insert(&rec(from, from, to, seq), 1, 1, None, &mut index).unwrap();
336 seq += 1;
337 }
338 assert_eq!(index.live_count(1), 16);
339 insert(&rec(17, 17, 18, seq), 1, 1, None, &mut index).unwrap();
340 assert_eq!(index.live_count(1), 17);
341
342 let oversize = [LinkMetric {
343 from: 15,
344 to: 16,
345 cost: 1,
346 bidirectional: true,
347 }];
348 let mut table = SpfTable::EMPTY;
349 assert_eq!(
351 compute_spf(15, &oversize, &mut table),
352 Err(QdnfError::Range)
353 );
354 assert_eq!(
355 compute_spf(MAX_NODES as u8, &[], &mut table),
356 Err(QdnfError::Range)
357 );
358 assert!(MAX_ADMITTED_EDGES > MAX_NODES);
359 }
360
361 #[test]
362 fn unpublished_recompute_does_not_replace_published() {
363 let mut index = AdjacencyIndex::new(1);
364 insert(&rec(1, 1, 2, 1), 1, 1, None, &mut index).unwrap();
365 let mut table = SpfTable::EMPTY;
366 table.nodes = 2;
367 table.dest[0] = 1;
368 table.dest[1] = 2;
369 table.hop_counts[1] = 1;
370 table.hops[1][0].node = 2;
371 index.live.publish(table).unwrap();
372 assert_eq!(index.published().lookup_next(2), Ok(2));
373
374 let mut draft_table = SpfTable::EMPTY;
375 draft_table.nodes = 2;
376 draft_table.dest[0] = 1;
377 draft_table.dest[1] = 3;
378 index.store_recompute(draft_table).unwrap();
379 assert_eq!(index.draft().lookup_next(3), Err(QdnfError::Incomplete));
380 assert_eq!(index.published().lookup_next(2), Ok(2));
381 assert_ne!(index.published().table.dest[1], 3);
382 }
383
384 #[test]
385 fn unpublished_forwarding_cannot_lookup() {
386 let index = AdjacencyIndex::new(1);
387 assert_eq!(index.published().lookup_next(1), Err(QdnfError::Incomplete));
388 assert_eq!(index.draft().lookup_next(1), Err(QdnfError::Incomplete));
389 }
390
391 #[test]
392 fn duplicate_origin_conflicting_adjacency_is_conflict() {
393 let mut index = AdjacencyIndex::new(1);
394 insert(&rec(1, 1, 2, 1), 1, 1, None, &mut index).unwrap();
395 assert_eq!(
396 insert(&rec(3, 1, 2, 1), 1, 1, None, &mut index),
397 Err(QdnfError::Conflict)
398 );
399 }
400
401 #[test]
402 fn capacity_is_table_size_not_sixteen() {
403 let mut index = AdjacencyIndex::new(1);
404 let mut seq = 1u32;
405 for i in 0..MAX_ADMITTED_EDGES as u8 {
406 let from = (i % 200) + 1;
407 let to = ((i + 1) % 200) + 1;
408 if from == to {
409 continue;
410 }
411 insert(&rec(from, from, to, seq), 1, 1, None, &mut index).unwrap();
412 seq += 1;
413 }
414 assert_eq!(index.live_count(1), MAX_ADMITTED_EDGES);
415 assert_eq!(
416 insert(&rec(50, 50, 60, seq), 1, 1, None, &mut index),
417 Err(QdnfError::Capacity)
418 );
419 }
420}