From 777d5e01a34b8ebe6f1a5751b593266f93e88499 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Sat, 25 Nov 2023 19:36:31 -0800 Subject: Add dir entry operations --- src/disk/allocation.rs | 159 ++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 132 insertions(+), 27 deletions(-) (limited to 'src/disk/allocation.rs') diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs index bde2014..57cca0e 100644 --- a/src/disk/allocation.rs +++ b/src/disk/allocation.rs @@ -1,20 +1,20 @@ -use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; -use crate::disk::inode::Inode; -use crate::memory::cached_block::convert; -use crate::AyaFS; +use crate::disk::block::{Block, DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; +use crate::disk::inode::{DIRECT_NUMBER, Inode}; +use crate::memory::cached_block::{CachedBlock, convert}; +use crate::{AyaFS, INODE_PER_BLOCK}; impl AyaFS { - /// 为 Inode 分配新 block, 返回 block 的编号 - pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option { + /// 为 Inode 分配新 block, 返回 block 的编号和它在 inode 内的编号 + pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<(u32, usize)> { // 先看这个 inode 的 direct block 有没有空闲 - for index in inode.direct.iter_mut() { + for (index_within_direct, index) in inode.direct.iter_mut().enumerate() { 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 里已经脏了 - return Some(block_index); + return Some((block_index, index_within_direct)); } } @@ -27,10 +27,11 @@ impl AyaFS { // println!("allocating {} for indirect", inode.single_indirect); } // 在 indirect block 里尝试分配 - if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) { + if let Some((block_index, index_within_indirect)) = self.allocate_in_indirect(inode.single_indirect) { // println!("allocating {} in indirect", block_index); inode.n_blocks += 1; - return Some(block_index); + let index_within_block = DIRECT_NUMBER + index_within_indirect; + return Some((block_index, index_within_block)); } // direct & indirect block 全部分配完了, 先检查 double indirect block 有没有分配, 没有就分配一个 @@ -42,10 +43,11 @@ impl AyaFS { // println!("allocating {} for double indirect", inode.double_indirect); } // 在 double indirect block 里尝试分配 - if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) { + if let Some((block_index, index_within_double)) = self.alloc_in_double_indirect(inode.double_indirect) { // println!("allocating {} in double indirect", block_index); inode.n_blocks += 1; - return Some(block_index); + let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + index_within_double; + return Some((block_index, index_within_block)); } // direct, indirect & double indirect block 全部分配完了, 先检查 triple indirect block 有没有分配, 没有就分配一个 @@ -57,15 +59,16 @@ impl AyaFS { // println!("allocating {} for triple indirect", inode.triple_indirect); } // 在 double indirect block 里尝试分配 - if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) { + if let Some((block_index, index_within_triple)) = self.alloc_in_triple_indirect(inode.triple_indirect) { // println!("allocating {} in triple indirect", block_index); inode.n_blocks += 1; - return Some(block_index); + let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_triple; + return Some((block_index, index_within_block)); } None } - fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option { + fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<(u32, usize)> { // 取出 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)); @@ -76,20 +79,20 @@ impl AyaFS { { // println!("found indirect block with number {}", indirect_entry); let mut indirect_block = block.clone(); - for entry in indirect_block.block.entries.iter_mut() { + for (index_within_indirect, entry) in indirect_block.block.entries.iter_mut().enumerate() { if self.data_bitmap.query(*entry as usize) == false { indirect_block.dirty = true; // 把这个块标记为 dirty let block_index = self.data_bitmap.allocate().expect("No free space") as u32; *entry = block_index; self.update_block(indirect_block); - return Some(block_index); + return Some((block_index, index_within_indirect)); } } } None } - fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option { + fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<(u32, usize)> { let double_indirect_entry = double_indirect_entry as usize; if let Some(block) = self @@ -97,24 +100,27 @@ impl AyaFS { .map(convert::) { let mut double_indirect_block = block.clone(); - for indirect_entry in double_indirect_block.block.indirect.iter_mut() { + let mut double_indirect_modified = false; + for (index_within_double_indirect, indirect_entry) in double_indirect_block.block.indirect.iter_mut().enumerate() { if self.data_bitmap.query(*indirect_entry as usize) == false { double_indirect_block.dirty = true; + double_indirect_modified = true; *indirect_entry = self.data_bitmap.allocate().expect("No free space") as u32; } - if let Some(block_index) = self.allocate_in_indirect(*indirect_entry) { - if double_indirect_block.dirty { + if let Some((block_index, index_within_indirect)) = self.allocate_in_indirect(*indirect_entry) { + if double_indirect_modified { self.update_block(double_indirect_block); } - return Some(block_index); + let index_within_double = index_within_double_indirect * INODE_PER_BLOCK + index_within_indirect; + return Some((block_index, index_within_double)); } } } None } - fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option { + fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option<(u32, usize)> { let triple_indirect_entry = triple_indirect_entry as usize; if let Some(block) = self @@ -122,17 +128,20 @@ impl AyaFS { .map(convert::) { let mut triple_indirect_block = block.clone(); - for double_indirect_entry in triple_indirect_block.block.double_indirect.iter_mut() { + let mut triple_indirect_modified = false; + for (index_within_triple_indirect, double_indirect_entry) in triple_indirect_block.block.double_indirect.iter_mut().enumerate() { if self.data_bitmap.query(*double_indirect_entry as usize) == false { triple_indirect_block.dirty = true; + triple_indirect_modified = true; *double_indirect_entry = self.data_bitmap.allocate().expect("No free space") as u32; } - if let Some(block_index) = self.alloc_in_double_indirect(*double_indirect_entry) { - if triple_indirect_block.dirty { + if let Some((block_index, index_within_double_indirect)) = self.alloc_in_double_indirect(*double_indirect_entry) { + if triple_indirect_modified { self.update_block(triple_indirect_block); } - return Some(block_index); + let index_within_triple = index_within_triple_indirect * INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_double_indirect; + return Some((block_index, index_within_triple)); } } } @@ -283,3 +292,99 @@ impl AyaFS { None } } + +impl AyaFS { + fn get_block_index(&mut self, inode: &Inode, mut block_index_within_inode: usize) -> Option { + // direct block + if block_index_within_inode < DIRECT_NUMBER { + let block_index = inode.direct[block_index_within_inode] as usize; + return Some(block_index); + } else { + block_index_within_inode -= DIRECT_NUMBER; + } + + // indirect block + let indirect_number = INODE_PER_BLOCK; + if block_index_within_inode < indirect_number { + return if let Some(indirect_block) = + self.get_block::(inode.single_indirect as usize) + { + let block_index = indirect_block.block.entries[block_index_within_inode] as usize; + Some(block_index) + } else { + None + }; + } else { + block_index_within_inode -= indirect_number; + } + + // double indirect block + let double_indirect_number = INODE_PER_BLOCK * INODE_PER_BLOCK; + if block_index_within_inode < double_indirect_number { + if let Some(double_indirect_block) = + self.get_block::(inode.double_indirect as usize) + { + // 取出 double indirect block + let indirect_block_index = double_indirect_block.block.indirect + [block_index_within_inode / INODE_PER_BLOCK] + as usize; + // 要找的 entry 在 double indirect block 中的第几个 indirect block + if let Some(indirect_block) = self.get_block::(indirect_block_index) + { + let block_index = indirect_block.block.entries + [block_index_within_inode % INODE_PER_BLOCK] + as usize; + // 拿到 DirectoryBlock 的 index + return Some(block_index) + } + } + return None; + } else { + block_index_within_inode -= double_indirect_number; + } + + // triple indirect block + if let Some(triple_indirect_block) = + self.get_block::(inode.triple_indirect as usize) + { + // 取出 triple indirect block + let double_indirect_block_index = triple_indirect_block.block.double_indirect + [block_index_within_inode / (INODE_PER_BLOCK * INODE_PER_BLOCK)] + as usize; + // 要找的 entry 在 triple indirect block 中的第几个 double indirect block + if let Some(double_indirect_block) = + self.get_block::(double_indirect_block_index) + { + // 取出 double indirect block + let indirect_block_index = double_indirect_block.block.indirect + [block_index_within_inode % (INODE_PER_BLOCK * INODE_PER_BLOCK) + / INODE_PER_BLOCK] as usize; + // 要找的 entry 在 double indirect block 中的第几个 indirect block + if let Some(indirect_block) = self.get_block::(indirect_block_index) + { + let block_index = indirect_block.block.entries + [block_index_within_inode % INODE_PER_BLOCK] + as usize; + // DirectoryBlock 的 index + return Some(block_index) + } + } + } + + None + } + + pub(crate) fn access_block(&mut self, inode: &Inode, block_index_within_inode: usize) -> Option<&CachedBlock> { + self.get_block_index(inode, block_index_within_inode) + .map(|block_index| { + self.get_block::(block_index).unwrap() // 可以 unwrap 吧这里 ?? + }) + } + + pub(crate) fn access_block_mut(&mut self, inode: &Inode, block_index_within_inode: usize) -> Option<&mut CachedBlock> { + self.get_block_index(inode, block_index_within_inode) + .map(|block_index| { + self.get_block_mut::(block_index).unwrap() // 可以 unwrap 吧这里 ?? + }) + } +} \ No newline at end of file -- cgit v1.2.3-70-g09d2