diff --git a/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl b/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
index 58ccfc3..bf4ac61 100644
--- a/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
+++ b/authfs/aidl/com/android/virt/fs/IVirtFdService.aidl
@@ -57,12 +57,20 @@
     long getFileSize(int fd);
 
     /**
+     * Open 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.
+     */
+    int openFileInDirectory(int dirFd, String pathname);
+
+    /**
      * Create 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.
      */
-    int createFileInDirectory(int fd, String basename);
+    int createFileInDirectory(int dirFd, String basename);
 
     /**
      * Create a directory inside the given remote directory FD.
@@ -70,5 +78,5 @@
      * @param basename The directory name to create. Must not contain directory separator.
      * @return file FD that represents the new created directory.
      */
-    int createDirectoryInDirectory(int id, String basename);
+    int createDirectoryInDirectory(int dirFd, String basename);
 }
diff --git a/authfs/fd_server/src/aidl.rs b/authfs/fd_server/src/aidl.rs
index 0c41eac..fa1914a 100644
--- a/authfs/fd_server/src/aidl.rs
+++ b/authfs/fd_server/src/aidl.rs
@@ -25,8 +25,8 @@
 use std::fs::File;
 use std::io;
 use std::os::unix::fs::FileExt;
-use std::os::unix::io::{AsRawFd, FromRawFd};
-use std::path::MAIN_SEPARATOR;
+use std::os::unix::io::{AsRawFd, FromRawFd, RawFd};
+use std::path::{Component, Path, PathBuf, MAIN_SEPARATOR};
 use std::sync::{Arc, Mutex};
 
 use crate::fsverity;
@@ -59,9 +59,11 @@
         file: File,
 
         /// Alternative Merkle tree stored in another file.
+        /// TODO(205987437): Replace with .fsv_meta file.
         alt_merkle_tree: Option<File>,
 
         /// Alternative signature stored in another file.
+        /// TODO(205987437): Replace with .fsv_meta file.
         alt_signature: Option<File>,
     },
 
@@ -69,6 +71,9 @@
     /// regular file and does not have any specific property.
     ReadWrite(File),
 
+    /// A read-only directory to serve by this server.
+    InputDir(Dir),
+
     /// A writable directory to serve by this server.
     OutputDir(Dir),
 }
@@ -132,7 +137,7 @@
                     new_errno_error(Errno::EIO)
                 })
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
         })
     }
 
@@ -165,7 +170,7 @@
                 // use.
                 Err(new_errno_error(Errno::ENOSYS))
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
         })
     }
 
@@ -195,7 +200,7 @@
                 // There is no signature for a writable file.
                 Err(new_errno_error(Errno::ENOSYS))
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
         })
     }
 
@@ -213,7 +218,7 @@
                     new_errno_error(Errno::EIO)
                 })? as i32)
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
         })
     }
 
@@ -229,7 +234,7 @@
                     new_errno_error(Errno::EIO)
                 })
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
         })
     }
 
@@ -254,7 +259,31 @@
                 // for a writable file.
                 Err(new_errno_error(Errno::ENOSYS))
             }
-            FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+            FdConfig::InputDir(_) | FdConfig::OutputDir(_) => Err(new_errno_error(Errno::EISDIR)),
+        })
+    }
+
+    fn openFileInDirectory(&self, 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 {
+            FdConfig::InputDir(dir) => {
+                let file = open_readonly_at(dir.as_raw_fd(), &path_buf).map_err(new_errno_error)?;
+
+                // TODO(205987437): Provide the corresponding ".fsv_meta" file when it's created.
+                Ok((
+                    file.as_raw_fd(),
+                    FdConfig::Readonly { file, alt_merkle_tree: None, alt_signature: None },
+                ))
+            }
+            FdConfig::OutputDir(_) => {
+                Err(new_errno_error(Errno::ENOSYS)) // TODO: Implement when needed
+            }
+            _ => Err(new_errno_error(Errno::ENOTDIR)),
         })
     }
 
@@ -263,6 +292,7 @@
             return Err(new_errno_error(Errno::EINVAL));
         }
         self.insert_new_fd(fd, |config| match config {
+            FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
             FdConfig::OutputDir(dir) => {
                 let new_fd = openat(
                     dir.as_raw_fd(),
@@ -286,6 +316,7 @@
             return Err(new_errno_error(Errno::EINVAL));
         }
         self.insert_new_fd(dir_fd, |config| match config {
+            FdConfig::InputDir(_) => Err(new_errno_error(Errno::EACCES)),
             FdConfig::OutputDir(_) => {
                 mkdirat(dir_fd, basename, Mode::S_IRWXU).map_err(new_errno_error)?;
                 let new_dir = Dir::openat(
@@ -313,3 +344,10 @@
 fn new_errno_error(errno: Errno) -> Status {
     new_binder_service_specific_error(errno as i32, errno.desc())
 }
+
+fn open_readonly_at(dir_fd: RawFd, path: &Path) -> nix::Result<File> {
+    let new_fd = openat(dir_fd, path, OFlag::O_RDONLY, Mode::empty())?;
+    // SAFETY: new_fd is just created successfully and not owned.
+    let new_file = unsafe { File::from_raw_fd(new_fd) };
+    Ok(new_file)
+}
diff --git a/authfs/fd_server/src/main.rs b/authfs/fd_server/src/main.rs
index bbcd49f..f5a3cba 100644
--- a/authfs/fd_server/src/main.rs
+++ b/authfs/fd_server/src/main.rs
@@ -78,9 +78,13 @@
     Ok((fd, FdConfig::ReadWrite(file)))
 }
 
+fn parse_arg_ro_dirs(arg: &str) -> Result<(i32, FdConfig)> {
+    let fd = arg.parse::<i32>()?;
+    Ok((fd, FdConfig::InputDir(Dir::from_fd(fd)?)))
+}
+
 fn parse_arg_rw_dirs(arg: &str) -> Result<(i32, FdConfig)> {
     let fd = arg.parse::<i32>()?;
-
     Ok((fd, FdConfig::OutputDir(Dir::from_fd(fd)?)))
 }
 
@@ -100,6 +104,10 @@
              .long("rw-fds")
              .multiple(true)
              .number_of_values(1))
+        .arg(clap::Arg::with_name("ro-dirs")
+             .long("ro-dirs")
+             .multiple(true)
+             .number_of_values(1))
         .arg(clap::Arg::with_name("rw-dirs")
              .long("rw-dirs")
              .multiple(true)
@@ -122,6 +130,12 @@
             fd_pool.insert(fd, config);
         }
     }
+    if let Some(args) = matches.values_of("ro-dirs") {
+        for arg in args {
+            let (fd, config) = parse_arg_ro_dirs(arg)?;
+            fd_pool.insert(fd, config);
+        }
+    }
     if let Some(args) = matches.values_of("rw-dirs") {
         for arg in args {
             let (fd, config) = parse_arg_rw_dirs(arg)?;
diff --git a/authfs/src/file.rs b/authfs/src/file.rs
index bbe5e6c..6353209 100644
--- a/authfs/src/file.rs
+++ b/authfs/src/file.rs
@@ -1,12 +1,13 @@
-mod remote_dir;
+mod dir;
 mod remote_file;
 
-pub use remote_dir::RemoteDirEditor;
+pub use dir::{InMemoryDir, RemoteDirEditor};
 pub use remote_file::{RemoteFileEditor, RemoteFileReader, RemoteMerkleTreeReader};
 
 use binder::unstable_api::{new_spibinder, AIBinder};
 use binder::FromIBinder;
 use std::io;
+use std::path::{Path, MAIN_SEPARATOR};
 
 use crate::common::CHUNK_SIZE;
 use authfs_aidl_interface::aidl::com::android::virt::fs::IVirtFdService::IVirtFdService;
@@ -71,3 +72,12 @@
     /// Resizes the file to the new size.
     fn resize(&self, size: u64) -> io::Result<()>;
 }
+
+/// Checks whether the path is a simple file name without any directory separator.
+pub fn validate_basename(path: &Path) -> io::Result<()> {
+    if matches!(path.to_str(), Some(path_str) if !path_str.contains(MAIN_SEPARATOR)) {
+        Ok(())
+    } else {
+        Err(io::Error::from_raw_os_error(libc::EINVAL))
+    }
+}
diff --git a/authfs/src/file/remote_dir.rs b/authfs/src/file/dir.rs
similarity index 66%
rename from authfs/src/file/remote_dir.rs
rename to authfs/src/file/dir.rs
index 2e1bc33..2eaaddd 100644
--- a/authfs/src/file/remote_dir.rs
+++ b/authfs/src/file/dir.rs
@@ -14,12 +14,12 @@
  * limitations under the License.
  */
 
-use std::collections::HashMap;
+use std::collections::{hash_map, HashMap};
 use std::io;
 use std::path::{Path, PathBuf};
 
 use super::remote_file::RemoteFileEditor;
-use super::{VirtFdService, VirtFdServiceStatus};
+use super::{validate_basename, VirtFdService, VirtFdServiceStatus};
 use crate::fsverity::VerifiedFileEditor;
 use crate::fusefs::Inode;
 
@@ -58,12 +58,12 @@
         self.entries.len() as u16 // limited to MAX_ENTRIES
     }
 
-    /// Creates a remote file at the current directory. If succeed, the returned remote FD is
-    /// stored in `entries` as the inode number.
+    /// Creates a remote file named `basename` with corresponding `inode` at the current directory.
     pub fn create_file(
         &mut self,
         basename: &Path,
-    ) -> io::Result<(Inode, VerifiedFileEditor<RemoteFileEditor>)> {
+        inode: Inode,
+    ) -> io::Result<VerifiedFileEditor<RemoteFileEditor>> {
         self.validate_argument(basename)?;
 
         let basename_str =
@@ -72,17 +72,16 @@
             .service
             .createFileInDirectory(self.remote_dir_fd, basename_str)
             .map_err(into_io_error)?;
-        let new_inode = new_fd as Inode;
 
         let new_remote_file =
             VerifiedFileEditor::new(RemoteFileEditor::new(self.service.clone(), new_fd));
-        self.entries.insert(basename.to_path_buf(), new_inode);
-        Ok((new_inode, new_remote_file))
+        self.entries.insert(basename.to_path_buf(), inode);
+        Ok(new_remote_file)
     }
 
-    /// Creates a remote directory at the current directory. If succeed, the returned remote FD is
-    /// stored in `entries` as the inode number.
-    pub fn mkdir(&mut self, basename: &Path) -> io::Result<(Inode, RemoteDirEditor)> {
+    /// Creates a remote directory named `basename` with corresponding `inode` at the current
+    /// directory.
+    pub fn mkdir(&mut self, basename: &Path, inode: Inode) -> io::Result<RemoteDirEditor> {
         self.validate_argument(basename)?;
 
         let basename_str =
@@ -91,11 +90,10 @@
             .service
             .createDirectoryInDirectory(self.remote_dir_fd, basename_str)
             .map_err(into_io_error)?;
-        let new_inode = new_fd as Inode;
 
         let new_remote_dir = RemoteDirEditor::new(self.service.clone(), new_fd);
-        self.entries.insert(basename.to_path_buf(), new_inode);
-        Ok((new_inode, new_remote_dir))
+        self.entries.insert(basename.to_path_buf(), inode);
+        Ok(new_remote_dir)
     }
 
     /// Returns the inode number of a file or directory named `name` previously created through
@@ -106,7 +104,8 @@
 
     fn validate_argument(&self, basename: &Path) -> io::Result<()> {
         // Kernel should only give us a basename.
-        debug_assert!(basename.parent().is_none());
+        debug_assert!(validate_basename(basename).is_ok());
+
         if self.entries.contains_key(basename) {
             Err(io::Error::from_raw_os_error(libc::EEXIST))
         } else if self.entries.len() >= MAX_ENTRIES.into() {
@@ -117,6 +116,43 @@
     }
 }
 
+/// An in-memory directory representation of a directory structure.
+pub struct InMemoryDir(HashMap<PathBuf, Inode>);
+
+impl InMemoryDir {
+    /// Creates an empty instance of `InMemoryDir`.
+    pub fn new() -> Self {
+        // Hash map is empty since "." and ".." are excluded in entries.
+        InMemoryDir(HashMap::new())
+    }
+
+    /// Returns the number of entries in the directory (not including "." and "..").
+    pub fn number_of_entries(&self) -> u16 {
+        self.0.len() as u16 // limited to MAX_ENTRIES
+    }
+
+    /// Adds an entry (name and the inode number) to the directory. Fails if already exists. The
+    /// caller is responsible for ensure the inode uniqueness.
+    pub fn add_entry(&mut self, basename: &Path, inode: Inode) -> io::Result<()> {
+        validate_basename(basename)?;
+        if self.0.len() >= MAX_ENTRIES.into() {
+            return Err(io::Error::from_raw_os_error(libc::EMLINK));
+        }
+
+        if let hash_map::Entry::Vacant(entry) = self.0.entry(basename.to_path_buf()) {
+            entry.insert(inode);
+            Ok(())
+        } else {
+            Err(io::Error::from_raw_os_error(libc::EEXIST))
+        }
+    }
+
+    /// Looks up an entry inode by name. `None` if not found.
+    pub fn lookup_inode(&self, basename: &Path) -> Option<Inode> {
+        self.0.get(basename).copied()
+    }
+}
+
 fn into_io_error(e: VirtFdServiceStatus) -> io::Error {
     let maybe_errno = e.service_specific_error();
     if maybe_errno > 0 {
diff --git a/authfs/src/fusefs.rs b/authfs/src/fusefs.rs
index 69a5cb8..ca73174 100644
--- a/authfs/src/fusefs.rs
+++ b/authfs/src/fusefs.rs
@@ -14,9 +14,9 @@
  * limitations under the License.
  */
 
-use anyhow::Result;
-use log::{debug, error, warn};
-use std::collections::{btree_map, BTreeMap, HashMap};
+use anyhow::{bail, Result};
+use log::{debug, warn};
+use std::collections::{btree_map, BTreeMap};
 use std::convert::TryFrom;
 use std::ffi::{CStr, OsStr};
 use std::fs::OpenOptions;
@@ -25,6 +25,7 @@
 use std::option::Option;
 use std::os::unix::{ffi::OsStrExt, io::AsRawFd};
 use std::path::{Path, PathBuf};
+use std::sync::atomic::{AtomicU64, Ordering};
 use std::sync::Mutex;
 use std::time::Duration;
 
@@ -36,7 +37,7 @@
 
 use crate::common::{divide_roundup, ChunkedSizeIter, CHUNK_SIZE};
 use crate::file::{
-    RandomWrite, ReadByChunk, RemoteDirEditor, RemoteFileEditor, RemoteFileReader,
+    InMemoryDir, RandomWrite, ReadByChunk, RemoteDirEditor, RemoteFileEditor, RemoteFileReader,
     RemoteMerkleTreeReader,
 };
 use crate::fsverity::{VerifiedFileEditor, VerifiedFileReader};
@@ -57,6 +58,8 @@
 
 /// `AuthFsEntry` defines the filesystem entry type supported by AuthFS.
 pub enum AuthFsEntry {
+    /// A read-only directory (writable during initialization). Root directory is an example.
+    ReadonlyDirectory { dir: InMemoryDir },
     /// A file type that is verified against fs-verity signature (thus read-only). The file is
     /// served from a remote server.
     VerifiedReadonly {
@@ -74,31 +77,60 @@
 }
 
 // AuthFS needs to be `Sync` to be accepted by fuse::worker::start_message_loop as a `FileSystem`.
-struct AuthFs {
+pub struct AuthFs {
     /// Table for `Inode` to `AuthFsEntry` lookup. This needs to be `Sync` to be used in
     /// `fuse::worker::start_message_loop`.
     inode_table: Mutex<BTreeMap<Inode, AuthFsEntry>>,
 
-    /// Root directory entry table for path to `Inode` lookup. The root directory content should
-    /// remain constant throughout the filesystem's lifetime.
-    root_entries: HashMap<PathBuf, Inode>,
+    /// The next available inode number.
+    next_inode: AtomicU64,
 }
 
+// Implementation for preparing an `AuthFs` instance, before starting to serve.
+// TODO(victorhsieh): Consider implement a builder to separate the mutable initialization from the
+// immutable / interiorly mutable serving phase.
 impl AuthFs {
-    pub fn new(root_entries_by_path: HashMap<PathBuf, AuthFsEntry>) -> AuthFs {
-        let mut next_inode = ROOT_INODE + 1;
+    pub fn new() -> AuthFs {
         let mut inode_table = BTreeMap::new();
-        let mut root_entries = HashMap::new();
+        inode_table.insert(ROOT_INODE, AuthFsEntry::ReadonlyDirectory { dir: InMemoryDir::new() });
 
-        root_entries_by_path.into_iter().for_each(|(path_buf, entry)| {
-            next_inode += 1;
-            root_entries.insert(path_buf, next_inode);
-            inode_table.insert(next_inode, entry);
-        });
-
-        AuthFs { inode_table: Mutex::new(inode_table), root_entries }
+        AuthFs { inode_table: Mutex::new(inode_table), next_inode: AtomicU64::new(ROOT_INODE + 1) }
     }
 
+    pub fn add_entry_at_root_dir(
+        &mut self,
+        basename: PathBuf,
+        entry: AuthFsEntry,
+    ) -> Result<Inode> {
+        if basename.is_absolute() {
+            bail!("Invalid entry name: {:?}", basename);
+        }
+
+        let inode_table = &mut *self.inode_table.get_mut().unwrap();
+        match inode_table
+            .get_mut(&ROOT_INODE)
+            .ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?
+        {
+            AuthFsEntry::ReadonlyDirectory { dir } => {
+                let new_inode = self.next_inode.fetch_add(1, Ordering::Relaxed);
+
+                dir.add_entry(&basename, new_inode)?;
+                if inode_table.insert(new_inode, entry).is_some() {
+                    bail!(
+                        "Found duplicated inode {} when adding {}",
+                        new_inode,
+                        basename.display()
+                    );
+                }
+                Ok(new_inode)
+            }
+            _ => bail!("Not a ReadonlyDirectory"),
+        }
+    }
+}
+
+// Implementation for serving requests.
+impl AuthFs {
     /// Handles the file associated with `inode` if found. This function returns whatever
     /// `handle_fn` returns.
     fn handle_inode<F, R>(&self, inode: &Inode, handle_fn: F) -> io::Result<R>
@@ -106,31 +138,41 @@
         F: FnOnce(&AuthFsEntry) -> io::Result<R>,
     {
         let inode_table = self.inode_table.lock().unwrap();
-        let config =
+        let entry =
             inode_table.get(inode).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
-        handle_fn(config)
+        handle_fn(entry)
     }
 
-    /// Inserts a new inode and corresponding `AuthFsEntry` created by `create_fn` to the inode
-    /// table, then returns the new inode number.
-    fn insert_new_inode<F>(&self, inode: &Inode, create_fn: F) -> io::Result<Inode>
+    /// Adds a new entry `name` created by `create_fn` at `parent_inode`.
+    ///
+    /// 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
+    /// table.
+    ///
+    /// `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>(
+        &self,
+        parent_inode: Inode,
+        name: &CStr,
+        create_fn: F,
+    ) -> io::Result<Inode>
     where
-        F: FnOnce(&mut AuthFsEntry) -> io::Result<(Inode, AuthFsEntry)>,
+        F: FnOnce(&mut AuthFsEntry, &Path, Inode) -> io::Result<AuthFsEntry>,
     {
         let mut inode_table = self.inode_table.lock().unwrap();
-        let mut config =
-            inode_table.get_mut(inode).ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
-        let (new_inode, new_file_config) = create_fn(&mut config)?;
+        let mut parent_entry = inode_table
+            .get_mut(&parent_inode)
+            .ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
+
+        let new_inode = self.next_inode.fetch_add(1, Ordering::Relaxed);
+        let basename: &Path = cstr_to_path(name);
+        let new_file_entry = create_fn(&mut parent_entry, basename, new_inode)?;
         if let btree_map::Entry::Vacant(entry) = inode_table.entry(new_inode) {
-            entry.insert(new_file_config);
+            entry.insert(new_file_entry);
             Ok(new_inode)
         } else {
-            // We can't assume fd_server is trusted, so the returned FD may collide with existing
-            // one, even when we are creating a new file. Do not override an existing FD. In terms
-            // of security, it is better to "leak" the file created earlier, than returning an
-            // existing inode as a new file.
-            error!("Inode {} already exists, do not override", new_inode);
-            Err(io::Error::from_raw_os_error(libc::EIO))
+            unreachable!("Unexpected duplication of inode {}", new_inode);
         }
     }
 }
@@ -247,8 +289,8 @@
     Ok(total)
 }
 
-// No need to support enumerating directory entries.
-struct EmptyDirectoryIterator {}
+// TODO(205715172): Support enumerating directory entries.
+pub struct EmptyDirectoryIterator {}
 
 impl DirectoryIterator for EmptyDirectoryIterator {
     fn next(&mut self) -> Option<DirEntry> {
@@ -272,58 +314,47 @@
     }
 
     fn lookup(&self, _ctx: Context, parent: Inode, name: &CStr) -> io::Result<Entry> {
-        if parent == ROOT_INODE {
-            let inode = *self
-                .root_entries
-                .get(cstr_to_path(name))
-                .ok_or_else(|| io::Error::from_raw_os_error(libc::ENOENT))?;
-            // 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`).
-            let st = self.handle_inode(&inode, |config| match config {
-                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())
-                }
-            })?;
-            Ok(Entry {
-                inode,
-                generation: 0,
-                attr: st,
-                entry_timeout: DEFAULT_METADATA_TIMEOUT,
-                attr_timeout: DEFAULT_METADATA_TIMEOUT,
-            })
-        } else {
-            let inode = self.handle_inode(&parent, |config| match config {
-                AuthFsEntry::VerifiedNewDirectory { dir } => {
-                    let path: &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 st = self.handle_inode(&inode, |config| match config {
-                AuthFsEntry::VerifiedNew { editor } => {
-                    create_stat(inode, editor.size(), AccessMode::ReadWrite)
-                }
-                AuthFsEntry::VerifiedNewDirectory { dir } => {
-                    create_dir_stat(inode, dir.number_of_entries())
-                }
-                _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
-            })?;
-            Ok(Entry {
-                inode,
-                generation: 0,
-                attr: st,
-                entry_timeout: DEFAULT_METADATA_TIMEOUT,
-                attr_timeout: DEFAULT_METADATA_TIMEOUT,
-            })
-        }
+        // 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)),
+        })?;
+
+        // 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`).
+
+        // Create the entry's stat if found.
+        let st = self.handle_inode(&inode, |entry| match entry {
+            AuthFsEntry::ReadonlyDirectory { .. } => {
+                unreachable!("FUSE shouldn't need to look up the root inode");
+                //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())
+            }
+        })?;
+        Ok(Entry {
+            inode,
+            generation: 0,
+            attr: st,
+            entry_timeout: DEFAULT_METADATA_TIMEOUT,
+            attr_timeout: DEFAULT_METADATA_TIMEOUT,
+        })
     }
 
     fn getattr(
@@ -335,17 +366,20 @@
         self.handle_inode(&inode, |config| {
             Ok((
                 match config {
+                    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)?
+                        create_stat(inode, *file_size, AccessMode::ReadOnly)
                     }
                     AuthFsEntry::VerifiedNew { editor } => {
-                        create_stat(inode, editor.size(), AccessMode::ReadWrite)?
+                        create_stat(inode, editor.size(), AccessMode::ReadWrite)
                     }
                     AuthFsEntry::VerifiedNewDirectory { dir } => {
-                        create_dir_stat(inode, dir.number_of_entries())?
+                        create_dir_stat(inode, dir.number_of_entries())
                     }
-                },
+                }?,
                 DEFAULT_METADATA_TIMEOUT,
             ))
         })
@@ -368,7 +402,8 @@
                     // No need to check access modes since all the modes are allowed to the
                     // read-writable file.
                 }
-                AuthFsEntry::VerifiedNewDirectory { .. } => {
+                AuthFsEntry::ReadonlyDirectory { .. }
+                | AuthFsEntry::VerifiedNewDirectory { .. } => {
                     // TODO(victorhsieh): implement when needed.
                     return Err(io::Error::from_raw_os_error(libc::ENOSYS));
                 }
@@ -390,17 +425,19 @@
     ) -> 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.insert_new_inode(&parent, |config| match config {
-            AuthFsEntry::VerifiedNewDirectory { dir } => {
-                let basename: &Path = cstr_to_path(name);
-                if dir.find_inode(basename).is_some() {
-                    return Err(io::Error::from_raw_os_error(libc::EEXIST));
+        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 })
+                    }
+                    _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
                 }
-                let (new_inode, new_file) = dir.create_file(basename)?;
-                Ok((new_inode, AuthFsEntry::VerifiedNew { editor: new_file }))
-            }
-            _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
-        })?;
+            })?;
 
         Ok((
             Entry {
@@ -566,17 +603,19 @@
         _umask: u32,
     ) -> io::Result<Entry> {
         // TODO(205169366): Implement mode properly.
-        let new_inode = self.insert_new_inode(&parent, |config| match config {
-            AuthFsEntry::VerifiedNewDirectory { dir } => {
-                let basename: &Path = cstr_to_path(name);
-                if dir.find_inode(basename).is_some() {
-                    return Err(io::Error::from_raw_os_error(libc::EEXIST));
+        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 })
+                    }
+                    _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
                 }
-                let (new_inode, new_dir) = dir.mkdir(basename)?;
-                Ok((new_inode, AuthFsEntry::VerifiedNewDirectory { dir: new_dir }))
-            }
-            _ => Err(io::Error::from_raw_os_error(libc::EBADF)),
-        })?;
+            })?;
 
         Ok(Entry {
             inode: new_inode,
@@ -590,7 +629,7 @@
 
 /// Mount and start the FUSE instance. This requires CAP_SYS_ADMIN.
 pub fn loop_forever(
-    root_entries: HashMap<PathBuf, AuthFsEntry>,
+    authfs: AuthFs,
     mountpoint: &Path,
     extra_options: &Option<String>,
 ) -> Result<(), fuse::Error> {
@@ -615,12 +654,7 @@
     fuse::mount(mountpoint, "authfs", libc::MS_NOSUID | libc::MS_NODEV, &mount_options)
         .expect("Failed to mount fuse");
 
-    fuse::worker::start_message_loop(
-        dev_fuse,
-        MAX_WRITE_BYTES,
-        MAX_READ_BYTES,
-        AuthFs::new(root_entries),
-    )
+    fuse::worker::start_message_loop(dev_fuse, MAX_WRITE_BYTES, MAX_READ_BYTES, authfs)
 }
 
 fn cstr_to_path(cstr: &CStr) -> &Path {
diff --git a/authfs/src/main.rs b/authfs/src/main.rs
index f6a2a56..ae446e3 100644
--- a/authfs/src/main.rs
+++ b/authfs/src/main.rs
@@ -29,7 +29,6 @@
 
 use anyhow::{bail, Context, Result};
 use log::error;
-use std::collections::HashMap;
 use std::convert::TryInto;
 use std::path::PathBuf;
 use structopt::StructOpt;
@@ -44,7 +43,7 @@
 use auth::FakeAuthenticator;
 use file::{RemoteDirEditor, RemoteFileEditor, RemoteFileReader, RemoteMerkleTreeReader};
 use fsverity::{VerifiedFileEditor, VerifiedFileReader};
-use fusefs::AuthFsEntry;
+use fusefs::{AuthFs, AuthFsEntry};
 
 #[derive(StructOpt)]
 struct Args {
@@ -160,51 +159,49 @@
     Ok(AuthFsEntry::VerifiedNewDirectory { dir })
 }
 
-fn prepare_root_dir_entries(args: &Args) -> Result<HashMap<PathBuf, AuthFsEntry>> {
-    let mut root_entries = HashMap::new();
-
+fn prepare_root_dir_entries(authfs: &mut AuthFs, args: &Args) -> Result<()> {
     let service = file::get_rpc_binder_service(args.cid)?;
 
     for config in &args.remote_ro_file {
-        root_entries.insert(
+        authfs.add_entry_at_root_dir(
             remote_fd_to_path_buf(config.remote_fd),
             new_remote_verified_file_entry(
                 service.clone(),
                 config.remote_fd,
                 service.getFileSize(config.remote_fd)?.try_into()?,
             )?,
-        );
+        )?;
     }
 
     for remote_fd in &args.remote_ro_file_unverified {
         let remote_fd = *remote_fd;
-        root_entries.insert(
+        authfs.add_entry_at_root_dir(
             remote_fd_to_path_buf(remote_fd),
             new_remote_unverified_file_entry(
                 service.clone(),
                 remote_fd,
                 service.getFileSize(remote_fd)?.try_into()?,
             )?,
-        );
+        )?;
     }
 
     for remote_fd in &args.remote_new_rw_file {
         let remote_fd = *remote_fd;
-        root_entries.insert(
+        authfs.add_entry_at_root_dir(
             remote_fd_to_path_buf(remote_fd),
             new_remote_new_verified_file_entry(service.clone(), remote_fd)?,
-        );
+        )?;
     }
 
     for remote_fd in &args.remote_new_rw_dir {
         let remote_fd = *remote_fd;
-        root_entries.insert(
+        authfs.add_entry_at_root_dir(
             remote_fd_to_path_buf(remote_fd),
             new_remote_new_verified_dir_entry(service.clone(), remote_fd)?,
-        );
+        )?;
     }
 
-    Ok(root_entries)
+    Ok(())
 }
 
 fn remote_fd_to_path_buf(fd: i32) -> PathBuf {
@@ -219,8 +216,9 @@
         android_logger::Config::default().with_tag("authfs").with_min_level(log_level),
     );
 
-    let root_entries = prepare_root_dir_entries(&args)?;
-    fusefs::loop_forever(root_entries, &args.mount_point, &args.extra_options)?;
+    let mut authfs = AuthFs::new();
+    prepare_root_dir_entries(&mut authfs, &args)?;
+    fusefs::loop_forever(authfs, &args.mount_point, &args.extra_options)?;
     bail!("Unexpected exit after the handler loop")
 }