miraland_program/
slot_history.rs

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

miraland_program/
slot_history.rs
