Skip to main content

qualia_core_db/net/qdnf/resolve/qsr/
kbucket.rs

1//! In-process Kademlia k-buckets over 48-byte [`StrongDigest`] keys (E07.8).
2//!
3//! XOR-distance buckets, K=8, bootstrap, iterative lookup, and a last-seen
4//! maintenance tick. This is **not** networked Kademlia: no transport, crypto
5//! suite, replication budget, asynchronous RPCs, or two-host overlay. Do not
6//! treat results as a superiority study.
7
8use super::key::keys_equal;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::StrongDigest;
11
12/// Contacts kept per XOR-distance bucket (classic k-bucket width).
13pub const K: usize = 8;
14/// Parallel probes per iterative-lookup round (Kademlia α).
15pub const ALPHA: u8 = 3;
16/// Bit length of [`StrongDigest`]; one bucket per `floor(log2(xor))`.
17pub const BUCKET_COUNT: usize = 384;
18/// In-process contact ceiling. Fail closed; not a DHT size.
19pub const CONTACT_CAP: usize = 64;
20/// Generations of `maintain` a contact may age before it is dropped.
21pub const STALE_GENERATIONS: u32 = 2;
22
23#[repr(C)]
24#[derive(Clone, Copy)]
25struct Contact {
26    id: StrongDigest,
27    last_seen: u32,
28}
29
30impl Contact {
31    const EMPTY: Self = Self {
32        id: StrongDigest::ZERO,
33        last_seen: 0,
34    };
35}
36
37/// Bounded XOR k-bucket routing table. Caller-owned; lookup does not allocate.
38pub struct KBucketTable {
39    local: StrongDigest,
40    clock: u32,
41    bucket_len: [u8; BUCKET_COUNT],
42    contacts: [Contact; CONTACT_CAP],
43    len: u8,
44}
45
46impl KBucketTable {
47    /// Creates a default `KBucketTable`.
48    pub const fn new(local: StrongDigest) -> Self {
49        Self {
50            local,
51            clock: 1,
52            bucket_len: [0; BUCKET_COUNT],
53            contacts: [Contact::EMPTY; CONTACT_CAP],
54            len: 0,
55        }
56    }
57
58    #[inline]
59    /// `KBucketTable::local_id`.
60    pub const fn local_id(&self) -> StrongDigest {
61        self.local
62    }
63
64    #[inline]
65    /// `KBucketTable::len`.
66    pub const fn len(&self) -> usize {
67        self.len as usize
68    }
69
70    /// Insert `id`. Duplicate IDs refresh last-seen. Distance-0 (self) is Range.
71    /// A full k-bucket or a full table is Capacity.
72    pub fn insert(&mut self, id: StrongDigest) -> Result<(), QdnfError> {
73        let bucket = bucket_index(&self.local, &id)?;
74        let mut i = 0usize;
75        while i < self.len as usize {
76            if keys_equal(&self.contacts[i].id, &id) {
77                self.contacts[i].last_seen = self.clock;
78                return Ok(());
79            }
80            i += 1;
81        }
82        if self.bucket_len[bucket] as usize >= K {
83            return Err(QdnfError::Capacity);
84        }
85        if self.len as usize >= CONTACT_CAP {
86            return Err(QdnfError::Capacity);
87        }
88        let slot = self.len as usize;
89        self.contacts[slot] = Contact {
90            id,
91            last_seen: self.clock,
92        };
93        self.len = self.len + 1;
94        self.bucket_len[bucket] = self.bucket_len[bucket] + 1;
95        Ok(())
96    }
97
98    /// Insert known node IDs. Stops and fails closed on the first Capacity/Range.
99    pub fn bootstrap(&mut self, known: &[StrongDigest]) -> Result<u8, QdnfError> {
100        let mut n: u8 = 0;
101        let mut i = 0usize;
102        while i < known.len() {
103            self.insert(known[i])?;
104            n = n + 1;
105            i += 1;
106        }
107        Ok(n)
108    }
109
110    /// Up to K XOR-nearest contacts. Empty `out` with contacts present is Capacity.
111    pub fn closest(
112        &self,
113        target: &StrongDigest,
114        out: &mut [StrongDigest],
115    ) -> Result<usize, QdnfError> {
116        if out.is_empty() {
117            return Err(QdnfError::Capacity);
118        }
119        let mut ids = [StrongDigest::ZERO; K];
120        let mut dists = [[0xffu8; 48]; K];
121        let n = self.collect_closest(target, &mut ids, &mut dists);
122        let mut w = 0usize;
123        while w < n && w < out.len() {
124            out[w] = ids[w];
125            w += 1;
126        }
127        Ok(w)
128    }
129
130    /// Iterative FIND_NODE over the local table. Each shortlist probe costs one
131    /// work unit. Shared-table respondents cannot introduce unknown contacts.
132    /// Exhausting `work_budget` before every shortlist contact is probed is
133    /// [`QdnfError::BudgetExhausted`].
134    pub fn iterative_lookup(
135        &self,
136        target: &StrongDigest,
137        work_budget: u8,
138        out: &mut [StrongDigest],
139    ) -> Result<u8, QdnfError> {
140        if self.len == 0 {
141            return Err(QdnfError::Incomplete);
142        }
143        if out.is_empty() {
144            return Err(QdnfError::Capacity);
145        }
146        let mut ids = [StrongDigest::ZERO; K];
147        let mut dists = [[0xffu8; 48]; K];
148        let n = self.collect_closest(target, &mut ids, &mut dists);
149        if n == 0 {
150            return Err(QdnfError::Incomplete);
151        }
152        let mut queried = [false; K];
153        let mut used: u8 = 0;
154        loop {
155            let mut probed: u8 = 0;
156            let mut i = 0usize;
157            while i < n && probed < ALPHA {
158                if !queried[i] {
159                    if used == work_budget {
160                        return Err(QdnfError::BudgetExhausted);
161                    }
162                    used = used + 1;
163                    queried[i] = true;
164                    probed = probed + 1;
165                }
166                i += 1;
167            }
168            if probed == 0 {
169                break;
170            }
171        }
172        let mut w = 0usize;
173        while w < n && w < out.len() {
174            out[w] = ids[w];
175            w += 1;
176        }
177        Ok(used)
178    }
179
180    /// Advance the last-seen clock and drop contacts older than
181    /// [`STALE_GENERATIONS`]. Returns the number of dropped entries.
182    pub fn maintain(&mut self) -> u16 {
183        self.clock = self.clock.wrapping_add(1);
184        let old_len = self.len as usize;
185        let mut w = 0usize;
186        let mut dropped: u16 = 0;
187        let mut r = 0usize;
188        while r < old_len {
189            let age = self.clock.saturating_sub(self.contacts[r].last_seen);
190            if age <= STALE_GENERATIONS {
191                if w != r {
192                    self.contacts[w] = self.contacts[r];
193                }
194                w += 1;
195            } else {
196                dropped = dropped + 1;
197            }
198            r += 1;
199        }
200        let mut t = w;
201        while t < old_len {
202            self.contacts[t] = Contact::EMPTY;
203            t += 1;
204        }
205        self.len = w as u8;
206        self.rebuild_bucket_len();
207        dropped
208    }
209
210    fn rebuild_bucket_len(&mut self) {
211        self.bucket_len = [0; BUCKET_COUNT];
212        let mut i = 0usize;
213        while i < self.len as usize {
214            if let Ok(b) = bucket_index(&self.local, &self.contacts[i].id) {
215                self.bucket_len[b] = self.bucket_len[b] + 1;
216            }
217            i += 1;
218        }
219    }
220
221    fn collect_closest(
222        &self,
223        target: &StrongDigest,
224        ids: &mut [StrongDigest; K],
225        dists: &mut [[u8; 48]; K],
226    ) -> usize {
227        let mut n = 0usize;
228        let mut i = 0usize;
229        while i < self.len as usize {
230            let id = self.contacts[i].id;
231            let mut dist = [0u8; 48];
232            xor_bytes(target, &id, &mut dist);
233            consider_candidate(id, &dist, ids, dists, &mut n);
234            i += 1;
235        }
236        n
237    }
238}
239
240/// `floor(log2(local XOR id))`. Identical IDs (distance 0) are Range.
241pub fn bucket_index(local: &StrongDigest, id: &StrongDigest) -> Result<usize, QdnfError> {
242    let mut i = 0usize;
243    while i < 48 {
244        let x = local.0[i] ^ id.0[i];
245        if x != 0 {
246            let from_msb = i * 8 + x.leading_zeros() as usize;
247            return Ok((BUCKET_COUNT - 1) - from_msb);
248        }
249        i += 1;
250    }
251    Err(QdnfError::Range)
252}
253
254fn xor_bytes(a: &StrongDigest, b: &StrongDigest, out: &mut [u8; 48]) {
255    let mut i = 0usize;
256    while i < 48 {
257        out[i] = a.0[i] ^ b.0[i];
258        i += 1;
259    }
260}
261
262fn dist_less(a: &[u8; 48], b: &[u8; 48]) -> bool {
263    let mut i = 0usize;
264    while i < 48 {
265        if a[i] < b[i] {
266            return true;
267        }
268        if a[i] > b[i] {
269            return false;
270        }
271        i += 1;
272    }
273    false
274}
275
276fn consider_candidate(
277    id: StrongDigest,
278    dist: &[u8; 48],
279    ids: &mut [StrongDigest; K],
280    dists: &mut [[u8; 48]; K],
281    n: &mut usize,
282) {
283    let mut i = 0usize;
284    while i < *n {
285        if keys_equal(&ids[i], &id) {
286            return;
287        }
288        i += 1;
289    }
290    if *n < K {
291        let mut pos = *n;
292        while pos > 0 && dist_less(dist, &dists[pos - 1]) {
293            ids[pos] = ids[pos - 1];
294            dists[pos] = dists[pos - 1];
295            pos -= 1;
296        }
297        ids[pos] = id;
298        dists[pos] = *dist;
299        *n += 1;
300        return;
301    }
302    if !dist_less(dist, &dists[K - 1]) {
303        return;
304    }
305    let mut pos = K - 1;
306    while pos > 0 && dist_less(dist, &dists[pos - 1]) {
307        ids[pos] = ids[pos - 1];
308        dists[pos] = dists[pos - 1];
309        pos -= 1;
310    }
311    ids[pos] = id;
312    dists[pos] = *dist;
313}
314
315#[cfg(test)]
316mod tests {
317    use super::*;
318
319    fn id_tail(last: u8) -> StrongDigest {
320        let mut k = StrongDigest::ZERO;
321        k.0[47] = last;
322        k
323    }
324
325    #[test]
326    fn insert_closest_returns_xor_nearest() {
327        let mut table = KBucketTable::new(StrongDigest::ZERO);
328        let a = id_tail(1);
329        let b = id_tail(4);
330        let c = id_tail(9);
331        table.insert(a).unwrap();
332        table.insert(c).unwrap();
333        table.insert(b).unwrap();
334        let mut out = [StrongDigest::ZERO; K];
335        let n = table.closest(&id_tail(5), &mut out).unwrap();
336        assert_eq!(n, 3);
337        assert!(keys_equal(&out[0], &b));
338        assert!(keys_equal(&out[1], &a) || keys_equal(&out[1], &c));
339    }
340
341    #[test]
342    fn iterative_lookup_finds_present_key() {
343        let mut table = KBucketTable::new(StrongDigest::ZERO);
344        let a = id_tail(1);
345        let b = id_tail(9);
346        table.bootstrap(&[a, b]).unwrap();
347        let mut out = [StrongDigest::ZERO; K];
348        let used = table.iterative_lookup(&a, 8, &mut out).unwrap();
349        assert_eq!(used, 2);
350        assert!(keys_equal(&out[0], &a));
351    }
352
353    #[test]
354    fn iterative_lookup_work_budget_exhaustion_is_budget_exhausted() {
355        let mut table = KBucketTable::new(StrongDigest::ZERO);
356        table.bootstrap(&[id_tail(1), id_tail(9)]).unwrap();
357        let mut out = [StrongDigest::ZERO; K];
358        assert_eq!(
359            table.iterative_lookup(&id_tail(1), 1, &mut out),
360            Err(QdnfError::BudgetExhausted)
361        );
362    }
363
364    #[test]
365    fn insert_fails_closed_when_k_bucket_is_full() {
366        let mut table = KBucketTable::new(StrongDigest::ZERO);
367        let mut last = 16u8;
368        while last < 24 {
369            table.insert(id_tail(last)).unwrap();
370            last = last + 1;
371        }
372        assert_eq!(table.len(), 8);
373        assert_eq!(table.insert(id_tail(24)), Err(QdnfError::Capacity));
374    }
375
376    #[test]
377    fn maintain_drops_stale_entries() {
378        let mut table = KBucketTable::new(StrongDigest::ZERO);
379        table.insert(id_tail(1)).unwrap();
380        assert_eq!(table.maintain(), 0);
381        assert_eq!(table.maintain(), 0);
382        assert_eq!(table.maintain(), 1);
383        assert_eq!(table.len(), 0);
384        table.insert(id_tail(2)).unwrap();
385        table.insert(id_tail(2)).unwrap();
386        assert_eq!(table.maintain(), 0);
387        assert_eq!(table.len(), 1);
388    }
389
390    #[test]
391    fn bucket_index_is_log2_xor_distance() {
392        assert_eq!(bucket_index(&StrongDigest::ZERO, &id_tail(1)), Ok(0));
393        assert_eq!(bucket_index(&StrongDigest::ZERO, &id_tail(16)), Ok(4));
394        assert_eq!(
395            bucket_index(&StrongDigest::ZERO, &StrongDigest::ZERO),
396            Err(QdnfError::Range)
397        );
398    }
399
400    #[test]
401    fn empty_table_lookup_is_incomplete() {
402        let table = KBucketTable::new(StrongDigest::ZERO);
403        let mut out = [StrongDigest::ZERO; 1];
404        assert_eq!(
405            table.iterative_lookup(&id_tail(1), 8, &mut out),
406            Err(QdnfError::Incomplete)
407        );
408    }
409}