Skip to main content

qualia_core_db/net/peer/replication/
cache.rs

1//! Canonical QSync cache keys (E06.3).
2//!
3//! Key = SHA-384 transcript over scope || source_generation || policy_generation
4//! || abi_tag. Lossy eviction is never evidence of absence. A miss is
5//! [`QdnfError::Incomplete`], never EmptyInSnapshot.
6
7use crate::crypto::network::transcript::Transcript;
8use crate::net::qdnf::errors::QdnfError;
9use crate::net::qdnf::types::{Generation, StrongDigest};
10
11pub const MAX_CACHE: usize = 16;
12
13const CACHE_DOMAIN: &[u8] = b"qdnf:sync:cache-key:v1-pq";
14
15/// Lookup of a generation-bound cache entry.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum CacheLookup {
18    Hit(StrongDigest),
19    Miss,
20    UntrustedMiss,
21}
22
23#[derive(Clone, Copy)]
24struct Slot {
25    occupied: bool,
26    scope: u64,
27    abi_tag: u64,
28    source_generation: Generation,
29    policy_generation: Generation,
30    key: StrongDigest,
31    value: StrongDigest,
32}
33
34/// Sixteen-slot generation-bound cache. Not a completeness oracle.
35pub struct CacheTable {
36    slots: [Slot; MAX_CACHE],
37}
38
39impl CacheTable {
40    /// Creates a default `CacheTable`.
41    pub const fn new() -> Self {
42        Self {
43            slots: [Slot {
44                occupied: false,
45                scope: 0,
46                abi_tag: 0,
47                source_generation: Generation::ZERO,
48                policy_generation: Generation::ZERO,
49                key: StrongDigest::ZERO,
50                value: StrongDigest::ZERO,
51            }; MAX_CACHE],
52        }
53    }
54}
55
56impl Default for CacheTable {
57    fn default() -> Self {
58        Self::new()
59    }
60}
61
62/// SHA-384 transcript key over scope and the two generations plus ABI tag.
63pub fn cache_key(
64    scope: u64,
65    source_generation: Generation,
66    policy_generation: Generation,
67    abi_tag: u64,
68) -> Result<StrongDigest, QdnfError> {
69    let mut t = Transcript::new();
70    t.append(b"v", CACHE_DOMAIN)?;
71    t.append(b"scope", &scope.to_be_bytes())?;
72    t.append(b"source_generation", &source_generation.0.to_be_bytes())?;
73    t.append(b"policy_generation", &policy_generation.0.to_be_bytes())?;
74    t.append(b"abi_tag", &abi_tag.to_be_bytes())?;
75    Ok(t.digest())
76}
77
78/// Insert `value` under the canonical key. Same key+value is idempotent.
79///
80/// [`QdnfError::Conflict`] if the key is occupied with a different value.
81/// [`QdnfError::Capacity`] at sixteen distinct keys.
82pub fn insert(
83    table: &mut CacheTable,
84    scope: u64,
85    source_generation: Generation,
86    policy_generation: Generation,
87    abi_tag: u64,
88    value: StrongDigest,
89) -> Result<StrongDigest, QdnfError> {
90    if value == StrongDigest::ZERO {
91        return Err(QdnfError::Malformed);
92    }
93    let key = cache_key(scope, source_generation, policy_generation, abi_tag)?;
94    if let Some(i) = find_key(table, &key) {
95        if table.slots[i].value != value {
96            return Err(QdnfError::Conflict);
97        }
98        return Ok(key);
99    }
100    let i = find_free(table).ok_or(QdnfError::Capacity)?;
101    table.slots[i] = Slot {
102        occupied: true,
103        scope,
104        abi_tag,
105        source_generation,
106        policy_generation,
107        key,
108        value,
109    };
110    Ok(key)
111}
112
113/// Look up by live generations. Generation mismatch on the same scope/ABI
114/// is [`CacheLookup::UntrustedMiss`]. Absence after eviction is [`CacheLookup::Miss`].
115pub fn lookup(
116    table: &CacheTable,
117    scope: u64,
118    source_generation: Generation,
119    policy_generation: Generation,
120    abi_tag: u64,
121) -> Result<CacheLookup, QdnfError> {
122    let key = cache_key(scope, source_generation, policy_generation, abi_tag)?;
123    if let Some(i) = find_key(table, &key) {
124        return Ok(CacheLookup::Hit(table.slots[i].value));
125    }
126    if let Some(i) = find_scope_abi(table, scope, abi_tag) {
127        let s = &table.slots[i];
128        if s.source_generation == source_generation && s.policy_generation == policy_generation {
129            return Ok(CacheLookup::Hit(s.value));
130        }
131        return Ok(CacheLookup::UntrustedMiss);
132    }
133    Ok(CacheLookup::Miss)
134}
135
136/// Drop the slot for `key`. Remaining lookups are [`CacheLookup::Miss`].
137pub fn evict(table: &mut CacheTable, key: StrongDigest) -> Result<(), QdnfError> {
138    let i = find_key(table, &key).ok_or(QdnfError::Incomplete)?;
139    table.slots[i].occupied = false;
140    Ok(())
141}
142
143/// Lossy eviction never becomes evidence of absence.
144#[inline]
145pub fn eviction_proves_absence() -> bool {
146    false
147}
148
149/// A miss is Incomplete, never EmptyInSnapshot.
150pub fn miss_is_incomplete(lookup: CacheLookup) -> Result<StrongDigest, QdnfError> {
151    match lookup {
152        CacheLookup::Hit(d) => Ok(d),
153        CacheLookup::Miss | CacheLookup::UntrustedMiss => Err(QdnfError::Incomplete),
154    }
155}
156
157fn find_key(table: &CacheTable, key: &StrongDigest) -> Option<usize> {
158    let mut i = 0usize;
159    while i < MAX_CACHE {
160        if table.slots[i].occupied && table.slots[i].key == *key {
161            return Some(i);
162        }
163        i += 1;
164    }
165    None
166}
167
168fn find_free(table: &CacheTable) -> Option<usize> {
169    let mut i = 0usize;
170    while i < MAX_CACHE {
171        if !table.slots[i].occupied {
172            return Some(i);
173        }
174        i += 1;
175    }
176    None
177}
178
179fn find_scope_abi(table: &CacheTable, scope: u64, abi_tag: u64) -> Option<usize> {
180    let mut i = 0usize;
181    while i < MAX_CACHE {
182        let s = &table.slots[i];
183        if s.occupied && s.scope == scope && s.abi_tag == abi_tag {
184            return Some(i);
185        }
186        i += 1;
187    }
188    None
189}
190
191#[cfg(test)]
192mod tests {
193    use super::*;
194
195    fn value(tag: u8) -> StrongDigest {
196        let mut d = StrongDigest::ZERO;
197        d.0[0] = tag;
198        d
199    }
200
201    #[test]
202    fn eviction_is_miss_not_absence() {
203        let mut table = CacheTable::new();
204        let gen = Generation(1);
205        let key = insert(&mut table, 7, gen, gen, 0xAB, value(1)).unwrap();
206        assert_eq!(
207            lookup(&table, 7, gen, gen, 0xAB).unwrap(),
208            CacheLookup::Hit(value(1))
209        );
210        evict(&mut table, key).unwrap();
211        let miss = lookup(&table, 7, gen, gen, 0xAB).unwrap();
212        assert_eq!(miss, CacheLookup::Miss);
213        assert!(!eviction_proves_absence());
214        assert_eq!(miss_is_incomplete(miss), Err(QdnfError::Incomplete));
215        assert_ne!(miss, CacheLookup::Hit(value(1)));
216    }
217
218    #[test]
219    fn generation_mismatch_is_untrusted_miss() {
220        let mut table = CacheTable::new();
221        insert(&mut table, 7, Generation(1), Generation(1), 3, value(2)).unwrap();
222        let stale = lookup(&table, 7, Generation(2), Generation(1), 3).unwrap();
223        assert_eq!(stale, CacheLookup::UntrustedMiss);
224        assert_eq!(miss_is_incomplete(stale), Err(QdnfError::Incomplete));
225    }
226
227    #[test]
228    fn key_changes_with_each_generation_and_abi() {
229        let a = cache_key(1, Generation(1), Generation(1), 1).unwrap();
230        let b = cache_key(1, Generation(2), Generation(1), 1).unwrap();
231        let c = cache_key(1, Generation(1), Generation(2), 1).unwrap();
232        let d = cache_key(1, Generation(1), Generation(1), 2).unwrap();
233        assert_ne!(a, b);
234        assert_ne!(a, c);
235        assert_ne!(a, d);
236        assert_ne!(a, StrongDigest::ZERO);
237    }
238
239    #[test]
240    fn seventeenth_insert_is_capacity() {
241        let mut table = CacheTable::new();
242        let gen = Generation(1);
243        let mut i = 0u64;
244        while i < MAX_CACHE as u64 {
245            insert(&mut table, i, gen, gen, 1, value(1)).unwrap();
246            i += 1;
247        }
248        assert_eq!(
249            insert(&mut table, 99, gen, gen, 1, value(1)),
250            Err(QdnfError::Capacity)
251        );
252    }
253}