util/sconfig: Re-factor device structure in parse tree

This change re-factors the device structure in parse tree to be able
to support multidev devices just like non-multidev devices.

With this change, every device has a bus under it which is the parent
of all devices that fall on the bus. If there are duplicate entries in
the devicetree, then there will be multiple buses under the device and
each bus will have its own set of children.

The tree starts out with a root device which has a root bus under
it. This is a special device which is created statically and its
parent is its own root bus. When parsing the device tree file, devices
get added under the root bus as children.

Since this change re-organizes the way devicetree is represented, it
gets rid of latestchild and next_sibling pointers from struct
device. Also, the tree traversal to generate static.c is changed to
breadth-first walk instead of using the next_sibling.

BUG=b:80081934
TEST=Verified using abuild that all boards compile successfully.

Change-Id: Ic8c8a73a247e8e992ab6b1b2cc3131e06fa2e5a1
Signed-off-by: Furquan Shaikh <furquan@google.com>
Reviewed-on: https://review.coreboot.org/26800
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Aaron Durbin <adurbin@chromium.org>

5 files changed, 410 insertions, 300 deletions

diff --git a/util/sconfig/main.c b/util/sconfig/main.c
index 188e7f93a2..a3c77eb135 100644
--- a/util/sconfig/main.c
+++ b/util/sconfig/main.c
@@ -20,8 +20,6 @@
 
 extern int linenum;
 
-struct device *head, *lastnode;
-
 static struct chip chip_header;
 
 /*
@@ -37,10 +35,64 @@ typedef enum {
 	TO_UPPER,
 } translate_t;
 
-static struct device root;
-
+/*
+ * Mainboard is assumed to have a root device whose bus is the parent of all the
+ * devices that are added by parsing the devicetree file. This device has a
+ * mainboard chip instance associated with it.
+ *
+ *
+ *
+ *                 +------------------------+                +----------------------+
+ *                 |                        |                |  Mainboard           |
+ *       +---------+ Root device (root_dev) +--------------->+  instance            +
+ *       |         |                        | chip_instance  |  (mainboard_instance)|
+ *       |         +------------------------+                |                      |
+ *       |                      |                            +----------------------+
+ *       |                      | bus                                  |
+ *       | parent               v                                      |
+ *       |            +-------------------+                            |
+ *       |            |     Root bus      |                            |
+ *       +----------->+    (root_bus)     |                            |
+ *                    |                   |                            |
+ *                    +-------------------+                            |
+ *                              |                                      |
+ *                              | children                             | chip
+ *                              v                                      |
+ *                              X                                      |
+ *                        (new devices will                            |
+ *                         be added here as                            |
+ *                         children)                                   |
+ *                                                                     |
+ *                                                                     |
+ *                                                                     |
+ *                                                             +-------+----------+
+ *                                                             |                  |
+ *                                                             |  Mainboard chip  +----------->X (new chips will be
+ *                                                             | (mainboard_chip) |               added here)
+ *                                                             |                  |
+ *                                                             +------------------+
+ *
+ *
+ */
+static struct device root_dev;
 static struct chip_instance mainboard_instance;
 
+static struct bus root_bus = {
+	.id = 0,
+	.dev = &root_dev,
+};
+
+static struct device root_dev = {
+	.name = "dev_root",
+	.id = 0,
+	.chip_instance = &mainboard_instance,
+	.path = " .type = DEVICE_PATH_ROOT ",
+	.ops = "&default_dev_ops_root",
+	.parent = &root_bus,
+	.enabled = 1,
+	.bus = &root_bus,
+};
+
 static struct chip mainboard_chip = {
 	.name = "mainboard",
 	.name_underscore = "mainboard",
@@ -52,15 +104,8 @@ static struct chip_instance mainboard_instance = {
 	.chip = &mainboard_chip,
 };
 
-static struct device root = {
-	.name = "dev_root",
-	.id = 0,
-	.chip_instance = &mainboard_instance,
-	.path = " .type = DEVICE_PATH_ROOT ",
-	.ops = "&default_dev_ops_root",
-	.parent = &root,
-	.enabled = 1
-};
+/* This is the parent of all devices added by parsing the devicetree file. */
+struct bus *root_parent = &root_bus;
 
 struct queue_entry {
 	void *data;
@@ -172,42 +217,6 @@ void *chip_dequeue_tail(void)
 	return dequeue_tail(&chip_q_head);
 }
 
-static struct device *new_dev(struct device *parent)
-{
-	struct device *dev = S_ALLOC(sizeof(struct device));
-
-	dev->id = ++count;
-	dev->parent = parent;
-	dev->subsystem_vendor = -1;
-	dev->subsystem_device = -1;
-	head->next = dev;
-	head = dev;
-	return dev;
-}
-
-static int device_match(struct device *a, struct device *b)
-{
-	if ((a->bustype == b->bustype) && (a->parent == b->parent)
-	    && (a->path_a == b->path_a) && (a->path_b == b->path_b))
-		return 1;
-	return 0;
-}
-
-void fold_in(struct device *parent)
-{
-	struct device *child = parent->children;
-	struct device *latest = 0;
-	while (child != latest) {
-		if (child->children) {
-			if (!latest)
-				latest = child->children;
-			parent->latestchild->next_sibling = child->children;
-			parent->latestchild = child->latestchild;
-		}
-		child = child->next_sibling;
-	}
-}
-
 int yywrap(void)
 {
 	return 1;
@@ -220,28 +229,6 @@ void yyerror(char const *str)
 	exit(1);
 }
 
-void postprocess_devtree(void)
-{
-	root.next_sibling = root.children;
-
-	/*
-	 * Since root is statically created we need to call fold_in explicitly
-	 * here to have the next_sibling and latestchild setup correctly.
-	 */
-	fold_in(&root);
-
-	struct device *dev = &root;
-	while (dev) {
-		/* skip functions of the same device in sibling chain */
-		while (dev->sibling && dev->sibling->used)
-			dev->sibling = dev->sibling->sibling;
-		/* skip duplicate function elements in next chain */
-		while (dev->next && dev->next->used)
-			dev->next = dev->next->next;
-		dev = dev->next_sibling;
-	}
-}
-
 char *translate_name(const char *str, translate_t mode)
 {
 	char *b, *c;
@@ -324,21 +311,104 @@ struct chip_instance *new_chip_instance(char *path)
 	return instance;
 }
 
-struct device *new_device(struct device *parent,
+/*
+ * Allocate a new bus for the provided device.
+ *   - If this is the first bus being allocated under this device, then its id
+ *     is set to 0 and bus and last_bus are pointed to the newly allocated bus.
+ *   - If this is not the first bus under this device, then its id is set to 1
+ *     plus the id of last bus and newly allocated bus is added to the list of
+ *     buses under the device. last_bus is updated to point to the newly
+ *     allocated bus.
+ */
+static void alloc_bus(struct device *dev)
+{
+	struct bus *bus = S_ALLOC(sizeof(*bus));
+
+	bus->dev = dev;
+
+	if (dev->last_bus == NULL)  {
+		bus->id = 0;
+		dev->bus = bus;
+	} else {
+		bus->id = dev->last_bus->id + 1;
+		dev->last_bus->next_bus = bus;
+	}
+
+	dev->last_bus = bus;
+}
+
+/*
+ * Allocate a new device under the given parent. This function allocates a new
+ * device structure under the provided parent bus and allocates a bus structure
+ * under the newly allocated device.
+ */
+static struct device *alloc_dev(struct bus *parent)
+{
+	struct device *dev = S_ALLOC(sizeof(*dev));
+
+	dev->id = ++count;
+	dev->parent = parent;
+	dev->subsystem_vendor = -1;
+	dev->subsystem_device = -1;
+
+	alloc_bus(dev);
+
+	return dev;
+}
+
+/*
+ * This function scans the children of given bus to see if any device matches
+ * the new device that is requested.
+ *
+ * Returns pointer to the node if found, else NULL.
+ */
+static struct device *get_dev(struct bus *parent, int path_a, int path_b,
+			      int bustype, struct chip_instance *chip_instance)
+{
+	struct device *child = parent->children;
+
+	while (child) {
+		if ((child->path_a == path_a) && (child->path_b == path_b) &&
+		    (child->bustype == bustype) &&
+		    (child->chip_instance == chip_instance))
+			return child;
+
+		child = child->sibling;
+	}
+
+	return NULL;
+}
+
+struct device *new_device(struct bus *parent,
 			  struct chip_instance *chip_instance,
 			  const int bustype, const char *devnum,
 			  int enabled)
 {
-	struct device *new_d = new_dev(parent);
-	new_d->bustype = bustype;
-
 	char *tmp;
-	new_d->path_a = strtol(devnum, &tmp, 16);
+	int path_a;
+	int path_b = 0;
+	struct device *new_d;
+
+	path_a = strtol(devnum, &tmp, 16);
 	if (*tmp == '.') {
 		tmp++;
-		new_d->path_b = strtol(tmp, NULL, 16);
+		path_b = strtol(tmp, NULL, 16);
+	}
+
+	/* If device is found under parent, no need to allocate new device. */
+	new_d = get_dev(parent, path_a, path_b, bustype, chip_instance);
+	if (new_d) {
+		alloc_bus(new_d);
+		return new_d;
 	}
 
+	new_d = alloc_dev(parent);
+
+	new_d->bustype = bustype;
+
+	new_d->path_a = path_a;
+	new_d->path_b = path_b;
+
 	char *name = S_ALLOC(10);
 	sprintf(name, "_dev%d", new_d->id);
 	new_d->name = name;
@@ -346,17 +416,14 @@ struct device *new_device(struct device *parent,
 	new_d->enabled = enabled;
 	new_d->chip_instance = chip_instance;
 
-	if (parent->latestchild) {
-		parent->latestchild->next_sibling = new_d;
-		parent->latestchild->sibling = new_d;
-	}
-	parent->latestchild = new_d;
-	if (!parent->children)
+	struct device *c = parent->children;
+	if (c) {
+		while (c->sibling)
+			c = c->sibling;
+		c->sibling = new_d;
+	} else
 		parent->children = new_d;
 
-	lastnode->next = new_d;
-	lastnode = new_d;
-
 	switch (bustype) {
 	case PCI:
 		new_d->path = ".type=DEVICE_PATH_PCI,{.pci={ .devfn = PCI_DEVFN(0x%x,%d)}}";
@@ -410,31 +477,9 @@ struct device *new_device(struct device *parent,
 	return new_d;
 }
 
-void alias_siblings(struct device *d)
-{
-	while (d) {
-		int link = 0;
-		struct device *cmp = d->next_sibling;
-		while (cmp && (cmp->parent == d->parent) && (cmp->path_a == d->path_a)
-		       && (cmp->path_b == d->path_b)) {
-			if (!cmp->used) {
-				if (device_match(d, cmp)) {
-					d->multidev = 1;
-
-					cmp->id = d->id;
-					cmp->name = d->name;
-					cmp->used = 1;
-					cmp->link = ++link;
-				}
-			}
-			cmp = cmp->next_sibling;
-		}
-		d = d->next_sibling;
-	}
-}
-
-void add_resource(struct device *dev, int type, int index, int base)
+void add_resource(struct bus *bus, int type, int index, int base)
 {
+	struct device *dev = bus->dev;
 	struct resource *r = S_ALLOC(sizeof(struct resource));
 
 	r->type = type;
@@ -480,9 +525,11 @@ void add_register(struct chip_instance *chip_instance, char *name, char *val)
 	}
 }
 
-void add_pci_subsystem_ids(struct device *dev, int vendor, int device,
+void add_pci_subsystem_ids(struct bus *bus, int vendor, int device,
 			   int inherit)
 {
+	struct device *dev = bus->dev;
+
 	if (dev->bustype != PCI && dev->bustype != DOMAIN) {
 		printf("ERROR: 'subsystem' only allowed for PCI devices\n");
 		exit(1);
@@ -493,11 +540,11 @@ void add_pci_subsystem_ids(struct device *dev, int vendor, int device,
 	dev->inherit_subsystem = inherit;
 }
 
-void add_ioapic_info(struct device *dev, int apicid, const char *_srcpin,
+void add_ioapic_info(struct bus *bus, int apicid, const char *_srcpin,
 		     int irqpin)
 {
-
 	int srcpin;
+	struct device *dev = bus->dev;
 
 	if (!_srcpin || strlen(_srcpin) < 4 || strncasecmp(_srcpin, "INT", 3) ||
 	    _srcpin[3] < 'A' || _srcpin[3] > 'D') {
@@ -520,163 +567,206 @@ void add_ioapic_info(struct device *dev, int apicid, const char *_srcpin,
 	dev->pci_irq_info[srcpin].ioapic_dst_id = apicid;
 }
 
-static void pass0(FILE *fil, struct device *ptr)
+static int dev_has_children(struct device *dev)
 {
-	if (ptr->id == 0)
+	struct bus *bus = dev->bus;
+
+	while (bus) {
+		if (bus->children)
+			return 1;
+		bus = bus->next_bus;
+	}
+
+	return 0;
+}
+
+static void pass0(FILE *fil, struct device *ptr, struct device *next)
+{
+	if (ptr == &root_dev) {
 		fprintf(fil, "DEVTREE_CONST struct bus %s_links[];\n",
 			ptr->name);
+		return;
+	}
 
-	if ((ptr->id != 0) && (!ptr->used)) {
-		fprintf(fil, "DEVTREE_CONST static struct device %s;\n",
+	fprintf(fil, "DEVTREE_CONST static struct device %s;\n", ptr->name);
+	if (ptr->rescnt > 0)
+		fprintf(fil, "DEVTREE_CONST struct resource %s_res[];\n",
 			ptr->name);
-		if (ptr->rescnt > 0)
-			fprintf(fil,
-				"DEVTREE_CONST struct resource %s_res[];\n",
-				ptr->name);
-		if (ptr->children || ptr->multidev)
-			fprintf(fil, "DEVTREE_CONST struct bus %s_links[];\n",
-				ptr->name);
+	if (dev_has_children(ptr))
+		fprintf(fil, "DEVTREE_CONST struct bus %s_links[];\n",
+			ptr->name);
+
+	if (next)
+		return;
+
+	fprintf(fil,
+		"DEVTREE_CONST struct device * DEVTREE_CONST last_dev = &%s;\n",
+		ptr->name);
+}
+
+static void emit_resources(FILE *fil, struct device *ptr)
+{
+	if (ptr->rescnt == 0)
+		return;
+
+	int i = 1;
+	fprintf(fil, "DEVTREE_CONST struct resource %s_res[] = {\n", ptr->name);
+	struct resource *r = ptr->res;
+	while (r) {
+		fprintf(fil,
+			"\t\t{ .flags=IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_");
+		if (r->type == IRQ)
+			fprintf(fil, "IRQ");
+		if (r->type == DRQ)
+			fprintf(fil, "DRQ");
+		if (r->type == IO)
+			fprintf(fil, "IO");
+		fprintf(fil, ", .index=0x%x, .base=0x%x,", r->index,
+			r->base);
+		if (r->next)
+			fprintf(fil, ".next=&%s_res[%d]},\n", ptr->name,
+				i++);
+		else
+			fprintf(fil, ".next=NULL },\n");
+		r = r->next;
+	}
+
+	fprintf(fil, "\t };\n");
+}
+
+static void emit_bus(FILE *fil, struct bus *bus)
+{
+	fprintf(fil, "\t\t[%d] = {\n", bus->id);
+	fprintf(fil, "\t\t\t.link_num = %d,\n", bus->id);
+	fprintf(fil, "\t\t\t.dev = &%s,\n", bus->dev->name);
+	if (bus->children)
+		fprintf(fil, "\t\t\t.children = &%s,\n", bus->children->name);
+
+	if (bus->next_bus)
+		fprintf(fil, "\t\t\t.next=&%s_links[%d],\n", bus->dev->name,
+			bus->id + 1);
+	else
+		fprintf(fil, "\t\t\t.next = NULL,\n");
+	fprintf(fil, "\t\t},\n");
+}
+
+static void emit_dev_links(FILE *fil, struct device *ptr)
+{
+	fprintf(fil, "DEVTREE_CONST struct bus %s_links[] = {\n",
+		ptr->name);
+
+	struct bus *bus = ptr->bus;
+
+	while (bus) {
+		emit_bus(fil, bus);
+		bus = bus->next_bus;
 	}
+
+	fprintf(fil, "\t};\n");
 }
 
-static void pass1(FILE *fil, struct device *ptr)
+static void pass1(FILE *fil, struct device *ptr, struct device *next)
 {
 	int pin;
 	struct chip_instance *chip_ins = ptr->chip_instance;
+	int has_children = dev_has_children(ptr);
 
-	if (!ptr->used) {
-		if (ptr->id != 0)
-			fprintf(fil, "static ");
-		fprintf(fil, "DEVTREE_CONST struct device %s = {\n",
-			ptr->name);
-		fprintf(fil, "#if !DEVTREE_EARLY\n");
-		fprintf(fil, "\t.ops = %s,\n", (ptr->ops) ? (ptr->ops) : "0");
-		fprintf(fil, "#endif\n");
-		fprintf(fil, "\t.bus = &%s_links[%d],\n", ptr->parent->name,
-			ptr->parent->link);
-		fprintf(fil, "\t.path = {");
-		fprintf(fil, ptr->path, ptr->path_a, ptr->path_b);
-		fprintf(fil, "},\n");
-		fprintf(fil, "\t.enabled = %d,\n", ptr->enabled);
-		fprintf(fil, "\t.on_mainboard = 1,\n");
-		if (ptr->subsystem_vendor > 0)
-			fprintf(fil, "\t.subsystem_vendor = 0x%04x,\n",
-				ptr->subsystem_vendor);
-
-		for (pin = 0; pin < 4; pin++) {
-			if (ptr->pci_irq_info[pin].ioapic_irq_pin > 0)
-				fprintf(fil, "\t.pci_irq_info[%d].ioapic_irq_pin = %d,\n",
-					pin, ptr->pci_irq_info[pin].ioapic_irq_pin);
-
-			if (ptr->pci_irq_info[pin].ioapic_dst_id > 0)
-				fprintf(fil, "\t.pci_irq_info[%d].ioapic_dst_id = %d,\n",
-					pin, ptr->pci_irq_info[pin].ioapic_dst_id);
-		}
-
-		if (ptr->subsystem_device > 0)
-			fprintf(fil, "\t.subsystem_device = 0x%04x,\n",
-				ptr->subsystem_device);
+	if (ptr != &root_dev)
+		fprintf(fil, "static ");
+	fprintf(fil, "DEVTREE_CONST struct device %s = {\n", ptr->name);
+	fprintf(fil, "#if !DEVTREE_EARLY\n");
+	fprintf(fil, "\t.ops = %s,\n", (ptr->ops) ? (ptr->ops) : "0");
+	fprintf(fil, "#endif\n");
+	fprintf(fil, "\t.bus = &%s_links[%d],\n", ptr->parent->dev->name,
+		ptr->parent->id);
+	fprintf(fil, "\t.path = {");
+	fprintf(fil, ptr->path, ptr->path_a, ptr->path_b);
+	fprintf(fil, "},\n");
+	fprintf(fil, "\t.enabled = %d,\n", ptr->enabled);
+	fprintf(fil, "\t.on_mainboard = 1,\n");
+	if (ptr->subsystem_vendor > 0)
+		fprintf(fil, "\t.subsystem_vendor = 0x%04x,\n",
+			ptr->subsystem_vendor);
+
+	for (pin = 0; pin < 4; pin++) {
+		if (ptr->pci_irq_info[pin].ioapic_irq_pin > 0)
+			fprintf(fil,
+				"\t.pci_irq_info[%d].ioapic_irq_pin = %d,\n",
+				pin, ptr->pci_irq_info[pin].ioapic_irq_pin);
 
-		if (ptr->rescnt > 0) {
-			fprintf(fil, "\t.resource_list = &%s_res[0],\n",
-				ptr->name);
-		}
-		if (ptr->children || ptr->multidev)
-			fprintf(fil, "\t.link_list = &%s_links[0],\n",
-				ptr->name);
-		else
-			fprintf(fil, "\t.link_list = NULL,\n");
-		if (ptr->sibling)
-			fprintf(fil, "\t.sibling = &%s,\n", ptr->sibling->name);
-		fprintf(fil, "#if !DEVTREE_EARLY\n");
-		fprintf(fil, "\t.chip_ops = &%s_ops,\n",
-			chip_ins->chip->name_underscore);
-		if (chip_ins == &mainboard_instance)
-			fprintf(fil, "\t.name = mainboard_name,\n");
-		fprintf(fil, "#endif\n");
-		if (chip_ins->chip->chiph_exists)
-			fprintf(fil, "\t.chip_info = &%s_info_%d,\n",
-				chip_ins->chip->name_underscore, chip_ins->id);
-		if (ptr->next)
-			fprintf(fil, "\t.next=&%s\n", ptr->next->name);
-		fprintf(fil, "};\n");
+		if (ptr->pci_irq_info[pin].ioapic_dst_id > 0)
+			fprintf(fil,
+				"\t.pci_irq_info[%d].ioapic_dst_id = %d,\n",
+				pin, ptr->pci_irq_info[pin].ioapic_dst_id);
 	}
+
+	if (ptr->subsystem_device > 0)
+		fprintf(fil, "\t.subsystem_device = 0x%04x,\n",
+			ptr->subsystem_device);
+
 	if (ptr->rescnt > 0) {
-		int i = 1;
-		fprintf(fil, "DEVTREE_CONST struct resource %s_res[] = {\n",
+		fprintf(fil, "\t.resource_list = &%s_res[0],\n",
 			ptr->name);
-		struct resource *r = ptr->res;
-		while (r) {
-			fprintf(fil,
-				"\t\t{ .flags=IORESOURCE_FIXED | IORESOURCE_ASSIGNED | IORESOURCE_");
-			if (r->type == IRQ)
-				fprintf(fil, "IRQ");
-			if (r->type == DRQ)
-				fprintf(fil, "DRQ");
-			if (r->type == IO)
-				fprintf(fil, "IO");
-			fprintf(fil, ", .index=0x%x, .base=0x%x,", r->index,
-				r->base);
-			if (r->next)
-				fprintf(fil, ".next=&%s_res[%d]},\n", ptr->name,
-					i++);
-			else
-				fprintf(fil, ".next=NULL },\n");
-			r = r->next;
-		}
-		fprintf(fil, "\t };\n");
 	}
-	if (!ptr->used && (ptr->children || ptr->multidev)) {
-		fprintf(fil, "DEVTREE_CONST struct bus %s_links[] = {\n",
+	if (has_children)
+		fprintf(fil, "\t.link_list = &%s_links[0],\n",
 			ptr->name);
-		if (ptr->multidev) {
-			struct device *d = ptr;
-			while (d) {
-				if (device_match(d, ptr)) {
-					fprintf(fil, "\t\t[%d] = {\n", d->link);
-					fprintf(fil, "\t\t\t.link_num = %d,\n",
-						d->link);
-					fprintf(fil, "\t\t\t.dev = &%s,\n",
-						d->name);
-					if (d->children)
-						fprintf(fil,
-							"\t\t\t.children = &%s,\n",
-							d->children->name);
-					if (d->next_sibling
-					    && device_match(d->next_sibling,
-							    ptr))
-						fprintf(fil,
-							"\t\t\t.next=&%s_links[%d],\n",
-							d->name, d->link + 1);
-					else
-						fprintf(fil,
-							"\t\t\t.next = NULL,\n");
-					fprintf(fil, "\t\t},\n");
-				}
-				d = d->next_sibling;
-			}
-		} else {
-			if (ptr->children) {
-				fprintf(fil, "\t\t[0] = {\n");
-				fprintf(fil, "\t\t\t.link_num = 0,\n");
-				fprintf(fil, "\t\t\t.dev = &%s,\n", ptr->name);
-				fprintf(fil, "\t\t\t.children = &%s,\n",
-					ptr->children->name);
-				fprintf(fil, "\t\t\t.next = NULL,\n");
-				fprintf(fil, "\t\t},\n");
-			}
-		}
-		fprintf(fil, "\t};\n");
+	else
+		fprintf(fil, "\t.link_list = NULL,\n");
+	if (ptr->sibling)
+		fprintf(fil, "\t.sibling = &%s,\n", ptr->sibling->name);
+	fprintf(fil, "#if !DEVTREE_EARLY\n");
+	fprintf(fil, "\t.chip_ops = &%s_ops,\n",
+		chip_ins->chip->name_underscore);
+	if (chip_ins == &mainboard_instance)
+		fprintf(fil, "\t.name = mainboard_name,\n");
+	fprintf(fil, "#endif\n");
+	if (chip_ins->chip->chiph_exists)
+		fprintf(fil, "\t.chip_info = &%s_info_%d,\n",
+			chip_ins->chip->name_underscore, chip_ins->id);
+	if (next)
+		fprintf(fil, "\t.next=&%s\n", next->name);
+	fprintf(fil, "};\n");
+
+	emit_resources(fil, ptr);
+
+	if (has_children)
+		emit_dev_links(fil, ptr);
+}
+
+static void add_siblings_to_queue(struct queue_entry **bfs_q_head,
+				  struct device *d)
+{
+	while (d) {
+		enqueue_tail(bfs_q_head, d);
+		d = d->sibling;
+	}
+}
+
+static void add_children_to_queue(struct queue_entry **bfs_q_head,
+				  struct device *d)
+{
+	struct bus *bus = d->bus;
+
+	while (bus) {
+		if (bus->children)
+			add_siblings_to_queue(bfs_q_head, bus->children);
+		bus = bus->next_bus;
 	}
 }
 
 static void walk_device_tree(FILE *fil, struct device *ptr,
-			     void (*func)(FILE *, struct device *))
+			     void (*func)(FILE *, struct device *,
+					  struct device *))
 {
-	do {
-		func(fil, ptr);
-		ptr = ptr->next_sibling;
-	} while (ptr);
+	struct queue_entry *bfs_q_head = NULL;
+
+	enqueue_tail(&bfs_q_head, ptr);
+
+	while ((ptr = dequeue_head(&bfs_q_head))) {
+		add_children_to_queue(&bfs_q_head, ptr);
+		func(fil, ptr, peek_queue_head(bfs_q_head));
+	}
 }
 
 static void emit_chip_headers(FILE *fil, struct chip *chip)
@@ -742,7 +832,8 @@ static void emit_chips(FILE *fil)
 	}
 }
 
-static void inherit_subsystem_ids(FILE *file, struct device *dev)
+static void inherit_subsystem_ids(FILE *file, struct device *dev,
+				  struct device *next)
 {
 	struct device *p;
 
@@ -751,7 +842,7 @@ static void inherit_subsystem_ids(FILE *file, struct device *dev)
 		return;
 	}
 
-	for (p = dev; p && p != p->parent; p = p->parent) {
+	for (p = dev; p && p->parent->dev != p; p = p->parent->dev) {
 
 		if (p->bustype != PCI && p->bustype != DOMAIN)
 			continue;
@@ -793,8 +884,6 @@ int main(int argc, char **argv)
 
 	yyrestart(filec);
 
-	lastnode = head = &root;
-
 	yyparse();
 
 	fclose(filec);
@@ -809,13 +898,11 @@ int main(int argc, char **argv)
 
 	emit_chips(autogen);
 
-	walk_device_tree(autogen, &root, inherit_subsystem_ids);
+	walk_device_tree(autogen, &root_dev, inherit_subsystem_ids);
 	fprintf(autogen, "\n/* pass 0 */\n");
-	walk_device_tree(autogen, &root, pass0);
-	fprintf(autogen, "\n/* pass 1 */\n"
-		"DEVTREE_CONST struct device * DEVTREE_CONST last_dev = &%s;\n",
-		lastnode->name);
-	walk_device_tree(autogen, &root, pass1);
+	walk_device_tree(autogen, &root_dev, pass0);
+	fprintf(autogen, "\n/* pass 1 */\n");
+	walk_device_tree(autogen, &root_dev, pass1);
 
 	fclose(autogen);
 
diff --git a/util/sconfig/sconfig.h b/util/sconfig/sconfig.h
index 2bb816d5ef..f9137fa7ac 100644
--- a/util/sconfig/sconfig.h
+++ b/util/sconfig/sconfig.h
@@ -78,50 +78,83 @@ struct chip {
 };
 
 struct device;
+struct bus {
+	/* Instance/ID of the bus under the device. */
+	int id;
+
+	/* Pointer to device to which this bus belongs. */
+	struct device *dev;
+
+	/* Pointer to list of children. */
+	struct device *children;
+
+	/* Pointer to next bus for the device. */
+	struct bus *next_bus;
+};
+
 struct device {
+	/* Monotonically increasing ID for the device. */
 	int id;
+
+	/* Indicates whether this device is enabled. */
 	int enabled;
-	int used;
-	int multidev;
-	int link;
+
+	/* Indicates number of resources for the device. */
 	int rescnt;
+
+	/* Subsystem IDs for the device. */
 	int subsystem_vendor;
 	int subsystem_device;
 	int inherit_subsystem;
+
+	/* Name of ops structure for the device. */
 	char *ops;
+
+	/* Name of this device. */
 	char *name;
+
+	/* Path of this device. */
 	char *path;
 	int path_a;
 	int path_b;
+
+	/* Type of bus that exists under this device. */
 	int bustype;
+
+	/* PCI IRQ info. */
 	struct pci_irq_info pci_irq_info[4];
 
-	struct device *parent;
-	struct device *next;
-	struct device *children;
-	struct device *latestchild;
-	struct device *next_sibling;
+	/* Pointer to bus of parent on which this device resides. */
+	struct bus *parent;
+
+	/* Pointer to next child under the same parent. */
 	struct device *sibling;
+
+	/* Pointer to resources for this device. */
 	struct resource *res;
 
+	/* Pointer to chip instance for this device. */
 	struct chip_instance *chip_instance;
-};
-
-extern struct device *head;
 
-void fold_in(struct device *parent);
+	/* Pointer to list of buses under this device. */
+	struct bus *bus;
+	/* Pointer to last bus under this device. */
+	struct bus *last_bus;
+};
 
-void postprocess_devtree(void);
+extern struct bus *root_parent;
 
-struct device *new_device(struct device *parent,
+struct device *new_device(struct bus *parent,
 			  struct chip_instance *chip_instance,
 			  const int bustype, const char *devnum,
 			  int enabled);
-void alias_siblings(struct device *d);
-void add_resource(struct device *dev, int type, int index, int base);
-void add_pci_subsystem_ids(struct device *dev, int vendor, int device,
+
+void add_resource(struct bus *bus, int type, int index, int base);
+
+void add_pci_subsystem_ids(struct bus *bus, int vendor, int device,
 			   int inherit);
-void add_ioapic_info(struct device *dev, int apicid, const char *_srcpin,
+
+void add_ioapic_info(struct bus *bus, int apicid, const char *_srcpin,
 		     int irqpin);
 
 void yyrestart(FILE *input_file);
diff --git a/util/sconfig/sconfig.tab.c_shipped b/util/sconfig/sconfig.tab.c_shipped
index 3f0e0af02a..c298a652a9 100644
--- a/util/sconfig/sconfig.tab.c_shipped
+++ b/util/sconfig/sconfig.tab.c_shipped
@@ -85,7 +85,7 @@
 int yylex();
 void yyerror(const char *s);
 
-static struct device *cur_parent;
+static struct bus *cur_parent;
 static struct chip_instance *cur_chip_instance;
 
 
@@ -164,7 +164,7 @@ union YYSTYPE
 {
 
 
-	struct device *device;
+	struct device *dev;
 	struct chip_instance *chip_instance;
 	char *string;
 	int number;
@@ -487,8 +487,8 @@ static const yytype_uint8 yytranslate[] =
 static const yytype_uint8 yyrline[] =
 {
        0,    36,    36,    36,    38,    38,    38,    38,    40,    40,
-      40,    40,    40,    40,    42,    42,    51,    51,    61,    64,
-      67,    70,    73
+      40,    40,    40,    40,    42,    42,    51,    51,    59,    62,
+      65,    68,    71
 };
 #endif
 
@@ -1287,13 +1287,7 @@ yyreduce:
     {
         case 2:
 
-    { cur_parent = head; }
-
-    break;
-
-  case 3:
-
-    { postprocess_devtree(); }
+    { cur_parent = root_parent; }
 
     break;
 
@@ -1318,8 +1312,8 @@ yyreduce:
   case 16:
 
     {
-	(yyval.device) = new_device(cur_parent, cur_chip_instance, (yyvsp[-2].number), (yyvsp[-1].string), (yyvsp[0].number));
-	cur_parent = (yyval.device);
+	(yyval.dev) = new_device(cur_parent, cur_chip_instance, (yyvsp[-2].number), (yyvsp[-1].string), (yyvsp[0].number));
+	cur_parent = (yyval.dev)->last_bus;
 }
 
     break;
@@ -1327,9 +1321,7 @@ yyreduce:
   case 17:
 
     {
-	cur_parent = (yyvsp[-2].device)->parent;
-	fold_in((yyvsp[-2].device));
-	alias_siblings((yyvsp[-2].device)->children);
+	cur_parent = (yyvsp[-2].dev)->parent;
 }
 
     break;
diff --git a/util/sconfig/sconfig.tab.h_shipped b/util/sconfig/sconfig.tab.h_shipped
index 378634789c..04af8248c8 100644
--- a/util/sconfig/sconfig.tab.h_shipped
+++ b/util/sconfig/sconfig.tab.h_shipped
@@ -85,7 +85,7 @@ union YYSTYPE
 {
 
 
-	struct device *device;
+	struct device *dev;
 	struct chip_instance *chip_instance;
 	char *string;
 	int number;
diff --git a/util/sconfig/sconfig.y b/util/sconfig/sconfig.y
index a355c77c56..3e463059c8 100755
--- a/util/sconfig/sconfig.y
+++ b/util/sconfig/sconfig.y
@@ -20,12 +20,12 @@
 int yylex();
 void yyerror(const char *s);
 
-static struct device *cur_parent;
+static struct bus *cur_parent;
 static struct chip_instance *cur_chip_instance;
 
 %}
 %union {
-	struct device *device;
+	struct device *dev;
 	struct chip_instance *chip_instance;
 	char *string;
 	int number;
@@ -33,7 +33,7 @@ static struct chip_instance *cur_chip_instance;
 
 %token CHIP DEVICE REGISTER BOOL BUS RESOURCE END EQUALS HEX STRING PCI PNP I2C APIC CPU_CLUSTER CPU DOMAIN IRQ DRQ IO NUMBER SUBSYSTEMID INHERIT IOAPIC_IRQ IOAPIC PCIINT GENERIC SPI USB MMIO
 %%
-devtree: { cur_parent = head; } chip { postprocess_devtree(); } ;
+devtree: { cur_parent = root_parent; } chip;
 
 chipchildren: chipchildren device | chipchildren chip | chipchildren registers | /* empty */ ;
 
@@ -49,13 +49,11 @@ chip: CHIP STRING /* == path */ {
 };
 
 device: DEVICE BUS NUMBER /* == devnum */ BOOL {
-	$<device>$ = new_device(cur_parent, cur_chip_instance, $<number>2, $<string>3, $<number>4);
-	cur_parent = $<device>$;
+	$<dev>$ = new_device(cur_parent, cur_chip_instance, $<number>2, $<string>3, $<number>4);
+	cur_parent = $<dev>$->last_bus;
 }
 	devicechildren END {
-	cur_parent = $<device>5->parent;
-	fold_in($<device>5);
-	alias_siblings($<device>5->children);
+	cur_parent = $<dev>5->parent;
 };
 
 resource: RESOURCE NUMBER /* == resnum */ EQUALS NUMBER /* == resval */