On Sun, Nov 23, 2014 at 5:22 PM, Gaurav Minocha <gaurav.minocha.os@xxxxxxxxx> wrote: > 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. > My bad! I can see your commits present in the next branch. I will send you a revised patch soon. Thanks! >> 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
