From ec2f349a648e4d87fba12d20e338b1cd6d8ef29a Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Mon, 27 Nov 2023 00:11:55 -0800 Subject: Fix directory stuff --- src/disk/allocation.rs | 26 +++- src/filesystem/trait_impl.rs | 207 ++++++++++++++++++++++------- src/main.rs | 22 +++- src/memory/cached_inode.rs | 92 ++++++++----- src/memory/dir_entry.rs | 304 ++++++++++++++++++++++++++++++++----------- src/memory/file_handle.rs | 19 +++ src/memory/mod.rs | 1 + src/tests/bitmap.rs | 15 +++ src/tests/block_cache.rs | 33 ++--- 9 files changed, 543 insertions(+), 176 deletions(-) create mode 100644 src/memory/file_handle.rs (limited to 'src') diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs index b88e7d5..a4bb3f7 100644 --- a/src/disk/allocation.rs +++ b/src/disk/allocation.rs @@ -398,7 +398,7 @@ impl AyaFS { } impl AyaFS { - fn get_block_index( + pub(crate) fn get_block_index( &mut self, inode: &Inode, mut block_index_within_inode: usize, @@ -406,7 +406,11 @@ impl AyaFS { // direct block if block_index_within_inode < DIRECT_NUMBER { let block_index = inode.direct[block_index_within_inode] as usize; - return Some(block_index); + return if self.data_bitmap.query(block_index) { + Some(block_index) + } else { + None + }; } else { block_index_within_inode -= DIRECT_NUMBER; } @@ -418,7 +422,11 @@ impl AyaFS { self.get_block::(inode.single_indirect as usize) { let block_index = indirect_block.block.entries[block_index_within_inode] as usize; - Some(block_index) + if self.data_bitmap.query(block_index) { + Some(block_index) + } else { + None + } } else { None }; @@ -443,7 +451,11 @@ impl AyaFS { [block_index_within_inode % INODE_PER_BLOCK] as usize; // 拿到 DirectoryBlock 的 index - return Some(block_index); + return if self.data_bitmap.query(block_index) { + Some(block_index) + } else { + None + }; } } return None; @@ -474,7 +486,11 @@ impl AyaFS { [block_index_within_inode % INODE_PER_BLOCK] as usize; // DirectoryBlock 的 index - return Some(block_index); + return if self.data_bitmap.query(block_index) { + Some(block_index) + } else { + None + }; } } } diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs index 636bae7..5353f6e 100644 --- a/src/filesystem/trait_impl.rs +++ b/src/filesystem/trait_impl.rs @@ -6,11 +6,12 @@ use crate::{AyaFS, TTL}; use fuser::TimeOrNow::{Now, SpecificTime}; use fuser::{ Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry, - ReplyLseek, ReplyOpen, Request, TimeOrNow, + ReplyLseek, ReplyOpen, ReplyWrite, Request, TimeOrNow, }; use libc::{ - c_int, EACCES, EEXIST, EISDIR, ENAMETOOLONG, ENOENT, ENOSPC, ENOSYS, ENOTDIR, EPERM, R_OK, - S_ISGID, S_ISUID, S_IXGRP, S_IXOTH, S_IXUSR, W_OK, + c_int, EACCES, EBADF, EEXIST, EINVAL, EISDIR, ENAMETOOLONG, ENOENT, ENOSPC, ENOSYS, ENOTDIR, + ENOTEMPTY, EPERM, O_ACCMODE, O_RDONLY, O_RDWR, O_WRONLY, R_OK, S_ISGID, S_ISUID, S_IXGRP, + S_IXOTH, S_IXUSR, W_OK, }; use log::debug; use std::ffi::OsStr; @@ -46,7 +47,7 @@ impl Filesystem for AyaFS { R_OK, ) { let parent_inode = parent_inode.clone(); - match self.lookup_name(&parent_inode, name) { + match self.lookup_name(parent, &parent_inode, name) { Ok((inode_index, _, inode)) => { let attr = to_fileattr(inode_index as usize, &inode); reply.entry(&TTL, &attr, 0); @@ -62,7 +63,6 @@ impl Filesystem for AyaFS { } fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) { - debug!("Filesystem::getattr(ino: {})", ino); if let Some(inode) = self.get_inode(ino as usize) { reply.attr(&TTL, &to_fileattr(ino as usize, inode)); } else { @@ -284,7 +284,10 @@ impl Filesystem for AyaFS { let mut parent_inode = parent_inode.clone(); // 如果已经存在, 返回 already exists - if self.lookup_name(&parent_inode, name).is_ok() { + if self + .lookup_name(parent as usize, &parent_inode, name) + .is_ok() + { reply.error(EEXIST); return; } @@ -295,9 +298,13 @@ impl Filesystem for AyaFS { { let child_inode = child_inode.clone(); let file_attr = to_fileattr(child_inode_index, &child_inode); - if let Err(err_code) = - self.add_direntry(&mut parent_inode, child_inode_index, name, &child_inode) - { + if let Err(err_code) = self.add_direntry( + parent as usize, + &mut parent_inode, + child_inode_index, + name, + child_inode.mode.into(), + ) { reply.error(err_code); return; } @@ -350,20 +357,27 @@ impl Filesystem for AyaFS { let mut parent_inode = parent_inode.clone(); // 已经存在 -> File exists - if self.lookup_name(&parent_inode, name).is_ok() { + if self + .lookup_name(parent as usize, &parent_inode, name) + .is_ok() + { reply.error(EEXIST); return; } let mode = mode as u16; if let Some((child_inode_index, child_inode)) = - self.create_directory(mode, req.uid(), req.gid(), 0, Some(parent as u32)) + self.create_directory(mode, req.uid(), req.gid(), 0, Some(parent as usize)) { let child_inode = child_inode.clone(); let file_attr = to_fileattr(child_inode_index, &child_inode); - if let Err(err_code) = - self.add_direntry(&mut parent_inode, child_inode_index, name, &child_inode) - { + if let Err(err_code) = self.add_direntry( + parent as usize, + &mut parent_inode, + child_inode_index, + name, + child_inode.mode.into(), + ) { reply.error(err_code); return; } @@ -409,7 +423,8 @@ impl Filesystem for AyaFS { let mut parent_inode = parent_inode.clone(); // 不存在 -> No such file or directory - if let Ok((inode_index, entry_index, mut inode)) = self.lookup_name(&parent_inode, name) + if let Ok((inode_index, entry_index, mut inode)) = + self.lookup_name(parent as usize, &parent_inode, name) { let inode_index = inode_index as usize; // 要删除的 entry 是目录, 不能用 unlink @@ -417,15 +432,10 @@ impl Filesystem for AyaFS { reply.error(EISDIR); return; } - // 删除 dir entry - if let Err(err_code) = self.remove_direntry(&mut parent_inode, entry_index) { - reply.error(err_code); - return; - } - // inode 的 n_links 减 1 + inode.n_links -= 1; if inode.n_links == 0 { - // 释放块的操作在 remove file 里实现了 + // n_links == 0 -> 整个 inode 都要删除掉 match self.remove_file(inode_index) { Ok(flag) => debug!(" unlink {}", flag), Err(err_code) => { @@ -434,8 +444,17 @@ impl Filesystem for AyaFS { } } } else { + // n_links > 0 -> 只是移除了一个 hard link, 将改动写回 self.update_inode(inode_index, inode); } + + // 删除 dir entry + if let Err(err_code) = + self.remove_direntry(parent as usize, &mut parent_inode, name, entry_index) + { + reply.error(err_code); + return; + } reply.ok(); } else { reply.error(ENOENT); @@ -475,7 +494,8 @@ impl Filesystem for AyaFS { let mut parent_inode = parent_inode.clone(); // 不存在 -> No such file or directory - if let Ok((inode_index, entry_index, mut inode)) = self.lookup_name(&parent_inode, name) + if let Ok((inode_index, entry_index, inode)) = + self.lookup_name(parent as usize, &parent_inode, name) { let inode_index = inode_index as usize; // 要删除的 entry 是一般文件, 不用 rmdir @@ -484,11 +504,10 @@ impl Filesystem for AyaFS { return; } - // TODO 检查待删除的 dir 是 empty 的 - - // 删除 dir entry - if let Err(err_code) = self.remove_direntry(&mut parent_inode, entry_index) { - reply.error(err_code); + // 一定有 . 和 .. 所以 size == 2 就是空目录 + // 目录非空 -> ENOTEMPTY + if inode.size > 2 { + reply.error(ENOTEMPTY); return; } @@ -501,6 +520,14 @@ impl Filesystem for AyaFS { } } + // 删除 dir entry + if let Err(err_code) = + self.remove_direntry(parent as usize, &mut parent_inode, name, entry_index) + { + reply.error(err_code); + return; + } + reply.ok(); } else { reply.error(ENOENT); @@ -510,6 +537,10 @@ impl Filesystem for AyaFS { } } + fn open(&mut self, _req: &Request<'_>, _ino: u64, _flags: i32, reply: ReplyOpen) { + todo!() + } + fn read( &mut self, _req: &Request<'_>, @@ -524,42 +555,111 @@ impl Filesystem for AyaFS { todo!() } - fn opendir(&mut self, _req: &Request<'_>, ino: u64, flags: i32, reply: ReplyOpen) { - debug!("OPENDIR ino {:#x} flags {}", ino, flags); - reply.opened(1, 0); + fn write( + &mut self, + _req: &Request<'_>, + ino: u64, + fh: u64, + offset: i64, + data: &[u8], + write_flags: u32, + flags: i32, + lock_owner: Option, + reply: ReplyWrite, + ) { + todo!() + } + + fn release( + &mut self, + _req: &Request<'_>, + _ino: u64, + _fh: u64, + _flags: i32, + _lock_owner: Option, + _flush: bool, + reply: ReplyEmpty, + ) { + todo!() + } + + fn opendir(&mut self, req: &Request<'_>, ino: u64, flags: i32, reply: ReplyOpen) { + debug!("opendir(ino: {:#x?}, flags: {:#x?})", ino, flags); + let (access_mask, read, write) = match flags & O_ACCMODE { + O_RDONLY => { + // Behavior is undefined, but most filesystems return EACCES + if flags & libc::O_TRUNC != 0 { + reply.error(libc::EACCES); + return; + } + (R_OK, true, false) + } + O_WRONLY => (W_OK, false, true), + O_RDWR => (R_OK | W_OK, true, true), + _ => { + // flag 非法 + reply.error(EINVAL); + return; + } + }; + + match self.get_inode(ino as usize) { + Some(inode) => { + if !check_access( + req.uid(), + req.gid(), + inode.uid, + inode.gid, + inode.mode, + access_mask, + ) { + reply.error(EACCES); + return; + } + let fd = self.allocate_file_descriptor(ino as usize, read, write); + reply.opened(fd, 0); + } + None => { + reply.error(ENOENT); + } + } } fn readdir( &mut self, req: &Request<'_>, ino: u64, - _fh: u64, // 如果 invoke 它的 opendir 里有指定 fh, 那么这里会收到 fh 参数 + fh: u64, // 如果 invoke 它的 opendir 里有指定 fh, 那么这里会收到 fh 参数 offset: i64, mut reply: ReplyDirectory, ) { + assert_eq!(self.file_handle_map.get(&fh).unwrap().0, ino as usize); if let Some(inode) = self.get_inode(ino as usize) { if inode.is_dir() { if check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, R_OK) { + debug!("reading dir entries from inode {:#x} with offset {}", ino, offset); let inode = inode.clone(); - let mut entry_index = offset as u32; - while let Some(dir_entry) = self.get_direntry(&inode, entry_index) { - debug!("reading inode {:#x} index {}", ino, entry_index); - if entry_index >= inode.size { - break; - } - // 最开头应该添加 `.` 和 `..`, 但这件事应该在 mkdir 的时候就在 inode 里加好 - // reply.add 返回 true 说明 buffer 已满, 停止累加 + self.load_direntry_map(ino as usize, &inode).unwrap(); + for (entry_index, (name, dir_entry)) in self + .dir_entry_map + .get(&(ino as usize)) + .unwrap() + .iter() + .enumerate() + .skip(offset as usize) + { + debug!(" entry {} from inode {:#x} with name {:?}", entry_index, dir_entry.inode, name); if reply.add( dir_entry.inode as u64, - entry_index as i64, - to_filetype(dir_entry.file_type).expect("file type should not be 0x0!"), - dir_entry.name(), + entry_index as i64 + 1, + to_filetype(dir_entry.file_type).expect("not 0x0!"), + name ) { break; } - entry_index += 1; } + reply.ok(); } else { reply.error(EACCES); @@ -572,11 +672,28 @@ impl Filesystem for AyaFS { } } + fn releasedir( + &mut self, + _req: &Request<'_>, + ino: u64, + fh: u64, + _flags: i32, + reply: ReplyEmpty, + ) { + debug!("releasedir(ino: {:#x?}, fh: {}", ino, fh); + if self.file_handle_map.contains_key(&fh) { + self.file_handle_map.remove(&fh); + reply.ok(); + } else { + reply.error(EBADF); + } + } + fn access(&mut self, req: &Request<'_>, ino: u64, mask: i32, reply: ReplyEmpty) { // mask: // - 要么是 libc::F_OK (aka 0), 检查文件是否存在 // - 要么是 libc::R_OK,libc::W_OK,libc::X_OK (aka 4/2/1) 构成的 bitmask, 检查是否有对应权限 - debug!("Filesystem::getattr(ino: {}, mask: {})", ino, mask); + debug!("Filesystem::access(ino: {}, mask: {})", ino, mask); if let Some(inode) = self.get_inode(ino as usize) { if mask == libc::F_OK // 只要检查是否存在 diff --git a/src/main.rs b/src/main.rs index 5d460fc..78f338a 100644 --- a/src/main.rs +++ b/src/main.rs @@ -7,12 +7,17 @@ mod utils; use clap::Parser; use fuser::MountOption; +use indexmap::IndexMap; use log::debug; +use lru::LruCache; +use std::collections::HashMap; +use std::ffi::OsString; +use std::num::NonZeroUsize; +use std::sync::atomic::AtomicU64; use std::sync::Arc; use std::time::Duration; -use crate::disk::block::InodeBlock; -use crate::disk::inode::InodeMode; +use crate::disk::block::{DirectoryEntry, InodeBlock}; use crate::memory::cached_block::BlockCache; use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE}; use disk::bitmap::Bitmap; @@ -61,6 +66,13 @@ struct AyaFS { inode_start_block: usize, data_start_block: usize, + next_file_handle: AtomicU64, + // file descriptor -> (inode index, read, write) + file_handle_map: HashMap, + + // inode index -> (index aware) hashmap that maps dir entry name to inode index + dir_entry_map: LruCache>, + cached_inodes: BlockCache, cached_blocks: BlockCache, } @@ -111,6 +123,12 @@ impl AyaFS { + inode_bitmap_block_number + inode_block_number + 1, + + next_file_handle: AtomicU64::new(3), // 0,1,2 are stdin, stdout and stderr + file_handle_map: HashMap::new(), + + dir_entry_map: LruCache::new(NonZeroUsize::new(1024).unwrap()), + cached_inodes: BlockCache::new(device.clone(), 1024), cached_blocks: BlockCache::new(device.clone(), 8192), }; diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs index aa4f5e3..a9c92f5 100644 --- a/src/memory/cached_inode.rs +++ b/src/memory/cached_inode.rs @@ -2,7 +2,7 @@ use crate::disk::block::{DirectoryBlock, DirectoryEntry, InodeBlock}; use crate::disk::inode::{Inode, INODE_SIZE}; use crate::{utils, AyaFS}; use and_then_some::BoolExt; -use libc::{c_int, EISDIR, ENOENT, ENOTDIR}; +use libc::{c_int, EISDIR, ENOENT, ENOTDIR, ENOTEMPTY}; impl AyaFS { pub(crate) fn create_file( @@ -27,41 +27,53 @@ impl AyaFS { uid: u32, gid: u32, flags: u32, - parent_inode_number: Option, + 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); - // 分配第一个 direct block - (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap(); - new_inode.size = 2; - // 在 direct block 里分配 . 和 .. - if let Some(directory_block) = - self.get_block_mut::(new_inode.direct[0] as usize) - { - let dot = '.'.to_ascii_lowercase() as u8; - // add dot entry - directory_block.block.entries[0] = DirectoryEntry { - inode: inode_index as u32, - record_len: 264, - name_len: 1, - file_type: 0x2, - name: [0; 256], - }; - directory_block.block.entries[0].name[0] = dot; + 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(); - // add dot dot entry - directory_block.block.entries[1] = DirectoryEntry { - inode: parent_inode_number.unwrap_or(inode_index as u32), - record_len: 264, - name_len: 2, - file_type: 0x2, - name: [0; 256], - }; - directory_block.block.entries[1].name[0] = dot; - directory_block.block.entries[1].name[1] = dot; - } + // // 分配第一个 direct block + // (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap(); + // new_inode.size = 2; + // // 在 direct block 里分配 . 和 .. + // if let Some(directory_block) = + // self.get_block_mut::(new_inode.direct[0] as usize) + // { + // let dot = '.'.to_ascii_lowercase() as u8; + // // add dot entry + // directory_block.block.entries[0] = DirectoryEntry { + // inode: inode_index as u32, + // record_len: 264, + // name_len: 1, + // file_type: 0x2, + // name: [0; 256], + // }; + // directory_block.block.entries[0].name[0] = dot; + // + // // add dot dot entry + // directory_block.block.entries[1] = DirectoryEntry { + // inode: parent_inode_number.unwrap_or(inode_index as u32), + // record_len: 264, + // name_len: 2, + // file_type: 0x2, + // name: [0; 256], + // }; + // directory_block.block.entries[1].name[0] = dot; + // directory_block.block.entries[1].name[1] = dot; + // } // 把 inode 放到指定位置 self.get_inode_mut(inode_index).map(|inode| { *inode = new_inode; @@ -70,10 +82,9 @@ impl AyaFS { (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) { - self.inode_bitmap.deallocate(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(); @@ -82,23 +93,32 @@ impl AyaFS { } self.deallocate_all_blocks_for(&inode).unwrap(); } + 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) { - self.inode_bitmap.deallocate(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(); + let inode = &cached_block.block.inodes[offset / INODE_SIZE].clone(); if !inode.is_dir() { + // 不是 dir -> ENOTDIR return Err(ENOTDIR); } - // TODO 递归删除所有下面的 direntry 里的 inode, 注意排除 . 和 .. + 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) diff --git a/src/memory/dir_entry.rs b/src/memory/dir_entry.rs index 2d961db..08a82c5 100644 --- a/src/memory/dir_entry.rs +++ b/src/memory/dir_entry.rs @@ -1,117 +1,275 @@ use crate::disk::block::{DirectoryBlock, DirectoryEntry}; use crate::disk::inode::Inode; use crate::AyaFS; +use indexmap::IndexMap; use libc::{c_int, ENOENT, ENOSPC}; -use std::ffi::OsStr; +use log::debug; +use std::ffi::{OsStr, OsString}; use std::os::unix::ffi::OsStrExt; impl AyaFS { - /// 删除所有的 dir entry, 递归 - pub(crate) fn clear_direntry(&mut self, parent_inode: &mut Inode) -> Result<(), c_int> { - todo!() + 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.entries[entry_index_within_block] = dir_entry; + } + None => { + return Err(ENOENT); + } + } + } + Ok(()) } /// 删除第 entry_index 个 dir entry pub(crate) fn remove_direntry( &mut self, + parent_index: usize, parent_inode: &mut Inode, + name: &OsStr, 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) - } + 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).is_some() { + Ok(()) + } else { + Err(ENOENT) } - None => Err(ENOENT), + } else { + Err(ENOENT) + // 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( + pub(crate) fn add_direntry>( &mut self, + parent_index: usize, parent_inode: &mut Inode, child_inode_index: usize, - child_inode_name: &OsStr, - child_inode: &Inode, + child_inode_name: T, + file_type: u8, ) -> 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 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, - }; - 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; + 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) } + // // 找到第一个有空闲 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 mut name = [0u8; 256]; + // (&mut name[0..name_len as usize]) + // .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, + // }; + // directory_block.block.entries[entry_index_within_block] = dir_entry; + // let entry_index = block_index_within_inode * 15 + entry_index_within_block; + // parent_inode.size += 1; + // return Ok(entry_index as u32); + // } + // } + // block_index_within_inode += 1; + // } } pub(crate) fn get_direntry( &mut self, + parent_index: usize, 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 - } - }) + ) -> 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) + // let block_index_within_inode = (entry_index / 15) as usize; + // let entry_index_within_block = (entry_index % 15) as usize; + // + // match self.access_block::(parent_inode, block_index_within_inode) { + // Some(directory_block) => { + // if directory_block.block.query(entry_index_within_block) { + // Ok(directory_block.block.entries[entry_index_within_block].clone()) + // } else { + // Err(ENOENT) + // } + // } + // None => Err(ENOENT), + // } + } } // TODO 实现一个带 cache 的版本 /// 返回 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> { - 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)); + 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; } - entry_index += 1; + Err(ENOENT) } - Err(ENOENT) } } diff --git a/src/memory/file_handle.rs b/src/memory/file_handle.rs new file mode 100644 index 0000000..0da2ed2 --- /dev/null +++ b/src/memory/file_handle.rs @@ -0,0 +1,19 @@ +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 + } + + pub(crate) fn get_inode_from_fd(&self, file_descriptor: u64) -> Option<(usize, bool, bool)> { + self.file_handle_map.get(&file_descriptor).copied() + } +} diff --git a/src/memory/mod.rs b/src/memory/mod.rs index 4080114..d1f1ab8 100644 --- a/src/memory/mod.rs +++ b/src/memory/mod.rs @@ -3,3 +3,4 @@ pub mod cached_block; pub mod cached_inode; mod dir_entry; +mod file_handle; diff --git a/src/tests/bitmap.rs b/src/tests/bitmap.rs index 9b21b6f..1a43f09 100644 --- a/src/tests/bitmap.rs +++ b/src/tests/bitmap.rs @@ -1,4 +1,5 @@ use crate::tests::common; +use indexmap::IndexMap; #[test] fn test_allocate() { @@ -21,3 +22,17 @@ fn test_query() { assert_eq!(fs.data_bitmap.query(5), true); assert_eq!(fs.data_bitmap.query(11), false); } + +#[test] +fn test_index_map() { + let mut map: IndexMap = IndexMap::new(); + map.insert(1, 2); + map.insert(2, 3); + map.insert(3, 4); + map.insert(4, 5); + map.remove(&3); + + for (entry_index, (key, value)) in map.iter().enumerate() { + println!("index {}, key {}, value {}", entry_index, key, value); + } +} diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs index 90875ae..52117b9 100644 --- a/src/tests/block_cache.rs +++ b/src/tests/block_cache.rs @@ -26,8 +26,8 @@ fn test_basic_lru() { fn test_inode_allocation() { 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(); + let (inode_index, inode) = fs.create_directory(0o755, 0, 0, 0, None).unwrap(); + let mut inode = inode.clone(); const DIRECT_NUMBER: u32 = 15; const INDIRECT_NUMBER: u32 = 1024; @@ -76,20 +76,20 @@ fn test_inode_allocation() { 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(); + let (inode_index, inode) = fs.create_directory(0o755, 0, 0, 0, None).unwrap(); + let mut inode = inode.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()); + 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!("Allocated {:?}", fs.allocate_block_for(&mut inode).unwrap()); } println!("single indirect is {}", inode.single_indirect); @@ -118,30 +118,33 @@ fn test_inode_deallocation() { 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 (inode_index_1, inode_1) = fs.create_directory(0o755, 0, 0, 0, None).unwrap(); + let mut inode_1 = inode_1.clone(); - let mut inode_1 = fs.get_inode(inode_index_1).unwrap().clone(); - let mut inode_2 = fs.get_inode(inode_index_2).unwrap().clone(); + let (inode_index_2, inode_2) = fs.create_file(0o755, 0, 0, 0).unwrap(); + let mut inode_2 = inode_2.clone(); + // 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!( - "Allocated {} in inode {}", + "Allocated {:?} in inode {}", fs.allocate_block_for(&mut inode_1).unwrap(), inode_index_1 ); println!( - "Allocated {} in inode {}", + "Allocated {:?} 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(); + let (inode_index_3, inode_3) = fs.create_directory(0o755, 0, 0, 0, None).unwrap(); + let mut inode_3 = inode_3.clone(); + // let mut inode_3 = fs.get_inode(inode_index_3).unwrap().clone(); for _i in 0..INDIRECT_NUMBER { println!( @@ -150,7 +153,7 @@ fn test_multiple_inode_allocation() { inode_index_1 ); println!( - "Allocated {} in inode {}", + "Allocated {:?} in inode {}", fs.allocate_block_for(&mut inode_3).unwrap(), inode_index_3 ); -- cgit v1.2.3-70-g09d2