Re: [PATCH] Patch to improve device tree structure

[Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>]

On 11/28/2014 8:48 AM, Grant Likely wrote:
> On Wed, 19 Nov 2014 11:30:12 -0800
> , Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>  wrote:
>> On 11/19/2014 5:56 AM, Grant Likely wrote:
>>> On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> 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-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>  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-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
>>>>>
>>>>> 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-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>>
>> 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-/MT0OVThwyLZJqsBc5GL+g@public.gmane.org>
>> ---
>>  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-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
> 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-QSEj5FYQhm4dnm+yROfE0A@public.gmane.org>
> Cc: Gaurav Minocha <gaurav.minocha.os-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> Cc: Frank Rowand <frowand.list-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
> ---
>  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-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html