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--