Date: Thu, 24 Mar 2016 13:34:39 +0000 (UTC) From: Edward Tomasz Napierala <trasz@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r297236 - head/sys/fs/autofs Message-ID: <201603241334.u2ODYdq1011945@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: trasz Date: Thu Mar 24 13:34:39 2016 New Revision: 297236 URL: https://svnweb.freebsd.org/changeset/base/297236 Log: Speed up lookups in autofs(5) by using red-black trees instead of linear searches. Reviewed by: kib@ MFC after: 1 month Sponsored by: The FreeBSD Foundation Differential Revision: https://reviews.freebsd.org/D5627 Modified: head/sys/fs/autofs/autofs.c head/sys/fs/autofs/autofs.h head/sys/fs/autofs/autofs_vfsops.c head/sys/fs/autofs/autofs_vnops.c Modified: head/sys/fs/autofs/autofs.c ============================================================================== --- head/sys/fs/autofs/autofs.c Thu Mar 24 13:28:33 2016 (r297235) +++ head/sys/fs/autofs/autofs.c Thu Mar 24 13:34:39 2016 (r297236) @@ -77,6 +77,7 @@ #include <sys/sysctl.h> #include <sys/syscallsubr.h> #include <sys/taskqueue.h> +#include <sys/tree.h> #include <sys/vnode.h> #include <machine/atomic.h> #include <vm/uma.h> @@ -149,6 +150,15 @@ TUNABLE_INT("vfs.autofs.interruptible", SYSCTL_INT(_vfs_autofs, OID_AUTO, interruptible, CTLFLAG_RWTUN, &autofs_interruptible, 1, "Allow requests to be interrupted by signal"); +static int +autofs_node_cmp(const struct autofs_node *a, const struct autofs_node *b) +{ + + return (strcmp(a->an_name, b->an_name)); +} + +RB_GENERATE(autofs_node_tree, autofs_node, an_link, autofs_node_cmp); + int autofs_init(struct vfsconf *vfsp) { Modified: head/sys/fs/autofs/autofs.h ============================================================================== --- head/sys/fs/autofs/autofs.h Thu Mar 24 13:28:33 2016 (r297235) +++ head/sys/fs/autofs/autofs.h Thu Mar 24 13:34:39 2016 (r297236) @@ -65,11 +65,12 @@ extern int autofs_mount_on_stat; #define AUTOFS_ASSERT_UNLOCKED(X) sx_assert(&X->am_lock, SA_UNLOCKED) struct autofs_node { - TAILQ_ENTRY(autofs_node) an_next; + RB_ENTRY(autofs_node) an_link; char *an_name; int an_fileno; struct autofs_node *an_parent; - TAILQ_HEAD(, autofs_node) an_children; + RB_HEAD(autofs_node_tree, + autofs_node) an_children; struct autofs_mount *an_mount; struct vnode *an_vnode; struct sx an_vnode_lock; @@ -136,4 +137,6 @@ void autofs_node_delete(struct autofs_no int autofs_node_vn(struct autofs_node *anp, struct mount *mp, int flags, struct vnode **vpp); +RB_PROTOTYPE(autofs_node_tree, autofs_node, an_link, autofs_node_cmp); + #endif /* !AUTOFS_H */ Modified: head/sys/fs/autofs/autofs_vfsops.c ============================================================================== --- head/sys/fs/autofs/autofs_vfsops.c Thu Mar 24 13:28:33 2016 (r297235) +++ head/sys/fs/autofs/autofs_vfsops.c Thu Mar 24 13:34:39 2016 (r297236) @@ -42,6 +42,7 @@ #include <sys/stat.h> #include <sys/sx.h> #include <sys/taskqueue.h> +#include <sys/tree.h> #include <sys/vnode.h> #include <fs/autofs/autofs.h> @@ -158,10 +159,10 @@ autofs_unmount(struct mount *mp, int mnt /* * Not terribly efficient, but at least not recursive. */ - while (!TAILQ_EMPTY(&->am_root->an_children)) { - anp = TAILQ_FIRST(&->am_root->an_children); - while (!TAILQ_EMPTY(&anp->an_children)) - anp = TAILQ_FIRST(&anp->an_children); + while (!RB_EMPTY(&->am_root->an_children)) { + anp = RB_MIN(autofs_node_tree, &->am_root->an_children); + while (!RB_EMPTY(&anp->an_children)) + anp = RB_MIN(autofs_node_tree, &anp->an_children); autofs_node_delete(anp); } autofs_node_delete(amp->am_root); Modified: head/sys/fs/autofs/autofs_vnops.c ============================================================================== --- head/sys/fs/autofs/autofs_vnops.c Thu Mar 24 13:28:33 2016 (r297235) +++ head/sys/fs/autofs/autofs_vnops.c Thu Mar 24 13:34:39 2016 (r297236) @@ -44,6 +44,7 @@ __FBSDID("$FreeBSD$"); #include <sys/stat.h> #include <sys/systm.h> #include <sys/taskqueue.h> +#include <sys/tree.h> #include <sys/vnode.h> #include <machine/atomic.h> #include <vm/uma.h> @@ -450,7 +451,7 @@ autofs_readdir(struct vop_readdir_args * * Write out the directory entries for subdirectories. */ AUTOFS_SLOCK(amp); - TAILQ_FOREACH(child, &anp->an_children, an_next) { + RB_FOREACH(child, autofs_node_tree, &anp->an_children) { /* * Check the offset to skip entries returned by previous * calls to getdents(). @@ -575,8 +576,8 @@ autofs_node_new(struct autofs_node *pare anp->an_parent = parent; anp->an_mount = amp; if (parent != NULL) - TAILQ_INSERT_TAIL(&parent->an_children, anp, an_next); - TAILQ_INIT(&anp->an_children); + RB_INSERT(autofs_node_tree, &parent->an_children, anp); + RB_INIT(&anp->an_children); *anpp = anp; return (0); @@ -586,27 +587,28 @@ int autofs_node_find(struct autofs_node *parent, const char *name, int namelen, struct autofs_node **anpp) { - struct autofs_node *anp; + struct autofs_node *anp, find; + int error; AUTOFS_ASSERT_LOCKED(parent->an_mount); - TAILQ_FOREACH(anp, &parent->an_children, an_next) { - if (namelen >= 0) { - if (strlen(anp->an_name) != namelen) - continue; - if (strncmp(anp->an_name, name, namelen) != 0) - continue; - } else { - if (strcmp(anp->an_name, name) != 0) - continue; - } + if (namelen >= 0) + find.an_name = strndup(name, namelen, M_AUTOFS); + else + find.an_name = strdup(name, M_AUTOFS); + anp = RB_FIND(autofs_node_tree, &parent->an_children, &find); + if (anp != NULL) { + error = 0; if (anpp != NULL) *anpp = anp; - return (0); + } else { + error = ENOENT; } - return (ENOENT); + free(find.an_name, M_AUTOFS); + + return (error); } void @@ -615,13 +617,13 @@ autofs_node_delete(struct autofs_node *a struct autofs_node *parent; AUTOFS_ASSERT_XLOCKED(anp->an_mount); - KASSERT(TAILQ_EMPTY(&anp->an_children), ("have children")); + KASSERT(RB_EMPTY(&anp->an_children), ("have children")); callout_drain(&anp->an_callout); parent = anp->an_parent; if (parent != NULL) - TAILQ_REMOVE(&parent->an_children, anp, an_next); + RB_REMOVE(autofs_node_tree, &parent->an_children, anp); sx_destroy(&anp->an_vnode_lock); free(anp->an_name, M_AUTOFS); uma_zfree(autofs_node_zone, anp);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201603241334.u2ODYdq1011945>