Merge branch 'stable'

Merge device tree sorting

2 files changed, 123 insertions, 4 deletions

diff --git a/core/device.c b/core/device.c
index c5f8634..4818d40 100644
--- a/core/device.c
+++ b/core/device.c
@@ -65,21 +65,69 @@ struct dt_node *dt_new_root(const char *name)
 	return new_node(name);
 }
 
+static const char *get_unitname(const struct dt_node *node)
+{
+	const char *c = strchr(node->name, '@');
+
+	if (!c)
+		return NULL;
+
+	return c + 1;
+}
+
+int dt_cmp_subnodes(const struct dt_node *a, const struct dt_node *b)
+{
+	const char *a_unit = get_unitname(a);
+	const char *b_unit = get_unitname(b);
+
+	ptrdiff_t basenamelen = a_unit - a->name;
+
+	/* sort hex unit addresses by number */
+	if (a_unit && b_unit && !strncmp(a->name, b->name, basenamelen)) {
+		unsigned long long a_num, b_num;
+		char *a_end, *b_end;
+
+		a_num = strtoul(a_unit, &a_end, 16);
+		b_num = strtoul(b_unit, &b_end, 16);
+
+		/* only compare if the unit addr parsed correctly */
+		if (*a_end == 0 && *b_end == 0)
+			return (a_num > b_num) - (a_num < b_num);
+	}
+
+	return strcmp(a->name, b->name);
+}
+
 bool dt_attach_root(struct dt_node *parent, struct dt_node *root)
 {
 	struct dt_node *node;
 
-	/* Look for duplicates */
-
 	assert(!root->parent);
+
+	if (list_empty(&parent->children)) {
+		list_add(&parent->children, &root->list);
+		root->parent = parent;
+
+		return true;
+	}
+
 	dt_for_each_child(parent, node) {
-		if (!strcmp(node->name, root->name)) {
+		int cmp = dt_cmp_subnodes(node, root);
+
+		/* Look for duplicates */
+		if (cmp == 0) {
 			prerror("DT: %s failed, duplicate %s\n",
 				__func__, root->name);
 			return false;
 		}
+
+		/* insert before the first node that's larger
+		 * the the node we're inserting */
+		if (cmp > 0)
+			break;
 	}
-	list_add_tail(&parent->children, &root->list);
+
+	list_add_before(&parent->children, &root->list, &node->list);
 	root->parent = parent;
 
 	return true;
diff --git a/core/test/run-device.c b/core/test/run-device.c
index cd6ec8d..61ecf84 100644
--- a/core/test/run-device.c
+++ b/core/test/run-device.c
@@ -15,6 +15,7 @@
  */
 
 #include <skiboot.h>
+#include <stdlib.h>
 
 /* Override this for testing. */
 #define is_rodata(p) fake_is_rodata(p)
@@ -32,6 +33,7 @@ static inline bool fake_is_rodata(const void *p)
 #include "../device.c"
 #include "../../ccan/list/list.c" /* For list_check */
 #include <assert.h>
+#include "../../test/dt_common.c"
 
 static void check_path(const struct dt_node *node, const char * expected_path)
 {
@@ -44,6 +46,49 @@ static void check_path(const struct dt_node *node, const char * expected_path)
 	free(path);
 }
 
+/* constructs a random nodes only device tree */
+static void build_tree(int max_depth, int min_depth, struct dt_node *parent)
+{
+	char name[64];
+	int i;
+
+	for (i = 0; i < max_depth; i++) {
+		struct dt_node *new;
+
+		snprintf(name, sizeof name, "prefix@%.8x", rand());
+
+		new = dt_new(parent, name);
+
+		if(max_depth > min_depth)
+			build_tree(max_depth - 1, min_depth, new);
+	}
+}
+
+static bool is_sorted(const struct dt_node *root)
+{
+	struct dt_node *end = list_tail(&root->children, struct dt_node, list);
+	struct dt_node *node;
+
+	dt_for_each_child(root, node) {
+		struct dt_node *next =
+			list_entry(node->list.next, struct dt_node, list);
+
+		/* current node must be "less than" the next node */
+		if (node != end && dt_cmp_subnodes(node, next) != -1) {
+			printf("nodes '%s' and '%s' out of order\n",
+				node->name, next->name);
+
+			return false;
+		}
+
+		if (!is_sorted(node))
+			return false;
+	}
+
+	return true;
+}
+
+
 int main(void)
 {
 	struct dt_node *root, *c1, *c2, *gc1, *gc2, *gc3, *ggc1;
@@ -297,5 +342,31 @@ int main(void)
 	assert(dt_find_by_phandle(root, 0xf0f) == NULL);
 
 	dt_free(root);
+
+	/* basic sorting */
+	root = dt_new_root("rewt");
+	dt_new(root, "a@1");
+	dt_new(root, "a@2");
+	dt_new(root, "a@3");
+	dt_new(root, "a@4");
+	dt_new(root, "b@4");
+	dt_new(root, "c@4");
+
+	assert(is_sorted(root));
+
+	dt_free(root);
+
+	/* Test child node sorting */
+	root = dt_new_root("test root");
+	build_tree(5, 3, root);
+
+	if (!is_sorted(root)) {
+		dump_dt(root, 1, false);
+	}
+	assert(is_sorted(root));
+
+	dt_free(root);
+
 	return 0;
 }
+