On Sun, Nov 23, 2014 at 5:22 PM, Gaurav Minocha
<[email protected]> wrote:
> On Tue, Nov 18, 2014 at 7:10 AM, Grant Likely <[email protected]> wrote:
>> On Sun, 16 Nov 2014 20:52:56 -0800
>> , Gaurav Minocha <[email protected]>
>> 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 <[email protected]>
>>
>> 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
