On 11/28/2014 8:48 AM, Grant Likely wrote:
> On Wed, 19 Nov 2014 11:30:12 -0800
> , Frank Rowand <frowand.list@xxxxxxxxx>
> wrote:
>> On 11/19/2014 5:56 AM, Grant Likely wrote:
>>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list@xxxxxxxxx> wrote:
>>>> On 11/18/2014 7:10 AM, Grant Likely 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'll make comments below where still relevant.
>>>>
>>>> Grant,
>>>>
>>>> My first reaction to this patch was that moving to using struct list_head
>>>> made the code less readable plus increased the size of struct device_node.
>>>>
>>>> I reworked the changes to drivers/of/base.c to see if I could make
>>>> it a little more readable. And I see below that you also have some
>>>> suggestions that make it more readable.
>>>>
>>>> Even after that, I'm still feeling that the gain of moving to a more
>>>> standard list data type might not be greater than the downsides in
>>>> terms of readability and space. The current list implementation does
>>>> seem like a decent fit to the problem space.
>>>
>>> Moving to list_head has a couple of nice benefits. The prime
>>> motification is that using a standard list_head means that the OF code
>>> can be migrated to use the standard rcu operations and get rid of manual
>>> of_node_{get,put} management in the majority of code paths.
>>
>> Oh yeah, I remember you mentioning that before. That is what was missing
>> from Gaurav's patch header, explaining the value of the change. If this
>> is the end goal, then I think it would be valuable to add a second patch
>> to the series that shows what the actual changes for rcu will be so that
>> the cost vs benefit of the end result can be evaluated.
>>
>>
>>> A second reason to do this is it becomes easy to add nodes to the end of
>>> the list instead of the beginning. It's a small thing, but it makes
>>> unflattening simpler.
>>
>> Not a big change. In the unflatten_dt_node() part of the patch, the
>> result was 4 lines deleted, 3 lines added. With my attached patch to
>> remove the next field, it would have been 8 lines deleted, 3 lines
>> added -- thus list_head is an even greater simplification. But still
>> tiny.
>>
>>
>>> I've also considered switching to a hlist_head/hlist_node to keep the
>>> footprint the same.* With an hlist_head the cost is a wash, but looses
>>> the ability to do O(1) addition to the end of the list.
>>>
>>> * Gaurav's patch removes the *child and *sibling pointers, but doesn't
>>> remove the *next pointer which can also be dropped. So, three pointers
>>> get dropped from the structure. Using list_head adds 4 pointers (Net
>>> +1). hlist_head adds 3 (Net 0).
>>
>> I include a patch below to also drop the *next pointer. Not to actually
>> propose submitting the patch, but to suggest that Gaurav's patch should be
>> counted as a net of +2 pointers. I expect that you will accept either a
>> list_head of an hlist_head patch, but if you do not then I will submit the
>> below patch to remove *next or a patch to rename *next to match the actual
>> usage of the field.
>>
>> I still do not have a strong opinion, but I am still feeling that the gain
>> probably does not outweigh the cost.
>>
>> -Frank
>>
>>>
>>> g.
>>>
>>
>> From: Frank Rowand <frank.rowand@xxxxxxxxxxxxxx>
>>
>> Decrease size of struct device_node by one pointer.
>> The pointer is only used during the unflattening of the
>> device tree at boot.
>>
>> The cost of removing the pointer is chasing through the
>> sibling list to add new nodes instead of using the
>> cached 'last_child'. The cost is expected to be in the
>> noise level.
>>
>> Signed-off-by: Frank Rowand <frank.rowand@xxxxxxxxxxxxxx>
>> ---
>> drivers/of/fdt.c | 14 +++++++++-----
>> include/linux/of.h | 1 -
>> 2 files changed, 9 insertions(+), 6 deletions(-)
>>
>> Index: b/include/linux/of.h
>> ===================================================================
>> --- a/include/linux/of.h
>> +++ b/include/linux/of.h
>> @@ -55,7 +55,6 @@ struct device_node {
>> 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 kobject kobj;
>> unsigned long _flags;
>> Index: b/drivers/of/fdt.c
>> ===================================================================
>> --- a/drivers/of/fdt.c
>> +++ b/drivers/of/fdt.c
>> @@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl
>> *allnextpp = &np->allnext;
>> if (dad != NULL) {
>> np->parent = dad;
>> - /* we temporarily use the next field as `last_child'*/
>> - if (dad->next == NULL)
>> + if (dad->child == NULL)
>> dad->child = np;
>> - else
>> - dad->next->sibling = np;
>> - dad->next = np;
>> + else {
>> + struct device_node *next;
>> +
>> + next = dad->child;
>> + while (next->sibling)
>> + next = next->sibling;
>> + next->sibling = np;
>> + }
>> }
>> }
>> /* process properties */
>
> Instead of keeping it always in order, what about reordering the whole
> list after all the nodes at a given level are unflattened? That would
> avoid traversing the entire sibling list on every node addition. Like
> this:
Seems pretty close to a wash to me. Either one would work. Though
mine would benefit from the comment you added in yours.
-Frank
>
> g.
>
>>From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001
> From: Grant Likely <grant.likely@xxxxxxxxxx>
> Date: Fri, 28 Nov 2014 16:03:33 +0000
> Subject: [PATCH] of: Drop ->next pointer from struct device_node
>
> The ->next pointer in struct device_node is a hanger-on from when it was
> used to iterate over the whole tree by a particular device_type property
> value. Those days are long over, but the fdt unflattening code still
> uses it to put nodes in the unflattened tree into the same order as node
> in the flat tree. By reworking the unflattening code to reverse the list
> after unflattening all the children of a node, the pointer can be
> dropped which gives a small amount of memory savings.
>
> Signed-off-by: Grant Likely <grant.likely@xxxxxxxxxx>
> Cc: Gaurav Minocha <gaurav.minocha.os@xxxxxxxxx>
> Cc: Frank Rowand <frowand.list@xxxxxxxxx>
> ---
> drivers/of/fdt.c | 24 ++++++++++++++++++------
> include/linux/of.h | 1 -
> 2 files changed, 18 insertions(+), 7 deletions(-)
>
> diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c
> index 7f6ee31d5650..a41f9fdb1aa0 100644
> --- a/drivers/of/fdt.c
> +++ b/drivers/of/fdt.c
> @@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob,
> prev_pp = &np->properties;
> 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;
> - dad->next = np;
> + np->sibling = dad->child;
> + dad->child = np;
> }
> }
> /* process properties */
> @@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob,
>
> if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND)
> pr_err("unflatten: error %d processing FDT\n", *poffset);
> +
> + /*
> + * Reverse the child list. Some drivers assumes node order matches .dts
> + * node order
> + */
> + if (!dryrun && np->child) {
> + struct device_node *child = np->child;
> + np->child = NULL;
> + while (child) {
> + struct device_node *next = child->sibling;
> + child->sibling = np->child;
> + np->child = child;
> + child = next;
> + }
> + }
> +
> if (nodepp)
> *nodepp = np;
>
> diff --git a/include/linux/of.h b/include/linux/of.h
> index 8b021db3e16e..3f0f0ffbd5e5 100644
> --- a/include/linux/of.h
> +++ b/include/linux/of.h
> @@ -56,7 +56,6 @@ struct device_node {
> struct device_node *parent;
> struct device_node *child;
> struct device_node *sibling;
> - struct device_node *next; /* next device of same type */
> struct kobject kobj;
> unsigned long _flags;
> void *data;
>
--
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
