1#![forbid(unsafe_code)]
8#![allow(
9 clippy::doc_markdown,
10 clippy::missing_errors_doc,
11 clippy::module_name_repetitions,
12 reason = "HNS and DNS protocol names are intentional"
13)]
14
15use std::collections::{HashMap, VecDeque};
16use std::fmt;
17use std::hash::Hash;
18use std::num::NonZeroUsize;
19use std::time::{Duration, Instant};
20
21use hns_dns_wire::{Name, RecordType};
22use sha2::{Digest, Sha256};
23use thiserror::Error;
24
25const CACHE_KEY_DOMAIN: &[u8] = b"hns-browser-cache-key-v1";
26
27#[derive(Clone, Copy, Debug, Eq, PartialEq)]
29pub struct CacheLimits {
30 pub max_entries: usize,
32 pub max_total_value_bytes: usize,
34 pub max_value_bytes: usize,
36 pub max_positive_ttl: u32,
38 pub max_negative_ttl: u32,
40}
41
42impl Default for CacheLimits {
43 fn default() -> Self {
44 Self {
45 max_entries: 4_096,
46 max_total_value_bytes: 16 * 1024 * 1024,
47 max_value_bytes: 256 * 1024,
48 max_positive_ttl: 86_400,
49 max_negative_ttl: 3_600,
50 }
51 }
52}
53
54impl CacheLimits {
55 fn validate(self) -> Result<Self, CacheError> {
56 if self.max_entries == 0
57 || self.max_total_value_bytes == 0
58 || self.max_value_bytes == 0
59 || self.max_value_bytes > self.max_total_value_bytes
60 || self.max_positive_ttl == 0
61 || self.max_negative_ttl == 0
62 {
63 return Err(CacheError::InvalidLimits);
64 }
65 Ok(self)
66 }
67}
68
69#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
71pub struct CacheGeneration {
72 pub runtime_generation: u64,
74 pub policy_generation: u64,
76 pub chain_height: u32,
78 pub tree_root: [u8; 32],
80}
81
82impl CacheGeneration {
83 fn validate(self) -> Result<Self, CacheError> {
84 if self.runtime_generation == 0 || self.policy_generation == 0 {
85 return Err(CacheError::InvalidGeneration);
86 }
87 Ok(self)
88 }
89}
90
91#[repr(u8)]
93#[derive(Clone, Copy, Debug, Eq, PartialEq)]
94pub enum NegativeKind {
95 NameError = 0,
97 NoData = 1,
99 HnsNameAbsent = 2,
101}
102
103#[derive(Clone, Copy, Debug, Eq, PartialEq)]
105pub enum CacheDisposition {
106 Positive,
108 Negative(NegativeKind),
110}
111
112#[derive(Clone, Copy, Debug, Eq, PartialEq)]
114pub struct CacheAdmission {
115 pub value_bytes: usize,
117 pub disposition: CacheDisposition,
119 pub generation: CacheGeneration,
121 pub now: u64,
123 pub ttl_seconds: u32,
125}
126
127#[derive(Clone, Copy, Eq, Hash, PartialEq)]
129pub struct CacheKey([u8; 32]);
130
131impl CacheKey {
132 pub fn derive(
134 session_secret: &[u8; 32],
135 network_id: u8,
136 generation: CacheGeneration,
137 name: &Name,
138 record_type: RecordType,
139 ) -> Result<Self, CacheError> {
140 if session_secret == &[0; 32] {
141 return Err(CacheError::WeakSessionSecret);
142 }
143 let generation = generation.validate()?;
144 let mut wire_name = Vec::with_capacity(name.wire_len());
145 name.encode(&mut wire_name)?;
146 let mut hasher = Sha256::new();
147 hasher.update(CACHE_KEY_DOMAIN);
148 hasher.update(session_secret);
149 hasher.update([network_id]);
150 hasher.update(generation.runtime_generation.to_be_bytes());
151 hasher.update(generation.policy_generation.to_be_bytes());
152 hasher.update(generation.chain_height.to_be_bytes());
153 hasher.update(generation.tree_root);
154 hasher.update(record_type.code().to_be_bytes());
155 hasher.update(
156 u16::try_from(wire_name.len())
157 .map_err(|_| CacheError::InvalidQuery)?
158 .to_be_bytes(),
159 );
160 hasher.update(&wire_name);
161 Ok(Self(hasher.finalize().into()))
162 }
163}
164
165impl fmt::Debug for CacheKey {
166 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
167 formatter.write_str("CacheKey([redacted])")
168 }
169}
170
171#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
173pub struct CacheStats {
174 pub entries: usize,
176 pub value_bytes: usize,
178 pub hits: u64,
180 pub misses: u64,
182 pub evictions: u64,
184 pub expirations: u64,
186 pub stale_removals: u64,
188}
189
190#[derive(Clone, Debug)]
191struct Entry<Value> {
192 value: Value,
193 value_bytes: usize,
194 disposition: CacheDisposition,
195 generation: CacheGeneration,
196 expires_at: u64,
197 last_access: u64,
198}
199
200#[derive(Clone, Debug)]
202pub struct SecureCache<Value> {
203 limits: CacheLimits,
204 entries: HashMap<CacheKey, Entry<Value>>,
205 sequence: u64,
206 stats: CacheStats,
207}
208
209#[derive(Clone, Debug)]
210struct TimedEntry<Value> {
211 value: Value,
212 expires_at: Instant,
213}
214
215#[derive(Clone, Debug)]
222pub struct ExpiringLru<Key, Value> {
223 max_entries: NonZeroUsize,
224 entries: HashMap<Key, TimedEntry<Value>>,
225 order: VecDeque<Key>,
226}
227
228impl<Key, Value> ExpiringLru<Key, Value>
229where
230 Key: Clone + Eq + Hash,
231 Value: Clone,
232{
233 #[must_use]
235 pub fn new(max_entries: NonZeroUsize) -> Self {
236 Self {
237 max_entries,
238 entries: HashMap::with_capacity(max_entries.get()),
239 order: VecDeque::with_capacity(max_entries.get()),
240 }
241 }
242
243 pub fn insert(&mut self, key: Key, value: Value, ttl: Duration) -> Result<(), CacheError> {
245 if ttl.is_zero() {
246 return Err(CacheError::TtlLimit);
247 }
248 let expires_at = Instant::now()
249 .checked_add(ttl)
250 .ok_or(CacheError::TimeOverflow)?;
251 self.prune_expired();
252 self.promote(&key);
253 self.order.push_back(key.clone());
254 self.entries.insert(key, TimedEntry { value, expires_at });
255 self.evict_over_limit();
256 Ok(())
257 }
258
259 pub fn get(&mut self, key: &Key) -> Option<Value> {
261 self.prune_expired();
262 let value = self.entries.get(key).map(|entry| entry.value.clone())?;
263 self.promote(key);
264 self.order.push_back(key.clone());
265 Some(value)
266 }
267
268 pub fn len(&mut self) -> usize {
270 self.prune_expired();
271 self.entries.len()
272 }
273
274 pub fn is_empty(&mut self) -> bool {
276 self.len() == 0
277 }
278
279 pub fn clear(&mut self) {
281 self.entries.clear();
282 self.order.clear();
283 }
284
285 fn prune_expired(&mut self) {
286 let now = Instant::now();
287 self.entries.retain(|_, entry| entry.expires_at > now);
288 self.order.retain(|key| self.entries.contains_key(key));
289 }
290
291 fn evict_over_limit(&mut self) {
292 while self.entries.len() > self.max_entries.get() {
293 let Some(key) = self.order.pop_front() else {
294 break;
295 };
296 self.entries.remove(&key);
297 }
298 }
299
300 fn promote(&mut self, key: &Key) {
301 self.order.retain(|candidate| candidate != key);
302 }
303}
304
305impl<Value> SecureCache<Value> {
306 pub fn new(limits: CacheLimits) -> Result<Self, CacheError> {
308 let limits = limits.validate()?;
309 Ok(Self {
310 limits,
311 entries: HashMap::with_capacity(limits.max_entries),
312 sequence: 0,
313 stats: CacheStats::default(),
314 })
315 }
316
317 pub fn insert(
321 &mut self,
322 key: CacheKey,
323 value: Value,
324 admission: CacheAdmission,
325 ) -> Result<(), CacheError> {
326 let generation = admission.generation.validate()?;
327 let value_bytes = admission.value_bytes;
328 if value_bytes == 0
329 || value_bytes > self.limits.max_value_bytes
330 || value_bytes > self.limits.max_total_value_bytes
331 {
332 return Err(CacheError::ValueLimit);
333 }
334 let maximum_ttl = match admission.disposition {
335 CacheDisposition::Positive => self.limits.max_positive_ttl,
336 CacheDisposition::Negative(_) => self.limits.max_negative_ttl,
337 };
338 if admission.ttl_seconds == 0 || admission.ttl_seconds > maximum_ttl {
339 return Err(CacheError::TtlLimit);
340 }
341 let expires_at = admission
342 .now
343 .checked_add(u64::from(admission.ttl_seconds))
344 .ok_or(CacheError::TimeOverflow)?;
345 let sequence = self.next_sequence()?;
346 self.remove_expired(admission.now);
347 self.remove_internal(&key);
348 while self.entries.len() >= self.limits.max_entries
349 || self
350 .stats
351 .value_bytes
352 .checked_add(value_bytes)
353 .is_none_or(|bytes| bytes > self.limits.max_total_value_bytes)
354 {
355 self.evict_lru().ok_or(CacheError::ValueLimit)?;
356 }
357 self.stats.value_bytes = self
358 .stats
359 .value_bytes
360 .checked_add(value_bytes)
361 .ok_or(CacheError::ValueLimit)?;
362 self.entries.insert(
363 key,
364 Entry {
365 value,
366 value_bytes,
367 disposition: admission.disposition,
368 generation,
369 expires_at,
370 last_access: sequence,
371 },
372 );
373 self.stats.entries = self.entries.len();
374 Ok(())
375 }
376
377 pub fn get(
379 &mut self,
380 key: &CacheKey,
381 generation: CacheGeneration,
382 now: u64,
383 ) -> Result<Option<(&Value, CacheDisposition)>, CacheError> {
384 let generation = generation.validate()?;
385 let Some(metadata) = self
386 .entries
387 .get(key)
388 .map(|entry| (entry.generation, entry.expires_at, entry.disposition))
389 else {
390 self.stats.misses = self.stats.misses.saturating_add(1);
391 return Ok(None);
392 };
393 if metadata.0 != generation {
394 self.remove_internal(key);
395 self.stats.stale_removals = self.stats.stale_removals.saturating_add(1);
396 self.stats.misses = self.stats.misses.saturating_add(1);
397 return Ok(None);
398 }
399 if now >= metadata.1 {
400 self.remove_internal(key);
401 self.stats.expirations = self.stats.expirations.saturating_add(1);
402 self.stats.misses = self.stats.misses.saturating_add(1);
403 return Ok(None);
404 }
405 let sequence = self.next_sequence()?;
406 let entry = self
407 .entries
408 .get_mut(key)
409 .ok_or(CacheError::InternalInvariant)?;
410 entry.last_access = sequence;
411 self.stats.hits = self.stats.hits.saturating_add(1);
412 Ok(Some((&entry.value, metadata.2)))
413 }
414
415 pub fn clear(&mut self) {
417 self.entries.clear();
418 self.stats.entries = 0;
419 self.stats.value_bytes = 0;
420 }
421
422 pub fn remove(&mut self, key: &CacheKey) -> bool {
424 self.remove_internal(key).is_some()
425 }
426
427 #[must_use]
429 pub const fn stats(&self) -> CacheStats {
430 self.stats
431 }
432
433 #[must_use]
435 pub const fn limits(&self) -> CacheLimits {
436 self.limits
437 }
438
439 fn next_sequence(&mut self) -> Result<u64, CacheError> {
440 self.sequence = self
441 .sequence
442 .checked_add(1)
443 .ok_or(CacheError::SequenceExhausted)?;
444 Ok(self.sequence)
445 }
446
447 fn remove_expired(&mut self, now: u64) {
448 let expired = self
449 .entries
450 .iter()
451 .filter_map(|(key, entry)| (now >= entry.expires_at).then_some(*key))
452 .collect::<Vec<_>>();
453 for key in expired {
454 if self.remove_internal(&key).is_some() {
455 self.stats.expirations = self.stats.expirations.saturating_add(1);
456 }
457 }
458 }
459
460 fn evict_lru(&mut self) -> Option<()> {
461 let key = self
462 .entries
463 .iter()
464 .min_by_key(|(_, entry)| entry.last_access)
465 .map(|(key, _)| *key)?;
466 self.remove_internal(&key)?;
467 self.stats.evictions = self.stats.evictions.saturating_add(1);
468 Some(())
469 }
470
471 fn remove_internal(&mut self, key: &CacheKey) -> Option<Entry<Value>> {
472 let entry = self.entries.remove(key)?;
473 self.stats.value_bytes = self.stats.value_bytes.saturating_sub(entry.value_bytes);
474 self.stats.entries = self.entries.len();
475 Some(entry)
476 }
477}
478
479#[derive(Debug, Error)]
481#[non_exhaustive]
482pub enum CacheError {
483 #[error("DNS query encoding failed: {0}")]
485 Wire(#[from] hns_dns_wire::Error),
486 #[error("invalid cache limits")]
488 InvalidLimits,
489 #[error("invalid cache generation")]
491 InvalidGeneration,
492 #[error("cache session secret must be randomly generated")]
494 WeakSessionSecret,
495 #[error("invalid cache query identity")]
497 InvalidQuery,
498 #[error("cache value exceeds its bound")]
500 ValueLimit,
501 #[error("cache TTL exceeds its bound")]
503 TtlLimit,
504 #[error("cache expiration time overflow")]
506 TimeOverflow,
507 #[error("cache LRU sequence exhausted")]
509 SequenceExhausted,
510 #[error("cache internal invariant failed")]
512 InternalInvariant,
513}
514
515#[cfg(test)]
516#[allow(
517 clippy::unwrap_used,
518 reason = "tests fail immediately on invalid local cache fixtures"
519)]
520mod tests {
521 use super::*;
522 use std::num::NonZeroUsize;
523
524 fn cache_generation(value: u8) -> CacheGeneration {
525 CacheGeneration {
526 runtime_generation: u64::from(value),
527 policy_generation: 1,
528 chain_height: 100,
529 tree_root: [value; 32],
530 }
531 }
532
533 fn key(secret: u8, name: &str, generation: CacheGeneration) -> CacheKey {
534 CacheKey::derive(
535 &[secret; 32],
536 0,
537 generation,
538 &Name::from_ascii(name).unwrap(),
539 RecordType::Tlsa,
540 )
541 .unwrap()
542 }
543
544 #[test]
545 fn expiring_lru_rejects_zero_ttl_and_evicts_least_recently_used() {
546 let mut cache = ExpiringLru::new(NonZeroUsize::new(2).unwrap());
547 assert!(matches!(
548 cache.insert("zero", 0, Duration::ZERO),
549 Err(CacheError::TtlLimit)
550 ));
551 cache.insert("a", 1, Duration::from_secs(60)).unwrap();
552 cache.insert("b", 2, Duration::from_secs(60)).unwrap();
553 assert_eq!(cache.get(&"a"), Some(1));
554 cache.insert("c", 3, Duration::from_secs(60)).unwrap();
555
556 assert_eq!(cache.get(&"a"), Some(1));
557 assert_eq!(cache.get(&"b"), None);
558 assert_eq!(cache.get(&"c"), Some(3));
559 }
560
561 #[test]
562 fn keys_are_qname_free_session_and_generation_specific() {
563 let generation = cache_generation(1);
564 let first = key(7, "_443._tcp.alpha.", generation);
565 let same = key(7, "_443._tcp.alpha.", generation);
566 let other_secret = key(8, "_443._tcp.alpha.", generation);
567 let other_generation = key(7, "_443._tcp.alpha.", cache_generation(2));
568 assert_eq!(first, same);
569 assert_ne!(first, other_secret);
570 assert_ne!(first, other_generation);
571 assert_eq!(format!("{first:?}"), "CacheKey([redacted])");
572 assert!(matches!(
573 CacheKey::derive(
574 &[0; 32],
575 0,
576 generation,
577 &Name::from_ascii("alpha.").unwrap(),
578 RecordType::A,
579 ),
580 Err(CacheError::WeakSessionSecret)
581 ));
582 }
583
584 #[test]
585 fn expiration_and_generation_mismatch_remove_before_use() {
586 let generation = cache_generation(1);
587 let cache_key = key(7, "alpha.", generation);
588 let mut cache = SecureCache::new(CacheLimits::default()).unwrap();
589 cache
590 .insert(
591 cache_key,
592 "secure",
593 CacheAdmission {
594 value_bytes: 6,
595 disposition: CacheDisposition::Positive,
596 generation,
597 now: 100,
598 ttl_seconds: 10,
599 },
600 )
601 .unwrap();
602 assert_eq!(
603 cache.get(&cache_key, generation, 109).unwrap(),
604 Some((&"secure", CacheDisposition::Positive))
605 );
606 assert_eq!(cache.get(&cache_key, generation, 110).unwrap(), None);
607 assert_eq!(cache.stats().expirations, 1);
608
609 cache
610 .insert(
611 cache_key,
612 "negative",
613 CacheAdmission {
614 value_bytes: 8,
615 disposition: CacheDisposition::Negative(NegativeKind::NoData),
616 generation,
617 now: 200,
618 ttl_seconds: 10,
619 },
620 )
621 .unwrap();
622 assert_eq!(
623 cache.get(&cache_key, cache_generation(2), 201).unwrap(),
624 None
625 );
626 assert_eq!(cache.stats().stale_removals, 1);
627 }
628
629 #[test]
630 fn entry_and_byte_bounds_evict_least_recently_used() {
631 let limits = CacheLimits {
632 max_entries: 2,
633 max_total_value_bytes: 8,
634 max_value_bytes: 8,
635 max_positive_ttl: 100,
636 max_negative_ttl: 10,
637 };
638 let generation = cache_generation(1);
639 let first = key(7, "one.", generation);
640 let second = key(7, "two.", generation);
641 let third = key(7, "three.", generation);
642 let mut cache = SecureCache::new(limits).unwrap();
643 for (key, value) in [(first, "1111"), (second, "2222")] {
644 cache
645 .insert(
646 key,
647 value,
648 CacheAdmission {
649 value_bytes: 4,
650 disposition: CacheDisposition::Positive,
651 generation,
652 now: 0,
653 ttl_seconds: 100,
654 },
655 )
656 .unwrap();
657 }
658 assert!(cache.get(&first, generation, 1).unwrap().is_some());
659 cache
660 .insert(
661 third,
662 "3333",
663 CacheAdmission {
664 value_bytes: 4,
665 disposition: CacheDisposition::Positive,
666 generation,
667 now: 2,
668 ttl_seconds: 100,
669 },
670 )
671 .unwrap();
672 assert!(cache.get(&second, generation, 3).unwrap().is_none());
673 assert!(cache.get(&first, generation, 3).unwrap().is_some());
674 assert!(cache.get(&third, generation, 3).unwrap().is_some());
675 assert_eq!(cache.stats().evictions, 1);
676 assert_eq!(cache.stats().entries, 2);
677 assert_eq!(cache.stats().value_bytes, 8);
678 }
679
680 #[test]
681 fn invalid_limits_sizes_and_ttls_fail_without_insertion() {
682 assert!(matches!(
683 SecureCache::<()>::new(CacheLimits {
684 max_entries: 0,
685 ..CacheLimits::default()
686 }),
687 Err(CacheError::InvalidLimits)
688 ));
689 let mut cache = SecureCache::new(CacheLimits {
690 max_entries: 1,
691 max_total_value_bytes: 8,
692 max_value_bytes: 4,
693 max_positive_ttl: 10,
694 max_negative_ttl: 2,
695 })
696 .unwrap();
697 let generation = cache_generation(1);
698 let cache_key = key(7, "alpha.", generation);
699 assert!(matches!(
700 cache.insert(
701 cache_key,
702 (),
703 CacheAdmission {
704 value_bytes: 5,
705 disposition: CacheDisposition::Positive,
706 generation,
707 now: 0,
708 ttl_seconds: 1,
709 },
710 ),
711 Err(CacheError::ValueLimit)
712 ));
713 assert!(matches!(
714 cache.insert(
715 cache_key,
716 (),
717 CacheAdmission {
718 value_bytes: 1,
719 disposition: CacheDisposition::Negative(NegativeKind::NameError),
720 generation,
721 now: 0,
722 ttl_seconds: 3,
723 },
724 ),
725 Err(CacheError::TtlLimit)
726 ));
727 assert_eq!(cache.stats().entries, 0);
728 }
729}