Skip to main content

radixip/
engine.rs

1//! Radix tree engine implementations with different concurrency models
2
3use 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
15// ============================================================
16// STANDARD ENGINE
17// ============================================================
18
19pub 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
120// SHARDED ENGINE
121// throughput = num_shards * throughput_per_shard
122
123pub 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                 // Mask the IP to keep only prefix bits
146                let mask = if self.mask_bits >= 32 {
147                    u32::MAX
148                } else {
149                    u32::MAX << (32 - self.mask_bits)
150                };
151                // this way we isolate the ip-adress from the network prefix
152                let masked_ip = ip_u32 & mask;
153
154                 // Hash the masked IP
155                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                     // Hash only the masked prefix part
166                    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                    // Handle partial byte masking if needed
171                    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                    // Hash first 16 bytes for large prefix lengths
178                    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// ENGINE WRAPPER
249// switches between concurrency models behind one type
250
251#[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    /// `num_shards`:
263    ///   `None`      -> auto-detect from CPU cores + available memory
264    ///   `Some(1)`   -> standard (unsharded)
265    ///   `Some(n>1)` -> sharded with exactly n shards
266    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        // ART carries its own sharding implementation, handled separately.
275        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        // LockFree and Adaptive pick their own node representation;
286        // everything else uses whatever node_variant the caller passed.
287        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        // LockFree relies on lock-free nodes for its concurrency, not sharding.
296        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    // shard-count auto-detection 
325
326    /// Cores -> shards, roughly matching:
327    /// Dev(2c)->1-2, Small(4c)->4-8, Medium(8c)->16-32, Large(16c)->32-64, Enterprise(32c)->64-128
328    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                // Take the more conservative bound so we don't over-shard
339                // (and thus over-allocate) on memory-constrained boxes.
340                cpu_based.min(mem_based)
341            }
342        }
343    }
344
345    /// `breakpoints` is `[(max_cpus, shards), ...]` ascending; `default`
346    /// applies once core count exceeds every breakpoint.
347    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    /// Only budget 75% of currently *available* RAM — leave headroom for
371    /// the OS, allocator, and other processes rather than assuming the
372    /// engine owns the whole machine.
373    fn usable_memory_bytes() -> u64 {
374        Self::detect_available_memory().saturating_mul(3) / 4
375    }
376
377    /// Cross-platform available memory via `sysinfo` (Linux/macOS/Windows/BSD/...).
378    /// Deliberately uses `available_memory`, not `total_memory` — total tells
379    /// you nothing about what's actually free to allocate right now, and
380    /// `System::new()` + `refresh_memory()` avoids pulling in CPU/process/disk
381    /// data we don't need just to answer this one question.
382    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}