From 7a748cadbb2e2ce8c0e045cb8fbd77ccbd47459f Mon Sep 17 00:00:00 2001 From: Chuyan Zhang Date: Tue, 17 Oct 2023 23:07:21 -0700 Subject: initial commit --- src/block_device/memory_disk.rs | 34 ++++++ src/block_device/mod.rs | 7 ++ src/disk/bitmap.rs | 49 +++++++++ src/disk/inode.rs | 152 +++++++++++++++++++++++++++ src/disk/mod.rs | 2 + src/main.rs | 225 ++++++++++++++++++++++++++++++++++++++++ 6 files changed, 469 insertions(+) create mode 100644 src/block_device/memory_disk.rs create mode 100644 src/block_device/mod.rs create mode 100644 src/disk/bitmap.rs create mode 100644 src/disk/inode.rs create mode 100644 src/disk/mod.rs create mode 100644 src/main.rs (limited to 'src') diff --git a/src/block_device/memory_disk.rs b/src/block_device/memory_disk.rs new file mode 100644 index 0000000..4cffaf2 --- /dev/null +++ b/src/block_device/memory_disk.rs @@ -0,0 +1,34 @@ +use std::cell::RefCell; +use crate::block_device::{BLOCK_SIZE, BlockDevice}; + +#[repr(C)] +pub struct MemoryDisk { + /// Emulating a block device with a segment of RAM, + /// which is 64MiB == 4KiB per block * 16384 blocks + pub arena: RefCell>, +} + +impl MemoryDisk { + pub fn new() -> Self { + Self { + arena: RefCell::new(vec![0u8; BLOCK_SIZE * 16384]), + } + } + +} + +impl BlockDevice for MemoryDisk { + fn read(&self, block_id: usize, buffer: &mut [u8]) { + let block_front = block_id * BLOCK_SIZE; + let block_back = block_front + BLOCK_SIZE; + let arena = self.arena.borrow(); + buffer.copy_from_slice(&arena[block_front..block_back]); + } + + fn write(&self, block_id: usize, buffer: &[u8]) { + let block_front = block_id * BLOCK_SIZE; + let block_back = block_front + BLOCK_SIZE; + let mut arena = self.arena.borrow_mut(); + arena[block_front..block_back].copy_from_slice(buffer); + } +} \ No newline at end of file diff --git a/src/block_device/mod.rs b/src/block_device/mod.rs new file mode 100644 index 0000000..9d52e53 --- /dev/null +++ b/src/block_device/mod.rs @@ -0,0 +1,7 @@ +pub mod memory_disk; + +pub const BLOCK_SIZE: usize = 4096; +pub trait BlockDevice { + fn read(&self, block_id: usize, buffer: &mut [u8]); + fn write(&self, block_id: usize, buffer: &[u8]); +} diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs new file mode 100644 index 0000000..a5a9cc4 --- /dev/null +++ b/src/disk/bitmap.rs @@ -0,0 +1,49 @@ +use crate::block_device::{BlockDevice, BLOCK_SIZE}; +use std::sync::Arc; + +pub struct Bitmap { + pub starting_block: usize, + pub length: usize, + pub device: Arc, + pub data: Vec, + pub dirty_blocks: Vec, +} + +impl Bitmap { + pub fn new(starting_block: usize, length: usize, device: Arc) -> Self { + Self { + starting_block, + length, + device, + data: vec![0u8; length * BLOCK_SIZE], + dirty_blocks: Vec::new(), + } + } + pub fn allocate(&mut self) -> usize { + for (i, byte) in self.data.iter_mut().enumerate() { + let leading_ones = byte.leading_ones(); + if leading_ones != 8 { + *byte |= (1 << (7 - leading_ones)) as u8; + self.dirty_blocks.push(i / BLOCK_SIZE); + return i * 8 + leading_ones as usize; + } + } + panic!("No more space for allocation!") + } + + pub fn query(&self, index: usize) -> bool { + self.data[index / 8] & ((1 << (7 - index % 8)) as u8) != 0 + } + + fn write_back(&mut self) { + for block_index_offset in self.dirty_blocks.iter() { + let buffer_front_index = BLOCK_SIZE * block_index_offset; + let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1); + self.device.write( + self.starting_block + block_index_offset, + &self.data[buffer_front_index..buffer_back_index], + ); + } + self.dirty_blocks = Vec::new(); + } +} diff --git a/src/disk/inode.rs b/src/disk/inode.rs new file mode 100644 index 0000000..f38508a --- /dev/null +++ b/src/disk/inode.rs @@ -0,0 +1,152 @@ +use bitflags::bitflags; + +const DIRECT_NUMBER: usize = 15; + +#[derive(Debug)] +pub struct InodeMode(u16); + +bitflags! { + impl InodeMode: u16 { + const IXOTH = 0x0001; + const IWOTH = 0x0002; + const IROTH = 0x0004; + const IXGRP = 0x0008; + const IWGRP = 0x0010; + const IRGRP = 0x0020; + const IXUSR = 0x0040; + const IWUSR = 0x0080; + const IRUSR = 0x0100; + const ISVTX = 0x0200; + const ISGID = 0x0400; + const ISUID = 0x0800; + // These are mutually-exclusive: + const IFIFO = 0x1000; + const IFCHR = 0x2000; + const IFDIR = 0x4000; + const IFBLK = 0x6000; + const IFREG = 0x8000; + const IFLNK = 0xA000; + const IFSOCK = 0xC000; + } +} + +/// Pretty much the same with ext2, with minor changes: +/// - removed OS dependent attributes (osd1 & osd2) +/// - removed i_faddr since fragmentation is not supported +/// - changed uid and gid from u16 to u32 +/// - added more direct blocks for a total size of 128 bytes +/// TODO: do we need to extend time precision? +#[repr(C)] +#[derive(Debug)] +pub struct Inode { + mode: InodeMode, + uid: u32, + size: u32, + atime: u32, // time in seconds + ctime: u32, + mtime: u32, + dtime: u32, + gid: u32, + n_links: u16, + n_blocks: u32, + flags: u32, // TODO: do we actually need this? maybe just return 0 + direct: [u32; DIRECT_NUMBER], + single_indirect: u32, + double_indirect: u32, + triple_indirect: u32, + generation: u32, + file_acl: u32, + dir_acl: u32, // TODO do we have to implement ACL......? +} + +impl Inode { + pub fn directory() -> Self { + Self { + mode: InodeMode::IFDIR + | InodeMode::IRUSR + | InodeMode::IWUSR + | InodeMode::IXUSR + | InodeMode::IRGRP + | InodeMode::IXGRP + | InodeMode::IROTH + | InodeMode::IXOTH, + // Directory, 755 permissions + uid: 0, + size: 0, + atime: 0, + ctime: 0, + mtime: 0, + dtime: 0, + gid: 0, + n_links: 0, + n_blocks: 0, + flags: 0, + direct: [0; DIRECT_NUMBER], + single_indirect: 0, + double_indirect: 0, + triple_indirect: 0, + generation: 0, + file_acl: 0, + dir_acl: 0, + } + } + + pub fn file() -> Self { + Self { + mode: InodeMode::IFREG + | InodeMode::IRUSR + | InodeMode::IWUSR + | InodeMode::IXUSR + | InodeMode::IRGRP + | InodeMode::IXGRP + | InodeMode::IROTH + | InodeMode::IXOTH, + // RegularFile, 755 permissions + uid: 0, + size: 0, + atime: 0, + ctime: 0, + mtime: 0, + dtime: 0, + gid: 0, + n_links: 0, + n_blocks: 0, + flags: 0, + direct: [0; DIRECT_NUMBER], + single_indirect: 0, + double_indirect: 0, + triple_indirect: 0, + generation: 0, + file_acl: 0, + dir_acl: 0, + } + } +} + +// +// #[repr(C)] +// #[derive(Debug, Default)] +// pub struct FileInode { +// file_size: u32, +// direct_blocks: [u32; DIRECT_NUMBER], +// indirect_block: u32, +// doubly_indirect_block: u32, +// } // sizeof(FileInode) == 124 bytes +// +// #[repr(C)] +// #[derive(Debug, Default)] +// pub struct DirectoryInode { +// child_number: u32, +// direct_blocks: [u32; DIRECT_NUMBER], +// indirect_block: u32, +// doubly_indirect_block: u32, +// } // sizeof(FileInode) == 124 bytes +// +// #[repr(C)] +// #[derive(Debug)] +// pub enum Inode { +// File(FileInode), +// Directory(DirectoryInode), +// } // sizeof(Inode) == 128 bytes + +pub const INODE_SIZE: usize = std::mem::size_of::(); diff --git a/src/disk/mod.rs b/src/disk/mod.rs new file mode 100644 index 0000000..e4e4216 --- /dev/null +++ b/src/disk/mod.rs @@ -0,0 +1,2 @@ +pub mod inode; +pub mod bitmap; diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..414baaf --- /dev/null +++ b/src/main.rs @@ -0,0 +1,225 @@ +mod block_device; +mod disk; + +use clap::Parser; +use fuser::{Filesystem, MountOption, ReplyAttr, ReplyData, ReplyDirectory, ReplyEntry, Request}; +use std::ffi::OsStr; +use std::sync::Arc; +use std::time::Duration; +use log::debug; + +use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE}; +use disk::bitmap::Bitmap; +use disk::inode::{Inode, INODE_SIZE}; +use libc::ENOENT; + +#[derive(Parser, Debug)] +#[command(author, version, about)] +struct Args { + mount_point: Option, + #[arg(long)] + auto_unmount: bool, + #[arg(long)] + allow_root: bool, +} + +const TTL: Duration = Duration::from_secs(1); +const INODE_PER_BLOCK: usize = BLOCK_SIZE / INODE_SIZE; + +/// The design of MyFS is rather simple: +/// +-------------------+ +/// | Super Block | +/// +-------------------+ +/// | Inode Bitmap | +/// +-------------------+ +/// | ... | +/// +-------------------+ +/// | Data Block Bitmap | +/// +-------------------+ +/// | ... | +/// +-------------------+ +/// | Inode Block | +/// +-------------------+ +/// | ... | +/// +-------------------+ +/// | Data Block | +/// +-------------------+ +/// With each block 4KiB, each Inode entry 128B + +#[repr(C)] +struct MyFS { + device: Arc, + data_bitmap: Bitmap, + inode_bitmap: Bitmap, + inode_start_block: usize, + data_start_block: usize, +} + +impl MyFS { + fn new(device: Arc, total_block_number: usize) -> Self { + let max_inode_number: usize = 16384; // TODO: remove hard-coded magic number + let inode_block_number = max_inode_number / INODE_PER_BLOCK; // == 128 + let inode_bitmap_block_number = (inode_block_number + BLOCK_SIZE - 1) / BLOCK_SIZE; + + let blocks_remaining = + total_block_number - inode_block_number - inode_bitmap_block_number - 1; + // let number of data blocks be x, the remaining block number be C, + // the corresponding data bitmap length should be ceil(x / BLK_SIZE), + // thus we have BLK_SIZE * (C-1) / (BLK_SIZE+1) <= x <= BLK_SIZE * C / (BLK_SIZE+1) + // the difference of the two bounds is less than 1, + // meaning only 1 integer could be in between. + // 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( + data_bitmap_block_number + 1, + inode_bitmap_block_number, + device.clone(), + ); + let mut fs = Self { + device, + data_bitmap, + inode_bitmap, + inode_start_block: data_bitmap_block_number + inode_bitmap_block_number + 1, + data_start_block: data_bitmap_block_number + + inode_bitmap_block_number + + inode_block_number + + 1, + }; + + let _ = fs.inode_bitmap.allocate(); // Inode starts from 1 + let root_inode_index = fs.inode_bitmap.allocate(); + 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 + } + + // pub fn allocate_inode(&mut self) -> usize { + // self.inode_bitmap.allocate() + // } + + 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) { + 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; + (block_number, block_offset) + } + + // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer + pub 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_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()); + } + + // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer + pub fn get_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_slice = unsafe { + std::slice::from_raw_parts_mut(&inode as *const Inode as *mut u8, INODE_SIZE) + }; + inode_slice.copy_from_slice(&buffer[offset..offset + INODE_SIZE]); + inode + } +} + +impl Filesystem for MyFS { + 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 self.inode_active(parent) { + let (block, offset) = self.locate_inode(parent); + let inode = self.get_inode(block, offset); + debug!("{:?}", inode); + } + reply.error(ENOENT); + } + + fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) { + debug!("Filesystem::getattr called with 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); + } + reply.error(ENOENT); + } + + fn read( + &mut self, + _req: &Request<'_>, + ino: u64, + _fh: u64, + offset: i64, + _size: u32, + _flags: i32, + _lock_owner: Option, + reply: ReplyData, + ) { + todo!() + } + + fn readdir( + &mut self, + _req: &Request<'_>, + ino: u64, + _fh: u64, + offset: i64, + mut reply: ReplyDirectory, + ) { + todo!() + } +} + +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::FSName("hello".to_string()), + MountOption::AutoUnmount, + MountOption::AllowRoot, + ]; + let mem_disk = Arc::new(MemoryDisk::new()); + let filesystem = MyFS::new(mem_disk, 16384); + + fuser::mount2(filesystem, mount_point, &options).unwrap(); +} -- cgit v1.2.3-70-g09d2