From 1eac97eea4ec0bcef0be061a2cba93a584355283 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Thu, 30 Nov 2023 02:15:06 -0800 Subject: Add real disk i/o, add mkfs.aya (not yet implemented) --- ayafs/src/memory/cached_block.rs | 180 +++++++++++++++++++++++ ayafs/src/memory/cached_inode.rs | 178 +++++++++++++++++++++++ ayafs/src/memory/dir_entry.rs | 305 +++++++++++++++++++++++++++++++++++++++ ayafs/src/memory/file_handle.rs | 15 ++ ayafs/src/memory/mod.rs | 6 + 5 files changed, 684 insertions(+) create mode 100644 ayafs/src/memory/cached_block.rs create mode 100644 ayafs/src/memory/cached_inode.rs create mode 100644 ayafs/src/memory/dir_entry.rs create mode 100644 ayafs/src/memory/file_handle.rs create mode 100644 ayafs/src/memory/mod.rs (limited to 'ayafs/src/memory') diff --git a/ayafs/src/memory/cached_block.rs b/ayafs/src/memory/cached_block.rs new file mode 100644 index 0000000..c3d0338 --- /dev/null +++ b/ayafs/src/memory/cached_block.rs @@ -0,0 +1,180 @@ +use crate::block_device::{BlockDevice, BLOCK_SIZE}; +use crate::disk::block::Block; +use crate::AyaFS; +use lru::LruCache; +use std::num::NonZeroUsize; +use std::sync::Arc; + +#[derive(Clone)] +pub struct CachedBlock { + pub block: T, + pub index: usize, + pub dirty: bool, +} + +pub fn convert_mut(input_block: &mut CachedBlock) -> &mut CachedBlock { + let ptr = input_block as *const CachedBlock as *mut u8; + let block = ptr.cast::>(); + unsafe { &mut *block } +} + +pub fn convert(input_block: &CachedBlock) -> &CachedBlock { + let ptr = input_block as *const CachedBlock as *mut u8; + let block = ptr.cast::>(); + unsafe { &*block } +} + +pub(crate) struct BlockCache { + device: Arc, + cache: LruCache>, +} + +impl BlockCache { + pub(crate) fn new(device: Arc, cache_size: usize) -> Self { + Self { + device, + cache: LruCache::new(NonZeroUsize::new(cache_size).unwrap()), + } + } + + pub(crate) fn load_block(&mut self, index: usize) -> bool { + if self.cache.contains(&index) == false { + let mut buffer = [0u8; BLOCK_SIZE]; + self.device.read(index, &mut buffer); + let block: T = unsafe { std::mem::transmute_copy(&buffer) }; + let cached_block = CachedBlock { + block, + index, + dirty: false, + }; + if let Some((old_index, old_block)) = self.cache.push(index, cached_block) { + assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入 + if old_block.dirty { + let old_block_ptr = &old_block.block as *const T as *mut u8; + let old_block_buffer = + unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) }; + self.device.write(old_index, old_block_buffer); + } + } + } + true + } + + /// 从 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); + } + self.cache.get(&index).map(convert::) + } + + /// 从 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(|block| { + block.dirty = true; + convert_mut::(block) + }) + } + + /// 向 LRU cache 中插入一个全新初始化的 block + /// 这个 block 全 0, 而且是 dirty 的, 即使被挤出去也会触发一次落盘 + pub(crate) fn init_block(&mut self, index: usize) { + let allocated_block = CachedBlock { + block: T::default(), + index, + dirty: true, + }; + if let Some((old_index, old_block)) = self.cache.push(index, allocated_block) { + if old_block.dirty { + let old_block_ptr = &old_block.block as *const T as *mut u8; + let old_block_buffer = + unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) }; + self.device.write(old_index, old_block_buffer); + } + } + } + + #[allow(unused)] + /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { + self.cache.peek(&index).map(convert::) + } + + #[allow(unused)] + /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载. + pub(crate) fn peek_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.cache.peek_mut(&index).map(convert_mut::) + } + + pub(crate) fn update_block(&mut self, block: CachedBlock) -> bool { + if self.cache.contains(&block.index) { + let mut data_block = convert::(&block).clone(); + data_block.dirty = true; // TODO 需要把显式写回的都标记为 dirty 吗 + self.cache.push(block.index, data_block); + true + } else { + false + } + } + + fn pop(&mut self, entry: &usize) -> Option> { + self.cache.pop(entry) + } +} + +impl AyaFS { + pub(crate) fn init_block(&mut self, index: usize) { + self.cached_blocks.init_block(index); + } + + pub(crate) fn get_block(&mut self, index: usize) -> Option<&CachedBlock> { + if self.data_bitmap.query(index) { + Some(self.cached_blocks.get_block::(index).unwrap()) + } else { + self.cached_blocks.pop(&index); + None + } + // self.data_bitmap + // .query(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> { + if self.data_bitmap.query(index) { + Some(self.cached_blocks.get_block_mut::(index).unwrap()) + } else { + self.cached_blocks.pop(&index); + None + } + // self.data_bitmap + // .query(index) + // .then(|| self.cached_blocks.get_block_mut::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid + } + + #[allow(unused)] + pub(crate) fn peek_block(&self, index: usize) -> Option<&CachedBlock> { + self.data_bitmap + .query(index) + .then(|| self.cached_blocks.peek_block::(index).unwrap()) + // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid + } + + #[allow(unused)] + pub(crate) fn peek_block_mut(&mut self, index: usize) -> Option<&mut CachedBlock> { + self.data_bitmap + .query(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 { + self.cached_blocks.update_block(block) + } +} diff --git a/ayafs/src/memory/cached_inode.rs b/ayafs/src/memory/cached_inode.rs new file mode 100644 index 0000000..2f26dde --- /dev/null +++ b/ayafs/src/memory/cached_inode.rs @@ -0,0 +1,178 @@ +use crate::disk::block::InodeBlock; +use crate::disk::inode::{Inode, INODE_SIZE}; +use crate::{utils, AyaFS}; +use and_then_some::BoolExt; +use fuser::FileType; +use libc::{c_int, EIO, EISDIR, ENOENT, ENOTDIR, ENOTEMPTY}; + +impl AyaFS { + pub(crate) fn create_file( + &mut self, + permissions: u16, + uid: u32, + gid: u32, + flags: u32, + ) -> Option<(usize, &Inode)> { + self.inode_bitmap.allocate().map(|inode_index| { + self.get_inode_mut(inode_index).map(|inode| { + *inode = Inode::file(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0); + }); + (inode_index, self.get_inode(inode_index).unwrap()) + }) + } + + pub(crate) fn create_symlink( + &mut self, + permissions: u16, + uid: u32, + gid: u32, + flags: u32, + ) -> Option<(usize, &Inode)> { + self.inode_bitmap.allocate().map(|inode_index| { + self.get_inode_mut(inode_index).map(|inode| { + *inode = Inode::symlink(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0); + }); + (inode_index, self.get_inode(inode_index).unwrap()) + }) + } + + /// 根目录的 parent_inode_number 传入 None, 会直接以自己作为 .. 的 inode number + pub(crate) fn create_directory( + &mut self, + permissions: u16, + uid: u32, + gid: u32, + flags: u32, + parent_inode_number: Option, + ) -> Option<(usize, &Inode)> { + self.inode_bitmap.allocate().map(|inode_index| { + // 创建 Inode + let mut new_inode = + Inode::directory(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0); + self.init_direntry_map(inode_index); + self.add_direntry(inode_index, &mut new_inode, inode_index, ".", 0x2) + .unwrap(); + self.add_direntry( + inode_index, + &mut new_inode, + parent_inode_number.unwrap_or(inode_index), + "..", + 0x2, + ) + .unwrap(); + // 把 inode 放到指定位置 + self.get_inode_mut(inode_index).map(|inode| { + *inode = new_inode; + }); + + (inode_index, self.get_inode(inode_index).unwrap()) + }) + } + + pub(crate) fn remove_file(&mut self, inode_index: usize) -> Result { + if self.inode_bitmap.query(inode_index) { + let (block_index, offset) = self.locate_inode(inode_index); + if let Some(cached_block) = self.cached_inodes.get_block::(block_index) { + let inode = cached_block.block.inodes[offset / INODE_SIZE].clone(); + match inode.file_type() { + FileType::RegularFile => self.deallocate_all_blocks_for(&inode).unwrap(), + FileType::Symlink => { + if inode.size >= 60 { + self.deallocate_all_blocks_for(&inode).unwrap(); + } + } + FileType::Directory => return Err(EISDIR), + _ => return Err(EIO), + } + } + self.inode_bitmap.deallocate(inode_index); + Ok(true) + } else { + Err(ENOENT) + } + } + + // 要删除的 inode 一定得是空的 + pub(crate) fn remove_dir(&mut self, inode_index: usize) -> Result { + if self.inode_bitmap.query(inode_index) { + let (block_index, offset) = self.locate_inode(inode_index); + if let Some(cached_block) = self.cached_inodes.get_block::(block_index) { + let inode = &cached_block.block.inodes[offset / INODE_SIZE].clone(); + if !inode.is_dir() { + // 不是 dir -> ENOTDIR + return Err(ENOTDIR); + } + if inode.size > 2 { + // 有 . 和 .. 以外的 entry -> ENOTEMPTY + return Err(ENOTEMPTY); + } + // 销毁 inode 里的所有 block + self.deallocate_all_blocks_for(inode).unwrap(); + } + // 销毁 inode + self.inode_bitmap.deallocate(inode_index); + Ok(true) + } else { + Err(ENOENT) + } + } + + pub(crate) fn update_inode(&mut self, inode_index: usize, inode: Inode) -> bool { + if self.inode_bitmap.query(inode_index) { + let (block_index, offset) = self.locate_inode(inode_index); + if let Some(cached_block) = self.cached_inodes.get_block_mut::(block_index) + { + cached_block.block.inodes[offset / INODE_SIZE] = inode; + } + true + } else { + false + } + } + + pub(crate) fn get_inode(&mut self, inode_index: usize) -> Option<&Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + // debug!("get_inode(inode_index: {}) -> block_index: {}, offset: {}", inode_index, block_index, offset); + self.cached_inodes + .get_block::(block_index) + .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE]) + }) + } + + pub(crate) fn get_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + // debug!("get_inode_mut(inode_index: {}) -> block_index: {}, offset: {}", inode_index, block_index, offset); + self.cached_inodes + .get_block_mut::(block_index) + .map(|cached_block| { + cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏 + &mut cached_block.block.inodes[offset / INODE_SIZE] + }) + }) + } + + #[allow(unused)] + pub(crate) fn peek_inode(&self, inode_index: usize) -> Option<&Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + self.cached_inodes + .peek_block::(block_index) + .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE]) + }) + } + + #[allow(unused)] + pub(crate) fn peek_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> { + self.inode_bitmap.query(inode_index).and_then(|| { + let (block_index, offset) = self.locate_inode(inode_index); + self.cached_inodes + .peek_block_mut::(block_index) + .map(|cached_block| { + cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏 + &mut cached_block.block.inodes[offset / INODE_SIZE] + }) + }) + } +} diff --git a/ayafs/src/memory/dir_entry.rs b/ayafs/src/memory/dir_entry.rs new file mode 100644 index 0000000..c013e1e --- /dev/null +++ b/ayafs/src/memory/dir_entry.rs @@ -0,0 +1,305 @@ +use crate::disk::block::{DirectoryBlock, DirectoryEntry}; +use crate::disk::inode::Inode; +use crate::AyaFS; +use indexmap::IndexMap; +use libc::{c_int, ENOENT, ENOSPC}; +use log::debug; +use std::ffi::{OsStr, OsString}; +use std::os::unix::ffi::OsStrExt; +use indexmap::map::Entry::Occupied; + +impl AyaFS { + pub(crate) fn init_direntry_map(&mut self, index: usize) { + let direntry_map: IndexMap = IndexMap::new(); + if let Some((old_inode_index, old_dir_entry_map)) = + self.dir_entry_map.push(index, direntry_map) + { + if let Some(old_inode) = self.get_inode(old_inode_index) { + let mut old_inode = old_inode.clone(); + self.write_back_direntry(old_inode_index, &mut old_inode, old_dir_entry_map) + .unwrap(); + self.update_inode(old_inode_index, old_inode); + } + } + } + + pub(crate) fn load_direntry_map(&mut self, index: usize, inode: &Inode) -> Result<(), c_int> { + if self.dir_entry_map.contains(&index) { + debug!("load_direntry_map(ino: {}) already in cache", index); + return Ok(()); + } + + debug!("load_direntry_map(ino: {}) loading", index); + let mut dir_entry_map: IndexMap = IndexMap::new(); + let mut entry_index: usize = 0; + loop { + let block_index_within_inode = entry_index / 15; + let entry_index_within_block = entry_index % 15; + + match self.access_block::(inode, block_index_within_inode) { + Some(directory_block) => { + if directory_block.block.query(entry_index_within_block) { + let dir_entry = &directory_block.block.entries[entry_index_within_block]; + let name = dir_entry.name(); + dir_entry_map.insert(name, dir_entry.clone()); + } else { + break; + } + } + None => break, + } + entry_index += 1; + } + + if let Some((old_inode_index, old_dir_entry_map)) = + self.dir_entry_map.push(index, dir_entry_map) + { + if let Some(old_inode) = self.get_inode(old_inode_index) { + let mut old_inode = old_inode.clone(); + self.write_back_direntry(old_inode_index, &mut old_inode, old_dir_entry_map)?; + self.update_inode(old_inode_index, old_inode); + } + } + + Ok(()) + } + + pub(crate) fn write_back_direntry( + &mut self, + _parent_index: usize, + parent_inode: &mut Inode, + dir_entry_map: IndexMap, + ) -> Result<(), c_int> { + for (entry_index, (_, dir_entry)) in dir_entry_map.into_iter().enumerate() { + let block_index_within_inode = entry_index / 15; + let entry_index_within_block = entry_index % 15; + // 不够就新分配 + if self + .get_block_index(parent_inode, block_index_within_inode) + .is_none() + { + match self.allocate_block_for(parent_inode) { + Some((_, block_index_within)) => { + assert_eq!(block_index_within, block_index_within_inode); + } + None => { + return Err(ENOSPC); + } + } + } + match self.access_block_mut::(parent_inode, block_index_within_inode) { + Some(directory_block) => { + directory_block.block.allocate(entry_index_within_block); + directory_block.block.entries[entry_index_within_block] = dir_entry; + } + None => { + return Err(ENOENT); + } + } + } + Ok(()) + } + + pub(crate) fn exchange_direntry>( + &mut self, + parent_index: usize, + parent_inode: &mut Inode, + name: T, + new_parent_index: usize, + new_parent_inode: &mut Inode, + new_name: T, + ) -> Result<(), c_int> { + self.load_direntry_map(parent_index, parent_inode)?; + self.load_direntry_map(new_parent_index, new_parent_inode)?; + + let dir_entry = self.dir_entry_map + .get(&parent_index) + .ok_or(ENOENT)? + .get(name.as_ref()) + .cloned() + .ok_or(ENOENT)?; + let new_dir_entry = self.dir_entry_map + .get(&new_parent_index) + .ok_or(ENOENT)? + .get(new_name.as_ref()) + .cloned() + .ok_or(ENOENT)?; + + let name: &OsStr = name.as_ref(); + let new_name: &OsStr = new_name.as_ref(); + + self.dir_entry_map + .get_mut(&parent_index) + .map(|dir_entry_map| { + if let Occupied(mut entry) = dir_entry_map.entry(name.to_os_string()) { + *entry.get_mut() = new_dir_entry.clone(); + } + }) + .ok_or(ENOENT)?; + self.dir_entry_map + .get_mut(&new_parent_index) + .map(|new_dir_entry_map| { + if let Occupied(mut entry) = new_dir_entry_map.entry(new_name.to_os_string()) { + *entry.get_mut() = dir_entry.clone(); + } + }) + .ok_or(ENOENT)?; + + Ok(()) + } + + /// 删除第 entry_index 个 dir entry + pub(crate) fn remove_direntry>( + &mut self, + parent_index: usize, + parent_inode: &mut Inode, + name: T, + _entry_index: u32, + ) -> Result<(), c_int> { + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get_mut(&parent_index) { + debug!(" remove_direntry(ino: {}) using hashmap", parent_index); + if dir_entry_map.shift_remove(name.as_ref()).is_some() { + Ok(()) + } else { + Err(ENOENT) + } + } else { + Err(ENOENT) + } + } + + pub(crate) fn add_direntry_2>( + &mut self, + parent_index: usize, + parent_inode: &mut Inode, + child_inode_name: T, + dir_entry: DirectoryEntry, + ) -> Result { + let child_inode_name = child_inode_name.as_ref(); + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get_mut(&parent_index) { + let (entry_index, _) = + dir_entry_map.insert_full(child_inode_name.to_os_string(), dir_entry); + debug!( + " add_direntry(ino: {}) using hashmap, entry {}", + parent_index, entry_index + ); + parent_inode.size += 1; + Ok(entry_index as u32) + } else { + Err(ENOENT) + } + } + + pub(crate) fn add_direntry>( + &mut self, + parent_index: usize, + parent_inode: &mut Inode, + child_inode_index: usize, + child_inode_name: T, + file_type: u8, + ) -> Result { + let child_inode_name = child_inode_name.as_ref(); + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get_mut(&parent_index) { + let name_len = child_inode_name.len() as u8; + let mut name = [0u8; 256]; + (&mut name[0..child_inode_name.len()]).copy_from_slice(child_inode_name.as_bytes()); + + let dir_entry = DirectoryEntry { + inode: child_inode_index as u32, + record_len: 264, + name_len, + file_type, + name, + }; + + let (entry_index, _) = + dir_entry_map.insert_full(child_inode_name.to_os_string(), dir_entry); + debug!( + " add_direntry(ino: {}) using hashmap, entry {}", + parent_index, entry_index + ); + parent_inode.size += 1; + Ok(entry_index as u32) + } else { + Err(ENOENT) + } + } + + pub(crate) fn get_direntry_by_name>( + &mut self, + parent_index: usize, + parent_inode: &Inode, + name: T, + ) -> Result { + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get(&parent_index) { + debug!( + " get_direntry(ino: {}, name: {:?}) using hashmap", + parent_index, name.as_ref() + ); + dir_entry_map + .get(name.as_ref()) + .cloned() + .ok_or(ENOENT) + } else { + Err(ENOENT) + } + } + + pub(crate) fn get_direntry( + &mut self, + parent_index: usize, + parent_inode: &Inode, + entry_index: u32, + ) -> Result { + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get(&parent_index) { + debug!( + " get_direntry(ino: {}, entry_index: {}) using hashmap", + parent_index, entry_index + ); + dir_entry_map + .iter() + .skip(entry_index as usize) + .next() + .map(|entry| entry.1.clone()) + .ok_or(ENOENT) + } else { + Err(ENOENT) + } + } + + /// 返回 inode_index, inode 在 parent 里的 index, inode 本身 + pub fn lookup_name( + &mut self, + parent_index: usize, + parent_inode: &Inode, + name: &OsStr, + ) -> Result<(u32, u32, Inode), c_int> { + self.load_direntry_map(parent_index, parent_inode)?; + if let Some(dir_entry_map) = self.dir_entry_map.get(&parent_index) { + if let Some((entry_index, _, dir_entry)) = dir_entry_map.get_full(name) { + let inode_index = dir_entry.inode; + let inode = self.get_inode(inode_index as usize).unwrap().clone(); + Ok((inode_index, entry_index as u32, inode)) + } else { + Err(ENOENT) + } + } else { + let mut entry_index = 0; + while entry_index < parent_inode.size { + if let Ok(entry) = self.get_direntry(parent_index, 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/ayafs/src/memory/file_handle.rs b/ayafs/src/memory/file_handle.rs new file mode 100644 index 0000000..c821619 --- /dev/null +++ b/ayafs/src/memory/file_handle.rs @@ -0,0 +1,15 @@ +use crate::AyaFS; +use std::sync::atomic::Ordering; + +impl AyaFS { + pub(crate) fn allocate_file_descriptor( + &mut self, + inode_index: usize, + read: bool, + write: bool, + ) -> u64 { + let fd = self.next_file_handle.fetch_add(1, Ordering::SeqCst); + self.file_handle_map.insert(fd, (inode_index, read, write)); + fd + } +} diff --git a/ayafs/src/memory/mod.rs b/ayafs/src/memory/mod.rs new file mode 100644 index 0000000..d1f1ab8 --- /dev/null +++ b/ayafs/src/memory/mod.rs @@ -0,0 +1,6 @@ +/// In-memory data structures and logic. +/// This is where the crucial block and inode methods presented to upper calls implemented. +pub mod cached_block; +pub mod cached_inode; +mod dir_entry; +mod file_handle; -- cgit v1.2.3-70-g09d2