ed25519_simd/
hot_key_cache.rs1use crate::cache::{CachedPublicKey, KeyCache};
2use crate::input::PUBLIC_KEY_LEN;
3use std::cell::Cell;
4use std::collections::HashMap;
5
6const NONE: usize = usize::MAX;
8
9#[derive(Debug)]
14struct CacheEntry {
15 key: CachedPublicKey,
16 newer: Cell<usize>,
19 older: Cell<usize>,
20}
21
22#[derive(Debug)]
35pub struct HotKeyCache {
36 entries: Vec<CacheEntry>,
38 index: HashMap<[u8; PUBLIC_KEY_LEN], usize>,
39 capacity: usize,
40 mru: Cell<usize>,
41 lru: Cell<usize>,
42}
43
44impl HotKeyCache {
45 pub fn with_capacity(capacity: usize) -> Self {
48 let capacity = capacity.max(1);
49 Self {
50 entries: Vec::with_capacity(capacity),
51 index: HashMap::with_capacity(capacity),
52 capacity,
53 mru: Cell::new(NONE),
54 lru: Cell::new(NONE),
55 }
56 }
57
58 pub fn set_capacity(&mut self, capacity: usize) {
63 self.capacity = capacity.max(1);
64 self.evict_to_capacity();
65 if self.capacity < self.entries.capacity() {
66 self.entries.shrink_to(self.capacity);
69 self.index.shrink_to(self.capacity);
70 } else {
71 self.entries.reserve(self.capacity - self.entries.len());
72 self.index.reserve(self.capacity - self.index.len());
73 }
74 }
75
76 fn unlink(&self, slot: usize) {
78 let newer = self.entries[slot].newer.get();
79 let older = self.entries[slot].older.get();
80 if newer == NONE {
81 self.mru.set(older);
82 } else {
83 self.entries[newer].older.set(older);
84 }
85 if older == NONE {
86 self.lru.set(newer);
87 } else {
88 self.entries[older].newer.set(newer);
89 }
90 }
91
92 fn link_mru(&self, slot: usize) {
94 let previous_mru = self.mru.get();
95 self.entries[slot].newer.set(NONE);
96 self.entries[slot].older.set(previous_mru);
97 if previous_mru == NONE {
98 self.lru.set(slot);
99 } else {
100 self.entries[previous_mru].newer.set(slot);
101 }
102 self.mru.set(slot);
103 }
104
105 fn touch(&self, slot: usize) {
106 if self.mru.get() != slot {
107 self.unlink(slot);
108 self.link_mru(slot);
109 }
110 }
111
112 fn evict_to_capacity(&mut self) {
114 while self.entries.len() > self.capacity {
115 let lru = self.lru.get();
116 debug_assert_ne!(lru, NONE, "a non-empty cache always has an LRU end");
117 self.remove_at(lru);
118 }
119 }
120
121 fn remove_at(&mut self, slot: usize) {
122 self.unlink(slot);
123 let removed = self.entries.swap_remove(slot);
124 self.index.remove(&removed.key.encoded);
125
126 if let Some(moved) = self.entries.get(slot) {
128 let (encoded, newer, older) = (moved.key.encoded, moved.newer.get(), moved.older.get());
129 self.index.insert(encoded, slot);
130 if newer == NONE {
131 self.mru.set(slot);
132 } else {
133 self.entries[newer].older.set(slot);
134 }
135 if older == NONE {
136 self.lru.set(slot);
137 } else {
138 self.entries[older].newer.set(slot);
139 }
140 }
141 }
142
143 #[cfg(test)]
145 fn assert_invariants(&self) {
146 assert_eq!(self.entries.len(), self.index.len());
147 assert!(self.entries.len() <= self.capacity);
148 for (slot, entry) in self.entries.iter().enumerate() {
149 assert_eq!(self.index.get(&entry.key.encoded), Some(&slot));
150 }
151
152 let mut forward = Vec::new();
153 let mut slot = self.mru.get();
154 let mut previous = NONE;
155 while slot != NONE {
156 assert!(slot < self.entries.len());
157 assert_eq!(self.entries[slot].newer.get(), previous);
158 forward.push(slot);
159 previous = slot;
160 slot = self.entries[slot].older.get();
161 }
162 assert_eq!(forward.len(), self.entries.len(), "list length");
163 assert_eq!(previous, self.lru.get(), "lru end");
164
165 let mut backward = Vec::new();
166 let mut slot = self.lru.get();
167 while slot != NONE {
168 backward.push(slot);
169 slot = self.entries[slot].newer.get();
170 }
171 backward.reverse();
172 assert_eq!(forward, backward, "list is not doubly consistent");
173 }
174}
175
176impl crate::cache::private::Sealed for HotKeyCache {}
177
178impl KeyCache for HotKeyCache {
179 type Queues<P: crate::VerificationPolicy> = P::Queues;
180
181 #[inline]
182 fn get(&self, encoded: &[u8; PUBLIC_KEY_LEN]) -> Option<&CachedPublicKey> {
183 let slot = *self.index.get(encoded)?;
184 self.touch(slot);
185 Some(&self.entries[slot].key)
186 }
187
188 #[inline]
189 fn dispatch_verify_batch<P: crate::VerificationPolicy>(
190 verifier: &mut crate::Verifier<P, Self>,
191 inputs: &[crate::VerifyInput<'_>],
192 out: &mut [bool],
193 ) {
194 P::dispatch_cached_verify_batch(verifier, inputs, out);
195 }
196
197 fn insert(&mut self, key: CachedPublicKey) {
198 if let Some(&slot) = self.index.get(&key.encoded) {
199 self.touch(slot);
200 return;
201 }
202
203 if self.entries.len() >= self.capacity {
204 let slot = self.lru.get();
205 debug_assert_ne!(slot, NONE, "a full cache always has an LRU entry");
206 self.unlink(slot);
207 self.index.remove(&self.entries[slot].key.encoded);
208
209 let encoded = key.encoded;
210 self.entries[slot] = CacheEntry {
211 key,
212 newer: Cell::new(NONE),
213 older: Cell::new(NONE),
214 };
215 self.index.insert(encoded, slot);
216 self.link_mru(slot);
217 return;
218 }
219
220 let slot = self.entries.len();
221 self.index.insert(key.encoded, slot);
222 self.entries.push(CacheEntry {
223 key,
224 newer: Cell::new(NONE),
225 older: Cell::new(NONE),
226 });
227 self.link_mru(slot);
228 }
229}
230
231#[cfg(test)]
232mod tests {
233 use super::*;
234 use crate::edwards::PointTable;
235 use rand::{RngCore, SeedableRng, rngs::StdRng};
236
237 fn encoded(index: u64) -> [u8; PUBLIC_KEY_LEN] {
238 let mut encoded = [0u8; PUBLIC_KEY_LEN];
239 encoded[..8].copy_from_slice(&index.to_le_bytes());
240 encoded
241 }
242
243 fn key(index: u64) -> CachedPublicKey {
245 CachedPublicKey {
246 encoded: encoded(index),
247 table: PointTable::identity(),
248 }
249 }
250
251 #[test]
252 fn evicts_least_recently_used() {
253 let mut cache = HotKeyCache::with_capacity(3);
254 for i in 0..3 {
255 cache.insert(key(i));
256 }
257 assert!(cache.get(&encoded(0)).is_some());
259 assert!(cache.get(&encoded(2)).is_some());
260 cache.assert_invariants();
261
262 cache.insert(key(3));
263 cache.assert_invariants();
264 assert!(
265 cache.get(&encoded(1)).is_none(),
266 "LRU key should be evicted"
267 );
268 for i in [0, 2, 3] {
269 assert!(
270 cache.get(&encoded(i)).is_some(),
271 "key {i} should be resident"
272 );
273 }
274 }
275
276 #[test]
277 fn a_repeatedly_used_hot_set_survives_distinct_key_churn() {
278 let capacity = 64;
280 let hot_count = 48;
281 let mut cache = HotKeyCache::with_capacity(capacity);
282 for i in 0..hot_count {
283 cache.insert(key(i));
284 }
285
286 for cold in 1000..3000 {
287 for i in 0..hot_count {
288 assert!(cache.get(&encoded(i)).is_some(), "hot key {i} was evicted");
289 }
290 cache.insert(key(cold));
291 }
292 cache.assert_invariants();
293 }
294
295 #[test]
296 fn insert_of_a_resident_key_only_refreshes_recency() {
297 let mut cache = HotKeyCache::with_capacity(2);
298 cache.insert(key(0));
299 cache.insert(key(1));
300 cache.insert(key(0));
302 cache.assert_invariants();
303 assert_eq!(cache.entries.len(), 2);
304
305 cache.insert(key(2));
306 assert!(cache.get(&encoded(1)).is_none(), "1 was the LRU");
307 assert!(cache.get(&encoded(0)).is_some());
308 assert!(cache.get(&encoded(2)).is_some());
309 }
310
311 #[test]
312 fn set_capacity_clamps_to_one_and_evicts_immediately() {
313 let mut cache = HotKeyCache::with_capacity(8);
314 for i in 0..8 {
315 cache.insert(key(i));
316 }
317
318 cache.set_capacity(3);
319 cache.assert_invariants();
320 assert_eq!(cache.entries.len(), 3);
321 for i in 5..8 {
323 assert!(cache.get(&encoded(i)).is_some(), "key {i} should survive");
324 }
325
326 cache.set_capacity(0);
327 cache.assert_invariants();
328 assert_eq!(cache.entries.len(), 1);
329 assert!(
330 cache.get(&encoded(7)).is_some(),
331 "the MRU key should survive"
332 );
333
334 for i in 8..12 {
335 cache.insert(key(i));
336 cache.assert_invariants();
337 assert_eq!(cache.entries.len(), 1);
338 assert!(cache.get(&encoded(i)).is_some(), "key {i} just inserted");
339 }
340 }
341
342 #[test]
343 fn lowering_capacity_retains_mru_entries_and_accepts_inserts() {
344 let mut cache = HotKeyCache::with_capacity(4096);
345 for i in 0..4096 {
346 cache.insert(key(i));
347 }
348
349 cache.set_capacity(8);
350 cache.assert_invariants();
351 assert_eq!(cache.entries.len(), 8);
352 for i in 4088..4096 {
353 assert!(cache.get(&encoded(i)).is_some(), "key {i} should survive");
354 }
355 cache.insert(key(9999));
356 cache.assert_invariants();
357 assert_eq!(cache.entries.len(), 8);
358 assert!(cache.get(&encoded(4088)).is_none(), "4088 was the LRU");
359 }
360
361 #[test]
362 fn raising_the_capacity_reserves_like_the_constructor() {
363 let mut cache = HotKeyCache::with_capacity(4);
364 for i in 0..4 {
365 cache.insert(key(i));
366 }
367
368 cache.set_capacity(64);
369 cache.assert_invariants();
370 assert!(
371 cache.entries.capacity() >= 64,
372 "raising the bound must reserve for it: capacity {}",
373 cache.entries.capacity()
374 );
375 for i in 0..4 {
376 assert!(cache.get(&encoded(i)).is_some(), "key {i} should survive");
377 }
378 }
379
380 #[test]
382 fn link_surgery_stays_consistent_under_mixed_operations() {
383 let mut cache = HotKeyCache::with_capacity(16);
384 let mut rng = StdRng::seed_from_u64(0x2545_f491_4f6c_dd1d);
385
386 for step in 0..4096u64 {
387 match rng.next_u64() % 4 {
388 0 => cache.insert(key(rng.next_u64() % 24)),
389 1 => {
390 cache.get(&encoded(rng.next_u64() % 24));
391 }
392 2 => cache.insert(key(step + 10_000)),
393 _ => cache.set_capacity((rng.next_u64() % 20) as usize),
394 }
395 cache.assert_invariants();
396 }
397 }
398}