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/block_device/memory_disk.rs | 4 +- src/block_device/mod.rs | 1 - src/disk/allocation.rs | 131 +++++++++++++++++++++++++- src/disk/bitmap.rs | 30 +++--- src/disk/block.rs | 168 +++++++++++++++++++++++++++++++++ src/disk/data_block.rs | 168 --------------------------------- src/disk/mod.rs | 5 +- src/filesystem/trait_impl.rs | 13 ++- src/main.rs | 25 +++-- src/memory/cached_block.rs | 201 +++++++++++++++++++++++++++++++++------- src/memory/cached_inode.rs | 48 ++++++++-- src/memory/mod.rs | 1 - src/tests/bitmap.rs | 23 +++++ src/tests/block_cache.rs | 79 ++++++++++++++++ src/tests/common/mod.rs | 8 ++ src/tests/mod.rs | 6 ++ 16 files changed, 660 insertions(+), 251 deletions(-) create mode 100644 src/disk/block.rs delete mode 100644 src/disk/data_block.rs create mode 100644 src/tests/bitmap.rs create mode 100644 src/tests/block_cache.rs create mode 100644 src/tests/common/mod.rs create mode 100644 src/tests/mod.rs diff --git a/src/block_device/memory_disk.rs b/src/block_device/memory_disk.rs index 3876736..0639d3e 100644 --- a/src/block_device/memory_disk.rs +++ b/src/block_device/memory_disk.rs @@ -9,9 +9,9 @@ pub struct MemoryDisk { } impl MemoryDisk { - pub fn new() -> Self { + pub fn new(block_number: usize) -> Self { Self { - arena: RefCell::new(vec![0u8; BLOCK_SIZE * 16384]), + arena: RefCell::new(vec![0u8; BLOCK_SIZE * block_number]), } } } diff --git a/src/block_device/mod.rs b/src/block_device/mod.rs index c7e1362..a8fd8b7 100644 --- a/src/block_device/mod.rs +++ b/src/block_device/mod.rs @@ -1,6 +1,5 @@ /// Abstracts for block devices. /// Currently only a mock memory disk. - pub mod memory_disk; pub const BLOCK_SIZE: usize = 4096; pub trait BlockDevice { diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs index 291a136..3622e4f 100644 --- a/src/disk/allocation.rs +++ b/src/disk/allocation.rs @@ -1,15 +1,16 @@ -use crate::memory::cached_block::convert; -use crate::disk::data_block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; +use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; use crate::disk::inode::Inode; +use crate::memory::cached_block::convert; use crate::AyaFS; impl AyaFS { /// 为 Inode 分配新 block, 返回 block 的编号 - pub(crate) fn allocate_block(&mut self, inode: &mut Inode) -> Option { + pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option { // 先看这个 inode 的 direct block 有没有空闲 for index in inode.direct.iter_mut() { if !self.data_bitmap.query(*index as usize) { let block_index = self.data_bitmap.allocate().unwrap() as u32; + println!("allocating {} for direct", block_index); *index = block_index; inode.n_blocks += 1; // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了 @@ -23,9 +24,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; + println!("allocating {} for indirect", inode.single_indirect); } // 在 indirect block 里尝试分配 if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) { + println!("allocating {} in indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -36,9 +39,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; + println!("allocating {} for double indirect", inode.double_indirect); } // 在 double indirect block 里尝试分配 if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) { + println!("allocating {} in double indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -49,9 +54,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; + println!("allocating {} for triple indirect", inode.triple_indirect); } // 在 double indirect block 里尝试分配 if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) { + println!("allocating {} in triple indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -61,11 +68,13 @@ impl AyaFS { fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option { // 取出 single indirect block, 尝试在里面分配 let indirect_entry = indirect_entry as usize; + // println!("finding indirect block with number {}, bitmap says {}", indirect_entry, self.data_bitmap.query(indirect_entry)); if let Some(block) = self .get_block(indirect_entry) .map(convert::) { + // println!("found indirect block with number {}", indirect_entry); let mut indirect_block = block.clone(); for entry in indirect_block.block.entries.iter_mut() { if self.data_bitmap.query(*entry as usize) == false { @@ -130,3 +139,119 @@ impl AyaFS { None } } + +impl AyaFS { + /// 从 inode 中删去最后一个 block + pub(crate) fn deallocate_block(&mut self, inode: &mut Inode) -> Option { + // 如果 triple indirect 块存在, 则尝试从中销毁一个块 + if self.data_bitmap.query(inode.triple_indirect as usize) { + if let Some(block_index) = self.deallocate_from_triple_indirect(inode.triple_indirect) { + inode.n_blocks -= 1; + return Some(block_index); // 销毁成功, 直接返回 + } else { + // 销毁失败, 说明 triple indirect 空了, 把它也销毁. + self.data_bitmap.deallocate(inode.triple_indirect as usize); + inode.triple_indirect = 0; // 这个地方理论上应该不用? + } + } + // 如果 double indirect 块存在, 则从其中销毁 + if self.data_bitmap.query(inode.double_indirect as usize) { + if let Some(block_index) = self.deallocate_from_double_indirect(inode.double_indirect) { + inode.n_blocks -= 1; + return Some(block_index); + } else { + self.data_bitmap.deallocate(inode.double_indirect as usize); + inode.double_indirect = 0; // 这个地方理论上应该不用? + } + } + // 如果 indirect 块存在, 则从其中销毁 + if self.data_bitmap.query(inode.single_indirect as usize) { + if let Some(block_index) = self.deallocate_from_indirect(inode.single_indirect) { + inode.n_blocks -= 1; + return Some(block_index); + } else { + self.data_bitmap.deallocate(inode.single_indirect as usize); + inode.single_indirect = 0; // 这个地方理论上应该不用? + } + } + // 都没有，直接从 direct 块中销毁 + for entry in inode.direct.iter_mut().rev() { + if self.data_bitmap.query(*entry as usize) { + let index = std::mem::replace(entry, 0); // let index = *entry; *entry = 0; + inode.n_blocks -= 1; + self.data_bitmap.deallocate(index as usize); + return Some(index); + } + } + None + } + + fn deallocate_from_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option { + let triple_indirect_entry = triple_indirect_entry as usize; + if let Some(triple_indirect_block) = self + .peek_block(triple_indirect_entry) + .map(convert::) + { + for double_indirect_entry in triple_indirect_block + .block + .double_indirect + .into_iter() + .rev() + { + // 如果这个位置的 double indirect 存在 + if self.data_bitmap.query(double_indirect_entry as usize) { + // 尝试从中销毁一个块 + if let Some(block_index) = + self.deallocate_from_double_indirect(double_indirect_entry) + { + return Some(block_index); // 成功则直接返回 + } else { + // 失败则把这个 double indirect 销毁 + self.data_bitmap.deallocate(double_indirect_entry as usize); + } + } + } + } + None + } + + fn deallocate_from_double_indirect(&mut self, double_indirect_entry: u32) -> Option { + let double_indirect_entry = double_indirect_entry as usize; + if let Some(double_indirect_block) = self + .peek_block(double_indirect_entry) + .map(convert::) + { + for indirect_entry in double_indirect_block.block.indirect.into_iter().rev() { + // 如果这个位置的 indirect 存在 + if self.data_bitmap.query(indirect_entry as usize) { + // 尝试从中销毁一个块 + if let Some(block_index) = self.deallocate_from_indirect(indirect_entry) { + return Some(block_index); // 成功则直接返回 + } else { + // 失败则把这个 indirect 销毁 + self.data_bitmap.deallocate(indirect_entry as usize); + } + } + } + } + None + } + + fn deallocate_from_indirect(&mut self, indirect_entry: u32) -> Option { + let indirect_entry = indirect_entry as usize; + if let Some(indirect_block) = self + .peek_block(indirect_entry) + .map(convert::) + { + // 遍历 indirect block 里的每个 block + for entry in indirect_block.block.entries.into_iter().rev() { + // 如果这个 block 存在, 销毁它 + if self.data_bitmap.query(entry as usize) { + self.data_bitmap.deallocate(entry as usize); + return Some(entry); + } + } + } + None + } +} diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs index 64389c2..b68c341 100644 --- a/src/disk/bitmap.rs +++ b/src/disk/bitmap.rs @@ -1,5 +1,4 @@ use crate::block_device::{BlockDevice, BLOCK_SIZE}; -use std::cell::RefCell; use std::sync::Arc; pub struct Bitmap { @@ -10,7 +9,7 @@ pub struct Bitmap { } impl Bitmap { - pub fn new(starting_block: usize, length: usize, device: Arc) -> Self { + pub(crate) fn new(starting_block: usize, length: usize, device: Arc) -> Self { Self { starting_block, length, @@ -18,8 +17,7 @@ impl Bitmap { data: vec![0u8; length * BLOCK_SIZE], } } - pub fn allocate(&mut self) -> Option { - // let mut data = self.data.borrow_mut(); + pub(crate) fn allocate(&mut self) -> Option { for (i, byte) in self.data.iter_mut().enumerate() { let leading_ones = byte.leading_ones(); if leading_ones != 8 { @@ -28,11 +26,9 @@ impl Bitmap { } } None - // panic!("No more space for allocation!") } - pub fn query(&self, index: usize) -> bool { - // let data = self.data.borrow(); + pub(crate) fn query(&self, index: usize) -> bool { if index == 0 { false } else { @@ -40,15 +36,13 @@ impl Bitmap { } } - // fn write_back(&mut self) { - // for block_index_offset in self.dirty_blocks.iter() { - // let buffer_front_index = BLOCK_SIZE * block_index_offset; - // let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1); - // self.device.write( - // self.starting_block + block_index_offset, - // &self.data[buffer_front_index..buffer_back_index], - // ); - // } - // self.dirty_blocks = Vec::new(); - // } + pub(crate) fn deallocate(&mut self, index: usize) -> bool { + if self.query(index) { + let mask = !(1u8 << (7 - index % 8)); + self.data[index / 8] &= mask; + true + } else { + false + } + } } diff --git a/src/disk/block.rs b/src/disk/block.rs new file mode 100644 index 0000000..d287ee6 --- /dev/null +++ b/src/disk/block.rs @@ -0,0 +1,168 @@ +use crate::disk::inode::Inode; + +pub trait Block: Default + Clone {} + +#[derive(Clone)] +pub struct DataBlock(pub(crate) [u8; 4096]); + +impl Default for DataBlock { + fn default() -> Self { + Self([0; 4096]) + } +} + +impl Block for DataBlock {} + +#[derive(Clone)] +pub struct InodeBlock { + pub(crate) inodes: [Inode; 16], +} + +impl Default for InodeBlock { + fn default() -> Self { + Self { + inodes: [ + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + Inode::empty(), + ], + } + } +} + +impl Block for InodeBlock {} + +const FULL_MAP: u32 = 0b111_111_111_111_111; + +#[derive(Clone)] +pub struct DirectoryBlock { + entries: [[u8; 256]; 15], + inode_ids: [usize; 15], + occupancy_map: u32, + reserved: [u8; 132], +} + +impl Default for DirectoryBlock { + fn default() -> Self { + Self { + entries: [[0; 256]; 15], + inode_ids: [0; 15], + occupancy_map: 0, + reserved: [0xFF; 132], + } + } +} + +impl Block for DirectoryBlock {} + +impl DirectoryBlock { + fn vacant(&self) -> bool { + self.occupancy_map & FULL_MAP != FULL_MAP + } + + fn first_free(&self) -> Option { + todo!() + } + + fn mark_busy(&mut self, entry_id: usize) { + todo!() + } + + /// 需要判断 entry_name.len() <= 255 + pub fn write_entry(&mut self, entry_name: &[u8], entry_inode_id: usize) -> Option { + if let Some(entry_id) = self.first_free() { + self.mark_busy(entry_id); + self.entries[entry_id].copy_from_slice(entry_name); + self.inode_ids[entry_id] = entry_inode_id; + Some(entry_id) + } else { + None + } + } +} + +#[derive(Clone)] +pub struct IndirectBlock { + pub entries: [u32; 1024], +} + +impl Default for IndirectBlock { + fn default() -> Self { + Self { entries: [0; 1024] } + } +} + +impl Block for IndirectBlock {} + +impl IndirectBlock { + pub fn full(&self) -> bool { + todo!() + } + + pub fn allocate(&mut self) -> Option { + todo!() + } +} + +#[derive(Clone)] +pub struct DoubleIndirectBlock { + pub indirect: [u32; 1024], +} + +impl Default for DoubleIndirectBlock { + fn default() -> Self { + Self { + indirect: [0; 1024], + } + } +} + +impl Block for DoubleIndirectBlock {} + +impl DoubleIndirectBlock { + pub fn full(&self) -> bool { + todo!() + } + + pub fn allocate(&mut self) -> Option { + todo!() + } +} + +#[derive(Clone)] +pub struct TripleIndirectBlock { + pub double_indirect: [u32; 1024], +} + +impl Default for TripleIndirectBlock { + fn default() -> Self { + Self { + double_indirect: [0; 1024], + } + } +} + +impl Block for TripleIndirectBlock {} + +impl TripleIndirectBlock { + pub fn full(&self) -> bool { + todo!() + } + + pub fn allocate(&mut self) -> Option { + todo!() + } +} diff --git a/src/disk/data_block.rs b/src/disk/data_block.rs deleted file mode 100644 index d287ee6..0000000 --- a/src/disk/data_block.rs +++ /dev/null @@ -1,168 +0,0 @@ -use crate::disk::inode::Inode; - -pub trait Block: Default + Clone {} - -#[derive(Clone)] -pub struct DataBlock(pub(crate) [u8; 4096]); - -impl Default for DataBlock { - fn default() -> Self { - Self([0; 4096]) - } -} - -impl Block for DataBlock {} - -#[derive(Clone)] -pub struct InodeBlock { - pub(crate) inodes: [Inode; 16], -} - -impl Default for InodeBlock { - fn default() -> Self { - Self { - inodes: [ - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - Inode::empty(), - ], - } - } -} - -impl Block for InodeBlock {} - -const FULL_MAP: u32 = 0b111_111_111_111_111; - -#[derive(Clone)] -pub struct DirectoryBlock { - entries: [[u8; 256]; 15], - inode_ids: [usize; 15], - occupancy_map: u32, - reserved: [u8; 132], -} - -impl Default for DirectoryBlock { - fn default() -> Self { - Self { - entries: [[0; 256]; 15], - inode_ids: [0; 15], - occupancy_map: 0, - reserved: [0xFF; 132], - } - } -} - -impl Block for DirectoryBlock {} - -impl DirectoryBlock { - fn vacant(&self) -> bool { - self.occupancy_map & FULL_MAP != FULL_MAP - } - - fn first_free(&self) -> Option { - todo!() - } - - fn mark_busy(&mut self, entry_id: usize) { - todo!() - } - - /// 需要判断 entry_name.len() <= 255 - pub fn write_entry(&mut self, entry_name: &[u8], entry_inode_id: usize) -> Option { - if let Some(entry_id) = self.first_free() { - self.mark_busy(entry_id); - self.entries[entry_id].copy_from_slice(entry_name); - self.inode_ids[entry_id] = entry_inode_id; - Some(entry_id) - } else { - None - } - } -} - -#[derive(Clone)] -pub struct IndirectBlock { - pub entries: [u32; 1024], -} - -impl Default for IndirectBlock { - fn default() -> Self { - Self { entries: [0; 1024] } - } -} - -impl Block for IndirectBlock {} - -impl IndirectBlock { - pub fn full(&self) -> bool { - todo!() - } - - pub fn allocate(&mut self) -> Option { - todo!() - } -} - -#[derive(Clone)] -pub struct DoubleIndirectBlock { - pub indirect: [u32; 1024], -} - -impl Default for DoubleIndirectBlock { - fn default() -> Self { - Self { - indirect: [0; 1024], - } - } -} - -impl Block for DoubleIndirectBlock {} - -impl DoubleIndirectBlock { - pub fn full(&self) -> bool { - todo!() - } - - pub fn allocate(&mut self) -> Option { - todo!() - } -} - -#[derive(Clone)] -pub struct TripleIndirectBlock { - pub double_indirect: [u32; 1024], -} - -impl Default for TripleIndirectBlock { - fn default() -> Self { - Self { - double_indirect: [0; 1024], - } - } -} - -impl Block for TripleIndirectBlock {} - -impl TripleIndirectBlock { - pub fn full(&self) -> bool { - todo!() - } - - pub fn allocate(&mut self) -> Option { - todo!() - } -} diff --git a/src/disk/mod.rs b/src/disk/mod.rs index 65f313c..878e832 100644 --- a/src/disk/mod.rs +++ b/src/disk/mod.rs @@ -1,7 +1,6 @@ +pub mod allocation; /// On-disk data structures and logic. /// Including bitmaps, inodes and blocks. - pub mod bitmap; +pub mod block; pub mod inode; -pub mod data_block; -pub mod allocation; diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs index 9f157a5..3a60578 100644 --- a/src/filesystem/trait_impl.rs +++ b/src/filesystem/trait_impl.rs @@ -1,9 +1,12 @@ -use std::ffi::OsStr; -use std::time::SystemTime; -use fuser::{Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry, ReplyLseek, ReplyWrite, Request, TimeOrNow}; +use crate::AyaFS; +use fuser::{ + Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry, + ReplyLseek, ReplyWrite, Request, TimeOrNow, +}; use libc::{c_int, ENOENT, ENOSPC, ENOSYS}; use log::debug; -use crate::AyaFS; +use std::ffi::OsStr; +use std::time::SystemTime; impl Filesystem for AyaFS { fn init(&mut self, _req: &Request<'_>, _config: &mut KernelConfig) -> Result<(), c_int> { @@ -186,4 +189,4 @@ impl Filesystem for AyaFS { ); reply.error(ENOSYS); } -} \ No newline at end of file +} diff --git a/src/main.rs b/src/main.rs index e01d352..a5ec616 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,7 +1,8 @@ mod block_device; mod disk; -mod memory; mod filesystem; +mod memory; +mod tests; mod utils; use clap::Parser; @@ -12,12 +13,14 @@ use std::num::NonZeroUsize; use std::sync::Arc; use std::time::Duration; -use memory::cached_block::CachedBlock; -use disk::data_block::DataBlock; +use crate::disk::block::InodeBlock; use crate::disk::inode::InodeMode; -use block_device::{BLOCK_SIZE, BlockDevice, memory_disk::MemoryDisk}; +use crate::memory::cached_block::BlockCache; +use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE}; use disk::bitmap::Bitmap; +use disk::block::DataBlock; use disk::inode::INODE_SIZE; +use memory::cached_block::CachedBlock; use users::{get_current_gid, get_current_uid}; #[derive(Parser, Debug)] @@ -61,8 +64,10 @@ struct AyaFS { inode_start_block: usize, data_start_block: usize, - // cached_inodes: LruCache, - cached_blocks: LruCache>, + cached_inodes: BlockCache, + cached_blocks: BlockCache, + // cached_inodes: LruCache>, + // cached_blocks: LruCache>, } impl AyaFS { @@ -103,7 +108,7 @@ impl AyaFS { let _ = inode_bitmap.allocate().unwrap(); // inode block 0 is not usable let mut fs = Self { - device, + device: device.clone(), data_bitmap, inode_bitmap, inode_start_block: data_bitmap_block_number + inode_bitmap_block_number + 1, @@ -111,8 +116,10 @@ impl AyaFS { + inode_bitmap_block_number + inode_block_number + 1, + cached_inodes: BlockCache::new(device.clone(), 256), + cached_blocks: BlockCache::new(device.clone(), 256), // cached_inodes: LruCache::new(NonZeroUsize::new(256).unwrap()), - cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()), + // cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()), }; fs.create_inode( @@ -137,7 +144,7 @@ fn main() { MountOption::AutoUnmount, MountOption::AllowRoot, ]; - let mem_disk = Arc::new(MemoryDisk::new()); + let mem_disk = Arc::new(MemoryDisk::new(16384)); let filesystem = AyaFS::new(mem_disk, 16384); fuser::mount2(filesystem, mount_point, &options).unwrap(); 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; diff --git a/src/tests/bitmap.rs b/src/tests/bitmap.rs new file mode 100644 index 0000000..9b21b6f --- /dev/null +++ b/src/tests/bitmap.rs @@ -0,0 +1,23 @@ +use crate::tests::common; + +#[test] +fn test_allocate() { + let mut fs = common::setup(); + for _ in 0..10 { + fs.data_bitmap.allocate().unwrap(); + } + assert!(fs.data_bitmap.deallocate(5)); + assert_eq!(fs.data_bitmap.allocate().unwrap(), 5); + assert_eq!(fs.data_bitmap.allocate().unwrap(), 11); +} + +#[test] +fn test_query() { + let mut fs = common::setup(); + for _ in 0..10 { + fs.data_bitmap.allocate().unwrap(); + } + assert_eq!(fs.data_bitmap.query(0), false); + assert_eq!(fs.data_bitmap.query(5), true); + assert_eq!(fs.data_bitmap.query(11), false); +} diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs new file mode 100644 index 0000000..f1c18cc --- /dev/null +++ b/src/tests/block_cache.rs @@ -0,0 +1,79 @@ +use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock}; +use crate::disk::inode::InodeMode; +use crate::tests::common; + +#[test] +fn test_basic_lru() { + let mut fs = common::setup(); + + let v: Vec = (1..=256) + .map(|_| { + let index = fs.data_bitmap.allocate().unwrap(); + fs.get_block::(index).unwrap(); + index + }) + .collect(); + assert!(fs.peek_block::(v[0]).is_some()); + + for i in 0..256 { + let index = fs.data_bitmap.allocate().unwrap(); + fs.get_block::(index).unwrap(); + assert!(fs.peek_block::(v[i]).is_none()); + } +} + +#[test] +fn test_inode() { + let mut fs = common::setup(); + + let inode_index = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap(); + let mut inode = fs.get_inode(inode_index).unwrap().clone(); + + const DIRECT_NUMBER: u32 = 15; + const INDIRECT_NUMBER: u32 = 1024; + const DOUBLE_INDIRECT_NUMBER: u32 = 1024 * 1024; + + for i in 0..DIRECT_NUMBER { + fs.allocate_block_for(&mut inode).unwrap(); + assert!(fs.data_bitmap.query(inode.direct[i as usize] as usize)) + } + + for i in 0..INDIRECT_NUMBER { + fs.allocate_block_for(&mut inode).unwrap(); + } + + for i in 0..DOUBLE_INDIRECT_NUMBER { + fs.allocate_block_for(&mut inode).unwrap(); + } + + let single_indirect = inode.single_indirect; + let double_indirect = inode.double_indirect; + let triple_indirect = inode.triple_indirect; + + fs.update_inode(inode_index, inode); + + let indirect_block = fs + .peek_block::(single_indirect as usize) + .unwrap(); + for entry in indirect_block.block.entries { + assert_ne!(entry, 0); + assert!(fs.data_bitmap.query(entry as usize)); + } + + // let double_indirect_block = fs + // .peek_block::(double_indirect as usize) + // .unwrap(); + // for indirect_entry in double_indirect_block.block.indirect { + // let indirect_block = fs + // .peek_block::(indirect_entry as usize) + // .unwrap(); + // for entry in indirect_block.block.entries { + // assert_ne!(entry, 0); + // assert!(fs.data_bitmap.query(entry as usize)); + // } + // } + + assert_eq!(fs.data_bitmap.query(double_indirect as usize), false); + + assert_eq!(fs.data_bitmap.query(triple_indirect as usize), false); +} diff --git a/src/tests/common/mod.rs b/src/tests/common/mod.rs new file mode 100644 index 0000000..9314fd9 --- /dev/null +++ b/src/tests/common/mod.rs @@ -0,0 +1,8 @@ +use crate::block_device::memory_disk::MemoryDisk; +use crate::AyaFS; +use std::sync::Arc; + +pub(crate) fn setup() -> AyaFS { + let mem_disk = Arc::new(MemoryDisk::new(1059715)); + AyaFS::new(mem_disk, 1059715) +} diff --git a/src/tests/mod.rs b/src/tests/mod.rs new file mode 100644 index 0000000..df442c1 --- /dev/null +++ b/src/tests/mod.rs @@ -0,0 +1,6 @@ +#[cfg(test)] +mod bitmap; +mod common; + +#[cfg(test)] +mod block_cache; -- cgit v1.2.3-70-g09d2