On Sun, 16 Nov 2014 20:52:56 -0800
, Gaurav Minocha <gaurav.minocha.os@xxxxxxxxx>
wrote:
> This patch improves the implementation of device tree structure.
>
> Traditional child and sibling linked list in device tree structure
> is removed and is replaced by list_head (i.e. circular doubly linked
> list) already available in Linux kernel.
>
> Signed-off-by: Gaurav Minocha <gaurav.minocha.os@xxxxxxxxx>
Hi Gaurav,
So, after you've done this work, I need to you rebase it (and of course
it is non-trivial) onto linux-next. I've already got a patch queued up
which gets rid of the of_allnodes/allnext list which will have conflicts
with this patch.
I'll make comments below where still relevant.
> ---
> drivers/of/base.c | 36 ++++++++++----
> drivers/of/dynamic.c | 18 ++-----
> drivers/of/fdt.c | 7 ++-
> drivers/of/selftest.c | 130 +++++++++++++++++++++++---------------------------
> include/linux/of.h | 4 +-
> 5 files changed, 97 insertions(+), 98 deletions(-)
>
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index 2305dc0..7acaeca 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -603,16 +603,25 @@ EXPORT_SYMBOL(of_get_next_parent);
> static struct device_node *__of_get_next_child(const struct device_node *node,
> struct device_node *prev)
> {
> - struct device_node *next;
> + struct device_node *next = NULL, *np;
> + struct list_head *pos;
> + int found = 0;
>
> if (!node)
> return NULL;
>
> - next = prev ? prev->sibling : node->child;
> - for (; next; next = next->sibling)
> - if (of_node_get(next))
> - break;
> + // move through the children list, and find the next node
> + list_for_each(pos, &node->children) {
> + np = list_entry(pos, struct device_node, siblings);
> + if ((!prev || (found == 1)) && of_node_get(np)) {
> + next = np;
> + break;
> + }
> + if (prev && strcmp(np->full_name, prev->full_name) == 0)
> + found = 1;
What is this 'found' stuff about? Why is this in the loop?
> + }
> of_node_put(prev);
Most of this code can be eliminated by using list_for_each_entry().
Actually, the use of a loop here in the original code is a little bit
goofy simply because it never actually loops. It always exits on the
first iteration, but it does conveniently calculate the next entry in
the list. The thing to do here is take inspiration from the
list_for_each_entry() implementation and do the following:
if (!prev) {
next = list_first_entry_or_null(&node->children, struct device_node, siblings);
} else if (prev->siblings.next != &node->children)
next = list_next_entry(prev, siblings);
} else {
next = NULL;
}
> +
> return next;
> }
> #define __for_each_child_of_node(parent, child) \
> @@ -651,22 +660,29 @@ EXPORT_SYMBOL(of_get_next_child);
> struct device_node *of_get_next_available_child(const struct device_node *node,
> struct device_node *prev)
> {
> - struct device_node *next;
> + struct device_node *next = NULL, *np;
> + struct list_head *pos;
> unsigned long flags;
> + int found = 0;
>
> if (!node)
> return NULL;
>
> raw_spin_lock_irqsave(&devtree_lock, flags);
> - next = prev ? prev->sibling : node->child;
> - for (; next; next = next->sibling) {
> - if (!__of_device_is_available(next))
> + list_for_each(pos, &node->children) {
Use list_for_each_entry_continue(), but there will be a bit of fiddling
to make sure the first entry in the list is handled correctly. You can
handle this by using list_entry on the &node->children list, but be
careful to never actually dereference that pointer.
> + np = list_entry(pos, struct device_node, siblings);
> + if (!__of_device_is_available(np))
> continue;
> - if (of_node_get(next))
> + if ((!prev || (found == 1)) && of_node_get(np)) {
> + next = np;
> break;
> + }
> + if (prev && strcmp(np->full_name, prev->full_name) == 0)
> + found = 1;
> }
> of_node_put(prev);
> raw_spin_unlock_irqrestore(&devtree_lock, flags);
> +
> return next;
> }
> EXPORT_SYMBOL(of_get_next_available_child);
> diff --git a/drivers/of/dynamic.c b/drivers/of/dynamic.c
> index f297891..3ffc726 100644
> --- a/drivers/of/dynamic.c
> +++ b/drivers/of/dynamic.c
> @@ -115,11 +115,12 @@ void __of_attach_node(struct device_node *np)
> phandle = __of_get_property(np, "ibm,phandle", &sz);
> np->phandle = (phandle && (sz >= 4)) ? be32_to_cpup(phandle) : 0;
>
> - np->child = NULL;
> - np->sibling = np->parent->child;
> + INIT_LIST_HEAD(&np->siblings);
> + INIT_LIST_HEAD(&np->children);
> + list_add_tail(&(np->siblings), &(np->parent->children));
> +
> np->allnext = np->parent->allnext;
> np->parent->allnext = np;
> - np->parent->child = np;
> of_node_clear_flag(np, OF_DETACHED);
> }
>
> @@ -165,16 +166,7 @@ void __of_detach_node(struct device_node *np)
> prev->allnext = np->allnext;
> }
>
> - if (parent->child == np)
> - parent->child = np->sibling;
> - else {
> - struct device_node *prevsib;
> - for (prevsib = np->parent->child;
> - prevsib->sibling != np;
> - prevsib = prevsib->sibling)
> - ;
> - prevsib->sibling = np->sibling;
> - }
> + list_del(&np->siblings);
>
> of_node_set_flag(np, OF_DETACHED);
> }
> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
> index d1ffca8..4cf2356 100644
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -224,13 +224,12 @@ static void * unflatten_dt_node(void *blob,
> prev_pp = &np->properties;
> **allnextpp = np;
> *allnextpp = &np->allnext;
> + INIT_LIST_HEAD(&np->siblings);
> + INIT_LIST_HEAD(&np->children);
> if (dad != NULL) {
> np->parent = dad;
> /* we temporarily use the next field as `last_child'*/
> - if (dad->next == NULL)
> - dad->child = np;
> - else
> - dad->next->sibling = np;
> + list_add_tail(&(np->siblings), &(dad->children));
> dad->next = np;
> }
> }
> diff --git a/drivers/of/selftest.c b/drivers/of/selftest.c
> index 7800127..8ec8a22 100644
> --- a/drivers/of/selftest.c
> +++ b/drivers/of/selftest.c
> @@ -25,10 +25,11 @@ static struct selftest_results {
> int failed;
> } selftest_results;
>
> -#define NO_OF_NODES 3
> -static struct device_node *nodes[NO_OF_NODES];
> -static int last_node_index;
> +#define MAX_NODES 50
> +
> +static int no_of_nodes;
> static bool selftest_live_tree;
> +static struct device_node* nodes[MAX_NODES];
I think it's time to rework this structure. Instead of a static list,
the code should figure out how many entries it needs and then kzalloc()
the region.
>
> #define selftest(result, fmt, ...) { \
> if (!(result)) { \
> @@ -417,7 +418,6 @@ static void __init of_selftest_changeset(void)
> n1->parent = parent;
> n2->parent = parent;
> n21->parent = n2;
> - n2->child = n21;
> ppremove = of_find_property(parent, "prop-remove", NULL);
> selftest(ppremove, "failed to find removal prop");
>
> @@ -713,44 +713,34 @@ static void update_node_properties(struct device_node *np,
> child->parent = dup;
> }
>
> -/**
> - * attach_node_and_children - attaches nodes
> - * and its children to live tree
> - *
> - * @np: Node to attach to live tree
> - */
> -static int attach_node_and_children(struct device_node *np)
> -{
> - struct device_node *next, *root = np, *dup;
>
> - /* skip root node */
> - np = np->child;
> - /* storing a copy in temporary node */
> - dup = np;
> +static void populate_node_list(struct device_node *np)
> +{
> + struct list_head *pos;
>
> - while (dup) {
> - if (WARN_ON(last_node_index >= NO_OF_NODES))
> - return -EINVAL;
> - nodes[last_node_index++] = dup;
> - dup = dup->sibling;
> + list_for_each(pos, &np->children) {
> + nodes[no_of_nodes] = list_entry(pos, struct device_node, siblings);
> + populate_node_list(nodes[no_of_nodes++]);
> }
> - dup = NULL;
> +}
>
> - while (np) {
> - next = np->allnext;
> - dup = of_find_node_by_path(np->full_name);
> +static void attach_node_and_children(struct device_node *np)
> +{
> + struct device_node *root = np, *dup, *temp;
> + int i;
> +
> + populate_node_list(np);
> +
> + for (i = 0; i < no_of_nodes && nodes[i]; i++) {
> + temp = nodes[i];
> + if (temp->parent == root)
> + temp->parent = of_allnodes;
> + dup = of_find_node_by_path(temp->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;
> + update_node_properties(temp, dup);
> + else
> + of_attach_node(temp);
> }
> -
> - return 0;
> }
>
> /**
> @@ -764,7 +754,8 @@ static int __init selftest_data_add(void)
> extern uint8_t __dtb_testcases_begin[];
> extern uint8_t __dtb_testcases_end[];
> const int size = __dtb_testcases_end - __dtb_testcases_begin;
> - int rc;
> + struct list_head *pos;
> + int rc, i = 0;
>
> if (!size) {
> pr_warn("%s: No testcase data to attach; not running tests\n",
> @@ -796,65 +787,66 @@ static int __init selftest_data_add(void)
> /* enabling flag for removing nodes */
> selftest_live_tree = true;
> of_allnodes = selftest_data_node;
> + populate_node_list(selftest_data_node);
> +
> + // attach the root node
> + __of_attach_node_sysfs(selftest_data_node);
> +
> + while (i < no_of_nodes && nodes[i])
> + __of_attach_node_sysfs(nodes[i++]);
>
> - for_each_of_allnodes(np)
> - __of_attach_node_sysfs(np);
> of_aliases = of_find_node_by_path("/aliases");
> of_chosen = of_find_node_by_path("/chosen");
> return 0;
> }
>
> + list_for_each(pos, &selftest_data_node->children) {
> + np = list_entry(pos, struct device_node, siblings);
> + np->parent = of_allnodes;
> + }
> +
> +
> /* attach the sub-tree to live tree */
> - return attach_node_and_children(selftest_data_node);
> -}
> + attach_node_and_children(selftest_data_node);
>
> -/**
> - * detach_node_and_children - detaches node
> - * and its children from live tree
> - *
> - * @np: Node to detach from live tree
> - */
> -static void detach_node_and_children(struct device_node *np)
> -{
> - while (np->child)
> - detach_node_and_children(np->child);
> - of_detach_node(np);
> + return 0;
> }
>
> -/**
> - * selftest_data_remove - removes the selftest data
> - * nodes from the live tree
> - */
> static void selftest_data_remove(void)
> {
> - struct device_node *np;
> struct property *prop;
> + struct device_node *np, *temp;
> + int i = no_of_nodes;
>
> if (selftest_live_tree) {
> of_node_put(of_aliases);
> of_node_put(of_chosen);
> of_aliases = NULL;
> of_chosen = NULL;
> - for_each_child_of_node(of_allnodes, np)
> - detach_node_and_children(np);
> + while (i >= 0) {
> + temp = nodes[i--];
> + if (temp)
> + of_detach_node(temp);
> + }
> __of_detach_node_sysfs(of_allnodes);
> of_allnodes = NULL;
> return;
> }
>
> - while (last_node_index >= 0) {
> - if (nodes[last_node_index]) {
> - np = of_find_node_by_path(nodes[last_node_index]->full_name);
> - if (strcmp(np->full_name, "/aliases") != 0) {
> - detach_node_and_children(np);
> - } else {
> - for_each_property_of_node(np, prop) {
> - if (strcmp(prop->name, "testcase-alias") == 0)
> + while (i >= 0) {
> + temp = nodes[i--];
> + if (temp) {
> + if (strcmp(temp->full_name, "/aliases") == 0) {
> + for_each_property_of_node(temp, prop) {
> + if (strcmp(prop->name, "testcase-alias") == 0) {
> + np = of_find_node_by_path(temp->full_name);
> of_remove_property(np, prop);
> + }
> }
> }
> + else
> + of_detach_node(temp);
> }
> - last_node_index--;
> }
> }
>
> @@ -865,6 +857,7 @@ static int __init of_selftest(void)
>
> /* adding data for selftest */
> res = selftest_data_add();
> +
> if (res)
> return res;
>
> @@ -891,7 +884,6 @@ static int __init of_selftest(void)
>
> /* removing selftest data from live tree */
> selftest_data_remove();
> -
> /* Double check linkage after removing testcase data */
> of_selftest_check_tree_linkage();
>
> diff --git a/include/linux/of.h b/include/linux/of.h
> index 6545e7a..84c708c 100644
> --- a/include/linux/of.h
> +++ b/include/linux/of.h
> @@ -53,10 +53,10 @@ struct device_node {
> struct property *properties;
> struct property *deadprops; /* removed properties */
> struct device_node *parent;
> - struct device_node *child;
> - struct device_node *sibling;
> struct device_node *next; /* next device of same type */
> struct device_node *allnext; /* next in list of all nodes */
> + struct list_head children;
> + struct list_head siblings;
> struct kobject kobj;
> unsigned long _flags;
> void *data;
> --
> 1.9.1
>
--
To unsubscribe from this list: send the line "unsubscribe devicetree" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
