use crate::block_dev::{BlockDevice, BlockDeviceHandle, BLOCK_SIZE};
use crate::file::FileError;
use alloc::{boxed::Box, collections::VecDeque};
use spin::Mutex;
const DEFAULT_CACHE_BLOCKS: usize = 64;
struct CachedBlock {
block_no: usize,
data: Box<[u8; BLOCK_SIZE]>,
dirty: bool,
}
struct CacheInner {
entries: VecDeque<CachedBlock>,
capacity: usize,
hits: u64,
misses: u64,
}
impl CacheInner {
fn new(capacity: usize) -> Self {
Self {
entries: VecDeque::with_capacity(capacity.max(1)),
capacity: capacity.max(1),
hits: 0,
misses: 0,
}
}
fn find(&self, block_no: usize) -> Option<usize> {
self.entries
.iter()
.position(|entry| entry.block_no == block_no)
}
fn touch(&mut self, idx: usize) {
if idx + 1 == self.entries.len() {
return;
}
if let Some(entry) = self.entries.remove(idx) {
self.entries.push_back(entry);
}
}
fn evict_lru(&mut self, dev: &dyn BlockDevice) -> Result<(), FileError> {
if let Some(victim) = self.entries.pop_front() {
if victim.dirty {
dev.write_block(victim.block_no, victim.data.as_ref())?;
}
}
Ok(())
}
fn dirty_count(&self) -> usize {
self.entries.iter().filter(|entry| entry.dirty).count()
}
fn flush_block(&mut self, dev: &dyn BlockDevice, block_no: usize) -> Result<bool, FileError> {
let Some(idx) = self.find(block_no) else {
return Ok(false);
};
if self.entries[idx].dirty {
let victim = &self.entries[idx];
dev.write_block(victim.block_no, victim.data.as_ref())?;
self.entries[idx].dirty = false;
}
Ok(true)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BlockCacheStats {
pub hits: u64,
pub misses: u64,
pub cached_blocks: usize,
pub dirty_blocks: usize,
pub capacity: usize,
}
impl BlockCacheStats {
pub fn total_reads(self) -> u64 {
self.hits + self.misses
}
pub fn hit_rate_percent(self) -> u64 {
let total = self.total_reads();
if total == 0 {
0
} else {
self.hits * 100 / total
}
}
}
pub struct BlockCache {
dev: BlockDeviceHandle,
inner: Mutex<CacheInner>,
}
impl BlockCache {
pub fn new(dev: BlockDeviceHandle) -> Self {
Self {
dev,
inner: Mutex::new(CacheInner::new(DEFAULT_CACHE_BLOCKS)),
}
}
pub fn with_capacity(dev: BlockDeviceHandle, capacity: usize) -> Self {
Self {
dev,
inner: Mutex::new(CacheInner::new(capacity)),
}
}
pub fn flush(&self) -> Result<(), FileError> {
let mut inner = self.inner.lock();
for entry in &inner.entries {
if entry.dirty {
self.dev.write_block(entry.block_no, entry.data.as_ref())?;
}
}
for entry in &mut inner.entries {
entry.dirty = false;
}
Ok(())
}
pub fn stats(&self) -> (u64, u64) {
let inner = self.inner.lock();
(inner.hits, inner.misses)
}
pub fn stats_snapshot(&self) -> BlockCacheStats {
let inner = self.inner.lock();
BlockCacheStats {
hits: inner.hits,
misses: inner.misses,
cached_blocks: inner.entries.len(),
dirty_blocks: inner.dirty_count(),
capacity: inner.capacity,
}
}
pub fn reset_stats(&self) {
let mut inner = self.inner.lock();
inner.hits = 0;
inner.misses = 0;
}
pub fn flush_block(&self, block_no: usize) -> Result<bool, FileError> {
self.inner.lock().flush_block(&*self.dev, block_no)
}
}
impl BlockDevice for BlockCache {
fn read_block(&self, block_no: usize, buf: &mut [u8]) -> Result<(), FileError> {
if buf.len() != BLOCK_SIZE {
return Err(FileError::InvalidOperation);
}
let mut inner = self.inner.lock();
if let Some(idx) = inner.find(block_no) {
buf.copy_from_slice(inner.entries[idx].data.as_ref());
inner.touch(idx);
inner.hits += 1;
return Ok(());
}
inner.misses += 1;
if inner.entries.len() >= inner.capacity {
inner.evict_lru(&*self.dev)?;
}
let mut data = Box::new([0u8; BLOCK_SIZE]);
self.dev.read_block(block_no, data.as_mut())?;
buf.copy_from_slice(data.as_ref());
inner.entries.push_back(CachedBlock {
block_no,
data,
dirty: false,
});
Ok(())
}
fn write_block(&self, block_no: usize, buf: &[u8]) -> Result<(), FileError> {
if buf.len() != BLOCK_SIZE {
return Err(FileError::InvalidOperation);
}
let mut inner = self.inner.lock();
if let Some(idx) = inner.find(block_no) {
inner.entries[idx].data.copy_from_slice(buf);
inner.entries[idx].dirty = true;
inner.touch(idx);
return Ok(());
}
if inner.entries.len() >= inner.capacity {
inner.evict_lru(&*self.dev)?;
}
let mut data = Box::new([0u8; BLOCK_SIZE]);
data.copy_from_slice(buf);
inner.entries.push_back(CachedBlock {
block_no,
data,
dirty: true,
});
Ok(())
}
fn block_count(&self) -> usize {
self.dev.block_count()
}
fn flush(&self) -> Result<(), FileError> {
BlockCache::flush(self)
}
}
impl Drop for BlockCache {
fn drop(&mut self) {
let _ = self.flush();
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::DummyBlockDev;
use alloc::sync::Arc;
fn block(fill: u8) -> [u8; BLOCK_SIZE] {
[fill; BLOCK_SIZE]
}
#[test]
fn repeated_read_uses_cache_and_updates_stats() {
let raw = Arc::new(DummyBlockDev::new(4));
raw.write_block(1, &block(7)).unwrap();
let cache = BlockCache::with_capacity(raw, 2);
let mut buf = [0u8; BLOCK_SIZE];
cache.read_block(1, &mut buf).unwrap();
assert_eq!(buf, block(7));
cache.read_block(1, &mut buf).unwrap();
let stats = cache.stats_snapshot();
assert_eq!(stats.misses, 1);
assert_eq!(stats.hits, 1);
assert_eq!(stats.cached_blocks, 1);
assert_eq!(stats.hit_rate_percent(), 50);
}
#[test]
fn write_back_defers_device_write_until_flush() {
let raw = Arc::new(DummyBlockDev::new(4));
let cache = BlockCache::with_capacity(raw.clone(), 2);
cache.write_block(2, &block(9)).unwrap();
let mut raw_buf = [0u8; BLOCK_SIZE];
raw.read_block(2, &mut raw_buf).unwrap();
assert_eq!(raw_buf, block(0));
assert!(cache.flush_block(2).unwrap());
raw.read_block(2, &mut raw_buf).unwrap();
assert_eq!(raw_buf, block(9));
}
}