sequential_storage/cache/
mod.rs

1//! Module implementing all things cache related
2
3use core::{fmt::Debug, ops::Range};
4
5use embedded_storage_async::nor_flash::NorFlash;
6
7use crate::{PageState, item::ItemHeader, map::Key};
8
9use self::{
10    key_pointers::{CachedKeyPointers, KeyPointersCache, UncachedKeyPointers},
11    page_pointers::{CachedPagePointers, UncachedPagePointers},
12    page_states::{CachedPageStates, UncachedPageStates},
13};
14
15pub(crate) mod key_pointers;
16pub(crate) mod page_pointers;
17pub(crate) mod page_states;
18mod tests;
19
20pub(crate) use page_pointers::PagePointersCache;
21pub(crate) use page_states::PageStatesCache;
22
23/// Trait implemented by all cache types
24#[allow(private_bounds)]
25pub trait CacheImpl: PrivateCacheImpl {}
26
27/// Trait implemented by all cache types that know about keys
28#[allow(private_bounds)]
29pub trait KeyCacheImpl<KEY: Key>: CacheImpl + PrivateKeyCacheImpl<KEY> {}
30
31pub(crate) trait Invalidate {
32    fn invalidate_cache_state(&mut self);
33}
34
35impl<T: Invalidate> Invalidate for &mut T {
36    fn invalidate_cache_state(&mut self) {
37        T::invalidate_cache_state(self)
38    }
39}
40
41pub(crate) trait PrivateCacheImpl: Invalidate {
42    type PSC: PageStatesCache;
43    type PPC: PagePointersCache;
44
45    fn dirt_tracker<R>(&mut self, f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R>;
46    fn page_states(&mut self) -> &mut Self::PSC;
47    fn page_pointers(&mut self) -> &mut Self::PPC;
48
49    /// True if the cache might be inconsistent
50    fn is_dirty(&mut self) -> bool {
51        self.dirt_tracker(|d| d.is_dirty()).unwrap_or_default()
52    }
53
54    /// Mark the cache as potentially inconsistent with reality
55    fn mark_dirty(&mut self) {
56        self.dirt_tracker(|d| d.mark_dirty());
57    }
58
59    /// Mark the cache as being consistent with reality
60    fn unmark_dirty(&mut self) {
61        self.dirt_tracker(|d| d.unmark_dirty());
62    }
63
64    /// Get the cache state of the requested page
65    fn get_page_state(&mut self, page_index: usize) -> Option<PageState> {
66        self.page_states().get_page_state(page_index)
67    }
68
69    /// Let the cache know a page state changed
70    ///
71    /// The dirty flag should be true if the page state is actually going to be changed.
72    /// Keep it false if we're only discovering the state.
73    fn notice_page_state(&mut self, page_index: usize, new_state: PageState, dirty: bool) {
74        if dirty {
75            self.mark_dirty();
76        }
77        self.page_states().notice_page_state(page_index, new_state);
78        self.page_pointers()
79            .notice_page_state(page_index, new_state);
80    }
81
82    /// Get the cached address of the first non-erased item in the requested page.
83    ///
84    /// This is purely for the items that get erased from start to end.
85    fn first_item_after_erased(&mut self, page_index: usize) -> Option<u32> {
86        self.page_pointers().first_item_after_erased(page_index)
87    }
88
89    /// Get the cached address of the first free unwritten item in the requested page.
90    fn first_item_after_written(&mut self, page_index: usize) -> Option<u32> {
91        self.page_pointers().first_item_after_written(page_index)
92    }
93
94    /// Let the cache know that an item has been written to flash
95    fn notice_item_written<S: NorFlash>(
96        &mut self,
97        flash_range: Range<u32>,
98        item_address: u32,
99        item_header: &ItemHeader,
100    ) {
101        self.mark_dirty();
102        self.page_pointers()
103            .notice_item_written::<S>(flash_range, item_address, item_header)
104    }
105
106    /// Let the cache know that an item has been erased from flash
107    fn notice_item_erased<S: NorFlash>(
108        &mut self,
109        flash_range: Range<u32>,
110        item_address: u32,
111        item_header: &ItemHeader,
112    ) {
113        self.mark_dirty();
114        self.page_pointers()
115            .notice_item_erased::<S>(flash_range, item_address, item_header)
116    }
117}
118
119impl<T: PrivateCacheImpl> PrivateCacheImpl for &mut T {
120    type PSC = T::PSC;
121    type PPC = T::PPC;
122
123    fn dirt_tracker<R>(&mut self, f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R> {
124        T::dirt_tracker(self, f)
125    }
126
127    fn page_states(&mut self) -> &mut Self::PSC {
128        T::page_states(self)
129    }
130
131    fn page_pointers(&mut self) -> &mut Self::PPC {
132        T::page_pointers(self)
133    }
134}
135
136pub(crate) trait PrivateKeyCacheImpl<KEY: Key>: PrivateCacheImpl {
137    type KPC: KeyPointersCache<KEY>;
138
139    fn key_pointers(&mut self) -> &mut Self::KPC;
140
141    fn key_location(&mut self, key: &KEY) -> Option<u32> {
142        self.key_pointers().key_location(key)
143    }
144
145    fn notice_key_location(&mut self, key: &KEY, item_address: u32, dirty: bool) {
146        if dirty {
147            self.mark_dirty();
148        }
149        self.key_pointers().notice_key_location(key, item_address)
150    }
151    #[allow(unused)]
152    fn notice_key_erased(&mut self, key: &KEY) {
153        self.mark_dirty();
154        self.key_pointers().notice_key_erased(key)
155    }
156}
157
158impl<KEY: Key, T: PrivateKeyCacheImpl<KEY>> PrivateKeyCacheImpl<KEY> for &mut T {
159    type KPC = T::KPC;
160
161    fn key_pointers(&mut self) -> &mut Self::KPC {
162        T::key_pointers(self)
163    }
164}
165
166#[derive(Debug)]
167#[cfg_attr(feature = "defmt-03", derive(defmt::Format))]
168pub(crate) struct DirtTracker {
169    /// Managed from the library code.
170    ///
171    /// When true, the cache and/or flash has changed and things might not be fully
172    /// consistent if there's an early return due to error.
173    dirty: bool,
174}
175
176impl DirtTracker {
177    pub const fn new() -> Self {
178        DirtTracker { dirty: false }
179    }
180
181    /// True if the cache might be inconsistent
182    pub fn is_dirty(&self) -> bool {
183        self.dirty
184    }
185
186    /// Mark the cache as potentially inconsistent with reality
187    pub fn mark_dirty(&mut self) {
188        self.dirty = true;
189    }
190
191    /// Mark the cache as being consistent with reality
192    pub fn unmark_dirty(&mut self) {
193        self.dirty = false;
194    }
195}
196
197/// A cache object implementing no cache.
198///
199/// This type of cache doesn't have to be kept around and may be constructed on every api call.
200/// You could simply pass `&mut NoCache::new()` every time.
201#[derive(Debug)]
202#[cfg_attr(feature = "defmt-03", derive(defmt::Format))]
203pub struct NoCache {
204    page_states: UncachedPageStates,
205    page_pointers: UncachedPagePointers,
206    key_pointers: UncachedKeyPointers,
207}
208
209impl NoCache {
210    /// Construct a new instance
211    pub const fn new() -> Self {
212        Self {
213            page_states: UncachedPageStates,
214            page_pointers: UncachedPagePointers,
215            key_pointers: UncachedKeyPointers,
216        }
217    }
218}
219
220impl Default for NoCache {
221    fn default() -> Self {
222        Self::new()
223    }
224}
225
226impl PrivateCacheImpl for NoCache {
227    type PSC = UncachedPageStates;
228    type PPC = UncachedPagePointers;
229
230    fn dirt_tracker<R>(&mut self, _f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R> {
231        // We have no state, so no need to track dirtyness
232        None
233    }
234
235    fn page_states(&mut self) -> &mut Self::PSC {
236        &mut self.page_states
237    }
238
239    fn page_pointers(&mut self) -> &mut Self::PPC {
240        &mut self.page_pointers
241    }
242}
243
244impl CacheImpl for NoCache {}
245impl<KEY: Key> KeyCacheImpl<KEY> for NoCache {}
246
247impl Invalidate for NoCache {
248    fn invalidate_cache_state(&mut self) {}
249}
250
251impl<KEY: Key> PrivateKeyCacheImpl<KEY> for NoCache {
252    type KPC = UncachedKeyPointers;
253
254    fn key_pointers(&mut self) -> &mut Self::KPC {
255        &mut self.key_pointers
256    }
257}
258
259/// A cache object that keeps track of the page states.
260///
261/// This cache has to be kept around and passed to *every* api call to the same memory region until the cache gets discarded.
262///
263/// Valid usecase:  
264/// `Create cache 1` -> `use 1` -> `use 1` -> `create cache 2` -> `use 2` -> `use 2`
265///
266/// Invalid usecase:  
267/// `Create cache 1` -> `use 1` -> `create cache 2` -> `use 2` -> `❌ use 1 ❌`
268///
269/// Make sure the page count is correct. If the number is lower than the actual amount, the code will panic at some point.
270#[derive(Debug)]
271#[cfg_attr(feature = "defmt-03", derive(defmt::Format))]
272pub struct PageStateCache<const PAGE_COUNT: usize> {
273    dirt_tracker: DirtTracker,
274    page_states: CachedPageStates<PAGE_COUNT>,
275    page_pointers: UncachedPagePointers,
276    key_pointers: UncachedKeyPointers,
277}
278
279impl<const PAGE_COUNT: usize> PageStateCache<PAGE_COUNT> {
280    /// Construct a new instance
281    pub const fn new() -> Self {
282        Self {
283            dirt_tracker: DirtTracker::new(),
284            page_states: CachedPageStates::new(),
285            page_pointers: UncachedPagePointers,
286            key_pointers: UncachedKeyPointers,
287        }
288    }
289}
290
291impl<const PAGE_COUNT: usize> Default for PageStateCache<PAGE_COUNT> {
292    fn default() -> Self {
293        Self::new()
294    }
295}
296
297impl<const PAGE_COUNT: usize> PrivateCacheImpl for PageStateCache<PAGE_COUNT> {
298    type PSC = CachedPageStates<PAGE_COUNT>;
299    type PPC = UncachedPagePointers;
300
301    fn dirt_tracker<R>(&mut self, f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R> {
302        Some(f(&mut self.dirt_tracker))
303    }
304
305    fn page_states(&mut self) -> &mut Self::PSC {
306        &mut self.page_states
307    }
308
309    fn page_pointers(&mut self) -> &mut Self::PPC {
310        &mut self.page_pointers
311    }
312}
313
314impl<const PAGE_COUNT: usize> CacheImpl for PageStateCache<PAGE_COUNT> {}
315impl<KEY: Key, const PAGE_COUNT: usize> KeyCacheImpl<KEY> for PageStateCache<PAGE_COUNT> {}
316
317impl<const PAGE_COUNT: usize> Invalidate for PageStateCache<PAGE_COUNT> {
318    fn invalidate_cache_state(&mut self) {
319        self.dirt_tracker.unmark_dirty();
320        self.page_states.invalidate_cache_state();
321        self.page_pointers.invalidate_cache_state();
322    }
323}
324
325impl<KEY: Key, const PAGE_COUNT: usize> PrivateKeyCacheImpl<KEY> for PageStateCache<PAGE_COUNT> {
326    type KPC = UncachedKeyPointers;
327
328    fn key_pointers(&mut self) -> &mut Self::KPC {
329        &mut self.key_pointers
330    }
331}
332
333/// A cache object that keeps track of the page states and some pointers to the items in the page.
334///
335/// This cache has to be kept around and passed to *every* api call to the same memory region until the cache gets discarded.
336///
337/// Valid usecase:  
338/// `Create cache 1` -> `use 1` -> `use 1` -> `create cache 2` -> `use 2` -> `use 2`
339///
340/// Invalid usecase:  
341/// `Create cache 1` -> `use 1` -> `create cache 2` -> `use 2` -> `❌ use 1 ❌`
342///
343/// Make sure the page count is correct. If the number is lower than the actual amount, the code will panic at some point.
344#[derive(Debug)]
345#[cfg_attr(feature = "defmt-03", derive(defmt::Format))]
346pub struct PagePointerCache<const PAGE_COUNT: usize> {
347    dirt_tracker: DirtTracker,
348    page_states: CachedPageStates<PAGE_COUNT>,
349    page_pointers: CachedPagePointers<PAGE_COUNT>,
350    key_pointers: UncachedKeyPointers,
351}
352
353impl<const PAGE_COUNT: usize> PagePointerCache<PAGE_COUNT> {
354    /// Construct a new instance
355    pub const fn new() -> Self {
356        Self {
357            dirt_tracker: DirtTracker::new(),
358            page_states: CachedPageStates::new(),
359            page_pointers: CachedPagePointers::new(),
360            key_pointers: UncachedKeyPointers,
361        }
362    }
363}
364
365impl<const PAGE_COUNT: usize> Default for PagePointerCache<PAGE_COUNT> {
366    fn default() -> Self {
367        Self::new()
368    }
369}
370
371impl<const PAGE_COUNT: usize> PrivateCacheImpl for PagePointerCache<PAGE_COUNT> {
372    type PSC = CachedPageStates<PAGE_COUNT>;
373    type PPC = CachedPagePointers<PAGE_COUNT>;
374
375    fn dirt_tracker<R>(&mut self, f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R> {
376        Some(f(&mut self.dirt_tracker))
377    }
378
379    fn page_states(&mut self) -> &mut Self::PSC {
380        &mut self.page_states
381    }
382
383    fn page_pointers(&mut self) -> &mut Self::PPC {
384        &mut self.page_pointers
385    }
386}
387
388impl<const PAGE_COUNT: usize> CacheImpl for PagePointerCache<PAGE_COUNT> {}
389impl<KEY: Key, const PAGE_COUNT: usize> KeyCacheImpl<KEY> for PagePointerCache<PAGE_COUNT> {}
390
391impl<const PAGE_COUNT: usize> Invalidate for PagePointerCache<PAGE_COUNT> {
392    fn invalidate_cache_state(&mut self) {
393        self.dirt_tracker.unmark_dirty();
394        self.page_states.invalidate_cache_state();
395        self.page_pointers.invalidate_cache_state();
396    }
397}
398
399impl<KEY: Key, const PAGE_COUNT: usize> PrivateKeyCacheImpl<KEY> for PagePointerCache<PAGE_COUNT> {
400    type KPC = UncachedKeyPointers;
401
402    fn key_pointers(&mut self) -> &mut Self::KPC {
403        &mut self.key_pointers
404    }
405}
406
407/// An object that caches the location of the newest item with a given key.
408/// This cache also caches pages states and page pointers.
409///
410/// This cache has to be kept around and passed to *every* api call to the same memory region until the cache gets discarded.
411///
412/// Valid usecase:  
413/// `Create cache 1` -> `use 1` -> `use 1` -> `create cache 2` -> `use 2` -> `use 2`
414///
415/// Invalid usecase:  
416/// `Create cache 1` -> `use 1` -> `create cache 2` -> `use 2` -> `❌ use 1 ❌`
417///
418/// Make sure the page count is correct. If the number is lower than the actual amount, the code will panic at some point.
419///
420/// The number of key slots can be lower than the total amount of possible keys used, but this will lower
421/// the chance of a cache hit.
422/// The keys are cached in a fifo and any time its location is updated in cache it's added to the front.
423#[derive(Debug)]
424#[cfg_attr(feature = "defmt-03", derive(defmt::Format))]
425pub struct KeyPointerCache<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> {
426    dirt_tracker: DirtTracker,
427    page_states: CachedPageStates<PAGE_COUNT>,
428    page_pointers: CachedPagePointers<PAGE_COUNT>,
429    key_pointers: CachedKeyPointers<KEY, KEYS>,
430}
431
432impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> KeyPointerCache<PAGE_COUNT, KEY, KEYS> {
433    /// Construct a new instance
434    pub const fn new() -> Self {
435        Self {
436            dirt_tracker: DirtTracker::new(),
437            page_states: CachedPageStates::new(),
438            page_pointers: CachedPagePointers::new(),
439            key_pointers: CachedKeyPointers::new(),
440        }
441    }
442}
443
444impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> Default
445    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
446{
447    fn default() -> Self {
448        Self::new()
449    }
450}
451
452impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> PrivateCacheImpl
453    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
454{
455    type PSC = CachedPageStates<PAGE_COUNT>;
456    type PPC = CachedPagePointers<PAGE_COUNT>;
457
458    fn dirt_tracker<R>(&mut self, f: impl FnOnce(&mut DirtTracker) -> R) -> Option<R> {
459        Some(f(&mut self.dirt_tracker))
460    }
461
462    fn page_states(&mut self) -> &mut Self::PSC {
463        &mut self.page_states
464    }
465
466    fn page_pointers(&mut self) -> &mut Self::PPC {
467        &mut self.page_pointers
468    }
469}
470
471impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> CacheImpl
472    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
473{
474}
475impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> KeyCacheImpl<KEY>
476    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
477{
478}
479
480impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> Invalidate
481    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
482{
483    fn invalidate_cache_state(&mut self) {
484        self.dirt_tracker.unmark_dirty();
485        self.page_states.invalidate_cache_state();
486        self.page_pointers.invalidate_cache_state();
487        self.key_pointers.invalidate_cache_state();
488    }
489}
490
491impl<const PAGE_COUNT: usize, KEY: Key, const KEYS: usize> PrivateKeyCacheImpl<KEY>
492    for KeyPointerCache<PAGE_COUNT, KEY, KEYS>
493{
494    type KPC = CachedKeyPointers<KEY, KEYS>;
495
496    fn key_pointers(&mut self) -> &mut Self::KPC {
497        &mut self.key_pointers
498    }
499}
sequential_storage/cache/mod.rs

sequential_storage/cache/
mod.rs
