Subject: device tree traversal
To: None <tech-kern@netbsd.org>
From: Jachym Holecek <freza@dspfpga.com>
List: tech-kern
Date: 07/02/2006 21:17:50
--LZvS9be/3tNcYl/X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hello,

below is an implementation of device tree iterator API. This will be
needed for proper powerhooks, recursive drvctl(8) detach and possibly
config_{de,}activate could benefit too. The usage is quite simple:

	deviter_t 		di;
	device_t 		dv;

	/* Allocate recursion context of max depth 16, topdown dir. */
	di = device_iterator_alloc(16, DIF_WAITOK | DIF_TOPDOWN);
	if (di == NULL)
		handle_enomem();

	/* Setup to traverse (device_t)parent's subtree. */
	device_iterator_init(di, parent);

	while ((dv = device_iterator_foreach(di)) != NULL)
		perform_stuff_on_device(dv);

	/* Free the context. */
	device_iterator_free(di);

There are two possible iterator types: DIF_TOPDOWN will handle
parents before their children, DIF_DOWNTOP will handle children before
their parents. The attached files give a concrete example -- given
device hierarchy devtree.dot (graphics/graphviz format), topdown
pass on "mainbus0" yields devtree.topdown while downtop pass gives
devtree.downtop.

Comments? Would it be OK to commit?

	-- Jachym

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	2 Jul 2006 18:48:21 -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 */
+#define	DIF_WAITOK 		0x00 		/* default */
+#define	DIF_TOPDOWN 		0x00 		/* default */
+#define	DIF_NOWAIT 		0x01
+#define	DIF_DOWNTOP 		0x02
+
 /*
  * 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(int, int);
+void 		device_iterator_free(deviter_t);
+void 		device_iterator_init(deviter_t, device_t);
+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: 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	2 Jul 2006 18:48:26 -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 cftable), 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);
+}
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	2 Jul 2006 18:48:27 -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
--- /dev/null	2006-07-02 20:39:33.000000000 +0200
+++ kern/subr_devtree.c	2006-07-02 20:35:55.000000000 +0200
@@ -0,0 +1,189 @@
+/* $NetBSD$ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD$");
+
+#include "opt_ddb.h"
+
+#include <sys/param.h>
+#include <sys/device.h>
+#include <sys/malloc.h>
+#include <sys/queue.h>
+#include <sys/types.h>
+
+
+struct deviter {
+	int 			dvi_flags;
+	int 			dvi_depth;
+	int 			dvi_index; 	/* current entry */
+	device_t 		dvi_root; 	/* root of subtree */
+	devchild_t 		*dvi_child;
+	device_t 		*dvi_parent; 	/* only for downtop pass */
+};
+
+#define	CURCLD(di) 		(di)->dvi_child[(di)->dvi_index]
+#define	CURPAR(di) 		(di)->dvi_parent[(di)->dvi_index]
+
+/* dvi_flags bits, DIF_* from <sys/device.h> and internal below */
+#define	DIF_FIRST 		0x80
+
+
+static device_t device_iterator_foreach_topdown(deviter_t);
+static device_t device_iterator_foreach_downtop(deviter_t);
+
+
+deviter_t
+device_iterator_alloc(int count, int flags)
+{
+	deviter_t 		di;
+	int 			mflags;
+
+	mflags = (flags & DIF_NOWAIT) ? M_NOWAIT : M_WAITOK;
+
+	di = (deviter_t)malloc(sizeof(struct deviter), M_DEVBUF, mflags);
+	if (di == NULL)
+		return (NULL);
+
+	/* We need the child stack in any case. */
+	di->dvi_child = (devchild_t *)malloc(count * sizeof(devchild_t),
+	    M_DEVBUF, mflags);
+	if (di->dvi_child == NULL)
+		goto fail_0;
+
+	/* But parents are only needed for downtop iterators. */
+	if (ISSET(flags, DIF_DOWNTOP)) {
+		di->dvi_parent = (device_t *)malloc(count * sizeof(device_t),
+		    M_DEVBUF, mflags);
+		if (di->dvi_parent == NULL)
+			goto fail_1;
+	} else
+		di->dvi_parent = NULL;
+
+	di->dvi_flags = flags;
+	di->dvi_depth = count;
+	di->dvi_index = 0;
+	di->dvi_root = NULL;
+
+	return (di);
+
+ fail_1:
+	free(di->dvi_child, M_DEVBUF);
+ fail_0:
+	free(di, M_DEVBUF);
+	return (NULL);
+}
+
+void
+device_iterator_free(deviter_t di)
+{
+	KASSERT(di != NULL);
+	KASSERT(di->dvi_child != NULL);
+
+	if (di->dvi_parent != NULL)
+		free(di->dvi_parent, M_DEVBUF);
+	free(di->dvi_child, M_DEVBUF);
+	free(di, M_DEVBUF);
+}
+
+void
+device_iterator_init(deviter_t di, device_t dev)
+{
+	KASSERT(di->dvi_depth > 0);
+	KASSERT(di->dvi_child != NULL);
+
+	SET(di->dvi_flags, DIF_FIRST);
+	di->dvi_root = dev;
+	di->dvi_index = 0;
+	di->dvi_child[0] = TAILQ_FIRST(&dev->dv_child_list);
+
+	if (ISSET(di->dvi_flags, DIF_DOWNTOP))
+		di->dvi_parent[0] = dev;
+}
+
+device_t
+device_iterator_foreach(deviter_t di)
+{
+	if (ISSET(di->dvi_flags, DIF_DOWNTOP))
+		return (device_iterator_foreach_downtop(di));
+	else
+		return (device_iterator_foreach_topdown(di));
+}
+
+static device_t
+device_iterator_foreach_topdown(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 (++di->dvi_index == di->dvi_depth)
+			panic("config_rootleaf_next: %s devstack "
+			    "overflow, depth = %d",
+			    device_xname(di->dvi_root), di->dvi_depth);
+
+		CURCLD(di) = TAILQ_FIRST(&dv->dv_child_list);
+	}
+
+	return (dv);
+}
+
+static device_t
+device_iterator_foreach_downtop(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 (++di->dvi_index == di->dvi_depth)
+			panic("device_foreach_downtop: %s devstack "
+			    "overflow, depth = %d",
+			    device_xname(di->dvi_root), di->dvi_depth);
+
+		CURCLD(di) = TAILQ_FIRST(&dv->dv_child_list);
+		CURPAR(di) = dv;
+
+		goto descend;
+	}
+
+	return (dv);
+}

--LZvS9be/3tNcYl/X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="devtree.dot"

strict graph hanele {
	cpu0 -- mainbus0 ;
	acpi0 -- mainbus0 ;
	acpilid0 -- acpi0 ;
	acpibut0 -- acpi0 ;
	attimer0 -- acpi0 ;
	npx0 -- acpi0 ;
	pckbc0 -- acpi0 ;
	pckbc1 -- acpi0 ;
	lpt0 -- acpi0 ;
	acpiec0 -- acpi0 ;
	acpibat0 -- acpi0 ;
	acpiacad0 -- acpi0 ;
	acpitz0 -- acpi0 ;
	pckbd0 -- pckbc0 ;
	wskbd0 -- pckbd0 ;
	pms0 -- pckbc0 ;
	wsmouse0 -- pms0 ;
	pci0 -- mainbus0 ;
	pchb0 -- pci0 ;
	agp0 -- pchb0 ;
	vga0 -- pci0 ;
	wsdisplay0 -- vga0 ;
	uhci0 -- pci0 ;
	usb0 -- uhci0 ;
	uhub0 -- usb0 ;
	uhci1 -- pci0 ;
	usb1 -- uhci1 ;
	uhub1 -- usb1 ;
	uhci2 -- pci0 ;
	usb2 -- uhci2 ;
	uhub2 -- usb2 ;
	ehci0 -- pci0 ;
	usb3 -- ehci0 ;
	uhub3 -- usb3 ;
	ppb0 -- pci0 ;
	pci1 -- ppb0 ;
	cbb0 -- pci1 ;
	iwi0 -- pci1 ;
	fxp0 -- pci1 ;
	inphy0 -- fxp0 ;
	cardslot0 -- cbb0 ;
	cardbus0 -- cardslot0 ;
	pcmcia0 -- cardslot0 ;
	ichlpcib0 -- pci0 ;
	piixide0 -- pci0 ;
	atabus0 -- piixide0 ;
	atabus1 -- piixide0 ;
	auich0 -- pci0 ;
	audio0 -- auich0 ;
	wd0 -- atabus0 ;
	atapibus0 -- atabus1 ;
	cd0 -- atapibus0 ;
}

--LZvS9be/3tNcYl/X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="devtree.downtop"

     1	cpu0
     2	acpilid0
     3	acpibut0
     4	attimer0
     5	npx0
     6	wskbd0
     7	pckbd0
     8	wsmouse0
     9	pms0
    10	pckbc0
    11	pckbc1
    12	lpt0
    13	acpiec0
    14	acpibat0
    15	acpiacad0
    16	acpitz0
    17	acpi0
    18	agp0
    19	pchb0
    20	wsdisplay0
    21	vga0
    22	uhub0
    23	usb0
    24	uhci0
    25	uhub1
    26	usb1
    27	uhci1
    28	uhub2
    29	usb2
    30	uhci2
    31	uhub3
    32	usb3
    33	ehci0
    34	cardbus0
    35	pcmcia0
    36	cardslot0
    37	cbb0
    38	iwi0
    39	inphy0
    40	fxp0
    41	pci1
    42	ppb0
    43	ichlpcib0
    44	wd0
    45	atabus0
    46	cd0
    47	atapibus0
    48	atabus1
    49	piixide0
    50	audio0
    51	auich0
    52	pci0
    53	mainbus0

--LZvS9be/3tNcYl/X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="devtree.topdown"

     1	mainbus0
     2	cpu0
     3	acpi0
     4	acpilid0
     5	acpibut0
     6	attimer0
     7	npx0
     8	pckbc0
     9	pckbd0
    10	wskbd0
    11	pms0
    12	wsmouse0
    13	pckbc1
    14	lpt0
    15	acpiec0
    16	acpibat0
    17	acpiacad0
    18	acpitz0
    19	pci0
    20	pchb0
    21	agp0
    22	vga0
    23	wsdisplay0
    24	uhci0
    25	usb0
    26	uhub0
    27	uhci1
    28	usb1
    29	uhub1
    30	uhci2
    31	usb2
    32	uhub2
    33	ehci0
    34	usb3
    35	uhub3
    36	ppb0
    37	pci1
    38	cbb0
    39	cardslot0
    40	cardbus0
    41	pcmcia0
    42	iwi0
    43	fxp0
    44	inphy0
    45	ichlpcib0
    46	piixide0
    47	atabus0
    48	wd0
    49	atabus1
    50	atapibus0
    51	cd0
    52	auich0
    53	audio0

--LZvS9be/3tNcYl/X--