Fix directory stuff

11 files changed, 561 insertions, 176 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 4b0f09f..bcb2183 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -161,6 +161,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "equivalent"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5"
+
+[[package]]
 name = "errno"
 version = "0.3.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -214,6 +220,16 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "9a3a5bfb195931eeb336b2a7b4d761daec841b97f947d34394601737a7bba5e4"
 
 [[package]]
+name = "indexmap"
+version = "2.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d530e1a18b1cb4c484e6e34556a0d948706958449fca0cab753d649f2bce3d1f"
+dependencies = [
+ "equivalent",
+ "hashbrown",
+]
+
+[[package]]
 name = "is-terminal"
 version = "0.4.9"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -266,6 +282,7 @@ dependencies = [
  "clap",
  "env_logger",
  "fuser",
+ "indexmap",
  "libc",
  "log",
  "lru",
diff --git a/Cargo.toml b/Cargo.toml
index f807e96..8cc9696 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,6 +11,7 @@ bitflags = "2.4.0"
 clap = { version = "4.4.6", features = ["derive"] }
 env_logger = "0.10.0"
 fuser = "0.14.0"
+indexmap = "2.1.0"
 libc = "0.2.148"
 log = "0.4.20"
 lru = "0.12.0"
diff --git a/src/disk/allocation.rs b/src/disk/allocation.rs
index b88e7d5..a4bb3f7 100644
--- a/src/disk/allocation.rs
+++ b/src/disk/allocation.rs
@@ -398,7 +398,7 @@ impl AyaFS {
 }
 
 impl AyaFS {
-    fn get_block_index(
+    pub(crate) fn get_block_index(
         &mut self,
         inode: &Inode,
         mut block_index_within_inode: usize,
@@ -406,7 +406,11 @@ impl AyaFS {
         // direct block
         if block_index_within_inode < DIRECT_NUMBER {
             let block_index = inode.direct[block_index_within_inode] as usize;
-            return Some(block_index);
+            return if self.data_bitmap.query(block_index) {
+                Some(block_index)
+            } else {
+                None
+            };
         } else {
             block_index_within_inode -= DIRECT_NUMBER;
         }
@@ -418,7 +422,11 @@ impl AyaFS {
                 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)
+                if self.data_bitmap.query(block_index) {
+                    Some(block_index)
+                } else {
+                    None
+                }
             } else {
                 None
             };
@@ -443,7 +451,11 @@ impl AyaFS {
                         [block_index_within_inode % INODE_PER_BLOCK]
                         as usize;
                     // 拿到 DirectoryBlock 的 index
-                    return Some(block_index);
+                    return if self.data_bitmap.query(block_index) {
+                        Some(block_index)
+                    } else {
+                        None
+                    };
                 }
             }
             return None;
@@ -474,7 +486,11 @@ impl AyaFS {
                         [block_index_within_inode % INODE_PER_BLOCK]
                         as usize;
                     // DirectoryBlock 的 index
-                    return Some(block_index);
+                    return if self.data_bitmap.query(block_index) {
+                        Some(block_index)
+                    } else {
+                        None
+                    };
                 }
             }
         }
diff --git a/src/filesystem/trait_impl.rs b/src/filesystem/trait_impl.rs
index 636bae7..5353f6e 100644
--- a/src/filesystem/trait_impl.rs
+++ b/src/filesystem/trait_impl.rs
@@ -6,11 +6,12 @@ use crate::{AyaFS, TTL};
 use fuser::TimeOrNow::{Now, SpecificTime};
 use fuser::{
     Filesystem, KernelConfig, ReplyAttr, ReplyData, ReplyDirectory, ReplyEmpty, ReplyEntry,
-    ReplyLseek, ReplyOpen, Request, TimeOrNow,
+    ReplyLseek, ReplyOpen, ReplyWrite, Request, TimeOrNow,
 };
 use libc::{
-    c_int, EACCES, EEXIST, EISDIR, ENAMETOOLONG, ENOENT, ENOSPC, ENOSYS, ENOTDIR, EPERM, R_OK,
-    S_ISGID, S_ISUID, S_IXGRP, S_IXOTH, S_IXUSR, W_OK,
+    c_int, EACCES, EBADF, EEXIST, EINVAL, EISDIR, ENAMETOOLONG, ENOENT, ENOSPC, ENOSYS, ENOTDIR,
+    ENOTEMPTY, EPERM, O_ACCMODE, O_RDONLY, O_RDWR, O_WRONLY, R_OK, S_ISGID, S_ISUID, S_IXGRP,
+    S_IXOTH, S_IXUSR, W_OK,
 };
 use log::debug;
 use std::ffi::OsStr;
@@ -46,7 +47,7 @@ impl Filesystem for AyaFS {
                 R_OK,
             ) {
                 let parent_inode = parent_inode.clone();
-                match self.lookup_name(&parent_inode, name) {
+                match self.lookup_name(parent, &parent_inode, name) {
                     Ok((inode_index, _, inode)) => {
                         let attr = to_fileattr(inode_index as usize, &inode);
                         reply.entry(&TTL, &attr, 0);
@@ -62,7 +63,6 @@ impl Filesystem for AyaFS {
     }
 
     fn getattr(&mut self, _req: &Request<'_>, ino: u64, reply: ReplyAttr) {
-        debug!("Filesystem::getattr(ino: {})", ino);
         if let Some(inode) = self.get_inode(ino as usize) {
             reply.attr(&TTL, &to_fileattr(ino as usize, inode));
         } else {
@@ -284,7 +284,10 @@ impl Filesystem for AyaFS {
 
             let mut parent_inode = parent_inode.clone();
             // 如果已经存在, 返回 already exists
-            if self.lookup_name(&parent_inode, name).is_ok() {
+            if self
+                .lookup_name(parent as usize, &parent_inode, name)
+                .is_ok()
+            {
                 reply.error(EEXIST);
                 return;
             }
@@ -295,9 +298,13 @@ impl Filesystem for AyaFS {
             {
                 let child_inode = child_inode.clone();
                 let file_attr = to_fileattr(child_inode_index, &child_inode);
-                if let Err(err_code) =
-                    self.add_direntry(&mut parent_inode, child_inode_index, name, &child_inode)
-                {
+                if let Err(err_code) = self.add_direntry(
+                    parent as usize,
+                    &mut parent_inode,
+                    child_inode_index,
+                    name,
+                    child_inode.mode.into(),
+                ) {
                     reply.error(err_code);
                     return;
                 }
@@ -350,20 +357,27 @@ impl Filesystem for AyaFS {
 
             let mut parent_inode = parent_inode.clone();
             // 已经存在 -> File exists
-            if self.lookup_name(&parent_inode, name).is_ok() {
+            if self
+                .lookup_name(parent as usize, &parent_inode, name)
+                .is_ok()
+            {
                 reply.error(EEXIST);
                 return;
             }
 
             let mode = mode as u16;
             if let Some((child_inode_index, child_inode)) =
-                self.create_directory(mode, req.uid(), req.gid(), 0, Some(parent as u32))
+                self.create_directory(mode, req.uid(), req.gid(), 0, Some(parent as usize))
             {
                 let child_inode = child_inode.clone();
                 let file_attr = to_fileattr(child_inode_index, &child_inode);
-                if let Err(err_code) =
-                    self.add_direntry(&mut parent_inode, child_inode_index, name, &child_inode)
-                {
+                if let Err(err_code) = self.add_direntry(
+                    parent as usize,
+                    &mut parent_inode,
+                    child_inode_index,
+                    name,
+                    child_inode.mode.into(),
+                ) {
                     reply.error(err_code);
                     return;
                 }
@@ -409,7 +423,8 @@ impl Filesystem for AyaFS {
 
             let mut parent_inode = parent_inode.clone();
             // 不存在 -> No such file or directory
-            if let Ok((inode_index, entry_index, mut inode)) = self.lookup_name(&parent_inode, name)
+            if let Ok((inode_index, entry_index, mut inode)) =
+                self.lookup_name(parent as usize, &parent_inode, name)
             {
                 let inode_index = inode_index as usize;
                 // 要删除的 entry 是目录, 不能用 unlink
@@ -417,15 +432,10 @@ impl Filesystem for AyaFS {
                     reply.error(EISDIR);
                     return;
                 }
-                // 删除 dir entry
-                if let Err(err_code) = self.remove_direntry(&mut parent_inode, entry_index) {
-                    reply.error(err_code);
-                    return;
-                }
-                // inode 的 n_links 减 1
+
                 inode.n_links -= 1;
                 if inode.n_links == 0 {
-                    // 释放块的操作在 remove file 里实现了
+                    // n_links == 0 -> 整个 inode 都要删除掉
                     match self.remove_file(inode_index) {
                         Ok(flag) => debug!("  unlink {}", flag),
                         Err(err_code) => {
@@ -434,8 +444,17 @@ impl Filesystem for AyaFS {
                         }
                     }
                 } else {
+                    // n_links > 0 -> 只是移除了一个 hard link, 将改动写回
                     self.update_inode(inode_index, inode);
                 }
+
+                // 删除 dir entry
+                if let Err(err_code) =
+                    self.remove_direntry(parent as usize, &mut parent_inode, name, entry_index)
+                {
+                    reply.error(err_code);
+                    return;
+                }
                 reply.ok();
             } else {
                 reply.error(ENOENT);
@@ -475,7 +494,8 @@ impl Filesystem for AyaFS {
 
             let mut parent_inode = parent_inode.clone();
             // 不存在 -> No such file or directory
-            if let Ok((inode_index, entry_index, mut inode)) = self.lookup_name(&parent_inode, name)
+            if let Ok((inode_index, entry_index, inode)) =
+                self.lookup_name(parent as usize, &parent_inode, name)
             {
                 let inode_index = inode_index as usize;
                 // 要删除的 entry 是一般文件, 不用 rmdir
@@ -484,11 +504,10 @@ impl Filesystem for AyaFS {
                     return;
                 }
 
-                // TODO 检查待删除的 dir 是 empty 的
-
-                // 删除 dir entry
-                if let Err(err_code) = self.remove_direntry(&mut parent_inode, entry_index) {
-                    reply.error(err_code);
+                // 一定有 . 和 .. 所以 size == 2 就是空目录
+                // 目录非空 -> ENOTEMPTY
+                if inode.size > 2 {
+                    reply.error(ENOTEMPTY);
                     return;
                 }
 
@@ -501,6 +520,14 @@ impl Filesystem for AyaFS {
                     }
                 }
 
+                // 删除 dir entry
+                if let Err(err_code) =
+                    self.remove_direntry(parent as usize, &mut parent_inode, name, entry_index)
+                {
+                    reply.error(err_code);
+                    return;
+                }
+
                 reply.ok();
             } else {
                 reply.error(ENOENT);
@@ -510,6 +537,10 @@ impl Filesystem for AyaFS {
         }
     }
 
+    fn open(&mut self, _req: &Request<'_>, _ino: u64, _flags: i32, reply: ReplyOpen) {
+        todo!()
+    }
+
     fn read(
         &mut self,
         _req: &Request<'_>,
@@ -524,42 +555,111 @@ impl Filesystem for AyaFS {
         todo!()
     }
 
-    fn opendir(&mut self, _req: &Request<'_>, ino: u64, flags: i32, reply: ReplyOpen) {
-        debug!("OPENDIR ino {:#x} flags {}", ino, flags);
-        reply.opened(1, 0);
+    fn write(
+        &mut self,
+        _req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        offset: i64,
+        data: &[u8],
+        write_flags: u32,
+        flags: i32,
+        lock_owner: Option<u64>,
+        reply: ReplyWrite,
+    ) {
+        todo!()
+    }
+
+    fn release(
+        &mut self,
+        _req: &Request<'_>,
+        _ino: u64,
+        _fh: u64,
+        _flags: i32,
+        _lock_owner: Option<u64>,
+        _flush: bool,
+        reply: ReplyEmpty,
+    ) {
+        todo!()
+    }
+
+    fn opendir(&mut self, req: &Request<'_>, ino: u64, flags: i32, reply: ReplyOpen) {
+        debug!("opendir(ino: {:#x?}, flags: {:#x?})", ino, flags);
+        let (access_mask, read, write) = match flags & O_ACCMODE {
+            O_RDONLY => {
+                // Behavior is undefined, but most filesystems return EACCES
+                if flags & libc::O_TRUNC != 0 {
+                    reply.error(libc::EACCES);
+                    return;
+                }
+                (R_OK, true, false)
+            }
+            O_WRONLY => (W_OK, false, true),
+            O_RDWR => (R_OK | W_OK, true, true),
+            _ => {
+                // flag 非法
+                reply.error(EINVAL);
+                return;
+            }
+        };
+
+        match self.get_inode(ino as usize) {
+            Some(inode) => {
+                if !check_access(
+                    req.uid(),
+                    req.gid(),
+                    inode.uid,
+                    inode.gid,
+                    inode.mode,
+                    access_mask,
+                ) {
+                    reply.error(EACCES);
+                    return;
+                }
+                let fd = self.allocate_file_descriptor(ino as usize, read, write);
+                reply.opened(fd, 0);
+            }
+            None => {
+                reply.error(ENOENT);
+            }
+        }
     }
 
     fn readdir(
         &mut self,
         req: &Request<'_>,
         ino: u64,
-        _fh: u64, // 如果 invoke 它的 opendir 里有指定 fh, 那么这里会收到 fh 参数
+        fh: u64, // 如果 invoke 它的 opendir 里有指定 fh, 那么这里会收到 fh 参数
         offset: i64,
         mut reply: ReplyDirectory,
     ) {
+        assert_eq!(self.file_handle_map.get(&fh).unwrap().0, ino as usize);
         if let Some(inode) = self.get_inode(ino as usize) {
             if inode.is_dir() {
                 if check_access(req.uid(), req.gid(), inode.uid, inode.gid, inode.mode, R_OK) {
+                    debug!("reading dir entries from inode {:#x} with offset {}", ino, offset);
                     let inode = inode.clone();
-                    let mut entry_index = offset as u32;
 
-                    while let Some(dir_entry) = self.get_direntry(&inode, entry_index) {
-                        debug!("reading inode {:#x} index {}", ino, entry_index);
-                        if entry_index >= inode.size {
-                            break;
-                        }
-                        // 最开头应该添加 `.` 和 `..`, 但这件事应该在 mkdir 的时候就在 inode 里加好
-                        // reply.add 返回 true 说明 buffer 已满, 停止累加
+                    self.load_direntry_map(ino as usize, &inode).unwrap();
+                    for (entry_index, (name, dir_entry)) in self
+                        .dir_entry_map
+                        .get(&(ino as usize))
+                        .unwrap()
+                        .iter()
+                        .enumerate()
+                        .skip(offset as usize)
+                    {
+                        debug!("  entry {} from inode {:#x} with name {:?}", entry_index, dir_entry.inode, name);
                         if reply.add(
                             dir_entry.inode as u64,
-                            entry_index as i64,
-                            to_filetype(dir_entry.file_type).expect("file type should not be 0x0!"),
-                            dir_entry.name(),
+                            entry_index as i64 + 1,
+                            to_filetype(dir_entry.file_type).expect("not 0x0!"),
+                            name
                         ) {
                             break;
                         }
-                        entry_index += 1;
                     }
+
                     reply.ok();
                 } else {
                     reply.error(EACCES);
@@ -572,11 +672,28 @@ impl Filesystem for AyaFS {
         }
     }
 
+    fn releasedir(
+        &mut self,
+        _req: &Request<'_>,
+        ino: u64,
+        fh: u64,
+        _flags: i32,
+        reply: ReplyEmpty,
+    ) {
+        debug!("releasedir(ino: {:#x?}, fh: {}", ino, fh);
+        if self.file_handle_map.contains_key(&fh) {
+            self.file_handle_map.remove(&fh);
+            reply.ok();
+        } else {
+            reply.error(EBADF);
+        }
+    }
+
     fn access(&mut self, req: &Request<'_>, ino: u64, mask: i32, reply: ReplyEmpty) {
         // mask:
         // - 要么是 libc::F_OK (aka 0), 检查文件是否存在
         // - 要么是 libc::R_OK,libc::W_OK,libc::X_OK (aka 4/2/1) 构成的 bitmask, 检查是否有对应权限
-        debug!("Filesystem::getattr(ino: {}, mask: {})", ino, mask);
+        debug!("Filesystem::access(ino: {}, mask: {})", ino, mask);
 
         if let Some(inode) = self.get_inode(ino as usize) {
             if mask == libc::F_OK // 只要检查是否存在
diff --git a/src/main.rs b/src/main.rs
index 5d460fc..78f338a 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -7,12 +7,17 @@ mod utils;
 
 use clap::Parser;
 use fuser::MountOption;
+use indexmap::IndexMap;
 use log::debug;
+use lru::LruCache;
+use std::collections::HashMap;
+use std::ffi::OsString;
+use std::num::NonZeroUsize;
+use std::sync::atomic::AtomicU64;
 use std::sync::Arc;
 use std::time::Duration;
 
-use crate::disk::block::InodeBlock;
-use crate::disk::inode::InodeMode;
+use crate::disk::block::{DirectoryEntry, InodeBlock};
 use crate::memory::cached_block::BlockCache;
 use block_device::{memory_disk::MemoryDisk, BlockDevice, BLOCK_SIZE};
 use disk::bitmap::Bitmap;
@@ -61,6 +66,13 @@ struct AyaFS {
     inode_start_block: usize,
     data_start_block: usize,
 
+    next_file_handle: AtomicU64,
+    // file descriptor -> (inode index, read, write)
+    file_handle_map: HashMap<u64, (usize, bool, bool)>,
+
+    // inode index -> (index aware) hashmap that maps dir entry name to inode index
+    dir_entry_map: LruCache<usize, IndexMap<OsString, DirectoryEntry>>,
+
     cached_inodes: BlockCache<InodeBlock>,
     cached_blocks: BlockCache<DataBlock>,
 }
@@ -111,6 +123,12 @@ impl AyaFS {
                 + inode_bitmap_block_number
                 + inode_block_number
                 + 1,
+
+            next_file_handle: AtomicU64::new(3), // 0,1,2 are stdin, stdout and stderr
+            file_handle_map: HashMap::new(),
+
+            dir_entry_map: LruCache::new(NonZeroUsize::new(1024).unwrap()),
+
             cached_inodes: BlockCache::new(device.clone(), 1024),
             cached_blocks: BlockCache::new(device.clone(), 8192),
         };
diff --git a/src/memory/cached_inode.rs b/src/memory/cached_inode.rs
index aa4f5e3..a9c92f5 100644
--- a/src/memory/cached_inode.rs
+++ b/src/memory/cached_inode.rs
@@ -2,7 +2,7 @@ use crate::disk::block::{DirectoryBlock, DirectoryEntry, InodeBlock};
 use crate::disk::inode::{Inode, INODE_SIZE};
 use crate::{utils, AyaFS};
 use and_then_some::BoolExt;
-use libc::{c_int, EISDIR, ENOENT, ENOTDIR};
+use libc::{c_int, EISDIR, ENOENT, ENOTDIR, ENOTEMPTY};
 
 impl AyaFS {
     pub(crate) fn create_file(
@@ -27,41 +27,53 @@ impl AyaFS {
         uid: u32,
         gid: u32,
         flags: u32,
-        parent_inode_number: Option<u32>,
+        parent_inode_number: Option<usize>,
     ) -> Option<(usize, &Inode)> {
         self.inode_bitmap.allocate().map(|inode_index| {
             // 创建 Inode
             let mut new_inode =
                 Inode::directory(permissions, uid, gid, utils::time_now(), flags, 0, 0, 0);
-            // 分配第一个 direct block
-            (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap();
-            new_inode.size = 2;
-            // 在 direct block 里分配 . 和 ..
-            if let Some(directory_block) =
-                self.get_block_mut::<DirectoryBlock>(new_inode.direct[0] as usize)
-            {
-                let dot = '.'.to_ascii_lowercase() as u8;
-                // add dot entry
-                directory_block.block.entries[0] = DirectoryEntry {
-                    inode: inode_index as u32,
-                    record_len: 264,
-                    name_len: 1,
-                    file_type: 0x2,
-                    name: [0; 256],
-                };
-                directory_block.block.entries[0].name[0] = dot;
+            self.init_direntry_map(inode_index);
+            self.add_direntry(inode_index, &mut new_inode, inode_index, ".", 0x2)
+                .unwrap();
+            self.add_direntry(
+                inode_index,
+                &mut new_inode,
+                parent_inode_number.unwrap_or(inode_index),
+                "..",
+                0x2,
+            )
+            .unwrap();
 
-                // add dot dot entry
-                directory_block.block.entries[1] = DirectoryEntry {
-                    inode: parent_inode_number.unwrap_or(inode_index as u32),
-                    record_len: 264,
-                    name_len: 2,
-                    file_type: 0x2,
-                    name: [0; 256],
-                };
-                directory_block.block.entries[1].name[0] = dot;
-                directory_block.block.entries[1].name[1] = dot;
-            }
+            // // 分配第一个 direct block
+            // (new_inode.direct[0], _) = self.allocate_block_for(&mut new_inode).unwrap();
+            // new_inode.size = 2;
+            // // 在 direct block 里分配 . 和 ..
+            // if let Some(directory_block) =
+            //     self.get_block_mut::<DirectoryBlock>(new_inode.direct[0] as usize)
+            // {
+            //     let dot = '.'.to_ascii_lowercase() as u8;
+            //     // add dot entry
+            //     directory_block.block.entries[0] = DirectoryEntry {
+            //         inode: inode_index as u32,
+            //         record_len: 264,
+            //         name_len: 1,
+            //         file_type: 0x2,
+            //         name: [0; 256],
+            //     };
+            //     directory_block.block.entries[0].name[0] = dot;
+            //
+            //     // add dot dot entry
+            //     directory_block.block.entries[1] = DirectoryEntry {
+            //         inode: parent_inode_number.unwrap_or(inode_index as u32),
+            //         record_len: 264,
+            //         name_len: 2,
+            //         file_type: 0x2,
+            //         name: [0; 256],
+            //     };
+            //     directory_block.block.entries[1].name[0] = dot;
+            //     directory_block.block.entries[1].name[1] = dot;
+            // }
             // 把 inode 放到指定位置
             self.get_inode_mut(inode_index).map(|inode| {
                 *inode = new_inode;
@@ -70,10 +82,9 @@ impl AyaFS {
             (inode_index, self.get_inode(inode_index).unwrap())
         })
     }
-    
+
     pub(crate) fn remove_file(&mut self, inode_index: usize) -> Result<bool, c_int> {
         if self.inode_bitmap.query(inode_index) {
-            self.inode_bitmap.deallocate(inode_index);
             let (block_index, offset) = self.locate_inode(inode_index);
             if let Some(cached_block) = self.cached_inodes.get_block::<InodeBlock>(block_index) {
                 let inode = cached_block.block.inodes[offset / INODE_SIZE].clone();
@@ -82,23 +93,32 @@ impl AyaFS {
                 }
                 self.deallocate_all_blocks_for(&inode).unwrap();
             }
+            self.inode_bitmap.deallocate(inode_index);
             Ok(true)
         } else {
             Err(ENOENT)
         }
     }
-    
+
+    // 要删除的 inode 一定得是空的
     pub(crate) fn remove_dir(&mut self, inode_index: usize) -> Result<bool, c_int> {
         if self.inode_bitmap.query(inode_index) {
-            self.inode_bitmap.deallocate(inode_index);
             let (block_index, offset) = self.locate_inode(inode_index);
             if let Some(cached_block) = self.cached_inodes.get_block::<InodeBlock>(block_index) {
-                let inode = cached_block.block.inodes[offset / INODE_SIZE].clone();
+                let inode = &cached_block.block.inodes[offset / INODE_SIZE].clone();
                 if !inode.is_dir() {
+                    // 不是 dir -> ENOTDIR
                     return Err(ENOTDIR);
                 }
-                // TODO 递归删除所有下面的 direntry 里的 inode, 注意排除 . 和 ..
+                if inode.size > 2 {
+                    // 有 . 和 .. 以外的 entry -> ENOTEMPTY
+                    return Err(ENOTEMPTY);
+                }
+                // 销毁 inode 里的所有 block
+                self.deallocate_all_blocks_for(inode).unwrap();
             }
+            // 销毁 inode
+            self.inode_bitmap.deallocate(inode_index);
             Ok(true)
         } else {
             Err(ENOENT)
diff --git a/src/memory/dir_entry.rs b/src/memory/dir_entry.rs
index 2d961db..08a82c5 100644
--- a/src/memory/dir_entry.rs
+++ b/src/memory/dir_entry.rs
@@ -1,117 +1,275 @@
 use crate::disk::block::{DirectoryBlock, DirectoryEntry};
 use crate::disk::inode::Inode;
 use crate::AyaFS;
+use indexmap::IndexMap;
 use libc::{c_int, ENOENT, ENOSPC};
-use std::ffi::OsStr;
+use log::debug;
+use std::ffi::{OsStr, OsString};
 use std::os::unix::ffi::OsStrExt;
 
 impl AyaFS {
-    /// 删除所有的 dir entry, 递归
-    pub(crate) fn clear_direntry(&mut self, parent_inode: &mut Inode) -> Result<(), c_int> {
-        todo!()
+    pub(crate) fn init_direntry_map(&mut self, index: usize) {
+        let direntry_map: IndexMap<OsString, DirectoryEntry> = IndexMap::new();
+        if let Some((old_inode_index, old_dir_entry_map)) =
+            self.dir_entry_map.push(index, direntry_map)
+        {
+            if let Some(old_inode) = self.get_inode(old_inode_index) {
+                let mut old_inode = old_inode.clone();
+                self.write_back_direntry(old_inode_index, &mut old_inode, old_dir_entry_map)
+                    .unwrap();
+                self.update_inode(old_inode_index, old_inode);
+            }
+        }
+    }
+
+    pub(crate) fn load_direntry_map(&mut self, index: usize, inode: &Inode) -> Result<(), c_int> {
+        if self.dir_entry_map.contains(&index) {
+            debug!("load_direntry_map(ino: {}) already in cache", index);
+            return Ok(());
+        }
+
+        debug!("load_direntry_map(ino: {}) loading", index);
+        let mut dir_entry_map: IndexMap<OsString, DirectoryEntry> = IndexMap::new();
+        let mut entry_index: usize = 0;
+        loop {
+            let block_index_within_inode = entry_index / 15;
+            let entry_index_within_block = entry_index % 15;
+
+            match self.access_block::<DirectoryBlock>(inode, block_index_within_inode) {
+                Some(directory_block) => {
+                    if directory_block.block.query(entry_index_within_block) {
+                        let dir_entry = &directory_block.block.entries[entry_index_within_block];
+                        let name = dir_entry.name();
+                        dir_entry_map.insert(name, dir_entry.clone());
+                    } else {
+                        break;
+                    }
+                }
+                None => break,
+            }
+            entry_index += 1;
+        }
+
+        if let Some((old_inode_index, old_dir_entry_map)) =
+            self.dir_entry_map.push(index, dir_entry_map)
+        {
+            if let Some(old_inode) = self.get_inode(old_inode_index) {
+                let mut old_inode = old_inode.clone();
+                self.write_back_direntry(old_inode_index, &mut old_inode, old_dir_entry_map)?;
+                self.update_inode(old_inode_index, old_inode);
+            }
+        }
+
+        Ok(())
+    }
+
+    pub(crate) fn write_back_direntry(
+        &mut self,
+        _parent_index: usize,
+        parent_inode: &mut Inode,
+        dir_entry_map: IndexMap<OsString, DirectoryEntry>,
+    ) -> Result<(), c_int> {
+        for (entry_index, (_, dir_entry)) in dir_entry_map.into_iter().enumerate() {
+            let block_index_within_inode = entry_index / 15;
+            let entry_index_within_block = entry_index % 15;
+            // 不够就新分配
+            if self
+                .get_block_index(parent_inode, block_index_within_inode)
+                .is_none()
+            {
+                match self.allocate_block_for(parent_inode) {
+                    Some((_, block_index_within)) => {
+                        assert_eq!(block_index_within, block_index_within_inode);
+                    }
+                    None => {
+                        return Err(ENOSPC);
+                    }
+                }
+            }
+            match self.access_block_mut::<DirectoryBlock>(parent_inode, block_index_within_inode) {
+                Some(directory_block) => {
+                    directory_block.block.entries[entry_index_within_block] = dir_entry;
+                }
+                None => {
+                    return Err(ENOENT);
+                }
+            }
+        }
+        Ok(())
     }
 
     /// 删除第 entry_index 个 dir entry
     pub(crate) fn remove_direntry(
         &mut self,
+        parent_index: usize,
         parent_inode: &mut Inode,
+        name: &OsStr,
         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)
-                }
+        self.load_direntry_map(parent_index, parent_inode)?;
+        if let Some(dir_entry_map) = self.dir_entry_map.get_mut(&parent_index) {
+            debug!("  remove_direntry(ino: {}) using hashmap", parent_index);
+            if dir_entry_map.shift_remove(name).is_some() {
+                Ok(())
+            } else {
+                Err(ENOENT)
             }
-            None => Err(ENOENT),
+        } else {
+            Err(ENOENT)
+            // 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(
+    pub(crate) fn add_direntry<T: AsRef<OsStr>>(
         &mut self,
+        parent_index: usize,
         parent_inode: &mut Inode,
         child_inode_index: usize,
-        child_inode_name: &OsStr,
-        child_inode: &Inode,
+        child_inode_name: T,
+        file_type: u8,
     ) -> 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 child_inode_name = child_inode_name.as_ref();
+        self.load_direntry_map(parent_index, parent_inode)?;
+        if let Some(dir_entry_map) = self.dir_entry_map.get_mut(&parent_index) {
+            let name_len = child_inode_name.len() as u8;
+            let mut name = [0u8; 256];
+            (&mut name[0..child_inode_name.len()]).copy_from_slice(child_inode_name.as_bytes());
 
-                    let dir_entry = DirectoryEntry {
-                        inode: child_inode_index as u32,
-                        record_len: 264,
-                        name_len,
-                        file_type,
-                        name,
-                    };
-                    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;
+            let dir_entry = DirectoryEntry {
+                inode: child_inode_index as u32,
+                record_len: 264,
+                name_len,
+                file_type,
+                name,
+            };
+
+            let (entry_index, _) =
+                dir_entry_map.insert_full(child_inode_name.to_os_string(), dir_entry);
+            debug!(
+                "  add_direntry(ino: {}) using hashmap, entry {}",
+                parent_index, entry_index
+            );
+            parent_inode.size += 1;
+            Ok(entry_index as u32)
+        } else {
+            Err(ENOENT)
         }
+        // // 找到第一个有空闲 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 mut name = [0u8; 256];
+        //             (&mut name[0..name_len as usize])
+        //                 .copy_from_slice(child_inode_name.as_bytes());
+        //
+        //             let dir_entry = DirectoryEntry {
+        //                 inode: child_inode_index as u32,
+        //                 record_len: 264,
+        //                 name_len,
+        //                 file_type,
+        //                 name,
+        //             };
+        //             directory_block.block.entries[entry_index_within_block] = dir_entry;
+        //             let entry_index = block_index_within_inode * 15 + entry_index_within_block;
+        //             parent_inode.size += 1;
+        //             return Ok(entry_index as u32);
+        //         }
+        //     }
+        //     block_index_within_inode += 1;
+        // }
     }
     pub(crate) fn get_direntry(
         &mut self,
+        parent_index: usize,
         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
-                }
-            })
+    ) -> Result<DirectoryEntry, c_int> {
+        self.load_direntry_map(parent_index, parent_inode)?;
+        if let Some(dir_entry_map) = self.dir_entry_map.get(&parent_index) {
+            debug!(
+                "  get_direntry(ino: {}, entry_index: {}) using hashmap",
+                parent_index, entry_index
+            );
+            dir_entry_map
+                .iter()
+                .skip(entry_index as usize)
+                .next()
+                .map(|entry| entry.1.clone())
+                .ok_or(ENOENT)
+        } else {
+            Err(ENOENT)
+            // let block_index_within_inode = (entry_index / 15) as usize;
+            // let entry_index_within_block = (entry_index % 15) as usize;
+            //
+            // match self.access_block::<DirectoryBlock>(parent_inode, block_index_within_inode) {
+            //     Some(directory_block) => {
+            //         if directory_block.block.query(entry_index_within_block) {
+            //             Ok(directory_block.block.entries[entry_index_within_block].clone())
+            //         } else {
+            //             Err(ENOENT)
+            //         }
+            //     }
+            //     None => Err(ENOENT),
+            // }
+        }
     }
 
     // TODO 实现一个带 cache 的版本
     /// 返回 inode_index, inode 在 parent 里的 index, inode 本身
     pub fn lookup_name(
         &mut self,
+        parent_index: usize,
         parent_inode: &Inode,
         name: &OsStr,
     ) -> Result<(u32, u32, Inode), c_int> {
-        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));
+        self.load_direntry_map(parent_index, parent_inode)?;
+        if let Some(dir_entry_map) = self.dir_entry_map.get(&parent_index) {
+            if let Some((entry_index, _, dir_entry)) = dir_entry_map.get_full(name) {
+                let inode_index = dir_entry.inode;
+                let inode = self.get_inode(inode_index as usize).unwrap().clone();
+                Ok((inode_index, entry_index as u32, inode))
+            } else {
+                Err(ENOENT)
+            }
+        } else {
+            let mut entry_index = 0;
+            while entry_index < parent_inode.size {
+                if let Ok(entry) = self.get_direntry(parent_index, parent_inode, entry_index) {
+                    if entry.name() == name {
+                        let inode = self.get_inode(entry.inode as usize).unwrap().clone();
+                        return Ok((entry.inode, entry_index, inode));
+                    }
                 }
+                entry_index += 1;
             }
-            entry_index += 1;
+            Err(ENOENT)
         }
-        Err(ENOENT)
     }
 }
diff --git a/src/memory/file_handle.rs b/src/memory/file_handle.rs
new file mode 100644
index 0000000..0da2ed2
--- /dev/null
+++ b/src/memory/file_handle.rs
@@ -0,0 +1,19 @@
+use crate::AyaFS;
+use std::sync::atomic::Ordering;
+
+impl AyaFS {
+    pub(crate) fn allocate_file_descriptor(
+        &mut self,
+        inode_index: usize,
+        read: bool,
+        write: bool,
+    ) -> u64 {
+        let fd = self.next_file_handle.fetch_add(1, Ordering::SeqCst);
+        self.file_handle_map.insert(fd, (inode_index, read, write));
+        fd
+    }
+
+    pub(crate) fn get_inode_from_fd(&self, file_descriptor: u64) -> Option<(usize, bool, bool)> {
+        self.file_handle_map.get(&file_descriptor).copied()
+    }
+}
diff --git a/src/memory/mod.rs b/src/memory/mod.rs
index 4080114..d1f1ab8 100644
--- a/src/memory/mod.rs
+++ b/src/memory/mod.rs
@@ -3,3 +3,4 @@
 pub mod cached_block;
 pub mod cached_inode;
 mod dir_entry;
+mod file_handle;
diff --git a/src/tests/bitmap.rs b/src/tests/bitmap.rs
index 9b21b6f..1a43f09 100644
--- a/src/tests/bitmap.rs
+++ b/src/tests/bitmap.rs
@@ -1,4 +1,5 @@
 use crate::tests::common;
+use indexmap::IndexMap;
 
 #[test]
 fn test_allocate() {
@@ -21,3 +22,17 @@ fn test_query() {
     assert_eq!(fs.data_bitmap.query(5), true);
     assert_eq!(fs.data_bitmap.query(11), false);
 }
+
+#[test]
+fn test_index_map() {
+    let mut map: IndexMap<i32, i32> = IndexMap::new();
+    map.insert(1, 2);
+    map.insert(2, 3);
+    map.insert(3, 4);
+    map.insert(4, 5);
+    map.remove(&3);
+
+    for (entry_index, (key, value)) in map.iter().enumerate() {
+        println!("index {}, key {}, value {}", entry_index, key, value);
+    }
+}
diff --git a/src/tests/block_cache.rs b/src/tests/block_cache.rs
index 90875ae..52117b9 100644
--- a/src/tests/block_cache.rs
+++ b/src/tests/block_cache.rs
@@ -26,8 +26,8 @@ fn test_basic_lru() {
 fn test_inode_allocation() {
     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();
+    let (inode_index, inode) = fs.create_directory(0o755, 0, 0, 0, None).unwrap();
+    let mut inode = inode.clone();
 
     const DIRECT_NUMBER: u32 = 15;
     const INDIRECT_NUMBER: u32 = 1024;
@@ -76,20 +76,20 @@ fn test_inode_allocation() {
 fn test_inode_deallocation() {
     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();
+    let (inode_index, inode) = fs.create_directory(0o755, 0, 0, 0, None).unwrap();
+    let mut inode = inode.clone();
 
     const DIRECT_NUMBER: u32 = 15;
     const INDIRECT_NUMBER: u32 = 1024;
     // const DOUBLE_INDIRECT_NUMBER: u32 = 1024 * 1024;
 
     for i in 0..DIRECT_NUMBER {
-        println!("Allocated {}", fs.allocate_block_for(&mut inode).unwrap());
+        println!("Allocated {:?}", fs.allocate_block_for(&mut inode).unwrap());
         assert!(fs.data_bitmap.query(inode.direct[i as usize] as usize))
     }
 
     for _i in 0..2 * INDIRECT_NUMBER {
-        println!("Allocated {}", fs.allocate_block_for(&mut inode).unwrap());
+        println!("Allocated {:?}", fs.allocate_block_for(&mut inode).unwrap());
     }
 
     println!("single indirect is {}", inode.single_indirect);
@@ -118,30 +118,33 @@ fn test_inode_deallocation() {
 fn test_multiple_inode_allocation() {
     let mut fs = common::setup();
 
-    let inode_index_1 = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap();
-    let inode_index_2 = fs.create_inode(0o755, InodeMode::IFREG, 0, 0, 0).unwrap();
+    let (inode_index_1, inode_1) = fs.create_directory(0o755, 0, 0, 0, None).unwrap();
+    let mut inode_1 = inode_1.clone();
 
-    let mut inode_1 = fs.get_inode(inode_index_1).unwrap().clone();
-    let mut inode_2 = fs.get_inode(inode_index_2).unwrap().clone();
+    let (inode_index_2, inode_2) = fs.create_file(0o755, 0, 0, 0).unwrap();
+    let mut inode_2 = inode_2.clone();
+    // let mut inode_1 = fs.get_inode(inode_index_1).unwrap().clone();
+    // let mut inode_2 = fs.get_inode(inode_index_2).unwrap().clone();
 
     const DIRECT_NUMBER: u32 = 15;
     const INDIRECT_NUMBER: u32 = 1024;
 
     for i in 0..DIRECT_NUMBER + INDIRECT_NUMBER {
         println!(
-            "Allocated {} in inode {}",
+            "Allocated {:?} in inode {}",
             fs.allocate_block_for(&mut inode_1).unwrap(),
             inode_index_1
         );
         println!(
-            "Allocated {} in inode {}",
+            "Allocated {:?} in inode {}",
             fs.allocate_block_for(&mut inode_2).unwrap(),
             inode_index_2
         );
     }
 
-    let inode_index_3 = fs.create_inode(0o755, InodeMode::IFDIR, 0, 0, 0).unwrap();
-    let mut inode_3 = fs.get_inode(inode_index_3).unwrap().clone();
+    let (inode_index_3, inode_3) = fs.create_directory(0o755, 0, 0, 0, None).unwrap();
+    let mut inode_3 = inode_3.clone();
+    // let mut inode_3 = fs.get_inode(inode_index_3).unwrap().clone();
 
     for _i in 0..INDIRECT_NUMBER {
         println!(
@@ -150,7 +153,7 @@ fn test_multiple_inode_allocation() {
             inode_index_1
         );
         println!(
-            "Allocated {} in inode {}",
+            "Allocated {:?} in inode {}",
             fs.allocate_block_for(&mut inode_3).unwrap(),
             inode_index_3
         );