diff --git a/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl b/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
index 64828fb..1c618a1 100644
--- a/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
+++ b/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
@@ -57,7 +57,7 @@
     long getFileSize(int fd);
 
     /**
-     * Open a file given the remote directory FD.
+     * Opens a file given the remote directory FD.
      *
      * @param pathname The file path to open. Must be a related path.
      * @return file A remote FD that represents the opened file.
@@ -65,7 +65,7 @@
     int openFileInDirectory(int dirFd, String pathname);
 
     /**
-     * Create a file given the remote directory FD.
+     * Creates a file given the remote directory FD.
      *
      * @param basename The file name to create. Must not contain directory separator.
      * @return file A remote FD that represents the new created file.
@@ -73,13 +73,27 @@
     int createFileInDirectory(int dirFd, String basename);
 
     /**
-     * Create a directory inside the given remote directory FD.
+     * Creates a directory inside the given remote directory FD.
      *
      * @param basename The directory name to create. Must not contain directory separator.
      * @return file FD that represents the new created directory.
      */
     int createDirectoryInDirectory(int dirFd, String basename);
 
+    /**
+     * Deletes a file in the given directory.
+     *
+     * @param basename The file name to delete. Must not contain directory separator.
+     */
+    void deleteFile(int dirFd, String basename);
+
+    /**
+     * Deletes a sub-directory in the given directory.
+     *
+     * @param basename The directory name to delete. Must not contain directory separator.
+     */
+    void deleteDirectory(int dirFd, String basename);
+
     /** Filesystem stats that AuthFS is interested in.*/
     parcelable FsStat {
         /** Block size of the filesystem */
diff --git a/authfs/fd_server/src/aidl.rs b/authfs/fd_server/src/aidl.rs
index ddac2bc..66c943e 100644
--- a/authfs/fd_server/src/aidl.rs
+++ b/authfs/fd_server/src/aidl.rs
@@ -18,7 +18,7 @@
 use log::error;
 use nix::{
     dir::Dir, errno::Errno, fcntl::openat, fcntl::OFlag, sys::stat::mkdirat, sys::stat::Mode,
-    sys::statvfs::statvfs, sys::statvfs::Statvfs,
+    sys::statvfs::statvfs, sys::statvfs::Statvfs, unistd::unlinkat, unistd::UnlinkatFlags,
 };
 use std::cmp::min;
 use std::collections::{btree_map, BTreeMap};
@@ -264,14 +264,14 @@
         })
     }
 
-    fn openFileInDirectory(&self, fd: i32, file_path: &str) -> BinderResult<i32> {
+    fn openFileInDirectory(&self, dir_fd: i32, file_path: &str) -> BinderResult<i32> {
         let path_buf = PathBuf::from(file_path);
         // Checks if the path is a simple, related path.
         if path_buf.components().any(|c| !matches!(c, Component::Normal(_))) {
             return Err(new_errno_error(Errno::EINVAL));
         }
 
-        self.insert_new_fd(fd, |config| match config {
+        self.insert_new_fd(dir_fd, |config| match config {
             FdConfig::InputDir(dir) => {
                 let file = open_readonly_at(dir.as_raw_fd(), &path_buf).map_err(new_errno_error)?;
 
@@ -288,11 +288,10 @@
         })
     }
 
-    fn createFileInDirectory(&self, fd: i32, basename: &str) -> BinderResult<i32> {
-        if basename.contains(MAIN_SEPARATOR) {
-            return Err(new_errno_error(Errno::EINVAL));
-        }
-        self.insert_new_fd(fd, |config| match config {
+    fn createFileInDirectory(&self, dir_fd: i32, basename: &str) -> BinderResult<i32> {
+        validate_basename(basename)?;
+
+        self.insert_new_fd(dir_fd, |config| match config {
             FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
             FdConfig::OutputDir(dir) => {
                 let new_fd = openat(
@@ -313,9 +312,8 @@
     }
 
     fn createDirectoryInDirectory(&self, dir_fd: i32, basename: &str) -> BinderResult<i32> {
-        if basename.contains(MAIN_SEPARATOR) {
-            return Err(new_errno_error(Errno::EINVAL));
-        }
+        validate_basename(basename)?;
+
         self.insert_new_fd(dir_fd, |config| match config {
             FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
             FdConfig::OutputDir(_) => {
@@ -333,6 +331,34 @@
         })
     }
 
+    fn deleteFile(&self, dir_fd: i32, basename: &str) -> BinderResult<()> {
+        validate_basename(basename)?;
+
+        self.handle_fd(dir_fd, |config| match config {
+            FdConfig::OutputDir(_dir) => {
+                unlinkat(Some(dir_fd), basename, UnlinkatFlags::NoRemoveDir)
+                    .map_err(new_errno_error)?;
+                Ok(())
+            }
+            FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
+            _ => Err(new_errno_error(Errno::ENOTDIR)),
+        })
+    }
+
+    fn deleteDirectory(&self, dir_fd: i32, basename: &str) -> BinderResult<()> {
+        validate_basename(basename)?;
+
+        self.handle_fd(dir_fd, |config| match config {
+            FdConfig::OutputDir(_dir) => {
+                unlinkat(Some(dir_fd), basename, UnlinkatFlags::RemoveDir)
+                    .map_err(new_errno_error)?;
+                Ok(())
+            }
+            FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
+            _ => Err(new_errno_error(Errno::ENOTDIR)),
+        })
+    }
+
     fn statfs(&self) -> BinderResult<FsStat> {
         let st = statvfs("/data").map_err(new_errno_error)?;
         try_into_fs_stat(st).map_err(|_e| new_errno_error(Errno::EINVAL))
@@ -368,3 +394,11 @@
     let new_file = unsafe { File::from_raw_fd(new_fd) };
     Ok(new_file)
 }
+
+fn validate_basename(name: &str) -> BinderResult<()> {
+    if name.contains(MAIN_SEPARATOR) {
+        Err(new_errno_error(Errno::EINVAL))
+    } else {
+        Ok(())
+    }
+}
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()?;
 
diff --git a/authfs/tests/java/src/com/android/fs/AuthFsHostTest.java b/authfs/tests/java/src/com/android/fs/AuthFsHostTest.java
index 2d7668a..e2188b9 100644
--- a/authfs/tests/java/src/com/android/fs/AuthFsHostTest.java
+++ b/authfs/tests/java/src/com/android/fs/AuthFsHostTest.java
@@ -386,6 +386,51 @@
     }
 
     @Test
+    public void testOutputDirectory_CanDeleteFile() throws Exception {
+        // Setup
+        String androidOutputDir = TEST_OUTPUT_DIR + "/dir";
+        String authfsOutputDir = MOUNT_DIR + "/3";
+        sAndroid.run("mkdir " + androidOutputDir);
+        runFdServerOnAndroid("--open-dir 3:" + androidOutputDir, "--rw-dirs 3");
+        runAuthFsOnMicrodroid("--remote-new-rw-dir 3 --cid " + VMADDR_CID_HOST);
+
+        runOnMicrodroid("echo -n foo > " + authfsOutputDir + "/file");
+        runOnMicrodroid("test -f " + authfsOutputDir + "/file");
+        sAndroid.run("test -f " + androidOutputDir + "/file");
+
+        // Action & Verify
+        runOnMicrodroid("rm " + authfsOutputDir + "/file");
+        runOnMicrodroid("test ! -f " + authfsOutputDir + "/file");
+        sAndroid.run("test ! -f " + androidOutputDir + "/file");
+    }
+
+    @Test
+    public void testOutputDirectory_CanDeleteDirectoryOnlyIfEmpty() throws Exception {
+        // Setup
+        String androidOutputDir = TEST_OUTPUT_DIR + "/dir";
+        String authfsOutputDir = MOUNT_DIR + "/3";
+        sAndroid.run("mkdir " + androidOutputDir);
+        runFdServerOnAndroid("--open-dir 3:" + androidOutputDir, "--rw-dirs 3");
+        runAuthFsOnMicrodroid("--remote-new-rw-dir 3 --cid " + VMADDR_CID_HOST);
+
+        runOnMicrodroid("mkdir -p " + authfsOutputDir + "/dir/dir2");
+        runOnMicrodroid("echo -n foo > " + authfsOutputDir + "/dir/file");
+        sAndroid.run("test -d " + androidOutputDir + "/dir/dir2");
+
+        // Action & Verify
+        runOnMicrodroid("rmdir " + authfsOutputDir + "/dir/dir2");
+        runOnMicrodroid("test ! -d " + authfsOutputDir + "/dir/dir2");
+        sAndroid.run("test ! -d " + androidOutputDir + "/dir/dir2");
+        // Can only delete a directory if empty
+        assertFailedOnMicrodroid("rmdir " + authfsOutputDir + "/dir");
+        runOnMicrodroid("test -d " + authfsOutputDir + "/dir");  // still there
+        runOnMicrodroid("rm " + authfsOutputDir + "/dir/file");
+        runOnMicrodroid("rmdir " + authfsOutputDir + "/dir");
+        runOnMicrodroid("test ! -d " + authfsOutputDir + "/dir");
+        sAndroid.run("test ! -d " + androidOutputDir + "/dir");
+    }
+
+    @Test
     public void testOutputDirectory_CannotRecreateDirectoryIfNameExists() throws Exception {
         // Setup
         String androidOutputDir = TEST_OUTPUT_DIR + "/dir";
@@ -408,6 +453,40 @@
     }
 
     @Test
+    public void testOutputDirectory_WriteToFdOfDeletedFile() throws Exception {
+        // Setup
+        String authfsOutputDir = MOUNT_DIR + "/3";
+        String androidOutputDir = TEST_OUTPUT_DIR + "/dir";
+        sAndroid.run("mkdir " + androidOutputDir);
+        runFdServerOnAndroid("--open-dir 3:" + androidOutputDir, "--rw-dirs 3");
+        runAuthFsOnMicrodroid("--remote-new-rw-dir 3 --cid " + VMADDR_CID_HOST);
+
+        // Create a file with some data. Test the existence.
+        String outputPath = authfsOutputDir + "/out";
+        String androidOutputPath = androidOutputDir + "/out";
+        runOnMicrodroid("echo -n 123 > " + outputPath);
+        runOnMicrodroid("test -f " + outputPath);
+        sAndroid.run("test -f " + androidOutputPath);
+
+        // Action
+        String output = runOnMicrodroid(
+                // Open the file for append and read
+                "exec 4>>" + outputPath + " 5<" + outputPath + "; "
+                // Delete the file from the directory
+                + "rm " + outputPath + "; "
+                // Append more data to the file descriptor
+                + "echo -n 456 >&4; "
+                // Print the whole file from the file descriptor
+                + "cat <&5");
+
+        // Verify
+        // Output contains all written data, while the files are deleted.
+        assertEquals("123456", output);
+        runOnMicrodroid("test ! -f " + outputPath);
+        sAndroid.run("test ! -f " + androidOutputDir + "/out");
+    }
+
+    @Test
     public void testInputDirectory_CanReadFile() throws Exception {
         // Setup
         String authfsInputDir = MOUNT_DIR + "/3";