Skip to main content

hns_cache/
lib.rs

1//! Bounded positive and negative cache for HNS browser resolution.
2//!
3//! Keys are session-secret-derived SHA-256 values rather than qnames. Entries
4//! are bound to runtime generation, policy generation, and exact Handshake
5//! chain anchor. Expired or mismatched entries are removed before use.
6
7#![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/// Bounds for one cache instance.
28#[derive(Clone, Copy, Debug, Eq, PartialEq)]
29pub struct CacheLimits {
30    /// Maximum resident entries.
31    pub max_entries: usize,
32    /// Maximum caller-reported bytes across resident values.
33    pub max_total_value_bytes: usize,
34    /// Maximum caller-reported bytes for one value.
35    pub max_value_bytes: usize,
36    /// Maximum positive TTL in seconds.
37    pub max_positive_ttl: u32,
38    /// Maximum negative TTL in seconds.
39    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/// Exact authority state under which an entry was produced.
70#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
71pub struct CacheGeneration {
72    /// Runtime generation.
73    pub runtime_generation: u64,
74    /// Policy generation.
75    pub policy_generation: u64,
76    /// Validated Handshake height.
77    pub chain_height: u32,
78    /// Exact committed Handshake name-tree root.
79    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/// Negative cache result.
92#[repr(u8)]
93#[derive(Clone, Copy, Debug, Eq, PartialEq)]
94pub enum NegativeKind {
95    /// DNSSEC-authenticated name error.
96    NameError = 0,
97    /// DNSSEC-authenticated no-data result.
98    NoData = 1,
99    /// Current HNS Urkel non-inclusion.
100    HnsNameAbsent = 2,
101}
102
103/// Positive or authenticated-negative cache disposition.
104#[derive(Clone, Copy, Debug, Eq, PartialEq)]
105pub enum CacheDisposition {
106    /// Positive validated data.
107    Positive,
108    /// Cryptographically authenticated absence.
109    Negative(NegativeKind),
110}
111
112/// Metadata checked when admitting one cache value.
113#[derive(Clone, Copy, Debug, Eq, PartialEq)]
114pub struct CacheAdmission {
115    /// Conservative encoded/in-memory value byte estimate.
116    pub value_bytes: usize,
117    /// Positive or authenticated-negative result.
118    pub disposition: CacheDisposition,
119    /// Exact runtime, policy, and chain authority.
120    pub generation: CacheGeneration,
121    /// Current monotonic or Unix time in seconds.
122    pub now: u64,
123    /// Requested TTL in seconds.
124    pub ttl_seconds: u32,
125}
126
127/// Opaque per-session query key.
128#[derive(Clone, Copy, Eq, Hash, PartialEq)]
129pub struct CacheKey([u8; 32]);
130
131impl CacheKey {
132    /// Derive a key from a secret runtime salt and canonical query identity.
133    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/// Name-free cache counters.
172#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
173pub struct CacheStats {
174    /// Resident entries.
175    pub entries: usize,
176    /// Caller-reported resident value bytes.
177    pub value_bytes: usize,
178    /// Successful current-generation reads.
179    pub hits: u64,
180    /// Absent, expired, or generation-mismatched reads.
181    pub misses: u64,
182    /// Capacity-driven removals.
183    pub evictions: u64,
184    /// TTL-driven removals.
185    pub expirations: u64,
186    /// Generation-mismatch removals.
187    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/// Bounded LRU cache with explicit TTL and authority-generation binding.
201#[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/// Small process-local expiring LRU for data that is already bound to an
216/// authenticated authority fingerprint by its key.
217///
218/// Browser adapters use this for short-lived connection-plan and delegated
219/// answer reuse. Consensus, proof, DNSSEC, and DANE caches should use
220/// [`SecureCache`] so the engine also binds their generation and chain anchor.
221#[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    /// Construct an empty cache with a nonzero hard entry bound.
234    #[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    /// Insert or replace one entry for a finite positive lifetime.
244    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    /// Return a cloned live entry and promote it to most recently used.
260    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    /// Number of live entries.
269    pub fn len(&mut self) -> usize {
270        self.prune_expired();
271        self.entries.len()
272    }
273
274    /// Whether no live entries remain.
275    pub fn is_empty(&mut self) -> bool {
276        self.len() == 0
277    }
278
279    /// Remove all entries.
280    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    /// Create an empty cache after validating all bounds.
307    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    /// Insert one positive or authenticated-negative result.
318    ///
319    /// `value_bytes` is the caller's conservative encoded/in-memory estimate.
320    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    /// Read one current entry and update its LRU position.
378    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    /// Remove every entry on a generation, policy, or chain-anchor transition.
416    pub fn clear(&mut self) {
417        self.entries.clear();
418        self.stats.entries = 0;
419        self.stats.value_bytes = 0;
420    }
421
422    /// Remove one opaque key.
423    pub fn remove(&mut self, key: &CacheKey) -> bool {
424        self.remove_internal(key).is_some()
425    }
426
427    /// Name-free counters.
428    #[must_use]
429    pub const fn stats(&self) -> CacheStats {
430        self.stats
431    }
432
433    /// Configured hard bounds.
434    #[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/// Cache configuration, key, bound, or invariant failure.
480#[derive(Debug, Error)]
481#[non_exhaustive]
482pub enum CacheError {
483    /// DNS name encoding failed.
484    #[error("DNS query encoding failed: {0}")]
485    Wire(#[from] hns_dns_wire::Error),
486    /// A configured cache bound is zero or inconsistent.
487    #[error("invalid cache limits")]
488    InvalidLimits,
489    /// Runtime or policy generation is zero.
490    #[error("invalid cache generation")]
491    InvalidGeneration,
492    /// Runtime cache-key secret is all zero.
493    #[error("cache session secret must be randomly generated")]
494    WeakSessionSecret,
495    /// Canonical query identity cannot be represented.
496    #[error("invalid cache query identity")]
497    InvalidQuery,
498    /// Caller-reported value size exceeds a bound.
499    #[error("cache value exceeds its bound")]
500    ValueLimit,
501    /// TTL is zero or exceeds its positive/negative bound.
502    #[error("cache TTL exceeds its bound")]
503    TtlLimit,
504    /// Expiration time overflowed.
505    #[error("cache expiration time overflow")]
506    TimeOverflow,
507    /// LRU sequence cannot advance.
508    #[error("cache LRU sequence exhausted")]
509    SequenceExhausted,
510    /// Internal entry disappeared during one exclusive operation.
511    #[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}