initial commit

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();
+}