6503650 dv_findbyname doesn't scale well in the presence of an extremely large number of devices

6672987 dev filesystem lookups are slow

8 files changed, 145 insertions, 105 deletions

diff --git a/usr/src/uts/common/fs/dev/sdev_netops.c b/usr/src/uts/common/fs/dev/sdev_netops.c
index b51b155344..22679f7004 100644
--- a/usr/src/uts/common/fs/dev/sdev_netops.c
+++ b/usr/src/uts/common/fs/dev/sdev_netops.c
@@ -270,8 +270,8 @@ devnet_filldir(struct sdev_node *ddv)
 		rw_enter(&ddv->sdev_contents, RW_WRITER);
 	}
 
-	for (dv = ddv->sdev_dot; dv; dv = next) {
-		next = dv->sdev_next;
+	for (dv = SDEV_FIRST_ENTRY(ddv); dv; dv = next) {
+		next = SDEV_NEXT_ENTRY(ddv, dv);
 
 		/* skip stale nodes */
 		if (dv->sdev_flags & SDEV_STALE)
diff --git a/usr/src/uts/common/fs/dev/sdev_profile.c b/usr/src/uts/common/fs/dev/sdev_profile.c
index 1756ac7115..6a0095657e 100644
--- a/usr/src/uts/common/fs/dev/sdev_profile.c
+++ b/usr/src/uts/common/fs/dev/sdev_profile.c
@@ -20,7 +20,7 @@
  */
 
 /*
- * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
  */
 
@@ -650,7 +650,8 @@ apply_dir_pattern(struct sdev_node *dir, char *expr, char *pathleft, int type)
 
 	/* directory pattern */
 	rw_enter(&dir->sdev_contents, RW_WRITER);
-	for (dv = dir->sdev_dot; dv; dv = dv->sdev_next) {
+
+	for (dv = SDEV_FIRST_ENTRY(dir); dv; dv = SDEV_NEXT_ENTRY(dir, dv)) {
 		if (gmatch(dv->sdev_name, expr) == 0 ||
 		    SDEVTOV(dv)->v_type != VDIR)
 			continue;
diff --git a/usr/src/uts/common/fs/dev/sdev_ptsops.c b/usr/src/uts/common/fs/dev/sdev_ptsops.c
index f6d1fda64e..a20d896c2b 100644
--- a/usr/src/uts/common/fs/dev/sdev_ptsops.c
+++ b/usr/src/uts/common/fs/dev/sdev_ptsops.c
@@ -19,7 +19,7 @@
  * CDDL HEADER END
  */
 /*
- * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
  */
 
@@ -236,8 +236,8 @@ devpts_prunedir(struct sdev_node *ddv)
 		rw_enter(&ddv->sdev_contents, RW_WRITER);
 	}
 
-	for (dv = ddv->sdev_dot; dv; dv = next) {
-		next = dv->sdev_next;
+	for (dv = SDEV_FIRST_ENTRY(ddv); dv; dv = next) {
+		next = SDEV_NEXT_ENTRY(ddv, dv);
 
 		/* skip stale nodes */
 		if (dv->sdev_flags & SDEV_STALE)
@@ -399,7 +399,7 @@ devpts_setattr(struct vnode *vp, struct vattr *vap, int flags,
 {
 	ASSERT((vp->v_type == VCHR) || (vp->v_type == VDIR));
 	return (devname_setattr_func(vp, vap, flags, cred,
-		    devpts_set_id, AT_UID|AT_GID));
+	    devpts_set_id, AT_UID|AT_GID));
 }
 
 
diff --git a/usr/src/uts/common/fs/dev/sdev_subr.c b/usr/src/uts/common/fs/dev/sdev_subr.c
index 77f47f4535..9b9172f5ee 100644
--- a/usr/src/uts/common/fs/dev/sdev_subr.c
+++ b/usr/src/uts/common/fs/dev/sdev_subr.c
@@ -243,6 +243,18 @@ sdev_node_cache_fini()
 	sdev_node_cache = NULL;
 }
 
+/*
+ * Compare two nodes lexographically to balance avl tree
+ */
+static int
+sdev_compare_nodes(const struct sdev_node *dv1, const struct sdev_node *dv2)
+{
+	int rv;
+	if ((rv = strcmp(dv1->sdev_name, dv2->sdev_name)) == 0)
+		return (0);
+	return ((rv < 0) ? -1 : 1);
+}
+
 void
 sdev_set_nodestate(struct sdev_node *dv, sdev_node_state_t state)
 {
@@ -312,8 +324,6 @@ sdev_nodeinit(struct sdev_node *ddv, char *nm, struct sdev_node **newdv,
 	vn_exists(vp);
 
 	dv->sdev_dotdot = NULL;
-	dv->sdev_dot = NULL;
-	dv->sdev_next = NULL;
 	dv->sdev_attrvp = NULL;
 	if (vap) {
 		sdev_attrinit(dv, vap);
@@ -378,6 +388,10 @@ sdev_nodeready(struct sdev_node *dv, struct vattr *vap, struct vnode *avp,
 		ASSERT(dv->sdev_dotdot);
 		ASSERT(SDEVTOV(dv->sdev_dotdot)->v_type == VDIR);
 		vp->v_rdev = SDEVTOV(dv->sdev_dotdot)->v_rdev;
+		avl_create(&dv->sdev_entries,
+		    (int (*)(const void *, const void *))sdev_compare_nodes,
+		    sizeof (struct sdev_node),
+		    offsetof(struct sdev_node, sdev_avllink));
 	} else if (type == VLNK) {
 		ASSERT(args);
 		dv->sdev_nlink = 1;
@@ -482,6 +496,11 @@ sdev_mkroot(struct vfs *vfsp, dev_t devdev, struct vnode *mvp,
 		dv->sdev_devtree_gen = 0;
 	}
 
+	avl_create(&dv->sdev_entries,
+	    (int (*)(const void *, const void *))sdev_compare_nodes,
+	    sizeof (struct sdev_node),
+	    offsetof(struct sdev_node, sdev_avllink));
+
 	rw_enter(&dv->sdev_contents, RW_WRITER);
 	sdev_set_nodestate(dv, SDEV_READY);
 	rw_exit(&dv->sdev_contents);
@@ -963,6 +982,11 @@ sdev_nodedestroy(struct sdev_node *dv, uint_t flags)
 	if (!SDEV_IS_GLOBAL(dv))
 		sdev_prof_free(dv);
 
+	if (SDEVTOV(dv)->v_type == VDIR) {
+		ASSERT(SDEV_FIRST_ENTRY(dv) == NULL);
+		avl_destroy(&dv->sdev_entries);
+	}
+
 	mutex_destroy(&dv->sdev_lookup_lock);
 	cv_destroy(&dv->sdev_lookup_cv);
 
@@ -980,25 +1004,21 @@ struct sdev_node *
 sdev_findbyname(struct sdev_node *ddv, char *nm)
 {
 	struct sdev_node *dv;
-	size_t	nmlen = strlen(nm);
+	struct sdev_node dvtmp;
+	avl_index_t	where;
 
 	ASSERT(RW_LOCK_HELD(&ddv->sdev_contents));
-	for (dv = ddv->sdev_dot; dv; dv = dv->sdev_next) {
-		if (dv->sdev_namelen != nmlen) {
-			continue;
-		}
 
-		/*
-		 * Can't lookup stale nodes
-		 */
+	dvtmp.sdev_name = nm;
+	dv = avl_find(&ddv->sdev_entries, &dvtmp, &where);
+	if (dv) {
+		ASSERT(dv->sdev_dotdot == ddv);
+		ASSERT(strcmp(dv->sdev_name, nm) == 0);
+		/* Can't lookup stale nodes */
 		if (dv->sdev_flags & SDEV_STALE) {
 			sdcmn_err9((
-			    "sdev_findbyname: skipped stale node: %s\n",
-			    dv->sdev_name));
-			continue;
-		}
-
-		if (strcmp(dv->sdev_name, nm) == 0) {
+			    "sdev_findbyname: skipped stale node: %s\n", nm));
+		} else {
 			SDEV_HOLD(dv);
 			return (dv);
 		}
@@ -1012,14 +1032,16 @@ sdev_findbyname(struct sdev_node *ddv, char *nm)
 void
 sdev_direnter(struct sdev_node *ddv, struct sdev_node *dv)
 {
+	avl_index_t where;
+
 	ASSERT(RW_WRITE_HELD(&ddv->sdev_contents));
 	ASSERT(SDEVTOV(ddv)->v_type == VDIR);
 	ASSERT(ddv->sdev_nlink >= 2);
 	ASSERT(dv->sdev_nlink == 0);
 
 	dv->sdev_dotdot = ddv;
-	dv->sdev_next = ddv->sdev_dot;
-	ddv->sdev_dot = dv;
+	VERIFY(avl_find(&ddv->sdev_entries, dv, &where) == NULL);
+	avl_insert(&ddv->sdev_entries, dv, where);
 	ddv->sdev_nlink++;
 }
 
@@ -1048,8 +1070,6 @@ decr_link(struct sdev_node *dv)
 static int
 sdev_dirdelete(struct sdev_node *ddv, struct sdev_node *dv)
 {
-	struct sdev_node *idv;
-	struct sdev_node *prev = NULL;
 	struct vnode *vp;
 
 	ASSERT(RW_WRITE_HELD(&ddv->sdev_contents));
@@ -1079,15 +1099,7 @@ sdev_dirdelete(struct sdev_node *ddv, struct sdev_node *dv)
 		decr_link(dv);		/* . to self */
 	}
 
-	for (idv = ddv->sdev_dot; idv && idv != dv;
-	    prev = idv, idv = idv->sdev_next)
-		;
-	ASSERT(idv == dv);	/* node to be deleted must exist */
-	if (prev == NULL)
-		ddv->sdev_dot = dv->sdev_next;
-	else
-		prev->sdev_next = dv->sdev_next;
-	dv->sdev_next = NULL;
+	avl_remove(&ddv->sdev_entries, dv);
 	decr_link(dv);	/* name, back to zero */
 	vp->v_count--;
 	mutex_exit(&vp->v_lock);
@@ -1289,16 +1301,15 @@ sdev_rnmnode(struct sdev_node *oddv, struct sdev_node *odv,
 
 	/* move dir contents */
 	if (doingdir) {
-		for (idv = odv->sdev_dot; idv; idv = idv->sdev_next) {
+		for (idv = SDEV_FIRST_ENTRY(odv); idv;
+		    idv = SDEV_NEXT_ENTRY(odv, idv)) {
 			error = sdev_rnmnode(odv, idv,
 			    (struct sdev_node *)(*ndvp), &ndv,
 			    idv->sdev_name, cred);
-
 			if (error)
 				goto err_out;
 			ndv = NULL;
 		}
-
 	}
 
 	if ((*ndvp)->sdev_attrvp) {
@@ -2501,7 +2512,7 @@ sdev_stale(struct sdev_node *ddv)
 	ASSERT(SDEVTOV(ddv)->v_type == VDIR);
 
 	rw_enter(&ddv->sdev_contents, RW_WRITER);
-	for (dv = ddv->sdev_dot; dv; dv = dv->sdev_next) {
+	for (dv = SDEV_FIRST_ENTRY(ddv); dv; dv = SDEV_NEXT_ENTRY(ddv, dv)) {
 		vp = SDEVTOV(dv);
 		if (vp->v_type == VDIR)
 			sdev_stale(dv);
@@ -2537,8 +2548,8 @@ sdev_cleandir(struct sdev_node *ddv, char *expr, uint_t flags)
 	 * We try our best to destroy all unused sdev_node's
 	 */
 	rw_enter(&ddv->sdev_contents, RW_WRITER);
-	for (dv = ddv->sdev_dot; dv; dv = next) {
-		next = dv->sdev_next;
+	for (dv = SDEV_FIRST_ENTRY(ddv); dv; dv = next) {
+		next = SDEV_NEXT_ENTRY(ddv, dv);
 		vp = SDEVTOV(dv);
 
 		if (expr && gmatch(dv->sdev_name, expr) == 0)
@@ -2845,7 +2856,8 @@ get_cache:
 
 	/* gets the cache */
 	diroff++;
-	for (dv = ddv->sdev_dot; dv; dv = dv->sdev_next, diroff++) {
+	for (dv = SDEV_FIRST_ENTRY(ddv); dv;
+	    dv = SDEV_NEXT_ENTRY(ddv, dv), diroff++) {
 		sdcmn_err3(("sdev_readdir: diroff %lld soff %lld for '%s' \n",
 		    diroff, soff, dv->sdev_name));
 
@@ -3728,8 +3740,6 @@ devname_inactive_func(struct vnode *vp, struct cred *cred,
 	int clean;
 	struct sdev_node *dv = VTOSDEV(vp);
 	struct sdev_node *ddv = dv->sdev_dotdot;
-	struct sdev_node *idv;
-	struct sdev_node *prev = NULL;
 	int state;
 	struct devname_nsmap *map = NULL;
 	struct devname_ops *dirops = NULL;
@@ -3765,15 +3775,7 @@ devname_inactive_func(struct vnode *vp, struct cred *cred,
 		if (vp->v_type == VDIR) {
 			dv->sdev_nlink--;
 		}
-		for (idv = ddv->sdev_dot; idv && idv != dv;
-		    prev = idv, idv = idv->sdev_next)
-			;
-		ASSERT(idv == dv);
-		if (prev == NULL)
-			ddv->sdev_dot = dv->sdev_next;
-		else
-			prev->sdev_next = dv->sdev_next;
-		dv->sdev_next = NULL;
+		avl_remove(&ddv->sdev_entries, dv);
 		dv->sdev_nlink--;
 		--vp->v_count;
 		mutex_exit(&vp->v_lock);
diff --git a/usr/src/uts/common/fs/devfs/devfs_subr.c b/usr/src/uts/common/fs/devfs/devfs_subr.c
index eeaac94430..d4b789a1d6 100644
--- a/usr/src/uts/common/fs/devfs/devfs_subr.c
+++ b/usr/src/uts/common/fs/devfs/devfs_subr.c
@@ -19,7 +19,7 @@
  * CDDL HEADER END
  */
 /*
- * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
  */
 
@@ -267,6 +267,18 @@ dv_mkino(dev_info_t *devi, vtype_t typ, dev_t dev)
 }
 
 /*
+ * Compare two nodes lexographically to balance avl tree
+ */
+static int
+dv_compare_nodes(const struct dv_node *dv1, const struct dv_node *dv2)
+{
+	int rv;
+	if ((rv = strcmp(dv1->dv_name, dv2->dv_name)) == 0)
+		return (0);
+	return ((rv < 0) ? -1 : 1);
+}
+
+/*
  * dv_mkroot
  *
  * Build the first VDIR dv_node.
@@ -308,6 +320,10 @@ dv_mkroot(struct vfs *vfsp, dev_t devfsdev)
 	dv->dv_busy = 0;
 	dv->dv_dflt_mode = 0;
 
+	avl_create(&dv->dv_entries,
+	    (int (*)(const void *, const void *))dv_compare_nodes,
+	    sizeof (struct dv_node), offsetof(struct dv_node, dv_avllink));
+
 	return (dv);
 }
 
@@ -332,6 +348,7 @@ dv_mkdir(struct dv_node *ddv, dev_info_t *devi, char *nm)
 	dv->dv_name = kmem_alloc(nmlen, KM_SLEEP);
 	bcopy(nm, dv->dv_name, nmlen);
 	dv->dv_namelen = nmlen - 1;	/* '\0' not included */
+
 	vp = DVTOV(dv);
 	vn_reinit(vp);
 	vp->v_flag = 0;
@@ -354,6 +371,10 @@ dv_mkdir(struct dv_node *ddv, dev_info_t *devi, char *nm)
 	dv->dv_busy = 0;
 	dv->dv_dflt_mode = 0;
 
+	avl_create(&dv->dv_entries,
+	    (int (*)(const void *, const void *))dv_compare_nodes,
+	    sizeof (struct dv_node), offsetof(struct dv_node, dv_avllink));
+
 	return (dv);
 }
 
@@ -378,6 +399,7 @@ dv_mknod(struct dv_node *ddv, dev_info_t *devi, char *nm,
 	dv->dv_name = kmem_alloc(nmlen, KM_SLEEP);
 	bcopy(nm, dv->dv_name, nmlen);
 	dv->dv_namelen = nmlen - 1;	/* no '\0' */
+
 	vp = DVTOV(dv);
 	vn_reinit(vp);
 	vp->v_flag = 0;
@@ -433,7 +455,6 @@ dv_destroy(struct dv_node *dv, uint_t flags)
 {
 	vnode_t *vp = DVTOV(dv);
 	ASSERT(dv->dv_nlink == 0);		/* no references */
-	ASSERT(dv->dv_next == NULL);		/* unlinked from directory */
 
 	dcmn_err4(("dv_destroy: %s\n", dv->dv_name));
 
@@ -450,6 +471,11 @@ dv_destroy(struct dv_node *dv, uint_t flags)
 		return;
 	}
 
+	if (vp->v_type == VDIR) {
+		ASSERT(DV_FIRST_ENTRY(dv) == NULL);
+		avl_destroy(&dv->dv_entries);
+	}
+
 	if (dv->dv_attrvp != NULLVP)
 		VN_RELE(dv->dv_attrvp);
 	if (dv->dv_attr != NULL)
@@ -469,21 +495,23 @@ dv_destroy(struct dv_node *dv, uint_t flags)
 /*
  * Find and hold dv_node by name
  */
-struct dv_node *
+static struct dv_node *
 dv_findbyname(struct dv_node *ddv, char *nm)
 {
-	struct dv_node	*dv;
-	size_t		nmlen = strlen(nm);
+	struct dv_node  *dv;
+	avl_index_t	where;
+	struct dv_node	dvtmp;
 
 	ASSERT(RW_LOCK_HELD(&ddv->dv_contents));
 	dcmn_err3(("dv_findbyname: %s\n", nm));
-	for (dv = ddv->dv_dot; dv; dv = dv->dv_next) {
-		if (dv->dv_namelen != nmlen)
-			continue;
-		if (strcmp(dv->dv_name, nm) == 0) {
-			VN_HOLD(DVTOV(dv));
-			return (dv);
-		}
+
+	dvtmp.dv_name = nm;
+	dv = avl_find(&ddv->dv_entries, &dvtmp, &where);
+	if (dv) {
+		ASSERT(dv->dv_dotdot == ddv);
+		ASSERT(strcmp(dv->dv_name, nm) == 0);
+		VN_HOLD(DVTOV(dv));
+		return (dv);
 	}
 	return (NULL);
 }
@@ -494,6 +522,8 @@ dv_findbyname(struct dv_node *ddv, char *nm)
 void
 dv_insert(struct dv_node *ddv, struct dv_node *dv)
 {
+	avl_index_t where;
+
 	ASSERT(RW_WRITE_HELD(&ddv->dv_contents));
 	ASSERT(DVTOV(ddv)->v_type == VDIR);
 	ASSERT(ddv->dv_nlink >= 2);
@@ -502,26 +532,27 @@ dv_insert(struct dv_node *ddv, struct dv_node *dv)
 	dcmn_err3(("dv_insert: %s\n", dv->dv_name));
 
 	dv->dv_dotdot = ddv;
-	dv->dv_next = ddv->dv_dot;
-	ddv->dv_dot = dv;
 	if (DVTOV(dv)->v_type == VDIR) {
 		ddv->dv_nlink++;	/* .. to containing directory */
 		dv->dv_nlink = 2;	/* name + . */
 	} else {
 		dv->dv_nlink = 1;	/* name */
 	}
+
+	/* enter node in the avl tree */
+	VERIFY(avl_find(&ddv->dv_entries, dv, &where) == NULL);
+	avl_insert(&ddv->dv_entries, dv, where);
 }
 
 /*
  * Unlink a dv_node from a perent directory
  */
 void
-dv_unlink(struct dv_node *ddv, struct dv_node *dv, struct dv_node **dv_pprev)
+dv_unlink(struct dv_node *ddv, struct dv_node *dv)
 {
 	/* verify linkage of arguments */
-	ASSERT(ddv && dv && dv_pprev);
+	ASSERT(ddv && dv);
 	ASSERT(dv->dv_dotdot == ddv);
-	ASSERT(*dv_pprev == dv);
 	ASSERT(RW_WRITE_HELD(&ddv->dv_contents));
 	ASSERT(DVTOV(ddv)->v_type == VDIR);
 
@@ -536,12 +567,10 @@ dv_unlink(struct dv_node *ddv, struct dv_node *dv, struct dv_node **dv_pprev)
 	ASSERT(ddv->dv_nlink >= 2);
 	ASSERT(dv->dv_nlink == 0);
 
-	/* update ddv->dv_dot/dv_next */
-	*dv_pprev = dv->dv_next;
-
 	dv->dv_dotdot = NULL;
-	dv->dv_next = NULL;
-	dv->dv_dot = NULL;
+
+	/* remove from avl tree */
+	avl_remove(&ddv->dv_entries, dv);
 }
 
 /*
@@ -824,10 +853,10 @@ dv_find_leafnode(dev_info_t *devi, char *minor_nm, struct ddi_minor_data *r_mi)
 		 * Skip alias nodes and nodes without a name.
 		 */
 		if ((dmd->type == DDM_ALIAS) || (dmd->ddm_name == NULL))
-			    continue;
+			continue;
 
 		dcmn_err4(("dv_find_leafnode: (%s,%s)\n",
-			minor_nm, dmd->ddm_name));
+		    minor_nm, dmd->ddm_name));
 		if (strcmp(minor_nm, dmd->ddm_name) == 0) {
 			r_mi->ddm_dev = dmd->ddm_dev;
 			r_mi->ddm_spec_type = dmd->ddm_spec_type;
@@ -1164,7 +1193,7 @@ found:
 		 * sp->s_devvp, and sp->s_dip)
 		 */
 		*vpp = specvp_devfs(vp, vp->v_rdev, vp->v_type, cred,
-			dv->dv_devi);
+		    dv->dv_devi);
 		VN_RELE(vp);
 		if (*vpp == NULLVP)
 			rv = ENOSYS;
@@ -1205,7 +1234,7 @@ dv_filldir(struct dv_node *ddv)
 
 	if (ndi_devi_config(pdevi, NDI_NO_EVENT) != NDI_SUCCESS) {
 		dcmn_err3(("dv_filldir: config error %s\n",
-			ddv->dv_name));
+		    ddv->dv_name));
 	}
 
 	ndi_devi_enter(pdevi, &circ);
@@ -1277,7 +1306,7 @@ int
 dv_cleandir(struct dv_node *ddv, char *devnm, uint_t flags)
 {
 	struct dv_node *dv;
-	struct dv_node **pprev, **npprev;
+	struct dv_node *next;
 	struct vnode *vp;
 	int busy = 0;
 
@@ -1299,9 +1328,8 @@ dv_cleandir(struct dv_node *ddv, char *devnm, uint_t flags)
 	    !rw_tryenter(&ddv->dv_contents, RW_WRITER))
 		return (EBUSY);
 
-	for (pprev = &ddv->dv_dot, dv = *pprev; dv;
-	    pprev = npprev, dv = *pprev) {
-		npprev = &dv->dv_next;
+	for (dv = DV_FIRST_ENTRY(ddv); dv; dv = next) {
+		next = DV_NEXT_ENTRY(ddv, dv);
 
 		/*
 		 * If devnm is specified, the non-minor portion of the
@@ -1361,7 +1389,7 @@ dv_cleandir(struct dv_node *ddv, char *devnm, uint_t flags)
 		}
 
 		/* unlink from directory */
-		dv_unlink(ddv, dv, pprev);
+		dv_unlink(ddv, dv);
 
 		/* drop locks */
 		mutex_exit(&vp->v_lock);
@@ -1372,8 +1400,6 @@ dv_cleandir(struct dv_node *ddv, char *devnm, uint_t flags)
 		if (vp->v_count == 0)
 			dv_destroy(dv, flags);
 
-		/* pointer to previous stays unchanged */
-		npprev = pprev;
 		continue;
 
 		/*
@@ -1407,7 +1433,7 @@ set_busy:	busy++;
 static int
 dv_reset_perm_dir(struct dv_node *ddv, uint_t flags)
 {
-	struct dv_node *dv, *next = NULL;
+	struct dv_node *dv;
 	struct vnode *vp;
 	int retval = 0;
 	struct vattr *attrp;
@@ -1418,9 +1444,8 @@ dv_reset_perm_dir(struct dv_node *ddv, uint_t flags)
 	mode_t old_mode;
 
 	rw_enter(&ddv->dv_contents, RW_WRITER);
-	for (dv = ddv->dv_dot; dv; dv = next) {
+	for (dv = DV_FIRST_ENTRY(ddv); dv; dv = DV_NEXT_ENTRY(ddv, dv)) {
 		int error = 0;
-		next = dv->dv_next;
 		nm = dv->dv_name;
 
 		rw_enter(&dv->dv_contents, RW_READER);
@@ -1454,7 +1479,7 @@ dv_reset_perm_dir(struct dv_node *ddv, uint_t flags)
 				 * No attribute vp, try to find one.
 				 */
 				dv_shadow_node(DVTOV(ddv), nm, vp,
-					NULL, NULLVP, kcred, 0);
+				    NULL, NULLVP, kcred, 0);
 			}
 			if (dv->dv_attrvp != NULLVP || dv->dv_attr == NULL) {
 				rw_exit(&dv->dv_contents);
@@ -1577,7 +1602,7 @@ devfs_remdrv_rmdir(vnode_t *dirvp, const char *dir, vnode_t *rvp)
 			break;
 
 		for (dp = dbuf; ((intptr_t)dp < (intptr_t)dbuf + dbuflen);
-			dp = (dirent64_t *)((intptr_t)dp + dp->d_reclen)) {
+		    dp = (dirent64_t *)((intptr_t)dp + dp->d_reclen)) {
 
 			nm = dp->d_name;
 
@@ -1595,7 +1620,7 @@ devfs_remdrv_rmdir(vnode_t *dirvp, const char *dir, vnode_t *rvp)
 				continue;
 
 			ASSERT(vp->v_type == VDIR ||
-				vp->v_type == VCHR || vp->v_type == VBLK);
+			    vp->v_type == VCHR || vp->v_type == VBLK);
 
 			if (vp->v_type == VDIR) {
 				error = devfs_remdrv_rmdir(vp, nm, rvp);
@@ -1717,7 +1742,7 @@ devfs_remdrv_cleanup(const char *dir, const char *nodename)
 			break;
 
 		for (dp = dbuf; ((intptr_t)dp < (intptr_t)dbuf + dbuflen);
-			dp = (dirent64_t *)((intptr_t)dp + dp->d_reclen)) {
+		    dp = (dirent64_t *)((intptr_t)dp + dp->d_reclen)) {
 
 			nm = dp->d_name;
 
@@ -1738,7 +1763,7 @@ devfs_remdrv_cleanup(const char *dir, const char *nodename)
 				continue;
 
 			ASSERT(vp->v_type == VDIR ||
-				vp->v_type == VCHR || vp->v_type == VBLK);
+			    vp->v_type == VCHR || vp->v_type == VBLK);
 
 			if (vp->v_type == VDIR) {
 				error = devfs_remdrv_rmdir(vp, nm, rvp);
@@ -1799,7 +1824,7 @@ dv_walk(
 
 	rw_enter(&ddv->dv_contents, RW_READER);
 	mutex_enter(&dvp->v_lock);
-	for (dv = ddv->dv_dot; dv; dv = dv->dv_next) {
+	for (dv = DV_FIRST_ENTRY(ddv); dv; dv = DV_NEXT_ENTRY(ddv, dv)) {
 		/*
 		 * If devnm is not NULL and is not the empty string,
 		 * select only dv_nodes with matching non-minor name
diff --git a/usr/src/uts/common/fs/devfs/devfs_vnops.c b/usr/src/uts/common/fs/devfs/devfs_vnops.c
index 5361b7e00d..13021229f0 100644
--- a/usr/src/uts/common/fs/devfs/devfs_vnops.c
+++ b/usr/src/uts/common/fs/devfs/devfs_vnops.c
@@ -948,7 +948,8 @@ devfs_readdir(struct vnode *dvp, struct uio *uiop, struct cred *cred, int *eofp,
 	}
 
 	diroff++;
-	for (dv = ddv->dv_dot; dv; dv = dv->dv_next, diroff++) {
+	for (dv = DV_FIRST_ENTRY(ddv); dv;
+	    dv = DV_NEXT_ENTRY(ddv, dv), diroff++) {
 		/*
 		 * although DDM_INTERNAL_PATH minor nodes are skipped for
 		 * readdirs outside the kernel, they still occupy directory
diff --git a/usr/src/uts/common/sys/fs/dv_node.h b/usr/src/uts/common/sys/fs/dv_node.h
index 52de93794a..c3c1daa4d5 100644
--- a/usr/src/uts/common/sys/fs/dv_node.h
+++ b/usr/src/uts/common/sys/fs/dv_node.h
@@ -19,7 +19,7 @@
  * CDDL HEADER END
  */
 /*
- * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
+ * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  * Use is subject to license terms.
  */
 
@@ -44,6 +44,7 @@
 #include <sys/ddi_impldefs.h>
 #include <sys/fs/sdev_node.h>
 #include <sys/devpolicy.h>
+#include <sys/avl.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -57,7 +58,6 @@ extern "C" {
 typedef struct dv_node {
 	char		*dv_name;	/* pointer to name */
 	size_t		dv_namelen;	/* strlen(dv_name) */
-
 	struct vnode	*dv_vnode;	/* vnode for this dv_node */
 
 	/*
@@ -70,8 +70,8 @@ typedef struct dv_node {
 					/* has ndi_devi_hold on device */
 
 	struct dv_node	*dv_dotdot;	/* parent: my parent dv_node */
-	struct dv_node	*dv_dot;	/* child: VDIR: head of children */
-	struct dv_node	*dv_next;	/* sibling: next in this directory */
+	avl_tree_t	dv_entries;	/* VDIR: contents as avl tree */
+	avl_node_t	dv_avllink;	/* avl node linkage */
 
 	struct vnode	*dv_attrvp;	/* persistent attribute store */
 	struct vattr	*dv_attr;	/* attributes not yet persistent */
@@ -151,6 +151,11 @@ struct dv_fid {
 #define	DV_SHADOW_CREATE	0x01		/* create attribute node */
 #define	DV_SHADOW_WRITE_HELD	0x02		/* dv_contents write held */
 
+/*
+ * Directory tree traversal
+ */
+#define	DV_FIRST_ENTRY(ddv)	avl_first(&(ddv)->dv_entries)
+#define	DV_NEXT_ENTRY(ddv, dv)	AVL_NEXT(&(ddv)->dv_entries, (dv))
 
 extern uint_t devfs_clean_key;	/* tsd key */
 extern const char dvnm[];	/* share some space.. */
@@ -161,7 +166,6 @@ extern void dv_node_cache_fini(void);
 extern struct dv_node *dv_mkdir(struct dv_node *, dev_info_t *, char *);
 extern struct dv_node *dv_mkroot(struct vfs *, dev_t);
 extern void dv_destroy(struct dv_node *, uint_t);
-extern struct dv_node *dv_findbyname(struct dv_node *, char *);
 extern void dv_insert(struct dv_node *, struct dv_node *);
 extern void dv_shadow_node(struct vnode *, char *nm, struct vnode *,
     struct pathname *, struct vnode *, struct cred *, int);
diff --git a/usr/src/uts/common/sys/fs/sdev_impl.h b/usr/src/uts/common/sys/fs/sdev_impl.h
index 33142fe703..ce86e0d5c0 100644
--- a/usr/src/uts/common/sys/fs/sdev_impl.h
+++ b/usr/src/uts/common/sys/fs/sdev_impl.h
@@ -173,8 +173,9 @@ typedef struct sdev_node {
 
 	krwlock_t	sdev_contents;	/* rw lock for this data structure */
 	struct sdev_node *sdev_dotdot;	/* parent */
-	struct sdev_node *sdev_dot;	/* child: VDIR: head of children */
-	struct sdev_node *sdev_next;	/* sibling: next in this directory */
+
+	avl_tree_t	sdev_entries;	/* VDIR: contents as avl tree */
+	avl_node_t	sdev_avllink;	/* avl node linkage */
 
 	struct vnode	*sdev_attrvp;	/* backing store vnode if persisted */
 	struct vattr	*sdev_attr;	/* memory copy of the vattr */
@@ -210,6 +211,12 @@ typedef struct sdev_node {
 #define	sdev_prof		sdev_ldata.sdev_lprof
 
 /*
+ * Directory contents traversal
+ */
+#define	SDEV_FIRST_ENTRY(ddv)		avl_first(&(ddv)->sdev_entries)
+#define	SDEV_NEXT_ENTRY(ddv, dv)	AVL_NEXT(&(ddv)->sdev_entries, (dv))
+
+/*
  * sdev_state
  *
  * A sdev_node may go through 3 states: