From 8a45cd95353ae9fe1286dbc4fcd36faaa66c9f82 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Sun, 19 Nov 2023 01:03:19 -0800 Subject: Layer 1 test not passing --- src/memory/cached_block.rs | 201 +++++++++++++++++++++++++++++++++++++-------- src/memory/cached_inode.rs | 48 +++++++++-- src/memory/mod.rs | 1 - 3 files changed, 208 insertions(+), 42 deletions(-) (limited to 'src/memory') diff --git a/src/memory/cached_block.rs b/src/memory/cached_block.rs index 0c401ff..9e266ef 100644 --- a/src/memory/cached_block.rs +++ b/src/memory/cached_block.rs @@ -1,7 +1,10 @@ -use and_then_some::BoolExt; +use crate::block_device::{BlockDevice, BLOCK_SIZE}; +use crate::disk::block::Block; use crate::AyaFS; -use crate::block_device::BLOCK_SIZE; -use crate::disk::data_block::{Block, DataBlock}; +use and_then_some::BoolExt; +use lru::LruCache; +use std::num::NonZeroUsize; +use std::sync::Arc; #[derive(Clone)] pub struct CachedBlock { @@ -28,39 +31,24 @@ pub fn convert(input_block: &CachedBlock) -> &CachedBlock unsafe { &*block } } -impl AyaFS { - pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { - if self.cached_blocks.contains(&block.index) { - let data_block = convert::(&block).clone(); - self.cached_blocks.push(block.index, data_block); - true - } else { - false - } - } - pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { - self.load_block(index) - .and_then(|| self.cached_blocks.get(&index).map(convert::)) - } +pub(crate) struct BlockCache { + device: Arc, + cache: LruCache>, +} - pub(crate) fn get_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { - self.load_block(index).and_then(|| { - self.cached_blocks - .get_mut(&index) - .map(convert_mut::) - }) +impl BlockCache { + pub(crate) fn new(device: Arc, cache_size: usize) -> Self { + Self { + device, + cache: LruCache::new(NonZeroUsize::new(cache_size).unwrap()), + } } pub(crate) fn load_block(&mut self, index: usize) -> bool { - // 反正我自己保证所有实现了 Block trait 的数据结构都是 4K bytes 长, 来回 cast 没问题 - // 如果 block cache 里没有这个 block - if self.cached_blocks.contains(&index) == false { - if self.data_bitmap.query(index) == false { - return false; - } // 先看这个 block 是不是 valid, 不 valid 直接返回 None - let block = DataBlock::default(); + if self.cache.contains(&index) == false { + let block = T::default(); let buffer = unsafe { - std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE) + std::slice::from_raw_parts_mut(&block as *const T as *mut u8, BLOCK_SIZE) }; self.device.read(index, buffer); let cached_block = CachedBlock { @@ -68,17 +56,160 @@ impl AyaFS { index, dirty: false, }; - if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) { + if let Some((old_index, old_block)) = self.cache.push(index, cached_block) { assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入 if old_block.dirty { - let old_block_ptr = &old_block.block as *const DataBlock as *mut u8; + let old_block_ptr = &old_block.block as *const T as *mut u8; let old_block_buffer = unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) }; self.device.write(old_index, old_block_buffer); } - } // 如果 valid 就放到 block cache 里, 同时将（可能）被驱逐的 block 依据其是否为脏块进行写回 + } } - true } + + /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载. + pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { + self.load_block(index) + .and_then(|| self.cache.get(&index).map(convert::)) + } + + /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载. + pub(crate) fn get_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.load_block(index) + .and_then(|| self.cache.get_mut(&index).map(convert_mut::)) + } + + /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { + self.cache.peek(&index).map(convert::) + } + + /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + pub(crate) fn peek_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.cache.peek_mut(&index).map(convert_mut::) + } + + pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { + if self.cache.contains(&block.index) { + let data_block = convert::(&block).clone(); + self.cache.push(block.index, data_block); + true + } else { + false + } + } + + fn pop(&mut self, entry: &usize) -> Option> { + self.cache.pop(entry) + } +} + +impl AyaFS { + pub(crate) fn load_block(&mut self, index: usize) -> bool { + if !self.data_bitmap.query(index) { + self.cached_blocks.pop(&index); + // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry. + return false; + } + self.cached_blocks.load_block(index) + } + + pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { + self.data_bitmap + .query(index) + .and_then(|| self.cached_blocks.get_block::(index)) + } + + pub(crate) fn get_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.data_bitmap + .query(index) + .and_then(|| self.cached_blocks.get_block_mut::(index)) + } + + pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { + self.data_bitmap + .query(index) + .and_then(|| self.cached_blocks.peek_block::(index)) + } + + pub(crate) fn peek_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.data_bitmap + .query(index) + .and_then(|| self.cached_blocks.peek_block_mut::(index)) + } + + pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { + self.cached_blocks.update_block(block) + } + + // pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { + // if self.cached_blocks.contains(&block.index) { + // let data_block = convert::(&block).clone(); + // self.cached_blocks.push(block.index, data_block); + // true + // } else { + // false + // } + // } + // + // /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载. + // pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { + // self.load_block(index) + // .and_then(|| self.cached_blocks.get(&index).map(convert::)) + // } + // + // /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载. + // pub(crate) fn get_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + // self.load_block(index).and_then(|| { + // self.cached_blocks + // .get_mut(&index) + // .map(convert_mut::) + // }) + // } + // + // /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + // pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { + // self.cached_blocks.peek(&index).map(convert::) + // } + // + // /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + // pub(crate) fn peek_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + // self.cached_blocks.peek_mut(&index).map(convert_mut::) + // } + // + // pub(crate) fn load_block(&mut self, index: usize) -> bool { + // // 先看这个 block 是不是 valid, 不 valid 直接返回 false. + // if !self.data_bitmap.query(index) { + // self.cached_blocks.pop(&index); + // // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry. + // return false; + // } + // + // // 接下来这个 block 一定 valid. 如果 cache 里没有这个 block 就把它 load 到 cache 里 + // if self.cached_blocks.contains(&index) == false { + // let block = DataBlock::default(); + // let buffer = unsafe { + // std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE) + // }; + // self.device.read(index, buffer); + // let cached_block = CachedBlock { + // block, + // index, + // dirty: false, + // }; + // if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) { + // assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入 + // if old_block.dirty { + // let old_block_ptr = &old_block.block as *const DataBlock as *mut u8; + // let old_block_buffer = + // unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) }; + // self.device.write(old_index, old_block_buffer); + // } + // } + // } + // + // true + // } } diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs index b51d279..b81bd2e 100644 --- a/src/memory/cached_inode.rs +++ b/src/memory/cached_inode.rs @@ -1,7 +1,7 @@ -use and_then_some::BoolExt; +use crate::disk::block::{Block, InodeBlock}; +use crate::disk::inode::{Inode, InodeMode, INODE_SIZE}; use crate::AyaFS; -use crate::disk::data_block::InodeBlock; -use crate::disk::inode::{Inode, INODE_SIZE, InodeMode}; +use and_then_some::BoolExt; impl AyaFS { pub(crate) fn create_inode( @@ -30,10 +30,24 @@ impl AyaFS { }) } + pub(crate) fn update_inode(&mut self, inode_index: usize, inode: Inode) -> bool { + if self.inode_bitmap.query(inode_index) { + let (block_index, offset) = self.locate_inode(inode_index); + if let Some(cached_block) = self.cached_inodes.get_block_mut::(block_index) + { + cached_block.block.inodes[offset / INODE_SIZE] = inode; + } + true + } else { + false + } + } + pub(crate) fn get_inode(&mut self, inode_index: usize) -> Option<&Inode> { self.inode_bitmap.query(inode_index).and_then(|| { let (block_index, offset) = self.locate_inode(inode_index); - self.get_block::(block_index) + self.cached_inodes + .get_block::(block_index) .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE]) }) } @@ -41,11 +55,33 @@ impl AyaFS { pub(crate) fn get_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> { self.inode_bitmap.query(inode_index).and_then(|| { let (block_index, offset) = self.locate_inode(inode_index); - self.get_block_mut::(block_index) + self.cached_inodes + .get_block_mut::(block_index) + .map(|cached_block| { + cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏 + &mut cached_block.block.inodes[offset / INODE_SIZE] + }) + }) + } + + pub(crate) fn peek_inode(&self, inode_index: usize) -> Option<&Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + self.cached_inodes + .peek_block::(block_index) + .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE]) + }) + } + + pub(crate) fn peek_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + self.cached_inodes + .peek_block_mut::(block_index) .map(|cached_block| { cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏 &mut cached_block.block.inodes[offset / INODE_SIZE] }) }) } -} \ No newline at end of file +} diff --git a/src/memory/mod.rs b/src/memory/mod.rs index ffdf04c..3380d0f 100644 --- a/src/memory/mod.rs +++ b/src/memory/mod.rs @@ -1,5 +1,4 @@ /// In-memory data structures and logic. /// This is where the crucial block and inode methods presented to upper calls implemented. - pub mod cached_block; pub mod cached_inode; -- cgit v1.2.3-70-g09d2