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/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 +- 5 files changed, 310 insertions(+), 192 deletions(-) create mode 100644 src/disk/block.rs delete mode 100644 src/disk/data_block.rs (limited to 'src/disk') 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; -- cgit v1.2.3-70-g09d2