diff options
Diffstat (limited to 'src/pkt')
| -rw-r--r-- | src/pkt/fake.rs | 143 | ||||
| -rw-r--r-- | src/pkt/hoptab.rs | 551 |
2 files changed, 694 insertions, 0 deletions
diff --git a/src/pkt/fake.rs b/src/pkt/fake.rs new file mode 100644 index 0000000..774642f --- /dev/null +++ b/src/pkt/fake.rs @@ -0,0 +1,143 @@ +// SPDX-FileCopyrightText: 2026 Dilluti0n <[email protected]> +// SPDX-License-Identifier: GPL-3.0-or-later + +use anyhow::Result; +use log::LogLevel; + +use crate::log; +use crate::opt; +use crate::log_println; +use crate::pkt::hoptab; + +use super::PktView; + +/// www.microsoft.com +/// Stolen from github.com/bol-van/zapret/blob/master/nfq/desync.c +const DEFAULT_FAKE_TLS_CLIENTHELLO: &'static [u8] = &[ + 0x16, 0x03, 0x01, 0x02, 0xa3, 0x01, 0x00, 0x02, 0x9f, 0x03, 0x03, 0x41, + 0x88, 0x82, 0x2d, 0x4f, 0xfd, 0x81, 0x48, 0x9e, 0xe7, 0x90, 0x65, 0x1f, + 0xba, 0x05, 0x7b, 0xff, 0xa7, 0x5a, 0xf9, 0x5b, 0x8a, 0x8f, 0x45, 0x8b, + 0x41, 0xf0, 0x3d, 0x1b, 0xdd, 0xe3, 0xf8, 0x20, 0x9b, 0x23, 0xa5, 0xd2, + 0x21, 0x1e, 0x9f, 0xe7, 0x85, 0x6c, 0xfc, 0x61, 0x80, 0x3a, 0x3f, 0xba, + 0xb9, 0x60, 0xba, 0xb3, 0x0e, 0x98, 0x27, 0x6c, 0xf7, 0x38, 0x28, 0x65, + 0x80, 0x5d, 0x40, 0x38, 0x00, 0x22, 0x13, 0x01, 0x13, 0x03, 0x13, 0x02, + 0xc0, 0x2b, 0xc0, 0x2f, 0xcc, 0xa9, 0xcc, 0xa8, 0xc0, 0x2c, 0xc0, 0x30, + 0xc0, 0x0a, 0xc0, 0x09, 0xc0, 0x13, 0xc0, 0x14, 0x00, 0x9c, 0x00, 0x9d, + 0x00, 0x2f, 0x00, 0x35, 0x01, 0x00, 0x02, 0x34, 0x00, 0x00, 0x00, 0x16, + 0x00, 0x14, 0x00, 0x00, 0x11, 0x77, 0x77, 0x77, 0x2e, 0x6d, 0x69, 0x63, + 0x72, 0x6f, 0x73, 0x6f, 0x66, 0x74, 0x2e, 0x63, 0x6f, 0x6d, 0x00, 0x17, + 0x00, 0x00, 0xff, 0x01, 0x00, 0x01, 0x00, 0x00, 0x0a, 0x00, 0x0e, 0x00, + 0x0c, 0x00, 0x1d, 0x00, 0x17, 0x00, 0x18, 0x00, 0x19, 0x01, 0x00, 0x01, + 0x01, 0x00, 0x0b, 0x00, 0x02, 0x01, 0x00, 0x00, 0x23, 0x00, 0x00, 0x00, + 0x10, 0x00, 0x0e, 0x00, 0x0c, 0x02, 0x68, 0x32, 0x08, 0x68, 0x74, 0x74, + 0x70, 0x2f, 0x31, 0x2e, 0x31, 0x00, 0x05, 0x00, 0x05, 0x01, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x22, 0x00, 0x0a, 0x00, 0x08, 0x04, 0x03, 0x05, 0x03, + 0x06, 0x03, 0x02, 0x03, 0x00, 0x12, 0x00, 0x00, 0x00, 0x33, 0x00, 0x6b, + 0x00, 0x69, 0x00, 0x1d, 0x00, 0x20, 0x69, 0x15, 0x16, 0x29, 0x6d, 0xad, + 0xd5, 0x68, 0x88, 0x27, 0x2f, 0xde, 0xaf, 0xac, 0x3c, 0x4c, 0xa4, 0xe4, + 0xd8, 0xc8, 0xfb, 0x41, 0x87, 0xf4, 0x76, 0x4e, 0x0e, 0xfa, 0x64, 0xc4, + 0xe9, 0x29, 0x00, 0x17, 0x00, 0x41, 0x04, 0xfe, 0x62, 0xb9, 0x08, 0xc8, + 0xc3, 0x2a, 0xb9, 0x87, 0x37, 0x84, 0x42, 0x6b, 0x5c, 0xcd, 0xc9, 0xca, + 0x62, 0x38, 0xd3, 0xd9, 0x99, 0x8a, 0xc4, 0x2d, 0xc6, 0xd0, 0xa3, 0x60, + 0xb2, 0x12, 0x54, 0x41, 0x8e, 0x52, 0x5e, 0xe3, 0xab, 0xf9, 0xc2, 0x07, + 0x81, 0xdc, 0xf8, 0xf2, 0x6a, 0x91, 0x40, 0x2f, 0xcb, 0xa4, 0xff, 0x6f, + 0x24, 0xc7, 0x4d, 0x77, 0x77, 0x2d, 0x6f, 0xe0, 0x77, 0xaa, 0x92, 0x00, + 0x2b, 0x00, 0x05, 0x04, 0x03, 0x04, 0x03, 0x03, 0x00, 0x0d, 0x00, 0x18, + 0x00, 0x16, 0x04, 0x03, 0x05, 0x03, 0x06, 0x03, 0x08, 0x04, 0x08, 0x05, + 0x08, 0x06, 0x04, 0x01, 0x05, 0x01, 0x06, 0x01, 0x02, 0x03, 0x02, 0x01, + 0x00, 0x2d, 0x00, 0x02, 0x01, 0x01, 0x00, 0x1c, 0x00, 0x02, 0x40, 0x01, + 0x00, 0x1b, 0x00, 0x07, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0xfe, + 0x0d, 0x01, 0x19, 0x00, 0x00, 0x01, 0x00, 0x03, 0x21, 0x00, 0x20, 0x62, + 0xe8, 0x83, 0xd8, 0x97, 0x05, 0x8a, 0xbe, 0xa1, 0xf2, 0x63, 0x4e, 0xce, + 0x93, 0x84, 0x8e, 0xcf, 0xe7, 0xdd, 0xb2, 0xe4, 0x87, 0x06, 0xac, 0x11, + 0x19, 0xbe, 0x0e, 0x71, 0x87, 0xf1, 0xa6, 0x00, 0xef, 0xd8, 0x6b, 0x27, + 0x5e, 0xc0, 0xa7, 0x5d, 0x42, 0x4e, 0x8c, 0xdc, 0xf3, 0x9f, 0x1c, 0x51, + 0x62, 0xef, 0xff, 0x5b, 0xed, 0xc8, 0xfd, 0xee, 0x6f, 0xbb, 0x88, 0x9b, + 0xb1, 0x30, 0x9c, 0x66, 0x42, 0xab, 0x0f, 0x66, 0x89, 0x18, 0x8b, 0x11, + 0xc1, 0x6d, 0xe7, 0x2a, 0xeb, 0x96, 0x3b, 0x7f, 0x52, 0x78, 0xdb, 0xf8, + 0x6d, 0x04, 0xf7, 0x95, 0x1a, 0xa8, 0xf0, 0x64, 0x52, 0x07, 0x39, 0xf0, + 0xa8, 0x1d, 0x0d, 0x16, 0x36, 0xb7, 0x18, 0x0e, 0xc8, 0x44, 0x27, 0xfe, + 0xf3, 0x31, 0xf0, 0xde, 0x8c, 0x74, 0xf5, 0xa1, 0xd8, 0x8f, 0x6f, 0x45, + 0x97, 0x69, 0x79, 0x5e, 0x2e, 0xd4, 0xb0, 0x2c, 0x0c, 0x1a, 0x6f, 0xcc, + 0xce, 0x90, 0xc7, 0xdd, 0xc6, 0x60, 0x95, 0xf3, 0xc2, 0x19, 0xde, 0x50, + 0x80, 0xbf, 0xde, 0xf2, 0x25, 0x63, 0x15, 0x26, 0x63, 0x09, 0x1f, 0xc5, + 0xdf, 0x32, 0xf5, 0xea, 0x9c, 0xd2, 0xff, 0x99, 0x4e, 0x67, 0xa2, 0xe5, + 0x1a, 0x94, 0x85, 0xe3, 0xdf, 0x36, 0xa5, 0x83, 0x4b, 0x0a, 0x1c, 0xaf, + 0xd7, 0x48, 0xc9, 0x4b, 0x8a, 0x27, 0xdd, 0x58, 0x7f, 0x95, 0xf2, 0x6b, + 0xde, 0x2b, 0x12, 0xd3, 0xec, 0x4d, 0x69, 0x37, 0x9c, 0x13, 0x9b, 0x16, + 0xb0, 0x45, 0x52, 0x38, 0x77, 0x69, 0xef, 0xaa, 0x65, 0x19, 0xbc, 0xc2, + 0x93, 0x4d, 0xb0, 0x1b, 0x7f, 0x5b, 0x41, 0xff, 0xaf, 0xba, 0x50, 0x51, + 0xc3, 0xf1, 0x27, 0x09, 0x25, 0xf5, 0x60, 0x90, 0x09, 0xb1, 0xe5, 0xc0, + 0xc7, 0x42, 0x78, 0x54, 0x3b, 0x23, 0x19, 0x7d, 0x8e, 0x72, 0x13, 0xb4, + 0xd3, 0xcd, 0x63, 0xb6, 0xc4, 0x4a, 0x28, 0x3d, 0x45, 0x3e, 0x8b, 0xdb, + 0x84, 0x4f, 0x78, 0x64, 0x30, 0x69, 0xe2, 0x1b +]; + +const AUTOTTL_DELTA: u8 = 1; + +/// Crudely infer hop from ttl +/// +/// Assume server initial TTL is one of: 64, 126, 255. +/// Pick the smallest origin that can produce the observed TTL (origin >= ttl), +/// then hops = origin - ttl. +fn infer_hops(ttl: u8) -> u8 { + let origin = if ttl <= 64 { + 64u8 + } else if ttl <= 126 { + 126u8 + } else { + 255u8 + }; + + origin - ttl +} + + +pub fn saddr_hop_put(view: &PktView) { + hoptab::put_0(view.saddr(), infer_hops(view.ttl())) +} + +fn daddr_hop(view: &PktView) -> hoptab::HopResult<u8> { + hoptab::find_0(view.daddr()) +} + +pub fn fake_clienthello( + view: &PktView, + start: u32, + end: Option<u32>, + out_buf: &mut Vec<u8> +) -> Result<()> { + + let tcp_checksum = if opt::fake_badsum() { + Some(0) + } else { + None + }; + + let ttl: u8 = if opt::fake_autottl() { + match daddr_hop(&view) { + Ok(hop) => { + let fake_ttl = hop.saturating_sub(AUTOTTL_DELTA); + log_println!(LogLevel::Debug, + "autottl: set ttl to {fake_ttl}" + ); + fake_ttl + }, + Err(e) => { + let fake_ttl = opt::fake_ttl(); + log_println!(LogLevel::Warning, + "autottl: sv_hop_find: {e}; fallback to {fake_ttl}"); + fake_ttl + } + } + } else { + opt::fake_ttl() + }; + + super::split_packet_0( + view, start, end, out_buf, + Some(DEFAULT_FAKE_TLS_CLIENTHELLO), + Some(ttl), + tcp_checksum + ) +} diff --git a/src/pkt/hoptab.rs b/src/pkt/hoptab.rs new file mode 100644 index 0000000..2ad1beb --- /dev/null +++ b/src/pkt/hoptab.rs @@ -0,0 +1,551 @@ +// SPDX-FileCopyrightText: 2026 Dilluti0n <[email protected]> +// SPDX-License-Identifier: GPL-3.0-or-later + +//! Linear probing hash table for ip-hop cache +//! +//! On inbound SYN/ACK (src port 443) from a server, infer the hop +//! count from the observed TTL via `crate::pkt::fake::infer_hops` and +//! store it with [`HopTab::put`]. Later, when sending a fake +//! ClientHello, look up the hop count by destination IP +//! [`HopTab::find_hop`] to automatically choose an appropriate TTL. +//! +//! One could consider keeping a global variable (like `current_hop`), +//! loading it when a SYN/ACK arrives, and reading it when needed. The +//! problem is that, before the ClientHello is sent after that SYN/ACK +//! (i.e., in between), a SYN/ACK from a different server may +//! arrive. To handle this, the (ip, hop) pair must be stored in an +//! appropriate data structure and looked up later. +//! +//! [`HopTab`] has capacity [`CAP`], which means that if at least +//! [`CAP`] SYN/ACKs arrive from distinct servers before the first +//! ClientHello is sent, [`HopLookupError::NotFound`] will inevitably +//! occur. (Given the size of [`CAP`], this is extremely unlikely.) +//! Also, after an entry is inserted, if [`HopTab::update`] runs at +//! least [`HopTab::STALE_AGE`] times, the entry is marked stale and +//! becomes evictable, so once the number of updates reaches +//! [`HopTab::STALE_AGE`] or more, there is a chance that +//! [`HopLookupError::NotFound`] occurs. Other than these cases, it +//! will not occur. + + +use std::fmt; +use std::net::IpAddr; +use std::sync::{Mutex, OnceLock}; +use std::net::{Ipv4Addr, Ipv6Addr}; + +use crate::log_println; +use crate::log::LogLevel; + +/// Size of [`HopTab`] +const CAP: usize = 1 << 7; // 128 + +/// 128-bit (IPv6-shaped) unified IP key for [`HopTab`] lookups (IPv4 +/// stored as ::ffff:a.b.c.d). +#[repr(C)] +#[derive(Clone, Copy, PartialEq, Eq)] +struct HopKey { + hi: u64, + lo: u64 +} + +impl HopKey { + const ZERO: Self = Self { hi: 0, lo: 0 }; + + #[inline] + fn from_ipaddr(ip: IpAddr) -> Self { + match ip { + IpAddr::V4(v4) => { + // ::ffff:a.b.c.d (IPv4-mapped IPv6) + let v4u = u32::from(v4) as u64; + Self { hi: 0, lo: (0xFFFFu64 << 32) | v4u } + } + IpAddr::V6(v6) => { + let b = v6.octets(); + let hi = u64::from_be_bytes(b[0..8].try_into().unwrap()); + let lo = u64::from_be_bytes(b[8..16].try_into().unwrap()); + Self { hi, lo } + } + } + } + + #[inline] + fn to_ipaddr(self) -> IpAddr { + // ::ffff:a.b.c.d (IPv4-mapped IPv6) + if self.hi == 0 && (self.lo >> 32) == 0x0000_FFFF { + let v4 = (self.lo & 0xFFFF_FFFF) as u32; + return IpAddr::V4(Ipv4Addr::from(v4)); + } + + let mut b = [0u8; 16]; + b[0..8].copy_from_slice(&self.hi.to_be_bytes()); + b[8..16].copy_from_slice(&self.lo.to_be_bytes()); + IpAddr::V6(Ipv6Addr::from(b)) + } +} + +#[derive(Clone, Copy)] +struct HopTabEntry { + key: HopKey, + + /// [RESERVED(32) | TS(16) | HOP(8) | STATE(8)] + /// * TS: timestamp snapshot (see [`HopTab::now`]) + /// * HOP: stored hop count + /// * STATE: [`Self::ST_OCCUPIED`], [`Self::ST_TOUCHED`] + meta: u64, +} + +impl HopTabEntry { + /// For internal use; Do not use it globally + const ST_EMPTY: u8 = 0; + const ST_OCCUPIED: u8 = 1 << 0; + + /// Entry has been touched (i.e., consumed by [`HopTab::find_hop`] + /// at least once). + /// + /// Note: "touched" does not mean "recently used, keep it". It + /// means the entry already served its purpose (consumed for Fake + /// ClientHello TTL), so it is more eligible for eviction under + /// pressure than a fresh, untouched entry. + const ST_TOUCHED: u8 = 1 << 1; + + const EMPTY: Self = Self { key: HopKey::ZERO, meta: Self::ST_EMPTY as u64}; + + const S_STATE: usize = 0; + const S_HOP: usize = 8; + const S_TS: usize = 16; + + #[inline] + fn key(&self) -> HopKey { + self.key + } + + #[inline] + fn new(key: HopKey, ts: u16, hop: u8) -> Self { + Self { + key: key, + meta: ((ts as u64) << Self::S_TS) + | ((hop as u64) << Self::S_HOP) + | ((Self::ST_OCCUPIED as u64) << Self::S_STATE) + } + } + + #[inline] + fn hop(&self) -> u8 { + (self.meta >> Self::S_HOP) as u8 + } + + #[inline] + fn state(&self) -> u8 { + (self.meta >> Self::S_STATE) as u8 + } + + #[inline] + fn has(&self, mask: u8) -> bool { + (self.state() & mask) == mask + } + + #[inline] + fn touch(&mut self) { + self.meta |= Self::ST_TOUCHED as u64; + } + + #[inline] + fn ts(&self) -> u16 { + (self.meta >> Self::S_TS) as u16 + } +} + +impl fmt::Debug for HopTabEntry { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let ip = self.key.to_ipaddr(); + let state = self.state(); + let hop = self.hop(); + let ts = self.ts(); + + write!( + f, + "HopTabEntry{{ ip={}, state=0x{:02x}, hop={}, ts={}, meta=0x{:016x} }}", + ip, state, hop, ts, self.meta + ) + } +} + +#[derive(Debug, Clone)] +pub enum HopLookupError { + NotFound { ip: IpAddr }, +} + +impl fmt::Display for HopLookupError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + HopLookupError::NotFound { ip } => write!(f, "hop not found for {ip}"), + } + } +} + +impl std::error::Error for HopLookupError {} + +pub type HopResult<T> = std::result::Result<T, HopLookupError>; + +struct HopTab<const CAP: usize> { + entries: Box<[HopTabEntry; CAP]>, + + /// Logical tick counter. + /// + /// Increments on every successful [`Self::update`] + /// (put/overwrite) and wraps via [`u16::wrapping_add`]. It is + /// ensured that at least [`CAP`] - [`Self::STALE_AGE`] entries + /// evictable. (i.e. [`HopTab`] not become corrupted.) + now: u16, +} + +/// Non-cryptographic hash using SplitMix64-style finalizer +#[inline] +fn hash(key: HopKey) -> usize { + let mut x = key.hi ^ key.lo.rotate_left(13); + x ^= x >> 30; + x = x.wrapping_mul(0xbf58476d1ce4e5b9); + x ^= x >> 27; + x = x.wrapping_mul(0x94d049bb133111eb); + x ^= x >> 31; + x as usize +} + +trait HashIdx { + /// `CAP` must be a power of two (we index via `hash & (CAP-1)`). + fn to_idx<const CAP: usize>(self) -> usize; +} + +impl HashIdx for usize { + #[inline] + fn to_idx<const CAP: usize>(self) -> usize { + self & (CAP - 1) + } +} + +#[derive(PartialEq, PartialOrd, Clone, Copy)] +enum EvictPriority { + /// Occupied && fresh && untouched + None = 0, + + /// Already consumed + Touched = 1, + Stale = 2, + Empty = 3, + + /// Same key occers + MustUpdate = 4, +} + +impl<const CAP: usize> HopTab<CAP> { + const ASSERT_CAP_POW2: () = { + assert!(CAP.is_power_of_two()); + }; + + /// To avoid the edge case where all entries become non-stale, + /// [`Self::STALE_AGE`] must be smaller than [`CAP`]. + const STALE_AGE: usize = CAP >> 1; // 64 + + fn new() -> Self { + _ = Self::ASSERT_CAP_POW2; + + Self { + entries: Box::new([HopTabEntry::EMPTY; CAP]), + now: 0, + } + } + + #[inline] + fn age(&self, entry: &HopTabEntry) -> u16 { + // Since we use u16 with wrapping_sub, the age calculation remains + // correct even when `self.now` overflows and wraps around to zero. + // This holds true as long as the temporal distance between + // `entry.ts()` and `self.now` does not exceed 2^15 (32,768). + // Given that STALE_AGE (64) << 2^15, the "stale" judgment is + // always mathematically sound. + self.now.wrapping_sub(entry.ts()) + } + + #[inline] + fn is_stale(&self, entry: &HopTabEntry) -> bool { + self.age(entry) >= Self::STALE_AGE as u16 + } + + #[inline] + fn update(&mut self, idx: usize, new: HopTabEntry) { + self.entries[idx] = new; + self.now = self.now.wrapping_add(1); + } + + #[inline] + fn evict_priority(&self, entry: &HopTabEntry) -> EvictPriority { + if !entry.has(HopTabEntry::ST_OCCUPIED) { + EvictPriority::Empty + } else if self.is_stale(entry) { + EvictPriority::Stale + } else if entry.has(HopTabEntry::ST_TOUCHED) { + EvictPriority::Touched + } else { + EvictPriority::None + } + } + + fn put(&mut self, ip: IpAddr, hop: u8) { + let key = HopKey::from_ipaddr(ip); + let entry = HopTabEntry::new(key, self.now, hop); + let start = hash(key).to_idx::<CAP>(); + + let mut victim = (0, EvictPriority::None); // (idx, priority) + + // Key must be unique in the table + for step in 0..CAP { + let idx = (start + step).to_idx::<CAP>(); + let e = self.entries[idx]; + + // Hit; must update same key (hop could be changed) + if e.key() == key && e.has(HopTabEntry::ST_OCCUPIED) { + victim = (idx, EvictPriority::MustUpdate); + #[cfg(debug_assertions)] + log_println!(LogLevel::Debug, "HopTab::put: hit {}; {:#?}", victim.0, entry); + break; + } + + let prio = self.evict_priority(&e); + + if prio > victim.1 { + victim = (idx, prio); + + if prio == EvictPriority::Empty { + #[cfg(debug_assertions)] + log_println!(LogLevel::Debug, + "HopTab::put: hit empty {}; {:#?}", victim.0, entry); + break; // linear probing; there is no key here + } + } + } + + if victim.1 > EvictPriority::None { + self.update(victim.0, entry); + #[cfg(debug_assertions)] + log_println!(LogLevel::Debug, "HopTab::put: update {} to {:#?}", victim.0, entry); + } else { + log_println!(LogLevel::Error, "HopTab::put: update fail: corrupted; {:#?}", entry); + } + } + + fn find_hop(&mut self, ip: IpAddr) -> HopResult<u8> { + let key = HopKey::from_ipaddr(ip); + let start = hash(key).to_idx::<CAP>(); + + for step in 0..CAP { + let idx = (start + step).to_idx::<CAP>(); + let e = self.entries[idx]; + + if !e.has(HopTabEntry::ST_OCCUPIED) { + break; // linear probing; there is no key here + } + + if e.key() == key { + self.entries[idx].touch(); + + #[cfg(debug_assertions)] + log_println!(LogLevel::Debug, "HopTab::find_hop: found {idx}; {:#?}", e); + return Ok(e.hop()); + } + } + + Err(HopLookupError::NotFound { ip }) + } +} + +static H_TAB: OnceLock<Mutex<HopTab<CAP>>> = OnceLock::new(); + +#[inline] +fn htab() -> std::sync::MutexGuard<'static, HopTab<CAP>> { + H_TAB.get_or_init(|| Mutex::new(HopTab::new())) + .lock() + .unwrap() +} + +pub fn put_0(ip: IpAddr, hop: u8) { + htab().put(ip, hop) +} + +pub fn find_0(ip: IpAddr) -> HopResult<u8> { + htab().find_hop(ip) +} + +// +// below are test/bench codes +// + +#[cfg(test)] +mod tests { + use super::*; + use std::fs::File; + use std::io::Read; + use std::net::{IpAddr, Ipv4Addr}; + + #[test] + fn test_hop_key_conversion() { + let ip: IpAddr = "1.2.3.4".parse().unwrap(); + let key = HopKey::from_ipaddr(ip); + assert_eq!(key.to_ipaddr(), ip); + } + + #[test] + fn test_basic_flow() { + let ip: IpAddr = "1.1.1.1".parse().unwrap(); + put_0(ip, 12); + + let result = find_0(ip).expect("cannot find {ip}"); + assert_eq!(result, 12); + } + + #[test] + fn test_not_found() { + let ip: IpAddr = "8.8.8.8".parse().unwrap(); + let result = find_0(ip); + assert!(result.is_err()); + } + + fn u32_to_ipaddr(i: u32) -> IpAddr { + IpAddr::V4(Ipv4Addr::from(i)) + } + + #[test] + fn test_full_table() { + let mut tab = HopTab::<CAP>::new(); + for i in 0..CAP { + tab.put(u32_to_ipaddr(i as u32), i as u8); + } + for i in 0..CAP { + assert_eq!(tab.find_hop(u32_to_ipaddr(i as u32)).unwrap(), i as u8); + } + } + + fn get_random(size: usize) -> Vec<u8> { + const RAND: &'static str = "/dev/urandom"; + let mut f = File::open(RAND).unwrap(); + let mut buf = vec![0u8; size]; + + f.read_exact(&mut buf).unwrap(); + + buf + } + + const ITERATIONS: usize = 1 << 19; + + fn get_random_bulk() -> Vec<u8> { + get_random(ITERATIONS * 5) + } + + fn get_iphop(raw: &Vec<u8>, idx: usize) -> (IpAddr, u8) { + let off = idx * 5; + let ip_num = u32::from_ne_bytes(raw[off..off+4].try_into().unwrap()); + + (u32_to_ipaddr(ip_num), raw[off+4]) + } + + #[test] + fn test_hoptab_stress() { + let mut tab = HopTab::<CAP>::new(); + let rand = get_random_bulk(); + + for i in 0..ITERATIONS { + let (ip, hop) = get_iphop(&rand, i); + + tab.put(ip, hop); + + assert_eq!(tab.find_hop(ip).unwrap(), hop); + } + } + + #[test] + fn test_random_cache_integrity() { + let mut tab = HopTab::<CAP>::new(); + + const SAFE_RANGE: usize = CAP - (CAP >> 1); + let rand = get_random_bulk(); + + let mut recent_data = std::collections::VecDeque::with_capacity(SAFE_RANGE); + + for i in 0..ITERATIONS { + let (ip, hop) = get_iphop(&rand, i); + + tab.put(ip, hop); + + if recent_data.len() == SAFE_RANGE { + recent_data.pop_front(); + } + recent_data.push_back((ip, hop)); + } + + for (ip, expected_hop) in recent_data { + let actual_hop = tab.find_hop(ip).expect("In-flight data should not be evicted"); + assert_eq!(actual_hop, expected_hop); + } + } + + #[test] + fn test_age_overflow_handling() { + let mut tab = HopTab::<CAP>::new(); + let ip1 = u32_to_ipaddr(1); + let ip2 = u32_to_ipaddr(2); + + tab.now = u16::MAX; + + tab.put(ip1, 10); + assert_eq!(tab.now, 0); + + tab.put(ip2, 20); + assert_eq!(tab.now, 1); + + let entry1 = tab.entries[hash(HopKey::from_ipaddr(ip1)).to_idx::<CAP>()]; + assert_eq!(tab.age(&entry1), 2); + assert!(!tab.is_stale(&entry1)); + + const DISTINCT: u32 = 3; + let ip3 = u32_to_ipaddr(DISTINCT); + + // Since there is no lookup for ip1, it is not become + // evictable by putting ip3. Use STALE_AGE - 1 because ip2 has + // been putted already. + for _ in 0..HopTab::<CAP>::STALE_AGE-1 { + tab.put(ip3, 3); + } + + assert!(tab.is_stale(&entry1)); + } +} + +#[cfg(feature = "bench")] +#[allow(unused_imports)] +pub use bench_support::reset_0; + +#[cfg(feature = "bench")] +#[allow(dead_code)] +mod bench_support { + use super::*; + + impl HopTabEntry { + #[inline] + fn clear(&mut self) { + self.meta &= (!Self::ST_OCCUPIED << Self::S_STATE) as u64; + } + } + + impl<const CAP: usize> HopTab<CAP> { + fn reset(&mut self) { + for i in 0..CAP { + self.entries[i].clear(); + } + self.now = 0; + } + } + + #[inline] + pub fn reset_0() { + htab().reset(); + } +} |