From 95d8d84eef645b52d92fd3fb8fdea7aed1f6d474 Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Fri, 17 Nov 2023 11:40:33 -0800 Subject: Layer 1 incomplete --- src/main.rs | 451 +++++++++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 400 insertions(+), 51 deletions(-) (limited to 'src/main.rs') diff --git a/src/main.rs b/src/main.rs index 414baaf..0e799e4 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,17 +1,26 @@ mod block_device; +mod cached_inode; mod disk; +use std::collections::HashMap; use clap::Parser; -use fuser::{Filesystem, MountOption, ReplyAttr, ReplyData, ReplyDirectory, ReplyEntry, Request}; +use fuser::{ + Filesystem, KernelConfig, MountOption, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, + ReplyEntry, ReplyLseek, ReplyWrite, Request, TimeOrNow, +}; +use log::debug; use std::ffi::OsStr; use std::sync::Arc; -use std::time::Duration; -use log::debug; +use std::time::{Duration, SystemTime, UNIX_EPOCH}; +use crate::cached_inode::CachedInode; +use crate::disk::data_block::{Block, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock}; +use crate::disk::inode::InodeMode; use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE}; use disk::bitmap::Bitmap; use disk::inode::{Inode, INODE_SIZE}; -use libc::ENOENT; +use libc::{c_int, ENOENT, ENOSPC, ENOSYS}; +use users::{get_current_gid, get_current_uid}; #[derive(Parser, Debug)] #[command(author, version, about)] @@ -53,6 +62,9 @@ struct MyFS { inode_bitmap: Bitmap, inode_start_block: usize, data_start_block: usize, + + cached_inode: HashMap, + cache: [[u8; 4096]; 8192], } impl MyFS { @@ -71,14 +83,20 @@ impl MyFS { // Thus we have x = floor(BLK_SIZE * C / (BLK_SIZE + 1)) let data_block_number = BLOCK_SIZE * blocks_remaining / (BLOCK_SIZE + 1); let data_bitmap_block_number = blocks_remaining - data_block_number; - debug!("dbbn: {}", data_bitmap_block_number); - debug!("ibbn: {}", inode_bitmap_block_number); - debug!("ibn: {}", inode_block_number); - debug!("dbn: {}", data_block_number); - debug!("sum: {}", 1 + data_bitmap_block_number + inode_bitmap_block_number + inode_block_number + data_block_number); - - let mut data_bitmap = Bitmap::new(1, data_bitmap_block_number, device.clone()); - let mut inode_bitmap = Bitmap::new( + debug!("data_bitmap_block_number: {}", data_bitmap_block_number); + debug!("inode_bitmap_block_number: {}", inode_bitmap_block_number); + debug!("inode_block_number: {}", inode_block_number); + debug!("data_block_number: {}", data_block_number); + debug!( + "sum: {}", + 1 + data_bitmap_block_number + + inode_bitmap_block_number + + inode_block_number + + data_block_number + ); + + let data_bitmap = Bitmap::new(1, data_bitmap_block_number, device.clone()); + let inode_bitmap = Bitmap::new( data_bitmap_block_number + 1, inode_bitmap_block_number, device.clone(), @@ -92,51 +110,262 @@ impl MyFS { + inode_bitmap_block_number + inode_block_number + 1, + cached_inode: HashMap::new(), + cache: [[0; 4096]; 8192], }; - let _ = fs.inode_bitmap.allocate(); // Inode starts from 1 - let root_inode_index = fs.inode_bitmap.allocate(); + let _ = fs.data_bitmap.allocate().unwrap(); // data block 0 is not usable + let _ = fs.inode_bitmap.allocate().unwrap(); // inode block 0 is not usable + let root_inode_index = fs.inode_bitmap.allocate().unwrap(); // Inode starts from 1 assert_eq!(root_inode_index, 1); let (root_inode_block, root_inode_offset) = fs.locate_inode(root_inode_index); - fs.put_inode(root_inode_block, root_inode_offset, Inode::directory()); + fs.put_inode( + root_inode_block, + root_inode_offset, + &Inode::directory( + 0o755, + get_current_uid(), + get_current_gid(), + Self::time_now(), + 0, + 0, + 0, + 0, + ), + ); fs } - // pub fn allocate_inode(&mut self) -> usize { - // self.inode_bitmap.allocate() - // } + fn time_now() -> u32 { + SystemTime::now() + .duration_since(UNIX_EPOCH) + .expect("How can current time be earlier than UNIX_EPOCH?") + .as_secs() as u32 + } pub fn inode_active(&self, inode: usize) -> bool { self.inode_bitmap.query(inode) } /// 输入 inode 编号, 返回它对应的 block number 和 block 内 offset - pub fn locate_inode(&self, inode: usize) -> (usize, usize) { + pub fn locate_inode(&self, inode_index: usize) -> (usize, usize) { let block_number = - inode / INODE_PER_BLOCK + 1 + self.inode_bitmap.length + self.data_bitmap.length; - let block_offset = inode % INODE_PER_BLOCK * INODE_SIZE; + inode_index / INODE_PER_BLOCK + 1 + self.inode_bitmap.length + self.data_bitmap.length; + let block_offset = inode_index % INODE_PER_BLOCK * INODE_SIZE; (block_number, block_offset) } + pub fn create_inode( + &mut self, + permissions: u16, + mode: InodeMode, + uid: u32, + gid: u32, + flags: u32, + ) -> Option { + self.inode_bitmap.allocate().map(|inode_index| { + let inode = CachedInode { + inode: Inode::make_inode( + permissions, + mode, + uid, + gid, + Self::time_now(), + flags, + 0, + 0, + 0, + ), + index: inode_index, + dirty: false, + }; + self.cached_inode.insert(inode_index, inode); + inode_index + }) + } + + /// 得有一个 Inode Cache 数据结构! + pub fn read_inode( + &mut self, + index: usize, + ) -> bool { + if self.cached_inode.contains_key(&index) { + return true; + } // 已经在 Inode Cache 里了, 返回 true + if self.inode_bitmap.query(index) { + let (block, offset) = self.locate_inode(index); + let inode = CachedInode { + inode: self.fetch_inode(block, offset), + index, + dirty: false, + }; + self.cached_inode.insert(index, inode); + return true; + } // 没有在 Inode Cache 里, 但是是有效 inode, 可以读到 Cache 里, 返回 true + false // 都没有, 返回 false. + } + + pub fn write_back_inode( + &mut self, + index: usize, + ) -> bool { + if let Some(cached_inode) = self.cached_inode.get_mut(&index) { + if cached_inode.dirty { + let (block, offset) = self.locate_inode(cached_inode.index); + self.put_inode(block, offset, &cached_inode.inode); + cached_inode.dirty = false; + } + true // Inode 在 Cache 中, 如果 dirty 则写回, 如果不脏不用管, 都返回写回成功. + } else { + false // Inode 没有在 Cache 中, 返回失败. + } + } + // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer - pub fn put_inode(&mut self, block: usize, offset: usize, inode: Inode) { + fn put_inode(&mut self, block: usize, offset: usize, inode: &Inode) { let mut buffer = vec![0u8; BLOCK_SIZE]; self.device.read(block, buffer.as_mut_slice()); - let inode_raw = &inode as *const Inode as *const u8; + let inode_raw = inode as *const Inode as *const u8; let inode_slice = unsafe { std::slice::from_raw_parts(inode_raw, INODE_SIZE) }; buffer[offset..offset + INODE_SIZE].copy_from_slice(inode_slice); self.device.write(block, buffer.as_slice()); } + pub fn write_inode(&mut self, inode_index: usize, inode: &Inode) -> bool { + if self.inode_active(inode_index) { + let (block, offset) = self.locate_inode(inode_index); + self.put_inode(block, offset, inode); + true + } else { + false + } + } + + pub fn get_inode(&self, inode_index: usize) -> Option { + if self.inode_active(inode_index) { + let (block, offset) = self.locate_inode(inode_index); + Some(self.fetch_inode(block, offset)) + } else { + None + } + } + + /// 为 Inode 分配新 block, 返回 block 的编号 + pub fn allocate_block(&mut self, inode: &mut Inode) -> Option { + /// 从 direct block 里面尝试分配 + for index in inode.direct.iter_mut() { + /// 如果这个位置没被分配, 分配一个 index 塞进去 + if self.data_bitmap.query(*index as usize) == false { + let block_index = self.data_bitmap.allocate() as u32; + *index = block_index; + inode.n_blocks += 1; + // TODO 标记 inode 所在 block 为脏 + return Some(block_index); + } + } + + /// 如果这个 indirect block 还未分配, 分配一个 + if self.data_bitmap.query(inode.single_indirect as usize) == false { + // TODO 标记 inode 所在 block 为脏 + inode.single_indirect = self.data_bitmap.allocate() as u32; + } + if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) { + // TODO 标记 inode 所在 block 为脏 + inode.n_blocks += 1; + return Some(block_index); + } + + /// 如果 double indirect block 还未分配, 分配一个 + if self.data_bitmap.query(inode.double_indirect as usize) == false { + // TODO 标记 inode 所在 block 为脏 + inode.double_indirect = self.data_bitmap.allocate() as u32; + } + if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) { + // TODO 标记 inode 所在 block 为脏 + inode.n_blocks += 1; + return Some(block_index); + } + + /// 如果 triple indirect block 还未分配, 分配一个 + if self.data_bitmap.query(inode.triple_indirect as usize) == false { + // TODO 标记 inode 所在 block 为脏 + inode.triple_indirect = self.data_bitmap.allocate() as u32; + } + if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) { + // TODO 标记 inode 所在 block 为脏 + inode.n_blocks += 1; + return Some(block_index); + } + + /// 到这里说明真没空间了 + None + } + + fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option { + // 取出 single indirect block, 尝试在里面分配 + let indirect = self.fetch_block::(*indirect_entry); + for entry in indirect.entries.iter_mut() { + // 如果这个位置没被分配, 分配一个 index 塞进去 + if self.data_bitmap.query(*entry as usize) == false { + let block_index = self.data_bitmap.allocate() as u32; + *entry = block_index; + // TODO 标记 single indirect 为脏 + return Some(block_index); + } + } + None + } + + fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option { + let double_indirect = self.fetch_block::(double_indirect_entry); + for indirect_entry in double_indirect.indirect.iter_mut() { + if self.data_bitmap.query(*indirect_entry as usize) == false { + // TODO 标记 double indirect 为脏 + *indirect_entry = self.data_bitmap.allocate() as u32; + } + if let Some(block_index) = self.allocate_in_indirect(*indirect_entry) { + return Some(block_index); + } + } + None + } + + fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option { + let triple_indirect = self.fetch_block::(triple_indirect_entry); + for double_indirect_entry in triple_indirect.double_indirect.iter_mut() { + if self.data_bitmap.query(*double_indirect_entry as usize) == false { + // TODO 标记 triple indirect 为脏 + *double_indirect_entry = self.data_bitmap.allocate() as u32; + } + if let Some(block_index) = self.alloc_in_double_indirect(*double_indirect_entry) { + return Some(block_index); + } + } + None + } + + // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer + fn fetch_block(&self, block_index: u32) -> T { + let mut buffer = vec![0u8; BLOCK_SIZE]; + self.device + .read(block_index as usize, buffer.as_mut_slice()); + + let block = T::default(); + let block_slice = + unsafe { std::slice::from_raw_parts_mut(&block as *const T as *mut u8, BLOCK_SIZE) }; + block_slice.copy_from_slice(&buffer[..]); + block + } + // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer - pub fn get_inode(&self, block: usize, offset: usize) -> Inode { + fn fetch_inode(&self, block: usize, offset: usize) -> Inode { let mut buffer = vec![0u8; BLOCK_SIZE]; self.device.read(block, buffer.as_mut_slice()); - let inode = Inode::file(); + let inode = Inode::empty(); let inode_slice = unsafe { std::slice::from_raw_parts_mut(&inode as *const Inode as *mut u8, INODE_SIZE) }; @@ -146,29 +375,159 @@ impl MyFS { } impl Filesystem for MyFS { - fn lookup(&mut self, _req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEntry) { + fn init(&mut self, _req: &Request<'_>, _config: &mut KernelConfig) -> Result<(), c_int> { + debug!("Filesystem::init called."); + Ok(()) + } + + fn destroy(&mut self) { + debug!("Filesystem::destroy()"); + } + + fn access(&mut self, _req: &Request<'_>, ino: u64, mask: i32, reply: ReplyEmpty) { + debug!("Filesystem::getattr(ino: {}, mask: {})", ino, mask); + if let Some(inode) = self.get_inode(ino as usize) { + reply.ok() + } else { + reply.error(ENOENT) + } + } + + fn mkdir( + &mut self, + _req: &Request<'_>, + parent: u64, + name: &OsStr, + mode: u32, + umask: u32, + reply: ReplyEntry, + ) { debug!( - "Filesystem::lookup called with parent {} name {}", - parent, - name.to_str().unwrap() + "Filesystem::mkdir(parent: {}, name: {:?}, mode: {}, umask: {})", + parent, name, mode, umask ); - let parent = parent as usize; - if self.inode_active(parent) { - let (block, offset) = self.locate_inode(parent); - let inode = self.get_inode(block, offset); - debug!("{:?}", inode); + if let Some(inode) = self.get_inode(parent as usize) { + } else { + reply.error(ENOENT); } - reply.error(ENOENT); + // reply.error(ENOSPC); + } + + fn mknod( + &mut self, + _req: &Request<'_>, + parent: u64, + name: &OsStr, + mode: u32, + umask: u32, + rdev: u32, + reply: ReplyEntry, + ) { + debug!( + "Filesystem::mknod(parent: {}, name: {:?}, mode: {}, umask: {}, rdev: {})", + parent, name, mode, umask, rdev + ); + reply.error(ENOSPC); + } + + fn forget(&mut self, _req: &Request<'_>, _ino: u64, _nlookup: u64) { + debug!("Filesystem::forget()"); + todo!("This is a dumb implementation") } fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) { - debug!("Filesystem::getattr called with ino {}", ino); + debug!("Filesystem::getattr(ino: {})", ino); let ino = ino as usize; - if self.inode_active(ino) { - let (block, offset) = self.locate_inode(ino); - let inode = self.get_inode(block, offset); - debug!("{:?}", inode); + if let Some(inode) = self.get_inode(ino) { + // debug!("{:?}", inode); + } + reply.error(ENOENT); + } + + fn setattr( + &mut self, + _req: &Request<'_>, + ino: u64, + mode: Option, + uid: Option, + gid: Option, + size: Option, + _atime: Option, + _mtime: Option, + _ctime: Option, + fh: Option, + _crtime: Option, + _chgtime: Option, + _bkuptime: Option, + flags: Option, + reply: ReplyAttr, + ) { + debug!( + "Filesystem::setattr(ino: {:#x?}, mode: {:?}, uid: {:?}, \ + gid: {:?}, size: {:?}, fh: {:?}, flags: {:?})", + ino, mode, uid, gid, size, fh, flags + ); + reply.error(ENOSYS); + } + + fn readlink(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyData) { + debug!("[Not Implemented] readlink(ino: {})", ino); + reply.error(ENOSYS); + } + + fn lseek( + &mut self, + _req: &Request<'_>, + ino: u64, + fh: u64, + offset: i64, + whence: i32, + reply: ReplyLseek, + ) { + debug!( + "lseek(ino: {:#x?}, fh: {}, offset: {}, whence: {})", + ino, fh, offset, whence + ); + reply.error(ENOSYS); + } + + fn copy_file_range( + &mut self, + _req: &Request<'_>, + ino_in: u64, + fh_in: u64, + offset_in: i64, + ino_out: u64, + fh_out: u64, + offset_out: i64, + len: u64, + flags: u32, + reply: ReplyWrite, + ) { + debug!( + "copy_file_range(ino_in: {:#x?}, fh_in: {}, \ + offset_in: {}, ino_out: {:#x?}, fh_out: {}, offset_out: {}, \ + len: {}, flags: {})", + ino_in, fh_in, offset_in, ino_out, fh_out, offset_out, len, flags + ); + reply.error(ENOSYS); + } + + fn lookup(&mut self, _req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEntry) { + debug!( + "Filesystem::lookup called with parent {} name {}", + parent, + name.to_str().unwrap() + ); + let parent = parent as usize; + if let Some(inode) = self.get_inode(parent) { + // debug!("{:?}", inode); } + // if self.inode_active(parent) { + // let (block, offset) = self.locate_inode(parent); + // let inode = self.get_inode(block, offset); + // debug!("{:?}", inode); + // } reply.error(ENOENT); } @@ -202,18 +561,8 @@ fn main() { env_logger::init(); let args = Args::parse(); let mount_point = args.mount_point.unwrap(); - // let mut options = vec![ - // MountOption::RO, - // MountOption::FSName("hello".to_string()), - // ]; - // if args.allow_root { - // options.push(MountOption::AutoUnmount); - // } - // if args.allow_root { - // options.push(MountOption::AllowRoot); - // } let options = vec![ - MountOption::RO, + // MountOption::RO, MountOption::FSName("hello".to_string()), MountOption::AutoUnmount, MountOption::AllowRoot, -- cgit v1.2.3-70-g09d2