use rb-tree for directory lookups
authorJohannes Hofmann <johannes.hofmann@gmx.de>
Tue, 22 May 2012 21:37:55 +0000 (23:37 +0200)
committerFran├žois Tigeot <ftigeot@wolfpond.org>
Mon, 18 Jun 2012 07:15:28 +0000 (09:15 +0200)
* tmpfs directories are structured as lists of directory entries; this
  leads to linear lookup costs. Directories with many files become fairly
  expensive to operate on.

* This patch uses a rb-tree keyed on the name of the searched file to
  speed up lookups

* Besides this rb-tree implementation, a hash version was also tested.
  Both gave solid performance enhancements compared to the previous tmpfs
  implementation.
  The rb-tree version was the faster of the two and thus becomes the
  choosen one.

* See issue 2375 for details and performance numbers
  https://bugs.dragonflybsd.org/issues/2375

sys/vfs/tmpfs/tmpfs.h
sys/vfs/tmpfs/tmpfs_subr.c
sys/vfs/tmpfs/tmpfs_vfsops.c
sys/vfs/tmpfs/tmpfs_vnops.c

index 7e8a7e6..2e20923 100644 (file)
@@ -40,7 +40,7 @@
  * --------------------------------------------------------------------- */
 #include <sys/dirent.h>
 #include <sys/mount.h>
-#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/vnode.h>
 #include <sys/file.h>
 #include <sys/lock.h>
@@ -62,7 +62,7 @@ MALLOC_DECLARE(M_TMPFSMNT);
  * Internal representation of a tmpfs directory entry.
  */
 struct tmpfs_dirent {
-       TAILQ_ENTRY(tmpfs_dirent)       td_entries;
+       RB_ENTRY(tmpfs_dirent) rb_node;
 
        /* Length of the name stored in this directory entry.  This avoids
         * the need to recalculate it every time the name is used. */
@@ -77,19 +77,24 @@ struct tmpfs_dirent {
        struct tmpfs_node *             td_node;
 };
 
-/* A directory in tmpfs holds a sorted list of directory entries, which in
+struct tmpfs_dirtree;
+RB_HEAD(tmpfs_dirtree, tmpfs_dirent);
+RB_PROTOTYPE(tmpfs_dirtree, tmpfs_dirent, rb_node,
+       tmpfs_dirtree_compare);
+
+
+/* A directory in tmpfs holds a set of directory entries, which in
  * turn point to other files (which can be directories themselves).
  *
- * In tmpfs, this list is managed by a tail queue, whose head is defined by
- * the struct tmpfs_dir type.
+ * In tmpfs, this set is managed by a red-black tree, whose root is defined
+ * by the struct tmpfs_dirtree type.
  *
- * It is imporant to notice that directories do not have entries for . and
+ * It is important to notice that directories do not have entries for . and
  * .. as other file systems do.  These can be generated when requested
  * based on information available by other means, such as the pointer to
  * the node itself in the former case or the pointer to the parent directory
  * in the latter case.  This is done to simplify tmpfs's code and, more
  * importantly, to remove redundancy. */
-TAILQ_HEAD(tmpfs_dir, tmpfs_dirent);
 
 /* Each entry in a directory has a cookie that identifies it.  Cookies
  * supersede offsets within directories because, given how tmpfs stores
@@ -252,10 +257,10 @@ struct tmpfs_node {
                         * this property identifies the root node. */
                        struct tmpfs_node *     tn_parent;
 
-                       /* Head of a tail-queue that links the contents of
+                       /* Root of a red-black tree that links the contents of
                         * the directory together.  See above for a
                         * description of its contents. */
-                       struct tmpfs_dir        tn_dirhead;
+                       struct tmpfs_dirtree    tn_dirtree;
 
                        /* Number and pointer of the first directory entry
                         * returned by the readdir operation if it were
index 14e70b9..0913eb9 100644 (file)
 #include <vfs/tmpfs/tmpfs_vnops.h>
 
 static ino_t tmpfs_fetch_ino(struct tmpfs_mount *);
+static int tmpfs_dirtree_compare(struct tmpfs_dirent *a,
+       struct tmpfs_dirent *b);
+
+RB_GENERATE(tmpfs_dirtree, tmpfs_dirent, rb_node, tmpfs_dirtree_compare);
+
 
 /* --------------------------------------------------------------------- */
 
@@ -129,7 +134,7 @@ tmpfs_alloc_node(struct tmpfs_mount *tmp, enum vtype type,
                break;
 
        case VDIR:
-               TAILQ_INIT(&nnode->tn_dir.tn_dirhead);
+               RB_INIT(&nnode->tn_dir.tn_dirtree);
                KKASSERT(parent != nnode);
                KKASSERT(IMPLIES(parent == NULL, tmp->tm_root == NULL));
                nnode->tn_dir.tn_parent = parent;
@@ -609,7 +614,7 @@ void
 tmpfs_dir_attach(struct tmpfs_node *dnode, struct tmpfs_dirent *de)
 {
        TMPFS_NODE_LOCK(dnode);
-       TAILQ_INSERT_TAIL(&dnode->tn_dir.tn_dirhead, de, td_entries);
+       RB_INSERT(tmpfs_dirtree, &dnode->tn_dir.tn_dirtree, de);
 
        TMPFS_ASSERT_ELOCKED(dnode);
        dnode->tn_size += sizeof(struct tmpfs_dirent);
@@ -633,7 +638,7 @@ tmpfs_dir_detach(struct tmpfs_node *dnode, struct tmpfs_dirent *de)
                dnode->tn_dir.tn_readdir_lastn = 0;
                dnode->tn_dir.tn_readdir_lastp = NULL;
        }
-       TAILQ_REMOVE(&dnode->tn_dir.tn_dirhead, de, td_entries);
+       RB_REMOVE(tmpfs_dirtree, &dnode->tn_dir.tn_dirtree, de);
 
        TMPFS_ASSERT_ELOCKED(dnode);
        dnode->tn_size -= sizeof(struct tmpfs_dirent);
@@ -658,17 +663,16 @@ tmpfs_dir_lookup(struct tmpfs_node *node, struct tmpfs_node *f,
 {
        struct tmpfs_dirent *de;
        int len = ncp->nc_nlen;
+       struct tmpfs_dirent wanted;
+
+       wanted.td_namelen = len;
+       wanted.td_name = ncp->nc_name;
 
        TMPFS_VALIDATE_DIR(node);
 
-       TAILQ_FOREACH(de, &node->tn_dir.tn_dirhead, td_entries) {
-               if (f != NULL && de->td_node != f)
-                   continue;
-               if (len == de->td_namelen) {
-                       if (!memcmp(ncp->nc_name, de->td_name, len))
-                               break;
-               }
-       }
+       de = RB_FIND(tmpfs_dirtree, &node->tn_dir.tn_dirtree, &wanted);
+
+       KKASSERT(f == NULL || f == de->td_node);
 
        TMPFS_NODE_LOCK(node);
        node->tn_status |= TMPFS_NODE_ACCESSED;
@@ -760,7 +764,7 @@ tmpfs_dir_getdotdotdent(struct tmpfs_mount *tmp, struct tmpfs_node *node,
                if (error == 0) {
                        struct tmpfs_dirent *de;
 
-                       de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+                       de = RB_MIN(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
                        if (de == NULL)
                                uio->uio_offset = TMPFS_DIRCOOKIE_EOF;
                        else
@@ -790,7 +794,7 @@ tmpfs_dir_lookupbycookie(struct tmpfs_node *node, off_t cookie)
                return node->tn_dir.tn_readdir_lastp;
        }
 
-       TAILQ_FOREACH(de, &node->tn_dir.tn_dirhead, td_entries) {
+       RB_FOREACH(de, tmpfs_dirtree, &node->tn_dir.tn_dirtree) {
                if (tmpfs_dircookie(de) == cookie) {
                        break;
                }
@@ -892,7 +896,7 @@ tmpfs_dir_getdents(struct tmpfs_node *node, struct uio *uio, off_t *cntp)
                error = uiomove((caddr_t)&d, reclen, uio);
 
                (*cntp)++;
-               de = TAILQ_NEXT(de, td_entries);
+               de = RB_NEXT(tmpfs_dirtree, node->tn_dir.tn_dirtree, de);
        } while (error == 0 && uio->uio_resid > 0 && de != NULL);
 
        /* Update the offset and cache. */
@@ -1346,3 +1350,14 @@ tmpfs_fetch_ino(struct tmpfs_mount *tmp)
 
        return (ret);
 }
+
+static int
+tmpfs_dirtree_compare(struct tmpfs_dirent *a, struct tmpfs_dirent *b)
+{
+       if (a->td_namelen > b->td_namelen)
+               return 1;
+       else if (a->td_namelen < b->td_namelen)
+               return -1;
+       else
+               return strncmp(a->td_name, b->td_name, a->td_namelen);
+}
index 4aa5eb1..de23cb7 100644 (file)
@@ -351,8 +351,8 @@ tmpfs_unmount(struct mount *mp, int mntflags)
                if (node->tn_type == VDIR) {
                        struct tmpfs_dirent *de;
 
-                       while (!TAILQ_EMPTY(&node->tn_dir.tn_dirhead)) {
-                               de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+                       while (!RB_EMPTY(&node->tn_dir.tn_dirtree)) {
+                               de = RB_FIRST(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
                                tmpfs_dir_detach(node, de);
                                tmpfs_free_dirent(tmp, de);
                                node->tn_size -= sizeof(struct tmpfs_dirent);
index 990a1ce..3bf59c5 100644 (file)
@@ -924,7 +924,7 @@ tmpfs_nrename(struct vop_nrename_args *v)
        struct vnode *tdvp = v->a_tdvp;
        struct namecache *tncp = v->a_tnch->ncp;
        struct vnode *tvp;
-       struct tmpfs_dirent *de;
+       struct tmpfs_dirent *de, *tde;
        struct tmpfs_mount *tmp;
        struct tmpfs_node *fdnode;
        struct tmpfs_node *fnode;
@@ -1039,6 +1039,9 @@ tmpfs_nrename(struct vop_nrename_args *v)
         */
        if (fdnode != tdnode)
                tmpfs_dir_detach(fdnode, de);
+       else {
+               RB_REMOVE(tmpfs_dirtree, &fdnode->tn_dir.tn_dirtree, de);
+       }
 
        /*
         * Handle any name change.  Swap with newname, we will
@@ -1057,6 +1060,25 @@ tmpfs_nrename(struct vop_nrename_args *v)
        }
 
        /*
+        * If we are overwriting an entry, we have to remove the old one
+        * from the target directory.
+        */
+       if (tvp != NULL) {
+               /* Remove the old entry from the target directory. */
+               tde = tmpfs_dir_lookup(tdnode, tnode, tncp);
+               tmpfs_dir_detach(tdnode, tde);
+               tmpfs_knote(tdnode->tn_vnode, NOTE_DELETE);
+
+               /*
+                * Free the directory entry we just deleted.  Note that the
+                * node referred by it will not be removed until the vnode is
+                * really reclaimed.
+                */
+               tmpfs_free_dirent(VFS_TO_TMPFS(tvp->v_mount), tde);
+               /*cache_inval_vp(tvp, CINV_DESTROY);*/
+       }
+
+       /*
         * Link entry to target directory.  If the entry
         * represents a directory move the parent linkage
         * as well.
@@ -1084,29 +1106,11 @@ tmpfs_nrename(struct vop_nrename_args *v)
        } else {
                TMPFS_NODE_LOCK(tdnode);
                tdnode->tn_status |= TMPFS_NODE_MODIFIED;
+               RB_INSERT(tmpfs_dirtree, &tdnode->tn_dir.tn_dirtree, de);
                TMPFS_NODE_UNLOCK(tdnode);
        }
 
        /*
-        * If we are overwriting an entry, we have to remove the old one
-        * from the target directory.
-        */
-       if (tvp != NULL) {
-               /* Remove the old entry from the target directory. */
-               de = tmpfs_dir_lookup(tdnode, tnode, tncp);
-               tmpfs_dir_detach(tdnode, de);
-               tmpfs_knote(tdnode->tn_vnode, NOTE_DELETE);
-
-               /*
-                * Free the directory entry we just deleted.  Note that the
-                * node referred by it will not be removed until the vnode is
-                * really reclaimed.
-                */
-               tmpfs_free_dirent(VFS_TO_TMPFS(tvp->v_mount), de);
-               /*cache_inval_vp(tvp, CINV_DESTROY);*/
-       }
-
-       /*
         * Finish up
         */
        if (newname) {
@@ -1368,14 +1372,14 @@ outok:
                                off = TMPFS_DIRCOOKIE_DOTDOT;
                        } else {
                                if (off == TMPFS_DIRCOOKIE_DOTDOT) {
-                                       de = TAILQ_FIRST(&node->tn_dir.tn_dirhead);
+                                       de = RB_MIN(tmpfs_dirtree, &node->tn_dir.tn_dirtree);
                                } else if (de != NULL) {
-                                       de = TAILQ_NEXT(de, td_entries);
+                                       de = RB_NEXT(tmpfs_dirtree, &node->tn_dir.tn_dirtree, de);
                                } else {
                                        de = tmpfs_dir_lookupbycookie(node,
                                            off);
                                        KKASSERT(de != NULL);
-                                       de = TAILQ_NEXT(de, td_entries);
+                                       de = RB_NEXT(tmpfs_dirtree, &node->tn_dir.tn_dirtree, de);
                                }
                                if (de == NULL)
                                        off = TMPFS_DIRCOOKIE_EOF;