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 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 128 insertions(+), 3 deletions(-) (limited to 'src/disk/allocation.rs') 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 + } +} -- cgit v1.2.3-70-g09d2