qualia_core_db/net/peer/replication/
cache.rs1use 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#[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
34pub struct CacheTable {
36 slots: [Slot; MAX_CACHE],
37}
38
39impl CacheTable {
40 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
62pub 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
78pub 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
113pub 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
136pub 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#[inline]
145pub fn eviction_proves_absence() -> bool {
146 false
147}
148
149pub 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}