# Memory Trait: Two Years Later

###### tags: `technical`

## Flash

I think it makes sense to use the traits in [`embedded-storage`](https://docs.rs/embedded-storage/latest/embedded_storage/index.html); specifically:

## RAM Cache

// works with both flash units that are memory mapped
// and those that are external (we don't actually care
// about this, the actual read optimization is handled
// by the underlying traits; we just need to know whether
// to figure out our offset based on address math or
// whether we're going to be handed an offset outright)

trait PersistentStorage {
    type Error: Debug;
    const READ_SIZE: usize;
    const WRITE_SIZE: usize;

    // Must be aligned.
    fn read(&mut self, offset: u32, bytes: &mut [u8]) -> Result<(), Self::Error>;
    
    // Will handle erasing for you; must be aligned.
    fn write(&mut self, offset: u32, bytes: &[u8]) -> Result<(), Self::Error>;

    // 
    fn capacity(&self) -> usize;
}

struct Empty;
impl PersistentStorage {
    type Error = !;
    const READ_SIZE: usize = 1;
    const WRITE_SIZE: usize = 1;
    fn read(&mut self, _offset: u32, _bytes: &mut [u8]) -> Result<(), !> { panic!() }
    fn write(&mut self, _offset: u32, _bytes: &[u8]) -> Result<(), !> { panic!() }
    fn capacity(&self) -> usize { 0 }
}

// TODO: hoist the &mut persistent_storage up to here so
// that we can report on it in `capacity()` so it's
// included in bound checks?
//
// actually i think this is not worth it...
//
// we just have checks in the constructor for RamCache and
// that's fine

#[derive(Debug, ...)]
pub struct Storage<S: es::Storage>(pub S);
impl<S: es::Storage> PersistentStorage for Storage<S> {
    type Error = S::Error;
    const READ_SIZE: usize = 1;
    const WRITE_SIZE: usize = 1;
    
    fn read(&mut self, offset: u32, bytes: &mut [u8]) -> Result<(), Self::Error> {
        self.0.read(offset, bytes)
    }
    
    fn write(&mut self, offset: u32, bytes: &[u8]) -> Result<(), Self::Error> {
        self.0.write(offset, bytes)
    }

    fn capacity(&self) -> usize { self.0.capacity() }
}

#[derive(Debug, ...)]
pub struct NorFlash<F: es::nor_flash::NorFlash>(pub F);
impl<F: es::nor_flash::NorFlash> PersistentStorage for NorFlash<F> {
    type Error = F::Error;
    
    const READ_SIZE: usize = F::READ_SIZE;
    const WRITE_SIZE: usize = {
        // Since writes now involve erasing first,
        // the write size is now whichever is larger
        // of the write and erase sizes:
        let smaller = min(F::ERASE_SIZE, F::WRITE_SIZE);
        let larger = max(F::ERASE_SIZE, F::WRITE_SIZE);
        
        // We also need to ensure that the smaller number
        // (whether it's the write size or the erase size)
        // is a factor of the larger number:
        assert!(larger % smaller == 0);
        
        larger
    };

    fn read(&mut self, offset: u32, bytes: &mut [u8]) -> Result<(), Self::Error> {
        self.0.read(offset, bytes)
    }

    // write now requires alignment to erase size too
    // this is only an issue if erase size is larger than
    // write size or not a factor/multiple of write size
    fn write(&mut self, offset: u32, bytes: &[u8]) -> Result<(), Self::Error> {
        es::nor_flash::check_write(self.0, offset, bytes.len())?;

        self.0.erase(offset, offset.checked_add(bytes.len()).unwrap())?;
        self.0.write(offset, bytes)
    }

    fn capacity(&self) -> usize { self.0.capacity() }
}

pub enum PersistentStorageAllocation<const NUM_PAGES: usize> {
    MemMapped {
        /// Device specific! memory mapped address
        ///
        /// FlashExt::address, for example
        persistent_storage_base_memory_address: usize,
        allocation: &mut [u16; NUM_PAGES * WORDS_IN_A_PAGE],
    },
    
    // for devices that are mem mapped we assume the `read`
    // function does the "smart" thing and just creates the
    // appropriate pointer and reads from it; we never explicitly touch `allocation`, it's purely just a compile time check. (volatile_read once to make sure it's not optimized out, TODO)
    
    Offset(usize),
}

impl<const NUM_PAGES: usize> PersistentStorageAllocation {
    fn offset(&self) -> u32 {
        match self {
            Self::MemMapped { persistent_storage_base_memory_address, allocation } => {
                (allocation as *mut _ as usize - persistent_storage_base_memory_address).try_into().unwrap()
            },
            Self::Offset(offs) => offs,
        }
    }
}


enum PageState {
    #[default]
    Main,

    // in RAM but clean
    InRam(u16),

    // in RAM but dirty
    InRamDirty(u16),

    // in `Swap` (and thus, dirty)
    Swapped(u16),
}


type PageMap = [PageState; NUM_PAGES];
trait EvictionPolicy<const RAM_PAGES: usize> {
    fn evict(&mut self, page_map: &PageMap) -> u16;
    
    // hooks to inform the policy:
    fn loaded_page(&mut self, pg_idx: u8) { } // when a page is first loaded into ram
    fn written_to_page(&mut self, pg_idx: u8) { } // when a page is first marked as dirty
    fn dropped_page(&mut self, pg_idx: u8) { } // evicted clean page
    fn swapped_page(&mut self, pg_idx: u8) { } // evicted dirty page
    
    fn read_from_page(&mut self, pg_idx: u8) { } // any read from the page
    fn write_to_page(&mut self, pg_idx: u8) { } // any write from the page
}

// naive example!
struct EvictFirst;
impl<const N: usize> EvictionPolicy<N> for EvictFirst {
    fn evict(&mut self, page_map: &PageMap) -> u16 {
        for (idx, e) in page_map.iter() {
            match e {
                // TODO: have this assertion at the caller
                PageState::InRam(idx) | PageState::InRamDirty(idx) => return idx,
                _ => {},
            }
        }
        
        unreachable!()
    }
}

// struct EvictClean<Then: EvictionPolicy>(Then);
// impl<T: EvictionPolicy> EvictionPolicy for EvictClean<T> {
//     fn evict(&mut self, page_map: &PageMap) -> u16 {
//         for (idx, e) in page_map.iter() {
//             if let PageState::
//         }
//     }
    
//     // TODO: forward other methods to inside...
// }

struct Map<const ENTRIES: usize, Val> {
    [Option<Val>; ENTRIES]
}

// fn set
// fn inc

impl<const E: usize, Val: Cmp> Map<E, Val> {
    fn min(&self) -> Option<u8> { // idx
        
    }
}

struct EvictLruLevel<Then: EvictionPolicy = EvictFirst, const RAM_PAGES: usize> {
    filter: fn(&PageState) -> bool,
    then: Then,
    counter: usize, // starts at 0
    lru: Lru<
}
impl<const N: usize, T: EvictionPolicy> EvictionPolicy<N> for EvictLruLevel<N, T> {
    fn evict()
}

struct EvictFreqLevel<Then: EvictionPolicy = EvictFirst, const RAM_PAGES: usize> {
    filter: fn(&PageState) -> bool,
    then: Then,
    counter: usize,
    freq: 
}

// Really we only want to bound on `Storage` but...
// that does clever "is subset" checks to elide erases
// and "merge buffer" things for unaligned writes.
//
// Our use case explicitly does not make use of unaligned
// writes and the "is subset" check (which reads in all
// of the current data which we're overwriting) is unlikely
// to benefit us.
//
// So, we use the NorFlash traits directly here.
//
// However, we also want to provide the _ability_ to use
// `Storage` impls, so... we'll introduce some indirection
// (another trait).
struct RamCache<
    /// Only read in pages on write if true, else eagerly.
    // /
    // / when true, assumes a flash unit that's mapped into
    // / the address space
    // /
    // / if you wish to use an external flash unit you must
    // / set this to false
    const LAZY_LOAD_PAGES: bool,

    const NUM_RAM_PAGES: usize,
    S: PersistentStorage,

    E: EvictionPolicy,

    const NUM_SWAP_PAGES: usize = 0,
    Swap: PersistentStorage = Empty,
> {
    pages: [
      [u16; PAGE_SIZE]; NUM_RAM_PAGES  
    ],
    page_map: PageMap,
    
    main_allocation: PersistentStorageAllocation<LC3_PAGES>,
    main_storage: S,
    evic: E,

    page_table: [
        
    ],
    
    swap_allocation: PersistentStorageAllocation<NUM_SWAP_PAGES>, // defaults to offset = 0
    swap_storage: Swap,
    
    /// ASSERT that S::WRITE_SIZE <= PAGE SIZE
    /// ASSERT that PAGE SIZE % S::WRITE_SIZE == 0
    /// ASSERT that
    ///   if LAZY_LOAD_PAGES:
    ///     S::READ_SIZE <= 2 (for direct access to words...)
    ///   else /* eager page load */:
    ///     S::READ_SIZE <= PAGE SIZE
    ///     PAGE SIZE % S::READ_SIZE == 0
    /// ASSERT that NUM_PAGES >= 0
}
impl<S, NUM_PAGES> {
        /// SAFETY: Persistent Storage impl given must match the `PersistentStorageAllocation` given, offset (if specified directly) must be correct and not overwrite program data, etc.
    unsafe fn new(persistent_storage_allocation: PersistentStorageAllocation<NUM_PAGES>, storage: S, swap_storage: Swap) -> Self {
        assert!(self.main_allocation.offset() + size_of::<u16> * LC3_PAGES * WORDS_IN_A_PAGE <= storage.capacity());
        
        assert!(self.swap_allocation.offset() + size_of::<u16> * NUM_SWAP_PAGES * WORDS_IN_A_PAGE <= swap_storage.capacity());
        ...
    }
    
    // construct the wrappers for you...
    unsafe fn from_storage() -> Self;
    unsafe fn from_nor_flash() -> Self;
}

## Memory Impl