From 3f2151c043177501b0c7beb580d9737e3d824ad0 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Wed, 22 Nov 2023 00:04:28 -0800 Subject: bugfix for layer 1 --- src/disk/allocation.rs | 76 +++++++++++++++-------- src/tests/block_cache.rs | 154 ++++++++++++++++++++++++++++++++++++++--------- 2 files changed, 178 insertions(+), 52 deletions(-) diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs index 3622e4f..bfdba46 100644 --- a/src/disk/allocation.rs +++ b/src/disk/allocation.rs @@ -1,6 +1,6 @@ use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; use crate::disk::inode::Inode; -use crate::memory::cached_block::convert; +use crate::memory::cached_block::{convert, convert_mut}; use crate::AyaFS; impl AyaFS { @@ -10,7 +10,7 @@ impl AyaFS { 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); + // println!("allocating {} for direct", block_index); *index = block_index; inode.n_blocks += 1; // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了 @@ -24,11 +24,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; - println!("allocating {} for indirect", inode.single_indirect); + // 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); + // println!("allocating {} in indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -39,11 +39,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; - println!("allocating {} for double indirect", inode.double_indirect); + // 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); + // println!("allocating {} in double indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -54,11 +54,11 @@ impl AyaFS { .data_bitmap .allocate() .expect("No free space for new block") as u32; - println!("allocating {} for triple indirect", inode.triple_indirect); + // 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); + // println!("allocating {} in triple indirect", block_index); inode.n_blocks += 1; return Some(block_index); } @@ -142,7 +142,7 @@ impl AyaFS { impl AyaFS { /// 从 inode 中删去最后一个 block - pub(crate) fn deallocate_block(&mut self, inode: &mut Inode) -> Option { + pub(crate) fn deallocate_block_for(&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) { @@ -189,28 +189,39 @@ impl AyaFS { 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) + .get_block(triple_indirect_entry) .map(convert::) { + let mut triple_indirect_block = triple_indirect_block.clone(); + let mut block_modified = false; for double_indirect_entry in triple_indirect_block .block .double_indirect - .into_iter() + .iter_mut() .rev() { // 如果这个位置的 double indirect 存在 - if self.data_bitmap.query(double_indirect_entry as usize) { + if self.data_bitmap.query(*double_indirect_entry as usize) { // 尝试从中销毁一个块 if let Some(block_index) = - self.deallocate_from_double_indirect(double_indirect_entry) + self.deallocate_from_double_indirect(*double_indirect_entry) { + if block_modified { + self.update_block(triple_indirect_block); + } return Some(block_index); // 成功则直接返回 } else { // 失败则把这个 double indirect 销毁 - self.data_bitmap.deallocate(double_indirect_entry as usize); + let double_indirect_entry_to_deallocate = std::mem::replace(double_indirect_entry, 0); + self.data_bitmap.deallocate(double_indirect_entry_to_deallocate as usize); + triple_indirect_block.dirty = true; + block_modified = true; } } } + if block_modified { + self.update_block(triple_indirect_block); + } } None } @@ -218,21 +229,32 @@ impl AyaFS { 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) + .get_block(double_indirect_entry) .map(convert::) { - for indirect_entry in double_indirect_block.block.indirect.into_iter().rev() { + let mut double_indirect_block = double_indirect_block.clone(); + let mut block_modified = false; + for indirect_entry in double_indirect_block.block.indirect.iter_mut().rev() { // 如果这个位置的 indirect 存在 - if self.data_bitmap.query(indirect_entry as usize) { + if self.data_bitmap.query(*indirect_entry as usize) { // 尝试从中销毁一个块 - if let Some(block_index) = self.deallocate_from_indirect(indirect_entry) { + if let Some(block_index) = self.deallocate_from_indirect(*indirect_entry) { + if block_modified { + self.update_block(double_indirect_block); + } return Some(block_index); // 成功则直接返回 } else { // 失败则把这个 indirect 销毁 - self.data_bitmap.deallocate(indirect_entry as usize); + let indirect_entry_to_deallocate = std::mem::replace(indirect_entry, 0); + self.data_bitmap.deallocate(indirect_entry_to_deallocate as usize); + double_indirect_block.dirty = true; + block_modified = true; } } } + if block_modified { + self.update_block(double_indirect_block); + } } None } @@ -240,15 +262,21 @@ impl AyaFS { 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) + .get_block(indirect_entry) .map(convert::) { + let mut indirect_block = indirect_block.clone(); // 遍历 indirect block 里的每个 block - for entry in indirect_block.block.entries.into_iter().rev() { + for entry in indirect_block.block.entries.iter_mut().rev() { // 如果这个 block 存在, 销毁它 - if self.data_bitmap.query(entry as usize) { - self.data_bitmap.deallocate(entry as usize); - return Some(entry); + if self.data_bitmap.query(*entry as usize) { + let entry_to_deallocate = std::mem::replace(entry, 0); + + self.data_bitmap.deallocate(entry_to_deallocate as usize); + indirect_block.dirty = true; + self.update_block(indirect_block); + + return Some(entry_to_deallocate); } } } diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs index f1c18cc..bbea3a0 100644 --- a/src/tests/block_cache.rs +++ b/src/tests/block_cache.rs @@ -23,7 +23,7 @@ fn test_basic_lru() { } #[test] -fn test_inode() { +fn test_inode_allocation() { let mut fs = common::setup(); let inode_index = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap(); @@ -31,49 +31,147 @@ fn test_inode() { const DIRECT_NUMBER: u32 = 15; const INDIRECT_NUMBER: u32 = 1024; - const DOUBLE_INDIRECT_NUMBER: u32 = 1024 * 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 { + for _i in 0..INDIRECT_NUMBER { fs.allocate_block_for(&mut inode).unwrap(); } - for i in 0..DOUBLE_INDIRECT_NUMBER { + println!("single indirect is {}", inode.single_indirect); + println!("double indirect is {}", inode.double_indirect); + println!("triple indirect is {}", inode.triple_indirect); + + let indirect_block = fs + .peek_block::(inode.single_indirect 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(inode.double_indirect as usize), false); + assert_eq!(fs.data_bitmap.query(inode.triple_indirect as usize), false); + + for _i in 0..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; + println!("double indirect is {} after allocation", inode.double_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)); + assert!(fs.data_bitmap.query(double_indirect as usize)); +} + +#[test] +fn test_inode_deallocation() { + 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 { + println!("Allocated {}", fs.allocate_block_for(&mut inode).unwrap()); + assert!(fs.data_bitmap.query(inode.direct[i as usize] as usize)) + } + + for _i in 0..2 * INDIRECT_NUMBER { + println!("Allocated {}", fs.allocate_block_for(&mut inode).unwrap()); + } + + println!("single indirect is {}", inode.single_indirect); + println!("double indirect is {}", inode.double_indirect); + println!("triple indirect is {}", inode.triple_indirect); + + assert!(fs.data_bitmap.query(inode.double_indirect as usize)); + + for i in 0..INDIRECT_NUMBER + 5 { + println!("Deallocated {}", fs.deallocate_block_for(&mut inode).unwrap()); } - // 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); + println!("single indirect is {}", inode.single_indirect); + println!("double indirect is {}", inode.double_indirect); + println!("triple indirect is {}", inode.triple_indirect); + + assert_eq!(fs.data_bitmap.query(inode.double_indirect as usize), false); + + fs.update_inode(inode_index, inode); } + +#[test] +fn test_multiple_inode_allocation() { + let mut fs = common::setup(); + + let inode_index_1 = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap(); + let inode_index_2 = fs.create_inode(0o755, InodeMode::IFREG, 0, 0, 0).unwrap(); + + let mut inode_1 = fs.get_inode(inode_index_1).unwrap().clone(); + let mut inode_2 = fs.get_inode(inode_index_2).unwrap().clone(); + + const DIRECT_NUMBER: u32 = 15; + const INDIRECT_NUMBER: u32 = 1024; + + for i in 0 .. DIRECT_NUMBER + INDIRECT_NUMBER { + println!("Allcoated {} in inode {}", fs.allocate_block_for(&mut inode_1).unwrap(), inode_index_1); + println!("Allcoated {} in inode {}", fs.allocate_block_for(&mut inode_2).unwrap(), inode_index_2); + } + + let inode_index_3 = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap(); + let mut inode_3 = fs.get_inode(inode_index_3).unwrap().clone(); + + for _i in 0 .. INDIRECT_NUMBER { + println!("Deallcoated {} in inode {}", fs.deallocate_block_for(&mut inode_1).unwrap(), inode_index_1); + println!("Allcoated {} in inode {}", fs.allocate_block_for(&mut inode_3).unwrap(), inode_index_3); + } + + for _i in 0 .. DIRECT_NUMBER { + println!("Deallcoated {} in inode {}", fs.deallocate_block_for(&mut inode_1).unwrap(), inode_index_1); + } + + assert!(fs.deallocate_block_for(&mut inode_1).is_none()); + + println!("single indirect is {} for {}", inode_1.single_indirect, inode_index_1); + println!("double indirect is {} for {}", inode_1.double_indirect, inode_index_1); + println!("single indirect is {} for {}", inode_2.single_indirect, inode_index_2); + println!("double indirect is {} for {}", inode_2.double_indirect, inode_index_2); + println!("single indirect is {} for {}", inode_3.single_indirect, inode_index_3); + println!("double indirect is {} for {}", inode_3.double_indirect, inode_index_3); + + assert_eq!(fs.data_bitmap.query(inode_1.single_indirect as usize), false); + assert!(fs.data_bitmap.query(inode_2.single_indirect as usize)); + assert_eq!(fs.data_bitmap.query(inode_2.double_indirect as usize), false); + assert!(fs.data_bitmap.query(inode_3.single_indirect as usize)); + assert_eq!(fs.data_bitmap.query(inode_3.double_indirect as usize), false); + + fs.allocate_block_for(&mut inode_2).unwrap(); + println!("-----------------"); + println!("double indirect is {} for {}", inode_2.double_indirect, inode_index_2); + + assert!(fs.data_bitmap.query(inode_2.double_indirect as usize)); + + for _i in 0 .. DIRECT_NUMBER { + fs.allocate_block_for(&mut inode_3).unwrap(); + } + println!("-----------------"); + println!("double indirect is {} for {}", inode_3.double_indirect, inode_index_3); + assert_eq!(fs.data_bitmap.query(inode_3.double_indirect as usize), false); + + fs.allocate_block_for(&mut inode_3).unwrap(); + println!("-----------------"); + println!("double indirect is {} for {}", inode_3.double_indirect, inode_index_3); + assert!(fs.data_bitmap.query(inode_3.double_indirect as usize)); + + fs.update_inode(inode_index_1, inode_1); + fs.update_inode(inode_index_2, inode_2); + fs.update_inode(inode_index_3, inode_3); +} \ No newline at end of file -- cgit v1.2.3-70-g09d2