1 files changed, 323 insertions, 22 deletions

diff --git a/scripts/dtc/livetree.c b/scripts/dtc/livetree.c
index 0ca3de550b3f..c9209d5c999e 100644
--- a/scripts/dtc/livetree.c
+++ b/scripts/dtc/livetree.c
@@ -24,17 +24,30 @@
  * Tree building functions
  */
 
-struct property *build_property(char *name, struct data val, char *label)
+void add_label(struct label **labels, char *label)
+{
+        struct label *new;
+
+        /* Make sure the label isn't already there */
+        for_each_label(*labels, new)
+                if (streq(new->label, label))
+                        return;
+
+        new = xmalloc(sizeof(*new));
+        new->label = label;
+        new->next = *labels;
+        *labels = new;
+}
+
+struct property *build_property(char *name, struct data val)
 {
         struct property *new = xmalloc(sizeof(*new));
 
+        memset(new, 0, sizeof(*new));
+
         new->name = name;
         new->val = val;
 
-        new->next = NULL;
-
-        new->label = label;
-
         return new;
 }
 
@@ -78,17 +91,82 @@ struct node *build_node(struct property *proplist, struct node *children)
         return new;
 }
 
-struct node *name_node(struct node *node, char *name, char * label)
+struct node *name_node(struct node *node, char *name)
 {
         assert(node->name == NULL);
 
         node->name = name;
 
-        node->label = label;
-
         return node;
 }
 
+struct node *merge_nodes(struct node *old_node, struct node *new_node)
+{
+        struct property *new_prop, *old_prop;
+        struct node *new_child, *old_child;
+        struct label *l;
+
+        /* Add new node labels to old node */
+        for_each_label(new_node->labels, l)
+                add_label(&old_node->labels, l->label);
+
+        /* Move properties from the new node to the old node.  If there
+         * is a collision, replace the old value with the new */
+        while (new_node->proplist) {
+                /* Pop the property off the list */
+                new_prop = new_node->proplist;
+                new_node->proplist = new_prop->next;
+                new_prop->next = NULL;
+
+                /* Look for a collision, set new value if there is */
+                for_each_property(old_node, old_prop) {
+                        if (streq(old_prop->name, new_prop->name)) {
+                                /* Add new labels to old property */
+                                for_each_label(new_prop->labels, l)
+                                        add_label(&old_prop->labels, l->label);
+
+                                old_prop->val = new_prop->val;
+                                free(new_prop);
+                                new_prop = NULL;
+                                break;
+                        }
+                }
+
+                /* if no collision occurred, add property to the old node. */
+                if (new_prop)
+                        add_property(old_node, new_prop);
+        }
+
+        /* Move the override child nodes into the primary node.  If
+         * there is a collision, then merge the nodes. */
+        while (new_node->children) {
+                /* Pop the child node off the list */
+                new_child = new_node->children;
+                new_node->children = new_child->next_sibling;
+                new_child->parent = NULL;
+                new_child->next_sibling = NULL;
+
+                /* Search for a collision.  Merge if there is */
+                for_each_child(old_node, old_child) {
+                        if (streq(old_child->name, new_child->name)) {
+                                merge_nodes(old_child, new_child);
+                                new_child = NULL;
+                                break;
+                        }
+                }
+
+                /* if no collision occured, add child to the old node. */
+                if (new_child)
+                        add_child(old_node, new_child);
+        }
+
+        /* The new node contents are now merged into the old node.  Free
+         * the new node. */
+        free(new_node);
+
+        return old_node;
+}
+
 struct node *chain_node(struct node *first, struct node *list)
 {
         assert(first->next_sibling == NULL);
@@ -124,18 +202,15 @@ void add_child(struct node *parent, struct node *child)
         *p = child;
 }
 
-struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size,
-                                         char *label)
+struct reserve_info *build_reserve_entry(uint64_t address, uint64_t size)
 {
         struct reserve_info *new = xmalloc(sizeof(*new));
 
+        memset(new, 0, sizeof(*new));
+
         new->re.address = address;
         new->re.size = size;
 
-        new->next = NULL;
-
-        new->label = label;
-
         return new;
 }
 
@@ -208,6 +283,60 @@ cell_t propval_cell(struct property *prop)
         return fdt32_to_cpu(*((cell_t *)prop->val.val));
 }
 
+struct property *get_property_by_label(struct node *tree, const char *label,
+                                       struct node **node)
+{
+        struct property *prop;
+        struct node *c;
+
+        *node = tree;
+
+        for_each_property(tree, prop) {
+                struct label *l;
+
+                for_each_label(prop->labels, l)
+                        if (streq(l->label, label))
+                                return prop;
+        }
+
+        for_each_child(tree, c) {
+                prop = get_property_by_label(c, label, node);
+                if (prop)
+                        return prop;
+        }
+
+        *node = NULL;
+        return NULL;
+}
+
+struct marker *get_marker_label(struct node *tree, const char *label,
+                                struct node **node, struct property **prop)
+{
+        struct marker *m;
+        struct property *p;
+        struct node *c;
+
+        *node = tree;
+
+        for_each_property(tree, p) {
+                *prop = p;
+                m = p->val.markers;
+                for_each_marker_of_type(m, LABEL)
+                        if (streq(m->ref, label))
+                                return m;
+        }
+
+        for_each_child(tree, c) {
+                m = get_marker_label(c, label, node, prop);
+                if (m)
+                        return m;
+        }
+
+        *prop = NULL;
+        *node = NULL;
+        return NULL;
+}
+
 struct node *get_subnode(struct node *node, const char *nodename)
 {
         struct node *child;
@@ -245,11 +374,13 @@ struct node *get_node_by_path(struct node *tree, const char *path)
 struct node *get_node_by_label(struct node *tree, const char *label)
 {
         struct node *child, *node;
+        struct label *l;
 
         assert(label && (strlen(label) > 0));
 
-        if (tree->label && streq(tree->label, label))
-                return tree;
+        for_each_label(tree->labels, l)
+                if (streq(l->label, label))
+                        return tree;
 
         for_each_child(tree, child) {
                 node = get_node_by_label(child, label);
@@ -293,16 +424,186 @@ cell_t get_node_phandle(struct node *root, struct node *node)
         if ((node->phandle != 0) && (node->phandle != -1))
                 return node->phandle;
 
-        assert(! get_property(node, "linux,phandle"));
-
         while (get_node_by_phandle(root, phandle))
                 phandle++;
 
         node->phandle = phandle;
-        add_property(node,
-                     build_property("linux,phandle",
-                                    data_append_cell(empty_data, phandle),
-                                    NULL));
+
+        if (!get_property(node, "linux,phandle")
+            && (phandle_format & PHANDLE_LEGACY))
+                add_property(node,
+                             build_property("linux,phandle",
+                                            data_append_cell(empty_data, phandle)));
+
+        if (!get_property(node, "phandle")
+            && (phandle_format & PHANDLE_EPAPR))
+                add_property(node,
+                             build_property("phandle",
+                                            data_append_cell(empty_data, phandle)));
+
+        /* If the node *does* have a phandle property, we must
+         * be dealing with a self-referencing phandle, which will be
+         * fixed up momentarily in the caller */
 
         return node->phandle;
 }
+
+uint32_t guess_boot_cpuid(struct node *tree)
+{
+        struct node *cpus, *bootcpu;
+        struct property *reg;
+
+        cpus = get_node_by_path(tree, "/cpus");
+        if (!cpus)
+                return 0;
+
+
+        bootcpu = cpus->children;
+        if (!bootcpu)
+                return 0;
+
+        reg = get_property(bootcpu, "reg");
+        if (!reg || (reg->val.len != sizeof(uint32_t)))
+                return 0;
+
+        /* FIXME: Sanity check node? */
+
+        return propval_cell(reg);
+}
+
+static int cmp_reserve_info(const void *ax, const void *bx)
+{
+        const struct reserve_info *a, *b;
+
+        a = *((const struct reserve_info * const *)ax);
+        b = *((const struct reserve_info * const *)bx);
+
+        if (a->re.address < b->re.address)
+                return -1;
+        else if (a->re.address > b->re.address)
+                return 1;
+        else if (a->re.size < b->re.size)
+                return -1;
+        else if (a->re.size > b->re.size)
+                return 1;
+        else
+                return 0;
+}
+
+static void sort_reserve_entries(struct boot_info *bi)
+{
+        struct reserve_info *ri, **tbl;
+        int n = 0, i = 0;
+
+        for (ri = bi->reservelist;
+             ri;
+             ri = ri->next)
+                n++;
+
+        if (n == 0)
+                return;
+
+        tbl = xmalloc(n * sizeof(*tbl));
+
+        for (ri = bi->reservelist;
+             ri;
+             ri = ri->next)
+                tbl[i++] = ri;
+
+        qsort(tbl, n, sizeof(*tbl), cmp_reserve_info);
+
+        bi->reservelist = tbl[0];
+        for (i = 0; i < (n-1); i++)
+                tbl[i]->next = tbl[i+1];
+        tbl[n-1]->next = NULL;
+
+        free(tbl);
+}
+
+static int cmp_prop(const void *ax, const void *bx)
+{
+        const struct property *a, *b;
+
+        a = *((const struct property * const *)ax);
+        b = *((const struct property * const *)bx);
+
+        return strcmp(a->name, b->name);
+}
+
+static void sort_properties(struct node *node)
+{
+        int n = 0, i = 0;
+        struct property *prop, **tbl;
+
+        for_each_property(node, prop)
+                n++;
+
+        if (n == 0)
+                return;
+
+        tbl = xmalloc(n * sizeof(*tbl));
+
+        for_each_property(node, prop)
+                tbl[i++] = prop;
+
+        qsort(tbl, n, sizeof(*tbl), cmp_prop);
+
+        node->proplist = tbl[0];
+        for (i = 0; i < (n-1); i++)
+                tbl[i]->next = tbl[i+1];
+        tbl[n-1]->next = NULL;
+
+        free(tbl);
+}
+
+static int cmp_subnode(const void *ax, const void *bx)
+{
+        const struct node *a, *b;
+
+        a = *((const struct node * const *)ax);
+        b = *((const struct node * const *)bx);
+
+        return strcmp(a->name, b->name);
+}
+
+static void sort_subnodes(struct node *node)
+{
+        int n = 0, i = 0;
+        struct node *subnode, **tbl;
+
+        for_each_child(node, subnode)
+                n++;
+
+        if (n == 0)
+                return;
+
+        tbl = xmalloc(n * sizeof(*tbl));
+
+        for_each_child(node, subnode)
+                tbl[i++] = subnode;
+
+        qsort(tbl, n, sizeof(*tbl), cmp_subnode);
+
+        node->children = tbl[0];
+        for (i = 0; i < (n-1); i++)
+                tbl[i]->next_sibling = tbl[i+1];
+        tbl[n-1]->next_sibling = NULL;
+
+        free(tbl);
+}
+
+static void sort_node(struct node *node)
+{
+        struct node *c;
+
+        sort_properties(node);
+        sort_subnodes(node);
+        for_each_child(node, c)
+                sort_node(c);
+}
+
+void sort_tree(struct boot_info *bi)
+{
+        sort_reserve_entries(bi);
+        sort_node(bi->dt);
+}