solana_slot_history/
lib.rs

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

solana_slot_history/
lib.rs
