Add dir entry operations

8 files changed, 301 insertions, 272 deletions

diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs
index bde2014..57cca0e 100644
--- a/src/disk/allocation.rs
+++ b/src/disk/allocation.rs
@@ -1,20 +1,20 @@
-use crate::disk::block::{DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
-use crate::disk::inode::Inode;
-use crate::memory::cached_block::convert;
-use crate::AyaFS;
+use crate::disk::block::{Block, DataBlock, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
+use crate::disk::inode::{DIRECT_NUMBER, Inode};
+use crate::memory::cached_block::{CachedBlock, convert};
+use crate::{AyaFS, INODE_PER_BLOCK};
 
 impl AyaFS {
-    /// 为 Inode 分配新 block, 返回 block 的编号
-    pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<u32> {
+    /// 为 Inode 分配新 block, 返回 block 的编号和它在 inode 内的编号
+    pub(crate) fn allocate_block_for(&mut self, inode: &mut Inode) -> Option<(u32, usize)> {
         // 先看这个 inode 的 direct block 有没有空闲
-        for index in inode.direct.iter_mut() {
+        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;
                 // 当调用 get_inode_mut 拿出 &mut Inode 的时候对应的 block 在 cache 里已经脏了
-                return Some(block_index);
+                return Some((block_index, index_within_direct));
             }
         }
 
@@ -27,10 +27,11 @@ impl AyaFS {
             // println!("allocating {} for indirect", inode.single_indirect);
         }
         // 在 indirect block 里尝试分配
-        if let Some(block_index) = self.allocate_in_indirect(inode.single_indirect) {
+        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;
-            return Some(block_index);
+            let index_within_block = DIRECT_NUMBER + index_within_indirect;
+            return Some((block_index, index_within_block));
         }
 
         // direct & indirect block 全部分配完了, 先检查 double indirect block 有没有分配, 没有就分配一个
@@ -42,10 +43,11 @@ impl AyaFS {
             // println!("allocating {} for double indirect", inode.double_indirect);
         }
         // 在 double indirect block 里尝试分配
-        if let Some(block_index) = self.alloc_in_double_indirect(inode.double_indirect) {
+        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;
-            return Some(block_index);
+            let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + index_within_double;
+            return Some((block_index, index_within_block));
         }
 
         // direct, indirect & double indirect block 全部分配完了, 先检查 triple indirect block 有没有分配, 没有就分配一个
@@ -57,15 +59,16 @@ impl AyaFS {
             // println!("allocating {} for triple indirect", inode.triple_indirect);
         }
         // 在 double indirect block 里尝试分配
-        if let Some(block_index) = self.alloc_in_triple_indirect(inode.triple_indirect) {
+        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;
-            return Some(block_index);
+            let index_within_block = DIRECT_NUMBER + INODE_PER_BLOCK + INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_triple;
+            return Some((block_index, index_within_block));
         }
         None
     }
 
-    fn allocate_in_indirect(&mut self, indirect_entry: u32) -> Option<u32> {
+    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));
@@ -76,20 +79,20 @@ impl AyaFS {
         {
             // println!("found indirect block with number {}", indirect_entry);
             let mut indirect_block = block.clone();
-            for entry in indirect_block.block.entries.iter_mut() {
+            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;
                     *entry = block_index;
                     self.update_block(indirect_block);
-                    return Some(block_index);
+                    return Some((block_index, index_within_indirect));
                 }
             }
         }
         None
     }
 
-    fn alloc_in_double_indirect(&mut self, double_indirect_entry: u32) -> Option<u32> {
+    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
@@ -97,24 +100,27 @@ impl AyaFS {
             .map(convert::<DataBlock, DoubleIndirectBlock>)
         {
             let mut double_indirect_block = block.clone();
-            for indirect_entry in double_indirect_block.block.indirect.iter_mut() {
+            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;
                     *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 {
+                if let Some((block_index, index_within_indirect)) = self.allocate_in_indirect(*indirect_entry) {
+                    if double_indirect_modified {
                         self.update_block(double_indirect_block);
                     }
-                    return Some(block_index);
+                    let index_within_double = index_within_double_indirect * INODE_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> {
+    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
@@ -122,17 +128,20 @@ impl AyaFS {
             .map(convert::<DataBlock, TripleIndirectBlock>)
         {
             let mut triple_indirect_block = block.clone();
-            for double_indirect_entry in triple_indirect_block.block.double_indirect.iter_mut() {
+            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;
                     *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 {
+                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);
                     }
-                    return Some(block_index);
+                    let index_within_triple = index_within_triple_indirect * INODE_PER_BLOCK * INODE_PER_BLOCK + index_within_double_indirect;
+                    return Some((block_index, index_within_triple));
                 }
             }
         }
@@ -283,3 +292,99 @@ impl AyaFS {
         None
     }
 }
+
+impl AyaFS {
+    fn get_block_index(&mut self, inode: &Inode, mut block_index_within_inode: usize) -> Option<usize> {
+        // direct block
+        if block_index_within_inode < DIRECT_NUMBER {
+            let block_index = inode.direct[block_index_within_inode] as usize;
+            return Some(block_index);
+        } else {
+            block_index_within_inode -= DIRECT_NUMBER;
+        }
+
+        // indirect block
+        let indirect_number = INODE_PER_BLOCK;
+        if block_index_within_inode < indirect_number {
+            return if let Some(indirect_block) =
+                self.get_block::<IndirectBlock>(inode.single_indirect as usize)
+            {
+                let block_index = indirect_block.block.entries[block_index_within_inode] as usize;
+                Some(block_index)
+            } else {
+                None
+            };
+        } else {
+            block_index_within_inode -= indirect_number;
+        }
+
+        // double indirect block
+        let double_indirect_number = INODE_PER_BLOCK * INODE_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)
+            {
+                // 取出 double indirect block
+                let indirect_block_index = double_indirect_block.block.indirect
+                    [block_index_within_inode / INODE_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 % INODE_PER_BLOCK]
+                        as usize;
+                    // 拿到 DirectoryBlock 的 index
+                    return Some(block_index)
+                }
+            }
+            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 / (INODE_PER_BLOCK * INODE_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 % (INODE_PER_BLOCK * INODE_PER_BLOCK)
+                    / INODE_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 % INODE_PER_BLOCK]
+                        as usize;
+                    // DirectoryBlock 的 index
+                    return Some(block_index)
+                }
+            }
+        }
+
+        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| {
+                self.get_block_mut::<T>(block_index).unwrap() // 可以 unwrap 吧这里 ??
+            })
+    }
+}
\ No newline at end of file
diff --git a/src/disk/block.rs b/src/disk/block.rs
index 0058b3e..be3d85a 100644
--- a/src/disk/block.rs
+++ b/src/disk/block.rs
@@ -49,7 +49,7 @@ impl Default for InodeBlock {
 
 impl Block for InodeBlock {}
 
-const FULL_MAP: u32 = 0b111_111_111_111_111;
+const FULL_MAP: u16 = 0b111_111_111_111_111;
 
 #[repr(C)]
 #[derive(Clone)]
@@ -84,7 +84,8 @@ impl Default for DirectoryEntry {
 #[derive(Clone)]
 pub struct DirectoryBlock {
     pub entries: [DirectoryEntry; 15],
-    reserved: [u8; 136],
+    pub occupancy: [u8; 2],
+    reserved: [u8; 134],
 }
 
 impl Default for DirectoryBlock {
@@ -107,7 +108,50 @@ impl Default for DirectoryBlock {
                 DirectoryEntry::default(),
                 DirectoryEntry::default(),
             ],
-            reserved: [0xFF; 136],
+            occupancy: [0x80, 0x00], // 0b1000_0000
+            reserved: [0xFF; 134],
+        }
+    }
+}
+
+impl DirectoryBlock {
+    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) -> 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);
         }
     }
 }
diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs
index c533c41..73ae878 100644
--- a/src/filesystem/trait_impl.rs
+++ b/src/filesystem/trait_impl.rs
@@ -46,7 +46,7 @@ impl Filesystem for AyaFS {
             ) {
                 let parent_inode = parent_inode.clone();
                 match self.lookup_name(&parent_inode, name) {
-                    Ok((inode_index, inode)) => {
+                    Ok((inode_index, _, inode)) => {
                         let attr = to_fileattr(inode_index as usize, &inode);
                         reply.entry(&TTL, &attr, 0);
                     },
diff --git a/src/memory/cached_block.rs b/src/memory/cached_block.rs
index 77cdf61..783e987 100644
--- a/src/memory/cached_block.rs
+++ b/src/memory/cached_block.rs
@@ -70,6 +70,7 @@ impl<T: Block> BlockCache<T> {
     }
 
     /// 从 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);
@@ -78,11 +79,15 @@ impl<T: Block> BlockCache<T> {
     }
 
     /// 从 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(convert_mut::<T, U>)
+        self.cache.get_mut(&index).map(|block| {
+            block.dirty = true;
+            convert_mut::<T, U>(block)
+        })
     }
 
     /// 从 LRU cache 中读取一个 block 的引用, *不会* 影响 LRU cache 的结构, 如果没有在 cache 中不会加载.
@@ -97,7 +102,8 @@ impl<T: Block> BlockCache<T> {
 
     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();
+            let mut data_block = convert::<U, T>(&block).clone();
+            data_block.dirty = true; // TODO 需要把显式写回的都标记为 dirty 吗
             self.cache.push(block.index, data_block);
             true
         } else {
@@ -123,25 +129,29 @@ impl AyaFS {
     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))
+            .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>> {
         self.data_bitmap
             .query(index)
-            .and_then(|| self.cached_blocks.get_block_mut::<T>(index))
+            .then(|| self.cached_blocks.get_block_mut::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
     }
 
     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))
+            .then(|| self.cached_blocks.peek_block::<T>(index).unwrap())
+        // 返回 None 当且仅当 data_bitmap 中这个 block 为 invalid
     }
 
     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))
+            .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 {
diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs
index be87850..b1be2de 100644
--- a/src/memory/cached_inode.rs
+++ b/src/memory/cached_inode.rs
@@ -34,7 +34,7 @@ impl AyaFS {
             let mut new_inode =
                 Inode::directory(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0);
             // 分配第一个 direct block
-            new_inode.direct[0] = self.allocate_block_for(&mut new_inode).unwrap();
+            (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap();
             new_inode.size = 2;
             // 在 direct block 里分配 . 和 ..
             if let Some(directory_block) =
diff --git a/src/memory/dir_entry.rs b/src/memory/dir_entry.rs
new file mode 100644
index 0000000..0ade23f
--- /dev/null
+++ b/src/memory/dir_entry.rs
@@ -0,0 +1,103 @@
+use std::ffi::OsStr;
+use std::os::unix::ffi::OsStrExt;
+use libc::{c_int, ENOENT, ENOSPC};
+use crate::disk::block::{DirectoryBlock, DirectoryEntry};
+use crate::disk::inode::{Inode};
+use crate::AyaFS;
+
+impl AyaFS {
+    pub(crate) fn remove_direntry(
+        &mut self,
+        parent_inode: &mut Inode,
+        entry_index: u32
+    ) -> Result<(), c_int> {
+        let block_index_within_inode = (entry_index / 15) as usize;
+        let entry_index_within_block = (entry_index % 15) as usize;
+
+        match self.access_block_mut::<DirectoryBlock>(parent_inode, block_index_within_inode) {
+            Some(directory_block) => {
+                if directory_block.block.query(entry_index_within_block) {
+                    directory_block.block.deallocate(entry_index_within_block);
+                    directory_block.block.entries[entry_index_within_block] = DirectoryEntry::default();
+                    Ok(())
+                } else {
+                    Err(ENOENT)
+                }
+            }
+            None => Err(ENOENT),
+        }
+    }
+
+    pub(crate) fn add_direntry(
+        &mut self,
+        parent_inode: &mut Inode,
+        child_inode_index: u32,
+        child_inode_name: &OsStr,
+        child_inode: &Inode,
+    ) -> Result<u32, c_int> {
+        // 找到第一个有空闲 DirEntry 的块, 从中分配一个 entry
+        let mut block_index_within_inode: usize = 0;
+        loop {
+            // 所有已经分配的块都用完, 需要额外分配一个块了
+            if block_index_within_inode as u32 == parent_inode.n_blocks {
+                if self.allocate_block_for(parent_inode).is_none() {
+                    return Err(ENOSPC);
+                }
+            }
+            // 寻找当前块里有没有空闲空间
+            if let Some(directory_block) = self.access_block_mut::<DirectoryBlock>(parent_inode, block_index_within_inode) {
+                if let Some(entry_index_within_block) = directory_block.block.allocate() {
+                    // 如果有空闲空间, 可以分配一个块
+                    let name_len = child_inode_name.len() as u8;
+                    let file_type = child_inode.mode.into();
+                    let mut name = [0u8; 256];
+                    name.copy_from_slice(child_inode_name.as_bytes());
+
+                    let dir_entry = DirectoryEntry {
+                        inode: child_inode_index,
+                        record_len: 264,
+                        name_len,
+                        file_type,
+                        name,
+                    };
+                    directory_block.block.entries[entry_index_within_block] = dir_entry;
+                    let entry_index = block_index_within_inode * 15 + entry_index_within_block;
+                    return Ok(entry_index as u32);
+                }
+            }
+            block_index_within_inode += 1;
+        };
+    }
+    pub(crate) fn get_direntry(
+        &mut self,
+        parent_inode: &Inode,
+        entry_index: u32
+    ) -> Option<DirectoryEntry> {
+        let block_index_within_inode = (entry_index / 15) as usize;
+        let entry_index_within_block = (entry_index % 15) as usize;
+
+        self.access_block::<DirectoryBlock>(parent_inode, block_index_within_inode)
+            .and_then(|directory_block| {
+                if directory_block.block.query(entry_index_within_block) {
+                    Some(directory_block.block.entries[entry_index_within_block].clone())
+                } else {
+                    None
+                }
+            })
+    }
+
+    // TODO 实现一个带 cache 的版本
+    pub fn lookup_name(&mut self, parent_inode: &Inode, name: &OsStr) -> Result<(u32, u32, Inode), c_int> {
+        let mut entry_index = 0;
+        while entry_index < parent_inode.size {
+            if let Some(entry) = self.get_direntry(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/src/memory/inode_iter.rs b/src/memory/inode_iter.rs
deleted file mode 100644
index d5909bc..0000000
--- a/src/memory/inode_iter.rs
+++ /dev/null
@@ -1,233 +0,0 @@
-use std::ffi::OsStr;
-use std::os::unix::ffi::OsStrExt;
-use libc::{c_int, ENOENT, ENOSPC};
-use crate::disk::block::{Block, DirectoryBlock, DirectoryEntry, DoubleIndirectBlock, IndirectBlock, TripleIndirectBlock};
-use crate::disk::inode::{Inode, DIRECT_NUMBER};
-use crate::{AyaFS, INODE_PER_BLOCK};
-use crate::memory::cached_block::CachedBlock;
-
-impl AyaFS {
-    pub(crate) fn access_block<T: Block>(&mut self, inode: &Inode, mut block_index_within_inode: usize) -> Option<&CachedBlock<T>> {
-        // direct block
-        if block_index_within_inode < DIRECT_NUMBER {
-            let block_index = inode.direct[block_index_within_inode] as usize;
-            return self.get_block::<T>(block_index);
-        } else {
-            block_index_within_inode -= DIRECT_NUMBER;
-        }
-
-        // indirect block
-        let indirect_number = INODE_PER_BLOCK;
-        if block_index_within_inode < indirect_number {
-            return if let Some(indirect_block) =
-                self.get_block::<IndirectBlock>(inode.single_indirect as usize)
-            {
-                let block_index = indirect_block.block.entries[block_index_within_inode] as usize;
-                self.get_block::<T>(block_index)
-            } else {
-                None
-            };
-        } else {
-            block_index_within_inode -= indirect_number;
-        }
-
-        // double indirect block
-        let double_indirect_number = INODE_PER_BLOCK * INODE_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)
-            {
-                // 取出 double indirect block
-                let indirect_block_index = double_indirect_block.block.indirect
-                    [block_index_within_inode / INODE_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 % INODE_PER_BLOCK]
-                        as usize;
-                    // 拿到 DirectoryBlock 的 index
-                    return self.get_block::<T>(block_index);
-                }
-            }
-            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 / (INODE_PER_BLOCK * INODE_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 % (INODE_PER_BLOCK * INODE_PER_BLOCK)
-                    / INODE_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 % INODE_PER_BLOCK]
-                        as usize;
-                    // DirectoryBlock 的 index
-                    return self.get_block::<T>(block_index);
-                }
-            }
-        }
-
-        None
-    }
-
-    pub(crate) fn add_direntry(
-        &mut self,
-        parent_inode: &mut Inode,
-        child_inode_index: u32,
-        child_inode_name: &OsStr,
-        child_inode: &Inode,
-    ) -> Result<u32, c_int> {
-        let entry_index = parent_inode.size;
-        let block_index_within_inode = (entry_index / 15) as usize;
-        let entry_index_within_block = (entry_index % 15) as usize;
-
-        // TODO 如果 block 内 offset 是 0 （或者访问到 block_index_within_inode 无效?）则为 Inode 分配新的 block
-
-        // TODO 把新的 entry 写到对应位置
-
-        Err(ENOSPC)
-    }
-    pub(crate) fn get_direntry(
-        &mut self,
-        inode: &Inode,
-        entry_index: u32
-    ) -> Option<DirectoryEntry> {
-        let block_index_within_inode = (entry_index / 15) as usize;
-        let entry_index_within_block = (entry_index % 15) as usize;
-
-        self.access_block::<DirectoryBlock>(inode, block_index_within_inode)
-            .map(|directory_block| {
-                directory_block.block.entries[entry_index_within_block].clone()
-            })
-    }
-
-    // pub(crate) fn get_direntry(
-    //     &mut self,
-    //     inode: &Inode,
-    //     entry_index: u32,
-    // ) -> Option<DirectoryEntry> {
-    //     // 每个 DirectoryBlock 里有 15 个 entry, 先确定 block 再确定 offset
-    //     let mut block_index_within_inode = (entry_index / 15) as usize;
-    //     let entry_index_within_block = (entry_index % 15) as usize;
-    //
-    //     // direct block
-    //     if block_index_within_inode < DIRECT_NUMBER {
-    //         let block_index = inode.direct[block_index_within_inode] as usize;
-    //         return self
-    //             .get_block::<DirectoryBlock>(block_index)
-    //             .map(|inode_block| inode_block.block.entries[entry_index_within_block].clone());
-    //     } else {
-    //         block_index_within_inode -= DIRECT_NUMBER;
-    //     }
-    //
-    //     // indirect block
-    //     let indirect_number = INODE_PER_BLOCK;
-    //     if block_index_within_inode < indirect_number {
-    //         return if let Some(indirect_block) =
-    //             self.get_block::<IndirectBlock>(inode.single_indirect as usize)
-    //         {
-    //             let block_index = indirect_block.block.entries[block_index_within_inode] as usize;
-    //             self.get_block::<DirectoryBlock>(block_index)
-    //                 .map(|inode_block| inode_block.block.entries[entry_index_within_block].clone())
-    //         } else {
-    //             None
-    //         };
-    //     } else {
-    //         block_index_within_inode -= indirect_number;
-    //     }
-    //
-    //     // double indirect block
-    //     let double_indirect_number = INODE_PER_BLOCK * INODE_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)
-    //         {
-    //             // 取出 double indirect block
-    //             let indirect_block_index = double_indirect_block.block.indirect
-    //                 [block_index_within_inode / INODE_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 % INODE_PER_BLOCK]
-    //                     as usize;
-    //                 // 拿到 DirectoryBlock 的 index
-    //                 return self
-    //                     .get_block::<DirectoryBlock>(block_index)
-    //                     .map(|inode_block| {
-    //                         inode_block.block.entries[entry_index_within_block].clone()
-    //                     });
-    //             }
-    //         }
-    //         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 / (INODE_PER_BLOCK * INODE_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 % (INODE_PER_BLOCK * INODE_PER_BLOCK)
-    //                     / INODE_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 % INODE_PER_BLOCK]
-    //                     as usize;
-    //                 // DirectoryBlock 的 index
-    //                 return self
-    //                     .get_block::<DirectoryBlock>(block_index)
-    //                     .map(|inode_block| {
-    //                         inode_block.block.entries[entry_index_within_block].clone()
-    //                     });
-    //             }
-    //         }
-    //     }
-    //     None
-    // }
-
-    // TODO 实现一个带 cache 的版本
-    pub fn lookup_name(&mut self, parent_inode: &Inode, name: &OsStr) -> Result<(u32, Inode), c_int> {
-        let mut entry_index = 0;
-        while entry_index < parent_inode.size {
-            if let Some(entry) = self.get_direntry(parent_inode, entry_index) {
-                if entry.name() == name {
-                    let inode = self.get_inode(entry.inode as usize).unwrap().clone();
-                    return Ok((entry.inode, inode))
-                }
-            }
-            entry_index += 1;
-        }
-        Err(ENOENT)
-    }
-}
diff --git a/src/memory/mod.rs b/src/memory/mod.rs
index dce7c42..4080114 100644
--- a/src/memory/mod.rs
+++ b/src/memory/mod.rs
@@ -2,4 +2,4 @@
 /// This is where the crucial block and inode methods presented to upper calls implemented.
 pub mod cached_block;
 pub mod cached_inode;
-mod inode_iter;
+mod dir_entry;