aboutsummaryrefslogtreecommitdiff
path: root/core
diff options
context:
space:
mode:
authorStewart Smith <stewart@linux.vnet.ibm.com>2016-01-21 15:27:44 +1100
committerStewart Smith <stewart@linux.vnet.ibm.com>2016-01-21 15:27:44 +1100
commitab6892b8bfce23eb3c6751fbf9e9d9a2e4c22ee3 (patch)
tree962c2350e5ac96b94153f40303df8ef3f3c94cb3 /core
parent33e3b5d3ce7d69272c22ae269b7f341dfd79be14 (diff)
parent5d9b239fadc6c0bdf18e34a48a4b0ade956994e6 (diff)
downloadskiboot-ab6892b8bfce23eb3c6751fbf9e9d9a2e4c22ee3.zip
skiboot-ab6892b8bfce23eb3c6751fbf9e9d9a2e4c22ee3.tar.gz
skiboot-ab6892b8bfce23eb3c6751fbf9e9d9a2e4c22ee3.tar.bz2
Merge branch 'stable'
Merge device tree sorting
Diffstat (limited to 'core')
-rw-r--r--core/device.c56
-rw-r--r--core/test/run-device.c71
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;
}
+