1use std::{
35 hash::{BuildHasherDefault, Hasher},
36 sync::atomic::{AtomicUsize, Ordering},
37 time::{Duration, Instant},
38};
39
40use hopr_api::types::internal::prelude::HoprSurbId;
41use indexmap::{IndexMap, map::Entry};
42use parking_lot::Mutex;
43
44const RECORDS_PER_SHARD: usize = 4096;
47
48const MAX_SHARDS: usize = 64;
50
51const EXPIRY_SWEEP_STEPS: usize = 16;
54
55const GROWTH_DIVISOR: usize = 16;
58
59const MIN_GROWTH_STEP: usize = 16;
61
62const INDEX_BYTES_PER_RECORD: usize = (23 * (size_of::<usize>() + 1)).div_ceil(10);
71
72const SHARD_MULTIPLIER: u64 = 0x9E37_79B9_7F4A_7C15;
75
76const HASH_MULTIPLIER: u64 = 0x517C_C1B7_2722_0A95;
79const RNG_MULTIPLIER: u64 = 0x2545_F491_4F6C_DD1D;
80
81#[derive(Debug, Clone, Copy)]
83struct Slot<V> {
84 value: V,
85 written: Instant,
86}
87
88#[allow(dead_code)]
91struct EntryLayout<V> {
92 hash: usize,
93 key: HoprSurbId,
94 slot: Slot<V>,
95}
96
97pub const fn record_bytes<V>() -> usize {
104 let entry = size_of::<EntryLayout<V>>();
105 entry + entry.div_ceil(GROWTH_DIVISOR) + INDEX_BYTES_PER_RECORD
106}
107
108#[derive(Default)]
112struct IdHasher(u64);
113
114impl IdHasher {
115 fn fold(&mut self, word: u64) {
116 self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(HASH_MULTIPLIER);
117 }
118}
119
120impl Hasher for IdHasher {
121 fn write(&mut self, bytes: &[u8]) {
122 for chunk in bytes.chunks(size_of::<u64>()) {
123 let mut word = [0u8; size_of::<u64>()];
124 word[..chunk.len()].copy_from_slice(chunk);
125 self.fold(u64::from_le_bytes(word));
126 }
127 }
128
129 fn write_usize(&mut self, length: usize) {
130 self.fold(length as u64);
131 }
132
133 fn finish(&self) -> u64 {
134 self.0 ^ (self.0 >> 32)
136 }
137}
138
139struct Shard<V> {
141 entries: IndexMap<HoprSurbId, Slot<V>, BuildHasherDefault<IdHasher>>,
142 rng: u64,
143}
144
145impl<V> Shard<V> {
146 fn next_random(&mut self) -> u64 {
148 let mut x = self.rng;
149 x ^= x >> 12;
150 x ^= x << 25;
151 x ^= x >> 27;
152 self.rng = x;
153 x.wrapping_mul(RNG_MULTIPLIER)
154 }
155
156 fn random_below(&mut self, len: usize) -> usize {
158 ((u128::from(self.next_random()) * len as u128) >> u64::BITS) as usize
159 }
160
161 fn make_room(&mut self, capacity: usize) {
167 let len = self.entries.len();
168 if len >= self.entries.capacity() {
169 let step = (len / GROWTH_DIVISOR).max(MIN_GROWTH_STEP).min(capacity - len);
170 self.entries.reserve_exact(step);
171 }
172 }
173}
174
175fn splitmix64(state: u64) -> u64 {
177 let mut z = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
178 z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
179 z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
180 z ^ (z >> 31)
181}
182
183pub struct RandomEvictionMap<V> {
186 shards: Box<[Mutex<Shard<V>>]>,
187 shard_bits: u32,
189 shard_capacity: usize,
191 next_sweep: AtomicUsize,
193}
194
195impl<V> std::fmt::Debug for RandomEvictionMap<V> {
196 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197 f.debug_struct("RandomEvictionMap")
198 .field("shards", &self.shards.len())
199 .field("shard_capacity", &self.shard_capacity)
200 .finish_non_exhaustive()
201 }
202}
203
204impl<V> RandomEvictionMap<V> {
205 pub fn new(budget_bytes: u64) -> Self {
208 let records = usize::try_from(budget_bytes / record_bytes::<V>() as u64).unwrap_or(usize::MAX);
209 Self::with_seed(records, rand::random::<u64>())
210 }
211
212 pub(crate) fn with_seed(records: usize, seed: u64) -> Self {
218 let records = records.max(1);
219 let shard_count = (1usize << (records / RECORDS_PER_SHARD).max(1).ilog2()).min(MAX_SHARDS);
220 let shard_capacity = (records / shard_count).max(1);
221 Self {
222 shards: (0..shard_count)
223 .map(|shard| {
224 Mutex::new(Shard {
225 entries: IndexMap::default(),
226 rng: splitmix64(seed.wrapping_add(shard as u64)) | 1,
227 })
228 })
229 .collect(),
230 shard_bits: shard_count.ilog2(),
231 shard_capacity,
232 next_sweep: AtomicUsize::new(0),
233 }
234 }
235
236 #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
238 pub fn capacity(&self) -> usize {
239 self.shards.len() * self.shard_capacity
240 }
241
242 fn shard_of(&self, id: &HoprSurbId) -> &Mutex<Shard<V>> {
243 let index = if self.shard_bits == 0 {
244 0
245 } else {
246 (u64::from_le_bytes(*id).wrapping_mul(SHARD_MULTIPLIER) >> (u64::BITS - self.shard_bits)) as usize
247 };
248 &self.shards[index]
249 }
250
251 pub fn insert(&self, id: HoprSurbId, value: V) -> Option<(HoprSurbId, V)> {
256 let slot = Slot {
257 value,
258 written: Instant::now(),
259 };
260 let mut shard = self.shard_of(&id).lock();
261 let full = shard.entries.len() >= self.shard_capacity;
262 match shard.entries.entry(id) {
263 Entry::Occupied(mut occupied) => {
264 occupied.insert(slot);
265 return None;
266 }
267 Entry::Vacant(_) if full => {}
268 Entry::Vacant(_) => {
269 shard.make_room(self.shard_capacity);
270 shard.entries.insert(id, slot);
271 return None;
272 }
273 }
274 let len = shard.entries.len();
275 let victim = shard.random_below(len);
276 let evicted = shard
277 .entries
278 .swap_remove_index(victim)
279 .map(|(evicted_id, evicted)| (evicted_id, evicted.value));
280 shard.entries.insert(id, slot);
281 evicted
282 }
283
284 pub fn remove(&self, id: &HoprSurbId) -> Option<V> {
286 self.shard_of(id)
287 .lock()
288 .entries
289 .swap_remove(id)
290 .map(|removed| removed.value)
291 }
292
293 pub fn update<R>(&self, id: &HoprSurbId, change: impl FnOnce(&mut V) -> R) -> Option<R> {
304 self.shard_of(id).lock().entries.get_mut(id).map(|slot| {
305 slot.written = Instant::now();
306 change(&mut slot.value)
307 })
308 }
309
310 pub fn contains_key(&self, id: &HoprSurbId) -> bool {
312 self.shard_of(id).lock().entries.contains_key(id)
313 }
314
315 #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
318 pub fn len(&self) -> usize {
319 self.shards.iter().map(|shard| shard.lock().entries.len()).sum()
320 }
321
322 #[cfg_attr(not(any(test, feature = "testing")), allow(dead_code))]
324 pub fn is_empty(&self) -> bool {
325 self.shards.iter().all(|shard| shard.lock().entries.is_empty())
326 }
327
328 pub fn for_each(&self, mut visit: impl FnMut(&HoprSurbId, &V)) {
334 for shard in &self.shards {
335 for (id, slot) in &shard.lock().entries {
336 visit(id, &slot.value);
337 }
338 }
339 }
340
341 pub fn expire_step(&self, horizon: Duration) -> usize {
348 let per_step = self.shards.len().div_ceil(EXPIRY_SWEEP_STEPS);
349 let start = self.next_sweep.fetch_add(per_step, Ordering::Relaxed);
350 let mut expired = 0;
351 for offset in 0..per_step {
352 let mut shard = self.shards[(start + offset) % self.shards.len()].lock();
353 let before = shard.entries.len();
354 shard.entries.retain(|_, slot| slot.written.elapsed() <= horizon);
355 expired += before - shard.entries.len();
356 }
357 expired
358 }
359}
360
361#[cfg(test)]
362impl<V: Clone> RandomEvictionMap<V> {
363 pub(crate) fn get(&self, id: &HoprSurbId) -> Option<V> {
365 self.shard_of(id).lock().entries.get(id).map(|slot| slot.value.clone())
366 }
367}
368
369#[cfg(test)]
370mod tests {
371 use std::sync::{Arc, Barrier};
372
373 use anyhow::Context;
374
375 use super::*;
376
377 const SEED: u64 = 0x5EED;
378
379 fn id(n: u32) -> HoprSurbId {
380 let mut id = [0u8; 8];
381 id[..4].copy_from_slice(&n.to_le_bytes());
382 id
383 }
384
385 #[test]
386 fn a_map_should_never_hold_more_than_its_capacity() {
387 let map = RandomEvictionMap::<u32>::with_seed(100, SEED);
388 for n in 0..1_000 {
389 map.insert(id(n), n);
390 assert!(map.len() <= 100, "{} records after {} inserts", map.len(), n + 1);
391 }
392 assert_eq!(100, map.len(), "and it fills up to it");
393 }
394
395 #[test]
396 fn a_sharded_map_should_never_hold_more_than_its_capacity() {
397 let map = RandomEvictionMap::<u32>::with_seed(5 * RECORDS_PER_SHARD, SEED);
398 assert!(map.shards.len() > 1, "large enough to be split");
399 assert!(map.capacity() <= 5 * RECORDS_PER_SHARD);
400 for n in 0..4 * map.capacity() as u32 {
401 map.insert(id(n), n);
402 }
403 assert!(map.len() <= map.capacity());
404 }
405
406 #[test]
407 fn the_newest_record_should_always_be_present_after_it_is_inserted() {
408 let map = RandomEvictionMap::<u32>::with_seed(8, SEED);
409 for n in 0..200 {
410 map.insert(id(n), n);
411 assert_eq!(Some(n), map.get(&id(n)), "record {n} must not be refused");
412 }
413 }
414
415 #[test]
416 fn inserting_into_a_full_map_should_return_the_evicted_record() -> anyhow::Result<()> {
417 let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
418 for n in 0..4 {
419 assert!(map.insert(id(n), n).is_none(), "nothing is evicted while there is room");
420 }
421 let (evicted_id, evicted) = map.insert(id(4), 4).context("a full map evicts")?;
422 assert_eq!(id(evicted), evicted_id);
423 assert!(!map.contains_key(&evicted_id), "and it is gone");
424 assert_eq!(4, map.len());
425 Ok(())
426 }
427
428 #[test]
429 fn replacing_a_record_should_evict_nothing() {
430 let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
431 for n in 0..4 {
432 map.insert(id(n), n);
433 }
434 assert!(map.insert(id(2), 99).is_none());
435 assert_eq!(Some(99), map.get(&id(2)));
436 assert_eq!(4, map.len());
437 }
438
439 #[test]
440 fn updating_a_removed_record_should_find_nothing_and_not_bring_it_back() {
441 let map = RandomEvictionMap::<u32>::with_seed(4, SEED);
442 map.insert(id(1), 1);
443 assert_eq!(Some(1), map.remove(&id(1)));
444 assert!(map.update(&id(1), |value| *value += 1).is_none());
445 assert!(!map.contains_key(&id(1)), "an update never inserts");
446 assert!(map.is_empty());
447
448 map.insert(id(2), 5);
449 assert_eq!(
450 Some(6),
451 map.update(&id(2), |value| {
452 *value += 1;
453 *value
454 })
455 );
456 assert_eq!(Some(6), map.get(&id(2)));
457 }
458
459 #[test]
462 fn a_record_removed_while_it_is_updated_should_never_come_back() -> anyhow::Result<()> {
463 const ROUNDS: usize = 20_000;
464 let map = Arc::new(RandomEvictionMap::<u32>::with_seed(16, SEED));
465 let barrier = Arc::new(Barrier::new(3));
466 let key = id(7);
467
468 let remover = {
469 let (map, barrier) = (map.clone(), barrier.clone());
470 std::thread::spawn(move || {
471 for _ in 0..ROUNDS {
472 barrier.wait();
473 map.remove(&key);
474 barrier.wait();
475 }
476 })
477 };
478 let updater = {
479 let (map, barrier) = (map.clone(), barrier.clone());
480 std::thread::spawn(move || {
481 for _ in 0..ROUNDS {
482 barrier.wait();
483 map.update(&key, |value| *value += 1);
484 barrier.wait();
485 }
486 })
487 };
488 for round in 0..ROUNDS {
489 map.insert(key, 0);
490 barrier.wait();
491 barrier.wait();
492 assert!(!map.contains_key(&key), "round {round}: the removed record came back");
493 }
494 remover.join().map_err(|_| anyhow::anyhow!("remover thread panicked"))?;
495 updater.join().map_err(|_| anyhow::anyhow!("updater thread panicked"))?;
496 Ok(())
497 }
498
499 #[test]
500 fn expiring_should_drop_only_the_records_past_the_horizon() {
501 const HORIZON: Duration = Duration::from_millis(20);
502 let map = RandomEvictionMap::<u32>::with_seed(16, SEED);
503 map.insert(id(1), 1);
504 map.insert(id(2), 2);
505 std::thread::sleep(2 * HORIZON);
506 map.insert(id(3), 3);
507
508 assert_eq!(2, map.expire_step(HORIZON));
509 assert!(!map.contains_key(&id(1)) && !map.contains_key(&id(2)));
510 assert!(map.contains_key(&id(3)), "a younger record stays");
511 assert_eq!(0, map.expire_step(HORIZON));
512 }
513
514 #[test]
520 fn an_update_should_restart_the_expiry_of_the_record() {
521 const HORIZON: Duration = Duration::from_secs(1);
524 let map = RandomEvictionMap::<u32>::with_seed(16, SEED);
525 map.insert(id(1), 1);
526 std::thread::sleep(HORIZON * 6 / 10);
527 assert_eq!(Some(()), map.update(&id(1), |value| *value += 1));
528 std::thread::sleep(HORIZON * 6 / 10);
530 assert_eq!(0, map.expire_step(HORIZON), "expiry counts from the update");
531 assert_eq!(Some(2), map.get(&id(1)));
532 std::thread::sleep(HORIZON * 6 / 10);
533 assert_eq!(1, map.expire_step(HORIZON), "and it expires a horizon after the update");
534 }
535
536 #[test]
537 fn expiring_should_reach_every_shard_within_a_cycle_of_steps() {
538 const HORIZON: Duration = Duration::from_millis(10);
539 let map = RandomEvictionMap::<u32>::with_seed(MAX_SHARDS * RECORDS_PER_SHARD, SEED);
540 assert_eq!(MAX_SHARDS, map.shards.len());
541 for n in 0..2_000 {
542 map.insert(id(n), n);
543 }
544 std::thread::sleep(2 * HORIZON);
545 let first = map.expire_step(HORIZON);
546 assert!(first < 2_000, "one step sweeps only part of the shards");
547 let rest: usize = (1..EXPIRY_SWEEP_STEPS).map(|_| map.expire_step(HORIZON)).sum();
548 assert_eq!(2_000, first + rest);
549 assert!(map.is_empty());
550 }
551
552 #[test]
556 fn eviction_should_not_favour_the_young_or_the_old() {
557 const N: u32 = 1_000;
558 let map = RandomEvictionMap::<u32>::with_seed(N as usize, SEED);
559 for n in 0..N {
560 map.insert(id(n), n);
561 }
562 for n in N..2 * N {
563 map.insert(id(n), n);
564 }
565 let old = (0..N).filter(|n| map.contains_key(&id(*n))).count();
566 let young = (N..2 * N).filter(|n| map.contains_key(&id(*n))).count();
567 assert_eq!(N as usize, old + young);
568 assert!((300..440).contains(&old), "{old} of the old batch survived");
570 }
571
572 #[test]
573 fn a_walk_should_visit_every_record_once() {
574 let map = RandomEvictionMap::<u32>::with_seed(2 * RECORDS_PER_SHARD, SEED);
575 for n in 0..1_000 {
576 map.insert(id(n), n);
577 }
578 let mut seen = std::collections::HashSet::new();
579 map.for_each(|id, _| assert!(seen.insert(*id)));
580 assert_eq!(1_000, seen.len());
581 }
582
583 #[test]
584 fn storage_should_grow_in_steps_and_never_past_the_capacity() {
585 const CAPACITY: usize = 1_000;
586 let map = RandomEvictionMap::<u32>::with_seed(CAPACITY, SEED);
587 assert_eq!(
588 0,
589 map.shards[0].lock().entries.capacity(),
590 "nothing is reserved up front"
591 );
592 map.insert(id(0), 0);
593 assert!(map.shards[0].lock().entries.capacity() < CAPACITY / 4);
594 for n in 1..3 * CAPACITY as u32 {
595 map.insert(id(n), n);
596 assert!(map.shards[0].lock().entries.capacity() <= CAPACITY);
597 }
598 assert_eq!(CAPACITY, map.shards[0].lock().entries.capacity());
599 }
600
601 #[test]
602 fn the_shard_count_should_follow_the_capacity() {
603 let shards = |records| RandomEvictionMap::<u32>::with_seed(records, SEED).shards.len();
604 assert_eq!(1, shards(0));
605 assert_eq!(1, shards(1));
606 assert_eq!(1, shards(2 * RECORDS_PER_SHARD - 1));
607 assert_eq!(2, shards(2 * RECORDS_PER_SHARD));
608 assert_eq!(MAX_SHARDS, shards(usize::MAX / 2));
609 }
610
611 #[test]
612 fn a_budget_should_buy_records_at_the_cost_of_its_own_type() {
613 let budget = 1_000 * record_bytes::<u64>() as u64;
614 assert_eq!(1_000, RandomEvictionMap::<u64>::new(budget).capacity());
615 assert!(record_bytes::<[u8; 512]>() > record_bytes::<u64>());
616 assert_eq!(1, RandomEvictionMap::<u64>::new(0).capacity(), "never fewer than one");
617 }
618}