Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_o3db_sync/tests/kademlia_routing.rs

7.5 KiB, 12 runs

created by r1870400018:11196, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Integration tests for the Kademlia routing-table primitive.
2//!
3//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
4//! Anthropic Claude
5#![cfg(feature = "dist")]
6
7use oxedyne_fe2o3_core::prelude::*;
8
9use oxedyne_fe2o3_o3db_sync::kademlia::{
10 contact::Contact,
11 id::{
12 Distance,
13 ID_BITS,
14 ID_LEN,
15 NodeId,
16 },
17 kmap::{
18 InsertOutcome,
19 KMap,
20 },
21 table::RoutingTable,
22};
23
24use std::net::SocketAddr;
25
26
27/// The bit is counted from the LSB.
28fn id_with_bit(bit: usize) -> NodeId {
29 let mut bytes = [0u8; ID_LEN];
30 let byte_from_msb = ID_LEN - 1 - bit / 8;
31 let bit_in_byte = bit % 8;
32 bytes[byte_from_msb] = 1u8 << bit_in_byte;
33 NodeId::from_bytes(bytes)
34}
35
36fn id_from_u64(suffix: u64) -> NodeId {
37 let mut bytes = [0u8; ID_LEN];
38 bytes[ID_LEN - 8 ..].copy_from_slice(&suffix.to_be_bytes());
39 NodeId::from_bytes(bytes)
40}
41
42fn loopback(port: u16) -> SocketAddr {
43 let s = format!("127.0.0.1:{}", port);
44 s.parse().expect("test loopback addr parses")
45}
46
47
48#[test]
49fn xor_distance_is_self_inverse() -> Outcome<()> {
50 let a = id_from_u64(0xdead_beef_cafe_babe);
51 let b = id_from_u64(0x0123_4567_89ab_cdef);
52 let d1 = a.distance(&b);
53 let d2 = b.distance(&a);
54 assert_eq!(d1, d2);
55 Ok(())
56}
57
58#[test]
59fn xor_distance_to_self_is_zero() -> Outcome<()> {
60 let a = id_from_u64(42);
61 let d = a.distance(&a);
62 assert!(d.is_zero());
63 assert_eq!(d.bucket_index(), None);
64 assert_eq!(a.bucket_index(&a), None);
65 Ok(())
66}
67
68#[test]
69fn bucket_index_matches_bit_position() -> Outcome<()> {
70 let me = NodeId::from_bytes([0u8; ID_LEN]);
71 for bit in 0..ID_BITS {
72 let peer = id_with_bit(bit);
73 let idx = res!(me.bucket_index(&peer).ok_or_else(|| err!(
74 "bit-exact distance unexpectedly zero for bit {}", bit;
75 Bug, Unexpected)));
76 assert_eq!(idx, bit,
77 "bit {} expected bucket {}, got {}", bit, bit, idx);
78 }
79 Ok(())
80}
81
82#[test]
83fn distance_ord_is_byte_wise_unsigned() -> Outcome<()> {
84 let mut low = [0u8; ID_LEN];
85 low[ID_LEN - 1] = 1;
86 let mut high = [0u8; ID_LEN];
87 high[0] = 1;
88 let d_low = Distance(low);
89 let d_high = Distance(high);
90 assert!(d_low < d_high);
91 Ok(())
92}
93
94#[test]
95fn kmap_inserts_then_refreshes() -> Outcome<()> {
96 let mut map = res!(KMap::new(3));
97 let id_a = id_from_u64(1);
98 let id_b = id_from_u64(2);
99
100 let c_a = Contact::new(id_a, vec![loopback(1)]);
101 let c_b = Contact::new(id_b, vec![loopback(2)]);
102
103 assert!(matches!(map.insert(c_a.clone()), InsertOutcome::Inserted));
104 assert!(matches!(map.insert(c_b.clone()), InsertOutcome::Inserted));
105 assert!(matches!(map.insert(c_a.clone()), InsertOutcome::Refreshed));
106 // After refresh, `a` is MRU (front), `b` is LRU (back).
107 let ordered: Vec<_> = map.iter().map(|c| c.node_id).collect();
108 assert_eq!(ordered, vec![id_a, id_b]);
109 Ok(())
110}
111
112#[test]
113fn kmap_full_surfaces_lru_candidate() -> Outcome<()> {
114 let mut map = res!(KMap::new(2));
115 let id_a = id_from_u64(1);
116 let id_b = id_from_u64(2);
117 let id_c = id_from_u64(3);
118
119 assert!(matches!(
120 map.insert(Contact::new(id_a, vec![loopback(1)])),
121 InsertOutcome::Inserted));
122 assert!(matches!(
123 map.insert(Contact::new(id_b, vec![loopback(2)])),
124 InsertOutcome::Inserted));
125
126 let outcome = map.insert(Contact::new(id_c, vec![loopback(3)]));
127 let (candidate_id, pending_id) = match outcome {
128 InsertOutcome::Full { candidate, pending } => (candidate.node_id, pending.node_id),
129 other => panic!("expected Full outcome, got {:?}", other),
130 };
131 assert_eq!(candidate_id, id_a, "LRU after two inserts is `a`");
132 assert_eq!(pending_id, id_c);
133 Ok(())
134}
135
136#[test]
137fn kmap_keep_lru_retains_on_live_probe() -> Outcome<()> {
138 let mut map = res!(KMap::new(2));
139 let id_a = id_from_u64(1);
140 let id_b = id_from_u64(2);
141 let _ = map.insert(Contact::new(id_a, vec![loopback(1)]));
142 let _ = map.insert(Contact::new(id_b, vec![loopback(2)]));
143 map.keep_lru(100);
144 // `a` was LRU; touching moves it to MRU.
145 let ordered: Vec<_> = map.iter().map(|c| c.node_id).collect();
146 assert_eq!(ordered, vec![id_a, id_b]);
147 let refreshed = res!(map.get(&id_a).ok_or_else(|| err!(
148 "`a` missing after keep_lru"; Bug, Unexpected)));
149 assert_eq!(refreshed.last_seen, 100);
150 Ok(())
151}
152
153#[test]
154fn kmap_evict_and_insert_drops_dead_lru() -> Outcome<()> {
155 let mut map = res!(KMap::new(2));
156 let id_a = id_from_u64(1);
157 let id_b = id_from_u64(2);
158 let id_c = id_from_u64(3);
159 let _ = map.insert(Contact::new(id_a, vec![loopback(1)]));
160 let _ = map.insert(Contact::new(id_b, vec![loopback(2)]));
161
162 let evicted = map.evict_and_insert(Contact::new(id_c, vec![loopback(3)]));
163 let evicted = res!(evicted.ok_or_else(|| err!(
164 "eviction did not return a prior contact"; Bug, Unexpected)));
165 assert_eq!(evicted.node_id, id_a);
166 let ordered: Vec<_> = map.iter().map(|c| c.node_id).collect();
167 assert_eq!(ordered, vec![id_c, id_b]);
168 Ok(())
169}
170
171#[test]
172fn routing_table_rejects_self_insertion() -> Outcome<()> {
173 let me = id_from_u64(42);
174 let mut table = res!(RoutingTable::new(me, 20));
175 let outcome = res!(table.insert(Contact::new(me, vec![loopback(1)])));
176 assert!(outcome.is_none());
177 assert!(table.is_empty());
178 Ok(())
179}
180
181#[test]
182fn routing_table_routes_by_bucket() -> Outcome<()> {
183 let me = NodeId::from_bytes([0u8; ID_LEN]);
184 let mut table = res!(RoutingTable::new(me, 20));
185 // Insert three peers into three distinct buckets.
186 for bit in [3usize, 100, 255] {
187 let peer_id = id_with_bit(bit);
188 let outcome = res!(table.insert(
189 Contact::new(peer_id, vec![loopback(bit as u16 + 1)])));
190 assert!(outcome.is_none(),
191 "bit {} expected trivial insert, got {:?}", bit, outcome);
192 }
193 assert_eq!(table.len(), 3);
194 Ok(())
195}
196
197#[test]
198fn k_closest_returns_ascending_distance() -> Outcome<()> {
199 let me = NodeId::from_bytes([0u8; ID_LEN]);
200 let mut table = res!(RoutingTable::new(me, 20));
201 // Sprinkle a handful of peers across buckets.
202 for bit in [1usize, 2, 4, 8, 16, 32, 64, 128] {
203 let peer = id_with_bit(bit);
204 let _ = res!(table.insert(Contact::new(peer, vec![loopback(bit as u16 + 1)])));
205 }
206 // Target is a single bit at position 3 -- closest match is bit-2 (distance
207 // differs in bits 2 and 3, XOR = 0x0C), then bit-4 (XOR = 0x18), etc.
208 let target = id_with_bit(3);
209 let closest = table.k_closest(&target, 3);
210 assert_eq!(closest.len(), 3);
211 // Verify ascending distance.
212 let mut prev = closest[0].node_id.distance(&target);
213 for c in &closest[1..] {
214 let d = c.node_id.distance(&target);
215 assert!(prev <= d, "k_closest must return ascending distance");
216 prev = d;
217 }
218 Ok(())
219}
220
221#[test]
222fn k_closest_caps_at_want() -> Outcome<()> {
223 let me = NodeId::from_bytes([0u8; ID_LEN]);
224 let mut table = res!(RoutingTable::new(me, 20));
225 for suffix in 1u64..=10 {
226 let peer = id_from_u64(suffix);
227 let _ = res!(table.insert(
228 Contact::new(peer, vec![loopback(suffix as u16)])));
229 }
230 let target = id_from_u64(5);
231 assert_eq!(table.k_closest(&target, 0).len(), 0);
232 assert_eq!(table.k_closest(&target, 3).len(), 3);
233 assert_eq!(table.k_closest(&target, 100).len(), 10);
234 Ok(())
235}
236
237#[test]
238fn two_peer_mutual_discovery() -> Outcome<()> {
239 // A tiny in-process two-peer scenario: each learns about the other and
240 // a k_closest lookup for the remote's id returns the remote contact.
241 let id_a = id_from_u64(0xaaaa_aaaa_aaaa_aaaa);
242 let id_b = id_from_u64(0xbbbb_bbbb_bbbb_bbbb);
243
244 let mut table_a = res!(RoutingTable::new(id_a, 20));
245 let mut table_b = res!(RoutingTable::new(id_b, 20));
246
247 let _ = res!(table_a.insert(Contact::new(id_b, vec![loopback(60001)])));
248 let _ = res!(table_b.insert(Contact::new(id_a, vec![loopback(60000)])));
249
250 let from_a = table_a.k_closest(&id_b, 1);
251 let from_b = table_b.k_closest(&id_a, 1);
252 assert_eq!(from_a.len(), 1);
253 assert_eq!(from_a[0].node_id, id_b);
254 assert_eq!(from_b.len(), 1);
255 assert_eq!(from_b[0].node_id, id_a);
256 Ok(())
257}