svn commit: r297236 - head/sys/fs/autofs
Edward Tomasz Napierala
trasz at FreeBSD.org
Thu Mar 24 13:34:40 UTC 2016
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);
More information about the svn-src-head
mailing list