From 880e011495cfeb0deb0423739055d4f7bbc2f9a7 Mon Sep 17 00:00:00 2001 From: Oliver O'Halloran Date: Mon, 18 Jan 2016 14:23:16 +1100 Subject: core/device.c: Sort nodes with name@unit names by unit When unflattening (or building from hdat) a device tree child nodes are added in the order in which they are encountered. For nodes that have a @ style name with a common basename it is useful to have them in the tree sorted by the unit in ascending order. Currently this requires the source data to present them in sorted order, but this isn't always the case. This patch modifies the node insertion process to insert new nodes in the correct location so the list of child nodes is sorted. Signed-off-by: Oliver O'Halloran [stewart@linux.vnet.ibm.com: remove trailing whitespace] Signed-off-by: Stewart Smith --- core/device.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 52 insertions(+), 4 deletions(-) (limited to 'core') diff --git a/core/device.c b/core/device.c index 483baec..2b44edb 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; +} + +static 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; -- cgit v1.1 From 5d9b239fadc6c0bdf18e34a48a4b0ade956994e6 Mon Sep 17 00:00:00 2001 From: Oliver O'Halloran Date: Mon, 18 Jan 2016 14:23:18 +1100 Subject: DT sorting test Moved the dt_dump() into test/dt_common.c so that it can be shared between hdata/test/hdata_to_dt.c and core/test/run-device.c run-device.c contains two tests, one basic sorting test and a generate-and-sort test. Signed-off-by: Oliver O'Halloran [stewart@linux.vnet.ibm.com: remove trailing whitespace] Signed-off-by: Stewart Smith --- core/device.c | 2 +- core/test/run-device.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+), 1 deletion(-) (limited to 'core') diff --git a/core/device.c b/core/device.c index 2b44edb..ba983c7 100644 --- a/core/device.c +++ b/core/device.c @@ -75,7 +75,7 @@ static const char *get_unitname(const struct dt_node *node) return c + 1; } -static int dt_cmp_subnodes(const struct dt_node *a, const struct dt_node *b) +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); 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 +#include /* 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 +#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; } + -- cgit v1.1