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;
16use std::fmt;
17use std::hash::Hash;
18
19use hns_dns_wire::{Name, RecordType};
20use sha2::{Digest, Sha256};
21use thiserror::Error;
22
23const CACHE_KEY_DOMAIN: &[u8] = b"hns-browser-cache-key-v1";
24
25#[derive(Clone, Copy, Debug, Eq, PartialEq)]
27pub struct CacheLimits {
28 pub max_entries: usize,
30 pub max_total_value_bytes: usize,
32 pub max_value_bytes: usize,
34 pub max_positive_ttl: u32,
36 pub max_negative_ttl: u32,
38}
39
40impl Default for CacheLimits {
41 fn default() -> Self {
42 Self {
43 max_entries: 4_096,
44 max_total_value_bytes: 16 * 1024 * 1024,
45 max_value_bytes: 256 * 1024,
46 max_positive_ttl: 86_400,
47 max_negative_ttl: 3_600,
48 }
49 }
50}
51
52impl CacheLimits {
53 fn validate(self) -> Result<Self, CacheError> {
54 if self.max_entries == 0
55 || self.max_total_value_bytes == 0
56 || self.max_value_bytes == 0
57 || self.max_value_bytes > self.max_total_value_bytes
58 || self.max_positive_ttl == 0
59 || self.max_negative_ttl == 0
60 {
61 return Err(CacheError::InvalidLimits);
62 }
63 Ok(self)
64 }
65}
66
67#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
69pub struct CacheGeneration {
70 pub runtime_generation: u64,
72 pub policy_generation: u64,
74 pub chain_height: u32,
76 pub tree_root: [u8; 32],
78}
79
80impl CacheGeneration {
81 fn validate(self) -> Result<Self, CacheError> {
82 if self.runtime_generation == 0 || self.policy_generation == 0 {
83 return Err(CacheError::InvalidGeneration);
84 }
85 Ok(self)
86 }
87}
88
89#[repr(u8)]
91#[derive(Clone, Copy, Debug, Eq, PartialEq)]
92pub enum NegativeKind {
93 NameError = 0,
95 NoData = 1,
97 HnsNameAbsent = 2,
99}
100
101#[derive(Clone, Copy, Debug, Eq, PartialEq)]
103pub enum CacheDisposition {
104 Positive,
106 Negative(NegativeKind),
108}
109
110#[derive(Clone, Copy, Debug, Eq, PartialEq)]
112pub struct CacheAdmission {
113 pub value_bytes: usize,
115 pub disposition: CacheDisposition,
117 pub generation: CacheGeneration,
119 pub now: u64,
121 pub ttl_seconds: u32,
123}
124
125#[derive(Clone, Copy, Eq, Hash, PartialEq)]
127pub struct CacheKey([u8; 32]);
128
129impl CacheKey {
130 pub fn derive(
132 session_secret: &[u8; 32],
133 network_id: u8,
134 generation: CacheGeneration,
135 name: &Name,
136 record_type: RecordType,
137 ) -> Result<Self, CacheError> {
138 if session_secret == &[0; 32] {
139 return Err(CacheError::WeakSessionSecret);
140 }
141 let generation = generation.validate()?;
142 let mut wire_name = Vec::with_capacity(name.wire_len());
143 name.encode(&mut wire_name)?;
144 let mut hasher = Sha256::new();
145 hasher.update(CACHE_KEY_DOMAIN);
146 hasher.update(session_secret);
147 hasher.update([network_id]);
148 hasher.update(generation.runtime_generation.to_be_bytes());
149 hasher.update(generation.policy_generation.to_be_bytes());
150 hasher.update(generation.chain_height.to_be_bytes());
151 hasher.update(generation.tree_root);
152 hasher.update(record_type.code().to_be_bytes());
153 hasher.update(
154 u16::try_from(wire_name.len())
155 .map_err(|_| CacheError::InvalidQuery)?
156 .to_be_bytes(),
157 );
158 hasher.update(&wire_name);
159 Ok(Self(hasher.finalize().into()))
160 }
161}
162
163impl fmt::Debug for CacheKey {
164 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
165 formatter.write_str("CacheKey([redacted])")
166 }
167}
168
169#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
171pub struct CacheStats {
172 pub entries: usize,
174 pub value_bytes: usize,
176 pub hits: u64,
178 pub misses: u64,
180 pub evictions: u64,
182 pub expirations: u64,
184 pub stale_removals: u64,
186}
187
188#[derive(Clone, Debug)]
189struct Entry<Value> {
190 value: Value,
191 value_bytes: usize,
192 disposition: CacheDisposition,
193 generation: CacheGeneration,
194 expires_at: u64,
195 last_access: u64,
196}
197
198#[derive(Clone, Debug)]
200pub struct SecureCache<Value> {
201 limits: CacheLimits,
202 entries: HashMap<CacheKey, Entry<Value>>,
203 sequence: u64,
204 stats: CacheStats,
205}
206
207impl<Value> SecureCache<Value> {
208 pub fn new(limits: CacheLimits) -> Result<Self, CacheError> {
210 let limits = limits.validate()?;
211 Ok(Self {
212 limits,
213 entries: HashMap::with_capacity(limits.max_entries),
214 sequence: 0,
215 stats: CacheStats::default(),
216 })
217 }
218
219 pub fn insert(
223 &mut self,
224 key: CacheKey,
225 value: Value,
226 admission: CacheAdmission,
227 ) -> Result<(), CacheError> {
228 let generation = admission.generation.validate()?;
229 let value_bytes = admission.value_bytes;
230 if value_bytes == 0
231 || value_bytes > self.limits.max_value_bytes
232 || value_bytes > self.limits.max_total_value_bytes
233 {
234 return Err(CacheError::ValueLimit);
235 }
236 let maximum_ttl = match admission.disposition {
237 CacheDisposition::Positive => self.limits.max_positive_ttl,
238 CacheDisposition::Negative(_) => self.limits.max_negative_ttl,
239 };
240 if admission.ttl_seconds == 0 || admission.ttl_seconds > maximum_ttl {
241 return Err(CacheError::TtlLimit);
242 }
243 let expires_at = admission
244 .now
245 .checked_add(u64::from(admission.ttl_seconds))
246 .ok_or(CacheError::TimeOverflow)?;
247 let sequence = self.next_sequence()?;
248 self.remove_expired(admission.now);
249 self.remove_internal(&key);
250 while self.entries.len() >= self.limits.max_entries
251 || self
252 .stats
253 .value_bytes
254 .checked_add(value_bytes)
255 .is_none_or(|bytes| bytes > self.limits.max_total_value_bytes)
256 {
257 self.evict_lru().ok_or(CacheError::ValueLimit)?;
258 }
259 self.stats.value_bytes = self
260 .stats
261 .value_bytes
262 .checked_add(value_bytes)
263 .ok_or(CacheError::ValueLimit)?;
264 self.entries.insert(
265 key,
266 Entry {
267 value,
268 value_bytes,
269 disposition: admission.disposition,
270 generation,
271 expires_at,
272 last_access: sequence,
273 },
274 );
275 self.stats.entries = self.entries.len();
276 Ok(())
277 }
278
279 pub fn get(
281 &mut self,
282 key: &CacheKey,
283 generation: CacheGeneration,
284 now: u64,
285 ) -> Result<Option<(&Value, CacheDisposition)>, CacheError> {
286 let generation = generation.validate()?;
287 let Some(metadata) = self
288 .entries
289 .get(key)
290 .map(|entry| (entry.generation, entry.expires_at, entry.disposition))
291 else {
292 self.stats.misses = self.stats.misses.saturating_add(1);
293 return Ok(None);
294 };
295 if metadata.0 != generation {
296 self.remove_internal(key);
297 self.stats.stale_removals = self.stats.stale_removals.saturating_add(1);
298 self.stats.misses = self.stats.misses.saturating_add(1);
299 return Ok(None);
300 }
301 if now >= metadata.1 {
302 self.remove_internal(key);
303 self.stats.expirations = self.stats.expirations.saturating_add(1);
304 self.stats.misses = self.stats.misses.saturating_add(1);
305 return Ok(None);
306 }
307 let sequence = self.next_sequence()?;
308 let entry = self
309 .entries
310 .get_mut(key)
311 .ok_or(CacheError::InternalInvariant)?;
312 entry.last_access = sequence;
313 self.stats.hits = self.stats.hits.saturating_add(1);
314 Ok(Some((&entry.value, metadata.2)))
315 }
316
317 pub fn clear(&mut self) {
319 self.entries.clear();
320 self.stats.entries = 0;
321 self.stats.value_bytes = 0;
322 }
323
324 pub fn remove(&mut self, key: &CacheKey) -> bool {
326 self.remove_internal(key).is_some()
327 }
328
329 #[must_use]
331 pub const fn stats(&self) -> CacheStats {
332 self.stats
333 }
334
335 #[must_use]
337 pub const fn limits(&self) -> CacheLimits {
338 self.limits
339 }
340
341 fn next_sequence(&mut self) -> Result<u64, CacheError> {
342 self.sequence = self
343 .sequence
344 .checked_add(1)
345 .ok_or(CacheError::SequenceExhausted)?;
346 Ok(self.sequence)
347 }
348
349 fn remove_expired(&mut self, now: u64) {
350 let expired = self
351 .entries
352 .iter()
353 .filter_map(|(key, entry)| (now >= entry.expires_at).then_some(*key))
354 .collect::<Vec<_>>();
355 for key in expired {
356 if self.remove_internal(&key).is_some() {
357 self.stats.expirations = self.stats.expirations.saturating_add(1);
358 }
359 }
360 }
361
362 fn evict_lru(&mut self) -> Option<()> {
363 let key = self
364 .entries
365 .iter()
366 .min_by_key(|(_, entry)| entry.last_access)
367 .map(|(key, _)| *key)?;
368 self.remove_internal(&key)?;
369 self.stats.evictions = self.stats.evictions.saturating_add(1);
370 Some(())
371 }
372
373 fn remove_internal(&mut self, key: &CacheKey) -> Option<Entry<Value>> {
374 let entry = self.entries.remove(key)?;
375 self.stats.value_bytes = self.stats.value_bytes.saturating_sub(entry.value_bytes);
376 self.stats.entries = self.entries.len();
377 Some(entry)
378 }
379}
380
381#[derive(Debug, Error)]
383#[non_exhaustive]
384pub enum CacheError {
385 #[error("DNS query encoding failed: {0}")]
387 Wire(#[from] hns_dns_wire::Error),
388 #[error("invalid cache limits")]
390 InvalidLimits,
391 #[error("invalid cache generation")]
393 InvalidGeneration,
394 #[error("cache session secret must be randomly generated")]
396 WeakSessionSecret,
397 #[error("invalid cache query identity")]
399 InvalidQuery,
400 #[error("cache value exceeds its bound")]
402 ValueLimit,
403 #[error("cache TTL exceeds its bound")]
405 TtlLimit,
406 #[error("cache expiration time overflow")]
408 TimeOverflow,
409 #[error("cache LRU sequence exhausted")]
411 SequenceExhausted,
412 #[error("cache internal invariant failed")]
414 InternalInvariant,
415}
416
417#[cfg(test)]
418#[allow(
419 clippy::unwrap_used,
420 reason = "tests fail immediately on invalid local cache fixtures"
421)]
422mod tests {
423 use super::*;
424
425 fn cache_generation(value: u8) -> CacheGeneration {
426 CacheGeneration {
427 runtime_generation: u64::from(value),
428 policy_generation: 1,
429 chain_height: 100,
430 tree_root: [value; 32],
431 }
432 }
433
434 fn key(secret: u8, name: &str, generation: CacheGeneration) -> CacheKey {
435 CacheKey::derive(
436 &[secret; 32],
437 0,
438 generation,
439 &Name::from_ascii(name).unwrap(),
440 RecordType::Tlsa,
441 )
442 .unwrap()
443 }
444
445 #[test]
446 fn keys_are_qname_free_session_and_generation_specific() {
447 let generation = cache_generation(1);
448 let first = key(7, "_443._tcp.alpha.", generation);
449 let same = key(7, "_443._tcp.alpha.", generation);
450 let other_secret = key(8, "_443._tcp.alpha.", generation);
451 let other_generation = key(7, "_443._tcp.alpha.", cache_generation(2));
452 assert_eq!(first, same);
453 assert_ne!(first, other_secret);
454 assert_ne!(first, other_generation);
455 assert_eq!(format!("{first:?}"), "CacheKey([redacted])");
456 assert!(matches!(
457 CacheKey::derive(
458 &[0; 32],
459 0,
460 generation,
461 &Name::from_ascii("alpha.").unwrap(),
462 RecordType::A,
463 ),
464 Err(CacheError::WeakSessionSecret)
465 ));
466 }
467
468 #[test]
469 fn expiration_and_generation_mismatch_remove_before_use() {
470 let generation = cache_generation(1);
471 let cache_key = key(7, "alpha.", generation);
472 let mut cache = SecureCache::new(CacheLimits::default()).unwrap();
473 cache
474 .insert(
475 cache_key,
476 "secure",
477 CacheAdmission {
478 value_bytes: 6,
479 disposition: CacheDisposition::Positive,
480 generation,
481 now: 100,
482 ttl_seconds: 10,
483 },
484 )
485 .unwrap();
486 assert_eq!(
487 cache.get(&cache_key, generation, 109).unwrap(),
488 Some((&"secure", CacheDisposition::Positive))
489 );
490 assert_eq!(cache.get(&cache_key, generation, 110).unwrap(), None);
491 assert_eq!(cache.stats().expirations, 1);
492
493 cache
494 .insert(
495 cache_key,
496 "negative",
497 CacheAdmission {
498 value_bytes: 8,
499 disposition: CacheDisposition::Negative(NegativeKind::NoData),
500 generation,
501 now: 200,
502 ttl_seconds: 10,
503 },
504 )
505 .unwrap();
506 assert_eq!(
507 cache.get(&cache_key, cache_generation(2), 201).unwrap(),
508 None
509 );
510 assert_eq!(cache.stats().stale_removals, 1);
511 }
512
513 #[test]
514 fn entry_and_byte_bounds_evict_least_recently_used() {
515 let limits = CacheLimits {
516 max_entries: 2,
517 max_total_value_bytes: 8,
518 max_value_bytes: 8,
519 max_positive_ttl: 100,
520 max_negative_ttl: 10,
521 };
522 let generation = cache_generation(1);
523 let first = key(7, "one.", generation);
524 let second = key(7, "two.", generation);
525 let third = key(7, "three.", generation);
526 let mut cache = SecureCache::new(limits).unwrap();
527 for (key, value) in [(first, "1111"), (second, "2222")] {
528 cache
529 .insert(
530 key,
531 value,
532 CacheAdmission {
533 value_bytes: 4,
534 disposition: CacheDisposition::Positive,
535 generation,
536 now: 0,
537 ttl_seconds: 100,
538 },
539 )
540 .unwrap();
541 }
542 assert!(cache.get(&first, generation, 1).unwrap().is_some());
543 cache
544 .insert(
545 third,
546 "3333",
547 CacheAdmission {
548 value_bytes: 4,
549 disposition: CacheDisposition::Positive,
550 generation,
551 now: 2,
552 ttl_seconds: 100,
553 },
554 )
555 .unwrap();
556 assert!(cache.get(&second, generation, 3).unwrap().is_none());
557 assert!(cache.get(&first, generation, 3).unwrap().is_some());
558 assert!(cache.get(&third, generation, 3).unwrap().is_some());
559 assert_eq!(cache.stats().evictions, 1);
560 assert_eq!(cache.stats().entries, 2);
561 assert_eq!(cache.stats().value_bytes, 8);
562 }
563
564 #[test]
565 fn invalid_limits_sizes_and_ttls_fail_without_insertion() {
566 assert!(matches!(
567 SecureCache::<()>::new(CacheLimits {
568 max_entries: 0,
569 ..CacheLimits::default()
570 }),
571 Err(CacheError::InvalidLimits)
572 ));
573 let mut cache = SecureCache::new(CacheLimits {
574 max_entries: 1,
575 max_total_value_bytes: 8,
576 max_value_bytes: 4,
577 max_positive_ttl: 10,
578 max_negative_ttl: 2,
579 })
580 .unwrap();
581 let generation = cache_generation(1);
582 let cache_key = key(7, "alpha.", generation);
583 assert!(matches!(
584 cache.insert(
585 cache_key,
586 (),
587 CacheAdmission {
588 value_bytes: 5,
589 disposition: CacheDisposition::Positive,
590 generation,
591 now: 0,
592 ttl_seconds: 1,
593 },
594 ),
595 Err(CacheError::ValueLimit)
596 ));
597 assert!(matches!(
598 cache.insert(
599 cache_key,
600 (),
601 CacheAdmission {
602 value_bytes: 1,
603 disposition: CacheDisposition::Negative(NegativeKind::NameError),
604 generation,
605 now: 0,
606 ttl_seconds: 3,
607 },
608 ),
609 Err(CacheError::TtlLimit)
610 ));
611 assert_eq!(cache.stats().entries, 0);
612 }
613}