sequential_storage/cache/
page_states.rs

1//! Implementation of page state caching
2
3#[cfg(feature = "alloc")]
4extern crate alloc;
5
6use core::fmt::Debug;
7
8use crate::PageState;
9
10pub(crate) trait SealedPageStatesCache {
11    fn get_page_state(&self, page_index: usize) -> Option<PageState>;
12    fn notice_page_state(&mut self, page_index: usize, new_state: PageState);
13    fn invalidate_cache_state(&mut self);
14}
15
16/// A cache that caches the states for all pages
17#[allow(private_bounds)]
18pub trait PageStatesCache: SealedPageStatesCache {}
19
20/// A cache that uses knowledge about the typical layout of pages.
21///
22/// Use the [ArrayPageStates] cache or [HeapPageStates] cache when you have fewer than ~32 pages.
23///
24/// The layout is always as follows:
25/// - X amount of closed pages
26/// - Y amount of open pages
27///   - Y is at least 1
28///   - One of the open pages may be partial
29/// - If a partial page is present, it's in the order ascending page indices: `Closed` -> `Partial` -> `Open`
30///
31/// The idea is to have an anchor which is the first open page (which may be the partial open page)
32/// and then keep track of the amount of open pages in front and the amount of closed pages behind it.
33///
34/// We know the anchor for sure when we find a partial open page.
35/// Since sequential-storage always iterates going forward and never back, we can have a 'guessed' anchor
36/// if we find the first open page. But when the anchor is guessed, we need to be a little pessimistic.
37///
38/// Thus, this cache isn't able to remember every page state in every situation, but this is only the case when
39/// the anchor hasn't been found yet. When the cache is fully warm, it does have perfect knowledge.
40///
41/// We don't have to care about corruption, because when corruption is repaired the cache is invalidated.
42#[cfg_attr(feature = "defmt", derive(defmt::Format))]
43pub struct CalculatedPageStates {
44    page_count: usize,
45    anchor: Option<usize>,
46    anchor_is_partial: bool,
47    anchor_is_guess: bool,
48    closed_pages: usize,
49    open_pages: usize,
50}
51
52impl Debug for CalculatedPageStates {
53    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
54        write!(f, "[")?;
55        for i in 0..self.page_count {
56            write!(
57                f,
58                "{}{i}: {:?}",
59                if i == 0 { "" } else { ", " },
60                self.get_page_state(i)
61            )?;
62        }
63        write!(f, "]")?;
64
65        Ok(())
66    }
67}
68
69impl CalculatedPageStates {
70    /// Create a new empty cache for the amount of pages
71    pub const fn new(page_count: usize) -> Self {
72        Self {
73            page_count,
74            anchor: None,
75            anchor_is_partial: false,
76            anchor_is_guess: true,
77            closed_pages: 0,
78            open_pages: 0,
79        }
80    }
81
82    fn places_in_front_of_anchor(&self, page_index: usize) -> Option<usize> {
83        let anchor = self.anchor?;
84
85        if page_index >= anchor {
86            Some(page_index - anchor)
87        } else {
88            Some(self.page_count - anchor + page_index)
89        }
90    }
91
92    fn places_behind_of_anchor(&self, page_index: usize) -> Option<usize> {
93        let anchor = self.anchor?;
94
95        if page_index <= anchor {
96            Some(anchor - page_index)
97        } else {
98            Some(anchor + 1 + self.page_count - page_index)
99        }
100    }
101}
102
103impl SealedPageStatesCache for CalculatedPageStates {
104    fn get_page_state(&self, page_index: usize) -> Option<PageState> {
105        if self.anchor == Some(page_index) {
106            if self.anchor_is_partial {
107                Some(PageState::PartialOpen)
108            } else {
109                Some(PageState::Open)
110            }
111        } else if let Some(in_front) = self.places_in_front_of_anchor(page_index)
112            && in_front < self.open_pages
113        {
114            Some(PageState::Open)
115        } else if let Some(behind) = self.places_behind_of_anchor(page_index)
116            && behind <= self.closed_pages
117        {
118            Some(PageState::Closed)
119        } else {
120            None
121        }
122    }
123
124    fn notice_page_state(&mut self, page_index: usize, new_state: PageState) {
125        #[cfg(fuzzing)]
126        eprintln!("Noticing page state: {page_index} -> {new_state:?}");
127        #[cfg(fuzzing)]
128        eprintln!("Before {self:?}");
129
130        match new_state {
131            PageState::PartialOpen => {
132                // What do we currently think it is?
133                match self.get_page_state(page_index) {
134                    Some(PageState::PartialOpen) => {
135                        // We've rediscovered ourselves and that's great
136                    }
137                    Some(PageState::Open) => {
138                        self.anchor = Some(page_index);
139                        self.anchor_is_partial = true;
140                    }
141                    Some(PageState::Closed) => {
142                        unreachable!("Can't partially open a closed page")
143                    }
144                    None => {
145                        // Unknown, so we can just become the anchor
146                        self.anchor = Some(page_index);
147                        self.anchor_is_partial = true;
148                        self.open_pages = 1;
149                    }
150                }
151
152                self.anchor_is_guess = false;
153            }
154            PageState::Closed => {
155                // What do we currently think it is?
156                match self.get_page_state(page_index) {
157                    Some(PageState::Closed) => {
158                        // We've rediscovered ourselves and that's great
159                    }
160                    Some(PageState::PartialOpen) => {
161                        let anchor = self.anchor.as_mut().unwrap();
162                        // The anchor moves one up
163                        self.closed_pages += 1;
164                        self.open_pages -= 1;
165                        *anchor = (*anchor + 1) % self.page_count;
166                        self.anchor_is_partial = false;
167                    }
168                    Some(PageState::Open) => {
169                        unreachable!("We never outright close a fully open page")
170                    }
171                    None => {
172                        // If we know the anchor, we can know the minimum amount of closed pages we have
173                        if !self.anchor_is_guess {
174                            if let Some(behind) = self.places_behind_of_anchor(page_index) {
175                                self.closed_pages = self.closed_pages.max(behind);
176                            }
177                        }
178                    }
179                }
180            }
181            PageState::Open => {
182                // What do we currently think it is?
183                match self.get_page_state(page_index) {
184                    Some(PageState::Open) => {
185                        // We've rediscovered ourselves and that's great
186                    }
187                    Some(PageState::PartialOpen) => {
188                        // We're opening our anchor
189                        self.anchor_is_partial = false;
190                    }
191                    Some(PageState::Closed) => {
192                        if let Some(in_front) = self.places_in_front_of_anchor(page_index) {
193                            self.open_pages = self.open_pages.max(in_front + 1);
194                        }
195                        if let Some(behind) =
196                            self.places_behind_of_anchor((page_index + 1) % self.page_count)
197                        {
198                            self.closed_pages = self.closed_pages.min(behind);
199                        }
200                    }
201                    None => {
202                        match self.anchor {
203                            Some(anchor) => {
204                                if self.anchor_is_guess {
205                                    // We're not sure about the anchor, but all open pages are one after each other.
206                                    // Our guessed anchor must be the at the start of the open pages,
207                                    // so if this open page simply extends that, then we can just add it
208                                    if page_index == (anchor + self.open_pages) % self.page_count {
209                                        self.open_pages += 1;
210                                    }
211                                } else {
212                                    if let Some(in_front) =
213                                        self.places_in_front_of_anchor(page_index)
214                                    {
215                                        self.open_pages = self.open_pages.max(in_front + 1);
216                                    }
217                                }
218                            }
219                            None => {
220                                // Become the guessed anchor for now
221                                self.anchor = Some(page_index);
222                                self.anchor_is_partial = false;
223                                self.anchor_is_guess = true;
224                                self.open_pages = 1;
225                                self.closed_pages = 0;
226                            }
227                        }
228                    }
229                }
230            }
231        }
232
233        #[cfg(fuzzing)]
234        eprintln!("Afterwards {self:?}");
235    }
236
237    fn invalidate_cache_state(&mut self) {
238        *self = Self {
239            page_count: self.page_count,
240            ..Self::new(0)
241        };
242    }
243}
244impl PageStatesCache for CalculatedPageStates {}
245
246/// A cache that stores page states in an array.
247#[derive(Debug)]
248#[cfg_attr(feature = "defmt", derive(defmt::Format))]
249pub struct ArrayPageStates<const PAGE_COUNT: usize> {
250    pages: [Option<PageState>; PAGE_COUNT],
251}
252
253impl<const PAGE_COUNT: usize> ArrayPageStates<PAGE_COUNT> {
254    /// Create a new empty cache
255    pub const fn new() -> Self {
256        Self {
257            pages: [None; PAGE_COUNT],
258        }
259    }
260}
261
262impl<const PAGE_COUNT: usize> Default for ArrayPageStates<PAGE_COUNT> {
263    fn default() -> Self {
264        Self::new()
265    }
266}
267
268impl<const PAGE_COUNT: usize> SealedPageStatesCache for ArrayPageStates<PAGE_COUNT> {
269    fn get_page_state(&self, page_index: usize) -> Option<PageState> {
270        self.pages[page_index]
271    }
272
273    fn notice_page_state(&mut self, page_index: usize, new_state: PageState) {
274        self.pages[page_index] = Some(new_state);
275    }
276
277    fn invalidate_cache_state(&mut self) {
278        for page in self.pages.iter_mut() {
279            *page = None;
280        }
281    }
282}
283impl<const PAGE_COUNT: usize> PageStatesCache for ArrayPageStates<PAGE_COUNT> {}
284
285#[cfg(feature = "alloc")]
286/// A cache that stores page states in a vec.
287#[derive(Debug)]
288#[cfg_attr(feature = "defmt", derive(defmt::Format))]
289pub struct HeapPageStates {
290    pages: alloc::vec::Vec<Option<PageState>>,
291}
292
293#[cfg(feature = "alloc")]
294impl HeapPageStates {
295    /// Create a new empty cache
296    pub fn new(page_count: usize) -> Self {
297        Self {
298            pages: alloc::vec![None; page_count],
299        }
300    }
301}
302
303#[cfg(feature = "alloc")]
304impl SealedPageStatesCache for HeapPageStates {
305    fn get_page_state(&self, page_index: usize) -> Option<PageState> {
306        self.pages[page_index]
307    }
308
309    fn notice_page_state(&mut self, page_index: usize, new_state: PageState) {
310        self.pages[page_index] = Some(new_state);
311    }
312
313    fn invalidate_cache_state(&mut self) {
314        for page in self.pages.iter_mut() {
315            *page = None;
316        }
317    }
318}
319#[cfg(feature = "alloc")]
320impl PageStatesCache for HeapPageStates {}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    #[test]
327    fn page_states_correct_from_erased() {
328        let mut page_states = CalculatedPageStates::new(4);
329
330        assert_eq!(page_states.get_page_state(0), None);
331        assert_eq!(page_states.get_page_state(1), None);
332        assert_eq!(page_states.get_page_state(2), None);
333        assert_eq!(page_states.get_page_state(3), None);
334
335        page_states.notice_page_state(0, PageState::Open);
336        page_states.notice_page_state(1, PageState::Open);
337        page_states.notice_page_state(2, PageState::Open);
338        page_states.notice_page_state(3, PageState::Open);
339
340        assert_eq!(page_states.get_page_state(0), Some(PageState::Open));
341        assert_eq!(page_states.get_page_state(1), Some(PageState::Open));
342        assert_eq!(page_states.get_page_state(2), Some(PageState::Open));
343        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
344
345        page_states.notice_page_state(0, PageState::PartialOpen);
346
347        assert_eq!(page_states.get_page_state(0), Some(PageState::PartialOpen));
348        assert_eq!(page_states.get_page_state(1), Some(PageState::Open));
349        assert_eq!(page_states.get_page_state(2), Some(PageState::Open));
350        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
351
352        page_states.notice_page_state(0, PageState::Closed);
353
354        assert_eq!(page_states.get_page_state(0), Some(PageState::Closed));
355        assert_eq!(page_states.get_page_state(1), Some(PageState::Open));
356        assert_eq!(page_states.get_page_state(2), Some(PageState::Open));
357        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
358
359        page_states.notice_page_state(1, PageState::PartialOpen);
360
361        assert_eq!(page_states.get_page_state(0), Some(PageState::Closed));
362        assert_eq!(page_states.get_page_state(1), Some(PageState::PartialOpen));
363        assert_eq!(page_states.get_page_state(2), Some(PageState::Open));
364        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
365
366        page_states.notice_page_state(0, PageState::Open);
367
368        assert_eq!(page_states.get_page_state(0), Some(PageState::Open));
369        assert_eq!(page_states.get_page_state(1), Some(PageState::PartialOpen));
370        assert_eq!(page_states.get_page_state(2), Some(PageState::Open));
371        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
372    }
373
374    #[test]
375    fn page_states_correct_from_recover() {
376        let mut page_states = CalculatedPageStates::new(4);
377
378        println!("{page_states:?}");
379        page_states.notice_page_state(3, PageState::PartialOpen);
380        println!("{page_states:?}");
381        page_states.notice_page_state(0, PageState::Closed);
382        println!("{page_states:?}");
383        page_states.notice_page_state(3, PageState::Open);
384        println!("{page_states:?}");
385
386        assert_eq!(page_states.get_page_state(0), Some(PageState::Closed));
387        assert_eq!(page_states.get_page_state(1), Some(PageState::Closed));
388        assert_eq!(page_states.get_page_state(2), Some(PageState::Closed));
389        assert_eq!(page_states.get_page_state(3), Some(PageState::Open));
390    }
391}
sequential_storage/cache/page_states.rs

sequential_storage/cache/
page_states.rs
