Add real disk i/o, add mkfs.aya (not yet implemented)

24 files changed, 3818 insertions, 0 deletions

diff --git a/ayafs/Cargo.toml b/ayafs/Cargo.toml
new file mode 100644
index 0000000..43585e0
--- /dev/null
+++ b/ayafs/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+name = "ayafs"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+and_then_some = "1.0.0"
+bitflags = "2.4.1"
+clap = { version = "4.4.10", features = ["derive"] }
+env_logger = "0.10.1"
+fuser = "0.14.0"
+indexmap = "2.1.0"
+libc = "0.2.150"
+log = "0.4.20"
+lru = "0.12.1"
+users = "0.11.0"
diff --git a/ayafs/src/block_device/disk.rs b/ayafs/src/block_device/disk.rs
new file mode 100644
index 0000000..3f0b018
--- /dev/null
+++ b/ayafs/src/block_device/disk.rs
@@ -0,0 +1,47 @@
+use std::cell::RefCell;
+use std::fs::File;
+use std::io::{Read, Seek, SeekFrom, Write};
+use std::path::{Path, PathBuf};
+use crate::block_device::{BLOCK_SIZE, BlockDevice};
+
+pub struct Disk {
+    disk_path: PathBuf,
+    device: RefCell<File>,
+}
+
+impl Disk {
+    pub fn new(disk_path: PathBuf) -> Self {
+        let device = File::options()
+            .read(true)
+            .write(true)
+            .open(disk_path.as_path())
+            .unwrap();
+        // let device = File::open(disk_path.as_path()).unwrap();
+        Self {
+            disk_path,
+            device: RefCell::new(device),
+        }
+    }
+}
+
+impl BlockDevice for Disk {
+    fn read(&self, block_id: usize, buffer: &mut [u8]) {
+        let mut device = self.device.borrow_mut();
+        device
+            .seek(SeekFrom::Start((block_id * BLOCK_SIZE) as u64))
+            .expect("Unable to seek!");
+        device
+            .read_exact(buffer)
+            .expect("Failed to read 4096 bytes!");
+    }
+
+    fn write(&self, block_id: usize, buffer: &[u8]) {
+        let mut device = self.device.borrow_mut();
+        device
+            .seek(SeekFrom::Start((block_id * BLOCK_SIZE) as u64))
+            .expect("Unable to seek!");
+        device
+            .write_all(buffer)
+            .expect("Unable to write 4096 bytes!");
+    }
+}
\ No newline at end of file
diff --git a/ayafs/src/block_device/memory_disk.rs b/ayafs/src/block_device/memory_disk.rs
new file mode 100644
index 0000000..0639d3e
--- /dev/null
+++ b/ayafs/src/block_device/memory_disk.rs
@@ -0,0 +1,33 @@
+use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use std::cell::RefCell;
+
+#[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(block_number: usize) -> Self {
+        Self {
+            arena: RefCell::new(vec![0u8; BLOCK_SIZE * block_number]),
+        }
+    }
+}
+
+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);
+    }
+}
diff --git a/ayafs/src/block_device/mod.rs b/ayafs/src/block_device/mod.rs
new file mode 100644
index 0000000..a1e6544
--- /dev/null
+++ b/ayafs/src/block_device/mod.rs
@@ -0,0 +1,10 @@
+/// Abstracts for block devices.
+/// Currently only a mock memory disk.
+pub mod memory_disk;
+pub mod 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/ayafs/src/disk/allocation.rs b/ayafs/src/disk/allocation.rs
new file mode 100644
index 0000000..a187fad
--- /dev/null
+++ b/ayafs/src/disk/allocation.rs
@@ -0,0 +1,542 @@
+use crate::disk::block::{
+    Block, DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock,
+};
+use crate::disk::inode::{Inode, DIRECT_NUMBER, ENTRY_PER_BLOCK};
+use crate::memory::cached_block::{convert, CachedBlock};
+use crate::AyaFS;
+use libc::c_int;
+use log::debug;
+
+impl AyaFS {
+    /// 为 Inode 分配新 block, 返回 block 的编号和它在 inode 内的编号
+    pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<(u32, usize)> {
+        // 先看这个 inode 的 direct block 有没有空闲
+        for (index_within_direct, index) in inode.direct.iter_mut().enumerate() {
+            if !self.data_bitmap.query(*index as usize) {
+                let block_index = self.data_bitmap.allocate().unwrap() as u32;
+                // println!("allocating {} for direct", block_index);
+                *index = block_index;
+                inode.n_blocks += 1;
+                // 初始化这个 block
+                self.init_block(block_index as usize);
+                // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
+                return Some((block_index, index_within_direct));
+            }
+        }
+
+        // direct block 全部分配完了, 先检查 indirect block 有没有分配, 没有就分配一个
+        if !self.data_bitmap.query(inode.single_indirect as usize) {
+            inode.single_indirect = self
+                .data_bitmap
+                .allocate()
+                .expect("No free space for new block") as u32;
+            self.init_block(inode.single_indirect as usize);
+            // println!("allocating {} for indirect", inode.single_indirect);
+        }
+        // 在 indirect block 里尝试分配
+        if let Some((block_index, index_within_indirect)) =
+            self.allocate_in_indirect(inode.single_indirect)
+        {
+            // println!("allocating {} in indirect", block_index);
+            inode.n_blocks += 1;
+
+            let index_within_block = DIRECT_NUMBER + index_within_indirect;
+            return Some((block_index, index_within_block));
+        }
+
+        // direct & indirect block 全部分配完了, 先检查 double indirect block 有没有分配, 没有就分配一个
+        if !self.data_bitmap.query(inode.double_indirect as usize) {
+            inode.double_indirect = self
+                .data_bitmap
+                .allocate()
+                .expect("No free space for new block") as u32;
+            self.init_block(inode.double_indirect as usize);
+            // println!("allocating {} for double indirect", inode.double_indirect);
+        }
+        // 在 double indirect block 里尝试分配
+        if let Some((block_index, index_within_double)) =
+            self.alloc_in_double_indirect(inode.double_indirect)
+        {
+            // println!("allocating {} in double indirect", block_index);
+            inode.n_blocks += 1;
+            let index_within_block = DIRECT_NUMBER + ENTRY_PER_BLOCK + index_within_double;
+            return Some((block_index, index_within_block));
+        }
+
+        // direct, indirect & double indirect block 全部分配完了, 先检查 triple indirect block 有没有分配, 没有就分配一个
+        if !self.data_bitmap.query(inode.triple_indirect as usize) {
+            inode.triple_indirect = self
+                .data_bitmap
+                .allocate()
+                .expect("No free space for new block") as u32;
+            self.init_block(inode.triple_indirect as usize);
+            // println!("allocating {} for triple indirect", inode.triple_indirect);
+        }
+        // 在 double indirect block 里尝试分配
+        if let Some((block_index, index_within_triple)) =
+            self.alloc_in_triple_indirect(inode.triple_indirect)
+        {
+            // println!("allocating {} in triple indirect", block_index);
+            inode.n_blocks += 1;
+            let index_within_block = DIRECT_NUMBER
+                + ENTRY_PER_BLOCK
+                + ENTRY_PER_BLOCK * ENTRY_PER_BLOCK
+                + index_within_triple;
+            return Some((block_index, index_within_block));
+        }
+        None
+    }
+
+    fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<(u32, usize)> {
+        // 取出 single indirect block, 尝试在里面分配
+        let indirect_entry = indirect_entry as usize;
+        // println!("finding indirect block with number {}, bitmap says {}", indirect_entry, self.data_bitmap.query(indirect_entry));
+
+        if let Some(block) = self
+            .get_block(indirect_entry)
+            .map(convert::<DataBlock, IndirectBlock>)
+        {
+            // println!("found indirect block with number {}", indirect_entry);
+            let mut indirect_block = block.clone();
+            for (index_within_indirect, entry) in
+                indirect_block.block.entries.iter_mut().enumerate()
+            {
+                if self.data_bitmap.query(*entry as usize) == false {
+                    indirect_block.dirty = true; // 把这个块标记为 dirty
+                    let block_index = self.data_bitmap.allocate().expect("No free space") as u32;
+                    self.init_block(block_index as usize);
+                    *entry = block_index;
+                    self.update_block(indirect_block);
+                    return Some((block_index, index_within_indirect));
+                }
+            }
+        }
+        None
+    }
+
+    fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<(u32, usize)> {
+        let double_indirect_entry = double_indirect_entry as usize;
+
+        if let Some(block) = self
+            .get_block(double_indirect_entry)
+            .map(convert::<DataBlock, DoubleIndirectBlock>)
+        {
+            let mut double_indirect_block = block.clone();
+            let mut double_indirect_modified = false;
+            for (index_within_double_indirect, indirect_entry) in
+                double_indirect_block.block.indirect.iter_mut().enumerate()
+            {
+                if self.data_bitmap.query(*indirect_entry as usize) == false {
+                    double_indirect_block.dirty = true;
+                    double_indirect_modified = true;
+
+                    let indirect_index = self.data_bitmap.allocate().expect("No free space");
+                    *indirect_entry = indirect_index as u32;
+                    self.init_block(indirect_index);
+                }
+
+                if let Some((block_index, index_within_indirect)) =
+                    self.allocate_in_indirect(*indirect_entry)
+                {
+                    if double_indirect_modified {
+                        self.update_block(double_indirect_block);
+                    }
+                    let index_within_double =
+                        index_within_double_indirect * ENTRY_PER_BLOCK + index_within_indirect;
+                    return Some((block_index, index_within_double));
+                }
+            }
+        }
+        None
+    }
+
+    fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option<(u32, usize)> {
+        let triple_indirect_entry = triple_indirect_entry as usize;
+
+        if let Some(block) = self
+            .get_block(triple_indirect_entry)
+            .map(convert::<DataBlock, TripleIndirectBlock>)
+        {
+            let mut triple_indirect_block = block.clone();
+            let mut triple_indirect_modified = false;
+            for (index_within_triple_indirect, double_indirect_entry) in triple_indirect_block
+                .block
+                .double_indirect
+                .iter_mut()
+                .enumerate()
+            {
+                if self.data_bitmap.query(*double_indirect_entry as usize) == false {
+                    triple_indirect_block.dirty = true;
+                    triple_indirect_modified = true;
+
+                    let double_indirect_index = self.data_bitmap.allocate().expect("No free space");
+                    *double_indirect_entry = double_indirect_index as u32;
+                    self.init_block(double_indirect_index)
+                }
+                if let Some((block_index, index_within_double_indirect)) =
+                    self.alloc_in_double_indirect(*double_indirect_entry)
+                {
+                    if triple_indirect_modified {
+                        self.update_block(triple_indirect_block);
+                    }
+                    let index_within_triple =
+                        index_within_triple_indirect * ENTRY_PER_BLOCK * ENTRY_PER_BLOCK
+                            + index_within_double_indirect;
+                    return Some((block_index, index_within_triple));
+                }
+            }
+        }
+        None
+    }
+}
+
+impl AyaFS {
+    pub(crate) fn deallocate_all_blocks_for(&mut self, inode: &Inode) -> Result<(), c_int> {
+        // 遍历 direct block 并删除
+        for block_index in inode.direct {
+            self.data_bitmap.deallocate(block_index as usize);
+        }
+
+        // 遍历 indirect block 并删除
+        if self.data_bitmap.query(inode.single_indirect as usize) {
+            let indirect = self
+                .get_block::<IndirectBlock>(inode.single_indirect as usize)
+                .unwrap();
+            for block_index in indirect.block.entries {
+                self.data_bitmap.deallocate(block_index as usize);
+            }
+            self.data_bitmap.deallocate(inode.single_indirect as usize);
+        }
+
+        // 遍历 double indirect block 并删除
+        if self.data_bitmap.query(inode.double_indirect as usize) {
+            let double_indirect = self
+                .get_block::<DoubleIndirectBlock>(inode.double_indirect as usize)
+                .unwrap();
+            for indirect_block_index in double_indirect.block.indirect {
+                if let Some(indirect) =
+                    self.get_block::<IndirectBlock>(indirect_block_index as usize)
+                {
+                    for block_index in indirect.block.entries {
+                        self.data_bitmap.deallocate(block_index as usize);
+                    }
+                    self.data_bitmap.deallocate(indirect_block_index as usize);
+                }
+            }
+            self.data_bitmap.deallocate(inode.double_indirect as usize);
+        }
+
+        // 遍历 triple indirect block 并删除
+        if self.data_bitmap.query(inode.triple_indirect as usize) {
+            let triple_indirect = self
+                .get_block::<TripleIndirectBlock>(inode.triple_indirect as usize)
+                .unwrap();
+            for double_indirect_block_index in triple_indirect.block.double_indirect {
+                if let Some(double_indirect) =
+                    self.get_block::<DoubleIndirectBlock>(double_indirect_block_index as usize)
+                {
+                    for indirect_block_index in double_indirect.block.indirect {
+                        if let Some(indirect) =
+                            self.get_block::<IndirectBlock>(indirect_block_index as usize)
+                        {
+                            for block_index in indirect.block.entries {
+                                self.data_bitmap.deallocate(block_index as usize);
+                            }
+                            self.data_bitmap.deallocate(indirect_block_index as usize);
+                        }
+                    }
+                    self.data_bitmap
+                        .deallocate(double_indirect_block_index as usize);
+                }
+            }
+            self.data_bitmap.deallocate(inode.triple_indirect as usize);
+        }
+
+        Ok(())
+    }
+
+    /// 从 inode 中删去最后一个 block
+    pub(crate) fn deallocate_block_for(&mut self, inode: &mut Inode) -> Option<u32> {
+        // 如果 triple indirect 块存在, 则尝试从中销毁一个块
+        if self.data_bitmap.query(inode.triple_indirect as usize) {
+            if let Some(block_index) = self.deallocate_from_triple_indirect(inode.triple_indirect) {
+                inode.n_blocks -= 1;
+                return Some(block_index); // 销毁成功, 直接返回
+            } else {
+                // 销毁失败, 说明 triple indirect 空了, 把它也销毁.
+                self.data_bitmap.deallocate(inode.triple_indirect as usize);
+                inode.triple_indirect = 0; // 这个地方理论上应该不用?
+            }
+        }
+        // 如果 double indirect 块存在, 则从其中销毁
+        if self.data_bitmap.query(inode.double_indirect as usize) {
+            if let Some(block_index) = self.deallocate_from_double_indirect(inode.double_indirect) {
+                inode.n_blocks -= 1;
+                return Some(block_index);
+            } else {
+                self.data_bitmap.deallocate(inode.double_indirect as usize);
+                inode.double_indirect = 0; // 这个地方理论上应该不用?
+            }
+        }
+        // 如果 indirect 块存在, 则从其中销毁
+        if self.data_bitmap.query(inode.single_indirect as usize) {
+            if let Some(block_index) = self.deallocate_from_indirect(inode.single_indirect) {
+                inode.n_blocks -= 1;
+                return Some(block_index);
+            } else {
+                self.data_bitmap.deallocate(inode.single_indirect as usize);
+                inode.single_indirect = 0; // 这个地方理论上应该不用?
+            }
+        }
+        // 都没有，直接从 direct 块中销毁
+        for entry in inode.direct.iter_mut().rev() {
+            if self.data_bitmap.query(*entry as usize) {
+                let index = std::mem::replace(entry, 0); // let index = *entry; *entry = 0;
+                inode.n_blocks -= 1;
+                self.data_bitmap.deallocate(index as usize);
+                return Some(index);
+            }
+        }
+        None
+    }
+
+    fn deallocate_from_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option<u32> {
+        let triple_indirect_entry = triple_indirect_entry as usize;
+        if let Some(triple_indirect_block) = self
+            .get_block(triple_indirect_entry)
+            .map(convert::<DataBlock, TripleIndirectBlock>)
+        {
+            let mut triple_indirect_block = triple_indirect_block.clone();
+            let mut block_modified = false;
+            for double_indirect_entry in
+                triple_indirect_block.block.double_indirect.iter_mut().rev()
+            {
+                // 如果这个位置的 double indirect 存在
+                if self.data_bitmap.query(*double_indirect_entry as usize) {
+                    // 尝试从中销毁一个块
+                    if let Some(block_index) =
+                        self.deallocate_from_double_indirect(*double_indirect_entry)
+                    {
+                        if block_modified {
+                            self.update_block(triple_indirect_block);
+                        }
+                        return Some(block_index); // 成功则直接返回
+                    } else {
+                        // 失败则把这个 double indirect 销毁
+                        let double_indirect_entry_to_deallocate =
+                            std::mem::replace(double_indirect_entry, 0);
+                        self.data_bitmap
+                            .deallocate(double_indirect_entry_to_deallocate as usize);
+                        triple_indirect_block.dirty = true;
+                        block_modified = true;
+                    }
+                }
+            }
+            if block_modified {
+                self.update_block(triple_indirect_block);
+            }
+        }
+        None
+    }
+
+    fn deallocate_from_double_indirect(&mut self, double_indirect_entry: u32) -> Option<u32> {
+        let double_indirect_entry = double_indirect_entry as usize;
+        if let Some(double_indirect_block) = self
+            .get_block(double_indirect_entry)
+            .map(convert::<DataBlock, DoubleIndirectBlock>)
+        {
+            let mut double_indirect_block = double_indirect_block.clone();
+            let mut block_modified = false;
+            for indirect_entry in double_indirect_block.block.indirect.iter_mut().rev() {
+                // 如果这个位置的 indirect 存在
+                if self.data_bitmap.query(*indirect_entry as usize) {
+                    // 尝试从中销毁一个块
+                    if let Some(block_index) = self.deallocate_from_indirect(*indirect_entry) {
+                        if block_modified {
+                            self.update_block(double_indirect_block);
+                        }
+                        return Some(block_index); // 成功则直接返回
+                    } else {
+                        // 失败则把这个 indirect 销毁
+                        let indirect_entry_to_deallocate = std::mem::replace(indirect_entry, 0);
+                        self.data_bitmap
+                            .deallocate(indirect_entry_to_deallocate as usize);
+                        double_indirect_block.dirty = true;
+                        block_modified = true;
+                    }
+                }
+            }
+            if block_modified {
+                self.update_block(double_indirect_block);
+            }
+        }
+        None
+    }
+
+    fn deallocate_from_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
+        let indirect_entry = indirect_entry as usize;
+        if let Some(indirect_block) = self
+            .get_block(indirect_entry)
+            .map(convert::<DataBlock, IndirectBlock>)
+        {
+            let mut indirect_block = indirect_block.clone();
+            // 遍历 indirect block 里的每个 block
+            for entry in indirect_block.block.entries.iter_mut().rev() {
+                // 如果这个 block 存在, 销毁它
+                if self.data_bitmap.query(*entry as usize) {
+                    let entry_to_deallocate = std::mem::replace(entry, 0);
+
+                    self.data_bitmap.deallocate(entry_to_deallocate as usize);
+                    indirect_block.dirty = true;
+                    self.update_block(indirect_block);
+
+                    return Some(entry_to_deallocate);
+                }
+            }
+        }
+        None
+    }
+}
+
+impl AyaFS {
+    pub(crate) fn get_block_index(
+        &mut self,
+        inode: &Inode,
+        mut block_index_within_inode: usize,
+    ) -> Option<usize> {
+        debug!(
+            "get_block_index(block_index_within_inode: {})",
+            block_index_within_inode
+        );
+        // direct block
+        if block_index_within_inode < DIRECT_NUMBER {
+            let block_index = inode.direct[block_index_within_inode] as usize;
+            debug!("  get_block_index -> direct");
+            return if self.data_bitmap.query(block_index) {
+                debug!("  get_block_index -> direct -> ✓");
+                Some(block_index)
+            } else {
+                debug!("  get_block_index -> direct -> ×");
+                None
+            };
+        } else {
+            block_index_within_inode -= DIRECT_NUMBER;
+        }
+
+        // indirect block
+        let indirect_number = ENTRY_PER_BLOCK;
+        if block_index_within_inode < indirect_number {
+            return if let Some(indirect_block) =
+                self.get_block::<IndirectBlock>(inode.single_indirect as usize)
+            {
+                debug!("  get_block_index -> indirect");
+                let block_index = indirect_block.block.entries[block_index_within_inode] as usize;
+                if self.data_bitmap.query(block_index) {
+                    debug!("  get_block_index -> indirect -> ✓");
+                    Some(block_index)
+                } else {
+                    debug!("  get_block_index -> indirect -> ×");
+                    None
+                }
+            } else {
+                debug!("  get_block_index -> indirect -> ×");
+                None
+            };
+        } else {
+            block_index_within_inode -= indirect_number;
+        }
+
+        // double indirect block
+        let double_indirect_number = ENTRY_PER_BLOCK * ENTRY_PER_BLOCK;
+        if block_index_within_inode < double_indirect_number {
+            if let Some(double_indirect_block) =
+                self.get_block::<DoubleIndirectBlock>(inode.double_indirect as usize)
+            {
+                debug!("  get_block_index -> double_indirect");
+                // 取出 double indirect block
+                let indirect_block_index = double_indirect_block.block.indirect
+                    [block_index_within_inode / ENTRY_PER_BLOCK]
+                    as usize;
+                // 要找的 entry 在 double indirect block 中的第几个 indirect block
+                if let Some(indirect_block) = self.get_block::<IndirectBlock>(indirect_block_index)
+                {
+                    debug!("  get_block_index -> double_indirect -> indirect");
+                    let block_index = indirect_block.block.entries
+                        [block_index_within_inode % ENTRY_PER_BLOCK]
+                        as usize;
+                    // 拿到 DirectoryBlock 的 index
+                    return if self.data_bitmap.query(block_index) {
+                        debug!("  get_block_index -> double_indirect -> indirect -> ✓");
+                        Some(block_index)
+                    } else {
+                        debug!("  get_block_index -> double_indirect -> indirect -> ×");
+                        None
+                    };
+                }
+            }
+            return None;
+        } else {
+            block_index_within_inode -= double_indirect_number;
+        }
+
+        // triple indirect block
+        if let Some(triple_indirect_block) =
+            self.get_block::<TripleIndirectBlock>(inode.triple_indirect as usize)
+        {
+            // 取出 triple indirect block
+            let double_indirect_block_index = triple_indirect_block.block.double_indirect
+                [block_index_within_inode / (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK)]
+                as usize;
+            // 要找的 entry 在 triple indirect block 中的第几个 double indirect block
+            if let Some(double_indirect_block) =
+                self.get_block::<DoubleIndirectBlock>(double_indirect_block_index)
+            {
+                // 取出 double indirect block
+                let indirect_block_index = double_indirect_block.block.indirect
+                    [block_index_within_inode % (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK)
+                        / ENTRY_PER_BLOCK] as usize;
+                // 要找的 entry 在 double indirect block 中的第几个 indirect block
+                if let Some(indirect_block) = self.get_block::<IndirectBlock>(indirect_block_index)
+                {
+                    let block_index = indirect_block.block.entries
+                        [block_index_within_inode % ENTRY_PER_BLOCK]
+                        as usize;
+                    // DirectoryBlock 的 index
+                    return if self.data_bitmap.query(block_index) {
+                        Some(block_index)
+                    } else {
+                        None
+                    };
+                }
+            }
+        }
+
+        None
+    }
+
+    pub(crate) fn access_block<T: Block>(
+        &mut self,
+        inode: &Inode,
+        block_index_within_inode: usize,
+    ) -> Option<&CachedBlock<T>> {
+        self.get_block_index(inode, block_index_within_inode)
+            .map(|block_index| {
+                self.get_block::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+            })
+    }
+
+    pub(crate) fn access_block_mut<T: Block>(
+        &mut self,
+        inode: &Inode,
+        block_index_within_inode: usize,
+    ) -> Option<&mut CachedBlock<T>> {
+        self.get_block_index(inode, block_index_within_inode)
+            .map(|block_index| {
+                debug!(
+                    "access_block_mut(index: {}) found",
+                    block_index_within_inode
+                );
+                self.get_block_mut::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+            })
+    }
+}
diff --git a/ayafs/src/disk/bitmap.rs b/ayafs/src/disk/bitmap.rs
new file mode 100644
index 0000000..b68c341
--- /dev/null
+++ b/ayafs/src/disk/bitmap.rs
@@ -0,0 +1,48 @@
+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>,
+}
+
+impl Bitmap {
+    pub(crate) fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
+        Self {
+            starting_block,
+            length,
+            device,
+            data: vec![0u8; length * BLOCK_SIZE],
+        }
+    }
+    pub(crate) fn allocate(&mut self) -> Option<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;
+                return Some(i * 8 + leading_ones as usize);
+            }
+        }
+        None
+    }
+
+    pub(crate) fn query(&self, index: usize) -> bool {
+        if index == 0 {
+            false
+        } else {
+            self.data[index / 8] & ((1 << (7 - index % 8)) as u8) != 0
+        }
+    }
+
+    pub(crate) fn deallocate(&mut self, index: usize) -> bool {
+        if self.query(index) {
+            let mask = !(1u8 << (7 - index % 8));
+            self.data[index / 8] &= mask;
+            true
+        } else {
+            false
+        }
+    }
+}
diff --git a/ayafs/src/disk/block.rs b/ayafs/src/disk/block.rs
new file mode 100644
index 0000000..73819e2
--- /dev/null
+++ b/ayafs/src/disk/block.rs
@@ -0,0 +1,245 @@
+use crate::disk::inode::Inode;
+use std::ffi::{OsStr, OsString};
+use std::os::unix::ffi::OsStrExt;
+
+pub trait Block: Default + Clone {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct DataBlock(pub(crate) [u8; 4096]);
+
+impl Default for DataBlock {
+    fn default() -> Self {
+        Self([0; 4096])
+    }
+}
+
+impl Block for DataBlock {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct InodeBlock {
+    pub(crate) inodes: [Inode; 32],
+}
+
+impl Default for InodeBlock {
+    fn default() -> Self {
+        Self {
+            inodes: [
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+                Inode::empty(),
+            ],
+        }
+    }
+}
+
+impl Block for InodeBlock {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct DirectoryEntry {
+    pub inode: u32,
+    pub record_len: u16,
+    pub name_len: u8,
+    pub file_type: u8,
+    pub name: [u8; 256],
+}
+
+impl DirectoryEntry {
+    pub(crate) fn name(&self) -> OsString {
+        let name = &self.name[0..self.name_len as usize];
+        OsStr::from_bytes(name).to_os_string()
+    }
+}
+
+impl Default for DirectoryEntry {
+    fn default() -> Self {
+        Self {
+            inode: 0,
+            record_len: 0,
+            name_len: 0,
+            file_type: 0x0,
+            name: [0; 256],
+        }
+    }
+}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct DirectoryBlock {
+    pub entries: [DirectoryEntry; 15],
+    pub occupancy: [u8; 2],
+    reserved: [u8; 134],
+}
+
+impl Default for DirectoryBlock {
+    fn default() -> Self {
+        Self {
+            entries: [
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+                DirectoryEntry::default(),
+            ],
+            occupancy: [0x80, 0x00], // 0b1000_0000
+            reserved: [0xFF; 134],
+        }
+    }
+}
+
+impl DirectoryBlock {
+    #[allow(unused)]
+    pub(crate) fn is_full(&self) -> bool {
+        self.occupancy[0] == 0xFF && self.occupancy[1] == 0xFF
+    }
+
+    pub(crate) fn query(&self, mut index: usize) -> bool {
+        if index < 7 {
+            // 0-6, first u8
+            index = index + 1;
+            self.occupancy[0] & (1 << (7 - index)) as u8 != 0
+        } else if index < 15 {
+            // 7-14, second u8
+            index = index - 7;
+            self.occupancy[1] & (1 << (7 - index)) as u8 != 0
+        } else {
+            false
+        }
+    }
+
+    pub(crate) fn allocate(&mut self, mut index: usize) -> bool {
+        if index < 7 {
+            index = index + 1;
+            let mask = (1 << (7 - index)) as u8;
+            if self.occupancy[0] & mask != 0 {
+                false
+            } else {
+                self.occupancy[0] |= mask;
+                true
+            }
+        } else {
+            index = index - 7;
+            let mask = (1 << (7 - index)) as u8;
+            if self.occupancy[1] & mask != 0 {
+                false
+            } else {
+                self.occupancy[1] |= mask;
+                true
+            }
+        }
+    }
+
+    // pub(crate) fn allocate(&mut self) -> Option<usize> {
+    //     if self.occupancy[0] != 0xFF {
+    //         let leading_ones = self.occupancy[0].leading_ones();
+    //         self.occupancy[0] |= (1 << (7 - leading_ones)) as u8;
+    //         Some(leading_ones as usize)
+    //     } else if self.occupancy[1] != 0xFF {
+    //         let leading_ones = self.occupancy[1].leading_ones();
+    //         self.occupancy[1] |= (1 << (7 - leading_ones)) as u8;
+    //         Some(7 + leading_ones as usize)
+    //     } else {
+    //         None
+    //     }
+    // }
+
+    pub(crate) fn deallocate(&mut self, mut index: usize) {
+        if index < 7 {
+            index = index + 1;
+            self.occupancy[0] &= !((1 << (7 - index)) as u8);
+        } else if index < 15 {
+            // 7-14, second u8
+            index = index - 7;
+            self.occupancy[1] &= !((1 << (7 - index)) as u8);
+        }
+    }
+}
+
+impl Block for DirectoryBlock {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct IndirectBlock {
+    pub entries: [u32; 1024],
+}
+
+impl Default for IndirectBlock {
+    fn default() -> Self {
+        Self { entries: [0; 1024] }
+    }
+}
+
+impl Block for IndirectBlock {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct DoubleIndirectBlock {
+    pub indirect: [u32; 1024],
+}
+
+impl Default for DoubleIndirectBlock {
+    fn default() -> Self {
+        Self {
+            indirect: [0; 1024],
+        }
+    }
+}
+
+impl Block for DoubleIndirectBlock {}
+
+#[repr(C)]
+#[derive(Clone)]
+pub struct TripleIndirectBlock {
+    pub double_indirect: [u32; 1024],
+}
+
+impl Default for TripleIndirectBlock {
+    fn default() -> Self {
+        Self {
+            double_indirect: [0; 1024],
+        }
+    }
+}
+
+impl Block for TripleIndirectBlock {}
diff --git a/ayafs/src/disk/inode.rs b/ayafs/src/disk/inode.rs
new file mode 100644
index 0000000..0c801ad
--- /dev/null
+++ b/ayafs/src/disk/inode.rs
@@ -0,0 +1,312 @@
+use crate::utils;
+use bitflags::bitflags;
+use fuser::FileType;
+use crate::block_device::BLOCK_SIZE;
+
+pub const DIRECT_NUMBER: usize = 15;
+
+#[derive(Debug, Clone, Copy)]
+pub struct InodeMode(pub 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;
+    }
+}
+
+impl InodeMode {
+    #[allow(unused)]
+    pub(crate) fn exec_other(&self) -> bool {
+        self.0 & Self::IXOTH.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn write_other(&self) -> bool {
+        self.0 & Self::IWOTH.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn read_other(&self) -> bool {
+        self.0 & Self::IROTH.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn exec_group(&self) -> bool {
+        self.0 & Self::IXGRP.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn write_group(&self) -> bool {
+        self.0 & Self::IWGRP.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn read_group(&self) -> bool {
+        self.0 & Self::IRGRP.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn exec_user(&self) -> bool {
+        self.0 & Self::IXUSR.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn write_user(&self) -> bool {
+        self.0 & Self::IWUSR.0 != 0
+    }
+    #[allow(unused)]
+    pub(crate) fn read_user(&self) -> bool {
+        self.0 & Self::IRUSR.0 != 0
+    }
+
+    pub(crate) fn perm(&self) -> u16 {
+        self.0 & 0x0FFF
+    }
+
+    pub(crate) fn is_file(&self) -> bool {
+        (self.0 & 0xF000) == Self::IFREG.0
+    }
+
+    pub(crate) fn is_dir(&self) -> bool {
+        (self.0 & 0xF000) == Self::IFDIR.0
+    }
+
+    pub(crate) fn is_symlink(&self) -> bool {
+        self.0 & 0xF000 == Self::IFLNK.0
+    }
+
+    pub(crate) fn validate(mode_value: u16) -> Option<Self> {
+        let valid_flags: [u16; 7] = [0x1000, 0x2000, 0x4000, 0x6000, 0x8000, 0xA000, 0xC000];
+        valid_flags
+            .contains(&(mode_value & 0xF000))
+            .then(|| Self(mode_value))
+    }
+}
+
+impl From<InodeMode> for FileType {
+    fn from(value: InodeMode) -> Self {
+        let type_flag = value.0 & 0xF000;
+        match type_flag {
+            0x1000 => FileType::NamedPipe,
+            0x2000 => FileType::CharDevice,
+            0x4000 => FileType::Directory,
+            0x6000 => FileType::BlockDevice,
+            0x8000 => FileType::RegularFile,
+            0xA000 => FileType::Symlink,
+            0xC000 => FileType::Socket,
+            _ => panic!("Invalid inode mode {:x}", type_flag),
+        }
+    }
+}
+
+impl From<InodeMode> for u8 {
+    fn from(value: InodeMode) -> Self {
+        utils::from_filetype(value.into())
+    }
+}
+
+/// 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, Clone)]
+pub struct Inode {
+    pub mode: InodeMode,
+    pub uid: u32,
+    pub size: u32,
+    pub atime: u32,  // access time, in seconds
+    pub ctime: u32,  // change time, in seconds
+    pub mtime: u32,  // modify time, in seconds
+    pub crtime: u32, // create time, in seconds
+    pub gid: u32,
+    pub n_links: u16,
+    pub n_blocks: u32,
+    pub flags: u32, // TODO: do we actually need this? maybe just return 0
+    pub direct: [u32; DIRECT_NUMBER],
+    pub single_indirect: u32,
+    pub double_indirect: u32,
+    pub triple_indirect: u32,
+    pub generation: u32,
+    pub file_acl: u32,
+    pub dir_acl: u32, // TODO do we have to implement ACL......?
+}
+
+impl Inode {
+    fn new(
+        mode: InodeMode,
+        uid: u32,
+        gid: u32,
+        time: u32,
+        flags: u32,
+        generation: u32,
+        file_acl: u32,
+        dir_acl: u32,
+    ) -> Self {
+        Self {
+            mode,
+            uid,
+            size: 0,
+            atime: time,
+            ctime: time,
+            mtime: time,
+            crtime: time,
+            gid,
+            n_links: 1,
+            n_blocks: 0,
+            flags,
+            direct: [0; DIRECT_NUMBER],
+            single_indirect: 0,
+            double_indirect: 0,
+            triple_indirect: 0,
+            generation,
+            file_acl,
+            dir_acl,
+        }
+    }
+
+    #[allow(unused)]
+    pub fn make_inode(
+        permissions: u16,
+        mode: InodeMode,
+        uid: u32,
+        gid: u32,
+        time: u32,
+        flags: u32,
+        generation: u32,
+        file_acl: u32,
+        dir_acl: u32,
+    ) -> Self {
+        Self::new(
+            InodeMode(permissions) | mode,
+            uid,
+            gid,
+            time,
+            flags,
+            generation,
+            file_acl,
+            dir_acl,
+        )
+    }
+
+    pub fn directory(
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        time: u32,
+        flags: u32,
+        generation: u32,
+        file_acl: u32,
+        dir_acl: u32,
+    ) -> Self {
+        Self::new(
+            InodeMode(permissions) | InodeMode::IFDIR,
+            uid,
+            gid,
+            time,
+            flags,
+            generation,
+            file_acl,
+            dir_acl,
+        )
+    }
+
+    pub fn file(
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        time: u32,
+        flags: u32,
+        generation: u32,
+        file_acl: u32,
+        dir_acl: u32,
+    ) -> Self {
+        Self::new(
+            InodeMode(permissions) | InodeMode::IFREG,
+            uid,
+            gid,
+            time,
+            flags,
+            generation,
+            file_acl,
+            dir_acl,
+        )
+    }
+
+    pub fn symlink(
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        time: u32,
+        flags: u32,
+        generation: u32,
+        file_acl: u32,
+        dir_acl: u32,
+    ) -> Self {
+        Self::new(
+            InodeMode(permissions) | InodeMode::IFLNK,
+            uid,
+            gid,
+            time,
+            flags,
+            generation,
+            file_acl,
+            dir_acl,
+        )
+    }
+
+    pub(crate) fn is_file(&self) -> bool {
+        self.mode.is_file()
+    }
+
+    pub(crate) fn is_dir(&self) -> bool {
+        self.mode.is_dir()
+    }
+
+    pub(crate) fn is_symlink(&self) -> bool {
+        self.mode.is_symlink()
+    }
+
+    pub(crate) fn file_type(&self) -> FileType {
+        self.mode.into()
+    }
+
+    pub fn empty() -> Self {
+        Self {
+            mode: InodeMode(0),
+            uid: 0,
+            size: 0,
+            atime: 0,
+            ctime: 0,
+            mtime: 0,
+            crtime: 0,
+            gid: 0,
+            n_links: 0,
+            n_blocks: 0,
+            flags: 0,
+            direct: [0; 15],
+            single_indirect: 0,
+            double_indirect: 0,
+            triple_indirect: 0,
+            generation: 0,
+            file_acl: 0,
+            dir_acl: 0,
+        }
+    }
+}
+pub const INODE_SIZE: usize = std::mem::size_of::<Inode>();
+pub const ENTRY_PER_BLOCK: usize = BLOCK_SIZE / 4;
\ No newline at end of file
diff --git a/ayafs/src/disk/mod.rs b/ayafs/src/disk/mod.rs
new file mode 100644
index 0000000..878e832
--- /dev/null
+++ b/ayafs/src/disk/mod.rs
@@ -0,0 +1,6 @@
+pub mod allocation;
+/// On-disk data structures and logic.
+/// Including bitmaps, inodes and blocks.
+pub mod bitmap;
+pub mod block;
+pub mod inode;
diff --git a/ayafs/src/filesystem/mod.rs b/ayafs/src/filesystem/mod.rs
new file mode 100644
index 0000000..1eaa8e8
--- /dev/null
+++ b/ayafs/src/filesystem/mod.rs
@@ -0,0 +1,2 @@
+/// Where upper filesystem calls are implemented.
+pub mod trait_impl;
diff --git a/ayafs/src/filesystem/trait_impl.rs b/ayafs/src/filesystem/trait_impl.rs
new file mode 100644
index 0000000..1c40b92
--- /dev/null
+++ b/ayafs/src/filesystem/trait_impl.rs
@@ -0,0 +1,1247 @@
+use crate::block_device::BLOCK_SIZE;
+use crate::disk::block::DataBlock;
+use crate::disk::inode::InodeMode;
+use crate::utils::permissions::{check_access, clear_suid_sgid, get_groups};
+use crate::utils::{from_filetype, from_systime, time_now, to_fileattr, to_filetype};
+use crate::{AyaFS, TTL};
+use fuser::TimeOrNow::{Now, SpecificTime};
+use fuser::{
+    FileType, Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty,
+    ReplyEntry, ReplyOpen, ReplyWrite, Request, TimeOrNow,
+};
+use libc::{c_int, EACCES, EBADF, EEXIST, EINVAL, EIO, EISDIR, ENAMETOOLONG, ENOENT, ENOSPC, ENOTDIR, ENOTEMPTY, EPERM, IPOPT_OFFSET, O_ACCMODE, O_RDONLY, O_RDWR, O_WRONLY, R_OK, S_ISGID, S_ISUID, S_IXGRP, S_IXOTH, S_IXUSR, W_OK, RENAME_NOREPLACE, RENAME_EXCHANGE};
+use log::debug;
+use std::ffi::OsStr;
+use std::os::unix::ffi::OsStrExt;
+use std::path::Path;
+use std::slice;
+use std::time::SystemTime;
+
+impl AyaFS {}
+
+impl Filesystem for AyaFS {
+    fn init(&mut self, _req: &Request<'_>, _config: &mut KernelConfig) -> Result<(), c_int> {
+        debug!("`init()");
+        Ok(())
+    }
+
+    fn destroy(&mut self) {
+        debug!("destroy()");
+        // TODO 写回
+    }
+
+    fn lookup(&mut self, req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEntry) {
+        if name.len() > 255 {
+            reply.error(ENAMETOOLONG);
+            return;
+        }
+
+        let parent = parent as usize;
+        if let Some(parent_inode) = self.get_inode(parent) {
+            if check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                R_OK,
+            ) {
+                let parent_inode = parent_inode.clone();
+                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);
+                    }
+                    Err(err_code) => reply.error(err_code),
+                };
+            } else {
+                reply.error(EACCES);
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) {
+        if let Some(inode) = self.get_inode(ino as usize) {
+            reply.attr(&TTL, &to_fileattr(ino as usize, inode));
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn setattr(
+        &mut self,
+        req: &Request<'_>,
+        ino: u64,
+        mode: Option<u32>,
+        uid: Option<u32>,
+        gid: Option<u32>,
+        size: Option<u64>, // 当 setattr 被 ftruncate invoke 时会设置 size
+        atime: Option<TimeOrNow>,
+        mtime: Option<TimeOrNow>,
+        _ctime: Option<SystemTime>,
+        fh: Option<u64>,               // 当 setattr 被 ftruncate invoke 时会提供 fh
+        _crtime: Option<SystemTime>,   // 忽略
+        _chgtime: Option<SystemTime>,  // 忽略
+        _bkuptime: Option<SystemTime>, // 忽略
+        _flags: Option<u32>,           // 忽略
+        reply: ReplyAttr,
+    ) {
+        if let Some(inode) = self.get_inode_mut(ino as usize) {
+            // chmod
+            if let Some(mode) = mode {
+                debug!("chmod on inode {:#x?} mode {:o}", ino, mode);
+                if req.uid() != 0 && req.uid() != inode.uid {
+                    reply.error(EPERM);
+                    return;
+                } // uid == 0 (root) or uid == inode.uid (user itself)
+
+                if req.uid() != 0
+                    && req.gid() != inode.gid
+                    && !get_groups(req.pid()).contains(&inode.gid)
+                {
+                    inode.mode = InodeMode((mode & !S_ISGID) as u16);
+                } else {
+                    inode.mode = InodeMode(mode as u16);
+                }
+
+                inode.ctime = time_now();
+                reply.attr(&TTL, &to_fileattr(ino as usize, inode));
+                return;
+            }
+
+            // chown
+            if uid.is_some() || gid.is_some() {
+                debug!("chown on inode {:#x?} uid {:?} gid {:?}", ino, uid, gid);
+                if let Some(uid) = uid {
+                    // 虽然只有 root 可以 chown 但是 user chown 自己也是不报错的
+                    if req.uid() != 0 && !(uid == inode.uid && uid == req.uid()) {
+                        reply.error(EPERM);
+                        return;
+                    }
+                }
+                if let Some(gid) = gid {
+                    // 只有 root 和 file owner 才可以 chgrp
+                    if req.uid() != 0 && req.uid() != inode.uid {
+                        reply.error(EPERM);
+                        return;
+                    }
+                    // root 可以任意 chgrp, 非 root 只能修改到用户自己所在的组里
+                    if req.gid() != 0 && !get_groups(req.pid()).contains(&gid) {
+                        reply.error(EPERM);
+                        return;
+                    }
+                }
+
+                // 可执行文件要清除 suid & sgid
+                if inode.mode.0 & (S_IXUSR | S_IXGRP | S_IXOTH) as u16 != 0 {
+                    inode.mode = clear_suid_sgid(inode.mode);
+                }
+
+                // chown 要清除 suid
+                if let Some(uid) = uid {
+                    inode.uid = uid;
+                    inode.mode.0 &= !S_ISUID as u16;
+                }
+
+                if let Some(gid) = gid {
+                    inode.gid = gid;
+                    if req.uid() != 0 {
+                        inode.mode.0 &= !S_ISGID as u16;
+                    }
+                }
+                inode.ctime = time_now();
+                reply.attr(&TTL, &to_fileattr(ino as usize, inode));
+                return;
+            }
+
+            // ftruncate
+            if let Some(size) = size {
+                // TODO 当大小减小的时候对应 deallocate 块
+                debug!("ftruncate on inode {:#x?} size {:?}", ino, size);
+                if let Some(file_handle) = fh {
+                    let mut inode = inode.clone();
+                    let (inode_index, _read, write) =
+                        self.file_handle_map.get(&file_handle).unwrap();
+                    assert_eq!(ino as usize, *inode_index);
+                    if !write {
+                        reply.error(EACCES);
+                    } else {
+                        inode.size = size as u32;
+                        reply.attr(&TTL, &to_fileattr(*inode_index, &inode));
+                        self.update_inode(*inode_index, inode);
+                    }
+                } else {
+                    if !check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, W_OK) {
+                        reply.error(EACCES);
+                    } else {
+                        inode.size = size as u32;
+                        reply.attr(&TTL, &to_fileattr(ino as usize, &inode));
+                    }
+                }
+                return;
+            }
+
+            // time 相关
+            if atime.is_some() || mtime.is_some() {
+                let current_time = time_now();
+                if let Some(atime) = atime {
+                    debug!("utimensat on inode {:#x?}, atime {:?}", ino, atime);
+                    // root 和 user 可以随意修改 atime, 其他用户只能 touch (即 atime == Now)
+                    if req.uid() != 0 && req.uid() != inode.uid && atime != Now {
+                        reply.error(EPERM);
+                        return;
+                    }
+
+                    if req.uid() != 0
+                        && req.uid() != inode.uid
+                        && check_access(
+                            req.uid(),
+                            req.gid(),
+                            inode.uid,
+                            inode.gid,
+                            inode.mode,
+                            R_OK, // atime 来说是 read TODO 对吗
+                        )
+                    {
+                        reply.error(EACCES);
+                        return;
+                    }
+
+                    inode.atime = match atime {
+                        SpecificTime(time) => from_systime(time),
+                        Now => current_time,
+                    };
+                    inode.ctime = current_time;
+                }
+                if let Some(mtime) = mtime {
+                    debug!("utimensat on inode {:#x?}, mtime {:?}", ino, mtime);
+                    // root 和 user 可以随意修改 mtime, 其他用户只能 mtime == Now
+                    if req.uid() != 0 && req.uid() != inode.uid && mtime != Now {
+                        reply.error(EPERM);
+                        return;
+                    }
+
+                    if req.uid() != 0
+                        && req.uid() != inode.uid
+                        && check_access(
+                            req.uid(),
+                            req.gid(),
+                            inode.uid,
+                            inode.gid,
+                            inode.mode,
+                            W_OK, // mtime 来说是 write
+                        )
+                    {
+                        reply.error(EACCES);
+                        return;
+                    }
+
+                    inode.mtime = match mtime {
+                        SpecificTime(time) => from_systime(time),
+                        Now => current_time,
+                    };
+                    inode.ctime = current_time;
+                }
+            }
+            reply.attr(&TTL, &to_fileattr(ino as usize, inode));
+            return;
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    // 这啥语义啊??
+    fn readlink(&mut self, req: &Request<'_>, ino: u64, reply: ReplyData) {
+        debug!("readlink(ino: {})", ino);
+        if let Some(inode) = self.get_inode(ino as usize) {
+            if !inode.is_symlink() {
+                reply.error(ENOENT);
+                return;
+            }
+            if !check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, R_OK) {
+                reply.error(EACCES);
+                return;
+            }
+            let path_length = inode.size as usize;
+            let mut path = vec![0u8; path_length];
+            if path_length < 60 {
+                debug!(
+                    "symlink path length is {}, reading directly from inode.direct",
+                    path_length
+                );
+                let copy_src = unsafe {
+                    let src = (&inode.direct) as *const u32 as *const u8;
+                    slice::from_raw_parts(src, path_length)
+                };
+                path.as_mut_slice().copy_from_slice(copy_src);
+            } else {
+                debug!(
+                    "symlink path length is {}, using original read",
+                    path_length
+                );
+                let inode = inode.clone();
+                let mut read_ptr = 0usize;
+                while read_ptr < path_length {
+                    let block_index = read_ptr / BLOCK_SIZE;
+                    let offset = read_ptr % BLOCK_SIZE;
+
+                    let read_length_within_block = if BLOCK_SIZE - offset < path_length - read_ptr {
+                        BLOCK_SIZE - offset
+                    } else {
+                        path_length - read_ptr
+                    };
+
+                    if let Some(block) = self.access_block::<DataBlock>(&inode, block_index) {
+                        (&mut path[read_ptr..read_ptr + read_length_within_block]).copy_from_slice(
+                            &block.block.0[offset..offset + read_length_within_block],
+                        );
+                        read_ptr += read_length_within_block;
+                    } else {
+                        reply.error(EIO);
+                        return;
+                    }
+                }
+            }
+            debug!(
+                "readlink path read is {:?}",
+                OsStr::from_bytes(path.as_slice())
+            );
+            reply.data(path.as_slice());
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn mknod(
+        &mut self,
+        req: &Request<'_>,
+        parent: u64,
+        name: &OsStr,
+        mode: u32,
+        _umask: u32, // umask 是用不到的
+        _rdev: u32,  // the device number (only valid if created file is a device)
+        reply: ReplyEntry,
+    ) {
+        debug!(
+            "mknod(parent: {}, name: {:?}, mode: {}, umask: {})",
+            parent, name, mode, _umask
+        );
+
+        let parent = parent as usize;
+        if let Some(parent_inode) = self.get_inode(parent) {
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                W_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            // parent 不是 IFDIR -> Not a directory
+            if !parent_inode.is_dir() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            // 文件名长度超过 255, 返回 filename too long
+            if name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            let mut parent_inode = parent_inode.clone();
+            // 如果已经存在, 返回 already exists
+            if self.lookup_name(parent, &parent_inode, name).is_ok() {
+                reply.error(EEXIST);
+                return;
+            }
+
+            let mode = mode as u16;
+            if let Some((child_inode_index, child_inode)) =
+                self.create_file(mode, req.uid(), req.gid(), 0)
+            {
+                let mode = child_inode.mode;
+                let file_attr = to_fileattr(child_inode_index, child_inode);
+                if let Err(err_code) = self.add_direntry(
+                    parent,
+                    &mut parent_inode,
+                    child_inode_index,
+                    name,
+                    mode.into(),
+                ) {
+                    reply.error(err_code);
+                    return;
+                }
+                self.update_inode(parent, parent_inode); // 前面 clone 了, 这里写回
+                reply.entry(&TTL, &file_attr, 0);
+            } else {
+                // create_inode 失败 -> no enough space
+                reply.error(ENOSPC);
+            }
+        } else {
+            // parent 不存在 -> No such file or directory
+            reply.error(ENOENT);
+        }
+    }
+
+    fn mkdir(
+        &mut self,
+        req: &Request<'_>,
+        parent: u64,
+        name: &OsStr,
+        mode: u32,
+        _umask: u32, // umask 应该也是用不到的
+        reply: ReplyEntry,
+    ) {
+        if let Some(parent_inode) = self.get_inode(parent as usize) {
+            // 无权限创建 -> EACCES
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                W_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            // parent 不是 IFDIR -> Not a directory
+            if !parent_inode.is_dir() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            // 文件名长度超过 255 -> filename too long
+            if name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            let mut parent_inode = parent_inode.clone();
+            // 已经存在 -> File exists
+            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 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(
+                    parent as usize,
+                    &mut parent_inode,
+                    child_inode_index,
+                    name,
+                    child_inode.mode.into(),
+                ) {
+                    reply.error(err_code);
+                    return;
+                }
+                self.update_inode(parent as usize, parent_inode); // 前面 clone 了, 这里写回
+                reply.entry(&TTL, &file_attr, 0);
+            } else {
+                // create_inode 失败 -> no enough space
+                reply.error(ENOSPC);
+            }
+        } else {
+            // parent 不存在 -> No such file or directory
+            reply.error(ENOENT);
+        }
+    }
+
+    fn unlink(&mut self, req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEmpty) {
+        debug!("unlink(parent: {:#x?}, name: {:?})", parent, name,);
+        if let Some(parent_inode) = self.get_inode(parent as usize) {
+            // 无权限删除 -> EACCES
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                W_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            // parent 不是 dir -> ENOTDIR
+            if !parent_inode.is_dir() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            // 文件名长度超过 255 -> filename too long
+            if name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            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 as usize, &parent_inode, name)
+            {
+                let inode_index = inode_index as usize;
+
+                match inode.file_type() {
+                    FileType::RegularFile => {
+                        inode.n_links -= 1;
+                        if inode.n_links == 0 {
+                            // n_links == 0 -> 整个 inode 都要删除掉
+                            match self.remove_file(inode_index) {
+                                Ok(flag) => debug!("  unlink {}", flag),
+                                Err(err_code) => {
+                                    reply.error(err_code);
+                                    return;
+                                }
+                            }
+                        } else {
+                            // n_links > 0 -> 只是移除了一个 hard link, 将改动写回
+                            self.update_inode(inode_index, inode);
+                        }
+                    }
+                    FileType::Symlink => {}
+                    FileType::Directory => {
+                        reply.error(EISDIR);
+                        return;
+                    }
+                    _ => {
+                        // Not implemented!
+                        reply.error(EIO);
+                        return;
+                    }
+                }
+
+                // 删除 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);
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn rmdir(&mut self, req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEmpty) {
+        debug!("rmdir(parent: {:#x?}, name: {:?}", parent, name,);
+        if let Some(parent_inode) = self.get_inode(parent as usize) {
+            // 无权限删除 -> EACCES
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                W_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            // parent 不是 dir -> ENOTDIR
+            if !parent_inode.is_dir() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            // 文件名长度超过 255 -> filename too long
+            if name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            let mut parent_inode = parent_inode.clone();
+            // 不存在 -> No such file or directory
+            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
+                if inode.is_file() {
+                    reply.error(ENOTDIR);
+                    return;
+                }
+
+                // 一定有 . 和 .. 所以 size == 2 就是空目录
+                // 目录非空 -> ENOTEMPTY
+                if inode.size > 2 {
+                    reply.error(ENOTEMPTY);
+                    return;
+                }
+
+                // directory 没有 hard link, 删了就是删了
+                match self.remove_dir(inode_index) {
+                    Ok(flag) => debug!("  rmdir {}", flag),
+                    Err(err_code) => {
+                        reply.error(err_code);
+                        return;
+                    }
+                }
+
+                // 删除 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);
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn symlink(
+        &mut self,
+        req: &Request<'_>,
+        parent: u64,
+        link_name: &OsStr,
+        target: &Path,
+        reply: ReplyEntry,
+    ) {
+        debug!(
+            "symlink(parent: {}, name: {:?}, target: {:?})",
+            parent, link_name, target
+        );
+        let parent = parent as usize;
+
+        // let root_inode_index = 1usize;
+        // if let Some(root_inode) = self.get_inode(root_inode_index) {
+        //     let mut curr_inode_index = root_inode_index;
+        //     let mut curr_inode = root_inode.clone();
+        //     for segment in target.iter() {
+        //         match self.lookup_name(curr_inode_index, &curr_inode, segment) {
+        //             Ok((next_inode_index, _, next_inode)) => {
+        //                 curr_inode_index = next_inode_index as usize;
+        //                 curr_inode = next_inode;
+        //             }
+        //             Err(err_code) => {
+        //                 reply.error(err_code);
+        //                 return;
+        //             }
+        //         }
+        //     }
+        // } else {
+        //     reply.error(EIO);
+        //     return;
+        // }
+
+        if let Some(parent_inode) = self.get_inode(parent) {
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                W_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            if !parent_inode.is_dir() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            if link_name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            let target = target.as_os_str();
+            let mut parent_inode = parent_inode.clone();
+            if self.lookup_name(parent, &parent_inode, link_name).is_ok() {
+                reply.error(EEXIST);
+                return;
+            }
+
+            if let Some((child_inode_index, child_inode)) =
+                self.create_symlink(0o777, req.uid(), req.gid(), 0)
+            {
+                let mut child_inode = child_inode.clone();
+                child_inode.size = target.len() as u32;
+                if target.len() < 60 {
+                    debug!("create_symlink: target length < 60, allocating in 'direct' section.");
+                    let target_path = target.as_bytes();
+                    let copy_dst = unsafe {
+                        let dst = (&mut child_inode.direct) as *mut u32 as *mut u8;
+                        slice::from_raw_parts_mut(dst, target_path.len())
+                    };
+                    copy_dst.copy_from_slice(target_path);
+                } else {
+                    debug!("create_symlink: target length >= 60, using original layout.");
+                    let mut write_ptr = 0usize;
+                    while write_ptr < target.len() {
+                        let block_index = write_ptr / BLOCK_SIZE;
+                        let offset = write_ptr % BLOCK_SIZE;
+
+                        let write_length_within_block =
+                            if BLOCK_SIZE - offset < target.len() - write_ptr {
+                                BLOCK_SIZE - offset
+                            } else {
+                                target.len() - write_ptr
+                            };
+
+                        if let Some(block) =
+                            self.access_block_mut::<DataBlock>(&child_inode, block_index)
+                        {
+                            block.block.0[offset..offset + write_length_within_block]
+                                .copy_from_slice(
+                                    &target.as_bytes()
+                                        [write_ptr..write_ptr + write_length_within_block],
+                                );
+                            write_ptr += write_length_within_block;
+                        } else {
+                            if let Some((_block_index, block_index_within_inode)) =
+                                self.allocate_block_for(&mut child_inode)
+                            {
+                                let block = self
+                                    .access_block_mut::<DataBlock>(
+                                        &child_inode,
+                                        block_index_within_inode,
+                                    )
+                                    .unwrap();
+                                block.block.0[offset..offset + write_length_within_block]
+                                    .copy_from_slice(
+                                        &target.as_bytes()
+                                            [write_ptr..write_ptr + write_length_within_block],
+                                    );
+                                write_ptr += write_length_within_block;
+                            } else {
+                                reply.error(ENOSPC);
+                                return;
+                            }
+                        }
+                    }
+                }
+
+                let file_attr = to_fileattr(child_inode_index, &child_inode);
+                self.update_inode(child_inode_index, child_inode);
+
+                if let Err(err_code) = self.add_direntry(
+                    parent,
+                    &mut parent_inode,
+                    child_inode_index,
+                    link_name,
+                    from_filetype(FileType::Symlink),
+                ) {
+                    reply.error(err_code);
+                    return;
+                }
+                self.update_inode(parent, parent_inode);
+                reply.entry(&TTL, &file_attr, 0);
+            } else {
+                reply.error(ENOSPC);
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn rename(
+        &mut self,
+        req: &Request<'_>,
+        parent: u64,
+        name: &OsStr,
+        new_parent: u64,
+        new_name: &OsStr,
+        flags: u32,
+        reply: ReplyEmpty,
+    ) {
+        debug!(
+            "rename(parent: {}, name: {:?}, new_parent: {}, new_name: {:?})",
+            parent, name, new_parent, new_name
+        );
+
+        let parent = parent as usize;
+        let new_parent = new_parent as usize;
+        if let Some(parent_inode) = self.get_inode(parent) {
+            if !check_access(
+                req.uid(),
+                req.gid(),
+                parent_inode.uid,
+                parent_inode.gid,
+                parent_inode.mode,
+                R_OK,
+            ) {
+                reply.error(EACCES);
+                return;
+            }
+
+            if name.len() > 255 {
+                reply.error(ENAMETOOLONG);
+                return;
+            }
+
+            let mut parent_inode = parent_inode.clone();
+            match self.lookup_name(parent, &parent_inode, name) {
+                Ok((inode_index, entry_index, inode)) => {
+                    if let Some(new_parent_inode) = self.get_inode(new_parent) {
+                        if !check_access(
+                            req.uid(),
+                            req.gid(),
+                            new_parent_inode.uid,
+                            new_parent_inode.gid,
+                            new_parent_inode.mode,
+                            W_OK,
+                        ) {
+                            reply.error(EACCES);
+                            return;
+                        }
+                        if new_name.len() > 255 {
+                            reply.error(ENAMETOOLONG);
+                            return;
+                        }
+
+                        let mut new_parent_inode = new_parent_inode.clone();
+                        match self.lookup_name(new_parent, &new_parent_inode, new_name) {
+                            Ok((new_inode_index, new_entry_index, new_inode)) => {
+                                // 新文件存在
+                                if flags & RENAME_NOREPLACE != 0 { // 指定 noreplace 之后不允许覆盖文件
+                                    reply.error(EEXIST);
+                                    return;
+                                }
+                                if flags & RENAME_EXCHANGE != 0 { // 交换两个文件
+                                    if let Err(err_code) = self.exchange_direntry(
+                                        parent,
+                                        &mut parent_inode,
+                                        name,
+                                        new_parent,
+                                        &mut new_parent_inode,
+                                        new_name
+                                    ) {
+                                        reply.error(err_code);
+                                        return;
+                                    }
+                                } else { // 用新文件替换旧文件
+                                    let dir_entry = self.get_direntry_by_name(parent, &parent_inode, name)
+                                        .unwrap();
+                                    if let Err(err_code) = self.remove_direntry(parent, &mut parent_inode, name, entry_index) {
+                                        reply.error(err_code);
+                                        return;
+                                    }
+                                    if let Err(err_code) = self.remove_direntry(new_parent, &mut new_parent_inode, new_name, new_entry_index) {
+                                        reply.error(err_code);
+                                        return;
+                                    }
+                                    if let Err(err_code) = self.add_direntry_2(new_parent, &mut new_parent_inode, new_name, dir_entry) {
+                                        reply.error(err_code);
+                                        return;
+                                    }
+                                }
+                                reply.ok();
+                            },
+                            Err(ENOENT) => { // 新文件不存在, 删除旧的创建新的
+                                let dir_entry = self.get_direntry_by_name(parent, &parent_inode, name)
+                                    .unwrap();
+                                if let Err(err_code) = self.remove_direntry(parent, &mut parent_inode, name, entry_index) {
+                                    reply.error(err_code);
+                                    return;
+                                }
+                                if let Err(err_code) = self.add_direntry_2(new_parent, &mut new_parent_inode, new_name, dir_entry) {
+                                    reply.error(err_code);
+                                    return;
+                                }
+                                reply.ok();
+                            },
+                            Err(err_code) => {
+                                // 其他 Err code
+                                reply.error(err_code);
+                                return;
+                            }
+                        }
+                    } else {
+                        reply.error(ENOENT);
+                    }
+                },
+                Err(err_code) => {
+                    reply.error(err_code);
+                    return;
+                }
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn open(&mut self, req: &Request<'_>, ino: u64, flags: i32, reply: ReplyOpen) {
+        debug!("open(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(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);
+            }
+        }
+    }
+
+    // read [offset, offset + size)
+    // - EOF < offset + size -> return EOF - offset
+    // - EOF > offset + size -> return size
+    fn read(
+        &mut self,
+        req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        offset: i64,
+        size: u32,
+        _flags: i32,
+        _lock_owner: Option<u64>, // 用不到!
+        reply: ReplyData,
+    ) {
+        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() {
+                reply.error(EISDIR);
+                return;
+            }
+            if !check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, R_OK) {
+                reply.error(EACCES);
+                return;
+            }
+            debug!("reading inode {:#x} (offset {} size {})", ino, offset, size);
+
+            if offset as u32 >= inode.size {
+                // offset 在 EOF 后面, 直接返回一个 0 长度的空 buffer
+                reply.data(&Vec::new());
+                return;
+            }
+
+            // let read_length = size.min(inode.size.saturating_sub(offset as u32)) as usize;
+            // 这和下面那个是等同的但是不利于让人看懂……
+            let read_length = if offset as u32 + size <= inode.size {
+                size // 没有越过 EOF, 读取 size 个 byte
+            } else {
+                inode.size - offset as u32 // 越过了 EOF, 读取 inode.size - offset 个 byte
+            } as usize;
+
+            let mut read_buffer = vec![0u8; read_length];
+            let mut read_ptr = 0usize;
+
+            let inode = inode.clone();
+
+            while read_ptr < read_length {
+                let current_point = offset as usize + read_ptr;
+                let current_block_index = current_point / BLOCK_SIZE;
+                let current_offset = current_point % BLOCK_SIZE;
+
+                let read_length_within_block =
+                    if BLOCK_SIZE - current_offset < read_length - read_ptr {
+                        BLOCK_SIZE - current_offset // 可以读到 block 最后
+                    } else {
+                        read_length - read_ptr // 读到中途会停下来
+                    };
+
+                if let Some(block) = self.access_block::<DataBlock>(&inode, current_block_index) {
+                    (&mut read_buffer[read_ptr..read_ptr + read_length_within_block])
+                        .copy_from_slice(
+                            &block.block.0
+                                [current_offset..current_offset + read_length_within_block],
+                        );
+                    read_ptr += read_length_within_block;
+                } else {
+                    reply.error(EIO);
+                    return;
+                }
+            }
+
+            reply.data(&read_buffer);
+        }
+    }
+
+    // 写了多少就返回多少
+    fn write(
+        &mut self,
+        req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        offset: i64,
+        data: &[u8],
+        _write_flags: u32,
+        _flags: i32,
+        _lock_owner: Option<u64>,
+        reply: ReplyWrite,
+    ) {
+        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() {
+                reply.error(EISDIR);
+                return;
+            }
+            if !check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, W_OK) {
+                reply.error(EACCES);
+                return;
+            }
+            debug!(
+                "writing inode {:#x} (offset {} size {})",
+                ino,
+                offset,
+                data.len()
+            );
+            let write_length = data.len();
+            let mut write_ptr = 0usize;
+
+            let mut inode = inode.clone();
+
+            while write_ptr < write_length {
+                let current_point = offset as usize + write_ptr;
+                let current_block_index = current_point / BLOCK_SIZE;
+                let current_offset = current_point % BLOCK_SIZE;
+
+                let write_length_within_block =
+                    if BLOCK_SIZE - current_offset < write_length - write_ptr {
+                        BLOCK_SIZE - current_offset // 可以写满 block
+                    } else {
+                        write_length - write_ptr // 写完 buffer 就停下来
+                    };
+
+                // 当前块已分配, 直接往里写
+                if let Some(block) = self.access_block_mut::<DataBlock>(&inode, current_block_index)
+                {
+                    debug!(
+                        "writing {} bytes in block {} within inode",
+                        write_length_within_block, current_block_index
+                    );
+                    (block.block.0[current_offset..current_offset + write_length_within_block])
+                        .copy_from_slice(&data[write_ptr..write_ptr + write_length_within_block]);
+                    write_ptr += write_length_within_block;
+                } else {
+                    // 当前块未分配，尝试分配
+                    if let Some((block_index, block_index_within_inode)) =
+                        self.allocate_block_for(&mut inode)
+                    {
+                        debug!("writing {} bytes in allocated block {} within inode, block index is {}", write_length_within_block, block_index_within_inode, block_index);
+                        // 能分配, 往里写
+                        let block = self
+                            .access_block_mut::<DataBlock>(&inode, block_index_within_inode)
+                            .unwrap();
+                        (block.block.0[current_offset..current_offset + write_length_within_block])
+                            .copy_from_slice(
+                                &data[write_ptr..write_ptr + write_length_within_block],
+                            );
+                        write_ptr += write_length_within_block;
+                    } else {
+                        // 分配不了, 没空间了
+                        break;
+                    }
+                }
+            }
+
+            inode.size = inode.size.max(offset as u32 + write_length as u32);
+            self.update_inode(ino as usize, inode);
+            reply.written(write_length as u32);
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    fn release(
+        &mut self,
+        _req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        _flags: i32,
+        _lock_owner: Option<u64>,
+        _flush: bool,
+        reply: ReplyEmpty,
+    ) {
+        debug!("release(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 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(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 参数
+        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() {
+                reply.error(ENOTDIR);
+                return;
+            }
+
+            if !check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, R_OK) {
+                reply.error(EACCES);
+                return;
+            }
+
+            debug!(
+                "reading dir entries from inode {:#x} with offset {}",
+                ino, offset
+            );
+            let inode = inode.clone();
+
+            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 + 1,
+                    to_filetype(dir_entry.file_type).expect("not 0x0!"),
+                    name,
+                ) {
+                    break;
+                }
+            }
+
+            reply.ok();
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+
+    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::access(ino: {}, mask: {})", ino, mask);
+
+        if let Some(inode) = self.get_inode(ino as usize) {
+            if mask == libc::F_OK // 只要检查是否存在
+                || check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, mask)
+            // 需要检查 rwx 权限
+            {
+                reply.ok();
+            } else {
+                reply.error(EACCES);
+            }
+        } else {
+            reply.error(ENOENT);
+        }
+    }
+}
diff --git a/ayafs/src/main.rs b/ayafs/src/main.rs
new file mode 100644
index 0000000..db4a017
--- /dev/null
+++ b/ayafs/src/main.rs
@@ -0,0 +1,171 @@
+mod block_device;
+mod disk;
+mod filesystem;
+mod memory;
+mod tests;
+mod utils;
+
+use clap::Parser;
+use fuser::MountOption;
+use indexmap::IndexMap;
+use log::{debug, LevelFilter};
+use lru::LruCache;
+use std::collections::HashMap;
+use std::ffi::OsString;
+use std::num::NonZeroUsize;
+use std::path::PathBuf;
+use std::sync::atomic::AtomicU64;
+use std::sync::Arc;
+use std::time::Duration;
+
+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;
+use disk::block::DataBlock;
+use disk::inode::INODE_SIZE;
+use users::{get_current_gid, get_current_uid};
+use crate::block_device::disk::Disk;
+
+#[derive(Parser, Debug)]
+#[command(author, version, about)]
+struct Args {
+    mount_point: Option<String>,
+    #[arg(short, action = clap::ArgAction::Count)]
+    verbosity: u8,
+    #[arg(long)]
+    auto_unmount: bool,
+    #[arg(long)]
+    allow_root: bool,
+}
+
+const TTL: Duration = Duration::new(0, 0);
+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 AyaFS {
+    device: Arc<dyn BlockDevice>,
+    data_bitmap: Bitmap,
+    inode_bitmap: Bitmap,
+    inode_start_block: usize,
+    data_start_block: usize,
+
+    next_file_handle: AtomicU64,
+    // file descriptor -> (inode index, read, write)
+    file_handle_map: HashMap<u64, (usize, bool, bool)>,
+
+    // inode index -> (index aware) hashmap that maps dir entry name to inode index
+    dir_entry_map: LruCache<usize, IndexMap<OsString, DirectoryEntry>>,
+
+    cached_inodes: BlockCache<InodeBlock>,
+    cached_blocks: BlockCache<DataBlock>,
+}
+
+impl AyaFS {
+    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!("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 mut data_bitmap = Bitmap::new(1, data_bitmap_block_number, device.clone());
+        let _ = data_bitmap.allocate().unwrap(); // data block 0 is not usable
+        let mut inode_bitmap = Bitmap::new(
+            data_bitmap_block_number + 1,
+            inode_bitmap_block_number,
+            device.clone(),
+        );
+        let _ = inode_bitmap.allocate().unwrap(); // inode block 0 is not usable
+
+        let mut fs = Self {
+            device: device.clone(),
+            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,
+
+            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),
+        };
+
+        fs.create_directory(0o755, get_current_uid(), get_current_gid(), 0, None);
+
+        fs
+    }
+}
+
+fn main() {
+    let args = Args::parse();
+    let mount_point = args.mount_point.unwrap();
+    let verbosity = args.verbosity;
+    let log_level = match verbosity {
+        0 => LevelFilter::Error,
+        1 => LevelFilter::Warn,
+        2 => LevelFilter::Info,
+        3 => LevelFilter::Debug,
+        _ => LevelFilter::Trace,
+    };
+    env_logger::builder()
+        .filter_level(log_level)
+        .init();
+    let options = vec![
+        // MountOption::RO,
+        MountOption::FSName("hello".to_string()),
+        MountOption::AutoUnmount,
+        MountOption::AllowRoot,
+    ];
+    let disk = Arc::new(Disk::new(PathBuf::from("/dev/nvme0n1p4")));
+    // let disk = Arc::new(MemoryDisk::new(16384));
+    let filesystem = AyaFS::new(disk, 7864320);
+
+    fuser::mount2(filesystem, mount_point, &options).unwrap();
+}
diff --git a/ayafs/src/memory/cached_block.rs b/ayafs/src/memory/cached_block.rs
new file mode 100644
index 0000000..c3d0338
--- /dev/null
+++ b/ayafs/src/memory/cached_block.rs
@@ -0,0 +1,180 @@
+use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use crate::disk::block::Block;
+use crate::AyaFS;
+use lru::LruCache;
+use std::num::NonZeroUsize;
+use std::sync::Arc;
+
+#[derive(Clone)]
+pub struct CachedBlock<T: Block> {
+    pub block: T,
+    pub index: usize,
+    pub dirty: bool,
+}
+
+pub fn convert_mut<U: Block, T: Block>(input_block: &mut CachedBlock<U>) -> &mut CachedBlock<T> {
+    let ptr = input_block as *const CachedBlock<U> as *mut u8;
+    let block = ptr.cast::<CachedBlock<T>>();
+    unsafe { &mut *block }
+}
+
+pub fn convert<U: Block, T: Block>(input_block: &CachedBlock<U>) -> &CachedBlock<T> {
+    let ptr = input_block as *const CachedBlock<U> as *mut u8;
+    let block = ptr.cast::<CachedBlock<T>>();
+    unsafe { &*block }
+}
+
+pub(crate) struct BlockCache<T: Block> {
+    device: Arc<dyn BlockDevice>,
+    cache: LruCache<usize, CachedBlock<T>>,
+}
+
+impl<T: Block> BlockCache<T> {
+    pub(crate) fn new(device: Arc<dyn BlockDevice>, cache_size: usize) -> Self {
+        Self {
+            device,
+            cache: LruCache::new(NonZeroUsize::new(cache_size).unwrap()),
+        }
+    }
+
+    pub(crate) fn load_block(&mut self, index: usize) -> bool {
+        if self.cache.contains(&index) == false {
+            let mut buffer = [0u8; BLOCK_SIZE];
+            self.device.read(index, &mut buffer);
+            let block: T = unsafe { std::mem::transmute_copy(&buffer) };
+            let cached_block = CachedBlock {
+                block,
+                index,
+                dirty: false,
+            };
+            if let Some((old_index, old_block)) = self.cache.push(index, cached_block) {
+                assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入
+                if old_block.dirty {
+                    let old_block_ptr = &old_block.block as *const T as *mut u8;
+                    let old_block_buffer =
+                        unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) };
+                    self.device.write(old_index, old_block_buffer);
+                }
+            }
+        }
+        true
+    }
+
+    /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载.
+    /// 这个函数不应该返回 None
+    pub(crate) fn get_block<U: Block>(&mut self, index: usize) -> Option<&CachedBlock<U>> {
+        if !self.cache.contains(&index) {
+            self.load_block(index);
+        }
+        self.cache.get(&index).map(convert::<T, U>)
+    }
+
+    /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载.
+    /// 这个函数不应该返回 None
+    pub(crate) fn get_block_mut<U: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<U>> {
+        if !self.cache.contains(&index) {
+            self.load_block(index);
+        }
+        self.cache.get_mut(&index).map(|block| {
+            block.dirty = true;
+            convert_mut::<T, U>(block)
+        })
+    }
+
+    /// 向 LRU cache 中插入一个全新初始化的 block
+    /// 这个 block 全 0, 而且是 dirty 的, 即使被挤出去也会触发一次落盘
+    pub(crate) fn init_block(&mut self, index: usize) {
+        let allocated_block = CachedBlock {
+            block: T::default(),
+            index,
+            dirty: true,
+        };
+        if let Some((old_index, old_block)) = self.cache.push(index, allocated_block) {
+            if old_block.dirty {
+                let old_block_ptr = &old_block.block as *const T as *mut u8;
+                let old_block_buffer =
+                    unsafe { std::slice::from_raw_parts(old_block_ptr, BLOCK_SIZE) };
+                self.device.write(old_index, old_block_buffer);
+            }
+        }
+    }
+
+    #[allow(unused)]
+    /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+    pub(crate) fn peek_block<U: Block>(&self, index: usize) -> Option<&CachedBlock<U>> {
+        self.cache.peek(&index).map(convert::<T, U>)
+    }
+
+    #[allow(unused)]
+    /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+    pub(crate) fn peek_block_mut<U: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<U>> {
+        self.cache.peek_mut(&index).map(convert_mut::<T, U>)
+    }
+
+    pub(crate) fn update_block<U: Block>(&mut self, block: CachedBlock<U>) -> bool {
+        if self.cache.contains(&block.index) {
+            let mut data_block = convert::<U, T>(&block).clone();
+            data_block.dirty = true; // TODO 需要把显式写回的都标记为 dirty 吗
+            self.cache.push(block.index, data_block);
+            true
+        } else {
+            false
+        }
+    }
+
+    fn pop(&mut self, entry: &usize) -> Option<CachedBlock<T>> {
+        self.cache.pop(entry)
+    }
+}
+
+impl AyaFS {
+    pub(crate) fn init_block(&mut self, index: usize) {
+        self.cached_blocks.init_block(index);
+    }
+
+    pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
+        if self.data_bitmap.query(index) {
+            Some(self.cached_blocks.get_block::<T>(index).unwrap())
+        } else {
+            self.cached_blocks.pop(&index);
+            None
+        }
+        // self.data_bitmap
+        //     .query(index)
+        //     .then(|| self.cached_blocks.get_block::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
+    }
+
+    pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+        if self.data_bitmap.query(index) {
+            Some(self.cached_blocks.get_block_mut::<T>(index).unwrap())
+        } else {
+            self.cached_blocks.pop(&index);
+            None
+        }
+        // self.data_bitmap
+        //     .query(index)
+        //     .then(|| self.cached_blocks.get_block_mut::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
+    }
+
+    #[allow(unused)]
+    pub(crate) fn peek_block<T: Block>(&self, index: usize) -> Option<&CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .then(|| self.cached_blocks.peek_block::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
+    }
+
+    #[allow(unused)]
+    pub(crate) fn peek_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .then(|| self.cached_blocks.peek_block_mut::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
+    }
+
+    pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
+        self.cached_blocks.update_block(block)
+    }
+}
diff --git a/ayafs/src/memory/cached_inode.rs b/ayafs/src/memory/cached_inode.rs
new file mode 100644
index 0000000..2f26dde
--- /dev/null
+++ b/ayafs/src/memory/cached_inode.rs
@@ -0,0 +1,178 @@
+use crate::disk::block::InodeBlock;
+use crate::disk::inode::{Inode, INODE_SIZE};
+use crate::{utils, AyaFS};
+use and_then_some::BoolExt;
+use fuser::FileType;
+use libc::{c_int, EIO, EISDIR, ENOENT, ENOTDIR, ENOTEMPTY};
+
+impl AyaFS {
+    pub(crate) fn create_file(
+        &mut self,
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        flags: u32,
+    ) -> Option<(usize, &Inode)> {
+        self.inode_bitmap.allocate().map(|inode_index| {
+            self.get_inode_mut(inode_index).map(|inode| {
+                *inode = Inode::file(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0);
+            });
+            (inode_index, self.get_inode(inode_index).unwrap())
+        })
+    }
+
+    pub(crate) fn create_symlink(
+        &mut self,
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        flags: u32,
+    ) -> Option<(usize, &Inode)> {
+        self.inode_bitmap.allocate().map(|inode_index| {
+            self.get_inode_mut(inode_index).map(|inode| {
+                *inode = Inode::symlink(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0);
+            });
+            (inode_index, self.get_inode(inode_index).unwrap())
+        })
+    }
+
+    /// 根目录的 parent_inode_number 传入 None, 会直接以自己作为 .. 的 inode number
+    pub(crate) fn create_directory(
+        &mut self,
+        permissions: u16,
+        uid: u32,
+        gid: u32,
+        flags: u32,
+        parent_inode_number: Option<usize>,
+    ) -> 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);
+            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();
+            // 把 inode 放到指定位置
+            self.get_inode_mut(inode_index).map(|inode| {
+                *inode = new_inode;
+            });
+
+            (inode_index, self.get_inode(inode_index).unwrap())
+        })
+    }
+
+    pub(crate) fn remove_file(&mut self, inode_index: usize) -> Result<bool, c_int> {
+        if self.inode_bitmap.query(inode_index) {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            if let Some(cached_block) = self.cached_inodes.get_block::<InodeBlock>(block_index) {
+                let inode = cached_block.block.inodes[offset / INODE_SIZE].clone();
+                match inode.file_type() {
+                    FileType::RegularFile => self.deallocate_all_blocks_for(&inode).unwrap(),
+                    FileType::Symlink => {
+                        if inode.size >= 60 {
+                            self.deallocate_all_blocks_for(&inode).unwrap();
+                        }
+                    }
+                    FileType::Directory => return Err(EISDIR),
+                    _ => return Err(EIO),
+                }
+            }
+            self.inode_bitmap.deallocate(inode_index);
+            Ok(true)
+        } else {
+            Err(ENOENT)
+        }
+    }
+
+    // 要删除的 inode 一定得是空的
+    pub(crate) fn remove_dir(&mut self, inode_index: usize) -> Result<bool, c_int> {
+        if self.inode_bitmap.query(inode_index) {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            if let Some(cached_block) = self.cached_inodes.get_block::<InodeBlock>(block_index) {
+                let inode = &cached_block.block.inodes[offset / INODE_SIZE].clone();
+                if !inode.is_dir() {
+                    // 不是 dir -> ENOTDIR
+                    return Err(ENOTDIR);
+                }
+                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)
+        }
+    }
+
+    pub(crate) fn update_inode(&mut self, inode_index: usize, inode: Inode) -> bool {
+        if self.inode_bitmap.query(inode_index) {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            if let Some(cached_block) = self.cached_inodes.get_block_mut::<InodeBlock>(block_index)
+            {
+                cached_block.block.inodes[offset / INODE_SIZE] = inode;
+            }
+            true
+        } else {
+            false
+        }
+    }
+
+    pub(crate) fn get_inode(&mut self, inode_index: usize) -> Option<&Inode> {
+        self.inode_bitmap.query(inode_index).and_then(|| {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            // debug!("get_inode(inode_index: {}) -> block_index: {}, offset: {}", inode_index, block_index, offset);
+            self.cached_inodes
+                .get_block::<InodeBlock>(block_index)
+                .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
+        })
+    }
+
+    pub(crate) fn get_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> {
+        self.inode_bitmap.query(inode_index).and_then(|| {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            // debug!("get_inode_mut(inode_index: {}) -> block_index: {}, offset: {}", inode_index, block_index, offset);
+            self.cached_inodes
+                .get_block_mut::<InodeBlock>(block_index)
+                .map(|cached_block| {
+                    cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏
+                    &mut cached_block.block.inodes[offset / INODE_SIZE]
+                })
+        })
+    }
+
+    #[allow(unused)]
+    pub(crate) fn peek_inode(&self, inode_index: usize) -> Option<&Inode> {
+        self.inode_bitmap.query(inode_index).and_then(|| {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            self.cached_inodes
+                .peek_block::<InodeBlock>(block_index)
+                .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
+        })
+    }
+
+    #[allow(unused)]
+    pub(crate) fn peek_inode_mut(&mut self, inode_index: usize) -> Option<&mut Inode> {
+        self.inode_bitmap.query(inode_index).and_then(|| {
+            let (block_index, offset) = self.locate_inode(inode_index);
+            self.cached_inodes
+                .peek_block_mut::<InodeBlock>(block_index)
+                .map(|cached_block| {
+                    cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏
+                    &mut cached_block.block.inodes[offset / INODE_SIZE]
+                })
+        })
+    }
+}
diff --git a/ayafs/src/memory/dir_entry.rs b/ayafs/src/memory/dir_entry.rs
new file mode 100644
index 0000000..c013e1e
--- /dev/null
+++ b/ayafs/src/memory/dir_entry.rs
@@ -0,0 +1,305 @@
+use crate::disk::block::{DirectoryBlock, DirectoryEntry};
+use crate::disk::inode::Inode;
+use crate::AyaFS;
+use indexmap::IndexMap;
+use libc::{c_int, ENOENT, ENOSPC};
+use log::debug;
+use std::ffi::{OsStr, OsString};
+use std::os::unix::ffi::OsStrExt;
+use indexmap::map::Entry::Occupied;
+
+impl AyaFS {
+    pub(crate) fn init_direntry_map(&mut self, index: usize) {
+        let direntry_map: IndexMap<OsString, DirectoryEntry> = 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<OsString, DirectoryEntry> = 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::<DirectoryBlock>(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<OsString, DirectoryEntry>,
+    ) -> 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::<DirectoryBlock>(parent_inode, block_index_within_inode) {
+                Some(directory_block) => {
+                    directory_block.block.allocate(entry_index_within_block);
+                    directory_block.block.entries[entry_index_within_block] = dir_entry;
+                }
+                None => {
+                    return Err(ENOENT);
+                }
+            }
+        }
+        Ok(())
+    }
+
+    pub(crate) fn exchange_direntry<T: AsRef<OsStr>>(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &mut Inode,
+        name: T,
+        new_parent_index: usize,
+        new_parent_inode: &mut Inode,
+        new_name: T,
+    ) -> Result<(), c_int> {
+        self.load_direntry_map(parent_index, parent_inode)?;
+        self.load_direntry_map(new_parent_index, new_parent_inode)?;
+
+        let dir_entry = self.dir_entry_map
+            .get(&parent_index)
+            .ok_or(ENOENT)?
+            .get(name.as_ref())
+            .cloned()
+            .ok_or(ENOENT)?;
+        let new_dir_entry = self.dir_entry_map
+            .get(&new_parent_index)
+            .ok_or(ENOENT)?
+            .get(new_name.as_ref())
+            .cloned()
+            .ok_or(ENOENT)?;
+
+        let name: &OsStr = name.as_ref();
+        let new_name: &OsStr = new_name.as_ref();
+
+        self.dir_entry_map
+            .get_mut(&parent_index)
+            .map(|dir_entry_map| {
+                if let Occupied(mut entry) = dir_entry_map.entry(name.to_os_string()) {
+                    *entry.get_mut() = new_dir_entry.clone();
+                }
+            })
+            .ok_or(ENOENT)?;
+        self.dir_entry_map
+            .get_mut(&new_parent_index)
+            .map(|new_dir_entry_map| {
+                if let Occupied(mut entry) = new_dir_entry_map.entry(new_name.to_os_string()) {
+                    *entry.get_mut() = dir_entry.clone();
+                }
+            })
+            .ok_or(ENOENT)?;
+
+        Ok(())
+    }
+
+    /// 删除第 entry_index 个 dir entry
+    pub(crate) fn remove_direntry<T: AsRef<OsStr>>(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &mut Inode,
+        name: T,
+        _entry_index: u32,
+    ) -> Result<(), c_int> {
+        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.as_ref()).is_some() {
+                Ok(())
+            } else {
+                Err(ENOENT)
+            }
+        } else {
+            Err(ENOENT)
+        }
+    }
+
+    pub(crate) fn add_direntry_2<T: AsRef<OsStr>>(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &mut Inode,
+        child_inode_name: T,
+        dir_entry: DirectoryEntry,
+    ) -> Result<u32, c_int> {
+        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 (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)
+        }
+    }
+
+    pub(crate) fn add_direntry<T: AsRef<OsStr>>(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &mut Inode,
+        child_inode_index: usize,
+        child_inode_name: T,
+        file_type: u8,
+    ) -> Result<u32, c_int> {
+        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,
+            };
+
+            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)
+        }
+    }
+
+    pub(crate) fn get_direntry_by_name<T: AsRef<OsStr>>(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &Inode,
+        name: T,
+    ) -> Result<DirectoryEntry, c_int> {
+        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: {}, name: {:?}) using hashmap",
+                parent_index, name.as_ref()
+            );
+            dir_entry_map
+                .get(name.as_ref())
+                .cloned()
+                .ok_or(ENOENT)
+        } else {
+            Err(ENOENT)
+        }
+    }
+
+    pub(crate) fn get_direntry(
+        &mut self,
+        parent_index: usize,
+        parent_inode: &Inode,
+        entry_index: u32,
+    ) -> Result<DirectoryEntry, c_int> {
+        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)
+        }
+    }
+
+    /// 返回 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> {
+        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;
+            }
+            Err(ENOENT)
+        }
+    }
+}
diff --git a/ayafs/src/memory/file_handle.rs b/ayafs/src/memory/file_handle.rs
new file mode 100644
index 0000000..c821619
--- /dev/null
+++ b/ayafs/src/memory/file_handle.rs
@@ -0,0 +1,15 @@
+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
+    }
+}
diff --git a/ayafs/src/memory/mod.rs b/ayafs/src/memory/mod.rs
new file mode 100644
index 0000000..d1f1ab8
--- /dev/null
+++ b/ayafs/src/memory/mod.rs
@@ -0,0 +1,6 @@
+/// In-memory data structures and logic.
+/// This is where the crucial block and inode methods presented to upper calls implemented.
+pub mod cached_block;
+pub mod cached_inode;
+mod dir_entry;
+mod file_handle;
diff --git a/ayafs/src/tests/bitmap.rs b/ayafs/src/tests/bitmap.rs
new file mode 100644
index 0000000..1a43f09
--- /dev/null
+++ b/ayafs/src/tests/bitmap.rs
@@ -0,0 +1,38 @@
+use crate::tests::common;
+use indexmap::IndexMap;
+
+#[test]
+fn test_allocate() {
+    let mut fs = common::setup();
+    for _ in 0..10 {
+        fs.data_bitmap.allocate().unwrap();
+    }
+    assert!(fs.data_bitmap.deallocate(5));
+    assert_eq!(fs.data_bitmap.allocate().unwrap(), 5);
+    assert_eq!(fs.data_bitmap.allocate().unwrap(), 11);
+}
+
+#[test]
+fn test_query() {
+    let mut fs = common::setup();
+    for _ in 0..10 {
+        fs.data_bitmap.allocate().unwrap();
+    }
+    assert_eq!(fs.data_bitmap.query(0), false);
+    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<i32, i32> = 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/ayafs/src/tests/block_cache.rs b/ayafs/src/tests/block_cache.rs
new file mode 100644
index 0000000..52117b9
--- /dev/null
+++ b/ayafs/src/tests/block_cache.rs
@@ -0,0 +1,245 @@
+use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock};
+use crate::disk::inode::InodeMode;
+use crate::tests::common;
+
+#[test]
+fn test_basic_lru() {
+    let mut fs = common::setup();
+
+    let v: Vec<usize> = (1..=256)
+        .map(|_| {
+            let index = fs.data_bitmap.allocate().unwrap();
+            fs.get_block::<DataBlock>(index).unwrap();
+            index
+        })
+        .collect();
+    assert!(fs.peek_block::<DataBlock>(v[0]).is_some());
+
+    for i in 0..256 {
+        let index = fs.data_bitmap.allocate().unwrap();
+        fs.get_block::<DataBlock>(index).unwrap();
+        assert!(fs.peek_block::<DataBlock>(v[i]).is_none());
+    }
+}
+
+#[test]
+fn test_inode_allocation() {
+    let mut fs = common::setup();
+
+    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 {
+        fs.allocate_block_for(&mut inode).unwrap();
+        assert!(fs.data_bitmap.query(inode.direct[i as usize] as usize))
+    }
+
+    for _i in 0..INDIRECT_NUMBER {
+        fs.allocate_block_for(&mut inode).unwrap();
+    }
+
+    println!("single indirect is {}", inode.single_indirect);
+    println!("double indirect is {}", inode.double_indirect);
+    println!("triple indirect is {}", inode.triple_indirect);
+
+    let indirect_block = fs
+        .peek_block::<IndirectBlock>(inode.single_indirect as usize)
+        .unwrap();
+    for entry in indirect_block.block.entries {
+        assert_ne!(entry, 0);
+        assert!(fs.data_bitmap.query(entry as usize));
+    }
+
+    assert_eq!(fs.data_bitmap.query(inode.double_indirect as usize), false);
+    assert_eq!(fs.data_bitmap.query(inode.triple_indirect as usize), false);
+
+    for _i in 0..INDIRECT_NUMBER {
+        fs.allocate_block_for(&mut inode).unwrap();
+    }
+
+    let double_indirect = inode.double_indirect;
+    println!(
+        "double indirect is {} after allocation",
+        inode.double_indirect
+    );
+
+    fs.update_inode(inode_index, inode);
+
+    assert!(fs.data_bitmap.query(double_indirect as usize));
+}
+
+#[test]
+fn test_inode_deallocation() {
+    let mut fs = common::setup();
+
+    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());
+        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!("single indirect is {}", inode.single_indirect);
+    println!("double indirect is {}", inode.double_indirect);
+    println!("triple indirect is {}", inode.triple_indirect);
+
+    assert!(fs.data_bitmap.query(inode.double_indirect as usize));
+
+    for i in 0..INDIRECT_NUMBER + 5 {
+        println!(
+            "Deallocated {}",
+            fs.deallocate_block_for(&mut inode).unwrap()
+        );
+    }
+
+    println!("single indirect is {}", inode.single_indirect);
+    println!("double indirect is {}", inode.double_indirect);
+    println!("triple indirect is {}", inode.triple_indirect);
+
+    assert_eq!(fs.data_bitmap.query(inode.double_indirect as usize), false);
+
+    fs.update_inode(inode_index, inode);
+}
+
+#[test]
+fn test_multiple_inode_allocation() {
+    let mut fs = common::setup();
+
+    let (inode_index_1, inode_1) = fs.create_directory(0o755, 0, 0, 0, None).unwrap();
+    let mut inode_1 = inode_1.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 {}",
+            fs.allocate_block_for(&mut inode_1).unwrap(),
+            inode_index_1
+        );
+        println!(
+            "Allocated {:?} in inode {}",
+            fs.allocate_block_for(&mut inode_2).unwrap(),
+            inode_index_2
+        );
+    }
+
+    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!(
+            "Deallocated {} in inode {}",
+            fs.deallocate_block_for(&mut inode_1).unwrap(),
+            inode_index_1
+        );
+        println!(
+            "Allocated {:?} in inode {}",
+            fs.allocate_block_for(&mut inode_3).unwrap(),
+            inode_index_3
+        );
+    }
+
+    for _i in 0..DIRECT_NUMBER {
+        println!(
+            "Deallocated {} in inode {}",
+            fs.deallocate_block_for(&mut inode_1).unwrap(),
+            inode_index_1
+        );
+    }
+
+    assert!(fs.deallocate_block_for(&mut inode_1).is_none());
+
+    println!(
+        "single indirect is {} for {}",
+        inode_1.single_indirect, inode_index_1
+    );
+    println!(
+        "double indirect is {} for {}",
+        inode_1.double_indirect, inode_index_1
+    );
+    println!(
+        "single indirect is {} for {}",
+        inode_2.single_indirect, inode_index_2
+    );
+    println!(
+        "double indirect is {} for {}",
+        inode_2.double_indirect, inode_index_2
+    );
+    println!(
+        "single indirect is {} for {}",
+        inode_3.single_indirect, inode_index_3
+    );
+    println!(
+        "double indirect is {} for {}",
+        inode_3.double_indirect, inode_index_3
+    );
+
+    assert_eq!(
+        fs.data_bitmap.query(inode_1.single_indirect as usize),
+        false
+    );
+    assert!(fs.data_bitmap.query(inode_2.single_indirect as usize));
+    assert_eq!(
+        fs.data_bitmap.query(inode_2.double_indirect as usize),
+        false
+    );
+    assert!(fs.data_bitmap.query(inode_3.single_indirect as usize));
+    assert_eq!(
+        fs.data_bitmap.query(inode_3.double_indirect as usize),
+        false
+    );
+
+    fs.allocate_block_for(&mut inode_2).unwrap();
+    println!("-----------------");
+    println!(
+        "double indirect is {} for {}",
+        inode_2.double_indirect, inode_index_2
+    );
+
+    assert!(fs.data_bitmap.query(inode_2.double_indirect as usize));
+
+    for _i in 0..DIRECT_NUMBER {
+        fs.allocate_block_for(&mut inode_3).unwrap();
+    }
+    println!("-----------------");
+    println!(
+        "double indirect is {} for {}",
+        inode_3.double_indirect, inode_index_3
+    );
+    assert_eq!(
+        fs.data_bitmap.query(inode_3.double_indirect as usize),
+        false
+    );
+
+    fs.allocate_block_for(&mut inode_3).unwrap();
+    println!("-----------------");
+    println!(
+        "double indirect is {} for {}",
+        inode_3.double_indirect, inode_index_3
+    );
+    assert!(fs.data_bitmap.query(inode_3.double_indirect as usize));
+
+    fs.update_inode(inode_index_1, inode_1);
+    fs.update_inode(inode_index_2, inode_2);
+    fs.update_inode(inode_index_3, inode_3);
+}
diff --git a/ayafs/src/tests/common/mod.rs b/ayafs/src/tests/common/mod.rs
new file mode 100644
index 0000000..3abfcb4
--- /dev/null
+++ b/ayafs/src/tests/common/mod.rs
@@ -0,0 +1,9 @@
+use crate::block_device::memory_disk::MemoryDisk;
+use crate::AyaFS;
+use std::sync::Arc;
+
+#[allow(unused)]
+pub(crate) fn setup() -> AyaFS {
+    let mem_disk = Arc::new(MemoryDisk::new(1059715));
+    AyaFS::new(mem_disk, 1059715)
+}
diff --git a/ayafs/src/tests/mod.rs b/ayafs/src/tests/mod.rs
new file mode 100644
index 0000000..df442c1
--- /dev/null
+++ b/ayafs/src/tests/mod.rs
@@ -0,0 +1,6 @@
+#[cfg(test)]
+mod bitmap;
+mod common;
+
+#[cfg(test)]
+mod block_cache;
diff --git a/ayafs/src/utils/constants.rs b/ayafs/src/utils/constants.rs
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/ayafs/src/utils/constants.rs
@@ -0,0 +1 @@
+
diff --git a/ayafs/src/utils/mod.rs b/ayafs/src/utils/mod.rs
new file mode 100644
index 0000000..468ebdb
--- /dev/null
+++ b/ayafs/src/utils/mod.rs
@@ -0,0 +1,92 @@
+mod constants;
+pub mod permissions;
+
+use crate::block_device::BLOCK_SIZE;
+use crate::disk::inode::{Inode, INODE_SIZE};
+use crate::{AyaFS, INODE_PER_BLOCK};
+use fuser::{FileAttr, FileType};
+use std::time::{Duration, SystemTime, UNIX_EPOCH};
+
+pub(crate) 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(crate) fn from_systime(system_time: SystemTime) -> u32 {
+    system_time
+        .duration_since(UNIX_EPOCH)
+        .expect("How can current time be earlier than UNIX_EPOCH?")
+        .as_secs() as u32
+}
+
+pub(crate) fn to_systime(time: u32) -> SystemTime {
+    UNIX_EPOCH + Duration::from_secs(time as u64)
+}
+
+// File type code, one of:
+// 0x0 	Unknown.
+// 0x1 	Regular file.
+// 0x2 	Directory.
+// 0x3 	Character device file.
+// 0x4 	Block device file.
+// 0x5 	FIFO.
+// 0x6 	Socket.
+// 0x7 	Symbolic link.
+
+pub(crate) fn from_filetype(file_type: FileType) -> u8 {
+    match file_type {
+        FileType::NamedPipe => 0x5,
+        FileType::CharDevice => 0x3,
+        FileType::BlockDevice => 0x4,
+        FileType::Directory => 0x2,
+        FileType::RegularFile => 0x1,
+        FileType::Symlink => 0x7,
+        FileType::Socket => 0x6,
+    }
+}
+
+pub(crate) fn to_filetype(file_type: u8) -> Option<FileType> {
+    match file_type {
+        0x0 => None,
+        0x1 => Some(FileType::RegularFile),
+        0x2 => Some(FileType::Directory),
+        0x3 => Some(FileType::CharDevice),
+        0x4 => Some(FileType::BlockDevice),
+        0x5 => Some(FileType::NamedPipe),
+        0x6 => Some(FileType::Socket),
+        0x7 => Some(FileType::Symlink),
+        _ => panic!("bad filetype"),
+    }
+}
+
+pub(crate) fn to_fileattr(inode_index: usize, inode: &Inode) -> FileAttr {
+    FileAttr {
+        ino: inode_index as u64,
+        size: inode.size as u64,
+        blocks: inode.n_blocks as u64,
+        atime: to_systime(inode.atime),
+        mtime: to_systime(inode.mtime),
+        ctime: to_systime(inode.ctime),
+        crtime: to_systime(inode.crtime),
+        kind: inode.mode.into(),
+        perm: inode.mode.perm(),
+        nlink: inode.n_links as u32,
+        uid: inode.uid,
+        gid: inode.gid,
+        rdev: 0,
+        blksize: BLOCK_SIZE as u32,
+        flags: inode.flags,
+    }
+}
+
+impl AyaFS {
+    /// 输入 inode 编号, 返回它对应的 block number 和 block 内 offset
+    pub(crate) fn locate_inode(&self, inode_index: usize) -> (usize, usize) {
+        let block_number =
+            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)
+    }
+}
diff --git a/ayafs/src/utils/permissions.rs b/ayafs/src/utils/permissions.rs
new file mode 100644
index 0000000..6773511
--- /dev/null
+++ b/ayafs/src/utils/permissions.rs
@@ -0,0 +1,62 @@
+use crate::disk::inode::InodeMode;
+use libc::{F_OK, S_ISGID, S_ISUID, S_IXGRP, X_OK};
+use std::fs::File;
+use std::io::BufRead;
+
+pub(crate) fn get_groups(pid: u32) -> Vec<u32> {
+    let file = File::open(format!("/proc/{pid}/task/{pid}/status"))
+        .expect(format!("pid {pid} incorrect!").as_str());
+    for line in std::io::BufReader::new(file).lines() {
+        let line = line.unwrap();
+        if line.starts_with("Groups:") {
+            return line["Groups: ".len()..]
+                .split(' ')
+                .filter(|x| !x.trim().is_empty())
+                .map(|x| x.parse::<u32>().unwrap())
+                .collect();
+        }
+    }
+
+    Vec::new()
+}
+
+pub(crate) fn clear_suid_sgid(mut mode: InodeMode) -> InodeMode {
+    mode.0 &= !S_ISUID as u16;
+    if mode.0 & S_IXGRP as u16 != 0 {
+        mode.0 &= !S_ISGID as u16;
+    }
+    mode
+}
+
+pub(crate) fn check_access(
+    incoming_uid: u32,
+    incoming_gid: u32,
+    uid: u32,
+    gid: u32,
+    mode: InodeMode,
+    mut mask: i32,
+) -> bool {
+    if mask == F_OK {
+        return true;
+    }
+
+    let perm = i32::from(mode.0);
+    // root
+    if incoming_uid == 0 {
+        // 读写任何东西都是可以的, 执行只有 IXOTH/IXGRP/IXUSR 之一设置才可以
+        mask &= X_OK;
+        mask -= mask & (perm >> 6);
+        mask -= mask & (perm >> 3);
+        mask -= mask & perm;
+        return mask == 0;
+    }
+
+    if incoming_uid == uid {
+        mask -= mask & (perm >> 6);
+    } else if incoming_gid == gid {
+        mask -= mask & (perm >> 3);
+    } else {
+        mask -= mask & perm;
+    }
+    mask == 0
+}