of: Eliminate of_allnodes list
The device tree structure is composed of two lists; the 'allnodes' list
which is a singly linked list containing every node in the tree, and the
child->parent structure where each parent node has a singly linked list
of children. All of the data in the allnodes list can be easily
reproduced with the parent-child lists, so of_allnodes is actually
unnecessary. Remove it entirely which saves a bit of memory and
simplifies the data structure quite a lot.
Signed-off-by: Grant Likely <grant.likely@linaro.org>
Cc: Rob Herring <robh@kernel.org>
Cc: Gaurav Minocha <gaurav.minocha.os@gmail.com>
Cc: Pantelis Antoniou <pantelis@pantelis.antoniou@konsulko.com>
diff --git a/drivers/mfd/vexpress-sysreg.c b/drivers/mfd/vexpress-sysreg.c
index 9e21e4f..8f43ab8 100644
--- a/drivers/mfd/vexpress-sysreg.c
+++ b/drivers/mfd/vexpress-sysreg.c
@@ -223,7 +223,7 @@
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 3823edf..1f61a90 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 @@
*/
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 @@
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 @@
}
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 @@
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 @@
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 @@
/* 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 @@
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 @@
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 @@
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 @@
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 @@
*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 @@
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 f297891..da2509d 100644
--- a/drivers/of/dynamic.c
+++ b/drivers/of/dynamic.c
@@ -117,8 +117,6 @@
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 @@
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 d1ffca8..1d30b9f 100644
--- a/drivers/of/fdt.c
+++ b/drivers/of/fdt.c
@@ -145,15 +145,15 @@
* @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 @@
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 @@
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 @@
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 @@
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 @@
(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 @@
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 @@
unsigned long size;
int start;
void *mem;
- struct device_node **allnextp = mynodes;
pr_debug(" -> unflatten_device_tree()\n");
@@ -373,7 +372,7 @@
/* 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 @@
/* 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 @@
*/
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 36b4035..d2acae8 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_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 @@
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 @@
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 11b873c..bf7d993 100644
--- a/drivers/of/selftest.c
+++ b/drivers/of/selftest.c
@@ -148,7 +148,7 @@
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 @@
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 @@
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 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 @@
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 @@
}
/* 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 @@
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;
}