1use std::net::IpAddr;
4use std::sync::{
5 Arc, RwLock,
6 atomic::{AtomicUsize, Ordering},
7};
8use sysinfo::System;
9
10use crate::traits::*;
11use crate::tree::{CompressedTree, UncompressedTree};
12use crate::types::{EngineStats, Metadata};
13use ipnetwork::IpNetwork;
14
15pub struct StandardEngine<T: RouteTree> {
20 tree: T,
21 size: AtomicUsize,
22 stats: RwLock<EngineStats>,
23}
24
25impl<T: RouteTree> StandardEngine<T> {
26 pub fn new(tree: T) -> Self {
27 Self {
28 tree,
29 size: AtomicUsize::new(0),
30 stats: RwLock::new(EngineStats::default()),
31 }
32 }
33
34 fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<(), String> {
35 let is_new = self.tree.insert(prefix, metadata)?;
36
37 if is_new {
38 self.size.fetch_add(1, Ordering::Relaxed);
39 }
40
41 let mut stats = self.stats.write().unwrap();
42 stats.inserts += 1;
43 stats.size = self.size();
44 Ok(())
45 }
46
47 fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
48 let result = self.tree.lookup(ip);
49
50 let mut stats = self.stats.write().unwrap();
51 stats.lookups += 1;
52 if result.is_some() {
53 stats.hits += 1;
54 } else {
55 stats.misses += 1;
56 }
57
58 result
59 }
60
61 fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
62 let removed = self.tree.remove(prefix);
63
64 if removed.is_some() {
65 self.size.fetch_sub(1, Ordering::Relaxed);
66 let mut stats = self.stats.write().unwrap();
67 stats.removals += 1;
68 stats.size = self.size();
69 }
70
71 removed
72 }
73
74 fn contains(&self, prefix: &IpNetwork) -> bool {
75 self.tree.contains(prefix)
76 }
77
78 fn clear(&self) {
79 self.tree.clear();
80 self.size.store(0, Ordering::Relaxed);
81 let mut stats = self.stats.write().unwrap();
82 stats.size = 0;
83 }
84
85 fn size(&self) -> usize {
86 self.size.load(Ordering::Relaxed)
87 }
88
89 fn stats(&self) -> EngineStats {
90 let mut stats = self.stats.read().unwrap().clone();
91 stats.size = self.size();
92 stats
93 }
94}
95
96impl<T: RouteTree> RadixEngine for StandardEngine<T> {
97 fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<(), String> {
98 StandardEngine::insert(self, prefix, metadata)
99 }
100 fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
101 StandardEngine::lookup(self, ip)
102 }
103 fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
104 StandardEngine::remove(self, prefix)
105 }
106 fn contains(&self, prefix: &IpNetwork) -> bool {
107 StandardEngine::contains(self, prefix)
108 }
109 fn clear(&self) {
110 StandardEngine::clear(self)
111 }
112 fn size(&self) -> usize {
113 StandardEngine::size(self)
114 }
115 fn stats(&self) -> EngineStats {
116 StandardEngine::stats(self)
117 }
118}
119
120pub struct ShardedEngine<T: RouteTree> {
124 pub shards: Vec<Arc<StandardEngine<T>>>,
125 pub num_shards: usize,
126 pub mask_bits: u8,
127}
128
129impl<T: RouteTree + Clone> ShardedEngine<T> {
130 fn new(num_shards: usize, tree: T) -> Self {
131 let shards = (0..num_shards)
132 .map(|_| Arc::new(StandardEngine::new(tree.clone())))
133 .collect();
134 Self {
135 shards,
136 num_shards,
137 mask_bits: 32,
138 }
139 }
140
141 fn get_shard(&self, ip: &IpAddr) -> usize {
142 let hash = match ip {
143 IpAddr::V4(ip) => {
144 let ip_u32 = u32::from_be_bytes(ip.octets());
145 let mask = if self.mask_bits >= 32 {
147 u32::MAX
148 } else {
149 u32::MAX << (32 - self.mask_bits)
150 };
151 let masked_ip = ip_u32 & mask;
153
154 let mut hash = 0u32;
156 for byte in masked_ip.to_be_bytes() {
157 hash = hash.wrapping_mul(31).wrapping_add(byte as u32);
158 }
159 hash as usize
160 }
161 IpAddr::V6(ip) => {
162 let bytes = ip.octets();
163 let mut hash = 0u64;
164 if self.mask_bits <= 64 {
165 let bytes_to_keep = ((self.mask_bits + 7) / 8) as usize;
167 for byte in bytes.iter().take(bytes_to_keep) {
168 hash = hash.wrapping_mul(31).wrapping_add(*byte as u64);
169 }
170 if self.mask_bits % 8 != 0 && bytes_to_keep < bytes.len() {
172 let mask = 0xFFu8 << (8 - (self.mask_bits % 8) as u8);
173 let partial_byte = bytes[bytes_to_keep] & mask;
174 hash = hash.wrapping_mul(31).wrapping_add(partial_byte as u64);
175 }
176 } else {
177 for byte in bytes.iter().take(16) {
179 hash = hash.wrapping_mul(31).wrapping_add(*byte as u64);
180 }
181 };
182 hash as usize
183 }
184 };
185 hash % self.num_shards
186 }
187}
188
189impl<T: RouteTree + Clone> RadixEngine for ShardedEngine<T> {
190 fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<(), String> {
191 for shard in &self.shards {
192 shard.insert(prefix, metadata.clone())?;
193 }
194 Ok(())
195 }
196
197 fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
198 let shard_idx = self.get_shard(ip);
199 self.shards[shard_idx].lookup(ip)
200 }
201
202 fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
203 let mut removed = None;
204 for shard in &self.shards {
205 let shard_removed = shard.remove(prefix);
206 if removed.is_none() {
207 removed = shard_removed;
208 }
209 }
210 removed
211 }
212
213 fn contains(&self, prefix: &IpNetwork) -> bool {
214 self.shards
215 .first()
216 .map(|s| s.contains(prefix))
217 .unwrap_or(false)
218 }
219
220 fn clear(&self) {
221 for shard in &self.shards {
222 shard.clear();
223 }
224 }
225
226 fn size(&self) -> usize {
227 self.shards.first().map(|s| s.size()).unwrap_or(0)
228 }
229
230 fn stats(&self) -> EngineStats {
231 let mut total = EngineStats::default();
232 for shard in &self.shards {
233 let stats = shard.stats();
234 total.lookups += stats.lookups;
235 total.hits += stats.hits;
236 total.misses += stats.misses;
237 }
238 if let Some(first) = self.shards.first() {
239 let stats = first.stats();
240 total.inserts = stats.inserts;
241 total.removals = stats.removals;
242 }
243 total.size = self.size();
244 total
245 }
246}
247
248#[derive(Clone)]
252pub enum EngineWrapper {
253 StandardUncompressed(Arc<StandardEngine<UncompressedTree>>),
254 ConcurrentUncompressed(Arc<ShardedEngine<UncompressedTree>>),
255 StandardCompressed(Arc<StandardEngine<CompressedTree>>),
256 ConcurrentCompressed(Arc<ShardedEngine<CompressedTree>>),
257 StandardART(Arc<crate::engine_art::ARTEngineAdapter>),
258 ConcurrentART(Arc<crate::engine_art::ShardedARTEngineAdapter>),
259}
260
261impl EngineWrapper {
262 pub fn new(
267 variant: EngineVariant,
268 node_variant: NodeVariant,
269 compressed: bool,
270 num_shards: Option<usize>,
271 ) -> Self {
272 let shard_count = num_shards.unwrap_or_else(|| Self::calculate_optimal_shards(&variant));
273
274 if variant == EngineVariant::ART {
276 return if shard_count > 1 {
277 EngineWrapper::ConcurrentART(Arc::new(
278 crate::engine_art::ShardedARTEngineAdapter::new(shard_count, 32, 32),
279 ))
280 } else {
281 EngineWrapper::StandardART(Arc::new(crate::engine_art::ARTEngineAdapter::new()))
282 };
283 }
284
285 let resolved_node_variant = match variant {
288 EngineVariant::LockFree if compressed => NodeVariant::LockFreeRadixNode,
289 EngineVariant::LockFree => NodeVariant::LockFreeTrieNode,
290 EngineVariant::Adaptive if compressed => NodeVariant::AtomicRadixNode,
291 EngineVariant::Adaptive => NodeVariant::AtomicTrieNode,
292 _ => node_variant,
293 };
294
295 let effective_shards = match variant {
297 EngineVariant::LockFree => 1,
298 _ => shard_count,
299 };
300
301 if compressed {
302 let tree = CompressedTree::new(resolved_node_variant);
303 if effective_shards > 1 {
304 EngineWrapper::ConcurrentCompressed(Arc::new(ShardedEngine::new(
305 effective_shards,
306 tree,
307 )))
308 } else {
309 EngineWrapper::StandardCompressed(Arc::new(StandardEngine::new(tree)))
310 }
311 } else {
312 let tree = UncompressedTree::new(resolved_node_variant);
313 if effective_shards > 1 {
314 EngineWrapper::ConcurrentUncompressed(Arc::new(ShardedEngine::new(
315 effective_shards,
316 tree,
317 )))
318 } else {
319 EngineWrapper::StandardUncompressed(Arc::new(StandardEngine::new(tree)))
320 }
321 }
322 }
323
324 fn calculate_optimal_shards(variant: &EngineVariant) -> usize {
329 match variant {
330 EngineVariant::Standard | EngineVariant::LockFree => 1,
331 EngineVariant::ART => Self::shards_from_cpu(&[(2, 2), (4, 4), (8, 8)], 16),
332 EngineVariant::Concurrent => {
333 Self::shards_from_cpu(&[(2, 2), (4, 8), (8, 16), (16, 32)], 64)
334 }
335 EngineVariant::Adaptive => {
336 let cpu_based = Self::shards_from_cpu(&[(2, 2), (4, 8), (8, 16), (16, 32)], 64);
337 let mem_based = Self::shards_from_memory();
338 cpu_based.min(mem_based)
341 }
342 }
343 }
344
345 fn shards_from_cpu(breakpoints: &[(usize, usize)], default: usize) -> usize {
348 let cpus = std::thread::available_parallelism()
349 .map(|c| c.get())
350 .unwrap_or(1);
351 breakpoints
352 .iter()
353 .find(|(max_cpus, _)| cpus <= *max_cpus)
354 .map(|(_, shards)| *shards)
355 .unwrap_or(default)
356 }
357
358 fn shards_from_memory() -> usize {
359 const MB: u64 = 1024 * 1024;
360 let usable_mb = Self::usable_memory_bytes() / MB;
361 match usable_mb {
362 0..=512 => 2,
363 513..=2048 => 8,
364 2049..=4096 => 16,
365 4097..=8192 => 32,
366 _ => 64,
367 }
368 }
369
370 fn usable_memory_bytes() -> u64 {
374 Self::detect_available_memory().saturating_mul(3) / 4
375 }
376
377 fn detect_available_memory() -> u64 {
383 let mut system = System::new();
384 system.refresh_memory();
385 system.available_memory()
386 }
387}
388
389impl RadixEngine for EngineWrapper {
390 fn insert(&self, prefix: IpNetwork, metadata: Metadata) -> Result<(), String> {
391 match self {
392 EngineWrapper::StandardUncompressed(e) => e.insert(prefix, metadata),
393 EngineWrapper::ConcurrentUncompressed(e) => e.insert(prefix, metadata),
394 EngineWrapper::StandardCompressed(e) => e.insert(prefix, metadata),
395 EngineWrapper::ConcurrentCompressed(e) => e.insert(prefix, metadata),
396 EngineWrapper::StandardART(e) => e.insert(prefix, metadata),
397 EngineWrapper::ConcurrentART(e) => e.insert(prefix, metadata),
398 }
399 }
400
401 fn lookup(&self, ip: &IpAddr) -> Option<Metadata> {
402 match self {
403 EngineWrapper::StandardUncompressed(e) => e.lookup(ip),
404 EngineWrapper::ConcurrentUncompressed(e) => e.lookup(ip),
405 EngineWrapper::StandardCompressed(e) => e.lookup(ip),
406 EngineWrapper::ConcurrentCompressed(e) => e.lookup(ip),
407 EngineWrapper::StandardART(e) => e.lookup(ip),
408 EngineWrapper::ConcurrentART(e) => e.lookup(ip),
409 }
410 }
411
412 fn remove(&self, prefix: &IpNetwork) -> Option<Metadata> {
413 match self {
414 EngineWrapper::StandardUncompressed(e) => e.remove(prefix),
415 EngineWrapper::ConcurrentUncompressed(e) => e.remove(prefix),
416 EngineWrapper::StandardCompressed(e) => e.remove(prefix),
417 EngineWrapper::ConcurrentCompressed(e) => e.remove(prefix),
418 EngineWrapper::StandardART(e) => e.remove(prefix),
419 EngineWrapper::ConcurrentART(e) => e.remove(prefix),
420 }
421 }
422
423 fn contains(&self, prefix: &IpNetwork) -> bool {
424 match self {
425 EngineWrapper::StandardUncompressed(e) => e.contains(prefix),
426 EngineWrapper::ConcurrentUncompressed(e) => e.contains(prefix),
427 EngineWrapper::StandardCompressed(e) => e.contains(prefix),
428 EngineWrapper::ConcurrentCompressed(e) => e.contains(prefix),
429 EngineWrapper::StandardART(e) => e.contains(prefix),
430 EngineWrapper::ConcurrentART(e) => e.contains(prefix),
431 }
432 }
433
434 fn clear(&self) {
435 match self {
436 EngineWrapper::StandardUncompressed(e) => e.clear(),
437 EngineWrapper::ConcurrentUncompressed(e) => e.clear(),
438 EngineWrapper::StandardCompressed(e) => e.clear(),
439 EngineWrapper::ConcurrentCompressed(e) => e.clear(),
440 EngineWrapper::StandardART(e) => e.clear(),
441 EngineWrapper::ConcurrentART(e) => e.clear(),
442 }
443 }
444
445 fn size(&self) -> usize {
446 match self {
447 EngineWrapper::StandardUncompressed(e) => e.size(),
448 EngineWrapper::ConcurrentUncompressed(e) => e.size(),
449 EngineWrapper::StandardCompressed(e) => e.size(),
450 EngineWrapper::ConcurrentCompressed(e) => e.size(),
451 EngineWrapper::StandardART(e) => e.size(),
452 EngineWrapper::ConcurrentART(e) => e.size(),
453 }
454 }
455
456 fn stats(&self) -> EngineStats {
457 match self {
458 EngineWrapper::StandardUncompressed(e) => e.stats(),
459 EngineWrapper::ConcurrentUncompressed(e) => e.stats(),
460 EngineWrapper::StandardCompressed(e) => e.stats(),
461 EngineWrapper::ConcurrentCompressed(e) => e.stats(),
462 EngineWrapper::StandardART(e) => e.stats(),
463 EngineWrapper::ConcurrentART(e) => e.stats(),
464 }
465 }
466}