Layer 1 test not passing

15 files changed, 492 insertions, 83 deletions

diff --git a/src/block_device/memory_disk.rs b/src/block_device/memory_disk.rs
index 3876736..0639d3e 100644
--- a/src/block_device/memory_disk.rs
+++ b/src/block_device/memory_disk.rs
@@ -9,9 +9,9 @@ pub struct MemoryDisk {
 }
 
 impl MemoryDisk {
-    pub fn new() -> Self {
+    pub fn new(block_number: usize) -> Self {
         Self {
-            arena: RefCell::new(vec![0u8; BLOCK_SIZE * 16384]),
+            arena: RefCell::new(vec![0u8; BLOCK_SIZE * block_number]),
         }
     }
 }
diff --git a/src/block_device/mod.rs b/src/block_device/mod.rs
index c7e1362..a8fd8b7 100644
--- a/src/block_device/mod.rs
+++ b/src/block_device/mod.rs
@@ -1,6 +1,5 @@
 /// Abstracts for block devices.
 /// Currently only a mock memory disk.
-
 pub mod memory_disk;
 pub const BLOCK_SIZE: usize = 4096;
 pub trait BlockDevice {
diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs
index 291a136..3622e4f 100644
--- a/src/disk/allocation.rs
+++ b/src/disk/allocation.rs
@@ -1,15 +1,16 @@
-use crate::memory::cached_block::convert;
-use crate::disk::data_block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
+use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
 use crate::disk::inode::Inode;
+use crate::memory::cached_block::convert;
 use crate::AyaFS;
 
 impl AyaFS {
     /// 为 Inode 分配新 block, 返回 block 的编号
-    pub(crate) fn allocate_block(&mut self, inode: &mut Inode) -> Option<u32> {
+    pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<u32> {
         // 先看这个 inode 的 direct block 有没有空闲
         for index in inode.direct.iter_mut() {
             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;
                 // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
@@ -23,9 +24,11 @@ impl AyaFS {
                 .data_bitmap
                 .allocate()
                 .expect("No free space for new block") as u32;
+            println!("allocating {} for indirect", inode.single_indirect);
         }
         // 在 indirect block 里尝试分配
         if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) {
+            println!("allocating {} in indirect", block_index);
             inode.n_blocks += 1;
             return Some(block_index);
         }
@@ -36,9 +39,11 @@ impl AyaFS {
                 .data_bitmap
                 .allocate()
                 .expect("No free space for new block") as u32;
+            println!("allocating {} for double indirect", inode.double_indirect);
         }
         // 在 double indirect block 里尝试分配
         if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) {
+            println!("allocating {} in double indirect", block_index);
             inode.n_blocks += 1;
             return Some(block_index);
         }
@@ -49,9 +54,11 @@ impl AyaFS {
                 .data_bitmap
                 .allocate()
                 .expect("No free space for new block") as u32;
+            println!("allocating {} for triple indirect", inode.triple_indirect);
         }
         // 在 double indirect block 里尝试分配
         if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) {
+            println!("allocating {} in triple indirect", block_index);
             inode.n_blocks += 1;
             return Some(block_index);
         }
@@ -61,11 +68,13 @@ impl AyaFS {
     fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
         // 取出 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 entry in indirect_block.block.entries.iter_mut() {
                 if self.data_bitmap.query(*entry as usize) == false {
@@ -130,3 +139,119 @@ impl AyaFS {
         None
     }
 }
+
+impl AyaFS {
+    /// 从 inode 中删去最后一个 block
+    pub(crate) fn deallocate_block(&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
+            .peek_block(triple_indirect_entry)
+            .map(convert::<DataBlock, TripleIndirectBlock>)
+        {
+            for double_indirect_entry in triple_indirect_block
+                .block
+                .double_indirect
+                .into_iter()
+                .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)
+                    {
+                        return Some(block_index); // 成功则直接返回
+                    } else {
+                        // 失败则把这个 double indirect 销毁
+                        self.data_bitmap.deallocate(double_indirect_entry as usize);
+                    }
+                }
+            }
+        }
+        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
+            .peek_block(double_indirect_entry)
+            .map(convert::<DataBlock, DoubleIndirectBlock>)
+        {
+            for indirect_entry in double_indirect_block.block.indirect.into_iter().rev() {
+                // 如果这个位置的 indirect 存在
+                if self.data_bitmap.query(indirect_entry as usize) {
+                    // 尝试从中销毁一个块
+                    if let Some(block_index) = self.deallocate_from_indirect(indirect_entry) {
+                        return Some(block_index); // 成功则直接返回
+                    } else {
+                        // 失败则把这个 indirect 销毁
+                        self.data_bitmap.deallocate(indirect_entry as usize);
+                    }
+                }
+            }
+        }
+        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
+            .peek_block(indirect_entry)
+            .map(convert::<DataBlock, IndirectBlock>)
+        {
+            // 遍历 indirect block 里的每个 block
+            for entry in indirect_block.block.entries.into_iter().rev() {
+                // 如果这个 block 存在, 销毁它
+                if self.data_bitmap.query(entry as usize) {
+                    self.data_bitmap.deallocate(entry as usize);
+                    return Some(entry);
+                }
+            }
+        }
+        None
+    }
+}
diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs
index 64389c2..b68c341 100644
--- a/src/disk/bitmap.rs
+++ b/src/disk/bitmap.rs
@@ -1,5 +1,4 @@
 use crate::block_device::{BlockDevice, BLOCK_SIZE};
-use std::cell::RefCell;
 use std::sync::Arc;
 
 pub struct Bitmap {
@@ -10,7 +9,7 @@ pub struct Bitmap {
 }
 
 impl Bitmap {
-    pub fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
+    pub(crate) fn new(starting_block: usize, length: usize, device: Arc<dyn BlockDevice>) -> Self {
         Self {
             starting_block,
             length,
@@ -18,8 +17,7 @@ impl Bitmap {
             data: vec![0u8; length * BLOCK_SIZE],
         }
     }
-    pub fn allocate(&mut self) -> Option<usize> {
-        // let mut data = self.data.borrow_mut();
+    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 {
@@ -28,11 +26,9 @@ impl Bitmap {
             }
         }
         None
-        // panic!("No more space for allocation!")
     }
 
-    pub fn query(&self, index: usize) -> bool {
-        // let data = self.data.borrow();
+    pub(crate) fn query(&self, index: usize) -> bool {
         if index == 0 {
             false
         } else {
@@ -40,15 +36,13 @@ impl Bitmap {
         }
     }
 
-    // fn write_back(&mut self) {
-    //     for block_index_offset in self.dirty_blocks.iter() {
-    //         let buffer_front_index = BLOCK_SIZE * block_index_offset;
-    //         let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1);
-    //         self.device.write(
-    //             self.starting_block + block_index_offset,
-    //             &self.data[buffer_front_index..buffer_back_index],
-    //         );
-    //     }
-    //     self.dirty_blocks = Vec::new();
-    // }
+    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/src/disk/data_block.rs b/src/disk/block.rs
index d287ee6..d287ee6 100644
--- a/src/disk/data_block.rs
+++ b/src/disk/block.rs
diff --git a/src/disk/mod.rs b/src/disk/mod.rs
index 65f313c..878e832 100644
--- a/src/disk/mod.rs
+++ b/src/disk/mod.rs
@@ -1,7 +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;
-pub mod data_block;
-pub mod allocation;
diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs
index 9f157a5..3a60578 100644
--- a/src/filesystem/trait_impl.rs
+++ b/src/filesystem/trait_impl.rs
@@ -1,9 +1,12 @@
-use std::ffi::OsStr;
-use std::time::SystemTime;
-use fuser::{Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry, ReplyLseek, ReplyWrite, Request, TimeOrNow};
+use crate::AyaFS;
+use fuser::{
+    Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry,
+    ReplyLseek, ReplyWrite, Request, TimeOrNow,
+};
 use libc::{c_int, ENOENT, ENOSPC, ENOSYS};
 use log::debug;
-use crate::AyaFS;
+use std::ffi::OsStr;
+use std::time::SystemTime;
 
 impl Filesystem for AyaFS {
     fn init(&mut self, _req: &Request<'_>, _config: &mut KernelConfig) -> Result<(), c_int> {
@@ -186,4 +189,4 @@ impl Filesystem for AyaFS {
         );
         reply.error(ENOSYS);
     }
-}
\ No newline at end of file
+}
diff --git a/src/main.rs b/src/main.rs
index e01d352..a5ec616 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,7 +1,8 @@
 mod block_device;
 mod disk;
-mod memory;
 mod filesystem;
+mod memory;
+mod tests;
 mod utils;
 
 use clap::Parser;
@@ -12,12 +13,14 @@ use std::num::NonZeroUsize;
 use std::sync::Arc;
 use std::time::Duration;
 
-use memory::cached_block::CachedBlock;
-use disk::data_block::DataBlock;
+use crate::disk::block::InodeBlock;
 use crate::disk::inode::InodeMode;
-use block_device::{BLOCK_SIZE, BlockDevice, memory_disk::MemoryDisk};
+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 memory::cached_block::CachedBlock;
 use users::{get_current_gid, get_current_uid};
 
 #[derive(Parser, Debug)]
@@ -61,8 +64,10 @@ struct AyaFS {
     inode_start_block: usize,
     data_start_block: usize,
 
-    // cached_inodes: LruCache<usize, CachedInode>,
-    cached_blocks: LruCache<usize, CachedBlock<DataBlock>>,
+    cached_inodes: BlockCache<InodeBlock>,
+    cached_blocks: BlockCache<DataBlock>,
+    // cached_inodes: LruCache<usize, CachedBlock<InodeBlock>>,
+    // cached_blocks: LruCache<usize, CachedBlock<DataBlock>>,
 }
 
 impl AyaFS {
@@ -103,7 +108,7 @@ impl AyaFS {
         let _ = inode_bitmap.allocate().unwrap(); // inode block 0 is not usable
 
         let mut fs = Self {
-            device,
+            device: device.clone(),
             data_bitmap,
             inode_bitmap,
             inode_start_block: data_bitmap_block_number + inode_bitmap_block_number + 1,
@@ -111,8 +116,10 @@ impl AyaFS {
                 + inode_bitmap_block_number
                 + inode_block_number
                 + 1,
+            cached_inodes: BlockCache::new(device.clone(), 256),
+            cached_blocks: BlockCache::new(device.clone(), 256),
             // cached_inodes: LruCache::new(NonZeroUsize::new(256).unwrap()),
-            cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()),
+            // cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()),
         };
 
         fs.create_inode(
@@ -137,7 +144,7 @@ fn main() {
         MountOption::AutoUnmount,
         MountOption::AllowRoot,
     ];
-    let mem_disk = Arc::new(MemoryDisk::new());
+    let mem_disk = Arc::new(MemoryDisk::new(16384));
     let filesystem = AyaFS::new(mem_disk, 16384);
 
     fuser::mount2(filesystem, mount_point, &options).unwrap();
diff --git a/src/memory/cached_block.rs b/src/memory/cached_block.rs
index 0c401ff..9e266ef 100644
--- a/src/memory/cached_block.rs
+++ b/src/memory/cached_block.rs
@@ -1,7 +1,10 @@
-use and_then_some::BoolExt;
+use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use crate::disk::block::Block;
 use crate::AyaFS;
-use crate::block_device::BLOCK_SIZE;
-use crate::disk::data_block::{Block, DataBlock};
+use and_then_some::BoolExt;
+use lru::LruCache;
+use std::num::NonZeroUsize;
+use std::sync::Arc;
 
 #[derive(Clone)]
 pub struct CachedBlock<T: Block> {
@@ -28,39 +31,24 @@ pub fn convert<U: Block, T: Block>(input_block: &CachedBlock<U>) -> &CachedBlock
     unsafe { &*block }
 }
 
-impl AyaFS {
-    pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
-        if self.cached_blocks.contains(&block.index) {
-            let data_block = convert::<T, DataBlock>(&block).clone();
-            self.cached_blocks.push(block.index, data_block);
-            true
-        } else {
-            false
-        }
-    }
-    pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
-        self.load_block(index)
-            .and_then(|| self.cached_blocks.get(&index).map(convert::<DataBlock, T>))
-    }
+pub(crate) struct BlockCache<T: Block> {
+    device: Arc<dyn BlockDevice>,
+    cache: LruCache<usize, CachedBlock<T>>,
+}
 
-    pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
-        self.load_block(index).and_then(|| {
-            self.cached_blocks
-                .get_mut(&index)
-                .map(convert_mut::<DataBlock, 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 {
-        // 反正我自己保证所有实现了 Block trait 的数据结构都是 4K bytes 长, 来回 cast 没问题
-        // 如果 block cache 里没有这个 block
-        if self.cached_blocks.contains(&index) == false {
-            if self.data_bitmap.query(index) == false {
-                return false;
-            } // 先看这个 block 是不是 valid, 不 valid 直接返回 None
-            let block = DataBlock::default();
+        if self.cache.contains(&index) == false {
+            let block = T::default();
             let buffer = unsafe {
-                std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE)
+                std::slice::from_raw_parts_mut(&block as *const T as *mut u8, BLOCK_SIZE)
             };
             self.device.read(index, buffer);
             let cached_block = CachedBlock {
@@ -68,17 +56,160 @@ impl AyaFS {
                 index,
                 dirty: false,
             };
-            if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) {
+            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 DataBlock as *mut u8;
+                    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);
                 }
-            } // 如果 valid 就放到 block cache 里, 同时将（可能）被驱逐的 block 依据其是否为脏块进行写回
+            }
         }
-
         true
     }
+
+    /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载.
+    pub(crate) fn get_block<U: Block>(&mut self, index: usize) -> Option<&CachedBlock<U>> {
+        self.load_block(index)
+            .and_then(|| self.cache.get(&index).map(convert::<T, U>))
+    }
+
+    /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载.
+    pub(crate) fn get_block_mut<U: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<U>> {
+        self.load_block(index)
+            .and_then(|| self.cache.get_mut(&index).map(convert_mut::<T, U>))
+    }
+
+    /// 从 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>)
+    }
+
+    /// 从 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 data_block = convert::<U, T>(&block).clone();
+            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 load_block(&mut self, index: usize) -> bool {
+        if !self.data_bitmap.query(index) {
+            self.cached_blocks.pop(&index);
+            // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry.
+            return false;
+        }
+        self.cached_blocks.load_block(index)
+    }
+
+    pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .and_then(|| self.cached_blocks.get_block::<T>(index))
+    }
+
+    pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .and_then(|| self.cached_blocks.get_block_mut::<T>(index))
+    }
+
+    pub(crate) fn peek_block<T: Block>(&self, index: usize) -> Option<&CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .and_then(|| self.cached_blocks.peek_block::<T>(index))
+    }
+
+    pub(crate) fn peek_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+        self.data_bitmap
+            .query(index)
+            .and_then(|| self.cached_blocks.peek_block_mut::<T>(index))
+    }
+
+    pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
+        self.cached_blocks.update_block(block)
+    }
+
+    // pub(crate) fn update_block<T: Block>(&mut self, block: CachedBlock<T>) -> bool {
+    //     if self.cached_blocks.contains(&block.index) {
+    //         let data_block = convert::<T, DataBlock>(&block).clone();
+    //         self.cached_blocks.push(block.index, data_block);
+    //         true
+    //     } else {
+    //         false
+    //     }
+    // }
+    //
+    // /// 从 LRU cache 里获取一个 block 的引用, 如果没有在 cache 中会加载.
+    // pub(crate) fn get_block<T: Block>(&mut self, index: usize) -> Option<&CachedBlock<T>> {
+    //     self.load_block(index)
+    //         .and_then(|| self.cached_blocks.get(&index).map(convert::<DataBlock, T>))
+    // }
+    //
+    // /// 从 LRU cache 里获取一个 block 的可变引用, 如果没有在 cache 中会加载.
+    // pub(crate) fn get_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+    //     self.load_block(index).and_then(|| {
+    //         self.cached_blocks
+    //             .get_mut(&index)
+    //             .map(convert_mut::<DataBlock, T>)
+    //     })
+    // }
+    //
+    // /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+    // pub(crate) fn peek_block<T: Block>(&self, index: usize) -> Option<&CachedBlock<T>> {
+    //     self.cached_blocks.peek(&index).map(convert::<DataBlock, T>)
+    // }
+    //
+    // /// 从 LRU cache 中读取一个 block 的可变引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
+    // pub(crate) fn peek_block_mut<T: Block>(&mut self, index: usize) -> Option<&mut CachedBlock<T>> {
+    //     self.cached_blocks.peek_mut(&index).map(convert_mut::<DataBlock, T>)
+    // }
+    //
+    // pub(crate) fn load_block(&mut self, index: usize) -> bool {
+    //     // 先看这个 block 是不是 valid, 不 valid 直接返回 false.
+    //     if !self.data_bitmap.query(index) {
+    //         self.cached_blocks.pop(&index);
+    //         // deallocate 时只更新 bitmap 没有动 cache, lazy 地驱逐 cache 中的无效 entry.
+    //         return false;
+    //     }
+    //
+    //     // 接下来这个 block 一定 valid. 如果 cache 里没有这个 block 就把它 load 到 cache 里
+    //     if self.cached_blocks.contains(&index) == false {
+    //         let block = DataBlock::default();
+    //         let buffer = unsafe {
+    //             std::slice::from_raw_parts_mut(&block as *const DataBlock as *mut u8, BLOCK_SIZE)
+    //         };
+    //         self.device.read(index, buffer);
+    //         let cached_block = CachedBlock {
+    //             block,
+    //             index,
+    //             dirty: false,
+    //         };
+    //         if let Some((old_index, old_block)) = self.cached_blocks.push(index, cached_block) {
+    //             assert_ne!(old_index, index); // 只有 block 不在 cache 里的时候才会插入
+    //             if old_block.dirty {
+    //                 let old_block_ptr = &old_block.block as *const DataBlock 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
+    // }
 }
diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs
index b51d279..b81bd2e 100644
--- a/src/memory/cached_inode.rs
+++ b/src/memory/cached_inode.rs
@@ -1,7 +1,7 @@
-use and_then_some::BoolExt;
+use crate::disk::block::{Block, InodeBlock};
+use crate::disk::inode::{Inode, InodeMode, INODE_SIZE};
 use crate::AyaFS;
-use crate::disk::data_block::InodeBlock;
-use crate::disk::inode::{Inode, INODE_SIZE, InodeMode};
+use and_then_some::BoolExt;
 
 impl AyaFS {
     pub(crate) fn create_inode(
@@ -30,10 +30,24 @@ impl AyaFS {
         })
     }
 
+    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);
-            self.get_block::<InodeBlock>(block_index)
+            self.cached_inodes
+                .get_block::<InodeBlock>(block_index)
                 .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
         })
     }
@@ -41,11 +55,33 @@ impl AyaFS {
     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);
-            self.get_block_mut::<InodeBlock>(block_index)
+            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]
+                })
+        })
+    }
+
+    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])
+        })
+    }
+
+    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]
                 })
         })
     }
-}
\ No newline at end of file
+}
diff --git a/src/memory/mod.rs b/src/memory/mod.rs
index ffdf04c..3380d0f 100644
--- a/src/memory/mod.rs
+++ b/src/memory/mod.rs
@@ -1,5 +1,4 @@
 /// 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;
diff --git a/src/tests/bitmap.rs b/src/tests/bitmap.rs
new file mode 100644
index 0000000..9b21b6f
--- /dev/null
+++ b/src/tests/bitmap.rs
@@ -0,0 +1,23 @@
+use crate::tests::common;
+
+#[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);
+}
diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs
new file mode 100644
index 0000000..f1c18cc
--- /dev/null
+++ b/src/tests/block_cache.rs
@@ -0,0 +1,79 @@
+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() {
+    let mut fs = common::setup();
+
+    let inode_index = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap();
+    let mut inode = fs.get_inode(inode_index).unwrap().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();
+    }
+
+    for i in 0..DOUBLE_INDIRECT_NUMBER {
+        fs.allocate_block_for(&mut inode).unwrap();
+    }
+
+    let single_indirect = inode.single_indirect;
+    let double_indirect = inode.double_indirect;
+    let triple_indirect = inode.triple_indirect;
+
+    fs.update_inode(inode_index, inode);
+
+    let indirect_block = fs
+        .peek_block::<IndirectBlock>(single_indirect as usize)
+        .unwrap();
+    for entry in indirect_block.block.entries {
+        assert_ne!(entry, 0);
+        assert!(fs.data_bitmap.query(entry as usize));
+    }
+
+    // let double_indirect_block = fs
+    //     .peek_block::<DoubleIndirectBlock>(double_indirect as usize)
+    //     .unwrap();
+    // for indirect_entry in double_indirect_block.block.indirect {
+    //     let indirect_block = fs
+    //         .peek_block::<IndirectBlock>(indirect_entry 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(double_indirect as usize), false);
+
+    assert_eq!(fs.data_bitmap.query(triple_indirect as usize), false);
+}
diff --git a/src/tests/common/mod.rs b/src/tests/common/mod.rs
new file mode 100644
index 0000000..9314fd9
--- /dev/null
+++ b/src/tests/common/mod.rs
@@ -0,0 +1,8 @@
+use crate::block_device::memory_disk::MemoryDisk;
+use crate::AyaFS;
+use std::sync::Arc;
+
+pub(crate) fn setup() -> AyaFS {
+    let mem_disk = Arc::new(MemoryDisk::new(1059715));
+    AyaFS::new(mem_disk, 1059715)
+}
diff --git a/src/tests/mod.rs b/src/tests/mod.rs
new file mode 100644
index 0000000..df442c1
--- /dev/null
+++ b/src/tests/mod.rs
@@ -0,0 +1,6 @@
+#[cfg(test)]
+mod bitmap;
+mod common;
+
+#[cfg(test)]
+mod block_cache;