Skip to main content

qualia_core_db/net/qdnf/route/
index.rs

1//! E08.2 — caller-backed adjacency index. Production is not capped at 16 nodes.
2
3use 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
10/// Fixed production table. Callers size work by this capacity, not by SPF's 16.
11pub 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
22/// Admitted adjacency plus unpublished recompute state.
23pub 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    /// Creates a default `AdjacencyIndex`.
37    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    /// Index scope.
53    pub const fn scope(&self) -> u64 {
54        self.scope
55    }
56
57    #[inline]
58    /// `true` when the index is dirty.
59    pub const fn is_dirty(&self) -> bool {
60        self.dirty
61    }
62
63    #[inline]
64    /// Topology generation.
65    pub const fn topology_generation(&self) -> Generation {
66        self.topology_gen
67    }
68
69    #[inline]
70    /// Published forwarding generation.
71    pub const fn published(&self) -> &ForwardingGeneration {
72        &self.live
73    }
74
75    #[inline]
76    /// Draft forwarding generation.
77    pub const fn draft(&self) -> &ForwardingGeneration {
78        &self.draft
79    }
80
81    /// Last sequence for `origin`.
82    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    /// `live` count.
91    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    /// `true` when `withdrawn`.
106    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    /// Copy live, unexpired, non-withdrawn edges into `out`.
120    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    /// Edge at `idx`.
136    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    /// Store a completed table in `draft` only. Does not replace published `live`.
144    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    /// Publish only after computation completed into `draft`.
153    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
230/// Insert a validated edge. Withdrawals become tombstones, never cheap candidates.
231pub 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        // Origin 15 is in the demo table; neighbor 16 is not.
350        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}