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/memory/cached_block.rs | 22 +++-- src/memory/cached_inode.rs | 2 +- src/memory/dir_entry.rs | 103 ++++++++++++++++++++ src/memory/inode_iter.rs | 233 --------------------------------------------- src/memory/mod.rs | 2 +- 5 files changed, 121 insertions(+), 241 deletions(-) create mode 100644 src/memory/dir_entry.rs delete mode 100644 src/memory/inode_iter.rs (limited to 'src/memory') diff --git a/src/memory/cached_block.rs b/src/memory/cached_block.rs index 77cdf61..783e987 100644 --- a/src/memory/cached_block.rs +++ b/src/memory/cached_block.rs @@ -70,6 +70,7 @@ impl BlockCache { } /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载. + /// 这个函数不应该返回 None pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { if !self.cache.contains(&index) { self.load_block(index); @@ -78,11 +79,15 @@ impl BlockCache { } /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载. + /// 这个函数不应该返回 None pub(crate) fn get_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { if !self.cache.contains(&index) { self.load_block(index); } - self.cache.get_mut(&index).map(convert_mut::) + self.cache.get_mut(&index).map(|block| { + block.dirty = true; + convert_mut::(block) + }) } /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. @@ -97,7 +102,8 @@ impl BlockCache { pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { if self.cache.contains(&block.index) { - let data_block = convert::(&block).clone(); + let mut data_block = convert::(&block).clone(); + data_block.dirty = true; // TODO 需要把显式写回的都标记为 dirty 吗 self.cache.push(block.index, data_block); true } else { @@ -123,25 +129,29 @@ impl AyaFS { pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { self.data_bitmap .query(index) - .and_then(|| self.cached_blocks.get_block::(index)) + .then(|| self.cached_blocks.get_block::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid } 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)) + .then(|| self.cached_blocks.get_block_mut::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid } pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { self.data_bitmap .query(index) - .and_then(|| self.cached_blocks.peek_block::(index)) + .then(|| self.cached_blocks.peek_block::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid } 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)) + .then(|| self.cached_blocks.peek_block_mut::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid } pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs index be87850..b1be2de 100644 --- a/src/memory/cached_inode.rs +++ b/src/memory/cached_inode.rs @@ -34,7 +34,7 @@ impl AyaFS { let mut new_inode = Inode::directory(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0); // 分配第一个 direct block - new_inode.direct[0] = self.allocate_block_for(&mut new_inode).unwrap(); + (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap(); new_inode.size = 2; // 在 direct block 里分配 . 和 .. if let Some(directory_block) = diff --git a/src/memory/dir_entry.rs b/src/memory/dir_entry.rs new file mode 100644 index 0000000..0ade23f --- /dev/null +++ b/src/memory/dir_entry.rs @@ -0,0 +1,103 @@ +use std::ffi::OsStr; +use std::os::unix::ffi::OsStrExt; +use libc::{c_int, ENOENT, ENOSPC}; +use crate::disk::block::{DirectoryBlock, DirectoryEntry}; +use crate::disk::inode::{Inode}; +use crate::AyaFS; + +impl AyaFS { + pub(crate) fn remove_direntry( + &mut self, + parent_inode: &mut Inode, + entry_index: u32 + ) -> Result<(), c_int> { + let block_index_within_inode = (entry_index / 15) as usize; + let entry_index_within_block = (entry_index % 15) as usize; + + match self.access_block_mut::(parent_inode, block_index_within_inode) { + Some(directory_block) => { + if directory_block.block.query(entry_index_within_block) { + directory_block.block.deallocate(entry_index_within_block); + directory_block.block.entries[entry_index_within_block] = DirectoryEntry::default(); + Ok(()) + } else { + Err(ENOENT) + } + } + None => Err(ENOENT), + } + } + + pub(crate) fn add_direntry( + &mut self, + parent_inode: &mut Inode, + child_inode_index: u32, + child_inode_name: &OsStr, + child_inode: &Inode, + ) -> Result { + // 找到第一个有空闲 DirEntry 的块, 从中分配一个 entry + let mut block_index_within_inode: usize = 0; + loop { + // 所有已经分配的块都用完, 需要额外分配一个块了 + if block_index_within_inode as u32 == parent_inode.n_blocks { + if self.allocate_block_for(parent_inode).is_none() { + return Err(ENOSPC); + } + } + // 寻找当前块里有没有空闲空间 + if let Some(directory_block) = self.access_block_mut::(parent_inode, block_index_within_inode) { + if let Some(entry_index_within_block) = directory_block.block.allocate() { + // 如果有空闲空间, 可以分配一个块 + let name_len = child_inode_name.len() as u8; + let file_type = child_inode.mode.into(); + let mut name = [0u8; 256]; + name.copy_from_slice(child_inode_name.as_bytes()); + + let dir_entry = DirectoryEntry { + inode: child_inode_index, + record_len: 264, + name_len, + file_type, + name, + }; + directory_block.block.entries[entry_index_within_block] = dir_entry; + let entry_index = block_index_within_inode * 15 + entry_index_within_block; + return Ok(entry_index as u32); + } + } + block_index_within_inode += 1; + }; + } + pub(crate) fn get_direntry( + &mut self, + parent_inode: &Inode, + entry_index: u32 + ) -> Option { + let block_index_within_inode = (entry_index / 15) as usize; + let entry_index_within_block = (entry_index % 15) as usize; + + self.access_block::(parent_inode, block_index_within_inode) + .and_then(|directory_block| { + if directory_block.block.query(entry_index_within_block) { + Some(directory_block.block.entries[entry_index_within_block].clone()) + } else { + None + } + }) + } + + // TODO 实现一个带 cache 的版本 + pub fn lookup_name(&mut self, parent_inode: &Inode, name: &OsStr) -> Result<(u32, u32, Inode), c_int> { + let mut entry_index = 0; + while entry_index < parent_inode.size { + if let Some(entry) = self.get_direntry(parent_inode, entry_index) { + if entry.name() == name { + let inode = self.get_inode(entry.inode as usize).unwrap().clone(); + return Ok((entry.inode, entry_index, inode)) + } + } + entry_index += 1; + } + Err(ENOENT) + } +} diff --git a/src/memory/inode_iter.rs b/src/memory/inode_iter.rs deleted file mode 100644 index d5909bc..0000000 --- a/src/memory/inode_iter.rs +++ /dev/null @@ -1,233 +0,0 @@ -use std::ffi::OsStr; -use std::os::unix::ffi::OsStrExt; -use libc::{c_int, ENOENT, ENOSPC}; -use crate::disk::block::{Block, DirectoryBlock, DirectoryEntry, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; -use crate::disk::inode::{Inode, DIRECT_NUMBER}; -use crate::{AyaFS, INODE_PER_BLOCK}; -use crate::memory::cached_block::CachedBlock; - -impl AyaFS { - pub(crate) fn access_block(&mut self, inode: &Inode, mut block_index_within_inode: usize) -> Option<&CachedBlock> { - // direct block - if block_index_within_inode < DIRECT_NUMBER { - let block_index = inode.direct[block_index_within_inode] as usize; - return self.get_block::(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; - self.get_block::(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 self.get_block::(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 self.get_block::(block_index); - } - } - } - - None - } - - pub(crate) fn add_direntry( - &mut self, - parent_inode: &mut Inode, - child_inode_index: u32, - child_inode_name: &OsStr, - child_inode: &Inode, - ) -> Result { - let entry_index = parent_inode.size; - let block_index_within_inode = (entry_index / 15) as usize; - let entry_index_within_block = (entry_index % 15) as usize; - - // TODO 如果 block 内 offset 是 0 （或者访问到 block_index_within_inode 无效?）则为 Inode 分配新的 block - - // TODO 把新的 entry 写到对应位置 - - Err(ENOSPC) - } - pub(crate) fn get_direntry( - &mut self, - inode: &Inode, - entry_index: u32 - ) -> Option { - let block_index_within_inode = (entry_index / 15) as usize; - let entry_index_within_block = (entry_index % 15) as usize; - - self.access_block::(inode, block_index_within_inode) - .map(|directory_block| { - directory_block.block.entries[entry_index_within_block].clone() - }) - } - - // pub(crate) fn get_direntry( - // &mut self, - // inode: &Inode, - // entry_index: u32, - // ) -> Option { - // // 每个 DirectoryBlock 里有 15 个 entry, 先确定 block 再确定 offset - // let mut block_index_within_inode = (entry_index / 15) as usize; - // let entry_index_within_block = (entry_index % 15) as usize; - // - // // direct block - // if block_index_within_inode < DIRECT_NUMBER { - // let block_index = inode.direct[block_index_within_inode] as usize; - // return self - // .get_block::(block_index) - // .map(|inode_block| inode_block.block.entries[entry_index_within_block].clone()); - // } 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; - // self.get_block::(block_index) - // .map(|inode_block| inode_block.block.entries[entry_index_within_block].clone()) - // } 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 self - // .get_block::(block_index) - // .map(|inode_block| { - // inode_block.block.entries[entry_index_within_block].clone() - // }); - // } - // } - // 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 self - // .get_block::(block_index) - // .map(|inode_block| { - // inode_block.block.entries[entry_index_within_block].clone() - // }); - // } - // } - // } - // None - // } - - // TODO 实现一个带 cache 的版本 - pub fn lookup_name(&mut self, parent_inode: &Inode, name: &OsStr) -> Result<(u32, Inode), c_int> { - let mut entry_index = 0; - while entry_index < parent_inode.size { - if let Some(entry) = self.get_direntry(parent_inode, entry_index) { - if entry.name() == name { - let inode = self.get_inode(entry.inode as usize).unwrap().clone(); - return Ok((entry.inode, inode)) - } - } - entry_index += 1; - } - Err(ENOENT) - } -} diff --git a/src/memory/mod.rs b/src/memory/mod.rs index dce7c42..4080114 100644 --- a/src/memory/mod.rs +++ b/src/memory/mod.rs @@ -2,4 +2,4 @@ /// This is where the crucial block and inode methods presented to upper calls implemented. pub mod cached_block; pub mod cached_inode; -mod inode_iter; +mod dir_entry; -- cgit v1.2.3-70-g09d2