On Tue, Nov 18, 2014 at 7:10 AM, Grant Likely <grant.likely@xxxxxxxxxx> wrote: > 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 am using http://git.kernel.org/pub/scm/linux/kernel/git/glikely/linux.git There is no branch linux-next in it. Also, I believe http://git.secretlab.ca/ is not up yet. Please correct. > 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? I think with your suggestions below, it will definitely change. Considering the fact that it is a doubly linked list. First, I try to locate the pre node in the list. If found, then only I call of_node_get() on the next node, and if successful I break. I used found in the loop so that I do not have to manually check the next node is head or not. I can follow another approach, by directly getting the next entry and failing it if it is the head node. > >> + } >> 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. Ok. > >> >> #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
