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>

5 files changed, 195 insertions, 108 deletions

diff --git a/util/sconfig/main.c b/util/sconfig/main.c
index 2e34d85ad5..382d5e5c7b 100644
--- a/util/sconfig/main.c
+++ b/util/sconfig/main.c
@@ -24,7 +24,13 @@ struct device *head, *lastdev;
 
 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 @@ typedef enum {
 } 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 @@ static struct device root = {
 	.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 yyerror(char const *str)
 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 @@ char *translate_name(const char *str, translate_t mode)
 	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 @@ struct device *new_chip(struct device *parent, struct device *bus, char *path)
 	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 @@ void add_header(struct device *dev)
 		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 @@ struct device *new_device(struct device *parent, struct device *busdev,
 	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 @@ void alias_siblings(struct device *d)
 		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 @@ void add_resource(struct device *dev, int type, int index, int base)
 	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 @@ void add_register(struct device *dev, char *name, char *val)
 		}
 		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 @@ void add_register(struct device *dev, char *name, char *val)
 			head->next = r;
 		}
 	} else {
-		dev->reg = r;
+		chip->reg = r;
 	}
 }
 
@@ -412,13 +463,13 @@ 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 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 pass0(FILE * fil, struct device *ptr)
 	}
 }
 
-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 @@ static void pass1(FILE * fil, struct device *ptr)
 		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 @@ static void pass1(FILE * fil, struct device *ptr)
 		}
 		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,13 +610,32 @@ static void pass1(FILE * fil, struct device *ptr)
 		}
 		fprintf(fil, "\t};\n");
 	}
-	if ((ptr->type == chip) && (ptr->chiph_exists)) {
-		if (ptr->reg) {
+}
+
+static void walk_device_tree(FILE *fil, struct device *ptr,
+			     void (*func)(FILE *, struct device *),
+			     struct device *chips)
+{
+	do {
+		func(fil, ptr);
+		ptr = ptr->next_sibling;
+	} while (ptr);
+}
+
+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",
-				ptr->name_underscore, ptr->name_underscore,
-				ptr->id);
-			struct reg *r = ptr->reg;
+				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;
@@ -574,23 +644,13 @@ static void pass1(FILE * fil, struct device *ptr)
 		} else {
 			fprintf(fil,
 				"DEVTREE_CONST struct %s_config %s_info_%d = { };\n",
-				ptr->name_underscore, ptr->name_underscore,
-				ptr->id);
+				chip->name_underscore, chip->name_underscore,
+				chip->id);
 		}
 	}
 }
 
-static void walk_device_tree(FILE * fil, struct device *ptr,
-			     void (*func) (FILE *, struct device *),
-			     struct device *chips)
-{
-	do {
-		func(fil, ptr);
-		ptr = ptr->next_sibling;
-	} while (ptr);
-}
-
-static void inherit_subsystem_ids(FILE * file, struct device *dev)
+static void inherit_subsystem_ids(FILE *file, struct device *dev)
 {
 	struct device *p;
 
@@ -649,13 +709,6 @@ int main(int argc, char **argv)
 
 	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 @@ int main(int argc, char **argv)
 	}
 	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 119d7b5fbf..79d2da0d16 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 @@ struct pci_irq_info {
 	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 @@ struct device {
 	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 {
 	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 @@ struct header {
 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 1832f35bf3..637927a8b2 100644
--- a/util/sconfig/sconfig.tab.c_shipped
+++ b/util/sconfig/sconfig.tab.c_shipped
@@ -86,6 +86,7 @@ int yylex();
 void yyerror(const char *s);
 
 static struct device *cur_parent, *cur_bus;
+static struct chip *cur_chip;
 
 
 
@@ -164,6 +165,7 @@ union YYSTYPE
 
 
 	struct device *device;
+	struct chip *chip;
 	char *string;
 	int number;
 
@@ -484,9 +486,9 @@ static const yytype_uint8 yytranslate[] =
   /* 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 @@ yyreduce:
   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 @@ yyreduce:
   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 @@ yyreduce:
   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 @@ yyreduce:
 
   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 89b936a156..e633fe0579 100644
--- a/util/sconfig/sconfig.tab.h_shipped
+++ b/util/sconfig/sconfig.tab.h_shipped
@@ -86,6 +86,7 @@ union YYSTYPE
 
 
 	struct device *device;
+	struct chip *chip;
 	char *string;
 	int number;
 
diff --git a/util/sconfig/sconfig.y b/util/sconfig/sconfig.y
index 5cecbbace6..651aa87d50 100755
--- a/util/sconfig/sconfig.y
+++ b/util/sconfig/sconfig.y
@@ -21,10 +21,12 @@ int yylex();
 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 @@ chipchildren: chipchildren device | chipchildren chip | chipchildren registers |
 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 @@ resource: RESOURCE NUMBER /* == resnum */ EQUALS NUMBER /* == resval */
 	{ 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); };