diff --git a/authfs/src/file/dir.rs b/authfs/src/file/dir.rs
index 2eaaddd..2a8f359 100644
--- a/authfs/src/file/dir.rs
+++ b/authfs/src/file/dir.rs
@@ -14,6 +14,7 @@
  * limitations under the License.
  */
 
+use log::warn;
 use std::collections::{hash_map, HashMap};
 use std::io;
 use std::path::{Path, PathBuf};
@@ -25,6 +26,16 @@
 
 const MAX_ENTRIES: u16 = 100; // Arbitrary limit
 
+struct DirEntry {
+    inode: Inode,
+
+    // This information is duplicated since it is also available in `AuthFs::inode_table` via the
+    // type system. But it makes it simple to deal with deletion, where otherwise we need to get a
+    // mutable parent directory in the table, and query the table for directory/file type checking
+    // at the same time.
+    is_dir: bool,
+}
+
 /// A remote directory backed by a remote directory FD, where the provider/fd_server is not
 /// trusted.
 ///
@@ -43,9 +54,9 @@
     service: VirtFdService,
     remote_dir_fd: i32,
 
-    /// Mapping of entry names to the corresponding inode number. The actual file/directory is
-    /// stored in the global pool in fusefs.
-    entries: HashMap<PathBuf, Inode>,
+    /// Mapping of entry names to the corresponding inode. The actual file/directory is stored in
+    /// the global pool in fusefs.
+    entries: HashMap<PathBuf, DirEntry>,
 }
 
 impl RemoteDirEditor {
@@ -75,7 +86,7 @@
 
         let new_remote_file =
             VerifiedFileEditor::new(RemoteFileEditor::new(self.service.clone(), new_fd));
-        self.entries.insert(basename.to_path_buf(), inode);
+        self.entries.insert(basename.to_path_buf(), DirEntry { inode, is_dir: false });
         Ok(new_remote_file)
     }
 
@@ -92,14 +103,68 @@
             .map_err(into_io_error)?;
 
         let new_remote_dir = RemoteDirEditor::new(self.service.clone(), new_fd);
-        self.entries.insert(basename.to_path_buf(), inode);
+        self.entries.insert(basename.to_path_buf(), DirEntry { inode, is_dir: true });
         Ok(new_remote_dir)
     }
 
+    /// Deletes a file
+    pub fn delete_file(&mut self, basename: &Path) -> io::Result<Inode> {
+        let inode = self.force_delete_entry(basename, /* expect_dir */ false)?;
+
+        let basename_str =
+            basename.to_str().ok_or_else(|| io::Error::from_raw_os_error(libc::EINVAL))?;
+        if let Err(e) = self.service.deleteFile(self.remote_dir_fd, basename_str) {
+            // Ignore the error to honor the local state.
+            warn!("Deletion on the host is reportedly failed: {:?}", e);
+        }
+        Ok(inode)
+    }
+
+    /// Forces to delete a directory. The caller must only call if `basename` is a directory and
+    /// empty.
+    pub fn force_delete_directory(&mut self, basename: &Path) -> io::Result<Inode> {
+        let inode = self.force_delete_entry(basename, /* expect_dir */ true)?;
+
+        let basename_str =
+            basename.to_str().ok_or_else(|| io::Error::from_raw_os_error(libc::EINVAL))?;
+        if let Err(e) = self.service.deleteDirectory(self.remote_dir_fd, basename_str) {
+            // Ignore the error to honor the local state.
+            warn!("Deletion on the host is reportedly failed: {:?}", e);
+        }
+        Ok(inode)
+    }
+
     /// Returns the inode number of a file or directory named `name` previously created through
     /// `RemoteDirEditor`.
-    pub fn find_inode(&self, name: &Path) -> Option<Inode> {
-        self.entries.get(name).copied()
+    pub fn find_inode(&self, name: &Path) -> io::Result<Inode> {
+        self.entries
+            .get(name)
+            .map(|entry| entry.inode)
+            .ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))
+    }
+
+    /// Returns whether the directory has an entry of the given name.
+    pub fn has_entry(&self, name: &Path) -> bool {
+        self.entries.contains_key(name)
+    }
+
+    fn force_delete_entry(&mut self, basename: &Path, expect_dir: bool) -> io::Result<Inode> {
+        // Kernel should only give us a basename.
+        debug_assert!(validate_basename(basename).is_ok());
+
+        if let Some(entry) = self.entries.get(basename) {
+            match (expect_dir, entry.is_dir) {
+                (true, false) => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
+                (false, true) => Err(io::Error::from_raw_os_error(libc::EISDIR)),
+                _ => {
+                    let inode = entry.inode;
+                    let _ = self.entries.remove(basename);
+                    Ok(inode)
+                }
+            }
+        } else {
+            Err(io::Error::from_raw_os_error(libc::ENOENT))
+        }
     }
 
     fn validate_argument(&self, basename: &Path) -> io::Result<()> {
diff --git a/authfs/src/fusefs.rs b/authfs/src/fusefs.rs
index 6fdcd62..17a368f 100644
--- a/authfs/src/fusefs.rs
+++ b/authfs/src/fusefs.rs
@@ -72,6 +72,24 @@
     VerifiedNewDirectory { dir: RemoteDirEditor },
 }
 
+impl AuthFsEntry {
+    fn expect_empty_writable_directory(&self) -> io::Result<()> {
+        match self {
+            AuthFsEntry::VerifiedNewDirectory { dir } => {
+                if dir.number_of_entries() == 0 {
+                    Ok(())
+                } else {
+                    Err(io::Error::from_raw_os_error(libc::ENOTEMPTY))
+                }
+            }
+            AuthFsEntry::ReadonlyDirectory { .. } => {
+                Err(io::Error::from_raw_os_error(libc::EACCES))
+            }
+            _ => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
+        }
+    }
+}
+
 struct InodeState {
     /// Actual inode entry.
     entry: AuthFsEntry,
@@ -85,15 +103,19 @@
     ///
     /// Note: This is not to be confused with hardlinks, which AuthFS doesn't currently implement.
     handle_ref_count: u64,
+
+    /// Whether the inode is already unlinked, i.e. should be removed, once `handle_ref_count` is
+    /// down to zero.
+    unlinked: bool,
 }
 
 impl InodeState {
     fn new(entry: AuthFsEntry) -> Self {
-        InodeState { entry, handle_ref_count: 0 }
+        InodeState { entry, handle_ref_count: 0, unlinked: false }
     }
 
     fn new_with_ref_count(entry: AuthFsEntry, handle_ref_count: u64) -> Self {
-        InodeState { entry, handle_ref_count }
+        InodeState { entry, handle_ref_count, unlinked: false }
     }
 }
 
@@ -411,7 +433,7 @@
                 }
                 AuthFsEntry::VerifiedNewDirectory { dir } => {
                     let path = cstr_to_path(name);
-                    dir.find_inode(path).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))
+                    dir.find_inode(path)
                 }
                 _ => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
             })?;
@@ -452,10 +474,10 @@
 
     fn forget(&self, _ctx: Context, inode: Self::Inode, count: u64) {
         let mut inode_table = self.inode_table.lock().unwrap();
-        let _ = handle_inode_mut_locked(
+        let delete_now = handle_inode_mut_locked(
             &mut inode_table,
             &inode,
-            |InodeState { handle_ref_count, .. }| {
+            |InodeState { handle_ref_count, unlinked, .. }| {
                 if count > *handle_ref_count {
                     error!(
                         "Trying to decrease refcount of inode {} by {} (> current {})",
@@ -464,11 +486,22 @@
                     panic!(); // log to logcat with error!
                 }
                 *handle_ref_count = handle_ref_count.saturating_sub(count);
-                // TODO(208892249): Remove the inode with zero ref count from inode_table, if the
-                // inode is marked for deletion.
-                Ok(())
+                Ok(*unlinked && *handle_ref_count == 0)
             },
         );
+
+        match delete_now {
+            Ok(true) => {
+                let _ = inode_table.remove(&inode).expect("Removed an existing entry");
+            }
+            Ok(false) => { /* Let the inode stay */ }
+            Err(e) => {
+                warn!(
+                    "Unexpected failure when tries to forget an inode {} by refcount {}: {:?}",
+                    inode, count, e
+                );
+            }
+        }
     }
 
     fn getattr(
@@ -544,7 +577,7 @@
             name,
             |parent_entry, basename, new_inode| match parent_entry {
                 AuthFsEntry::VerifiedNewDirectory { dir } => {
-                    if dir.find_inode(basename).is_some() {
+                    if dir.has_entry(basename) {
                         return Err(io::Error::from_raw_os_error(libc::EEXIST));
                     }
                     let new_file = dir.create_file(basename, new_inode)?;
@@ -723,7 +756,7 @@
             name,
             |parent_entry, basename, new_inode| match parent_entry {
                 AuthFsEntry::VerifiedNewDirectory { dir } => {
-                    if dir.find_inode(basename).is_some() {
+                    if dir.has_entry(basename) {
                         return Err(io::Error::from_raw_os_error(libc::EEXIST));
                     }
                     let new_dir = dir.mkdir(basename, new_inode)?;
@@ -745,6 +778,68 @@
         })
     }
 
+    fn unlink(&self, _ctx: Context, parent: Self::Inode, name: &CStr) -> io::Result<()> {
+        let mut inode_table = self.inode_table.lock().unwrap();
+        handle_inode_mut_locked(
+            &mut inode_table,
+            &parent,
+            |InodeState { entry, unlinked, .. }| match entry {
+                AuthFsEntry::VerifiedNewDirectory { dir } => {
+                    let basename: &Path = cstr_to_path(name);
+                    // Delete the file from in both the local and remote directories.
+                    let _inode = dir.delete_file(basename)?;
+                    *unlinked = true;
+                    Ok(())
+                }
+                AuthFsEntry::ReadonlyDirectory { .. } => {
+                    Err(io::Error::from_raw_os_error(libc::EACCES))
+                }
+                AuthFsEntry::VerifiedNew { .. } => {
+                    // Deleting a entry in filesystem root is not currently supported.
+                    Err(io::Error::from_raw_os_error(libc::ENOSYS))
+                }
+                AuthFsEntry::UnverifiedReadonly { .. } | AuthFsEntry::VerifiedReadonly { .. } => {
+                    Err(io::Error::from_raw_os_error(libc::ENOTDIR))
+                }
+            },
+        )
+    }
+
+    fn rmdir(&self, _ctx: Context, parent: Self::Inode, name: &CStr) -> io::Result<()> {
+        let mut inode_table = self.inode_table.lock().unwrap();
+
+        // Check before actual removal, with readonly borrow.
+        handle_inode_locked(&inode_table, &parent, |inode_state| match &inode_state.entry {
+            AuthFsEntry::VerifiedNewDirectory { dir } => {
+                let basename: &Path = cstr_to_path(name);
+                let existing_inode = dir.find_inode(basename)?;
+                handle_inode_locked(&inode_table, &existing_inode, |inode_state| {
+                    inode_state.entry.expect_empty_writable_directory()
+                })
+            }
+            AuthFsEntry::ReadonlyDirectory { .. } => {
+                Err(io::Error::from_raw_os_error(libc::EACCES))
+            }
+            _ => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
+        })?;
+
+        // Look up again, this time with mutable borrow. This needs to be done separately because
+        // the previous lookup needs to borrow multiple entry references in the table.
+        handle_inode_mut_locked(
+            &mut inode_table,
+            &parent,
+            |InodeState { entry, unlinked, .. }| match entry {
+                AuthFsEntry::VerifiedNewDirectory { dir } => {
+                    let basename: &Path = cstr_to_path(name);
+                    let _inode = dir.force_delete_directory(basename)?;
+                    *unlinked = true;
+                    Ok(())
+                }
+                _ => unreachable!("Mismatched entry type that is just checked"),
+            },
+        )
+    }
+
     fn statfs(&self, _ctx: Context, _inode: Self::Inode) -> io::Result<libc::statvfs64> {
         let remote_stat = self.remote_fs_stats_reader.statfs()?;