1use std::sync::atomic::{AtomicU64, Ordering};
26
27use spider_route::{registrable_domain, AttemptOutcome, SiteMemory, StatusClass};
28use url::Url;
29
30pub const DEFAULT_CAPACITY: usize = 256;
36
37const MIN_CAPACITY: usize = 16;
39
40const MAX_CAPACITY: usize = 65_536;
43
44const DECAY: f32 = 0.25;
49
50#[derive(Debug)]
55pub struct SiteMemoryStore {
56 slots: Box<[Slot]>,
57}
58
59#[derive(Debug, Default)]
65struct Slot {
66 key: AtomicU64,
67 packed: AtomicU64,
68}
69
70impl Default for SiteMemoryStore {
71 fn default() -> SiteMemoryStore {
72 SiteMemoryStore::new(DEFAULT_CAPACITY)
73 }
74}
75
76impl SiteMemoryStore {
77 pub fn new(capacity: usize) -> SiteMemoryStore {
84 if capacity == 0 {
85 return SiteMemoryStore {
86 slots: Box::default(),
87 };
88 }
89 let wanted = capacity.clamp(MIN_CAPACITY, MAX_CAPACITY);
90 let slots = wanted.next_power_of_two().min(MAX_CAPACITY);
91 let mut table = Vec::with_capacity(slots);
92 table.resize_with(slots, Slot::default);
93
94 SiteMemoryStore {
95 slots: table.into_boxed_slice(),
96 }
97 }
98
99 pub fn capacity(&self) -> usize {
102 self.slots.len()
103 }
104
105 pub fn len(&self) -> usize {
110 self.slots
111 .iter()
112 .filter(|slot| slot.key.load(Ordering::Relaxed) != 0)
113 .count()
114 }
115
116 pub fn is_empty(&self) -> bool {
118 self.len() == 0
119 }
120
121 pub fn get(&self, url: &Url) -> Option<SiteMemory> {
126 if self.slots.is_empty() {
127 return None;
128 }
129 let key = key_of(url)?;
130 let slot = self.slot(key)?;
131
132 if slot.key.load(Ordering::Relaxed) != key {
133 return None;
134 }
135
136 let memory = unpack(slot.packed.load(Ordering::Relaxed));
137 if memory.observations == 0 {
138 None
139 } else {
140 Some(memory)
141 }
142 }
143
144 pub fn observe(&self, url: &Url, outcome: &AttemptOutcome) {
150 self.update(url, |memory| fold(memory, outcome));
151 }
152
153 pub fn remember(&self, url: &Url, memory: SiteMemory) {
158 self.update(url, |_| memory);
159 }
160
161 pub fn clear(&self) {
163 for slot in &self.slots {
164 slot.key.store(0, Ordering::Relaxed);
165 slot.packed.store(0, Ordering::Relaxed);
166 }
167 }
168
169 fn update(&self, url: &Url, next: impl Fn(SiteMemory) -> SiteMemory) {
171 if self.slots.is_empty() {
172 return;
173 }
174 let Some(key) = key_of(url) else {
175 return;
176 };
177 let Some(slot) = self.slot(key) else {
178 return;
179 };
180
181 if slot.key.load(Ordering::Relaxed) != key {
187 slot.key.store(key, Ordering::Relaxed);
188 slot.packed.store(0, Ordering::Relaxed);
189 }
190
191 let mut current = slot.packed.load(Ordering::Relaxed);
192 loop {
193 let packed = pack(next(unpack(current)));
194 match slot.packed.compare_exchange_weak(
195 current,
196 packed,
197 Ordering::Relaxed,
198 Ordering::Relaxed,
199 ) {
200 Ok(_) => return,
201 Err(seen) => current = seen,
202 }
203 }
204 }
205
206 fn slot(&self, key: u64) -> Option<&Slot> {
208 let mask = self.slots.len().saturating_sub(1);
210 self.slots.get((key as usize) & mask)
211 }
212}
213
214fn key_of(url: &Url) -> Option<u64> {
220 let name = registrable_domain(url)?;
221 let hashed = fnv1a(name.as_bytes());
222
223 Some(if hashed == 0 { 1 } else { hashed })
225}
226
227fn fnv1a(bytes: &[u8]) -> u64 {
233 let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
234 for byte in bytes {
235 hash ^= u64::from(byte.to_ascii_lowercase());
236 hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
237 }
238 hash
239}
240
241fn fold(memory: SiteMemory, outcome: &AttemptOutcome) -> SiteMemory {
243 let scored = if outcome.success { 1.0 } else { 0.0 };
244 let success_rate = if memory.observations == 0 {
245 scored
246 } else {
247 memory.success_rate + (scored - memory.success_rate) * DECAY
248 };
249
250 let streak = match (outcome.success, memory.streak) {
253 (true, held) if held > 0 => held.saturating_add(1),
254 (true, _) => 1,
255 (false, held) if held < 0 => held.saturating_sub(1),
256 (false, _) => -1,
257 };
258
259 SiteMemory {
260 observations: memory.observations.saturating_add(1),
261 success_rate: success_rate.clamp(0.0, 1.0),
262 streak,
263 last_status: outcome.status,
264 }
265}
266
267const RATE_STEPS: f32 = u16::MAX as f32;
269
270fn pack(memory: SiteMemory) -> u64 {
276 let observations = u64::from(memory.observations.min(u32::from(u16::MAX)) as u16);
277 let rate = u64::from((memory.success_rate.clamp(0.0, 1.0) * RATE_STEPS).round() as u16);
278 let streak = u64::from(memory.streak as u16);
279 let status = u64::from(status_code(memory.last_status));
280
281 observations | (rate << 16) | (streak << 32) | (status << 48)
282}
283
284fn unpack(packed: u64) -> SiteMemory {
286 let observations = (packed & 0xffff) as u32;
287 let rate = ((packed >> 16) & 0xffff) as u16;
288 let streak = ((packed >> 32) & 0xffff) as u16 as i16;
289 let status = ((packed >> 48) & 0xff) as u8;
290
291 SiteMemory {
292 observations,
293 success_rate: f32::from(rate) / RATE_STEPS,
294 streak,
295 last_status: status_from_code(status),
296 }
297}
298
299fn status_code(status: StatusClass) -> u8 {
305 match status {
306 StatusClass::Ok => 1,
307 StatusClass::Empty => 2,
308 StatusClass::BadRequest => 3,
309 StatusClass::NeedsLogin => 4,
310 StatusClass::Blocked => 5,
311 StatusClass::NotFound => 6,
312 StatusClass::RateLimited => 7,
313 StatusClass::ServerError => 8,
314 _ => 0,
317 }
318}
319
320fn status_from_code(code: u8) -> StatusClass {
322 match code {
323 1 => StatusClass::Ok,
324 2 => StatusClass::Empty,
325 3 => StatusClass::BadRequest,
326 4 => StatusClass::NeedsLogin,
327 5 => StatusClass::Blocked,
328 6 => StatusClass::NotFound,
329 7 => StatusClass::RateLimited,
330 8 => StatusClass::ServerError,
331 _ => StatusClass::Unknown,
332 }
333}
334
335#[cfg(test)]
336mod tests {
337 #![allow(
340 clippy::unwrap_used,
341 clippy::expect_used,
342 clippy::panic,
343 clippy::unreachable,
344 clippy::indexing_slicing,
345 clippy::string_slice
346 )]
347 use super::*;
348
349 fn url(raw: &str) -> Url {
350 Url::parse(raw).expect("a url")
351 }
352
353 #[test]
354 fn a_site_is_remembered_and_an_unseen_one_is_not() {
355 let store = SiteMemoryStore::default();
356 let seen = url("https://example.com/a");
357
358 assert!(store.get(&seen).is_none());
359 assert!(store.is_empty());
360
361 store.observe(&seen, &AttemptOutcome::failed(StatusClass::Blocked, 900));
362 let memory = store.get(&seen).expect("a record");
363
364 assert_eq!(memory.observations, 1);
365 assert_eq!(memory.streak, -1);
366 assert_eq!(memory.last_status, StatusClass::Blocked);
367 assert_eq!(memory.success_rate, 0.0);
368 assert!(store.get(&url("https://other.example.org/a")).is_none());
369 }
370
371 #[test]
372 fn every_host_under_one_name_shares_a_record() {
373 let store = SiteMemoryStore::default();
374 store.observe(
375 &url("https://www.example.com/a"),
376 &AttemptOutcome::failed(StatusClass::Blocked, 100),
377 );
378 store.observe(
379 &url("https://api.example.com/b"),
380 &AttemptOutcome::failed(StatusClass::Blocked, 100),
381 );
382
383 let memory = store.get(&url("https://example.com/c")).expect("a record");
384 assert_eq!(memory.observations, 2);
385 assert_eq!(memory.streak, -2);
386 assert_eq!(store.len(), 1);
387 }
388
389 #[test]
390 fn a_streak_turns_around_rather_than_counting_through_zero() {
391 let store = SiteMemoryStore::default();
392 let site = url("https://example.com/a");
393
394 for _ in 0..3 {
395 store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
396 }
397 assert_eq!(store.get(&site).expect("a record").streak, -3);
398
399 store.observe(&site, &AttemptOutcome::ok(2_000, 10));
400 let memory = store.get(&site).expect("a record");
401 assert_eq!(memory.streak, 1);
402 assert_eq!(memory.observations, 4);
403 assert!(memory.success_rate > 0.0);
404 }
405
406 #[test]
407 fn the_table_never_grows_past_its_capacity() {
408 let store = SiteMemoryStore::new(64);
409 assert_eq!(store.capacity(), 64);
410
411 for n in 0..5_000 {
412 let site = url(&format!("https://site-{n}.example{n}.com/a"));
413 store.observe(&site, &AttemptOutcome::ok(1_000, 20));
414 }
415
416 assert!(
417 store.len() <= store.capacity(),
418 "{} records in {} slots",
419 store.len(),
420 store.capacity()
421 );
422 assert!(store.len() > 16, "only {} slots filled", store.len());
424 }
425
426 #[test]
427 fn a_capacity_is_rounded_up_and_held_inside_its_limits() {
428 assert_eq!(SiteMemoryStore::new(1).capacity(), MIN_CAPACITY);
429 assert_eq!(SiteMemoryStore::new(100).capacity(), 128);
430 assert_eq!(SiteMemoryStore::new(usize::MAX).capacity(), MAX_CAPACITY);
431 }
432
433 #[test]
434 fn zero_capacity_disables_site_memory() {
435 let store = SiteMemoryStore::new(0);
436 let site = url("https://example.com/a");
437 assert_eq!(store.capacity(), 0);
438 store.observe(&site, &AttemptOutcome::failed(StatusClass::Blocked, 10));
439 store.remember(
440 &site,
441 SiteMemory {
442 observations: 9,
443 success_rate: 0.0,
444 streak: -9,
445 last_status: StatusClass::Blocked,
446 },
447 );
448 assert!(store.get(&site).is_none());
449 assert!(store.is_empty());
450 store.clear();
451 assert_eq!(store.capacity(), 0);
452 }
453
454 #[test]
455 fn a_record_survives_the_trip_through_one_word() {
456 let cases = [
457 SiteMemory::cold(),
458 SiteMemory {
459 observations: 12,
460 success_rate: 0.5,
461 streak: -3,
462 last_status: StatusClass::Blocked,
463 },
464 SiteMemory {
465 observations: u32::MAX,
466 success_rate: 1.0,
467 streak: i16::MAX,
468 last_status: StatusClass::RateLimited,
469 },
470 SiteMemory {
471 observations: 1,
472 success_rate: 0.0,
473 streak: i16::MIN,
474 last_status: StatusClass::Empty,
475 },
476 ];
477
478 for memory in cases {
479 let read = unpack(pack(memory));
480 assert_eq!(read.streak, memory.streak, "{memory:?}");
481 assert_eq!(read.last_status, memory.last_status, "{memory:?}");
482 assert_eq!(
483 read.observations,
484 memory.observations.min(u32::from(u16::MAX)),
485 "{memory:?}"
486 );
487 assert!(
488 (read.success_rate - memory.success_rate).abs() < 0.001,
489 "{memory:?} came back at {}",
490 read.success_rate
491 );
492 }
493 }
494
495 #[test]
496 fn a_literal_address_is_not_a_site_to_remember() {
497 let store = SiteMemoryStore::default();
498 let literal = url("http://192.0.2.1/status");
499
500 store.observe(&literal, &AttemptOutcome::ok(10, 10));
501 assert!(store.get(&literal).is_none());
502 assert!(store.is_empty());
503 }
504
505 #[test]
506 fn a_record_can_be_written_directly_and_cleared() {
507 let store = SiteMemoryStore::default();
508 let site = url("https://example.com/a");
509
510 store.remember(
511 &site,
512 SiteMemory {
513 observations: 9,
514 success_rate: 0.1,
515 streak: -4,
516 last_status: StatusClass::Blocked,
517 },
518 );
519 assert_eq!(store.get(&site).expect("a record").observations, 9);
520
521 store.clear();
522 assert!(store.get(&site).is_none());
523 }
524
525 #[test]
526 fn records_from_many_threads_all_land() {
527 let store = std::sync::Arc::new(SiteMemoryStore::default());
528 let site = url("https://example.com/a");
529
530 std::thread::scope(|scope| {
531 for _ in 0..4 {
532 let store = std::sync::Arc::clone(&store);
533 let site = site.clone();
534 scope.spawn(move || {
535 for _ in 0..50 {
536 store.observe(&site, &AttemptOutcome::ok(100, 10));
537 }
538 });
539 }
540 });
541
542 assert_eq!(store.get(&site).expect("a record").observations, 200);
543 }
544}