--UlVJffcvxoiEqYs2
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hello,

I made some changes to the device tree traversal API [*]:

  * Change names as per chap's comment (s/DIF_TOPDOWN/DIF_PREORDER,
    s/DIF_DOWNTOP/DIF_POSTORDER).
  * Remove traversal stack depth limit from device_iterator_alloc().
  * Make it possible to reuse one iterator object for either traversal
    direction.
  * Fix allocation bug (thanks Magnus Larsson).

New usage example:

	deviter_t 		di;
	device_t 		dv;

	di = device_iterator_alloc();
	if (di == NULL)
		panic("borked");

	device_iterator_init(di, TAILQ_FIRST(&alldevs),
	    DIF_PREORDER | DIF_WAITOK);

	while ((dv = device_iterator_foreach(di)) != NULL)
		printf("FOO %s\n", device_xname(dv));

	device_iterator_init(di, TAILQ_FIRST(&alldevs),
	    DIF_POSTORDER | DIF_WAITOK);

	while ((dv = device_iterator_foreach(di)) != NULL)
		printf("BAR %s\n", device_xname(dv));

	device_iterator_free(di);

I've kept DIF_NOWAIT at place -- while I agree we should avoid allocations
from interrupt context, I'd like to keep the option available _for now_.

Attached is the implementation itself (subr_devtree.c -> sys/kern/) and
a patch to be applied under sys/.

Looks OK to commit?

	-- Jachym

[*] http://mail-index.netbsd.org/tech-kern/2006/07/02/0010.html

--UlVJffcvxoiEqYs2
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="devtree.diff"

Index: sys/device.h
===================================================================
RCS file: /cvsroot/src/sys/sys/device.h,v
retrieving revision 1.90
diff -d -p -u -r1.90 device.h
--- sys/device.h	5 May 2006 18:04:43 -0000	1.90
+++ sys/device.h	21 Jul 2006 12:01:03 -0000
@@ -107,6 +107,12 @@ typedef struct cfdata *cfdata_t;
 typedef struct cfdriver *cfdriver_t;
 typedef struct cfattach *cfattach_t;
 typedef struct device *device_t;
+typedef struct devchild *devchild_t;
+
+struct devchild {
+	TAILQ_ENTRY(devchild) 	dvc_list;
+	device_t 		dvc_device;
+};
 
 struct device {
 	devclass_t	dv_class;	/* this device's classification */
@@ -122,6 +128,7 @@ struct device {
 	int		dv_flags;	/* misc. flags; see below */
 	int		*dv_locators;	/* our actual locators (optional) */
 	prop_dictionary_t dv_properties;/* properties dictionary */
+	TAILQ_HEAD(, devchild)	dv_child_list; /* this device's children */
 };
 
 /* dv_flags */
@@ -129,6 +136,14 @@ struct device {
 
 TAILQ_HEAD(devicelist, device);
 
+typedef struct deviter *deviter_t; 	/* kern/subr_devtree.c */
+
+/* deviter_t flags, bits 8-15 for internal needs */
+#define DIF_PREORDER 		0x0000
+#define DIF_WAITOK 		0x0000 		/* M_WAITOK */
+#define DIF_POSTORDER 		0x0001
+#define DIF_NOWAIT 		0x0002 		/* M_NOWAIT */
+
 /*
  * Description of a locator, as part of interface attribute definitions.
  */
@@ -357,6 +372,11 @@ void		*device_lookup(cfdriver_t, int);
 void		device_register(device_t, void *);
 #endif
 
+deviter_t 	device_iterator_alloc(void);
+void 		device_iterator_free(deviter_t);
+void 		device_iterator_init(deviter_t, device_t, int);
+device_t 	device_iterator_foreach(deviter_t);
+
 devclass_t	device_class(device_t);
 cfdata_t	device_cfdata(device_t);
 cfdriver_t	device_cfdriver(device_t);
Index: conf/files
===================================================================
RCS file: /cvsroot/src/sys/conf/files,v
retrieving revision 1.784
diff -d -p -u -r1.784 files
--- conf/files	26 Jun 2006 16:13:21 -0000	1.784
+++ conf/files	21 Jul 2006 12:01:25 -0000
@@ -1264,6 +1264,7 @@ file	kern/subr_blist.c		vmswap
 file	kern/subr_bufq.c
 file	kern/subr_callback.c
 file	kern/subr_devsw.c
+file	kern/subr_devtree.c
 file	kern/subr_disk.c
 file	kern/subr_iostat.c
 file	kern/subr_evcnt.c
Index: kern/subr_autoconf.c
===================================================================
RCS file: /cvsroot/src/sys/kern/subr_autoconf.c,v
retrieving revision 1.114
diff -d -p -u -r1.114 subr_autoconf.c
--- kern/subr_autoconf.c	14 May 2006 05:26:59 -0000	1.114
+++ kern/subr_autoconf.c	21 Jul 2006 12:01:38 -0000
@@ -160,6 +160,8 @@ struct deferred_config_head deferred_con
 struct deferred_config_head interrupt_config_queue;
 
 static void config_process_deferred(struct deferred_config_head *, device_t);
+static void config_insert_child(device_t);
+static void config_remove_child(device_t);
 
 /* Hooks to finalize configuration once all real devices have been found. */
 struct finalize_hook {
@@ -965,6 +967,7 @@ config_attach_loc(device_t parent, cfdat
 	    panic("config_attach: memory allocation for device softc failed");
 	memset(dev, 0, ca->ca_devsize);
 	TAILQ_INSERT_TAIL(&alldevs, dev, dv_list);	/* link up */
+	TAILQ_INIT(&dev->dv_child_list); 		/* no children yet */
 	dev->dv_class = cd->cd_class;
 	dev->dv_cfdata = cf;
 	dev->dv_cfdriver = cd;
@@ -997,6 +1000,7 @@ config_attach_loc(device_t parent, cfdat
 		aprint_naive("%s (root)", dev->dv_xname);
 		aprint_normal("%s (root)", dev->dv_xname);
 	} else {
+		config_insert_child(dev);
 		aprint_naive("%s at %s", dev->dv_xname, parent->dv_xname);
 		aprint_normal("%s at %s", dev->dv_xname, parent->dv_xname);
 		if (print)
@@ -1164,9 +1168,6 @@ config_detach(device_t dev, int flags)
 	cfdata_t cf;
 	const struct cfattach *ca;
 	struct cfdriver *cd;
-#ifdef DIAGNOSTIC
-	device_t d;
-#endif
 	int rv = 0, i;
 
 #ifdef DIAGNOSTIC
@@ -1216,18 +1217,12 @@ config_detach(device_t dev, int flags)
 #ifdef DIAGNOSTIC
 	/*
 	 * Sanity: If you're successfully detached, you should have no
-	 * children.  (Note that because children must be attached
-	 * after parents, we only need to search the latter part of
-	 * the list.)
+	 * children.
 	 */
-	for (d = TAILQ_NEXT(dev, dv_list); d != NULL;
-	    d = TAILQ_NEXT(d, dv_list)) {
-		if (d->dv_parent == dev) {
-			printf("config_detach: detached device %s"
-			    " has children %s\n", dev->dv_xname, d->dv_xname);
-			panic("config_detach");
-		}
-	}
+	if (! TAILQ_EMPTY(&dev->dv_child_list))
+		panic("config_detach: detached device %s has children %s",
+		    device_xname(dev),
+		    device_xname(TAILQ_FIRST(&dev->dv_child_list)->dvc_device));
 #endif
 
 	/* notify the parent that the child is gone */
@@ -1265,6 +1260,9 @@ config_detach(device_t dev, int flags)
 	 */
 	TAILQ_REMOVE(&alldevs, dev, dv_list);
 
+	if (dev->dv_parent != ROOT)
+		config_remove_child(dev);
+
 	/*
 	 * Remove from cfdriver's array, tell the world (unless it was
 	 * a pseudo-device), and free softc.
@@ -1608,3 +1606,50 @@ device_is_a(device_t dev, const char *dn
 
 	return (strcmp(dev->dv_cfdriver->cd_name, dname) == 0);
 }
+
+/*
+ * config_remove_child:
+ *
+ * 	Remove child from its parent. Called from process context.
+ */
+static void
+config_remove_child(device_t dev)
+{
+	struct devchild 	*dc;
+	device_t 		par = dev->dv_parent;
+
+	KASSERT(par != ROOT);
+
+	TAILQ_FOREACH(dc, &par->dv_child_list, dvc_list)
+		if (dc->dvc_device == dev)
+			break;
+	if (dc == NULL)
+		panic("config_remove_child: %s not listed as child of %s",
+		    device_xname(dev), device_xname(par));
+
+	TAILQ_REMOVE(&par->dv_child_list, dc, dvc_list);
+	free(dc, M_DEVBUF);
+}
+
+/*
+ * config_insert_child:
+ *
+ * 	Insert child to its parent. Called from process context.
+ */
+static void
+config_insert_child(device_t dev)
+{
+	struct devchild 	*dc;
+	device_t 		par = dev->dv_parent;
+
+	KASSERT(par != ROOT);
+
+	dc = (struct devchild *)malloc(sizeof(struct devchild), M_DEVBUF,
+	    cold ? M_NOWAIT : M_WAITOK);
+	if (dc == NULL)
+		panic("config_insert_child: could not alloc %s child %s",
+		    device_xname(par), device_xname(dev));
+
+	dc->dvc_device = dev;
+	TAILQ_INSERT_TAIL(&par->dv_child_list, dc, dvc_list);
+}

--UlVJffcvxoiEqYs2
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="subr_devtree.c"

/* $NetBSD$ */

/*
 * Copyright (c)2006 Jachym Holecek,
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD$");

#include "opt_ddb.h"

#include <sys/param.h>
#include <sys/kernel.h> 	/* cold */
#include <sys/device.h>
#include <sys/malloc.h>
#include <sys/queue.h>
#include <sys/types.h>


struct devstack {
	devchild_t 		dvs_child;
	device_t 		dvs_parent; 	/* only for postorder */
};

struct deviter {
	int 			dvi_flags;
	int 			dvi_depth;
	int 			dvi_index; 	/* current entry */
	device_t 		dvi_root; 	/* root of subtree */
	struct devstack 	*dvi_stack; 	/* traversal stack */
};

#define	CURCLD(di) 		(di)->dvi_stack[(di)->dvi_index].dvs_child
#define CURPAR(di) 		(di)->dvi_stack[(di)->dvi_index].dvs_parent

/* dvi_flags bits, DIF_* from <sys/device.h> and internal below */
#define DIF_FIRST 		0x8000

/* iterator stack depth incerement */
#define DEPTHINCR 		8


static device_t device_iterator_foreach_preorder(deviter_t);
static device_t device_iterator_foreach_postorder(deviter_t);
static int device_iterator_grow(deviter_t di, int mflags);


static inline const char *
device_iterator_name(deviter_t di)
{
	if (di->dvi_root == NULL)
		return ("<initial>");

	return (device_xname(di->dvi_root));
}

/*
 * device_iterator_grow: 				[internal]
 *
 * 	Grow traversal stack of iterator ${di} by a fixed increment,
 * 	use allocation flags ${mflags}.
 */
static int
device_iterator_grow(deviter_t di, int mflags)
{
	void 			*p;

	di->dvi_depth += DEPTHINCR;
	KASSERT(di->dvi_depth > 0);

	p = realloc(di->dvi_stack, di->dvi_depth * sizeof(struct devstack),
	    M_DEVBUF, mflags);
	if (p == NULL) {
		if (di->dvi_stack != NULL) {
			free(di->dvi_stack, M_DEVBUF);
			di->dvi_stack = NULL;
		}
		return (ENOMEM);
	}

	di->dvi_stack = (struct devstack *)p;
	return (0);
}

/*
 * device_iterator_descend: 				[internal]
 *
 * 	Descend traversal stack by one "frame", grow the stack if needed.
 */
static int
device_iterator_descend(deviter_t di)
{
	if (++di->dvi_index == di->dvi_depth)
		return (device_iterator_grow(di,
		    ISSET(di->dvi_flags, DIF_NOWAIT) ? M_NOWAIT : M_WAITOK));

	return (0);
}

/*
 * device_iterator_alloc:
 *
 * 	Create device iterator object. Assumes process context.
 */
deviter_t
device_iterator_alloc(void)
{
	deviter_t 		di;

	di = (deviter_t)malloc(sizeof(struct deviter), M_DEVBUF,
	    (cold ? M_NOWAIT : M_WAITOK));
	if (di == NULL)
		return (NULL);

	di->dvi_stack = NULL;
	di->dvi_flags = 0;
	di->dvi_depth = 0;
	di->dvi_index = 0;
	di->dvi_root = NULL;

	/* Allocate initial stack. */
	if (device_iterator_grow(di, (cold ? M_NOWAIT : M_WAITOK))) {
		free(di, M_DEVBUF);
		return (NULL);
	}

	return (di);
}

/*
 * device_iterator_free:
 *
 * 	Release any resources allocated by device iterator ${di}.
 */
void
device_iterator_free(deviter_t di)
{
	KASSERT(di != NULL);
	KASSERT(di->dvi_stack != NULL);

	free(di->dvi_stack, M_DEVBUF);
	free(di, M_DEVBUF);
}

/*
 * device_iterator_init:
 *
 * 	Setup iterator object ${di} to process subtree rooted by device
 * 	${dev} in a way specified by ${flags}.
 */
void
device_iterator_init(deviter_t di, device_t dev, int flags)
{
	KASSERT(di->dvi_depth > 0);

	di->dvi_flags = flags | DIF_FIRST;
	di->dvi_root = dev;
	di->dvi_index = 0;
	CURCLD(di) = TAILQ_FIRST(&dev->dv_child_list);

	if (ISSET(di->dvi_flags, DIF_POSTORDER))
		CURPAR(di) = dev;
}

/*
 * device_iterator_foreach:
 *
 * 	Iterate devices according to earlier call to device_iterator_init().
 */
device_t
device_iterator_foreach(deviter_t di)
{
	if (ISSET(di->dvi_flags, DIF_POSTORDER))
		return (device_iterator_foreach_postorder(di));
	else
		return (device_iterator_foreach_preorder(di));
}

/*
 * device_iterator_foreach_preorder: 			[internal]
 *
 * 	Iterate devices so that "parents" go before their "children".
 * 	In other words, a device is processed and if it has any children,
 * 	they're processed next (recursively).
 */
static device_t
device_iterator_foreach_preorder(deviter_t di)
{
	devchild_t 		dc;
	device_t 		dv;

	/* Handle subtree root, entered once. */
	if (ISSET(di->dvi_flags, DIF_FIRST)) {
		CLR(di->dvi_flags, DIF_FIRST);

		return (di->dvi_root);
	}

	/* Unwind until we get a valid entry. */
	while ((dc = CURCLD(di)) == NULL) {
		/* Top of the stack, we're done. */
		if (di->dvi_index == 0)
			return (NULL);

		di->dvi_index--;
	}

	dv = dc->dvc_device;
	CURCLD(di) = TAILQ_NEXT(dc, dvc_list);

	/* Setup descent into !leaf device. */
	if (! TAILQ_EMPTY(&dv->dv_child_list)) {
		if (device_iterator_descend(di))
			panic("device_iterator_foreach_preorder: %s devstack "
			    "overflow, depth = %d",
			    device_iterator_name(di), di->dvi_depth);

		CURCLD(di) = TAILQ_FIRST(&dv->dv_child_list);
	}

	return (dv);
}

/*
 * device_iterator_foreach_postorder: 			[internal]
 *
 * 	Iterate devices so that "children" go before their "parents".
 * 	In other words, device is processed as soon as _all_ of its
 * 	children are processed (recursively).
 */
static device_t
device_iterator_foreach_postorder(deviter_t di)
{
	devchild_t 		dc;
	device_t 		dv;

	/* We're done when we've finished all layers. */
	if (di->dvi_index == -1)
		return (NULL);

 descend:
	dc = CURCLD(di);

	/* Subtree finished in past step, handle its root and unwind. */
	if (dc == NULL) {
		dv = CURPAR(di);
		di->dvi_index--; 	/* underflow is ok */

		return (dv);
	}

	/* Get ready for next child at this level. */
	CURCLD(di) = TAILQ_NEXT(dc, dvc_list);
	dv = dc->dvc_device;

	/* Descend until we see a leaf device. */
	if (! TAILQ_EMPTY(&dv->dv_child_list)) {
		if (device_iterator_descend(di))
			panic("device_iterator_foreach_postorder: %s devstack "
			    "overflow, depth = %d",
			    device_iterator_name(di), di->dvi_depth);

		CURCLD(di) = TAILQ_FIRST(&dv->dv_child_list);
		CURPAR(di) = dv;

		goto descend;
	}

	return (dv);
}

--UlVJffcvxoiEqYs2--