Re: [PATCH] Patch to improve device tree structure

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

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 */
--
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