util/sconfig: Re-factor sconfig to not assume chip as device

This change adds a new structure "struct chip" to identify elements of
type chip rather than re-using the structure for device. Until now
chip was treated as a device while generating the parse tree and then
device tree postprocessing skipped over all the chip entries in
children and sibling pointers of device nodes.

With this change, the device tree will only contain struct device in
the parsed tree. It helps by avoiding unnecessary pointers to chip
structure as children or next_sibling and then skipping those elements
in post processing. Every device can then hold a pointer to its chip.

When generating static.c, chip structure is emitted before device
structure to ensure that the device structure has chip within its
scope. Externally, the only visible change in static.c should be the
order in which chip/device elements are emitted i.e. previously all
chips under a particular device were emitted to static.c and then the
devices using those chips. Now, all chips are emitted before all the
devices in static.c

BUG=b:80081934
TEST=Verified that abuild is successful for all boards. Also, verified
that static.c generated for eve, kahlee, scarlet, asrock imb_a180 is
unchanged from before in node definitions.

Change-Id: I255092f527c8eecb144385eb681df20e54caf8f5
Signed-off-by: Furquan Shaikh <furquan@google.com>
Reviewed-on: https://review.coreboot.org/26720
Tested-by: build bot (Jenkins) <no-reply@coreboot.org>
Reviewed-by: Aaron Durbin <adurbin@chromium.org>
diff --git a/util/sconfig/main.c b/util/sconfig/main.c
index 2e34d85..382d5e5 100644
--- a/util/sconfig/main.c
+++ b/util/sconfig/main.c
@@ -24,7 +24,13 @@
 
 struct header headers;
 
-static int devcount = 0;
+static struct chip *chip_head;
+
+/*
+ * This is intentionally shared between chip and device structure ids because it
+ * is easier to track the order of parsing for chip and device.
+ */
+static int count = 0;
 
 typedef enum {
 	UNSLASH,
@@ -34,22 +40,15 @@
 } translate_t;
 
 static struct device root;
-static struct device mainboard = {
+static struct chip mainboard = {
 	.name = "mainboard",
 	.name_underscore = "mainboard",
-	.id = 0,
-	.chip = &mainboard,
-	.type = chip,
-	.chiph_exists = 0,
-	.children = &root
 };
 
 static struct device root = {
 	.name = "dev_root",
-	.name_underscore = "dev_root",
 	.id = 0,
 	.chip = &mainboard,
-	.type = device,
 	.path = " .type = DEVICE_PATH_ROOT ",
 	.ops = "&default_dev_ops_root",
 	.parent = &root,
@@ -57,11 +56,64 @@
 	.enabled = 1
 };
 
+static struct queue {
+	void *data;
+	struct queue *next;
+	struct queue *prev;
+} *q;
+
+struct queue *new_queue_entry(void *data)
+{
+	struct queue *e = malloc(sizeof(*e));
+
+	if (!e) {
+		fprintf(stderr, "%s: malloc failure!\n", __func__);
+		exit(1);
+	}
+
+	e->data = data;
+	e->next = e->prev = e;
+	return e;
+}
+
+void chip_enqueue_tail(void *data)
+{
+	struct queue *tmp = new_queue_entry(data);
+
+	if (!q) {
+		q = tmp;
+		return;
+	}
+
+	q->prev->next = tmp;
+	tmp->prev = q->prev;
+	q->prev = tmp;
+	tmp->next = q;
+}
+
+void *chip_dequeue_tail(void)
+{
+	struct queue *tmp = q->prev;
+	void *data;
+
+	if (tmp == q)
+		q = NULL;
+	else {
+		tmp->prev->next = q;
+		q->prev = tmp->prev;
+	}
+
+	data = tmp->data;
+	free(tmp);
+
+	return data;
+}
+
 static struct device *new_dev(struct device *parent, struct device *bus)
 {
 	struct device *dev = malloc(sizeof(struct device));
 	memset(dev, 0, sizeof(struct device));
-	dev->id = ++devcount;
+	dev->id = ++count;
 	dev->parent = parent;
 	dev->bus = bus;
 	dev->subsystem_vendor = -1;
@@ -109,22 +161,18 @@
 void postprocess_devtree(void)
 {
 	root.next_sibling = root.children;
-	root.next_sibling->next_sibling = root.next_sibling->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 "chip" elements in children chain */
-		while (dev->children && (dev->children->type == chip))
-			dev->children = dev->children->children;
-		/* skip "chip" elements and functions of the same device in sibling chain */
+		/* skip functions of the same device in sibling chain */
 		while (dev->sibling && dev->sibling->used)
 			dev->sibling = dev->sibling->sibling;
-		/* If end of chain, and parent is a chip, move on */
-		if (!dev->sibling && (dev->parent->type == chip))
-			dev->sibling = dev->parent->sibling;
-		/* skip chips */
-		while (dev->sibling && dev->sibling->type == chip)
-			dev->sibling = dev->sibling->children;
 		/* skip duplicate function elements in nextdev chain */
 		while (dev->nextdev && dev->nextdev->used)
 			dev->nextdev = dev->nextdev->nextdev;
@@ -154,14 +202,20 @@
 	return b;
 }
 
-struct device *new_chip(struct device *parent, struct device *bus, char *path)
+struct chip *new_chip(char *path)
 {
-	struct device *new_chip = new_dev(parent, bus);
+	struct chip *new_chip = malloc(sizeof(*new_chip));
+	if (!new_chip) {
+		fprintf(stderr, "%s: malloc failure!\n", __func__);
+		exit(1);
+	}
+
+	memset(new_chip, 0, sizeof(*new_chip));
+
+	new_chip->id = ++count;
 	new_chip->chiph_exists = 1;
 	new_chip->name = path;
 	new_chip->name_underscore = translate_name(new_chip->name, UNSLASH);
-	new_chip->type = chip;
-	new_chip->chip = new_chip;
 
 	struct stat st;
 	char *chip_h = malloc(strlen(path) + 18);
@@ -182,23 +236,20 @@
 	if ((stat(chip_h, &st) == -1) && (errno == ENOENT))
 		new_chip->chiph_exists = 0;
 
-	if (parent->latestchild) {
-		parent->latestchild->next_sibling = new_chip;
-		parent->latestchild->sibling = new_chip;
-	}
-	parent->latestchild = new_chip;
-	if (!parent->children)
-		parent->children = new_chip;
 	free(chip_h);
+
+	new_chip->next = chip_head;
+	chip_head = new_chip;
+
 	return new_chip;
 }
 
-void add_header(struct device *dev)
+void add_header(struct chip *chip)
 {
 	int include_exists = 0;
 	struct header *h = &headers;
 	while (h->next) {
-		int result = strcmp(dev->name, h->next->name);
+		int result = strcmp(chip->name, h->next->name);
 		if (result == 0) {
 			include_exists = 1;
 			break;
@@ -211,14 +262,15 @@
 		struct header *tmp = h->next;
 		h->next = malloc(sizeof(struct header));
 		memset(h->next, 0, sizeof(struct header));
-		h->next->chiph_exists = dev->chiph_exists;
-		h->next->name = dev->name;
+		h->next->chiph_exists = chip->chiph_exists;
+		h->next->name = chip->name;
 		h->next->next = tmp;
 	}
 }
 
 struct device *new_device(struct device *parent, struct device *busdev,
-			  const int bus, const char *devnum, int enabled)
+			  struct chip *chip, const int bus, const char *devnum,
+			  int enabled)
 {
 	struct device *new_d = new_dev(parent, busdev);
 	new_d->bustype = bus;
@@ -233,10 +285,9 @@
 	char *name = malloc(10);
 	sprintf(name, "_dev%d", new_d->id);
 	new_d->name = name;
-	new_d->name_underscore = name;	// shouldn't be necessary, but avoid 0-ptr
-	new_d->type = device;
+
 	new_d->enabled = enabled;
-	new_d->chip = new_d->parent->chip;
+	new_d->chip = chip;
 
 	if (parent->latestchild) {
 		parent->latestchild->next_sibling = new_d;
@@ -309,7 +360,7 @@
 		struct device *cmp = d->next_sibling;
 		while (cmp && (cmp->bus == d->bus) && (cmp->path_a == d->path_a)
 		       && (cmp->path_b == d->path_b)) {
-			if (cmp->type == device && !cmp->used) {
+			if (!cmp->used) {
 				if (device_match(d, cmp)) {
 					d->multidev = 1;
 
@@ -343,14 +394,14 @@
 	dev->rescnt++;
 }
 
-void add_register(struct device *dev, char *name, char *val)
+void add_register(struct chip *chip, char *name, char *val)
 {
 	struct reg *r = malloc(sizeof(struct reg));
 	memset(r, 0, sizeof(struct reg));
 	r->key = name;
 	r->value = val;
-	if (dev->reg) {
-		struct reg *head = dev->reg;
+	if (chip->reg) {
+		struct reg *head = chip->reg;
 		// sorting to be equal to sconfig's behaviour
 		int sort = strcmp(r->key, head->key);
 		if (sort == 0) {
@@ -359,7 +410,7 @@
 		}
 		if (sort < 0) {
 			r->next = head;
-			dev->reg = r;
+			chip->reg = r;
 		} else {
 			while ((head->next)
 			       && (strcmp(head->next->key, r->key) < 0))
@@ -368,7 +419,7 @@
 			head->next = r;
 		}
 	} else {
-		dev->reg = r;
+		chip->reg = r;
 	}
 }
 
@@ -412,13 +463,13 @@
 	dev->pci_irq_info[srcpin].ioapic_dst_id = apicid;
 }
 
-static void pass0(FILE * fil, struct device *ptr)
+static void pass0(FILE *fil, struct device *ptr)
 {
-	if (ptr->type == device && ptr->id == 0)
+	if (ptr->id == 0)
 		fprintf(fil, "DEVTREE_CONST struct bus %s_links[];\n",
 			ptr->name);
 
-	if ((ptr->type == device) && (ptr->id != 0) && (!ptr->used)) {
+	if ((ptr->id != 0) && (!ptr->used)) {
 		fprintf(fil, "DEVTREE_CONST static struct device %s;\n",
 			ptr->name);
 		if (ptr->rescnt > 0)
@@ -431,10 +482,11 @@
 	}
 }
 
-static void pass1(FILE * fil, struct device *ptr)
+static void pass1(FILE *fil, struct device *ptr)
 {
 	int pin;
-	if (!ptr->used && (ptr->type == device)) {
+
+	if (!ptr->used) {
 		if (ptr->id != 0)
 			fprintf(fil, "static ");
 		fprintf(fil, "DEVTREE_CONST struct device %s = {\n",
@@ -481,7 +533,7 @@
 		fprintf(fil, "#if !DEVTREE_EARLY\n");
 		fprintf(fil, "\t.chip_ops = &%s_ops,\n",
 			ptr->chip->name_underscore);
-		if (ptr->chip->chip == &mainboard)
+		if (ptr->chip == &mainboard)
 			fprintf(fil, "\t.name = mainboard_name,\n");
 		fprintf(fil, "#endif\n");
 		if (ptr->chip->chiph_exists)
@@ -516,8 +568,7 @@
 		}
 		fprintf(fil, "\t };\n");
 	}
-	if (!ptr->used && ptr->type == device
-	    && (ptr->children || ptr->multidev)) {
+	if (!ptr->used && (ptr->children || ptr->multidev)) {
 		fprintf(fil, "DEVTREE_CONST struct bus %s_links[] = {\n",
 			ptr->name);
 		if (ptr->multidev) {
@@ -559,29 +610,10 @@
 		}
 		fprintf(fil, "\t};\n");
 	}
-	if ((ptr->type == chip) && (ptr->chiph_exists)) {
-		if (ptr->reg) {
-			fprintf(fil,
-				"DEVTREE_CONST struct %s_config %s_info_%d = {\n",
-				ptr->name_underscore, ptr->name_underscore,
-				ptr->id);
-			struct reg *r = ptr->reg;
-			while (r) {
-				fprintf(fil, "\t.%s = %s,\n", r->key, r->value);
-				r = r->next;
-			}
-			fprintf(fil, "};\n\n");
-		} else {
-			fprintf(fil,
-				"DEVTREE_CONST struct %s_config %s_info_%d = { };\n",
-				ptr->name_underscore, ptr->name_underscore,
-				ptr->id);
-		}
-	}
 }
 
-static void walk_device_tree(FILE * fil, struct device *ptr,
-			     void (*func) (FILE *, struct device *),
+static void walk_device_tree(FILE *fil, struct device *ptr,
+			     void (*func)(FILE *, struct device *),
 			     struct device *chips)
 {
 	do {
@@ -590,7 +622,35 @@
 	} while (ptr);
 }
 
-static void inherit_subsystem_ids(FILE * file, struct device *dev)
+static void emit_chips(FILE *fil)
+{
+	struct chip *chip;
+
+	for (chip = chip_head; chip; chip = chip->next) {
+		if (!chip->chiph_exists)
+			continue;
+
+		if (chip->reg) {
+			fprintf(fil,
+				"DEVTREE_CONST struct %s_config %s_info_%d = {\n",
+				chip->name_underscore, chip->name_underscore,
+				chip->id);
+			struct reg *r = chip->reg;
+			while (r) {
+				fprintf(fil, "\t.%s = %s,\n", r->key, r->value);
+				r = r->next;
+			}
+			fprintf(fil, "};\n\n");
+		} else {
+			fprintf(fil,
+				"DEVTREE_CONST struct %s_config %s_info_%d = { };\n",
+				chip->name_underscore, chip->name_underscore,
+				chip->id);
+		}
+	}
+}
+
+static void inherit_subsystem_ids(FILE *file, struct device *dev)
 {
 	struct device *p;
 
@@ -649,13 +709,6 @@
 
 	fclose(filec);
 
-	if ((head->type == chip) && (!head->chiph_exists)) {
-		struct device *tmp = head;
-		head = &root;
-		while (head->next != tmp)
-			head = head->next;
-	}
-
 	FILE *autogen = fopen(outputc, "w");
 	if (!autogen) {
 		fprintf(stderr, "Could not open file '%s' for writing: ",
@@ -687,6 +740,8 @@
 	}
 	fprintf(autogen, "#endif\n");
 
+	emit_chips(autogen);
+
 	walk_device_tree(autogen, &root, inherit_subsystem_ids, NULL);
 	fprintf(autogen, "\n/* pass 0 */\n");
 	walk_device_tree(autogen, &root, pass0, NULL);
diff --git a/util/sconfig/sconfig.h b/util/sconfig/sconfig.h
index 119d7b5..79d2da0 100644
--- a/util/sconfig/sconfig.h
+++ b/util/sconfig/sconfig.h
@@ -22,8 +22,6 @@
 #include <unistd.h>
 #include <errno.h>
 
-enum devtype { chip, device };
-
 struct resource;
 struct resource {
 	int type;
@@ -43,6 +41,30 @@
 	int ioapic_irq_pin;
 	int ioapic_dst_id;
 };
+
+struct chip {
+	/*
+	 * Monotonically increasing ID for each newly allocated
+	 * node(chip/device).
+	 */
+	int id;
+
+	/* Indicates if chip header exists for this chip. */
+	int chiph_exists;
+
+	/* Name of current chip. */
+	char *name;
+
+	/* Name of current chip normalized to _. */
+	char *name_underscore;
+
+	/* Pointer to registers for this chip. */
+	struct reg *reg;
+
+	/* Pointer to next chip. */
+	struct chip *next;
+};
+
 struct device;
 struct device {
 	int id;
@@ -51,19 +73,17 @@
 	int multidev;
 	int link;
 	int rescnt;
-	int chiph_exists;
 	int subsystem_vendor;
 	int subsystem_device;
 	int inherit_subsystem;
 	char *ops;
 	char *name;
-	char *name_underscore;
 	char *path;
 	int path_a;
 	int path_b;
 	int bustype;
 	struct pci_irq_info pci_irq_info[4];
-	enum devtype type;
+
 	struct device *parent;
 	struct device *bus;
 	struct device *next;
@@ -72,12 +92,12 @@
 	struct device *latestchild;
 	struct device *next_sibling;
 	struct device *sibling;
-	struct device *chip;
 	struct resource *res;
-	struct reg *reg;
+
+	struct chip *chip;
 };
 
-struct device *head;
+extern struct device *head;
 
 struct header;
 struct header {
@@ -89,16 +109,23 @@
 void fold_in(struct device *parent);
 
 void postprocess_devtree(void);
-struct device *new_chip(struct device *parent, struct device *bus, char *path);
-void add_header(struct device *dev);
+struct chip *new_chip(char *path);
+void add_header(struct chip *chip);
 struct device *new_device(struct device *parent, struct device *busdev,
-			  const int bus, const char *devnum, int enabled);
+			  struct chip *chip, const int bus, 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_register(struct device *dev, char *name, char *val);
+void add_register(struct chip *chip, char *name, char *val);
 void add_pci_subsystem_ids(struct device *dev, int vendor, int device,
 			   int inherit);
 void add_ioapic_info(struct device *dev, int apicid, const char *_srcpin,
 		     int irqpin);
 
 void yyrestart(FILE *input_file);
+
+/* Add chip data to tail of queue. */
+void chip_enqueue_tail(void *data);
+
+/* Retrieve chip data from tail of queue. */
+void *chip_dequeue_tail(void);
diff --git a/util/sconfig/sconfig.tab.c_shipped b/util/sconfig/sconfig.tab.c_shipped
index 1832f35..637927a 100644
--- a/util/sconfig/sconfig.tab.c_shipped
+++ b/util/sconfig/sconfig.tab.c_shipped
@@ -86,6 +86,7 @@
 void yyerror(const char *s);
 
 static struct device *cur_parent, *cur_bus;
+static struct chip *cur_chip;
 
 
 
@@ -164,6 +165,7 @@
 
 
 	struct device *device;
+	struct chip *chip;
 	char *string;
 	int number;
 
@@ -484,9 +486,9 @@
   /* YYRLINE[YYN] -- Source line where rule number YYN was defined.  */
 static const yytype_uint8 yyrline[] =
 {
-       0,    34,    34,    34,    36,    36,    36,    36,    38,    38,
-      38,    38,    38,    38,    40,    40,    50,    50,    62,    65,
-      68,    71,    74
+       0,    36,    36,    36,    38,    38,    38,    38,    40,    40,
+      40,    40,    40,    40,    42,    42,    52,    52,    64,    67,
+      70,    73,    76
 };
 #endif
 
@@ -1298,8 +1300,9 @@
   case 14:
 
     {
-	(yyval.device) = new_chip(cur_parent, cur_bus, (yyvsp[0].string));
-	cur_parent = (yyval.device);
+	(yyval.chip) = new_chip((yyvsp[0].string));
+	chip_enqueue_tail(cur_chip);
+	cur_chip = (yyval.chip);
 }
 
     break;
@@ -1307,9 +1310,8 @@
   case 15:
 
     {
-	cur_parent = (yyvsp[-2].device)->parent;
-	fold_in((yyvsp[-2].device));
-	add_header((yyvsp[-2].device));
+	cur_chip = chip_dequeue_tail();
+	add_header((yyvsp[-2].chip));
 }
 
     break;
@@ -1317,7 +1319,7 @@
   case 16:
 
     {
-	(yyval.device) = new_device(cur_parent, cur_bus, (yyvsp[-2].number), (yyvsp[-1].string), (yyvsp[0].number));
+	(yyval.device) = new_device(cur_parent, cur_bus, cur_chip, (yyvsp[-2].number), (yyvsp[-1].string), (yyvsp[0].number));
 	cur_parent = (yyval.device);
 	cur_bus = (yyval.device);
 }
@@ -1343,7 +1345,7 @@
 
   case 19:
 
-    { add_register(cur_parent, (yyvsp[-2].string), (yyvsp[0].string)); }
+    { add_register(cur_chip, (yyvsp[-2].string), (yyvsp[0].string)); }
 
     break;
 
diff --git a/util/sconfig/sconfig.tab.h_shipped b/util/sconfig/sconfig.tab.h_shipped
index 89b936a..e633fe0 100644
--- a/util/sconfig/sconfig.tab.h_shipped
+++ b/util/sconfig/sconfig.tab.h_shipped
@@ -86,6 +86,7 @@
 
 
 	struct device *device;
+	struct chip *chip;
 	char *string;
 	int number;
 
diff --git a/util/sconfig/sconfig.y b/util/sconfig/sconfig.y
index 5cecbba..651aa87 100755
--- a/util/sconfig/sconfig.y
+++ b/util/sconfig/sconfig.y
@@ -21,10 +21,12 @@
 void yyerror(const char *s);
 
 static struct device *cur_parent, *cur_bus;
+static struct chip *cur_chip;
 
 %}
 %union {
 	struct device *device;
+	struct chip *chip;
 	char *string;
 	int number;
 }
@@ -38,17 +40,17 @@
 devicechildren: devicechildren device | devicechildren chip | devicechildren resource | devicechildren subsystemid | devicechildren ioapic_irq | /* empty */ ;
 
 chip: CHIP STRING /* == path */ {
-	$<device>$ = new_chip(cur_parent, cur_bus, $<string>2);
-	cur_parent = $<device>$;
+	$<chip>$ = new_chip($<string>2);
+	chip_enqueue_tail(cur_chip);
+	cur_chip = $<chip>$;
 }
 	chipchildren END {
-	cur_parent = $<device>3->parent;
-	fold_in($<device>3);
-	add_header($<device>3);
+	cur_chip = chip_dequeue_tail();
+	add_header($<chip>3);
 };
 
 device: DEVICE BUS NUMBER /* == devnum */ BOOL {
-	$<device>$ = new_device(cur_parent, cur_bus, $<number>2, $<string>3, $<number>4);
+	$<device>$ = new_device(cur_parent, cur_bus, cur_chip, $<number>2, $<string>3, $<number>4);
 	cur_parent = $<device>$;
 	cur_bus = $<device>$;
 }
@@ -63,7 +65,7 @@
 	{ add_resource(cur_parent, $<number>1, strtol($<string>2, NULL, 0), strtol($<string>4, NULL, 0)); } ;
 
 registers: REGISTER STRING /* == regname */ EQUALS STRING /* == regval */
-	{ add_register(cur_parent, $<string>2, $<string>4); } ;
+	{ add_register(cur_chip, $<string>2, $<string>4); } ;
 
 subsystemid: SUBSYSTEMID NUMBER NUMBER
 	{ add_pci_subsystem_ids(cur_parent, strtol($<string>2, NULL, 16), strtol($<string>3, NULL, 16), 0); };