I hate cache!

8 files changed, 553 insertions, 277 deletions

diff --git a/.gitignore b/.gitignore
index b83d222..431845e 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1 +1,2 @@
 /target/
+.idea/
diff --git a/Cargo.lock b/Cargo.lock
index b4b65f3..4b0f09f 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,6 +3,18 @@
 version = 3
 
 [[package]]
+name = "ahash"
+version = "0.8.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "91429305e9f0a25f6205c5b8e0d2db09e0708a7a6df0f42212bb56c32c8ac97a"
+dependencies = [
+ "cfg-if",
+ "once_cell",
+ "version_check",
+ "zerocopy",
+]
+
+[[package]]
 name = "aho-corasick"
 version = "1.1.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -12,6 +24,18 @@ dependencies = [
 ]
 
 [[package]]
+name = "allocator-api2"
+version = "0.2.16"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0942ffc6dcaadf03badf6e6a2d0228460359d5e34b57ccdc720b7382dfbd5ec5"
+
+[[package]]
+name = "and_then_some"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a9fe53f9ae2a60243d22bb106d809eb10bd9b2550ea98a68e8855d21e70a37ef"
+
+[[package]]
 name = "anstream"
 version = "0.6.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -72,6 +96,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1fd0f2584146f6f2ef48085050886acf353beff7305ebd1ae69500e27c67f64b"
 
 [[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
 name = "clap"
 version = "4.4.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -142,9 +172,9 @@ dependencies = [
 
 [[package]]
 name = "fuser"
-version = "0.13.0"
+version = "0.14.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "21370f84640642c8ea36dfb2a6bfc4c55941f476fcf431f6fef25a5ddcf0169b"
+checksum = "2e697f6f62c20b6fad1ba0f84ae909f25971cf16e735273524e3977c94604cf8"
 dependencies = [
  "libc",
  "log",
@@ -156,6 +186,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "hashbrown"
+version = "0.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f93e7192158dbcda357bdec5fb5788eebf8bbac027f3f33e719d29135ae84156"
+dependencies = [
+ "ahash",
+ "allocator-api2",
+]
+
+[[package]]
 name = "heck"
 version = "0.4.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -203,6 +243,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b5e6163cb8c49088c2c36f57875e58ccd8c87c7427f7fbd50ea6710b2f3f2e8f"
 
 [[package]]
+name = "lru"
+version = "0.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1efa59af2ddfad1854ae27d75009d538d0998b4b2fd47083e743ac1a10e46c60"
+dependencies = [
+ "hashbrown",
+]
+
+[[package]]
 name = "memchr"
 version = "2.6.4"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -212,20 +261,28 @@ checksum = "f665ee40bc4a3c5590afb1e9677db74a508659dfd71e126420da8274909a0167"
 name = "myfs"
 version = "0.1.0"
 dependencies = [
+ "and_then_some",
  "bitflags",
  "clap",
  "env_logger",
  "fuser",
  "libc",
  "log",
+ "lru",
  "users",
 ]
 
 [[package]]
+name = "once_cell"
+version = "1.18.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "dd8b5dd2ae5ed71462c540258bedcb51965123ad7e7ccf4b9a8cafaa4a63576d"
+
+[[package]]
 name = "page_size"
-version = "0.5.0"
+version = "0.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1b7663cbd190cfd818d08efa8497f6cd383076688c49a391ef7c0d03cd12b561"
+checksum = "30d5b2194ed13191c1999ae0704b7839fb18384fa22e49b57eeaa97d79ce40da"
 dependencies = [
  "libc",
  "winapi",
@@ -352,6 +409,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "711b9620af191e0cdc7468a8d14e709c3dcdb115b36f838e601583af800a370a"
 
 [[package]]
+name = "version_check"
+version = "0.9.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f"
+
+[[package]]
 name = "winapi"
 version = "0.3.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -450,9 +513,9 @@ checksum = "ed94fce61571a4006852b7389a063ab983c02eb1bb37b47f8272ce92d06d9538"
 
 [[package]]
 name = "zerocopy"
-version = "0.6.4"
+version = "0.7.26"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "20707b61725734c595e840fb3704378a0cd2b9c74cc9e6e20724838fc6a1e2f9"
+checksum = "e97e415490559a91254a2979b4829267a57d2fcd741a98eee8b722fb57289aa0"
 dependencies = [
  "byteorder",
  "zerocopy-derive",
@@ -460,9 +523,9 @@ dependencies = [
 
 [[package]]
 name = "zerocopy-derive"
-version = "0.6.4"
+version = "0.7.26"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "56097d5b91d711293a42be9289403896b68654625021732067eac7a4ca388a1f"
+checksum = "dd7e48ccf166952882ca8bd778a43502c64f33bf94c12ebe2a7f08e5a0f6689f"
 dependencies = [
  "proc-macro2",
  "quote",
diff --git a/Cargo.toml b/Cargo.toml
index 9bcabcf..f807e96 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -6,10 +6,12 @@ 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.0"
 clap = { version = "4.4.6", features = ["derive"] }
 env_logger = "0.10.0"
-fuser = "0.13.0"
+fuser = "0.14.0"
 libc = "0.2.148"
 log = "0.4.20"
+lru = "0.12.0"
 users = "0.11.0"
diff --git a/src/cached_inode.rs b/src/cached_inode.rs
index 814c1aa..a4e8202 100644
--- a/src/cached_inode.rs
+++ b/src/cached_inode.rs
@@ -1,3 +1,4 @@
+use crate::disk::data_block::{Block, DataBlock};
 use crate::disk::inode::Inode;
 
 pub struct CachedInode {
@@ -5,3 +6,28 @@ pub struct CachedInode {
     pub index: usize,
     pub dirty: bool,
 }
+
+#[derive(Clone)]
+pub struct CachedBlock<T: Block> {
+    pub block: T,
+    pub index: usize,
+    pub dirty: bool,
+}
+
+impl<T: Block> CachedBlock<T> {
+    fn cast<U: Block>(&self) -> CachedBlock<U> {
+        unsafe { std::mem::transmute_copy(&self) }
+    }
+}
+
+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 }
+}
diff --git a/src/disk/bitmap.rs b/src/disk/bitmap.rs
index d5a8fe9..64389c2 100644
--- a/src/disk/bitmap.rs
+++ b/src/disk/bitmap.rs
@@ -1,4 +1,5 @@
 use crate::block_device::{BlockDevice, BLOCK_SIZE};
+use std::cell::RefCell;
 use std::sync::Arc;
 
 pub struct Bitmap {
@@ -6,7 +7,6 @@ pub struct Bitmap {
     pub length: usize,
     pub device: Arc<dyn BlockDevice>,
     pub data: Vec<u8>,
-    pub dirty_blocks: Vec<usize>,
 }
 
 impl Bitmap {
@@ -16,15 +16,14 @@ impl Bitmap {
             length,
             device,
             data: vec![0u8; length * BLOCK_SIZE],
-            dirty_blocks: Vec::new(),
         }
     }
     pub fn allocate(&mut self) -> Option<usize> {
+        // let mut data = self.data.borrow_mut();
         for (i, byte) in self.data.iter_mut().enumerate() {
             let leading_ones = byte.leading_ones();
             if leading_ones != 8 {
                 *byte |= (1 << (7 - leading_ones)) as u8;
-                self.dirty_blocks.push(i / BLOCK_SIZE);
                 return Some(i * 8 + leading_ones as usize);
             }
         }
@@ -33,6 +32,7 @@ impl Bitmap {
     }
 
     pub fn query(&self, index: usize) -> bool {
+        // let data = self.data.borrow();
         if index == 0 {
             false
         } else {
@@ -40,15 +40,15 @@ 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();
-    }
+    // fn write_back(&mut self) {
+    //     for block_index_offset in self.dirty_blocks.iter() {
+    //         let buffer_front_index = BLOCK_SIZE * block_index_offset;
+    //         let buffer_back_index = BLOCK_SIZE * (block_index_offset + 1);
+    //         self.device.write(
+    //             self.starting_block + block_index_offset,
+    //             &self.data[buffer_front_index..buffer_back_index],
+    //         );
+    //     }
+    //     self.dirty_blocks = Vec::new();
+    // }
 }
diff --git a/src/disk/data_block.rs b/src/disk/data_block.rs
index 2160b91..9c8cc26 100644
--- a/src/disk/data_block.rs
+++ b/src/disk/data_block.rs
@@ -1,12 +1,54 @@
-pub trait Block: Default {}
+use crate::disk::inode::Inode;
+use libc::pathconf;
+
+pub trait Block: Default + Clone {}
+
+#[derive(Clone)]
+pub struct DataBlock(pub(crate) [u8; 4096]);
+
+impl Default for DataBlock {
+    fn default() -> Self {
+        Self([0; 4096])
+    }
+}
 
-#[derive(Default)]
-pub struct DataBlock([u8; 4096]);
 impl Block for DataBlock {}
 
+#[derive(Clone)]
+pub struct InodeBlock {
+    pub(crate) inodes: [Inode; 16],
+}
+
+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(),
+            ],
+        }
+    }
+}
+
+impl Block for InodeBlock {}
+
 const FULL_MAP: u32 = 0b111_111_111_111_111;
 
-#[derive(Default)]
+#[derive(Clone)]
 pub struct DirectoryBlock {
     entries: [[u8; 256]; 15],
     inode_ids: [usize; 15],
@@ -14,6 +56,17 @@ pub struct DirectoryBlock {
     reserved: [u8; 132],
 }
 
+impl Default for DirectoryBlock {
+    fn default() -> Self {
+        Self {
+            entries: [[0; 256]; 15],
+            inode_ids: [0; 15],
+            occupancy_map: 0,
+            reserved: [0xFF; 132],
+        }
+    }
+}
+
 impl Block for DirectoryBlock {}
 
 impl DirectoryBlock {
@@ -42,11 +95,17 @@ impl DirectoryBlock {
     }
 }
 
-#[derive(Default)]
+#[derive(Clone)]
 pub struct IndirectBlock {
     pub entries: [u32; 1024],
 }
 
+impl Default for IndirectBlock {
+    fn default() -> Self {
+        Self { entries: [0; 1024] }
+    }
+}
+
 impl Block for IndirectBlock {}
 
 impl IndirectBlock {
@@ -59,11 +118,19 @@ impl IndirectBlock {
     }
 }
 
-#[derive(Default)]
+#[derive(Clone)]
 pub struct DoubleIndirectBlock {
     pub indirect: [u32; 1024],
 }
 
+impl Default for DoubleIndirectBlock {
+    fn default() -> Self {
+        Self {
+            indirect: [0; 1024],
+        }
+    }
+}
+
 impl Block for DoubleIndirectBlock {}
 
 impl DoubleIndirectBlock {
@@ -76,11 +143,19 @@ impl DoubleIndirectBlock {
     }
 }
 
-#[derive(Default)]
+#[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 {}
 
 impl TripleIndirectBlock {
diff --git a/src/disk/inode.rs b/src/disk/inode.rs
index 6adc75d..48085d8 100644
--- a/src/disk/inode.rs
+++ b/src/disk/inode.rs
@@ -2,7 +2,7 @@ use bitflags::bitflags;
 
 const DIRECT_NUMBER: usize = 15;
 
-#[derive(Debug)]
+#[derive(Debug, Clone, Copy)]
 pub struct InodeMode(u16);
 
 bitflags! {
@@ -37,7 +37,7 @@ bitflags! {
 /// - added more direct blocks for a total size of 128 bytes
 /// TODO: do we need to extend time precision?
 #[repr(C)]
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct Inode {
     mode: InodeMode,
     uid: u32,
diff --git a/src/main.rs b/src/main.rs
index 0e799e4..2885b14 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -2,19 +2,23 @@ mod block_device;
 mod cached_inode;
 mod disk;
 
-use std::collections::HashMap;
+use and_then_some::BoolExt;
 use clap::Parser;
 use fuser::{
     Filesystem, KernelConfig, MountOption, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty,
     ReplyEntry, ReplyLseek, ReplyWrite, Request, TimeOrNow,
 };
 use log::debug;
+use lru::LruCache;
 use std::ffi::OsStr;
+use std::num::NonZeroUsize;
 use std::sync::Arc;
 use std::time::{Duration, SystemTime, UNIX_EPOCH};
 
-use crate::cached_inode::CachedInode;
-use crate::disk::data_block::{Block, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
+use crate::cached_inode::{convert, convert_mut, CachedBlock, CachedInode};
+use crate::disk::data_block::{
+    Block, DataBlock, DoubleIndirectBlock, IndirectBlock, InodeBlock, TripleIndirectBlock,
+};
 use crate::disk::inode::InodeMode;
 use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE};
 use disk::bitmap::Bitmap;
@@ -63,8 +67,9 @@ struct MyFS {
     inode_start_block: usize,
     data_start_block: usize,
 
-    cached_inode: HashMap<usize, CachedInode>,
-    cache: [[u8; 4096]; 8192],
+    cached_inodes: LruCache<usize, CachedInode>,
+    cached_blocks: LruCache<usize, CachedBlock<DataBlock>>,
+    // cached_block_cleanness: LruCache<usize, bool>,
 }
 
 impl MyFS {
@@ -95,12 +100,15 @@ impl MyFS {
                 + data_block_number
         );
 
-        let data_bitmap = Bitmap::new(1, data_bitmap_block_number, device.clone());
-        let inode_bitmap = Bitmap::new(
+        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,
             data_bitmap,
@@ -110,28 +118,16 @@ impl MyFS {
                 + inode_bitmap_block_number
                 + inode_block_number
                 + 1,
-            cached_inode: HashMap::new(),
-            cache: [[0; 4096]; 8192],
+            cached_inodes: LruCache::new(NonZeroUsize::new(256).unwrap()),
+            cached_blocks: LruCache::new(NonZeroUsize::new(256).unwrap()),
         };
 
-        let _ = fs.data_bitmap.allocate().unwrap(); // data block 0 is not usable
-        let _ = fs.inode_bitmap.allocate().unwrap(); // inode block 0 is not usable
-        let root_inode_index = fs.inode_bitmap.allocate().unwrap(); // Inode starts from 1
-        assert_eq!(root_inode_index, 1);
-        let (root_inode_block, root_inode_offset) = fs.locate_inode(root_inode_index);
-        fs.put_inode(
-            root_inode_block,
-            root_inode_offset,
-            &Inode::directory(
-                0o755,
-                get_current_uid(),
-                get_current_gid(),
-                Self::time_now(),
-                0,
-                0,
-                0,
-                0,
-            ),
+        fs.create_inode_2(
+            0o755,
+            InodeMode::IFDIR,
+            get_current_uid(),
+            get_current_gid(),
+            0,
         );
 
         fs
@@ -144,18 +140,6 @@ impl MyFS {
             .as_secs() as u32
     }
 
-    pub fn inode_active(&self, inode: usize) -> bool {
-        self.inode_bitmap.query(inode)
-    }
-
-    /// 输入 inode 编号, 返回它对应的 block number 和 block 内 offset
-    pub 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)
-    }
-
     pub fn create_inode(
         &mut self,
         permissions: u16,
@@ -180,198 +164,323 @@ impl MyFS {
                 index: inode_index,
                 dirty: false,
             };
-            self.cached_inode.insert(inode_index, inode);
+            self.cached_inodes.put(inode_index, inode); // TODO write back evicted inode
             inode_index
         })
     }
 
-    /// 得有一个 Inode Cache 数据结构!
-    pub fn read_inode(
+    pub fn create_inode_2(
         &mut self,
-        index: usize,
-    ) -> bool {
-        if self.cached_inode.contains_key(&index) {
-            return true;
-        } // 已经在 Inode Cache 里了, 返回 true
-        if self.inode_bitmap.query(index) {
-            let (block, offset) = self.locate_inode(index);
-            let inode = CachedInode {
-                inode: self.fetch_inode(block, offset),
-                index,
-                dirty: false,
-            };
-            self.cached_inode.insert(index, inode);
-            return true;
-        } // 没有在 Inode Cache 里, 但是是有效 inode, 可以读到 Cache 里, 返回 true
-        false // 都没有, 返回 false.
+        permissions: u16,
+        mode: InodeMode,
+        uid: u32,
+        gid: u32,
+        flags: u32,
+    ) -> Option<usize> {
+        self.inode_bitmap.allocate().map(|inode_index| {
+            self.get_inode_mut_2(inode_index).map(|inode| {
+                *inode = Inode::make_inode(
+                    permissions,
+                    mode,
+                    uid,
+                    gid,
+                    Self::time_now(),
+                    flags,
+                    0,
+                    0,
+                    0,
+                );
+            });
+            inode_index
+        })
     }
 
-    pub fn write_back_inode(
-        &mut self,
-        index: usize,
-    ) -> bool {
-        if let Some(cached_inode) = self.cached_inode.get_mut(&index) {
-            if cached_inode.dirty {
-                let (block, offset) = self.locate_inode(cached_inode.index);
-                self.put_inode(block, offset, &cached_inode.inode);
-                cached_inode.dirty = false;
-            }
-            true // Inode 在 Cache 中, 如果 dirty 则写回, 如果不脏不用管, 都返回写回成功.
+    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 // Inode 没有在 Cache 中, 返回失败.
+            false
         }
     }
 
-    // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer
-    fn put_inode(&mut self, block: usize, offset: usize, inode: &Inode) {
-        let mut buffer = vec![0u8; BLOCK_SIZE];
-        self.device.read(block, buffer.as_mut_slice());
+    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>))
+    }
+
+    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>)
+        })
+    }
+
+    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();
+            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);
+                }
+            } // 如果 valid 就放到 block cache 里, 同时将（可能）被驱逐的 block 依据其是否为脏块进行写回
+        }
+
+        true
+    }
 
-        let inode_raw = inode as *const Inode as *const u8;
-        let inode_slice = unsafe { std::slice::from_raw_parts(inode_raw, INODE_SIZE) };
-        buffer[offset..offset + INODE_SIZE].copy_from_slice(inode_slice);
+    fn get_inode_2(&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)
+                .map(|cached_block| &cached_block.block.inodes[offset / INODE_SIZE])
+        })
+    }
 
-        self.device.write(block, buffer.as_slice());
+    fn get_inode_mut_2(&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)
+                .map(|cached_block| {
+                    cached_block.dirty = true; // 保守一些, 只要返回了 &mut Inode 这个页一定标记为脏
+                    &mut cached_block.block.inodes[offset / INODE_SIZE]
+                })
+        })
     }
 
-    pub fn write_inode(&mut self, inode_index: usize, inode: &Inode) -> bool {
-        if self.inode_active(inode_index) {
-            let (block, offset) = self.locate_inode(inode_index);
-            self.put_inode(block, offset, inode);
-            true
-        } else {
-            false
+    /// 不使用 inode cache, 只用 block cache 的方案
+    fn load_inode_2(&mut self, inode_index: usize) -> bool {
+        // 首先保证 inode 有效, 无效返回 false
+        if !self.inode_bitmap.query(inode_index) {
+            return false;
+        }
+        // 找到 inode
+        let (block_index, _) = self.locate_inode(inode_index);
+        if self.cached_blocks.contains(&block_index) {
+            return true;
         }
+
+        return self.load_block(block_index);
+    }
+
+    fn get_inode(&mut self, inode_index: usize) -> Option<&CachedInode> {
+        self.load_inode(inode_index)
+            .and_then(|| self.cached_inodes.get(&inode_index))
     }
 
-    pub fn get_inode(&self, inode_index: usize) -> Option<Inode> {
-        if self.inode_active(inode_index) {
-            let (block, offset) = self.locate_inode(inode_index);
-            Some(self.fetch_inode(block, offset))
+    fn get_inode_mut(&mut self, inode_index: usize) -> Option<&mut CachedInode> {
+        self.load_inode(inode_index)
+            .and_then(|| self.cached_inodes.get_mut(&inode_index))
+    }
+
+    fn load_inode(&mut self, inode_index: usize) -> bool {
+        // 首先保证 inode 有效, 无效返回 false
+        if !self.inode_bitmap.query(inode_index) {
+            return false;
+        }
+        // 如果已经缓存了就返回 true
+        if self.cached_inodes.contains(&inode_index) {
+            return true;
+        }
+        // inode 有效但没有在 cache 里
+        let (block_index, offset) = self.locate_inode(inode_index);
+        // 找到 inode 所在的 block
+        if let Some(inode_block) = self.get_block::<DataBlock>(block_index) {
+            // 创建新的 inode 并且从 block 中加载.
+            let inode = unsafe { std::mem::zeroed::<Inode>() };
+            let inode_slice = unsafe {
+                std::slice::from_raw_parts_mut(&inode as *const Inode as *mut u8, INODE_SIZE)
+            };
+            inode_slice.copy_from_slice(&inode_block.block.0[offset..offset + INODE_SIZE]);
+
+            let cached_inode = CachedInode {
+                inode,
+                index: inode_index,
+                dirty: false,
+            };
+
+            // 将加载好的 inode 放进 inode cache
+            if let Some((old_index, old_inode)) = self.cached_inodes.push(inode_index, cached_inode)
+            {
+                assert_ne!(old_index, inode_index); // 如果 old_index == inode index 说明它原本就在 inode cache 里了.
+                if old_inode.dirty {
+                    // 如果旧的 inode 被修改过了, 将它写回 block cache 并且标记对应 block 为脏
+                    let (old_block_index, old_offset) = self.locate_inode(old_index);
+                    self.get_block_mut::<DataBlock>(old_block_index)
+                        .map(|cached_block| {
+                            let old_inode_ptr = &old_inode.inode as *const Inode as *const u8;
+                            let old_inode_slice =
+                                unsafe { std::slice::from_raw_parts(old_inode_ptr, INODE_SIZE) };
+                            cached_block.dirty = true;
+                            cached_block.block.0[old_offset..old_offset + INODE_SIZE]
+                                .copy_from_slice(old_inode_slice);
+                        })
+                        .expect("Writing inode back to a invalid block!"); // Debug use
+                }
+            }
         } else {
-            None
+            panic!("Getting inode from a invalid block!"); // Debug use
         }
+
+        true
+    }
+
+    /// 输入 inode 编号, 返回它对应的 block number 和 block 内 offset
+    pub 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)
     }
 
     /// 为 Inode 分配新 block, 返回 block 的编号
     pub fn allocate_block(&mut self, inode: &mut Inode) -> Option<u32> {
-        /// 从 direct block 里面尝试分配
+        // 先看这个 inode 的 direct block 有没有空闲
         for index in inode.direct.iter_mut() {
-            /// 如果这个位置没被分配, 分配一个 index 塞进去
-            if self.data_bitmap.query(*index as usize) == false {
-                let block_index = self.data_bitmap.allocate() as u32;
+            if !self.data_bitmap.query(*index as usize) {
+                let block_index = self
+                    .data_bitmap
+                    .allocate()
+                    .unwrap() as u32;
                 *index = block_index;
                 inode.n_blocks += 1;
-                // TODO 标记 inode 所在 block 为脏
+                // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
                 return Some(block_index);
             }
         }
 
-        /// 如果这个 indirect block 还未分配, 分配一个
-        if self.data_bitmap.query(inode.single_indirect as usize) == false {
-            // TODO 标记 inode 所在 block 为脏
-            inode.single_indirect = self.data_bitmap.allocate() as u32;
+        // 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;
         }
+        // 在 indirect block 里尝试分配
         if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) {
-            // TODO 标记 inode 所在 block 为脏
             inode.n_blocks += 1;
             return Some(block_index);
         }
 
-        /// 如果 double indirect block 还未分配, 分配一个
-        if self.data_bitmap.query(inode.double_indirect as usize) == false {
-            // TODO 标记 inode 所在 block 为脏
-            inode.double_indirect = self.data_bitmap.allocate() as u32;
+        // 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;
         }
+        // 在 double indirect block 里尝试分配
         if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) {
-            // TODO 标记 inode 所在 block 为脏
             inode.n_blocks += 1;
             return Some(block_index);
         }
 
-        /// 如果 triple indirect block 还未分配, 分配一个
-        if self.data_bitmap.query(inode.triple_indirect as usize) == false {
-            // TODO 标记 inode 所在 block 为脏
-            inode.triple_indirect = self.data_bitmap.allocate() as u32;
+        // 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;
         }
+        // 在 double indirect block 里尝试分配
         if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) {
-            // TODO 标记 inode 所在 block 为脏
             inode.n_blocks += 1;
             return Some(block_index);
         }
-
-        /// 到这里说明真没空间了
         None
     }
 
     fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
         // 取出 single indirect block, 尝试在里面分配
-        let indirect = self.fetch_block::<IndirectBlock>(*indirect_entry);
-        for entry in indirect.entries.iter_mut() {
-            // 如果这个位置没被分配, 分配一个 index 塞进去
-            if self.data_bitmap.query(*entry as usize) == false {
-                let block_index = self.data_bitmap.allocate() as u32;
-                *entry = block_index;
-                // TODO 标记 single indirect 为脏
-                return Some(block_index);
+        let indirect_entry = indirect_entry as usize;
+
+        if let Some(block) = self
+            .get_block(indirect_entry)
+            .map(convert::<DataBlock, IndirectBlock>)
+        {
+            let mut indirect_block = block.clone();
+            for entry in indirect_block.block.entries.iter_mut() {
+                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;
+                    *entry = block_index;
+                    self.update_block(indirect_block);
+                    return Some(block_index);
+                }
             }
         }
         None
     }
 
     fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<u32> {
-        let double_indirect = self.fetch_block::<DoubleIndirectBlock>(double_indirect_entry);
-        for indirect_entry in double_indirect.indirect.iter_mut() {
-            if self.data_bitmap.query(*indirect_entry as usize) == false {
-                // TODO 标记 double indirect 为脏
-                *indirect_entry = self.data_bitmap.allocate() as u32;
-            }
-            if let Some(block_index) = self.allocate_in_indirect(*indirect_entry) {
-                return Some(block_index);
+        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();
+            for indirect_entry in double_indirect_block.block.indirect.iter_mut() {
+                if self.data_bitmap.query(*indirect_entry as usize) == false {
+                    double_indirect_block.dirty = true;
+                    *indirect_entry = self.data_bitmap.allocate().expect("No free space") as u32;
+                }
+
+                if let Some(block_index) = self.allocate_in_indirect(*indirect_entry) {
+                    if double_indirect_block.dirty {
+                        self.update_block(double_indirect_block);
+                    }
+                    return Some(block_index);
+                }
             }
         }
         None
     }
 
     fn alloc_in_triple_indirect(&mut self, triple_indirect_entry: u32) -> Option<u32> {
-        let triple_indirect = self.fetch_block::<TripleIndirectBlock>(triple_indirect_entry);
-        for double_indirect_entry in triple_indirect.double_indirect.iter_mut() {
-            if self.data_bitmap.query(*double_indirect_entry as usize) == false {
-                // TODO 标记 triple indirect 为脏
-                *double_indirect_entry = self.data_bitmap.allocate() as u32;
-            }
-            if let Some(block_index) = self.alloc_in_double_indirect(*double_indirect_entry) {
-                return Some(block_index);
+        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();
+            for double_indirect_entry in triple_indirect_block.block.double_indirect.iter_mut() {
+                if self.data_bitmap.query(*double_indirect_entry as usize) == false {
+                    triple_indirect_block.dirty = true;
+                    *double_indirect_entry =
+                        self.data_bitmap.allocate().expect("No free space") as u32;
+                }
+                if let Some(block_index) = self.alloc_in_double_indirect(*double_indirect_entry) {
+                    if triple_indirect_block.dirty {
+                        self.update_block(triple_indirect_block);
+                    }
+                    return Some(block_index);
+                }
             }
         }
         None
     }
-
-    // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer
-    fn fetch_block<T: Block>(&self, block_index: u32) -> T {
-        let mut buffer = vec![0u8; BLOCK_SIZE];
-        self.device
-            .read(block_index as usize, buffer.as_mut_slice());
-
-        let block = T::default();
-        let block_slice =
-            unsafe { std::slice::from_raw_parts_mut(&block as *const T as *mut u8, BLOCK_SIZE) };
-        block_slice.copy_from_slice(&buffer[..]);
-        block
-    }
-
-    // TODO: 实现一个 LRU 的 cache 机制, 不要每次都开 buffer
-    fn fetch_inode(&self, block: usize, offset: usize) -> Inode {
-        let mut buffer = vec![0u8; BLOCK_SIZE];
-        self.device.read(block, buffer.as_mut_slice());
-
-        let inode = Inode::empty();
-        let inode_slice = unsafe {
-            std::slice::from_raw_parts_mut(&inode as *const Inode as *mut u8, INODE_SIZE)
-        };
-        inode_slice.copy_from_slice(&buffer[offset..offset + INODE_SIZE]);
-        inode
-    }
 }
 
 impl Filesystem for MyFS {
@@ -384,50 +493,22 @@ impl Filesystem for MyFS {
         debug!("Filesystem::destroy()");
     }
 
-    fn access(&mut self, _req: &Request<'_>, ino: u64, mask: i32, reply: ReplyEmpty) {
-        debug!("Filesystem::getattr(ino: {}, mask: {})", ino, mask);
-        if let Some(inode) = self.get_inode(ino as usize) {
-            reply.ok()
-        } else {
-            reply.error(ENOENT)
-        }
-    }
-
-    fn mkdir(
-        &mut self,
-        _req: &Request<'_>,
-        parent: u64,
-        name: &OsStr,
-        mode: u32,
-        umask: u32,
-        reply: ReplyEntry,
-    ) {
+    fn lookup(&mut self, _req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEntry) {
         debug!(
-            "Filesystem::mkdir(parent: {}, name: {:?}, mode: {}, umask: {})",
-            parent, name, mode, umask
+            "Filesystem::lookup called with parent {} name {}",
+            parent,
+            name.to_str().unwrap()
         );
-        if let Some(inode) = self.get_inode(parent as usize) {
-        } else {
-            reply.error(ENOENT);
+        let parent = parent as usize;
+        if let Some(inode) = self.get_inode_2(parent) {
+            // debug!("{:?}", inode);
         }
-        // reply.error(ENOSPC);
-    }
-
-    fn mknod(
-        &mut self,
-        _req: &Request<'_>,
-        parent: u64,
-        name: &OsStr,
-        mode: u32,
-        umask: u32,
-        rdev: u32,
-        reply: ReplyEntry,
-    ) {
-        debug!(
-            "Filesystem::mknod(parent: {}, name: {:?}, mode: {}, umask: {}, rdev: {})",
-            parent, name, mode, umask, rdev
-        );
-        reply.error(ENOSPC);
+        // if self.inode_active(parent) {
+        //     let (block, offset) = self.locate_inode(parent);
+        //     let inode = self.get_inode_2(block, offset);
+        //     debug!("{:?}", inode);
+        // }
+        reply.error(ENOENT);
     }
 
     fn forget(&mut self, _req: &Request<'_>, _ino: u64, _nlookup: u64) {
@@ -438,7 +519,7 @@ impl Filesystem for MyFS {
     fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) {
         debug!("Filesystem::getattr(ino: {})", ino);
         let ino = ino as usize;
-        if let Some(inode) = self.get_inode(ino) {
+        if let Some(inode) = self.get_inode_2(ino) {
             // debug!("{:?}", inode);
         }
         reply.error(ENOENT);
@@ -475,60 +556,41 @@ impl Filesystem for MyFS {
         reply.error(ENOSYS);
     }
 
-    fn lseek(
+    fn mknod(
         &mut self,
         _req: &Request<'_>,
-        ino: u64,
-        fh: u64,
-        offset: i64,
-        whence: i32,
-        reply: ReplyLseek,
+        parent: u64,
+        name: &OsStr,
+        mode: u32,
+        umask: u32,
+        rdev: u32,
+        reply: ReplyEntry,
     ) {
         debug!(
-            "lseek(ino: {:#x?}, fh: {}, offset: {}, whence: {})",
-            ino, fh, offset, whence
+            "Filesystem::mknod(parent: {}, name: {:?}, mode: {}, umask: {}, rdev: {})",
+            parent, name, mode, umask, rdev
         );
-        reply.error(ENOSYS);
+        reply.error(ENOSPC);
     }
 
-    fn copy_file_range(
+    fn mkdir(
         &mut self,
         _req: &Request<'_>,
-        ino_in: u64,
-        fh_in: u64,
-        offset_in: i64,
-        ino_out: u64,
-        fh_out: u64,
-        offset_out: i64,
-        len: u64,
-        flags: u32,
-        reply: ReplyWrite,
+        parent: u64,
+        name: &OsStr,
+        mode: u32,
+        umask: u32,
+        reply: ReplyEntry,
     ) {
         debug!(
-            "copy_file_range(ino_in: {:#x?}, fh_in: {}, \
-            offset_in: {}, ino_out: {:#x?}, fh_out: {}, offset_out: {}, \
-            len: {}, flags: {})",
-            ino_in, fh_in, offset_in, ino_out, fh_out, offset_out, len, flags
-        );
-        reply.error(ENOSYS);
-    }
-
-    fn lookup(&mut self, _req: &Request<'_>, parent: u64, name: &OsStr, reply: ReplyEntry) {
-        debug!(
-            "Filesystem::lookup called with parent {} name {}",
-            parent,
-            name.to_str().unwrap()
+            "Filesystem::mkdir(parent: {}, name: {:?}, mode: {}, umask: {})",
+            parent, name, mode, umask
         );
-        let parent = parent as usize;
-        if let Some(inode) = self.get_inode(parent) {
-            // debug!("{:?}", inode);
+        if let Some(inode) = self.get_inode_2(parent as usize) {
+        } else {
+            reply.error(ENOENT);
         }
-        // if self.inode_active(parent) {
-        //     let (block, offset) = self.locate_inode(parent);
-        //     let inode = self.get_inode(block, offset);
-        //     debug!("{:?}", inode);
-        // }
-        reply.error(ENOENT);
+        // reply.error(ENOSPC);
     }
 
     fn read(
@@ -555,6 +617,53 @@ impl Filesystem for MyFS {
     ) {
         todo!()
     }
+
+    fn access(&mut self, _req: &Request<'_>, ino: u64, mask: i32, reply: ReplyEmpty) {
+        debug!("Filesystem::getattr(ino: {}, mask: {})", ino, mask);
+        if let Some(inode) = self.get_inode_2(ino as usize) {
+            reply.ok()
+        } else {
+            reply.error(ENOENT)
+        }
+    }
+
+    fn lseek(
+        &mut self,
+        _req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        offset: i64,
+        whence: i32,
+        reply: ReplyLseek,
+    ) {
+        debug!(
+            "lseek(ino: {:#x?}, fh: {}, offset: {}, whence: {})",
+            ino, fh, offset, whence
+        );
+        reply.error(ENOSYS);
+    }
+
+    fn copy_file_range(
+        &mut self,
+        _req: &Request<'_>,
+        ino_in: u64,
+        fh_in: u64,
+        offset_in: i64,
+        ino_out: u64,
+        fh_out: u64,
+        offset_out: i64,
+        len: u64,
+        flags: u32,
+        reply: ReplyWrite,
+    ) {
+        debug!(
+            "copy_file_range(ino_in: {:#x?}, fh_in: {}, \
+            offset_in: {}, ino_out: {:#x?}, fh_out: {}, offset_out: {}, \
+            len: {}, flags: {})",
+            ino_in, fh_in, offset_in, ino_out, fh_out, offset_out, len, flags
+        );
+        reply.error(ENOSYS);
+    }
 }
 
 fn main() {