qualia_core_db/net/qdnf/resolve/qsr/
kbucket.rs1use super::key::keys_equal;
9use crate::net::qdnf::errors::QdnfError;
10use crate::net::qdnf::types::StrongDigest;
11
12pub const K: usize = 8;
14pub const ALPHA: u8 = 3;
16pub const BUCKET_COUNT: usize = 384;
18pub const CONTACT_CAP: usize = 64;
20pub 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
37pub 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 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 pub const fn local_id(&self) -> StrongDigest {
61 self.local
62 }
63
64 #[inline]
65 pub const fn len(&self) -> usize {
67 self.len as usize
68 }
69
70 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 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 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 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 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
240pub 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}