summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorChuyan Zhang <me@zcy.moe>2023-10-17 23:07:21 -0700
committerChuyan Zhang <me@zcy.moe>2023-10-17 23:07:21 -0700
commit7a748cadbb2e2ce8c0e045cb8fbd77ccbd47459f (patch)
tree07ed09bb6c55110dd2f2ea59283623f023b11666 /src
downloadmyfs-7a748cadbb2e2ce8c0e045cb8fbd77ccbd47459f.tar.gz
myfs-7a748cadbb2e2ce8c0e045cb8fbd77ccbd47459f.zip
initial commit
Diffstat (limited to 'src')
-rw-r--r--src/block_device/memory_disk.rs34
-rw-r--r--src/block_device/mod.rs7
-rw-r--r--src/disk/bitmap.rs49
-rw-r--r--src/disk/inode.rs152
-rw-r--r--src/disk/mod.rs2
-rw-r--r--src/main.rs225
6 files changed, 469 insertions, 0 deletions
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<Vec<u8>>,
+}
+
+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<dyn BlockDevice>,
+ pub data: Vec<u8>,
+ pub dirty_blocks: Vec<usize>,
+}
+
+impl Bitmap {
+ pub fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> 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::<Inode>();
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<String>,
+ #[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<dyn BlockDevice>,
+ data_bitmap: Bitmap,
+ inode_bitmap: Bitmap,
+ inode_start_block: usize,
+ data_start_block: usize,
+}
+
+impl MyFS {
+ fn new(device: Arc<dyn BlockDevice>, 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<u64>,
+ 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();
+}