9ns: Add fs_files and tree_files
authorBarret Rhoden <brho@cs.berkeley.edu>
Thu, 1 Mar 2018 02:23:40 +0000 (21:23 -0500)
committerBarret Rhoden <brho@cs.berkeley.edu>
Mon, 30 Apr 2018 18:31:43 +0000 (14:31 -0400)
fs_files are a basic structure that any 9ns device can use for a file
that contains data.  It's mostly a struct dir and a pagemap, though
future versions might not have a page mapping.  fs_files also come with
a set of operations, which will grow over time.

tree_files are fs_files that are arranged in a hierarchy consisting of
parents and children.  There are no hardlinks, but there are symlinks.
tree_files also come with a set of operations, which a device can use to
perform its role in operations such as lookups and creation.

Both fs_files and tree_files come with a collection of helper utilities,
such as fs_file_stat(), which a device can call.  The helpers handle the
various races and whatnot.

Devices do not need to use these at all, though my long term plan is to
replace all of the struct dirtabs with fs_files.  The dirtab is
basically a dir, but with the storage for the name built-in.

Signed-off-by: Barret Rhoden <brho@cs.berkeley.edu>
kern/include/fs_file.h [new file with mode: 0644]
kern/include/tree_file.h [new file with mode: 0644]
kern/src/ns/Kbuild
kern/src/ns/fs_file.c [new file with mode: 0644]
kern/src/ns/tree_file.c [new file with mode: 0644]

diff --git a/kern/include/fs_file.h b/kern/include/fs_file.h
new file mode 100644 (file)
index 0000000..00e6046
--- /dev/null
@@ -0,0 +1,142 @@
+/* Copyright (c) 2018 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * fs_file: structs and helpers for files for 9ns devices
+ */
+
+#pragma once
+
+#include <ns.h>
+#include <pagemap.h>
+
+/* fs_file has all the info of the 9ns dir and the dirtab (which is a subset of
+ * struct dir), plus whatever is needed for generic mmappable filesystems.
+ * Specifically, it has a page_map and a few synchronization fields.  It doesn't
+ * need to support mmap either.  Longer range, fs_file can replace dirtab for
+ * static device filesystems.
+ *
+ * Most fs_files will end up being tree_files (see below).  Some devices might
+ * use fs_files that are hooked in to their own tree structures.
+ *
+ * fs_info is for devices to use.  For instance, #mnt will probably have an
+ * actual chan for every walked fs_file.  It will use that chan/FID for all of
+ * its operations on the backend: walking to discover child files, stat()ing to
+ * get fs_file metadata, reading and writing pages for the page cache, etc.
+ *
+ *
+ * Synchronization rules
+ * ------------------
+ * Note this qlock is also used by tree_file code.  See below for details.
+ *
+ * Hold the qlock when changing the contents of a file.  This includes writes
+ * (which need to adjust the len and add data), truncate / hole-punches
+ * (which need to adjust the len and remove data), changing parts of dir (name,
+ * permissions/mode, atimes), etc.  Tree files will hold this qlock when
+ * changing a parent's children.
+ *
+ * Readers who just 'peak' at atomically-writable fields do not need to grab the
+ * qlock.  For example, you can glance at dir->perms.  In arbitrary cases, you
+ * can't look at name, since we can't change it atomically (it can smear or run
+ * into other issues).  'name' is somewhat special: if you find the tree_file
+ * via a RCU protected wc hash lookup, you can access name.
+ *
+ * fs_file_read() can skip the qlock in the common case.  It can try to grab a
+ * page from the PM (if it was there, then some ordering exists on the
+ * concurrent ops where the read partially succeeds).  If the read fails to find
+ * a page, then we'd need to lock, since that interacts with length.
+ *
+ * There's actually not a lot in dir that is atomically writable.
+ * atime/mtime/ctime won't be when we use timespecs.  We might be able to craft
+ * something for lockless reads of dir state with seq counters.  That would save
+ * a qlock for each fs_file on a readdir.  It's a little tricky; we probably
+ * need to kfree_rcu the dir->name (never leak in a convD2M, even if we retry),
+ * and we need to be careful about multi-field changes where the changer might
+ * block.  i.e. don't hold a seq lock when making a backend op, which could
+ * block.  Not too concerned with this for now, esp since it's not clear how
+ * chown will work.
+ *
+ * Note that even if we can atomically write to the dir, we should still grab
+ * the qlock.  The reason is that there may be readers who want to make sure
+ * parts of the dir doesn't change.
+ *
+ * The PM code is pretty rough.  For now, we're using the old VFS PM code, but
+ * it needs a few changes:
+ * - Hole punching / truncate:  pm_remove_contig() leaves behind pages if they
+ *   were concurrently opened.  We can't detach from the tree since the pm_page
+ *   assumes it is always hooked in.  This means a truncate during a read or
+ *   mmap could leave data behind in the PM, which will be accessible when len
+ *   gets increased again (e.g. seek and write).  Truncate could zero that page,
+ *   though we'd need a history counter so reads don't see a partial value.
+ *   Further, pinned VMRs get skipped.  During trunc, they should get removed
+ *   and generate a SIGBUS on access.
+ * - Heavily integrated with struct page.  Maybe some sort of 'struct page' on
+ *   demand, that is built for an IO mapping.  There might be some huge-page
+ *   stuff here too.
+ * - The pm_ops callbacks and whatnot could use some help, even just the
+ *   arguments and indirections.  Maybe integrate them more into the funcs, e.g.
+ *   fs_file_*().  They probably should be fs_file_ops.  For now, the pm ops
+ *   assume the qlock is held.
+ */
+
+struct fs_file;
+
+/* TODO: Once we get rid of the VFS and rework the PM, we can put the PM ops in
+ * here properly. */
+struct fs_file_ops {
+       struct page_map_operations;     /* readpage and writepage */
+       void (*punch_hole)(struct fs_file *f, off64_t begin, off64_t end);
+       bool (*can_grow_to)(struct fs_file *f, size_t len);
+};
+
+#define FSF_DIRTY                              (1 << 1)
+
+struct fs_file {
+       struct dir                                      dir;
+       int                                                     flags;
+       qlock_t                                         qlock;
+       struct fs_file_ops                      *ops;
+       struct page_map                         *pm;
+       void                                            *priv;
+
+       /* optional inline storage */
+       char                                            static_name[KNAMELEN];  /* for dir->name */
+       struct page_map                         static_pm;                              /* for pm */
+       /* we need to be aligned to 64 bytes for the linker tables. */
+} __attribute__ ((aligned(64)));
+
+static inline bool caller_has_file_perms(struct fs_file *f, int omode)
+{
+       return caller_has_dir_perms(&f->dir, omode);
+}
+
+static inline void fs_file_perm_check(struct fs_file *f, int omode)
+{
+       dir_perm_check(&f->dir, omode);
+}
+
+void fs_file_init(struct fs_file *f, const char *name, struct fs_file_ops *ops);
+void fs_file_set_basename(struct fs_file *f, const char *name);
+void fs_file_change_basename(struct fs_file *f, const char *name);
+void fs_file_init_dir(struct fs_file *f, int dir_type, int dir_dev,
+                      struct username *user, int perm);
+void fs_file_copy_from_dir(struct fs_file *f, struct dir *dir);
+void cleanup_fs_file(struct fs_file *f);
+
+#define FSF_ATIME                              (1 << 0)
+#define FSF_BTIME                              (1 << 1)
+#define FSF_CTIME                              (1 << 2)
+#define FSF_MTIME                              (1 << 3)
+
+void __set_acmtime_to(struct fs_file *f, int which, struct timespec *t);
+void __set_acmtime(struct fs_file *f, int which);
+void set_acmtime_to(struct fs_file *f, int which, struct timespec *t);
+void set_acmtime_noperm(struct fs_file *f, int which);
+
+size_t fs_file_stat(struct fs_file *f, uint8_t *m_buf, size_t m_buf_sz);
+void fs_file_truncate(struct fs_file *f, off64_t to);
+size_t fs_file_read(struct fs_file *f, uint8_t *buf, size_t count,
+                    off64_t offset);
+size_t fs_file_write(struct fs_file *f, const uint8_t *buf, size_t count,
+                     off64_t offset);
+size_t fs_file_wstat(struct fs_file *f, uint8_t *m_buf, size_t m_buf_sz);
diff --git a/kern/include/tree_file.h b/kern/include/tree_file.h
new file mode 100644 (file)
index 0000000..68a14af
--- /dev/null
@@ -0,0 +1,274 @@
+/* Copyright (c) 2018 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * tree_file: structs and helpers to for a tree-based filesystem for 9ns
+ * devices.
+ */
+
+#pragma once
+
+#include <fs_file.h>
+#include <ns.h>
+#include <list.h>
+#include <rcu.h>
+
+struct tree_file;
+struct tree_filesystem;
+
+/* The walk cache encapsulates a couple things related to caching, similar to
+ * the dentry cache in the VFS.
+ * - the parent -> child links in a hash table
+ * - the LRU list, consisting of all tree files with kref == 0
+ *
+ * LRU notes.  Once a TF gets linked into a tree:
+ * - a TF is on the LRU IFF its refcnt == 0
+ * - a TF is on the LRU only if it is in the tree
+ * - any time kref gets set to 0, we consider putting it on the LRU (if not
+ *   DISCONNECTED / in the tree).  anytime it is increffed from 0, we yank it.
+ * - NEG entries are always kref == 0, and are on the LRU list if they are in
+ *   the tree.  They are never increffed, only rcu-read.
+ */
+struct walk_cache {
+       spinlock_t                                      lru_lock;
+       struct list_head                        lru;
+       spinlock_t                                      ht_lock;
+       struct hash_helper                      hh;             /* parts are rcu-read */
+       struct hlist_head                       *ht;
+       struct hlist_head                       static_ht[HASH_INIT_SZ];
+};
+
+/* All ops that operate on a parent have the parent qlocked.
+ *
+ * free(): the TF is being freed.  Might be called on TFs that the TFS is
+ * unaware of (e.g. lookup threw an error).
+ *
+ * unlink(): child is being unlinked from the parent.
+ *
+ * lookup(): backends fill in the child TF with whatever it knows about the
+ * entry.  This function is optional.  TFSs whose entire tree is in the frontend
+ * (e.g.  ramfs) don't do lookups from the non-existent backend.  This
+ * structure, positive or negative, will be used until it is unlinked.
+ *
+ * create(): given parent and it's initialized child struct, create the file and
+ * do whatever else you need (e.g. 9p backend does the create).  Same as lookup,
+ * the TFS needs to fill in child->dir, except for name.  Note we don't pass
+ * omode.  That's handled in the device's front-end create: open the chan after
+ * creating.
+ *
+ * rename(): rename / move TF from the old_parent to the new_parent, and change
+ * the name to name (NULL == no change).  Note that the rename op does *not* set
+ * the TF's name yet.  Be careful changing any fields in the TF, since it is
+ * still in old_parent's HT.
+ *
+ * has_children(): TFSs that use the front end as a cache (e.g. #mnt) need to
+ * check with their backend to know if there are children or not.  Checking the
+ * children list isn't necessarily sufficient.
+ */
+struct tree_file_ops {
+       void (*free)(struct tree_file *tf);
+       void (*unlink)(struct tree_file *parent, struct tree_file *child);
+       void (*lookup)(struct tree_file *parent, struct tree_file *child);
+       void (*create)(struct tree_file *parent, struct tree_file *child, int perm);
+       void (*rename)(struct tree_file *tf, struct tree_file *old_parent,
+                      struct tree_file *new_parent, const char *name, int flags);
+       bool (*has_children)(struct tree_file *parent);
+};
+
+struct tree_filesystem {
+       struct walk_cache                       wc;
+       struct tree_file_ops            tf_ops;
+       struct fs_file_ops                      fs_ops;
+       qlock_t                                         rename_mtx;
+       struct tree_file                        *root;
+       void                                            *priv;
+};
+
+/* The tree_file is an fs_file (i.e. the first struct field) that exists in a
+ * tree filesystem with parent/child relationships.
+ *
+ * Children hold krefs on their parents.  Parents have weak refs (i.e. not a
+ * kref) on their children.  Parent's have a list of *known* children.  The
+ * backend of the FS (e.g. the other side of #mnt) may know of other children.
+ * In this way, the parent's list is a cache.  For devices like a ramfs or any
+ * dynamic, completely tree-based system (e.g. #srv), the tree filesystem is the
+ * authoritative FS; there is no backend.
+ *
+ * If we know of a parent-child relationship (i.e. it's in the tree_filesystem),
+ * then the following invariants are true:
+ * - The child is in the parent's list.
+ * - The child->parent == the parent's tree_file
+ * - There is an entry in the walk cache from {parent,name} -> child_tree_file.
+ * - The backend FS (if there is one) knows about the parent-child link
+ *
+ * To change these, hold the parent's qlock and you must change them all,
+ * with a slight exception: you must *set* child->parent = parent under the
+ * lock.  You may *clear* that reference (and decref the parent) outside the
+ * parent's qlock when freeing the child.  At this point, there are no
+ * references to child, it is off all lists and structures, and RCU readers are
+ * done.
+ *
+ * We'll need to make these changes for create, remove, rename, and lookup (add
+ * entries (positive or negative) that we didn't know about).  Note that even
+ * changing the basename, but not moving, a child during rename requires the
+ * parent's qlock.  (It changes the hashtable linkage).
+ *
+ * Keep in mind that the info in the frontend (tree_files) may be a subset of
+ * the real filesystem, which is the backend (e.g. 9p mount, disk structures,
+ * etc).  The frontend might not have everything from the backend, typically
+ * because of memory reclaim.
+ *
+ * Readers use the walk cache hash table and child->parent) with RCU read
+ * locks.  The linked list of children is only accessed under the parent's
+ * qlock.  If a child needs a ref on its parent, it will need to kref_get during
+ * rcu lock.  Children hold refs on parents, but a concurrent removal/rename
+ * could break that link and decref the parent.
+ *
+ * Synchronization rules
+ * ------------------
+ * Hold the lifetime spin lock when:
+ * - Changing or relying on the value of flags (e.g., during kcref upping)
+ * - Upping a kref from 0 during a lookup
+ * - Changing membership on LRU lists (e.g. during release or kcref upping)
+ *   The lock ordering is entry -> LRU list.  Note the LRU pruner will lock the
+ *   list first, then *trylock* the entry *and* the parent, skipping on failure.
+ *
+ * Refcounting rules: (subject to a device's whims)
+ * - All walked or attached chans (distinct; those that will be closed in the
+ *   device) have a refcounted tree_file.
+ * - The tree_files do not have to be in a lookup structure (parent's list /
+ *   hash table); they could have been unlinked/removed and waiting for the
+ *   final close.
+ * - tree_files can have 0 references.  Typically, files that are unopened
+ *   (technically, unwalked) will have their kref == 0.  On release, they can
+ *   stay in the tree/lookup system, and they are added to an LRU list.
+ * - negative tree_files (i.e. names for files that don't exist) always have a
+ *   refcnt == 0, and are candidates for being pruned at all times.
+ *
+ * Lock ordering:
+ * - Note the tree uses the qlock in the FS file.  In essence, they are the same
+ *   object (a tree_file is an fs_file).  This qlock is for changing the
+ *   contents of the file, whether that's the parent directories links to its
+ *   children, a file's contents (via write), or the metadata (dir) of either.
+ * - Parent qlock -> hash_table bucketlock
+ * - Parent qlock -> child lifetime spinlock -> LRU list spinlock
+ *   Note the LRU pruner inverts this ordering, and uses trylocks
+ * - Parent qlock -> child qlock (unlink and create/rename).
+ * - Qlocking multiple files that aren't parent->child requires the rename_mtx
+ */
+struct tree_file {
+       struct fs_file                          file;
+       spinlock_t                                      lifetime;
+       int                                                     flags;
+       struct kref                                     kref;
+       struct rcu_head                         rcu;
+       struct tree_file                        *parent;                /* rcu protected */
+       struct hlist_node                       hash;                   /* rcu protected */
+       struct list_head                        siblings;
+       struct list_head                        children;
+       struct list_head                        lru;
+       bool                                            can_have_children;
+       struct tree_filesystem          *tfs;
+};
+
+#define TF_F_DISCONNECTED              (1 << 0)
+#define TF_F_NEGATIVE                  (1 << 1)
+#define TF_F_ON_LRU                            (1 << 2)
+#define TF_F_IS_ROOT                   (1 << 3)
+
+/* Devices can put their tree_files / fs_files whereever they want.  For now,
+ * all of them will use aux.  We can make ops for this if we need it. */
+static inline struct tree_file *chan_to_tree_file(struct chan *c)
+{
+       return c->aux;
+}
+
+static inline void chan_set_tree_file(struct chan *c, struct tree_file *tf)
+{
+       c->aux = tf;
+}
+
+static inline struct qid tree_file_to_qid(struct tree_file *tf)
+{
+       return tf->file.dir.qid;
+}
+
+static inline bool tree_file_is_dir(struct tree_file *tf)
+{
+       return tree_file_to_qid(tf).type & QTDIR ? true : false;
+}
+
+static inline bool tree_file_is_file(struct tree_file *tf)
+{
+       return tree_file_to_qid(tf).type & QTFILE ? true : false;
+}
+
+static inline bool tree_file_is_symlink(struct tree_file *tf)
+{
+       return tree_file_to_qid(tf).type & QTSYMLINK ? true : false;
+}
+
+static inline bool tree_file_is_negative(struct tree_file *tf)
+{
+       return tf->flags & TF_F_NEGATIVE ? true : false;
+}
+
+static inline bool tree_file_is_root(struct tree_file *tf)
+{
+       return tf == tf->tfs->root;
+}
+
+static inline char *tree_file_to_name(struct tree_file *tf)
+{
+       return tf->file.dir.name;
+}
+
+static inline bool caller_has_tf_perms(struct tree_file *tf, int omode)
+{
+       return caller_has_file_perms(&tf->file, omode);
+}
+
+static inline void tree_file_perm_check(struct tree_file *tf, int omode)
+{
+       fs_file_perm_check(&tf->file, omode);
+}
+
+/* tree_file helpers */
+bool tf_kref_get(struct tree_file *tf);
+void tf_kref_put(struct tree_file *tf);
+struct tree_file *tree_file_alloc(struct tree_filesystem *tfs,
+                                  struct tree_file *parent, const char *name);
+struct walkqid *tree_file_walk(struct tree_file *from, char **name,
+                               unsigned int nname);
+struct tree_file *tree_file_create(struct tree_file *parent, const char *name,
+                                   uint32_t perm, char *ext);
+void tree_file_remove(struct tree_file *child);
+void tree_file_rename(struct tree_file *tf, struct tree_file *new_parent,
+                      const char *name, int flags);
+ssize_t tree_file_readdir(struct tree_file *parent, void *ubuf, size_t n,
+                          off64_t offset, int *dri);
+
+/* tree_file helpers that operate on chans */
+struct walkqid *tree_chan_walk(struct chan *c, struct chan *nc, char **name,
+                               unsigned int nname);
+void tree_chan_create(struct chan *c, char *name, int omode, uint32_t perm,
+                      char *ext);
+struct chan *tree_chan_open(struct chan *c, int omode);
+void tree_chan_close(struct chan *c);
+void tree_chan_remove(struct chan *c);
+void tree_chan_rename(struct chan *c, struct chan *new_p_c, const char *name,
+                      int flags);
+size_t tree_chan_read(struct chan *c, void *ubuf, size_t n, off64_t offset);
+size_t tree_chan_write(struct chan *c, void *ubuf, size_t n, off64_t offset);
+size_t tree_chan_stat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz);
+size_t tree_chan_wstat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz);
+
+struct chan *tree_file_alloc_chan(struct tree_file *tf, struct dev *dev,
+                                  char *name);
+void tfs_init(struct tree_filesystem *tfs);
+void tfs_destroy(struct tree_filesystem *tfs);
+void tfs_frontend_for_each(struct tree_filesystem *tfs,
+                           void (*cb)(struct tree_file *tf));
+void tfs_frontend_purge(struct tree_filesystem *tfs,
+                        void (*cb)(struct tree_file *tf));
+void __tfs_dump(struct tree_filesystem *tfs);
index 32fef4d..06b0bb7 100644 (file)
@@ -9,10 +9,12 @@ obj-y                                         += convM2S.o
 obj-y                                          += convS2M.o
 obj-y                                          += dev.o
 obj-y                                          += devtab.o
+obj-y                                          += fs_file.o
 obj-y                                          += getfields.o
 obj-y                                          += parse.o
 obj-y                                          += pgrp.o
 obj-y                                          += qio.o
 obj-y                                          += sysfile.o
 obj-y                                          += tokenize.o
+obj-y                                          += tree_file.o
 obj-y                                          += util.o
diff --git a/kern/src/ns/fs_file.c b/kern/src/ns/fs_file.c
new file mode 100644 (file)
index 0000000..680bbf0
--- /dev/null
@@ -0,0 +1,459 @@
+/* Copyright (c) 2018 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * fs_file: structs and helpers for files for 9ns devices
+ */
+
+#include <fs_file.h>
+#include <kmalloc.h>
+#include <string.h>
+#include <stdio.h>
+#include <assert.h>
+#include <error.h>
+#include <umem.h>
+#include <pmap.h>
+
+/* Initializes a zalloced fs_file.  The caller is responsible for filling in
+ * dir, except for name.  Most fields are fine with being zeroed.  Note the kref
+ * == 0 too. */
+void fs_file_init(struct fs_file *f, const char *name, struct fs_file_ops *ops)
+{
+       qlock_init(&f->qlock);
+       fs_file_set_basename(f, name);
+       f->ops = ops;
+       /* TODO: consider holding off on initializing the PM, since only walked and
+        * opened entries could use it.  pm == NULL means no PM yet.  Negative
+        * entries will never be used in this manner.  Doing it now avoids races,
+        * though it's mostly zeroing cache-hot fields. */
+       f->pm = &f->static_pm;
+       pm_init(f->pm, (struct page_map_operations*)ops, f);
+}
+
+void fs_file_set_basename(struct fs_file *f, const char *name)
+{
+       size_t name_len = strlen(name) + 1;
+
+       if (name_len > KNAMELEN)
+               f->dir.name = kzmalloc(name_len, MEM_WAIT);
+       else
+               f->dir.name = f->static_name;
+       memcpy(f->dir.name, name, name_len);
+}
+
+/* Technically, a reader could see the old string pointer and read it.  That
+ * memory could be realloced and used for something else.  But thanks to the
+ * seqctr, the reader will retry.  Otherwise, we might not need the seqctr,
+ * since we never change_basename when a file is in a tree.  So far.
+ *
+ * The only reader that races with setting the name is stat.  Regular lookups
+ * won't see the file, since it was removed from the HT, and readdirs won't see
+ * it due to the parent's qlock. */
+void fs_file_change_basename(struct fs_file *f, const char *name)
+{
+       char *old_name = NULL;
+       char *new_name = NULL;
+       size_t name_len = strlen(name) + 1;
+
+       if (name_len > KNAMELEN)
+               new_name = kzmalloc(name_len, MEM_WAIT);
+       qlock(&f->qlock);
+       if (f->dir.name != f->static_name)
+               old_name = f->dir.name;
+       if (new_name)
+               f->dir.name = new_name;
+       else
+               f->dir.name = f->static_name;
+       memcpy(f->dir.name, name, name_len);
+       /* TODO: if we store the hash of the name in the file, do so here. */
+       qunlock(&f->qlock);
+       kfree(old_name);
+}
+
+/* Helper for building a dir.  Caller sets qid path and vers.  YMMV. */
+void fs_file_init_dir(struct fs_file *f, int dir_type, int dir_dev,
+                      struct username *user, int perm)
+{
+       struct dir *dir = &f->dir;
+
+       if (perm & DMDIR)
+               dir->qid.type |= QTDIR;
+       if (perm & DMAPPEND)
+               dir->qid.type |= QTAPPEND;
+       if (perm & DMEXCL)
+               dir->qid.type |= QTEXCL;
+       if (perm & DMSYMLINK)
+               dir->qid.type |= QTSYMLINK;
+       if (!(dir->qid.type & (QTSYMLINK | QTDIR)))
+               dir->qid.type |= QTFILE;
+       dir->mode = perm;
+       __set_acmtime(f, FSF_ATIME | FSF_BTIME | FSF_MTIME | FSF_CTIME);
+       dir->length = 0;
+       /* TODO: this is a mess if you use anything other than eve.  If you use a
+        * process, that memory is sitting in the proc struct, but we have weak refs
+        * on it.  What happens when that proc exits?  Disaster. */
+       assert(user == &eve);
+       dir->uid = user->name;
+       dir->gid = user->name;
+       dir->muid = user->name;
+}
+
+static char *copy_str(const char *s)
+{
+       char *ret;
+       size_t sz;
+
+       if (!s)
+               return NULL;
+       sz = strlen(s) + 1;
+       ret = kmalloc(sz, MEM_WAIT);
+       memcpy(ret, s, sz);
+       return ret;
+}
+
+/* Deep copies the contents of dir into the fs_file's dir. */
+void fs_file_copy_from_dir(struct fs_file *f, struct dir *dir)
+{
+       memcpy(&f->dir, dir, sizeof(struct dir));
+       fs_file_set_basename(f, dir->name);
+       /* TODO: sort out usernames.  Not only are these just eve, but they are not
+        * struct user or something and they ignore whatever the name was from the
+        * remote end. */
+       f->dir.uid = eve.name;
+       f->dir.gid = eve.name;
+       f->dir.muid = eve.name;
+       f->dir.ext = copy_str(dir->ext);
+}
+
+void cleanup_fs_file(struct fs_file *f)
+{
+       if (f->dir.name != f->static_name)
+               kfree(f->dir.name);
+       /* TODO: Not sure if these will be refcounted objects in the future.  Keep
+        * this in sync with other code that manages/sets uid/gid/muid. */
+       f->dir.uid = NULL;
+       f->dir.gid = NULL;
+       f->dir.muid = NULL;
+       if (f->dir.ext)
+               kfree(f->dir.ext);
+       f->dir.ext = NULL;
+       pm_destroy(f->pm);
+       /* Might share mappings in the future.  Catch it here. */
+       assert(f->pm == &f->static_pm);
+}
+
+void __set_acmtime_to(struct fs_file *f, int which, struct timespec *t)
+{
+       /* WRITE_ONCE, due to lockless peakers */
+       if (which & FSF_ATIME) {
+               WRITE_ONCE(f->dir.atime.tv_sec, t->tv_sec);
+               WRITE_ONCE(f->dir.atime.tv_nsec, t->tv_nsec);
+       }
+       if (which & FSF_BTIME) {
+               WRITE_ONCE(f->dir.btime.tv_sec, t->tv_sec);
+               WRITE_ONCE(f->dir.btime.tv_nsec, t->tv_nsec);
+       }
+       if (which & FSF_CTIME) {
+               WRITE_ONCE(f->dir.ctime.tv_sec, t->tv_sec);
+               WRITE_ONCE(f->dir.ctime.tv_nsec, t->tv_nsec);
+       }
+       if (which & FSF_MTIME) {
+               WRITE_ONCE(f->dir.mtime.tv_sec, t->tv_sec);
+               WRITE_ONCE(f->dir.mtime.tv_nsec, t->tv_nsec);
+       }
+}
+
+/* Caller should hold f's qlock */
+void __set_acmtime(struct fs_file *f, int which)
+{
+       struct timespec now = nsec2timespec(epoch_nsec());
+
+       __set_acmtime_to(f, which, &now);
+}
+
+/* Recall that the frontend always has the most up-to-date info.  This gets
+ * synced to the backend when we flush or fsync. */
+void set_acmtime_to(struct fs_file *f, int which, struct timespec *t)
+{
+       ERRSTACK(1);
+
+       qlock(&f->qlock);
+       if (waserror()) {
+               qunlock(&f->qlock);
+               nexterror();
+       }
+       if ((which & FSF_ATIME) && !caller_has_file_perms(f, O_READ))
+               error(EPERM, "insufficient perms to set atime");
+       if ((which & FSF_BTIME) && !caller_is_username(f->dir.uid))
+               error(EPERM, "insufficient perms to set btime");
+       if ((which & FSF_CTIME) && !caller_has_file_perms(f, O_WRITE))
+               error(EPERM, "insufficient perms to set ctime");
+       if ((which & FSF_MTIME) && !caller_has_file_perms(f, O_WRITE))
+               error(EPERM, "insufficient perms to set mtime");
+       __set_acmtime_to(f, which, t);
+       qunlock(&f->qlock);
+       poperror();
+}
+
+void set_acmtime_noperm(struct fs_file *f, int which)
+{
+       struct timespec now = nsec2timespec(epoch_nsec());
+
+       /* <3 atime.  We'll go with an hour resolution, like NTFS. */
+       if (which == FSF_ATIME) {
+               if (now.tv_sec < ACCESS_ONCE(f->dir.atime.tv_sec) + 3600)
+                       return;
+       }
+       qlock(&f->qlock);
+       __set_acmtime_to(f, which, &now);
+       qunlock(&f->qlock);
+}
+
+size_t fs_file_stat(struct fs_file *f, uint8_t *m_buf, size_t m_buf_sz)
+{
+       size_t ret;
+
+       qlock(&f->qlock);
+       ret = convD2M(&f->dir, m_buf, m_buf_sz);
+       qunlock(&f->qlock);
+       if (ret <= BIT16SZ)
+               error(EINVAL, "buffer too small for stat");
+       return ret;
+}
+
+/* Punches a hole from begin to end.  Pages completely in the hole will be
+ * removed.  Otherwise, the edges will be zeroed.  Caller holds the qlock. */
+static void __fs_file_punch_hole(struct fs_file *f, off64_t begin, off64_t end)
+{
+       size_t first_pg_idx, last_pg_idx, nr_pages, zero_amt;
+       struct page *page;
+       int error;
+
+       /* Caller should check for this */
+       assert((long)begin >= 0);
+       assert((long)end >= 0);
+       end = MIN(end, f->dir.length);
+       if (end <= begin)
+               return;
+       first_pg_idx = LA2PPN(begin);
+       last_pg_idx = LA2PPN(end);
+       nr_pages = last_pg_idx - first_pg_idx + 1;
+       if (PGOFF(begin)) {
+               error = pm_load_page(f->pm, first_pg_idx, &page);
+               if (error)
+                       error(-error, "punch_hole pm_load_page failed");
+               zero_amt = MIN(PGSIZE - PGOFF(begin), end - begin);
+               memset(page2kva(page) + PGOFF(begin), 0, zero_amt);
+               atomic_or(&page->pg_flags, PG_DIRTY);
+               pm_put_page(page);
+               first_pg_idx--;
+               nr_pages--;
+               if (!nr_pages)
+                       return;
+       }
+       if (PGOFF(end) && (end < f->dir.length)) {
+               error = pm_load_page(f->pm, last_pg_idx, &page);
+               if (error)
+                       error(-error, "punch_hole pm_load_page failed");
+               memset(page2kva(page), 0, PGOFF(end));
+               atomic_or(&page->pg_flags, PG_DIRTY);
+               pm_put_page(page);
+               nr_pages--;
+               if (!nr_pages)
+                       return;
+       }
+       /* We hold the qlock, so new pages won't get loaded (load_nowait will fail).
+        * However, this won't remove all pages yet! (see PM comments above) */
+       pm_remove_contig(f->pm, first_pg_idx, nr_pages);
+       /* Need to do an FS op to immediately tell the backing store before we read
+        * a page back in to the PM.  Otherwise, we might see old data.  Consider a
+        * truncate to 0, then back to len. */
+       f->ops->punch_hole(f, begin, end);
+}
+
+void fs_file_truncate(struct fs_file *f, off64_t to)
+{
+       ERRSTACK(1);
+
+       fs_file_perm_check(f, O_WRITE);
+       qlock(&f->qlock);
+       if (waserror()) {
+               qunlock(&f->qlock);
+               nexterror();
+       }
+       if (to < f->dir.length) {
+               __fs_file_punch_hole(f, to, f->dir.length);
+       } else {
+               if (!f->ops->can_grow_to(f, to))
+                       error(EINVAL, "can't grow file to %lu bytes", to);
+       }
+       WRITE_ONCE(f->dir.length, to);
+       __set_acmtime(f, FSF_MTIME | FSF_CTIME);
+       qunlock(&f->qlock);
+       poperror();
+}
+
+/* This attempts to avoid the file qlock when pages are in the page cache.
+ *
+ * If we want to go simpler and use the qlock, always check len, don't use
+ * _nowait, it's not a 'lockless peak', write can set the len at the top, and
+ * all writes to dir.length can be normal. */
+size_t fs_file_read(struct fs_file *f, uint8_t *buf, size_t count,
+                    off64_t offset)
+{
+       ERRSTACK(1);
+       struct page *page;
+       size_t copy_amt, pg_off, pg_idx, total_remaining;
+       volatile size_t so_far = 0;             /* volatile for waserror */
+       const uint8_t *buf_end = buf + count;
+       int error;
+
+       if (waserror()) {
+               if (so_far) {
+                       poperror();
+                       return so_far;
+               }
+               nexterror();
+       }
+       while (buf < buf_end) {
+               pg_off = PGOFF(offset + so_far);
+               pg_idx = LA2PPN(offset + so_far);
+               error = pm_load_page_nowait(f->pm, pg_idx, &page);
+               if (error == -EAGAIN) {
+                       qlock(&f->qlock);
+                       /* Don't attempt to load pages beyond len.  The rest of the read
+                        * code can handle it (it won't copy), but the backend FS might get
+                        * confused. */
+                       if (f->dir.length <= offset + so_far) {
+                               qunlock(&f->qlock);
+                               break;
+                       }
+                       error = pm_load_page(f->pm, pg_idx, &page);
+                       qunlock(&f->qlock);
+               }
+               if (error)
+                       error(-error, "read pm_load_page failed");
+               copy_amt = MIN(PGSIZE - pg_off, buf_end - buf);
+               /* Lockless peak.  Check the len so we don't read beyond EOF.  We have a
+                * page, but we don't necessarily have access to all of it. */
+               total_remaining = ACCESS_ONCE(f->dir.length) - (offset + so_far);
+               if (copy_amt > total_remaining) {
+                       copy_amt = total_remaining;
+                       buf_end = buf + copy_amt;
+               }
+               memcpy_to_safe(buf, page2kva(page) + pg_off, copy_amt);
+               buf += copy_amt;
+               so_far += copy_amt;
+               pm_put_page(page);
+       }
+       if (so_far)
+               set_acmtime_noperm(f, FSF_ATIME);
+       poperror();
+       return so_far;
+}
+
+size_t fs_file_write(struct fs_file *f, const uint8_t *buf, size_t count,
+                     off64_t offset)
+{
+       ERRSTACK(1);
+       struct page *page;
+       size_t copy_amt, pg_off, pg_idx;
+       volatile size_t so_far = 0;             /* volatile for waserror */
+       const uint8_t *buf_end = buf + count;
+       int error;
+
+       qlock(&f->qlock);
+       if (waserror()) {
+               qunlock(&f->qlock);
+               if (so_far) {
+                       poperror();
+                       return so_far;
+               }
+               nexterror();
+       };
+       if (offset + count > f->dir.length) {
+               if (!f->ops->can_grow_to(f, offset + count))
+                       error(EINVAL, "can't write file to %lu bytes", offset + count);
+       }
+       f->flags |= FSF_DIRTY;
+       while (buf < buf_end) {
+               pg_off = PGOFF(offset + so_far);
+               pg_idx = LA2PPN(offset + so_far);
+               error = pm_load_page(f->pm, pg_idx, &page);
+               if (error)
+                       error(-error, "write pm_load_page failed");
+               copy_amt = MIN(PGSIZE - pg_off, buf_end - buf);
+               memcpy_from_safe(page2kva(page) + pg_off, buf, copy_amt);
+               buf += copy_amt;
+               so_far += copy_amt;
+               atomic_or(&page->pg_flags, PG_DIRTY);
+               pm_put_page(page);
+       }
+       assert(buf == buf_end);
+       /* We set the len *after* writing for our lockless reads.  If we set len
+        * before, then read() could start as soon as we loaded the page (all
+        * zeros), but before we wrote the actual data.  They'd get zeros instead of
+        * what we added. */
+       if (offset + count > f->dir.length)
+               WRITE_ONCE(f->dir.length, offset + count);
+       __set_acmtime(f, FSF_MTIME | FSF_CTIME);
+       qunlock(&f->qlock);
+       poperror();
+       return so_far;
+}
+
+static void wstat_mode(struct fs_file *f, int new_mode)
+{
+       ERRSTACK(1);
+       int mode;
+
+       qlock(&f->qlock);
+       if (waserror()) {
+               qunlock(&f->qlock);
+               nexterror();
+       }
+       if (!caller_is_username(f->dir.uid))
+               error(EPERM, "wrong user for wstat, need %s", f->dir.uid);
+       /* Only allowing changes in permissions, not random stuff like whether it is
+        * a directory or symlink. */
+       mode = (f->dir.mode & ~S_PMASK) | (new_mode & S_PMASK);
+       WRITE_ONCE(f->dir.mode, mode);
+       __set_acmtime(f, FSF_CTIME);
+       qunlock(&f->qlock);
+       poperror();
+}
+
+size_t fs_file_wstat(struct fs_file *f, uint8_t *m_buf, size_t m_buf_sz)
+{
+       struct dir *m_dir;
+       size_t m_sz;
+
+       /* common trick in wstats.  we want the dir and any strings in the M.  the
+        * strings are smaller than the entire M (which is strings plus the real dir
+        * M).  the strings will be placed right after the dir (dir[1]) */
+       m_dir = kzmalloc(sizeof(struct dir) + m_buf_sz, MEM_WAIT);
+       m_sz = convM2D(m_buf, m_buf_sz, &m_dir[0], (char*)&m_dir[1]);
+       if (!m_sz) {
+               kfree(m_dir);
+               error(ENODATA, "couldn't convM2D");
+       }
+       /* We'll probably have similar issues for all of the strings.  At that
+        * point, we might not even bother reading the strings in. */
+       if (!emptystr(m_dir->name))
+               error(EINVAL, "do not rename with wstat");
+       if (m_dir->mode != -1)
+               wstat_mode(f, m_dir->mode);
+       if (m_dir->length != -1)
+               fs_file_truncate(f, m_dir->length);
+       if ((int64_t)m_dir->atime.tv_sec != -1)
+               set_acmtime_to(f, FSF_ATIME, &m_dir->atime);
+       if ((int64_t)m_dir->btime.tv_sec != -1)
+               set_acmtime_to(f, FSF_BTIME, &m_dir->btime);
+       if ((int64_t)m_dir->ctime.tv_sec != -1)
+               set_acmtime_to(f, FSF_CTIME, &m_dir->ctime);
+       if ((int64_t)m_dir->mtime.tv_sec != -1)
+               set_acmtime_to(f, FSF_MTIME, &m_dir->mtime);
+       /* TODO: handle uid/gid/muid changes */
+       kfree(m_dir);
+       return m_sz;
+}
diff --git a/kern/src/ns/tree_file.c b/kern/src/ns/tree_file.c
new file mode 100644 (file)
index 0000000..224cec5
--- /dev/null
@@ -0,0 +1,1166 @@
+/* Copyright (c) 2018 Google Inc
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * tree_file: structs and helpers for a tree-based filesystem for 9ns devices.
+ */
+
+#include <tree_file.h>
+#include <kmalloc.h>
+#include <string.h>
+#include <stdio.h>
+#include <assert.h>
+#include <error.h>
+
+/* Adds to the LRU if it was not on it.
+ *
+ * Caller holds the TF lock or o/w knows it has the only ref to tf. */
+static void __add_to_lru(struct tree_file *tf)
+{
+       struct walk_cache *wc = &tf->tfs->wc;
+
+       if (tf->flags & TF_F_ON_LRU)
+               return;
+       tf->flags |= TF_F_ON_LRU;
+       spin_lock(&wc->lru_lock);
+       list_add_tail(&tf->lru, &wc->lru);
+       spin_unlock(&wc->lru_lock);
+}
+
+/* Removes from the LRU if it was on it.
+ *
+ * Caller holds the TF lock or o/w knows it has the only ref to tf. */
+static void __remove_from_lru(struct tree_file *tf)
+{
+       struct walk_cache *wc = &tf->tfs->wc;
+
+       if (!(tf->flags & TF_F_ON_LRU))
+               return;
+       assert(kref_refcnt(&tf->kref) == 0);
+       tf->flags &= ~TF_F_ON_LRU;
+       spin_lock(&wc->lru_lock);
+       list_del(&tf->lru);
+       spin_unlock(&wc->lru_lock);
+}
+
+/* Caller holds the parent's qlock.  Separate helpers here in case we track
+ * nr_children. */
+static void __add_to_parent_list(struct tree_file *parent,
+                                 struct tree_file *child)
+{
+       list_add(&child->siblings, &parent->children);
+}
+
+/* Caller holds the parent's qlock */
+static void __remove_from_parent_list(struct tree_file *parent,
+                                      struct tree_file *child)
+{
+       list_del(&child->siblings);
+}
+
+/* Safely grabs a kref on TF, possibly resurrecting from 0, at which point the
+ * file would be on an LRU list.  This syncs with tree removers, including
+ * unlinking from the tree on remove and LRU cache pruners.  Returns true if we
+ * got the ref, false if we lost and the file was disconnected. */
+bool tf_kref_get(struct tree_file *tf)
+{
+       spin_lock(&tf->lifetime);
+       if (tf->flags & TF_F_DISCONNECTED) {
+               spin_unlock(&tf->lifetime);
+               return false;
+       }
+       __remove_from_lru(tf);
+       __kref_get(&tf->kref, 1);
+       spin_unlock(&tf->lifetime);
+       return true;
+}
+
+void tf_kref_put(struct tree_file *tf)
+{
+       kref_put(&tf->kref);
+}
+
+static void __tf_free(struct tree_file *tf)
+{
+       struct tree_file *parent = tf->parent;
+       struct tree_filesystem *tfs = tf->tfs;
+
+       tf->tfs->tf_ops.free(tf);
+       if (tf->flags & TF_F_IS_ROOT) {
+               assert(tfs->root == tf);
+               assert(!parent);
+       }
+       cleanup_fs_file((struct fs_file*)tf);
+       kfree(tf);
+       /* the reason for decreffing the parent now is for convenience on releasing.
+        * When we unlink the child from the LRU pruner, we don't want to release
+        * the parent immediately while we hold the parent's qlock (and other
+        * locks). */
+       if (parent)
+               tf_kref_put(parent);
+}
+
+static void __tf_free_rcu(struct rcu_head *head)
+{
+       struct tree_file *tf = container_of(head, struct tree_file, rcu);
+
+       __tf_free(tf);
+}
+
+static void tf_release(struct kref *kref)
+{
+       struct tree_file *tf = container_of(kref, struct tree_file, kref);
+
+       assert(!(tf->flags & TF_F_NEGATIVE));
+
+       spin_lock(&tf->lifetime);
+       if (kref_refcnt(&tf->kref) > 0) {
+               /* Someone resurrected after we decreffed to 0. */
+               assert(!(tf->flags & TF_F_ON_LRU));
+               spin_unlock(&tf->lifetime);
+               return;
+       }
+       if (!(tf->flags & (TF_F_DISCONNECTED | TF_F_IS_ROOT))) {
+               /* It's possible that we paused before locking, then another thread
+                * upped, downed, and put it on the LRU list already.  The helper deals
+                * with that. */
+               __add_to_lru(tf);
+               spin_unlock(&tf->lifetime);
+               return;
+       }
+       spin_unlock(&tf->lifetime);
+       /* Need RCU, since we could have had a reader who saw the object and still
+        * needs to try to kref (and fail).  call_rcu, since we can't block. */
+       call_rcu(&tf->rcu, __tf_free_rcu);
+}
+
+static unsigned long hash_string(const char *name)
+{
+       unsigned long hash = 5381;
+
+       for (const char *p = name; *p; p++) {
+               /* hash * 33 + c, djb2's technique */
+               hash = ((hash << 5) + hash) + *p;
+       }
+       return hash;
+}
+
+static void wc_init(struct walk_cache *wc)
+{
+       spinlock_init(&wc->lru_lock);
+       INIT_LIST_HEAD(&wc->lru);
+       spinlock_init(&wc->ht_lock);
+       wc->ht = wc->static_ht;
+       hash_init_hh(&wc->hh);
+       for (int i = 0; i < wc->hh.nr_hash_lists; i++)
+               INIT_HLIST_HEAD(&wc->ht[i]);
+}
+
+static void wc_destroy(struct walk_cache *wc)
+{
+       assert(list_empty(&wc->lru));
+       for (int i = 0; i < wc->hh.nr_hash_lists; i++)
+               assert(hlist_empty(&wc->ht[i]));
+       if (wc->ht != wc->static_ht)
+               kfree(wc->ht);
+}
+
+/* Looks up the child of parent named 'name' in the walk cache hash table.
+ * Caller needs to hold an rcu read lock. */
+static struct tree_file *wc_lookup_child(struct tree_file *parent,
+                                         const char *name)
+{
+       struct walk_cache *wc = &parent->tfs->wc;
+       unsigned long hash_val = hash_string(name);
+       struct hlist_head *bucket;
+       struct tree_file *i;
+
+       bucket = &wc->ht[hash_val % wc->hh.nr_hash_bits];
+       hlist_for_each_entry_rcu(i, bucket, hash) {
+               /* Note 'i' is an rcu protected pointer.  That deref is safe.  i->parent
+                * is also a pointer that in general we want to protect.  In this case,
+                * even though we don't dereference it, we want a pointer that is good
+                * enough to dereference so we can do the comparison. */
+               if (rcu_dereference(i->parent) != parent)
+                       continue;
+               /* The file's name should never change while it is in the table, so no
+                * need for a seq-reader.  Can't assert though, since there are valid
+                * reasons for other seq lockers. */
+               if (!strcmp(tree_file_to_name(i), name))
+                       return i;
+       }
+       return NULL;
+}
+
+/* Caller should hold the parent's qlock */
+static void wc_insert_child(struct tree_file *parent, struct tree_file *child)
+{
+       struct walk_cache *wc = &parent->tfs->wc;
+       unsigned long hash_val = hash_string(tree_file_to_name(child));
+       struct hlist_head *bucket;
+
+       assert(child->parent == parent);        /* catch bugs from our callers */
+       /* TODO: consider bucket locks and/or growing the HT.  Prob need a seq_ctr
+        * in the WC, used on the read side during resizing.  Removal probably would
+        * need something other than the bucket lock too (confusion about which
+        * bucket during the op). */
+       spin_lock(&wc->ht_lock);
+       bucket = &wc->ht[hash_val % wc->hh.nr_hash_bits];
+       hlist_add_head_rcu(&child->hash, bucket);
+       spin_unlock(&wc->ht_lock);
+}
+
+/* Caller should hold the parent's qlock */
+static void wc_remove_child(struct tree_file *parent, struct tree_file *child)
+{
+       struct walk_cache *wc = &parent->tfs->wc;
+
+       assert(child->parent == parent);        /* catch bugs from our callers */
+       spin_lock(&wc->ht_lock);
+       hlist_del_rcu(&child->hash);
+       spin_unlock(&wc->ht_lock);
+}
+
+/* Helper: returns a refcounted pointer to the potential parent.  May return 0.
+ *
+ * Caller needs to qlock the parent and recheck tf->parent.  Callers always need
+ * to get a kref on the parent.  We can rcu-read the parent and *attempt* to
+ * qlock under rcu, but we might block.  Then, say, the TF and the parent got
+ * removed, and *then* we get the qlock.  We're too late. */
+static struct tree_file *__tf_get_potential_parent(struct tree_file *tf)
+{
+       struct tree_file *parent;
+
+       rcu_read_lock();
+       parent = rcu_dereference(tf->parent);
+       if (!parent) {
+               /* the root of the tree has no parent */
+               rcu_read_unlock();
+               return NULL;
+       }
+       if (!tf_kref_get(parent))
+               parent = NULL;
+       rcu_read_unlock();
+       return parent;
+}
+
+/* Returns a refcounted and qlocked parent for child.  NULL on failure. */
+static struct tree_file *get_locked_and_kreffed_parent(struct tree_file *child)
+{
+       struct tree_file *parent;
+
+       parent = __tf_get_potential_parent(child);
+       if (!parent)
+               return NULL;
+       qlock(&parent->file.qlock);
+       if (parent != child->parent) {
+               qunlock(&parent->file.qlock);
+               tf_kref_put(parent);
+               return NULL;
+       }
+       return parent;
+}
+
+static bool __mark_disconnected(struct tree_file *tf)
+{
+       bool need_to_free;
+
+       spin_lock(&tf->lifetime);
+       tf->flags |= TF_F_DISCONNECTED;
+       __remove_from_lru(tf);
+       need_to_free = kref_refcnt(&tf->kref) == 0;
+       spin_unlock(&tf->lifetime);
+       return need_to_free;
+}
+
+/* Disconnects child from the in-memory tree structure (i.e. only the front
+ * end).  Caller holds the parent qlock.  Assumes child is a child of parent.
+ * Once you disconnect, you can't touch the child object.
+ *
+ * Racing with concurrent lookups, who might grab a ref if they get in before
+ * DISCONNECTED, and racing with release (after ref = 0), who might free, if it
+ * was already unlinked. */
+static void __disconnect_child(struct tree_file *parent,
+                               struct tree_file *child)
+{
+       bool need_to_free;
+
+       need_to_free = __mark_disconnected(child);
+       /* Note child->parent is still set.  We clear that in __tf_free. */
+       __remove_from_parent_list(parent, child);
+       wc_remove_child(parent, child);
+       if (need_to_free)
+               call_rcu(&child->rcu, __tf_free_rcu);
+}
+
+/* Backend will need to fill in dir, except for name.  Note this has a kref ==
+ * 0, but is not on the LRU yet. */
+struct tree_file *tree_file_alloc(struct tree_filesystem *tfs,
+                                  struct tree_file *parent, const char *name)
+{
+       struct tree_file *tf;
+
+       tf = kzmalloc(sizeof(struct tree_file), MEM_WAIT);
+       fs_file_init((struct fs_file*)tf, name, &tfs->fs_ops);
+       kref_init(&tf->kref, tf_release, 0);
+       spinlock_init(&tf->lifetime);
+       /* Need to set the parent early on, even if the child isn't linked yet, so
+        * that the TFS ops know who the parent is. */
+       tf->parent = parent;
+       if (parent)
+               kref_get(&parent->kref, 1);
+       INIT_LIST_HEAD(&tf->children);
+       tf->can_have_children = true;
+       tf->tfs = tfs;
+       return tf;
+}
+
+/* Callers must hold the parent's qlock. */
+static void __link_child(struct tree_file *parent, struct tree_file *child)
+{
+       /* Devices may have already increffed ("+1 for existing").  Those that don't
+        * need to be on the LRU.  We haven't linked to the parent yet, so we hold
+        * the only ref.  Once we unlock in __add_to_lru, we're discoverable via
+        * that list, even though we're not linked.  The lru pruner is careful to
+        * not muck with the parent's or wc linkage without qlocking the parent,
+        * which we currently hold. */
+       if (kref_refcnt(&child->kref) == 0)
+               __add_to_lru(child);
+       /* This was set in tree_file_alloc */
+       assert(child->parent == parent);
+       __add_to_parent_list(parent, child);
+       wc_insert_child(parent, child);
+}
+
+static void neuter_directory(struct tree_file *dir)
+{
+       bool throw = false;
+
+       qlock(&dir->file.qlock);
+       if (dir->tfs->tf_ops.has_children(dir))
+               throw = true;
+       dir->can_have_children = false;
+       qunlock(&dir->file.qlock);
+       if (throw)
+               error(ENOTEMPTY, "can't remove dir with children");
+}
+
+/* Unlink a child from the tree.  Last ref will clean it up, which will not be
+ * us.  Caller should hold krefs on the child and parent.  The child's kref will
+ * actually keep the parent's alive, but all practical callers will have the
+ * parent kreff'ed and qlocked - which is required to ensure the child is still
+ * a child of parent. */
+static void __unlink_child(struct tree_file *parent, struct tree_file *child)
+{
+       /* Need to make sure concurrent creates/renames do not add children to
+        * directories that are unlinked.  Note we don't undo the neutering if the
+        * backend fails. */
+       if (tree_file_is_dir(child))
+               neuter_directory(child);
+       /* The ramfs backend will probably decref the "+1 for existing" ref.
+        * This is OK.  If that was the last ref, the child will briefly be on
+        * the LRU list (which ramfs ignores).  When we disconnect, we'll yank
+        * the child back off the list and then free it (after rcu). */
+       parent->tfs->tf_ops.unlink(parent, child);
+       __disconnect_child(parent, child);
+}
+
+/* Talks to the backend and ensures a tree_file for the child exists, either
+ * positive or negative.  Throws an error; doesn't return NULL.
+ *
+ * This returns with an rcu read lock sufficient to protect the returned TF, but
+ * it is *not* kreffed.  It could be a negative entry, which is not kreffed.
+ *
+ * It is possible that at the moment we qunlock, someone comes along and removes
+ * the entry (LRU prune or file removal (for positive entries)).  That's fine -
+ * we have an rcu read lock, just like during a regular walk, when the removal
+ * could happen anyways. */
+static struct tree_file *lookup_child_entry(struct tree_file *parent,
+                                            const char *name)
+{
+       ERRSTACK(1);
+       struct tree_file *child;
+
+       qlock(&parent->file.qlock);
+       child = wc_lookup_child(parent, name);
+       if (child) {
+               /* Since we last looked, but before we qlocked, someone else added our
+                * entry. */
+               rcu_read_lock();
+               qunlock(&parent->file.qlock);
+               return child;
+       }
+       child = tree_file_alloc(parent->tfs, parent, name);
+       if (waserror()) {
+               /* child wasn't fully created, so freeing it may be tricky, esp on the
+                * device ops side (might see something they never created). */
+               __tf_free(child);
+               qunlock(&parent->file.qlock);
+               nexterror();
+       }
+       parent->tfs->tf_ops.lookup(parent, child);
+       poperror();
+       __link_child(parent, child);
+       rcu_read_lock();
+       qunlock(&parent->file.qlock);
+       return child;
+}
+
+/* Walks a tree filesystem from 'from' for array of null-terminated names.
+ * Devices will often use tree_chan_walk(), but can use this directly if they
+ * want more control.
+ *
+ * Returns the WQ of qids.  On complete/successful walks, we hang a refcnted TF
+ * on wq->clone.
+ *
+ * Walks can return intermediate results, which is when there is an error but we
+ * have walked at least once.  The partial return is useful for namec(), which
+ * can succeed if something was mounted on an intermediate QID.  Walks that have
+ * no results set error and return NULL, which is what namec() expects. */
+struct walkqid *tree_file_walk(struct tree_file *from, char **name,
+                               unsigned int nname)
+{
+       ERRSTACK(2);
+       struct tree_file *at, *next;
+       struct tree_filesystem *tfs = from->tfs;
+       struct walkqid *wq;
+
+       wq = kzmalloc(sizeof(struct walkqid) + nname * sizeof(struct qid),
+                                 MEM_WAIT);
+       /* A walk with zero names means "make me a copy."  If we go through the
+        * regular walker, our usual tf_kref_get will fail - similar to failing if
+        * we got a walk for "foo/../" during a concurrent removal of ourselves.
+        * We'll let a walk of zero names work, but if you provide any names, the
+        * actual walk must happen.
+        *
+        * This is tricky, and confused me a little.  We're returning a *TF* through
+        * wq->clone, not a chan, and that is refcounted.  Normally for chans that
+        * end up with wq->clone == c, we do not incref the object hanging off the
+        * chan (see k/d/d/eventfd.c), since there is just one chan with a kreffed
+        * object hanging off e.g. c->aux.  But here, wq->clone is considered a
+        * distinct refcnt to some TF, and it might be 'from.'  Our *caller* needs
+        * to deal with the "wq->clone == from_chan", since they deal with chans.
+        * We deal with tree files. */
+       if (!nname) {
+               kref_get(&from->kref, 1);
+               wq->clone = (struct chan*)from;
+               return wq;
+       }
+       if (waserror()) {
+               kfree(wq);
+               poperror();
+               return NULL;
+       }
+       rcu_read_lock();
+       at = from;
+       for (int i = 0; i < nname; i++) {
+               /* Walks end if we reach a regular file, i.e. you can't walk through a
+                * file, only a dir.  But even if there are more names, the overall walk
+                * might succeed.  E.g. a directory could be mounted on top of the
+                * current file we're at.  That's just not our job. */
+               if (tree_file_is_file(at)) {
+                       if (i == 0)
+                               error(ENOTDIR, "initial walk from a file");
+                       break;
+               }
+               /* Normally, symlinks stop walks, and namec's walk() will deal with it.
+                * We allow walks 'through' symlinks, but only for .. and only for the
+                * first name.  This is for relative lookups so we can find the parent
+                * of a symlink. */
+               if (tree_file_is_symlink(at)) {
+                       if (i != 0)
+                               break;
+                       if (strcmp(name[i], ".."))
+                               error(ELOOP, "walk from a symlink that wasn't ..");
+               }
+               if (!caller_has_tf_perms(at, O_READ)) {
+                       if (i == 0)
+                               error(EACCES, "missing perm for lookup");
+                       break;
+               }
+               if (!strcmp(name[i], ".")) {
+                       wq->qid[wq->nqid++] = tree_file_to_qid(at);
+                       continue;
+               }
+               if (!strcmp(name[i], "..")) {
+                       next = rcu_dereference(at->parent);
+                       if (!next) {
+                               if (tree_file_is_root(at)) {
+                                       wq->qid[wq->nqid++] = tree_file_to_qid(at);
+                                       /* I think namec should never give us DOTDOT that isn't at
+                                        * the end of the names array.  Though devwalk() seems to
+                                        * expect it. */
+                                       if (i != nname - 1)
+                                               warn("Possible namec DOTDOT bug, call for help!");
+                                       continue;
+                               }
+                               /* We lost our parent due to a removal/rename.  We might have
+                                * walked enough for our walk to succeed (e.g.  there's a mount
+                                * point in the WQ), so we can return what we have.  Though if
+                                * we've done nothing, it's a failure.
+                                *
+                                * Note the removal could have happened a long time ago:
+                                * consider an O_PATH open, then namec_from().
+                                *
+                                * We also could walk up and see the *new* parent during
+                                * rename().  For instance, /src/x/../y could get the old /src/y
+                                * or the new /dst/y.  If we want to avoid that, then we'll need
+                                * some sort of sync with rename to make sure we don't get the
+                                * new one.  Though this can happen with namec_from(), so I'm
+                                * not sure I care. */
+                               if (i == 0)
+                                       error(ENOENT, "file lost its parent during lookup");
+                               break;
+                       }
+                       at = next;
+                       wq->qid[wq->nqid++] = tree_file_to_qid(at);
+                       continue;
+               }
+               next = wc_lookup_child(at, name[i]);
+               if (!next) {
+                       /* TFSs with no backend have the entire tree in the WC HT. */
+                       if (!tfs->tf_ops.lookup) {
+                               if (i == 0)
+                                       error(ENOENT, "file does not exist");
+                               break;
+                       }
+                       /* Need to hold a kref on 'at' before we rcu_read_unlock().  Our
+                        * TFS op might block. */
+                       if (!tf_kref_get(at)) {
+                               if (i == 0)
+                                       error(ENOENT, "file was removed during lookup");
+                               /* WQ has a qid for 'at' from a previous loop, but since we
+                                * can't walk to it, we should unwind it. */
+                               wq->nqid--;
+                               break;
+                       }
+                       rcu_read_unlock();
+                       /* propagate the error only on the first name.  Note we run the
+                        * 'else' case, and run the poperror case for non-errors and
+                        * non-name=0-errors. */
+                       if (waserror()) {
+                               if (i == 0) {
+                                       tf_kref_put(at);
+                                       nexterror();
+                               }
+                       } else {
+                               /* This returns with an rcu_read_lock protecting 'next' */
+                               next = lookup_child_entry(at, name[i]);
+                       }
+                       tf_kref_put(at);
+                       poperror();
+                       assert(next);
+               }
+               if (tree_file_is_negative(next)) {
+                       if (i == 0)
+                               error(ENOENT, "file does not exist");
+                       break;
+               }
+               at = next;
+               wq->qid[wq->nqid++] = tree_file_to_qid(at);
+       }
+       if (wq->nqid == nname || tree_file_is_symlink(at)) {
+               if (!tf_kref_get(at)) {
+                       /* We need to undo our last result as if we never saw it. */
+                       wq->nqid--;
+                       if (wq->nqid == 0)
+                               error(ENOENT, "file was removed during lookup");
+               } else {
+                       /* Hanging the refcounted TF off the wq->clone, which is cheating.
+                        * Our walker shim knows to expect this. */
+                       wq->clone = (struct chan*)at;
+               }
+       }
+       rcu_read_unlock();
+       poperror();
+       return wq;
+}
+
+/* Most tree devices will use this for their walk op, similar to devwalk. */
+struct walkqid *tree_chan_walk(struct chan *c, struct chan *nc, char **name,
+                               unsigned int nname)
+{
+       struct tree_file *from, *to;
+       struct walkqid *wq;
+
+       from = chan_to_tree_file(c);
+       wq = tree_file_walk(from, name, nname);
+       if (!wq)
+               return NULL;
+       if (!wq->clone)
+               return wq;
+       if (!nc)
+               nc = devclone(c);
+       /* Not sure if callers that specify nc must have a chan from our device */
+       assert(nc->type == c->type);
+       to = (struct tree_file*)wq->clone;
+       nc->qid = tree_file_to_qid(to);
+       chan_set_tree_file(nc, to);
+       wq->clone = nc;
+       /* We might be returning the same chan, so there's actually just one ref */
+       if (wq->clone == c)
+               tf_kref_put(chan_to_tree_file(c));
+       return wq;
+}
+
+/* Creates a tree file under parent with name, omode, and perm.  Returns a
+ * kreffed tree_file for the new child.  Throws on error. */
+struct tree_file *tree_file_create(struct tree_file *parent, const char *name,
+                                   uint32_t perm, char *ext)
+{
+       ERRSTACK(2);
+       struct tree_file *child;
+       bool got_ref;
+       struct timespec now;
+
+       qlock(&parent->file.qlock);
+       if (waserror()) {
+               qunlock(&parent->file.qlock);
+               nexterror();
+       }
+       if (!caller_has_tf_perms(parent, O_WRITE))
+               error(EACCES, "missing create permission on dir");
+       child = wc_lookup_child(parent, name);
+       if (child) {
+               /* The create(5) message fails if the file exists, which differs from
+                * the syscall.  namec() handles this. */
+               if (!tree_file_is_negative(child))
+                       error(EEXIST, "file exists");
+               /* future lookups that find no entry will qlock.  concurrent ones that
+                * see the child, even if disconnected, will see it was negative and
+                * fail. */
+               __disconnect_child(parent, child);
+       }
+       child = tree_file_alloc(parent->tfs, parent, name);
+       if (waserror()) {
+               __tf_free(child);
+               nexterror();
+       }
+       /* Backend will need to know the ext for its create.  This gets cleaned up
+        * on error. */
+       if (perm & DMSYMLINK)
+               kstrdup(&child->file.dir.ext, ext);
+       /* Backend will need to fill in dir, except for name. */
+       parent->tfs->tf_ops.create(parent, child, perm);
+       now = nsec2timespec(epoch_nsec());
+       __set_acmtime_to(&child->file,
+                        FSF_ATIME | FSF_BTIME | FSF_CTIME | FSF_MTIME, &now);
+       poperror();
+       /* At this point, the child is visible, so it must be ready to go */
+       __link_child(parent, child);
+       got_ref = tf_kref_get(child);
+       assert(got_ref);        /* we hold the qlock, no one should have removed */
+       __set_acmtime_to(&parent->file, FSF_CTIME | FSF_MTIME, &now);
+       qunlock(&parent->file.qlock);
+       poperror();
+       return child;
+}
+
+/* Most tree devices will use this for their create op. */
+void tree_chan_create(struct chan *c, char *name, int omode, uint32_t perm,
+                      char *ext)
+{
+       struct tree_file *parent, *child;
+
+       parent = chan_to_tree_file(c);
+       child = tree_file_create(parent, name, perm, ext);
+       c->qid = tree_file_to_qid(child);
+       c->mode = openmode(omode);
+       chan_set_tree_file(c, child);
+       tf_kref_put(parent);
+}
+
+struct chan *tree_chan_open(struct chan *c, int omode)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       if ((c->qid.type & QTDIR) && (omode & O_WRITE))
+               error(EISDIR, "can't open a dir for writing");
+       if (c->qid.type & QTSYMLINK)
+               error(ELOOP, "can't open a symlink");
+       tree_file_perm_check(tf, omode);
+       /* TODO: if we want to support DMEXCL on dir.mode, we'll need to lock/sync
+        * on the fs_file (have a flag for FSF_IS_OPEN, handle in close).  We'll
+        * also need a way to pass it in to the dir.mode during create/wstat/etc. */
+       if (omode & O_TRUNC)
+               fs_file_truncate(&tf->file, 0);
+       c->mode = openmode(omode);
+       c->flag |= COPEN;
+       c->offset = 0;
+       return c;
+}
+
+void tree_chan_close(struct chan *c)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       tf_kref_put(tf);
+}
+
+void tree_file_remove(struct tree_file *child)
+{
+       ERRSTACK(1);
+       struct tree_file *parent;
+
+       parent = get_locked_and_kreffed_parent(child);
+       if (!parent)
+               error(ENOENT, "%s had no parent", tree_file_to_name(child));
+       if (waserror()) {
+               qunlock(&parent->file.qlock);
+               tf_kref_put(parent);
+               nexterror();
+       }
+       if (!caller_has_tf_perms(parent, O_WRITE))
+               error(EACCES, "missing remove perm for dir");
+       __unlink_child(parent, child);
+       __set_acmtime(&parent->file, FSF_CTIME | FSF_MTIME);
+       poperror();
+       qunlock(&parent->file.qlock);
+       tf_kref_put(parent);
+}
+
+void tree_chan_remove(struct chan *c)
+{
+       ERRSTACK(1);
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       /* sysremove expects a chan that is disconnected from the device, regardless
+        * of whether or not we fail.  See sysremove(); it will clear type, ensuring
+        * our close is never called. */
+       if (waserror()) {
+               chan_set_tree_file(c, NULL);
+               tf_kref_put(tf);        /* The ref from the original walk */
+               nexterror();
+       }
+       tree_file_remove(tf);
+       chan_set_tree_file(c, NULL);
+       tf_kref_put(tf);        /* The ref from the original walk */
+       poperror();
+}
+
+static bool is_descendant_of(struct tree_file *descendant,
+                             struct tree_file *ancestor)
+{
+       if (!tree_file_is_dir(ancestor))
+               return false;
+       rcu_read_lock();
+       for (struct tree_file *i = rcu_dereference(descendant->parent);
+            i;
+            i = rcu_dereference(i->parent)) {
+               if (i == ancestor) {
+                       rcu_read_unlock();
+                       return true;
+               }
+       }
+       rcu_read_unlock();
+       return false;
+}
+
+/* Caller should hold the rename mutex.  This qlocks a and b, which can be the
+ * same file, and this handles lock ordering.  Recall the rule: parents before
+ * children, and otherwise only the renamer can lock. */
+static void qlock_tree_files(struct tree_file *a, struct tree_file *b)
+{
+       if (a == b) {
+               qlock(&a->file.qlock);
+               return;
+       }
+       if (is_descendant_of(a, b)) {
+               qlock(&b->file.qlock);
+               qlock(&a->file.qlock);
+       } else {
+               qlock(&a->file.qlock);
+               qlock(&b->file.qlock);
+       }
+}
+
+static void qunlock_tree_files(struct tree_file *a, struct tree_file *b)
+{
+       if (a != b)
+               qunlock(&a->file.qlock);
+       qunlock(&b->file.qlock);
+}
+
+/* Higher layers (namec) ensure that tf and new_parent are in the same device.
+ * The device (e.g. #mnt) ensures that they are in the same instance.
+ * new_parent could be the parent of tf; everything should still work if the
+ * move is within the same directory. */
+void tree_file_rename(struct tree_file *tf, struct tree_file *new_parent,
+                      const char *name, int flags)
+{
+       ERRSTACK(1);
+       struct tree_file *old_parent;
+       struct tree_file *prev_dst;
+       struct timespec now;
+
+       old_parent = __tf_get_potential_parent(tf);
+       if (!old_parent)
+               error(ENOENT, "renamed file had no parent");
+       /* global mtx helps with a variety of weird races, including the "can't move
+        * to a subdirectory of yourself" case and the lock ordering of parents
+        * (locks flow from parent->child). */
+       qlock(&tf->tfs->rename_mtx);
+       qlock_tree_files(old_parent, new_parent);
+       if (waserror()) {
+               qunlock_tree_files(old_parent, new_parent);
+               qunlock(&tf->tfs->rename_mtx);
+               tf_kref_put(old_parent);
+               nexterror();
+       };
+       if (old_parent != tf->parent)
+               error(ENOENT, "renamed file lost its parent");
+       /* Probably a namec bug (that code isn't written yet). */
+       assert(tree_file_is_dir(new_parent));
+       if (!new_parent->can_have_children)
+               error(ENOENT, "target dir being removed");
+       if (!caller_has_tf_perms(old_parent, O_WRITE))
+               error(EACCES, "missing remove perm for src dir");
+       if (!caller_has_tf_perms(new_parent, O_WRITE))
+               error(EACCES, "missing create perm for dst dir");
+       /* can't move tf to one of its subdirs */
+       if (is_descendant_of(new_parent, tf))
+               error(EINVAL, "can't rename to a child directory");
+       /* We hold new_parent's qlock, so there's no worry about prev_dst
+        * disappearing, so no need for an rcu read lock. */
+       prev_dst = wc_lookup_child(new_parent, name);
+       if (prev_dst) {
+               if (tree_file_is_dir(prev_dst)) {
+                       if (!tree_file_is_dir(tf))
+                               error(EISDIR, "can't rename a file onto a dir");
+                       /* We need to ensure prev_dst is childless and remains so.  That
+                        * requires grabbing its qlock, but there's a potential lock
+                        * ordering issue with old_parent.  We could have this:
+                        * new_parent/dst/x/y/z/old_parent/src.  That will fail, but we need
+                        * to check for that case instead of grabbing prev_dst's qlock. */
+                       if (is_descendant_of(prev_dst, old_parent))
+                               error(ENOTEMPTY, "old_parent descends from dst");
+                       neuter_directory(prev_dst);
+               } else {
+                       if (tree_file_is_dir(tf))
+                               error(ENOTDIR, "can't rename a dir onto a file");
+               }
+       }
+       /* We check with the backend first, so that it has a chance to fail early.
+        * Once we make the changes to the front end, lookups can see the effects of
+        * the change, which we can't roll back.  Since we hold the parents' qlocks,
+        * no one should be able to get the info from the backend either (lookups
+        * that require the backend, readdir, etc). */
+       tf->tfs->tf_ops.rename(tf, old_parent, new_parent, name, flags);
+       /* Similar to __disconnect_child, we don't clear tf->parent.  rcu readers at
+        * TF will be able to walk up (with ..).  Same with namec_from an FD.  If we
+        * atomically replace tf->parent, we should be good.  See tree_file_walk().
+        *
+        * Further, we don't mark the tf disconnected.  Someone might lookup from
+        * the old location, and that's fine.  We just don't want issues with
+        * decrefs. */
+       __remove_from_parent_list(old_parent, tf);
+       wc_remove_child(old_parent, tf);
+       synchronize_rcu();
+       /* Now, no new lookups will find it at the old location.  That change is not
+        * atomic wrt src, but it will be wrt dst.  Importantly, no one will see
+        * /path/to/old_parent/new_basename */
+       fs_file_change_basename((struct fs_file*)tf, name);
+       /* We're clobbering the old_parent ref, which we'll drop later */
+       rcu_assign_pointer(tf->parent, new_parent);
+       kref_get(&new_parent->kref, 1);
+       __add_to_parent_list(new_parent, tf);
+       wc_insert_child(new_parent, tf);
+       /* Now both the prev_dst (if it existed) or the tf file are in the walk
+        * cache / HT and either could have been looked up by a concurrent reader.
+        * Readers will always get one or the other, but never see nothing.  This is
+        * the atomic guarantee of rename. */
+       if (prev_dst) {
+               __remove_from_parent_list(new_parent, prev_dst);
+               wc_remove_child(new_parent, prev_dst);
+               synchronize_rcu();
+               /* Now no one can find prev_dst.  Someone might still have a ref, or it
+                * might be on the LRU list (if kref == 0).  Now we can mark
+                * disconnected.  Had we disconnected earlier, then lookup code would
+                * see that and treat it as a failure.  Using rcu and putting the
+                * complexity in rename was easier and simpler than changing lookup.
+                *
+                * We still need RCU here for freeing the prev_dst.  We could have had
+                * an LRU pruner, etc, looking.  The synchronize_rcu above only dealt
+                * with lookups via parent in this function. */
+               if (__mark_disconnected(prev_dst))
+                       call_rcu(&prev_dst->rcu, __tf_free_rcu);
+       }
+       now = nsec2timespec(epoch_nsec());
+       __set_acmtime_to(&old_parent->file, FSF_CTIME | FSF_MTIME, &now);
+       __set_acmtime_to(&new_parent->file, FSF_CTIME | FSF_MTIME, &now);
+       /* Can we unlock earlier?  No.  We need to at least hold new_parent's qlock,
+        * which was the parent of old_dst, until old_dst is marked disconnected.
+        * Even though old_dst is removed from new_parent's HT, it is still in the
+        * LRU list. */
+       qunlock_tree_files(old_parent, new_parent);
+       qunlock(&tf->tfs->rename_mtx);
+       poperror();
+       tf_kref_put(old_parent);        /* the original tf->parent ref we clobbered */
+       tf_kref_put(old_parent);        /* the one we grabbed when we started */
+}
+
+void tree_chan_rename(struct chan *c, struct chan *new_p_c, const char *name,
+                      int flags)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+       struct tree_file *new_parent = chan_to_tree_file(new_p_c);
+
+       tree_file_rename(tf, new_parent, name, flags);
+}
+
+/* dri is a pointer to the chan->dri, which is a count of how many directory
+ * entries that have been read from this chan so far.  9ns handles it; we just
+ * need to increment it for every successful entry.  Note we ignore offset. */
+ssize_t tree_file_readdir(struct tree_file *parent, void *ubuf, size_t n,
+                          off64_t offset, int *dri)
+{
+       ERRSTACK(1);
+       struct tree_file *i;
+       size_t dir_amt, so_far = 0;
+       uint8_t *write_pos = ubuf;
+       int child_nr = 0;
+
+       qlock(&parent->file.qlock);
+       if (waserror()) {
+               qunlock(&parent->file.qlock);
+               nexterror();
+       }
+       list_for_each_entry(i, &parent->children, siblings) {
+               if (child_nr++ < *dri)
+                       continue;
+               qlock(&i->file.qlock);
+               dir_amt = convD2M(&i->file.dir, write_pos, n - so_far);
+               qunlock(&i->file.qlock);
+               if (dir_amt <= BIT16SZ) {
+                       if (!so_far)
+                               error(EINVAL, "buffer to small for readdir");
+                       break;
+               }
+               write_pos += dir_amt;
+               so_far += dir_amt;
+               assert(n - so_far >= 0);
+               (*dri)++;
+       }
+       /* If we care about directory atime, we can do that here. (if so_far) */
+       qunlock(&parent->file.qlock);
+       poperror();
+       return so_far;
+}
+
+/* Note this only works for backend-less TFSs.  It calls tree_file_readdir,
+ * which only looks at the frontend's tree. */
+size_t tree_chan_read(struct chan *c, void *ubuf, size_t n, off64_t offset)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       if (tree_file_is_dir(tf))
+               return tree_file_readdir(tf, ubuf, n, offset, &c->dri);
+       return fs_file_read(&tf->file, ubuf, n, offset);
+}
+
+size_t tree_chan_write(struct chan *c, void *ubuf, size_t n, off64_t offset)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       /* sysfile.c:rwrite checked the chan's type. */
+       assert(!tree_file_is_dir(tf));
+       return fs_file_write(&tf->file, ubuf, n, offset);
+}
+
+size_t tree_chan_stat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       return fs_file_stat(&tf->file, m_buf, m_buf_sz);
+}
+
+size_t tree_chan_wstat(struct chan *c, uint8_t *m_buf, size_t m_buf_sz)
+{
+       struct tree_file *tf = chan_to_tree_file(c);
+
+       return fs_file_wstat(&tf->file, m_buf, m_buf_sz);
+}
+
+/* Given a tree file, construct a chan that points to the TF for the given
+ * device.  Careful with this - it's for bootstrapping. */
+struct chan *tree_file_alloc_chan(struct tree_file *tf, struct dev *dev,
+                                  char *name)
+{
+       struct chan *c;
+
+       c = newchan();
+       c->type = dev - devtab;
+       c->name = newcname(name);
+       kref_get(&tf->kref, 1);
+       chan_set_tree_file(c, tf);
+       c->qid = tree_file_to_qid(tf);
+       return c;
+}
+
+/* Caller needs to set its customizable fields: tf_ops, pm_ops, etc.  root is
+ * created with a ref of 1, but needs filled in by the particular TFS. */
+void tfs_init(struct tree_filesystem *tfs)
+{
+       wc_init(&tfs->wc);
+       qlock_init(&tfs->rename_mtx);
+       tfs->root = tree_file_alloc(tfs, NULL, ".");
+       tfs->root->flags |= TF_F_IS_ROOT;
+       assert(!(tfs->root->flags & TF_F_ON_LRU));
+       __kref_get(&tfs->root->kref, 1);
+}
+
+void tfs_destroy(struct tree_filesystem *tfs)
+{
+       tfs->root = NULL;       /* was just freed in __tf_free() */
+       wc_destroy(&tfs->wc);
+}
+
+/* For every file except root, we hold our parent's qlock (root has no parent).
+ * This prevents TF's removal/rename and any changes to tf->parent. */
+static void tf_dfs_cb(struct tree_file *tf, void (*cb)(struct tree_file *tf))
+{
+       struct tree_file *child;
+
+       if (tree_file_is_dir(tf)) {
+               qlock(&tf->file.qlock);
+               /* Note we don't have a kref on our child's TF - we have a weak
+                * reference (the list membership).  We hold the parent's qlock, which
+                * prevents removal/unlinking/disconnecting/etc.  The child's membership
+                * on the LRU list can change repeatedly.
+                *
+                * If we want to avoid holding the parent's qlock, we could grab a kref
+                * on the child.  However, our list walk would be in jeopardy - both
+                * child and temp could be removed from the list.  So we'd need to qlock
+                * the parent, grab krefs on all children, and put them on a local list.
+                * Also, grabbing krefs on our children will muck with the LRU list;
+                * when we're done, it would be like we sorted the LRU list in the DFS
+                * order. */
+               list_for_each_entry(child, &tf->children, siblings)
+                       tf_dfs_cb(child, cb);
+               qunlock(&tf->file.qlock);
+       }
+       if (!tree_file_is_negative(tf))
+               cb(tf);
+}
+
+/* Runs CB on all in-memory, non-negative TFs from the TFS in a depth-first
+ * search.  Compared to the other CB walkers (purge, LRU, etc), this never
+ * removes/prunes/disconnects a TF from the tree.  You can use it for syncing FS
+ * trees or pruning page maps (i.e. discarding non-dirty pages).
+ *
+ * One thing to note is that it qlocks the tree as part of its DFS.  We can
+ * change that, but at a slight cost in complexity and tampering with the LRU
+ * list.  Translation: we can do it if there's a performance problem.
+ *
+ * The tfs->root reference is also weak.  It's up to the user to make sure
+ * there is no concurrent tfs_destroy.  Typically, if we're called on any
+ * mounted device, we're fine (e.g. #tmpfs) or a device that is never destroyed
+ * (e.g. #kfs). */
+void tfs_frontend_for_each(struct tree_filesystem *tfs,
+                           void (*cb)(struct tree_file *tf))
+{
+       tf_dfs_cb(tfs->root, cb);
+}
+
+/* We should be single-user, so no need for concurrency protections.  I keep
+ * them around for paranoia/future use/documentation. */
+static void tf_dfs_purge(struct tree_file *tf, void (*cb)(struct tree_file *tf))
+{
+       struct tree_file *child, *temp;
+
+       if (tree_file_is_dir(tf)) {
+               qlock(&tf->file.qlock);
+               /* Note we don't have a kref on TF, and one of our children should
+                * decref *us* to 0.  We aren't disconnected yet, and we can't be
+                * removed (parent's qlock is held), so we'll just end up on the LRU
+                * list, which is OK.
+                *
+                * Our child should remove itself from our list, so we need the _safe.
+                *
+                * Also note that the child decrefs us in a call_rcu.  CB can block, and
+                * technically so can qlock, so we might run RCU callbacks while
+                * qlocked.  We'll need to rcu_barrier so that our children's decrefs
+                * occur before we remove ourselves from our parent. */
+               list_for_each_entry_safe(child, temp, &tf->children, siblings)
+                       tf_dfs_purge(child, cb);
+               qunlock(&tf->file.qlock);
+       }
+       rcu_barrier();
+       /* ramfs will drop the "+1 for existing" ref here */
+       if (!tree_file_is_negative(tf))
+               cb(tf);
+       spin_lock(&tf->lifetime);
+       /* should be unused, with no children.  we have a ref on root, to keep the
+        * TFS around while we destroy the tree. */
+       assert(kref_refcnt(&tf->kref) == 0 || tree_file_is_root(tf));
+       /* This mark prevents new lookups.  We'll disconnect it shortly. */
+       tf->flags |= TF_F_DISCONNECTED;
+       spin_unlock(&tf->lifetime);
+       if (tf->parent)
+               __disconnect_child(tf->parent, tf);
+}
+
+/* Purges all in-memory TFs from the TFS in a depth-first search, both positive
+ * and negative.  We run CB on all non-negative TFs.  It's up to the caller to
+ * ensure there is no concurrency.
+ *
+ * The caller must make sure they have an extra ref on tfs->root to keep the
+ * TFS around while it gets destroyed.  The root TF will get freed when it is
+ * released, unlike other TFs that are still connected.
+ *
+ * This is for devices that want to destroy themselves, such as an unmounted
+ * #tmpfs or #gtfs/#mnt, that want to do some extra work (e.g. sync).
+ * Typically, those devices will call this after they have no users (e.g. mounts
+ * or open chans). */
+void tfs_frontend_purge(struct tree_filesystem *tfs,
+                        void (*cb)(struct tree_file *tf))
+{
+       assert(kref_refcnt(&tfs->root->kref) > 0);
+       tf_dfs_purge(tfs->root, cb);
+}
+
+static void print_tf(struct tree_file *tf)
+{
+       if (tree_file_is_negative(tf)) {
+               printk("%-10s: Negative\n", tree_file_to_name(tf));
+               return;
+       }
+       printk("%-10s: Q: %5d, R: %2d, U %s, %c%o %s\n",
+                  tree_file_to_name(tf),
+                  tf->file.dir.qid.path,
+                  kref_refcnt(&tf->kref),
+                  tf->file.dir.uid,
+                  tree_file_is_dir(tf) ? 'd' :
+                                                               tf->file.dir.mode & DMSYMLINK ? 'l' : '-',
+                  tf->file.dir.mode & S_PMASK,
+                  tf->file.dir.mode & DMSYMLINK ? tf->file.dir.ext : ""
+                  );
+}
+
+static void dump_tf(struct tree_file *tf, int tabs)
+{
+       struct tree_file *child;
+
+       if (!!(tf->file.dir.mode & DMSYMLINK) !=
+           !!(tf->file.dir.qid.type & QTSYMLINK))
+               warn("%s has differing symlink bits", tree_file_to_name(tf));
+
+       if ((tf->file.dir.qid.type & (QTFILE | QTDIR | QTSYMLINK)) == 0)
+               warn("%s has no type!  (prob QTFILE)", tree_file_to_name(tf));
+
+       for (int i = 0; i < tabs; i++)
+               printk("    ");
+       print_tf(tf);
+       if (tree_file_is_dir(tf)) {
+               for (int i = 0; i < tabs; i++)
+                       printk("    ");
+               printk("---------------------\n");
+               list_for_each_entry(child, &tf->children, siblings)
+                       dump_tf(child, tabs + 1);
+       }
+}
+
+void __tfs_dump(struct tree_filesystem *tfs)
+{
+       dump_tf(tfs->root, 0);
+}