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

solana_program/
slot_history.rs
