DOCSEARCHbyAlgolia
Submit Docs

sequential-storage

repository·master·Indexed 41 days ago

https://github.com/tweedegolf/sequential-storage

A Rust crate for storing data in flash memory with minimal erase cycles, providing Map (key-value) and Queue (FIFO) data structures. Designed for embedded environments, it prioritizes wear leveling, power-fail safety, and corruption repair using the embedded-storage trait. Version 8.0.1 includes features like CRC protection and optional RAM caching (ArrayPageStates, ArrayPagePointers, ArrayKeyPointers) to optimize performance.

Tokens
9.6K
Snippets
27
Records
47
Agent score
52%

What's inside sequential-storage

  1. Overview of Sequential-storage

    master

    Sequential-storage is a Rust crate designed for storing data in flash memory with minimal erase cycles. It is built on top of the embedded-storage trait and is suitable for embedded systems where flash longevity is a concern.

    It provides two primary data structures:

    • Map: A key-value pair store, ideal for configuration data. It supports user-defined key and value types.
    • Queue: A FIFO (First-In-First-Out) store, ideal for caching byte slices in memory.

    Key features include:

    • Wear Leveling: Pages are used cyclically to ensure equal erase cycles across all pages.
    • Power-fail Safety: The system is designed to be either fine or fully recoverable after a power failure.
    • Corruption Repair: Automatically attempts to repair flash state when corruption is detected during operations.
    • CRC Protection: Both item headers and item data are protected by CRCs.

    Warning on Async Operations: The crate uses futures for operations. If a future is cancelled while writing to flash, it can lead to a corrupted flash state. While the crate will attempt to repair the state, the specific data you were attempting to store or erase may be lost or incomplete.

  2. How Page states and Items work

    master

    The crate manages flash by dividing it into pages and storing data as 'items'.

    Page States

    A page can be in one of three states, encoded in its first and last words:

    1. Open: The page is erased (both words are FF).
    2. Partial open: The page has been written to but is not full (first word contains a marker).
    3. Closed: The page is fully written (both words are written).

    Items

    Every piece of data is an 'item' consisting of a header and the data itself. The header includes:

    • Data length (u16)
    • CRC for the length
    • CRC for the data

    Security Note: An item is considered 'erased' when its data CRC field is set to 0. However, the actual data remains on the flash until the page is physically erased. If your use case requires secure deletion, be aware that data may persist on the flash until a page erase occurs.

  3. Understand the in-flash representation and versioning

    master

    The in-flash representation of data follows semantic versioning (semver). This is critical for long-term data persistence:

    • Major version bumps: Indicate a breaking change to the in-flash representation. Data created by an older major version cannot be used by a newer one.
    • Minor version bumps: Indicate feature additions. These are backward-compatible (e.g., data from 1.0.0 can be used by 1.1.0), but may not be forward-compatible (e.g., data from 1.0.1 might not work with 1.0.0).
    • Patch releases: Only fix bugs and do not change the in-flash representation.

    Always consult the changelog before updating to ensure your existing flash data remains compatible with the new version.

  4. How Map and Queue operations work

    master

    Map (Key-Value Store)

    • Writing: New values are appended to the last 'partial open' page or the first 'open' page following the last 'closed' page.
    • Wear Leveling/Compaction: When a page needs to be erased, the crate checks all items on that page. If an item does not have a newer version elsewhere, it is copied to the current partial-open page before the old page is erased. This prevents data loss.

    Queue (FIFO Store)

    • Pushing: The crate searches for the youngest available spot. If it doesn't fit, it returns an error or erases an old page if permission was granted.
    • Peeking/Popping: Operations look at the oldest data available. When an item is 'popped', it is also marked as erased.

  5. Optimize performance with Caching

    master

    By default, all state is stored in flash, requiring a full read for every operation. You can optionally store state in RAM using various cache types to speed up operations.

    Common cache types and their impacts:

    • ArrayPageStates: Stores page states in an array. Slightly more efficient than CalculatedPageStates because it provides perfect caching.
    • ArrayPagePointers: Highly effective for Queues, reducing flash reads significantly.
    • ArrayKeyPointers: Highly effective for Maps, especially if you have enough RAM to store all keys. If you only access a subset of keys, a smaller key cache can still yield significant savings.

    Best Practice: If your application is performance-sensitive, ensure it remains functional even when no cache is used. This ensures you have accounted for the worst-case execution time.

  6. Use the Cache struct

    master

    The Cache struct is a composite object that implements the CacheImpl<KEY> trait. It aggregates three specialized sub-caches:

    1. PAGE: PageStatesCache: Tracks the state of pages (e.g., erased, partially written, etc.).
    2. POINTERS: PagePointersCache: Tracks item addresses within pages, such as the first item after an erase or the first free unwritten item.
    3. KEYS: KeyPointersCache<KEY>: Maps specific keys to their item addresses in flash.

    When using a custom Cache, ensure the page_count provided to the underlying sub-caches is correct; providing a count lower than the actual number of pages will cause a panic.

  7. How the Cache lifecycle and consistency works

    master

    The Cache manages consistency using a "dirty" flag via an internal DirtTracker.

    • Dirty State: When the cache is marked as dirty, it indicates that the cache might be inconsistent with the actual state of the flash memory (e.g., due to an interrupted write or an error during an operation).
    • Consistency: You can check if the cache is dirty using is_dirty(). If an operation fails or an inconsistency is detected, you should use invalidate_cache_state() to clear all cached information and force the system to re-discover the state from flash.

    Important Usage Rule:

    • Valid: Create cache 1 $\rightarrow$ use 1 $\rightarrow$ use 1 $\rightarrow$ create cache 2 $\rightarrow$ use 2 $\rightarrow$ use 2.
    • Invalid: Create cache 1 $\rightarrow$ use 1 $\rightarrow$ create cache 2 $\rightarrow$ use 2 $\rightarrow$ ❌ use 1 ❌ (Using an old cache instance for a region after a new cache has been created is unsafe).

  8. Use MapStorage for key-value storage

    master

    MapStorage provides a key-value interface where storing a value with an existing key logically overwrites the old value.

    Important Requirements:

    • Data Buffer: You must provide a mutable data_buffer for all operations. This buffer must be large enough to hold the combined serialized size of your Key and Value types, rounded up to the flash's word alignment.
    • Type Consistency: You must use the same Key and Value types consistently for all operations. Using different types for the same key can lead to incorrect data or deserialization errors.
    • Generics: MapStorage is generic over the Key type K, the Flash type S, and the Cache implementation C.
    // Example initialization and usage
let mut storage = MapStorage::<u8, _, _>::new(
    flash, 
    const { MapConfig::new(0x1000..0x3000) }, 
    Cache::new_uncached()
);

let mut data_buffer = [0; 128];

// Store an item
storage.store_item(&mut data_buffer, &42u8, &104729u32).await.unwrap();

// Fetch an item
let val: Option<u32> = storage.fetch_item(&mut data_buffer, &42u8).await.unwrap();
assert_eq!(val, Some(104729));

  9. Understand the KeyPointersCache trait

    master

    The KeyPointersCache<KEY> trait defines the interface for components that cache the location of keys to avoid repeated lookups. It is the primary public interface for interacting with different cache implementations like ArrayKeyPointers and HeapKeyPointers.

    Key capabilities include:

    • Locating a key's address.
    • Notifying the cache when a key's location is known or updated.
    • Notifying the cache when a key is erased.
    • Invalidating the entire cache state.

  10. The MaybeItem enum and its states

    master

    When reading items from flash, the library returns a MaybeItem enum to represent the state of the data at a specific address. This is used to handle the realities of flash storage (erased vs. corrupted vs. valid):

    • MaybeItem::Present(Item<'d>): A valid item with a matching CRC.
    • MaybeItem::Erased(ItemHeader, &'d mut [u8]): The item is considered erased (CRC is 0).
    • MaybeItem::Corrupted(ItemHeader, &'d mut [u8]): The item's CRC or length CRC failed validation.

    Developers can use MaybeItem::unwrap() to attempt to convert a MaybeItem into a valid Item, which will return an Error::Corrupted if the state is not Present or Error::LogicBug if the state is Erased (since an erased item cannot be unwrapped as valid data).

  11. Understand PageState

    master

    The library manages flash memory in discrete units called pages. Each page exists in one of three states, which determines how the storage engine interacts with it:

    • PageState::Open: The page is fully erased and ready for new data.
    • PageState::PartialOpen: The page has been written to, but may still have available space for more items.
    • PageState::Closed: The page is fully written and has been sealed (markers written at both start and end).

  12. How item corruption and erasure are detected

    master

    The library uses specific CRC patterns to distinguish between valid data, erased space, and corrupted data:

    • Erased Items: An item is considered erased if its crc field is 0. The adapted_crc32 function is designed to never produce a 0 value on its own.
    • Corrupted Items: Corruption is detected if the length_crc (CRC16 of the length field) does not match the stored value, or if the adapted_crc32 of the data does not match the stored crc field.
    • CRC Implementation: The library uses a modified CRC32 (Castagnoli polynomial) with a custom initial value (0xEEEE_EEEE) to ensure it is resistant to all-ones (0xFF...) patterns, which are common in erased flash.