hypercall_engine/
nonce.rs

1use serde::{Deserialize, Serialize};
2use std::collections::BTreeSet;
3
4pub const DEFAULT_NONCE_SET_CAPACITY: usize = 100;
5pub const TWO_DAYS_MS: u64 = 2 * 24 * 60 * 60 * 1000;
6pub const ONE_DAY_MS: u64 = 24 * 60 * 60 * 1000;
7
8#[derive(Debug, Clone, Serialize)]
9pub struct BoundedNonceSet {
10    nonces: BTreeSet<u64>,
11    capacity: usize,
12}
13
14impl<'de> Deserialize<'de> for BoundedNonceSet {
15    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
16    where
17        D: serde::Deserializer<'de>,
18    {
19        #[derive(Deserialize)]
20        struct Raw {
21            nonces: BTreeSet<u64>,
22            capacity: usize,
23        }
24        let raw = Raw::deserialize(deserializer)?;
25        if raw.capacity == 0 {
26            panic!(
27                "STATE_CORRUPTION: BoundedNonceSet deserialized with capacity=0 \
28                 ({} nonces). Persisted state is invalid.",
29                raw.nonces.len()
30            );
31        }
32        let mut set = Self {
33            nonces: raw.nonces,
34            capacity: raw.capacity,
35        };
36        while set.nonces.len() > set.capacity {
37            if let Some(&min) = set.nonces.iter().next() {
38                set.nonces.remove(&min);
39            }
40        }
41        Ok(set)
42    }
43}
44
45impl BoundedNonceSet {
46    pub fn new(capacity: usize) -> Self {
47        assert!(capacity > 0);
48        Self {
49            nonces: BTreeSet::new(),
50            capacity,
51        }
52    }
53
54    pub fn purge_expired(&mut self, now_ms: u64) {
55        let cutoff = now_ms.saturating_sub(TWO_DAYS_MS);
56        self.nonces.retain(|&n| n > cutoff);
57    }
58
59    pub fn admits(&self, nonce: u64) -> bool {
60        if self.nonces.contains(&nonce) {
61            return false;
62        }
63        if self.nonces.len() < self.capacity {
64            return true;
65        }
66        // Full set: nonce must be greater than the smallest stored nonce
67        nonce > *self.nonces.iter().next().unwrap()
68    }
69
70    pub fn insert(&mut self, nonce: u64) -> bool {
71        if !self.admits(nonce) {
72            return false;
73        }
74        self.nonces.insert(nonce);
75        while self.nonces.len() > self.capacity {
76            if let Some(&min) = self.nonces.iter().next() {
77                self.nonces.remove(&min);
78            }
79        }
80        true
81    }
82
83    pub fn min(&self) -> Option<u64> {
84        self.nonces.iter().next().copied()
85    }
86
87    pub fn count(&self) -> usize {
88        self.nonces.len()
89    }
90
91    pub fn capacity(&self) -> usize {
92        self.capacity
93    }
94
95    pub fn contains(&self, nonce: &u64) -> bool {
96        self.nonces.contains(nonce)
97    }
98
99    pub fn iter(&self) -> impl Iterator<Item = &u64> {
100        self.nonces.iter()
101    }
102
103    pub fn to_vec(&self) -> Vec<u64> {
104        self.nonces.iter().copied().collect()
105    }
106
107    pub fn from_vec(nonces: Vec<u64>, capacity: usize) -> Self {
108        let mut set = Self::new(capacity);
109        for n in nonces {
110            set.nonces.insert(n);
111        }
112        while set.nonces.len() > capacity {
113            if let Some(&min) = set.nonces.iter().next() {
114                set.nonces.remove(&min);
115            }
116        }
117        set
118    }
119}
120
121pub fn nonce_within_time_bounds(nonce: u64, command_timestamp_ms: u64) -> bool {
122    let lower = command_timestamp_ms.saturating_sub(TWO_DAYS_MS);
123    let upper = command_timestamp_ms.saturating_add(ONE_DAY_MS);
124    nonce > lower && nonce < upper
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    #[test]
132    fn empty_set_admits_any_nonce() {
133        let set = BoundedNonceSet::new(3);
134        assert!(set.admits(0));
135        assert!(set.admits(42));
136        assert!(set.admits(u64::MAX));
137    }
138
139    #[test]
140    fn insert_and_contains() {
141        let mut set = BoundedNonceSet::new(3);
142        assert!(set.insert(10));
143        assert!(set.contains(&10));
144        assert!(!set.contains(&11));
145    }
146
147    #[test]
148    fn rejects_duplicate_nonce() {
149        let mut set = BoundedNonceSet::new(3);
150        assert!(set.insert(10));
151        assert!(!set.insert(10));
152        assert!(!set.admits(10));
153    }
154
155    #[test]
156    fn evicts_smallest_when_full() {
157        let mut set = BoundedNonceSet::new(3);
158        assert!(set.insert(10));
159        assert!(set.insert(20));
160        assert!(set.insert(30));
161        assert_eq!(set.count(), 3);
162
163        // Insert 40 → evicts 10
164        assert!(set.insert(40));
165        assert_eq!(set.count(), 3);
166        assert!(!set.contains(&10));
167        assert!(set.contains(&20));
168        assert!(set.contains(&30));
169        assert!(set.contains(&40));
170    }
171
172    #[test]
173    fn rejects_below_min_when_full() {
174        let mut set = BoundedNonceSet::new(3);
175        assert!(set.insert(10));
176        assert!(set.insert(20));
177        assert!(set.insert(30));
178
179        // 5 < min(10), rejected
180        assert!(!set.admits(5));
181        assert!(!set.insert(5));
182        // 10 == min, but already in set
183        assert!(!set.admits(10));
184    }
185
186    #[test]
187    fn admits_above_min_when_full() {
188        let mut set = BoundedNonceSet::new(3);
189        assert!(set.insert(10));
190        assert!(set.insert(20));
191        assert!(set.insert(30));
192
193        // 15 > min(10) and not in set
194        assert!(set.admits(15));
195        assert!(set.insert(15));
196        // 10 evicted, set is now {15, 20, 30}
197        assert!(!set.contains(&10));
198        assert_eq!(set.min(), Some(15));
199    }
200
201    #[test]
202    fn out_of_order_nonces_work() {
203        let mut set = BoundedNonceSet::new(100);
204        assert!(set.insert(100));
205        assert!(set.insert(50));
206        assert!(set.insert(75));
207        assert_eq!(set.count(), 3);
208        assert_eq!(set.min(), Some(50));
209    }
210
211    #[test]
212    fn to_vec_is_sorted() {
213        let mut set = BoundedNonceSet::new(100);
214        set.insert(30);
215        set.insert(10);
216        set.insert(20);
217        assert_eq!(set.to_vec(), vec![10, 20, 30]);
218    }
219
220    #[test]
221    fn from_vec_roundtrip() {
222        let mut set = BoundedNonceSet::new(3);
223        set.insert(10);
224        set.insert(20);
225        set.insert(30);
226        let v = set.to_vec();
227        let restored = BoundedNonceSet::from_vec(v, 3);
228        assert_eq!(restored.count(), 3);
229        assert_eq!(restored.min(), Some(10));
230        assert!(restored.contains(&20));
231    }
232
233    #[test]
234    fn from_vec_truncates_to_capacity() {
235        let restored = BoundedNonceSet::from_vec(vec![1, 2, 3, 4, 5], 3);
236        assert_eq!(restored.count(), 3);
237        assert_eq!(restored.min(), Some(3));
238    }
239
240    #[test]
241    fn time_bounds_accept_valid() {
242        let now = 1_700_000_000_000u64;
243        assert!(nonce_within_time_bounds(now, now));
244        assert!(nonce_within_time_bounds(now - ONE_DAY_MS, now));
245        assert!(nonce_within_time_bounds(now + 60_000, now));
246    }
247
248    #[test]
249    fn time_bounds_reject_too_old() {
250        let now = 1_700_000_000_000u64;
251        assert!(!nonce_within_time_bounds(now - TWO_DAYS_MS - 1, now));
252    }
253
254    #[test]
255    fn time_bounds_reject_too_far_future() {
256        let now = 1_700_000_000_000u64;
257        assert!(!nonce_within_time_bounds(now + ONE_DAY_MS + 1, now));
258    }
259
260    #[test]
261    fn time_bounds_saturating_near_zero() {
262        assert!(nonce_within_time_bounds(1, 1000));
263    }
264
265    #[test]
266    fn purge_expired_removes_old_nonces() {
267        let mut set = BoundedNonceSet::new(100);
268        let now = 1_700_000_000_000u64;
269        let old = now - TWO_DAYS_MS - 1000;
270        let recent = now - ONE_DAY_MS;
271
272        set.insert(old);
273        set.insert(old + 1);
274        set.insert(recent);
275        assert_eq!(set.count(), 3);
276
277        set.purge_expired(now);
278        assert_eq!(set.count(), 1);
279        assert!(!set.contains(&old));
280        assert!(set.contains(&recent));
281    }
282
283    #[test]
284    fn purge_expired_frees_capacity_for_new_nonces() {
285        let mut set = BoundedNonceSet::new(3);
286        let now = 1_700_000_000_000u64;
287        let old = now - TWO_DAYS_MS - 1000;
288
289        set.insert(old);
290        set.insert(old + 1);
291        set.insert(old + 2);
292        assert_eq!(set.count(), 3);
293        assert_eq!(set.min(), Some(old));
294
295        set.purge_expired(now);
296        assert_eq!(set.count(), 0);
297        assert!(set.insert(now));
298        assert!(set.insert(now + 1));
299        assert!(set.insert(now + 2));
300        assert_eq!(set.count(), 3);
301    }
302
303    #[test]
304    fn bench_insert_full_set() {
305        let mut set = BoundedNonceSet::new(DEFAULT_NONCE_SET_CAPACITY);
306        let base = 1_700_000_000_000u64;
307        for i in 0..DEFAULT_NONCE_SET_CAPACITY as u64 {
308            set.insert(base + i);
309        }
310        assert_eq!(set.count(), DEFAULT_NONCE_SET_CAPACITY);
311
312        let start = std::time::Instant::now();
313        let iterations = 10_000;
314        for i in 0..iterations {
315            set.insert(base + DEFAULT_NONCE_SET_CAPACITY as u64 + i);
316        }
317        let elapsed = start.elapsed();
318        let per_op_ns = elapsed.as_nanos() / iterations as u128;
319        assert!(
320            per_op_ns < 10_000,
321            "insert on full set took {}ns/op (expected <10us)",
322            per_op_ns
323        );
324    }
325
326    #[test]
327    fn bench_admits_full_set() {
328        let mut set = BoundedNonceSet::new(DEFAULT_NONCE_SET_CAPACITY);
329        let base = 1_700_000_000_000u64;
330        for i in 0..DEFAULT_NONCE_SET_CAPACITY as u64 {
331            set.insert(base + i);
332        }
333
334        let start = std::time::Instant::now();
335        let iterations = 100_000;
336        for i in 0..iterations {
337            std::hint::black_box(set.admits(base + DEFAULT_NONCE_SET_CAPACITY as u64 + i));
338        }
339        let elapsed = start.elapsed();
340        let per_op_ns = elapsed.as_nanos() / iterations as u128;
341        assert!(
342            per_op_ns < 1_000,
343            "admits on full set took {}ns/op (expected <1us)",
344            per_op_ns
345        );
346    }
347
348    #[test]
349    fn bench_purge_expired_full_set() {
350        let now = 1_700_000_000_000u64;
351        let old = now - TWO_DAYS_MS - 1000;
352        let mut set = BoundedNonceSet::new(DEFAULT_NONCE_SET_CAPACITY);
353        for i in 0..DEFAULT_NONCE_SET_CAPACITY as u64 {
354            set.insert(old + i);
355        }
356
357        let start = std::time::Instant::now();
358        let iterations = 10_000;
359        for _ in 0..iterations {
360            let mut s = set.clone();
361            s.purge_expired(now);
362        }
363        let elapsed = start.elapsed();
364        let per_op_ns = elapsed.as_nanos() / iterations as u128;
365        assert!(
366            per_op_ns < 50_000,
367            "purge_expired on full set took {}ns/op (expected <50us)",
368            per_op_ns
369        );
370    }
371}
hypercall_engine/nonce.rs

hypercall_engine/
nonce.rs
