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 8ca82f8..17a368f 100644
--- a/authfs/src/fusefs.rs
+++ b/authfs/src/fusefs.rs
@@ -17,7 +17,7 @@
 mod mount;
 
 use anyhow::{anyhow, bail, Result};
-use log::{debug, warn};
+use log::{debug, error, warn};
 use std::collections::{btree_map, BTreeMap};
 use std::convert::TryFrom;
 use std::ffi::{CStr, OsStr};
@@ -72,11 +72,58 @@
     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,
+
+    /// Number of `Handle`s (i.e. file descriptors) that are currently referring to the this inode.
+    ///
+    /// Technically, this does not matter to readonly entries, since they live forever. The
+    /// reference count is only needed for manageing lifetime of writable entries like `VerifiedNew`
+    /// and `VerifiedNewDirectory`. That is, when an entry is deleted, the actual entry needs to
+    /// stay alive until the reference count reaches zero.
+    ///
+    /// 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, unlinked: false }
+    }
+
+    fn new_with_ref_count(entry: AuthFsEntry, handle_ref_count: u64) -> Self {
+        InodeState { entry, handle_ref_count, unlinked: false }
+    }
+}
+
 // AuthFS needs to be `Sync` to be accepted by fuse::worker::start_message_loop as a `FileSystem`.
 pub struct AuthFs {
-    /// Table for `Inode` to `AuthFsEntry` lookup. This needs to be `Sync` to be used in
+    /// Table for `Inode` to `InodeState` lookup. This needs to be `Sync` to be used in
     /// `fuse::worker::start_message_loop`.
-    inode_table: Mutex<BTreeMap<Inode, AuthFsEntry>>,
+    inode_table: Mutex<BTreeMap<Inode, InodeState>>,
 
     /// The next available inode number.
     next_inode: AtomicU64,
@@ -92,7 +139,10 @@
 impl AuthFs {
     pub fn new(remote_fs_stats_reader: RemoteFsStatsReader) -> AuthFs {
         let mut inode_table = BTreeMap::new();
-        inode_table.insert(ROOT_INODE, AuthFsEntry::ReadonlyDirectory { dir: InMemoryDir::new() });
+        inode_table.insert(
+            ROOT_INODE,
+            InodeState::new(AuthFsEntry::ReadonlyDirectory { dir: InMemoryDir::new() }),
+        );
 
         AuthFs {
             inode_table: Mutex::new(inode_table),
@@ -130,10 +180,12 @@
                     Component::Normal(name) => {
                         let inode_table = self.inode_table.get_mut().unwrap();
                         // Locate the internal directory structure.
-                        let current_dir_entry =
-                            inode_table.get_mut(&current_dir_inode).ok_or_else(|| {
+                        let current_dir_entry = &mut inode_table
+                            .get_mut(&current_dir_inode)
+                            .ok_or_else(|| {
                                 anyhow!("Unknown directory inode {}", current_dir_inode)
-                            })?;
+                            })?
+                            .entry;
                         let dir = match current_dir_entry {
                             AuthFsEntry::ReadonlyDirectory { dir } => dir,
                             _ => unreachable!("Not a ReadonlyDirectory"),
@@ -148,7 +200,10 @@
 
                             // Actually update the tables.
                             dir.add_entry(name.as_ref(), new_inode)?;
-                            if inode_table.insert(new_inode, new_dir_entry).is_some() {
+                            if inode_table
+                                .insert(new_inode, InodeState::new(new_dir_entry))
+                                .is_some()
+                            {
                                 bail!("Unexpected to find a duplicated inode");
                             }
                             Ok(new_inode)
@@ -160,7 +215,8 @@
 
         // 2. Insert the entry to the parent directory, as well as the inode table.
         let inode_table = self.inode_table.get_mut().unwrap();
-        match inode_table.get_mut(&parent_inode).expect("previously returned inode") {
+        let inode_state = inode_table.get_mut(&parent_inode).expect("previously returned inode");
+        match &mut inode_state.entry {
             AuthFsEntry::ReadonlyDirectory { dir } => {
                 let basename =
                     path.file_name().ok_or_else(|| anyhow!("Bad file name: {:?}", path))?;
@@ -168,7 +224,7 @@
 
                 // Actually update the tables.
                 dir.add_entry(basename.as_ref(), new_inode)?;
-                if inode_table.insert(new_inode, entry).is_some() {
+                if inode_table.insert(new_inode, InodeState::new(entry)).is_some() {
                     bail!("Unexpected to find a duplicated inode");
                 }
                 Ok(new_inode)
@@ -187,12 +243,11 @@
         F: FnOnce(&AuthFsEntry) -> io::Result<R>,
     {
         let inode_table = self.inode_table.lock().unwrap();
-        let entry =
-            inode_table.get(inode).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
-        handle_fn(entry)
+        handle_inode_locked(&inode_table, inode, |inode_state| handle_fn(&inode_state.entry))
     }
 
-    /// Adds a new entry `name` created by `create_fn` at `parent_inode`.
+    /// Adds a new entry `name` created by `create_fn` at `parent_inode`, with an initial ref count
+    /// of one.
     ///
     /// The operation involves two updates: adding the name with a new allocated inode to the
     /// parent directory, and insert the new inode and the actual `AuthFsEntry` to the global inode
@@ -200,7 +255,7 @@
     ///
     /// `create_fn` receives the parent directory, through which it can create the new entry at and
     /// register the new inode to. Its returned entry is then added to the inode table.
-    fn create_new_entry<F>(
+    fn create_new_entry_with_ref_count<F>(
         &self,
         parent_inode: Inode,
         name: &CStr,
@@ -210,15 +265,19 @@
         F: FnOnce(&mut AuthFsEntry, &Path, Inode) -> io::Result<AuthFsEntry>,
     {
         let mut inode_table = self.inode_table.lock().unwrap();
-        let parent_entry = inode_table
-            .get_mut(&parent_inode)
-            .ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
+        let (new_inode, new_file_entry) = handle_inode_mut_locked(
+            &mut inode_table,
+            &parent_inode,
+            |InodeState { entry, .. }| {
+                let new_inode = self.next_inode.fetch_add(1, Ordering::Relaxed);
+                let basename: &Path = cstr_to_path(name);
+                let new_file_entry = create_fn(entry, basename, new_inode)?;
+                Ok((new_inode, new_file_entry))
+            },
+        )?;
 
-        let new_inode = self.next_inode.fetch_add(1, Ordering::Relaxed);
-        let basename: &Path = cstr_to_path(name);
-        let new_file_entry = create_fn(parent_entry, basename, new_inode)?;
         if let btree_map::Entry::Vacant(entry) = inode_table.entry(new_inode) {
-            entry.insert(new_file_entry);
+            entry.insert(InodeState::new_with_ref_count(new_file_entry, 1));
             Ok(new_inode)
         } else {
             unreachable!("Unexpected duplication of inode {}", new_inode);
@@ -363,39 +422,47 @@
     }
 
     fn lookup(&self, _ctx: Context, parent: Inode, name: &CStr) -> io::Result<Entry> {
-        // Look up the entry's inode number in parent directory.
-        let inode = self.handle_inode(&parent, |parent_entry| match parent_entry {
-            AuthFsEntry::ReadonlyDirectory { dir } => {
-                let path = cstr_to_path(name);
-                dir.lookup_inode(path).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))
-            }
-            AuthFsEntry::VerifiedNewDirectory { dir } => {
-                let path = cstr_to_path(name);
-                dir.find_inode(path).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))
-            }
-            _ => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
-        })?;
+        let mut inode_table = self.inode_table.lock().unwrap();
 
-        // Normally, `lookup` is required to increase a reference count for the inode (while
-        // `forget` will decrease it). It is not yet necessary until we start to support
-        // deletion (only for `VerifiedNewDirectory`).
+        // Look up the entry's inode number in parent directory.
+        let inode =
+            handle_inode_locked(&inode_table, &parent, |inode_state| match &inode_state.entry {
+                AuthFsEntry::ReadonlyDirectory { dir } => {
+                    let path = cstr_to_path(name);
+                    dir.lookup_inode(path).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))
+                }
+                AuthFsEntry::VerifiedNewDirectory { dir } => {
+                    let path = cstr_to_path(name);
+                    dir.find_inode(path)
+                }
+                _ => Err(io::Error::from_raw_os_error(libc::ENOTDIR)),
+            })?;
 
         // Create the entry's stat if found.
-        let st = self.handle_inode(&inode, |entry| match entry {
-            AuthFsEntry::ReadonlyDirectory { dir } => {
-                create_dir_stat(inode, dir.number_of_entries())
-            }
-            AuthFsEntry::UnverifiedReadonly { file_size, .. }
-            | AuthFsEntry::VerifiedReadonly { file_size, .. } => {
-                create_stat(inode, *file_size, AccessMode::ReadOnly)
-            }
-            AuthFsEntry::VerifiedNew { editor } => {
-                create_stat(inode, editor.size(), AccessMode::ReadWrite)
-            }
-            AuthFsEntry::VerifiedNewDirectory { dir } => {
-                create_dir_stat(inode, dir.number_of_entries())
-            }
-        })?;
+        let st = handle_inode_mut_locked(
+            &mut inode_table,
+            &inode,
+            |InodeState { entry, handle_ref_count, .. }| {
+                let st = match entry {
+                    AuthFsEntry::ReadonlyDirectory { dir } => {
+                        create_dir_stat(inode, dir.number_of_entries())
+                    }
+                    AuthFsEntry::UnverifiedReadonly { file_size, .. }
+                    | AuthFsEntry::VerifiedReadonly { file_size, .. } => {
+                        create_stat(inode, *file_size, AccessMode::ReadOnly)
+                    }
+                    AuthFsEntry::VerifiedNew { editor } => {
+                        create_stat(inode, editor.size(), AccessMode::ReadWrite)
+                    }
+                    AuthFsEntry::VerifiedNewDirectory { dir } => {
+                        create_dir_stat(inode, dir.number_of_entries())
+                    }
+                }?;
+                *handle_ref_count += 1;
+                Ok(st)
+            },
+        )?;
+
         Ok(Entry {
             inode,
             generation: 0,
@@ -405,6 +472,38 @@
         })
     }
 
+    fn forget(&self, _ctx: Context, inode: Self::Inode, count: u64) {
+        let mut inode_table = self.inode_table.lock().unwrap();
+        let delete_now = handle_inode_mut_locked(
+            &mut inode_table,
+            &inode,
+            |InodeState { handle_ref_count, unlinked, .. }| {
+                if count > *handle_ref_count {
+                    error!(
+                        "Trying to decrease refcount of inode {} by {} (> current {})",
+                        inode, count, *handle_ref_count
+                    );
+                    panic!(); // log to logcat with error!
+                }
+                *handle_ref_count = handle_ref_count.saturating_sub(count);
+                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(
         &self,
         _ctx: Context,
@@ -473,19 +572,20 @@
     ) -> io::Result<(Entry, Option<Self::Handle>, fuse::sys::OpenOptions)> {
         // TODO(205169366): Implement mode properly.
         // TODO(205172873): handle O_TRUNC and O_EXCL properly.
-        let new_inode =
-            self.create_new_entry(parent, name, |parent_entry, basename, new_inode| {
-                match parent_entry {
-                    AuthFsEntry::VerifiedNewDirectory { dir } => {
-                        if dir.find_inode(basename).is_some() {
-                            return Err(io::Error::from_raw_os_error(libc::EEXIST));
-                        }
-                        let new_file = dir.create_file(basename, new_inode)?;
-                        Ok(AuthFsEntry::VerifiedNew { editor: new_file })
+        let new_inode = self.create_new_entry_with_ref_count(
+            parent,
+            name,
+            |parent_entry, basename, new_inode| match parent_entry {
+                AuthFsEntry::VerifiedNewDirectory { dir } => {
+                    if dir.has_entry(basename) {
+                        return Err(io::Error::from_raw_os_error(libc::EEXIST));
                     }
-                    _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
+                    let new_file = dir.create_file(basename, new_inode)?;
+                    Ok(AuthFsEntry::VerifiedNew { editor: new_file })
                 }
-            })?;
+                _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
+            },
+        )?;
 
         Ok((
             Entry {
@@ -651,22 +751,23 @@
         _umask: u32,
     ) -> io::Result<Entry> {
         // TODO(205169366): Implement mode properly.
-        let new_inode =
-            self.create_new_entry(parent, name, |parent_entry, basename, new_inode| {
-                match parent_entry {
-                    AuthFsEntry::VerifiedNewDirectory { dir } => {
-                        if dir.find_inode(basename).is_some() {
-                            return Err(io::Error::from_raw_os_error(libc::EEXIST));
-                        }
-                        let new_dir = dir.mkdir(basename, new_inode)?;
-                        Ok(AuthFsEntry::VerifiedNewDirectory { dir: new_dir })
+        let new_inode = self.create_new_entry_with_ref_count(
+            parent,
+            name,
+            |parent_entry, basename, new_inode| match parent_entry {
+                AuthFsEntry::VerifiedNewDirectory { dir } => {
+                    if dir.has_entry(basename) {
+                        return Err(io::Error::from_raw_os_error(libc::EEXIST));
                     }
-                    AuthFsEntry::ReadonlyDirectory { .. } => {
-                        Err(io::Error::from_raw_os_error(libc::EACCES))
-                    }
-                    _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
+                    let new_dir = dir.mkdir(basename, new_inode)?;
+                    Ok(AuthFsEntry::VerifiedNewDirectory { dir: new_dir })
                 }
-            })?;
+                AuthFsEntry::ReadonlyDirectory { .. } => {
+                    Err(io::Error::from_raw_os_error(libc::EACCES))
+                }
+                _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
+            },
+        )?;
 
         Ok(Entry {
             inode: new_inode,
@@ -677,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()?;
 
@@ -704,6 +867,36 @@
     }
 }
 
+fn handle_inode_locked<F, R>(
+    inode_table: &BTreeMap<Inode, InodeState>,
+    inode: &Inode,
+    handle_fn: F,
+) -> io::Result<R>
+where
+    F: FnOnce(&InodeState) -> io::Result<R>,
+{
+    if let Some(inode_state) = inode_table.get(inode) {
+        handle_fn(inode_state)
+    } else {
+        Err(io::Error::from_raw_os_error(libc::ENOENT))
+    }
+}
+
+fn handle_inode_mut_locked<F, R>(
+    inode_table: &mut BTreeMap<Inode, InodeState>,
+    inode: &Inode,
+    handle_fn: F,
+) -> io::Result<R>
+where
+    F: FnOnce(&mut InodeState) -> io::Result<R>,
+{
+    if let Some(inode_state) = inode_table.get_mut(inode) {
+        handle_fn(inode_state)
+    } else {
+        Err(io::Error::from_raw_os_error(libc::ENOENT))
+    }
+}
+
 fn cstr_to_path(cstr: &CStr) -> &Path {
     OsStr::from_bytes(cstr.to_bytes()).as_ref()
 }
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";