gemachain_program/
slot_history.rs

1#![allow(clippy::integer_arithmetic)]
2//!
3//! slot history
4//!
5pub use crate::clock::Slot;
6use bv::BitVec;
7use bv::BitsMut;
8
9#[repr(C)]
10#[derive(Clone, Serialize, Deserialize, PartialEq)]
11pub struct SlotHistory {
12    pub bits: BitVec<u64>,
13    pub next_slot: Slot,
14}
15
16impl Default for SlotHistory {
17    fn default() -> Self {
18        let mut bits = BitVec::new_fill(false, MAX_ENTRIES);
19        bits.set(0, true);
20        Self { bits, next_slot: 1 }
21    }
22}
23
24impl std::fmt::Debug for SlotHistory {
25    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
26        write!(f, "SlotHistory {{ slot: {} bits:", self.next_slot)?;
27        for i in 0..MAX_ENTRIES {
28            if self.bits.get(i) {
29                write!(f, "1")?;
30            } else {
31                write!(f, "0")?;
32            }
33        }
34        Ok(())
35    }
36}
37
38pub const MAX_ENTRIES: u64 = 1024 * 1024; // 1 million slots is about 5 days
39
40#[derive(PartialEq, Debug)]
41pub enum Check {
42    Future,
43    TooOld,
44    Found,
45    NotFound,
46}
47
48impl SlotHistory {
49    pub fn add(&mut self, slot: Slot) {
50        if slot > self.next_slot && slot - self.next_slot >= MAX_ENTRIES {
51            // Wrapped past current history,
52            // clear entire bitvec.
53            let full_blocks = (MAX_ENTRIES as usize) / 64;
54            for i in 0..full_blocks {
55                self.bits.set_block(i, 0);
56            }
57        } else {
58            for skipped in self.next_slot..slot {
59                self.bits.set(skipped % MAX_ENTRIES, false);
60            }
61        }
62        self.bits.set(slot % MAX_ENTRIES, true);
63        self.next_slot = slot + 1;
64    }
65
66    pub fn check(&self, slot: Slot) -> Check {
67        if slot > self.newest() {
68            Check::Future
69        } else if slot < self.oldest() {
70            Check::TooOld
71        } else if self.bits.get(slot % MAX_ENTRIES) {
72            Check::Found
73        } else {
74            Check::NotFound
75        }
76    }
77
78    pub fn oldest(&self) -> Slot {
79        self.next_slot.saturating_sub(MAX_ENTRIES)
80    }
81
82    pub fn newest(&self) -> Slot {
83        self.next_slot - 1
84    }
85}
86
87#[cfg(test)]
88mod tests {
89    use super::*;
90    use log::*;
91
92    #[test]
93    fn slot_history_test1() {
94        gemachain_logger::setup();
95        // should be divisible by 64 since the clear logic works on blocks
96        assert_eq!(MAX_ENTRIES % 64, 0);
97        let mut slot_history = SlotHistory::default();
98        info!("add 2");
99        slot_history.add(2);
100        assert_eq!(slot_history.check(0), Check::Found);
101        assert_eq!(slot_history.check(1), Check::NotFound);
102        for i in 3..MAX_ENTRIES {
103            assert_eq!(slot_history.check(i), Check::Future);
104        }
105        info!("add 20");
106        slot_history.add(20);
107        info!("add max_entries");
108        slot_history.add(MAX_ENTRIES);
109        assert_eq!(slot_history.check(0), Check::TooOld);
110        assert_eq!(slot_history.check(1), Check::NotFound);
111        for i in &[2, 20, MAX_ENTRIES] {
112            assert_eq!(slot_history.check(*i), Check::Found);
113        }
114        for i in 3..20 {
115            assert_eq!(slot_history.check(i), Check::NotFound, "i: {}", i);
116        }
117        for i in 21..MAX_ENTRIES {
118            assert_eq!(slot_history.check(i), Check::NotFound, "i: {}", i);
119        }
120        assert_eq!(slot_history.check(MAX_ENTRIES + 1), Check::Future);
121
122        info!("add max_entries + 3");
123        let slot = 3 * MAX_ENTRIES + 3;
124        slot_history.add(slot);
125        for i in &[0, 1, 2, 20, 21, MAX_ENTRIES] {
126            assert_eq!(slot_history.check(*i), Check::TooOld);
127        }
128        let start = slot - MAX_ENTRIES + 1;
129        let end = slot;
130        for i in start..end {
131            assert_eq!(slot_history.check(i), Check::NotFound, "i: {}", i);
132        }
133        assert_eq!(slot_history.check(slot), Check::Found);
134    }
135
136    #[test]
137    fn slot_history_test_wrap() {
138        gemachain_logger::setup();
139        let mut slot_history = SlotHistory::default();
140        info!("add 2");
141        slot_history.add(2);
142        assert_eq!(slot_history.check(0), Check::Found);
143        assert_eq!(slot_history.check(1), Check::NotFound);
144        for i in 3..MAX_ENTRIES {
145            assert_eq!(slot_history.check(i), Check::Future);
146        }
147        info!("add 20");
148        slot_history.add(20);
149        info!("add max_entries + 19");
150        slot_history.add(MAX_ENTRIES + 19);
151        for i in 0..19 {
152            assert_eq!(slot_history.check(i), Check::TooOld);
153        }
154        assert_eq!(slot_history.check(MAX_ENTRIES), Check::NotFound);
155        assert_eq!(slot_history.check(20), Check::Found);
156        assert_eq!(slot_history.check(MAX_ENTRIES + 19), Check::Found);
157        assert_eq!(slot_history.check(20), Check::Found);
158        for i in 21..MAX_ENTRIES + 19 {
159            assert_eq!(slot_history.check(i), Check::NotFound, "found: {}", i);
160        }
161        assert_eq!(slot_history.check(MAX_ENTRIES + 20), Check::Future);
162    }
163
164    #[test]
165    fn slot_history_test_same_index() {
166        gemachain_logger::setup();
167        let mut slot_history = SlotHistory::default();
168        info!("add 3,4");
169        slot_history.add(3);
170        slot_history.add(4);
171        assert_eq!(slot_history.check(1), Check::NotFound);
172        assert_eq!(slot_history.check(2), Check::NotFound);
173        assert_eq!(slot_history.check(3), Check::Found);
174        assert_eq!(slot_history.check(4), Check::Found);
175        slot_history.add(MAX_ENTRIES + 5);
176        assert_eq!(slot_history.check(5), Check::TooOld);
177        for i in 6..MAX_ENTRIES + 5 {
178            assert_eq!(slot_history.check(i), Check::NotFound, "i: {}", i);
179        }
180        assert_eq!(slot_history.check(MAX_ENTRIES + 5), Check::Found);
181    }
182
183    #[test]
184    fn test_older_slot() {
185        let mut slot_history = SlotHistory::default();
186        slot_history.add(10);
187        slot_history.add(5);
188        assert_eq!(slot_history.check(0), Check::Found);
189        assert_eq!(slot_history.check(5), Check::Found);
190        // If we go backwards we reset?
191        assert_eq!(slot_history.check(10), Check::Future);
192        assert_eq!(slot_history.check(6), Check::Future);
193        assert_eq!(slot_history.check(11), Check::Future);
194    }
195
196    #[test]
197    fn test_oldest() {
198        let mut slot_history = SlotHistory::default();
199        assert_eq!(slot_history.oldest(), 0);
200        slot_history.add(10);
201        assert_eq!(slot_history.oldest(), 0);
202        slot_history.add(MAX_ENTRIES - 1);
203        assert_eq!(slot_history.oldest(), 0);
204        slot_history.add(MAX_ENTRIES);
205        assert_eq!(slot_history.oldest(), 1);
206    }
207}
gemachain_program/slot_history.rs

gemachain_program/
slot_history.rs
