6 files changed, 88 insertions, 108 deletions

diff --git a/drivers/mfd/vexpress-sysreg.c b/drivers/mfd/vexpress-sysreg.c
index 9e21e4fc9599..8f43ab8fd2d6 100644
--- a/drivers/mfd/vexpress-sysreg.c
+++ b/drivers/mfd/vexpress-sysreg.c
@@ -223,7 +223,7 @@ static int vexpress_sysreg_probe(struct platform_device *pdev)
         vexpress_config_set_master(vexpress_sysreg_get_master());
 
         /* Confirm board type against DT property, if available */
-        if (of_property_read_u32(of_allnodes, "arm,hbi", &dt_hbi) == 0) {
+        if (of_property_read_u32(of_root, "arm,hbi", &dt_hbi) == 0) {
                 u32 id = vexpress_get_procid(VEXPRESS_SITE_MASTER);
                 u32 hbi = (id >> SYS_PROCIDx_HBI_SHIFT) & SYS_HBI_MASK;
 
diff --git a/drivers/of/base.c b/drivers/of/base.c
index 3823edf2d012..1f61a908a767 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -32,8 +32,8 @@
 
 LIST_HEAD(aliases_lookup);
 
-struct device_node *of_allnodes;
-EXPORT_SYMBOL(of_allnodes);
+struct device_node *of_root;
+EXPORT_SYMBOL(of_root);
 struct device_node *of_chosen;
 struct device_node *of_aliases;
 struct device_node *of_stdout;
@@ -48,7 +48,7 @@ struct kset *of_kset;
  */
 DEFINE_MUTEX(of_mutex);
 
-/* use when traversing tree through the allnext, child, sibling,
+/* use when traversing tree through the child, sibling,
  * or parent members of struct device_node.
  */
 DEFINE_RAW_SPINLOCK(devtree_lock);
@@ -204,7 +204,7 @@ static int __init of_init(void)
         mutex_unlock(&of_mutex);
 
         /* Symlink in /proc as required by userspace ABI */
-        if (of_allnodes)
+        if (of_root)
                 proc_symlink("device-tree", NULL, "/sys/firmware/devicetree/base");
 
         return 0;
@@ -245,6 +245,23 @@ struct property *of_find_property(const struct device_node *np,
 }
 EXPORT_SYMBOL(of_find_property);
 
+struct device_node *__of_find_all_nodes(struct device_node *prev)
+{
+        struct device_node *np;
+        if (!prev) {
+                np = of_root;
+        } else if (prev->child) {
+                np = prev->child;
+        } else {
+                /* Walk back up looking for a sibling, or the end of the structure */
+                np = prev;
+                while (np->parent && !np->sibling)
+                        np = np->parent;
+                np = np->sibling; /* Might be null at the end of the tree */
+        }
+        return np;
+}
+
 /**
  * of_find_all_nodes - Get next node in global list
  * @prev:       Previous node or NULL to start iteration
@@ -259,10 +276,8 @@ struct device_node *of_find_all_nodes(struct device_node *prev)
         unsigned long flags;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = prev ? prev->allnext : of_allnodes;
-        for (; np != NULL; np = np->allnext)
-                if (of_node_get(np))
-                        break;
+        np = __of_find_all_nodes(prev);
+        of_node_get(np);
         of_node_put(prev);
         raw_spin_unlock_irqrestore(&devtree_lock, flags);
         return np;
@@ -736,7 +751,7 @@ struct device_node *of_find_node_by_path(const char *path)
         unsigned long flags;
 
         if (strcmp(path, "/") == 0)
-                return of_node_get(of_allnodes);
+                return of_node_get(of_root);
 
         /* The path could begin with an alias */
         if (*path != '/') {
@@ -761,7 +776,7 @@ struct device_node *of_find_node_by_path(const char *path)
         /* Step down the tree matching path components */
         raw_spin_lock_irqsave(&devtree_lock, flags);
         if (!np)
-                np = of_node_get(of_allnodes);
+                np = of_node_get(of_root);
         while (np && *path == '/') {
                 path++; /* Increment past '/' delimiter */
                 np = __of_find_node_by_path(np, path);
@@ -790,8 +805,7 @@ struct device_node *of_find_node_by_name(struct device_node *from,
         unsigned long flags;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = from ? from->allnext : of_allnodes;
-        for (; np; np = np->allnext)
+        for_each_of_allnodes_from(from, np)
                 if (np->name && (of_node_cmp(np->name, name) == 0)
                     && of_node_get(np))
                         break;
@@ -820,8 +834,7 @@ struct device_node *of_find_node_by_type(struct device_node *from,
         unsigned long flags;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = from ? from->allnext : of_allnodes;
-        for (; np; np = np->allnext)
+        for_each_of_allnodes_from(from, np)
                 if (np->type && (of_node_cmp(np->type, type) == 0)
                     && of_node_get(np))
                         break;
@@ -852,12 +865,10 @@ struct device_node *of_find_compatible_node(struct device_node *from,
         unsigned long flags;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = from ? from->allnext : of_allnodes;
-        for (; np; np = np->allnext) {
+        for_each_of_allnodes_from(from, np)
                 if (__of_device_is_compatible(np, compatible, type, NULL) &&
                     of_node_get(np))
                         break;
-        }
         of_node_put(from);
         raw_spin_unlock_irqrestore(&devtree_lock, flags);
         return np;
@@ -884,8 +895,7 @@ struct device_node *of_find_node_with_property(struct device_node *from,
         unsigned long flags;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = from ? from->allnext : of_allnodes;
-        for (; np; np = np->allnext) {
+        for_each_of_allnodes_from(from, np) {
                 for (pp = np->properties; pp; pp = pp->next) {
                         if (of_prop_cmp(pp->name, prop_name) == 0) {
                                 of_node_get(np);
@@ -967,8 +977,7 @@ struct device_node *of_find_matching_node_and_match(struct device_node *from,
                 *match = NULL;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        np = from ? from->allnext : of_allnodes;
-        for (; np; np = np->allnext) {
+        for_each_of_allnodes_from(from, np) {
                 m = __of_match_node(matches, np);
                 if (m && of_node_get(np)) {
                         if (match)
@@ -1025,7 +1034,7 @@ struct device_node *of_find_node_by_phandle(phandle handle)
                 return NULL;
 
         raw_spin_lock_irqsave(&devtree_lock, flags);
-        for (np = of_allnodes; np; np = np->allnext)
+        for_each_of_allnodes(np)
                 if (np->phandle == handle)
                         break;
         of_node_get(np);
diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
index f297891d8529..da2509d639c8 100644
--- a/drivers/of/dynamic.c
+++ b/drivers/of/dynamic.c
@@ -117,8 +117,6 @@ void __of_attach_node(struct device_node *np)
 
         np->child = NULL;
         np->sibling = np->parent->child;
-        np->allnext = np->parent->allnext;
-        np->parent->allnext = np;
         np->parent->child = np;
         of_node_clear_flag(np, OF_DETACHED);
 }
@@ -154,17 +152,6 @@ void __of_detach_node(struct device_node *np)
         if (WARN_ON(!parent))
                 return;
 
-        if (of_allnodes == np)
-                of_allnodes = np->allnext;
-        else {
-                struct device_node *prev;
-                for (prev = of_allnodes;
-                     prev->allnext != np;
-                     prev = prev->allnext)
-                        ;
-                prev->allnext = np->allnext;
-        }
-
         if (parent->child == np)
                 parent->child = np->sibling;
         else {
diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
index d1ffca8b34ea..1d30b9f96466 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -145,15 +145,15 @@ static void *unflatten_dt_alloc(void **mem, unsigned long size,
  * @mem: Memory chunk to use for allocating device nodes and properties
  * @p: pointer to node in flat tree
  * @dad: Parent struct device_node
- * @allnextpp: pointer to ->allnext from last allocated device_node
  * @fpsize: Size of the node path up at the current depth.
  */
 static void * unflatten_dt_node(void *blob,
                                 void *mem,
                                 int *poffset,
                                 struct device_node *dad,
-                                struct device_node ***allnextpp,
-                                unsigned long fpsize)
+                                struct device_node **nodepp,
+                                unsigned long fpsize,
+                                bool dryrun)
 {
         const __be32 *p;
         struct device_node *np;
@@ -200,7 +200,7 @@ static void * unflatten_dt_node(void *blob,
 
         np = unflatten_dt_alloc(&mem, sizeof(struct device_node) + allocl,
                                 __alignof__(struct device_node));
-        if (allnextpp) {
+        if (!dryrun) {
                 char *fn;
                 of_node_init(np);
                 np->full_name = fn = ((char *)np) + sizeof(*np);
@@ -222,8 +222,6 @@ static void * unflatten_dt_node(void *blob,
                 memcpy(fn, pathp, l);
 
                 prev_pp = &np->properties;
-                **allnextpp = np;
-                *allnextpp = &np->allnext;
                 if (dad != NULL) {
                         np->parent = dad;
                         /* we temporarily use the next field as `last_child'*/
@@ -254,7 +252,7 @@ static void * unflatten_dt_node(void *blob,
                         has_name = 1;
                 pp = unflatten_dt_alloc(&mem, sizeof(struct property),
                                         __alignof__(struct property));
-                if (allnextpp) {
+                if (!dryrun) {
                         /* We accept flattened tree phandles either in
                          * ePAPR-style "phandle" properties, or the
                          * legacy "linux,phandle" properties.  If both
@@ -296,7 +294,7 @@ static void * unflatten_dt_node(void *blob,
                 sz = (pa - ps) + 1;
                 pp = unflatten_dt_alloc(&mem, sizeof(struct property) + sz,
                                         __alignof__(struct property));
-                if (allnextpp) {
+                if (!dryrun) {
                         pp->name = "name";
                         pp->length = sz;
                         pp->value = pp + 1;
@@ -308,7 +306,7 @@ static void * unflatten_dt_node(void *blob,
                                 (char *)pp->value);
                 }
         }
-        if (allnextpp) {
+        if (!dryrun) {
                 *prev_pp = NULL;
                 np->name = of_get_property(np, "name", NULL);
                 np->type = of_get_property(np, "device_type", NULL);
@@ -324,11 +322,13 @@ static void * unflatten_dt_node(void *blob,
         if (depth < 0)
                 depth = 0;
         while (*poffset > 0 && depth > old_depth)
-                mem = unflatten_dt_node(blob, mem, poffset, np, allnextpp,
-                                        fpsize);
+                mem = unflatten_dt_node(blob, mem, poffset, np, NULL,
+                                        fpsize, dryrun);
 
         if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
                 pr_err("unflatten: error %d processing FDT\n", *poffset);
+        if (nodepp)
+                *nodepp = np;
 
         return mem;
 }
@@ -352,7 +352,6 @@ static void __unflatten_device_tree(void *blob,
         unsigned long size;
         int start;
         void *mem;
-        struct device_node **allnextp = mynodes;
 
         pr_debug(" -> unflatten_device_tree()\n");
 
@@ -373,7 +372,7 @@ static void __unflatten_device_tree(void *blob,
 
         /* First pass, scan for size */
         start = 0;
-        size = (unsigned long)unflatten_dt_node(blob, NULL, &start, NULL, NULL, 0);
+        size = (unsigned long)unflatten_dt_node(blob, NULL, &start, NULL, NULL, 0, true);
         size = ALIGN(size, 4);
 
         pr_debug("  size is %lx, allocating...\n", size);
@@ -388,11 +387,10 @@ static void __unflatten_device_tree(void *blob,
 
         /* Second pass, do actual unflattening */
         start = 0;
-        unflatten_dt_node(blob, mem, &start, NULL, &allnextp, 0);
+        unflatten_dt_node(blob, mem, &start, NULL, mynodes, 0, false);
         if (be32_to_cpup(mem + size) != 0xdeadbeef)
                 pr_warning("End of tree marker overwritten: %08x\n",
                            be32_to_cpup(mem + size));
-        *allnextp = NULL;
 
         pr_debug(" <- unflatten_device_tree()\n");
 }
@@ -1041,7 +1039,7 @@ bool __init early_init_dt_scan(void *params)
  */
 void __init unflatten_device_tree(void)
 {
-        __unflatten_device_tree(initial_boot_params, &of_allnodes,
+        __unflatten_device_tree(initial_boot_params, &of_root,
                                 early_init_dt_alloc_memory_arch);
 
         /* Get pointer to "/chosen" and "/aliases" nodes for use everywhere */
diff --git a/drivers/of/pdt.c b/drivers/of/pdt.c
index 36b4035881b0..d2acae825af9 100644
--- a/drivers/of/pdt.c
+++ b/drivers/of/pdt.c
@@ -25,8 +25,7 @@
 
 static struct of_pdt_ops *of_pdt_prom_ops __initdata;
 
-void __initdata (*of_pdt_build_more)(struct device_node *dp,
-                struct device_node ***nextp);
+void __initdata (*of_pdt_build_more)(struct device_node *dp);
 
 #if defined(CONFIG_SPARC)
 unsigned int of_pdt_unique_id __initdata;
@@ -192,8 +191,7 @@ static struct device_node * __init of_pdt_create_node(phandle node,
 }
 
 static struct device_node * __init of_pdt_build_tree(struct device_node *parent,
-                                                   phandle node,
-                                                   struct device_node ***nextp)
+                                                   phandle node)
 {
         struct device_node *ret = NULL, *prev_sibling = NULL;
         struct device_node *dp;
@@ -210,16 +208,12 @@ static struct device_node * __init of_pdt_build_tree(struct device_node *parent,
                         ret = dp;
                 prev_sibling = dp;
 
-                *(*nextp) = dp;
-                *nextp = &dp->allnext;
-
                 dp->full_name = of_pdt_build_full_name(dp);
 
-                dp->child = of_pdt_build_tree(dp,
-                                of_pdt_prom_ops->getchild(node), nextp);
+                dp->child = of_pdt_build_tree(dp, of_pdt_prom_ops->getchild(node));
 
                 if (of_pdt_build_more)
-                        of_pdt_build_more(dp, nextp);
+                        of_pdt_build_more(dp);
 
                 node = of_pdt_prom_ops->getsibling(node);
         }
@@ -234,20 +228,17 @@ static void * __init kernel_tree_alloc(u64 size, u64 align)
 
 void __init of_pdt_build_devicetree(phandle root_node, struct of_pdt_ops *ops)
 {
-        struct device_node **nextp;
-
         BUG_ON(!ops);
         of_pdt_prom_ops = ops;
 
-        of_allnodes = of_pdt_create_node(root_node, NULL);
+        of_root = of_pdt_create_node(root_node, NULL);
 #if defined(CONFIG_SPARC)
-        of_allnodes->path_component_name = "";
+        of_root->path_component_name = "";
 #endif
-        of_allnodes->full_name = "/";
+        of_root->full_name = "/";
 
-        nextp = &of_allnodes->allnext;
-        of_allnodes->child = of_pdt_build_tree(of_allnodes,
-                        of_pdt_prom_ops->getchild(of_allnodes->phandle), &nextp);
+        of_root->child = of_pdt_build_tree(of_root,
+                                of_pdt_prom_ops->getchild(of_root->phandle));
 
         /* Get pointer to "/chosen" and "/aliases" nodes for use everywhere */
         of_alias_scan(kernel_tree_alloc);
diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
index 11b873c54a77..bf7d99317a94 100644
--- a/drivers/of/selftest.c
+++ b/drivers/of/selftest.c
@@ -148,7 +148,7 @@ static void __init of_selftest_dynamic(void)
 
 static int __init of_selftest_check_node_linkage(struct device_node *np)
 {
-        struct device_node *child, *allnext_index = np;
+        struct device_node *child;
         int count = 0, rc;
 
         for_each_child_of_node(np, child) {
@@ -158,14 +158,6 @@ static int __init of_selftest_check_node_linkage(struct device_node *np)
                         return -EINVAL;
                 }
 
-                while (allnext_index && allnext_index != child)
-                        allnext_index = allnext_index->allnext;
-                if (allnext_index != child) {
-                        pr_err("Node %s is ordered differently in sibling and allnode lists\n",
-                                 child->name);
-                        return -EINVAL;
-                }
-
                 rc = of_selftest_check_node_linkage(child);
                 if (rc < 0)
                         return rc;
@@ -180,12 +172,12 @@ static void __init of_selftest_check_tree_linkage(void)
         struct device_node *np;
         int allnode_count = 0, child_count;
 
-        if (!of_allnodes)
+        if (!of_root)
                 return;
 
         for_each_of_allnodes(np)
                 allnode_count++;
-        child_count = of_selftest_check_node_linkage(of_allnodes);
+        child_count = of_selftest_check_node_linkage(of_root);
 
         selftest(child_count > 0, "Device node data structure is corrupted\n");
         selftest(child_count == allnode_count, "allnodes list size (%i) doesn't match"
@@ -775,33 +767,29 @@ static void update_node_properties(struct device_node *np,
  */
 static int attach_node_and_children(struct device_node *np)
 {
-        struct device_node *next, *root = np, *dup;
+        struct device_node *next, *dup, *child;
 
-        /* skip root node */
-        np = np->child;
-        /* storing a copy in temporary node */
-        dup = np;
+        dup = of_find_node_by_path(np->full_name);
+        if (dup) {
+                update_node_properties(np, dup);
+                return 0;
+        }
 
-        while (dup) {
+        /* Children of the root need to be remembered for removal */
+        if (np->parent == of_root) {
                 if (WARN_ON(last_node_index >= NO_OF_NODES))
                         return -EINVAL;
-                nodes[last_node_index++] = dup;
-                dup = dup->sibling;
+                nodes[last_node_index++] = np;
         }
-        dup = NULL;
 
-        while (np) {
-                next = np->allnext;
-                dup = of_find_node_by_path(np->full_name);
-                if (dup)
-                        update_node_properties(np, dup);
-                else {
-                        np->child = NULL;
-                        if (np->parent == root)
-                                np->parent = of_allnodes;
-                        of_attach_node(np);
-                }
-                np = next;
+        child = np->child;
+        np->child = NULL;
+        np->sibling = NULL;
+        of_attach_node(np);
+        while (child) {
+                next = child->sibling;
+                attach_node_and_children(child);
+                child = next;
         }
 
         return 0;
@@ -846,10 +834,10 @@ static int __init selftest_data_add(void)
                 return -EINVAL;
         }
 
-        if (!of_allnodes) {
+        if (!of_root) {
                 /* enabling flag for removing nodes */
                 selftest_live_tree = true;
-                of_allnodes = selftest_data_node;
+                of_root = selftest_data_node;
 
                 for_each_of_allnodes(np)
                         __of_attach_node_sysfs(np);
@@ -859,7 +847,14 @@ static int __init selftest_data_add(void)
         }
 
         /* attach the sub-tree to live tree */
-        return attach_node_and_children(selftest_data_node);
+        np = selftest_data_node->child;
+        while (np) {
+                struct device_node *next = np->sibling;
+                np->parent = of_root;
+                attach_node_and_children(np);
+                np = next;
+        }
+        return 0;
 }
 
 /**
@@ -889,10 +884,10 @@ static void selftest_data_remove(void)
                 of_node_put(of_chosen);
                 of_aliases = NULL;
                 of_chosen = NULL;
-                for_each_child_of_node(of_allnodes, np)
+                for_each_child_of_node(of_root, np)
                         detach_node_and_children(np);
-                __of_detach_node_sysfs(of_allnodes);
-                of_allnodes = NULL;
+                __of_detach_node_sysfs(of_root);
+                of_root = NULL;
                 return;
         }