Skip to main content

qualia_core_db/net/dns/
cache_ring.rs

1//! Zero-heap circular ring buffer for DNS and SDN Q42 records.
2//!
3//! Maintains a fast, deterministic cache of recent DNS resolution quins
4//! without performing any heap allocations (Vec/String/Box).
5//!
6//! Provides explicit TTL-based pruning, clock-based pruning, and zero-heap
7//! archival extraction into caller-supplied storage buffers.
8//!
9//! Fully conforms to QualiaDB Rule 0-A (zero heap in hot paths) and Rule 0-B.
10
11#![allow(dead_code)]
12
13use crate::NQuin;
14
15/// Default capacity for the stack-resident DNS ring buffer.
16pub const DEFAULT_DNS_CACHE_CAPACITY: usize = 256;
17
18/// Zero-allocation ring buffer storing `NQuin` records.
19#[derive(Debug, Clone)]
20pub struct DnsCacheRing<const N: usize = DEFAULT_DNS_CACHE_CAPACITY> {
21    slots: [NQuin; N],
22    timestamps: [u32; N],
23    head: usize,
24    count: usize,
25}
26
27impl<const N: usize> Default for DnsCacheRing<N> {
28    fn default() -> Self {
29        Self::new()
30    }
31}
32
33impl<const N: usize> DnsCacheRing<N> {
34    /// Creates a default `DnsCacheRing`.
35    pub const fn new() -> Self {
36        Self {
37            slots: [NQuin {
38                subject: 0,
39                predicate: 0,
40                object: 0,
41                context: 0,
42                metadata: 0,
43                parity: 0,
44            }; N],
45            timestamps: [0u32; N],
46            head: 0,
47            count: 0,
48        }
49    }
50
51    /// Number of active items in the ring buffer.
52    pub fn len(&self) -> usize {
53        self.count
54    }
55
56    /// Check if the cache is empty.
57    pub fn is_empty(&self) -> bool {
58        self.count == 0
59    }
60
61    /// Insert a quin into the ring buffer, evicting the oldest entry on wrap.
62    pub fn insert(&mut self, quin: NQuin, current_clock: u32) {
63        if !quin.verify_ecc_parity() {
64            return;
65        }
66        let idx = self.head % N;
67        self.slots[idx] = quin;
68        self.timestamps[idx] = current_clock;
69        self.head = self.head.wrapping_add(1);
70        if self.count < N {
71            self.count += 1;
72        }
73    }
74
75    /// Find the most recent record matching `subject_hash` and `opcode`.
76    /// Searches backwards from most recently inserted to oldest. Zero-allocation.
77    pub fn lookup(&self, subject_hash: u64, opcode: u8) -> Option<NQuin> {
78        let active = self.count;
79        for i in 0..active {
80            let offset = (self.head.wrapping_sub(1).wrapping_sub(i)) % N;
81            let quin = self.slots[offset];
82            if quin.subject == subject_hash && (quin.predicate & 0xFF) as u8 == opcode {
83                return Some(quin);
84            }
85        }
86        None
87    }
88
89    /// Find the most recent record matching `subject_hash` and `opcode` that has NOT expired.
90    ///
91    /// Verifies `current_clock < inserted_clock + ttl`. Zero-allocation.
92    pub fn lookup_valid(&self, subject_hash: u64, opcode: u8, current_clock: u32) -> Option<NQuin> {
93        let active = self.count;
94        for i in 0..active {
95            let offset = (self.head.wrapping_sub(1).wrapping_sub(i)) % N;
96            let quin = self.slots[offset];
97            if quin.subject == subject_hash && (quin.predicate & 0xFF) as u8 == opcode {
98                let ttl = (quin.metadata & 0xFFFF_FFFF) as u32;
99                let inserted_at = self.timestamps[offset];
100                if current_clock < inserted_at.saturating_add(ttl) {
101                    return Some(quin);
102                }
103            }
104        }
105        None
106    }
107
108    /// Collect all records matching `subject_hash` into a caller-supplied buffer.
109    ///
110    /// Returns the number of items written into `out`. Zero-allocation.
111    pub fn lookup_all(&self, subject_hash: u64, out: &mut [NQuin]) -> usize {
112        let mut written = 0;
113        let active = self.count;
114        for i in 0..active {
115            if written >= out.len() {
116                break;
117            }
118            let offset = (self.head.wrapping_sub(1).wrapping_sub(i)) % N;
119            let quin = self.slots[offset];
120            if quin.subject == subject_hash {
121                out[written] = quin;
122                written += 1;
123            }
124        }
125        written
126    }
127
128    /// Prune all expired records from the ring buffer based on `current_clock`.
129    ///
130    /// Reclaims slots and compacts active unexpired entries in place.
131    /// Returns the count of pruned records. Zero heap allocation.
132    pub fn prune_expired(&mut self, current_clock: u32) -> usize {
133        let mut retained_slots = [NQuin::default(); N];
134        let mut retained_times = [0u32; N];
135        let mut retained_count = 0;
136
137        let active = self.count;
138        for i in 0..active {
139            let offset = (self.head.wrapping_sub(active).wrapping_add(i)) % N;
140            let quin = self.slots[offset];
141            let ttl = (quin.metadata & 0xFFFF_FFFF) as u32;
142            let inserted_at = self.timestamps[offset];
143            let is_expired = current_clock >= inserted_at.saturating_add(ttl);
144
145            if !is_expired {
146                retained_slots[retained_count] = quin;
147                retained_times[retained_count] = inserted_at;
148                retained_count += 1;
149            }
150        }
151
152        let pruned = self.count - retained_count;
153        self.slots = retained_slots;
154        self.timestamps = retained_times;
155        self.head = retained_count;
156        self.count = retained_count;
157        pruned
158    }
159
160    /// Prune records inserted strictly before `cutoff_clock`.
161    ///
162    /// Returns the count of pruned records. Zero heap allocation.
163    pub fn prune_older_than(&mut self, cutoff_clock: u32) -> usize {
164        let mut retained_slots = [NQuin::default(); N];
165        let mut retained_times = [0u32; N];
166        let mut retained_count = 0;
167
168        let active = self.count;
169        for i in 0..active {
170            let offset = (self.head.wrapping_sub(active).wrapping_add(i)) % N;
171            let quin = self.slots[offset];
172            let inserted_at = self.timestamps[offset];
173
174            if inserted_at >= cutoff_clock {
175                retained_slots[retained_count] = quin;
176                retained_times[retained_count] = inserted_at;
177                retained_count += 1;
178            }
179        }
180
181        let pruned = self.count - retained_count;
182        self.slots = retained_slots;
183        self.timestamps = retained_times;
184        self.head = retained_count;
185        self.count = retained_count;
186        pruned
187    }
188
189    /// Archive all expired records into `archive_sink` and remove them from the ring buffer.
190    ///
191    /// Returns the count of archived records written into `archive_sink`. Zero heap allocation.
192    pub fn archive_expired_into(
193        &mut self,
194        current_clock: u32,
195        archive_sink: &mut [NQuin],
196    ) -> usize {
197        let mut archived = 0;
198        let mut retained_count = 0;
199        let active = self.count;
200
201        let mut retained_slots = [NQuin::default(); N];
202        let mut retained_times = [0u32; N];
203
204        for i in 0..active {
205            let offset = (self.head.wrapping_sub(active).wrapping_add(i)) % N;
206            let quin = self.slots[offset];
207            let ttl = (quin.metadata & 0xFFFF_FFFF) as u32;
208            let inserted_at = self.timestamps[offset];
209            let is_expired = current_clock >= inserted_at.saturating_add(ttl);
210
211            if is_expired {
212                if archived < archive_sink.len() {
213                    archive_sink[archived] = quin;
214                    archived += 1;
215                }
216            } else {
217                retained_slots[retained_count] = quin;
218                retained_times[retained_count] = inserted_at;
219                retained_count += 1;
220            }
221        }
222
223        self.slots = retained_slots;
224        self.timestamps = retained_times;
225        self.head = retained_count;
226        self.count = retained_count;
227        archived
228    }
229
230    /// Archive records inserted before `cutoff_clock` into `archive_sink` and remove them.
231    ///
232    /// Returns the count of archived records written into `archive_sink`. Zero heap allocation.
233    pub fn archive_older_than(&mut self, cutoff_clock: u32, archive_sink: &mut [NQuin]) -> usize {
234        let mut archived = 0;
235        let mut retained_count = 0;
236        let active = self.count;
237
238        let mut retained_slots = [NQuin::default(); N];
239        let mut retained_times = [0u32; N];
240
241        for i in 0..active {
242            let offset = (self.head.wrapping_sub(active).wrapping_add(i)) % N;
243            let quin = self.slots[offset];
244            let inserted_at = self.timestamps[offset];
245            let is_older = inserted_at < cutoff_clock;
246
247            if is_older {
248                if archived < archive_sink.len() {
249                    archive_sink[archived] = quin;
250                    archived += 1;
251                }
252            } else {
253                retained_slots[retained_count] = quin;
254                retained_times[retained_count] = inserted_at;
255                retained_count += 1;
256            }
257        }
258
259        self.slots = retained_slots;
260        self.timestamps = retained_times;
261        self.head = retained_count;
262        self.count = retained_count;
263        archived
264    }
265
266    /// Clear all cached records.
267    pub fn clear(&mut self) {
268        self.head = 0;
269        self.count = 0;
270    }
271}
272
273#[cfg(test)]
274mod tests {
275    use super::*;
276    use crate::net::dns::quin_records::*;
277    use crate::PermissiveRoutingLane;
278
279    #[test]
280    fn ring_insert_and_lookup() {
281        let mut ring = DnsCacheRing::<16>::new();
282        assert!(ring.is_empty());
283
284        let q1 = encode_a_record(
285            "host1.lan",
286            [10, 0, 0, 1],
287            60,
288            PermissiveRoutingLane::PassthroughStandard,
289        );
290        let q2 = encode_a_record(
291            "host2.lan",
292            [10, 0, 0, 2],
293            60,
294            PermissiveRoutingLane::PassthroughStandard,
295        );
296
297        ring.insert(q1, 100);
298        ring.insert(q2, 101);
299        assert_eq!(ring.len(), 2);
300
301        let found = ring.lookup(q1.subject, OP_DNS_A).unwrap();
302        assert_eq!(found.object, q1.object);
303
304        assert!(ring.lookup(99999, OP_DNS_A).is_none());
305        assert!(ring.lookup(q1.subject, OP_DNS_TXT).is_none());
306    }
307
308    #[test]
309    fn ring_lookup_valid_ttl_expiration() {
310        let mut ring = DnsCacheRing::<16>::new();
311        let q1 = encode_a_record(
312            "expiring.lan",
313            [192, 168, 1, 1],
314            10,
315            PermissiveRoutingLane::PassthroughStandard,
316        );
317        ring.insert(q1, 100); // inserted at clock 100 with TTL 10 -> valid until < 110
318
319        // At clock 105: still valid
320        assert!(ring.lookup_valid(q1.subject, OP_DNS_A, 105).is_some());
321
322        // At clock 110: expired
323        assert!(ring.lookup_valid(q1.subject, OP_DNS_A, 110).is_none());
324    }
325
326    #[test]
327    fn ring_prune_expired() {
328        let mut ring = DnsCacheRing::<16>::new();
329        let q_short = encode_a_record(
330            "short.lan",
331            [1, 1, 1, 1],
332            5,
333            PermissiveRoutingLane::PassthroughStandard,
334        );
335        let q_long = encode_a_record(
336            "long.lan",
337            [2, 2, 2, 2],
338            100,
339            PermissiveRoutingLane::PassthroughStandard,
340        );
341
342        ring.insert(q_short, 50); // expires at 55
343        ring.insert(q_long, 50); // expires at 150
344        assert_eq!(ring.len(), 2);
345
346        // At clock 60, q_short has expired
347        let pruned = ring.prune_expired(60);
348        assert_eq!(pruned, 1);
349        assert_eq!(ring.len(), 1);
350
351        assert!(ring.lookup(q_short.subject, OP_DNS_A).is_none());
352        assert!(ring.lookup(q_long.subject, OP_DNS_A).is_some());
353    }
354
355    #[test]
356    fn ring_archive_expired_into() {
357        let mut ring = DnsCacheRing::<16>::new();
358        let q_expired1 = encode_a_record(
359            "exp1.lan",
360            [10, 0, 0, 1],
361            10,
362            PermissiveRoutingLane::PassthroughStandard,
363        );
364        let q_expired2 = encode_a_record(
365            "exp2.lan",
366            [10, 0, 0, 2],
367            15,
368            PermissiveRoutingLane::PassthroughStandard,
369        );
370        let q_alive = encode_a_record(
371            "alive.lan",
372            [10, 0, 0, 3],
373            300,
374            PermissiveRoutingLane::PassthroughStandard,
375        );
376
377        ring.insert(q_expired1, 100); // expires at 110
378        ring.insert(q_expired2, 100); // expires at 115
379        ring.insert(q_alive, 100); // expires at 400
380
381        let mut archive = [NQuin::default(); 4];
382        let count = ring.archive_expired_into(120, &mut archive);
383
384        assert_eq!(count, 2);
385        assert_eq!(archive[0].subject, q_expired1.subject);
386        assert_eq!(archive[1].subject, q_expired2.subject);
387        assert_eq!(ring.len(), 1);
388        assert!(ring.lookup(q_alive.subject, OP_DNS_A).is_some());
389    }
390
391    #[test]
392    fn ring_wrap_eviction() {
393        let mut ring = DnsCacheRing::<4>::new();
394        for i in 0..6 {
395            let q = encode_a_record(
396                "wrap.lan",
397                [10, 0, 0, i as u8],
398                60,
399                PermissiveRoutingLane::PassthroughStandard,
400            );
401            ring.insert(q, i as u32);
402        }
403        assert_eq!(ring.len(), 4);
404        let found = ring
405            .lookup(
406                encode_a_record(
407                    "wrap.lan",
408                    [0, 0, 0, 0],
409                    60,
410                    PermissiveRoutingLane::PassthroughStandard,
411                )
412                .subject,
413                OP_DNS_A,
414            )
415            .unwrap();
416        assert_eq!(
417            found.object,
418            encode_a_record(
419                "wrap.lan",
420                [10, 0, 0, 5],
421                60,
422                PermissiveRoutingLane::PassthroughStandard
423            )
424            .object
425        );
426    }
427
428    #[test]
429    fn lookup_all_zero_heap() {
430        let mut ring = DnsCacheRing::<16>::new();
431        let q1 = encode_a_record(
432            "multi.lan",
433            [1, 2, 3, 4],
434            60,
435            PermissiveRoutingLane::PassthroughStandard,
436        );
437        let q2 = encode_txt_record(
438            "multi.lan",
439            "v=spf1",
440            60,
441            PermissiveRoutingLane::PassthroughStandard,
442        );
443
444        ring.insert(q1, 1);
445        ring.insert(q2, 2);
446
447        let mut out = [NQuin::default(); 4];
448        let n = ring.lookup_all(q1.subject, &mut out);
449        assert_eq!(n, 2);
450    }
451}