Skip to main content

ed25519_simd/
hot_key_cache.rs

1use crate::cache::{CachedPublicKey, KeyCache};
2use crate::input::PUBLIC_KEY_LEN;
3use std::cell::Cell;
4use std::collections::HashMap;
5
6/// Link sentinel for the ends of the recency list.
7const NONE: usize = usize::MAX;
8
9/// One retained public key and its slot-indexed links in the LRU list.
10///
11/// A cache hit detaches this slot and relinks it at the MRU end
12/// without moving the key or allocating a list node.
13#[derive(Debug)]
14struct CacheEntry {
15    key: CachedPublicKey,
16    // Intrusive recency-list links, as slot indices into `entries`. `newer`
17    // runs toward the most-recently-used end.
18    newer: Cell<usize>,
19    older: Cell<usize>,
20}
21
22/// A bounded LRU [`KeyCache`] for decoded keys.
23///
24/// # Memory
25///
26/// A retained key costs roughly 2.8 KB, nearly all of it its 17-entry
27/// multiplication table. [`with_capacity`](Self::with_capacity) reserves
28/// allocator capacity for the whole bound, but pages generally become resident
29/// as entries are written. Size the bound from measured key reuse, or use
30/// [`NullKeyCache`](crate::NullKeyCache).
31///
32/// Verifying another signature from a retained key reuses its
33/// decoded multiplication table instead of decompressing and tabulating it.
34#[derive(Debug)]
35pub struct HotKeyCache {
36    // Slot-indexed entries linked by recency give O(1) lookup and eviction.
37    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    /// Create a cache holding at most `capacity` keys, clamped to at least one.
46    /// Reserves allocator capacity for the whole bound; see [Memory](Self#memory).
47    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    /// Set the maximum retained key count, clamped to at least one. Lowering it
59    /// evicts excess keys and requests smaller backing allocations (the
60    /// allocator may retain freed memory); raising it reserves for the new
61    /// bound, like [`with_capacity`](Self::with_capacity).
62    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            // Slot indices survive a reallocation, so the recency links stay
67            // valid across both the shrink and the reserve.
68            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    /// Detach `slot` from the recency list.
77    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    /// Attach an already-detached `slot` at the most-recently-used end.
93    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    /// Evict LRU entries until the count fits the bound.
113    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        // Repoint links from the old last slot to its post-`swap_remove` slot.
127        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    /// Cross-check both recency-list directions against `entries` and `index`.
144    #[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    /// Give each index a distinct encoding over the shared identity table.
244    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        // Touch 0 and 2, leaving 1 as the LRU.
258        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        // Ensure distinct-key churn cannot evict a repeatedly touched hot set.
279        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        // Re-inserting 0 must refresh it rather than add a second entry.
301        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        // Shrinking keeps the most recently used keys.
322        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    /// Exercise link relocation under mixed operations and capacity changes.
381    #[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}