[PATCH] libfdt: place new nodes & properties after the parent's ones

[PATCH] libfdt: place new nodes & properties after the parent's ones

[Marek Szyprowski]

While applying dt-overlays using libfdt code, the order of the applied
properties and sub-nodes is reversed. This should not be a problem in
ideal world (mainline), but this matters for some vendor specific/custom
dtb files. This can be easily fixed by the little change to libfdt code:
any new properties and sub-nodes should be added after the parent's node
properties and subnodes.

Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
---
 libfdt/fdt_rw.c | 26 ++++++++++++++++++++++----
 1 file changed, 22 insertions(+), 4 deletions(-)

diff --git a/libfdt/fdt_rw.c b/libfdt/fdt_rw.c
index 8795947..88c5930 100644
--- a/libfdt/fdt_rw.c
+++ b/libfdt/fdt_rw.c
@@ -189,19 +189,27 @@ static int fdt_add_property_(void *fdt, int nodeoffset, const char *name,
 			     int len, struct fdt_property **prop)
 {
 	int proplen;
-	int nextoffset;
+	int offset, nextoffset;
 	int namestroff;
 	int err;
 	int allocated;
+	uint32_t tag;
 
 	if ((nextoffset = fdt_check_node_offset_(fdt, nodeoffset)) < 0)
 		return nextoffset;
 
+	/* Try to place the new property after the parent's properties */
+	fdt_next_tag(fdt, nodeoffset, &nextoffset); /* skip the BEGIN_NODE */
+	do {
+		offset = nextoffset;
+		tag = fdt_next_tag(fdt, offset, &nextoffset);
+	} while ((tag == FDT_PROP) || (tag == FDT_NOP));
+
 	namestroff = fdt_find_add_string_(fdt, name, &allocated);
 	if (namestroff < 0)
 		return namestroff;
 
-	*prop = fdt_offset_ptr_w_(fdt, nextoffset);
+	*prop = fdt_offset_ptr_w_(fdt, offset);
 	proplen = sizeof(**prop) + FDT_TAGALIGN(len);
 
 	err = fdt_splice_struct_(fdt, *prop, 0, proplen);
@@ -321,6 +329,7 @@ int fdt_add_subnode_namelen(void *fdt, int parentoffset,
 	struct fdt_node_header *nh;
 	int offset, nextoffset;
 	int nodelen;
+	int depth = 0;
 	int err;
 	uint32_t tag;
 	fdt32_t *endtag;
@@ -333,12 +342,21 @@ int fdt_add_subnode_namelen(void *fdt, int parentoffset,
 	else if (offset != -FDT_ERR_NOTFOUND)
 		return offset;
 
-	/* Try to place the new node after the parent's properties */
+	/* Try to place the new node after the parent's subnodes */
 	fdt_next_tag(fdt, parentoffset, &nextoffset); /* skip the BEGIN_NODE */
 	do {
+again:
 		offset = nextoffset;
 		tag = fdt_next_tag(fdt, offset, &nextoffset);
-	} while ((tag == FDT_PROP) || (tag == FDT_NOP));
+		if (depth && tag == FDT_END_NODE) {
+			depth--;
+			goto again;
+		}
+		if (tag == FDT_BEGIN_NODE) {
+			depth++;
+			goto again;
+		}
+	} while (depth || (tag == FDT_PROP) || (tag == FDT_NOP));
 
 	nh = fdt_offset_ptr_w_(fdt, offset);
 	nodelen = sizeof(*nh) + FDT_TAGALIGN(namelen+1) + FDT_TAGSIZE;
-- 
2.17.1

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 3623 bytes --]

On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
> While applying dt-overlays using libfdt code, the order of the applied
> properties and sub-nodes is reversed. This should not be a problem in
> ideal world (mainline), but this matters for some vendor specific/custom
> dtb files. This can be easily fixed by the little change to libfdt code:
> any new properties and sub-nodes should be added after the parent's node
> properties and subnodes.
> 
> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>

I'm not convinced this is a good idea.

First, anything that relies on the order of properties or subnodes in
a dtb is deeply, fundamentally broken.  That can't even really be a
problem with a dtb file itself, only with the code processing it.

I'm also concerned this could have a negative performance impact,
since it has to skip over a bunch of existing things before adding the
new one.  On the other hand, that may be offset by the fact that it
will reduce the amount of stuff that needs to be memmove()ed later on.

> ---
>  libfdt/fdt_rw.c | 26 ++++++++++++++++++++++----
>  1 file changed, 22 insertions(+), 4 deletions(-)
> 
> diff --git a/libfdt/fdt_rw.c b/libfdt/fdt_rw.c
> index 8795947..88c5930 100644
> --- a/libfdt/fdt_rw.c
> +++ b/libfdt/fdt_rw.c
> @@ -189,19 +189,27 @@ static int fdt_add_property_(void *fdt, int nodeoffset, const char *name,
>  			     int len, struct fdt_property **prop)
>  {
>  	int proplen;
> -	int nextoffset;
> +	int offset, nextoffset;
>  	int namestroff;
>  	int err;
>  	int allocated;
> +	uint32_t tag;
>  
>  	if ((nextoffset = fdt_check_node_offset_(fdt, nodeoffset)) < 0)
>  		return nextoffset;
>  
> +	/* Try to place the new property after the parent's properties */
> +	fdt_next_tag(fdt, nodeoffset, &nextoffset); /* skip the BEGIN_NODE */
> +	do {
> +		offset = nextoffset;
> +		tag = fdt_next_tag(fdt, offset, &nextoffset);
> +	} while ((tag == FDT_PROP) || (tag == FDT_NOP));
> +
>  	namestroff = fdt_find_add_string_(fdt, name, &allocated);
>  	if (namestroff < 0)
>  		return namestroff;
>  
> -	*prop = fdt_offset_ptr_w_(fdt, nextoffset);
> +	*prop = fdt_offset_ptr_w_(fdt, offset);
>  	proplen = sizeof(**prop) + FDT_TAGALIGN(len);
>  
>  	err = fdt_splice_struct_(fdt, *prop, 0, proplen);
> @@ -321,6 +329,7 @@ int fdt_add_subnode_namelen(void *fdt, int parentoffset,
>  	struct fdt_node_header *nh;
>  	int offset, nextoffset;
>  	int nodelen;
> +	int depth = 0;
>  	int err;
>  	uint32_t tag;
>  	fdt32_t *endtag;
> @@ -333,12 +342,21 @@ int fdt_add_subnode_namelen(void *fdt, int parentoffset,
>  	else if (offset != -FDT_ERR_NOTFOUND)
>  		return offset;
>  
> -	/* Try to place the new node after the parent's properties */
> +	/* Try to place the new node after the parent's subnodes */
>  	fdt_next_tag(fdt, parentoffset, &nextoffset); /* skip the BEGIN_NODE */
>  	do {
> +again:
>  		offset = nextoffset;
>  		tag = fdt_next_tag(fdt, offset, &nextoffset);
> -	} while ((tag == FDT_PROP) || (tag == FDT_NOP));
> +		if (depth && tag == FDT_END_NODE) {
> +			depth--;
> +			goto again;
> +		}
> +		if (tag == FDT_BEGIN_NODE) {
> +			depth++;
> +			goto again;
> +		}
> +	} while (depth || (tag == FDT_PROP) || (tag == FDT_NOP));
>  
>  	nh = fdt_offset_ptr_w_(fdt, offset);
>  	nodelen = sizeof(*nh) + FDT_TAGALIGN(namelen+1) + FDT_TAGSIZE;

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[Marek Szyprowski]

Hi David,

On 05.02.2020 06:45, David Gibson wrote:
> On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
>> While applying dt-overlays using libfdt code, the order of the applied
>> properties and sub-nodes is reversed. This should not be a problem in
>> ideal world (mainline), but this matters for some vendor specific/custom
>> dtb files. This can be easily fixed by the little change to libfdt code:
>> any new properties and sub-nodes should be added after the parent's node
>> properties and subnodes.
>>
>> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
> I'm not convinced this is a good idea.
>
> First, anything that relies on the order of properties or subnodes in
> a dtb is deeply, fundamentally broken.  That can't even really be a
> problem with a dtb file itself, only with the code processing it.

I agree about the properties, but generally the order of nodes usually 
implies the order of creation of some devices or objects. This sometimes 
has some side-effects.

For comparison, the other lib used for fdt manipulation (libufdt) 
applies overlays in a such way, that the order of properties and nodes 
is not reversed.

> I'm also concerned this could have a negative performance impact,
> since it has to skip over a bunch of existing things before adding the
> new one.  On the other hand, that may be offset by the fact that it
> will reduce the amount of stuff that needs to be memmove()ed later on.

This code is already slow (especially in the way the uboot's use it for 
'fdt apply' command), but in practice I've didn't observe negative 
impact on the performance of applying large overlays at all.

Best regards
-- 
Marek Szyprowski, PhD
Samsung R&D Institute Poland

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 2367 bytes --]

On Mon, Feb 10, 2020 at 12:40:19PM +0100, Marek Szyprowski wrote:
> Hi David,
> 
> On 05.02.2020 06:45, David Gibson wrote:
> > On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
> >> While applying dt-overlays using libfdt code, the order of the applied
> >> properties and sub-nodes is reversed. This should not be a problem in
> >> ideal world (mainline), but this matters for some vendor specific/custom
> >> dtb files. This can be easily fixed by the little change to libfdt code:
> >> any new properties and sub-nodes should be added after the parent's node
> >> properties and subnodes.
> >>
> >> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
> > I'm not convinced this is a good idea.
> >
> > First, anything that relies on the order of properties or subnodes in
> > a dtb is deeply, fundamentally broken.  That can't even really be a
> > problem with a dtb file itself, only with the code processing it.
> 
> I agree about the properties, but generally the order of nodes usually 
> implies the order of creation of some devices or objects.

Huh?  From the device tree client's point of view the devices just
exist - the order of creation should not be visible to it.

> This sometimes 
> has some side-effects.

If those side effects matter, your code is broken.  If you need to
apply an order to nodes, you should be looking at 'reg' or other
properties.

> For comparison, the other lib used for fdt manipulation (libufdt) 
> applies overlays in a such way, that the order of properties and nodes 
> is not reversed.
> 
> > I'm also concerned this could have a negative performance impact,
> > since it has to skip over a bunch of existing things before adding the
> > new one.  On the other hand, that may be offset by the fact that it
> > will reduce the amount of stuff that needs to be memmove()ed later on.
> 
> This code is already slow (especially in the way the uboot's use it for 
> 'fdt apply' command), but in practice I've didn't observe negative 
> impact on the performance of applying large overlays at all.

I'm going to need numbers, not just "I didn't see anything".

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[Rob Herring]

On Mon, Feb 10, 2020 at 5:44 PM David Gibson
<david@gibson.dropbear.id.au> wrote:
>
> On Mon, Feb 10, 2020 at 12:40:19PM +0100, Marek Szyprowski wrote:
> > Hi David,
> >
> > On 05.02.2020 06:45, David Gibson wrote:
> > > On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
> > >> While applying dt-overlays using libfdt code, the order of the applied
> > >> properties and sub-nodes is reversed. This should not be a problem in
> > >> ideal world (mainline), but this matters for some vendor specific/custom
> > >> dtb files. This can be easily fixed by the little change to libfdt code:
> > >> any new properties and sub-nodes should be added after the parent's node
> > >> properties and subnodes.
> > >>
> > >> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
> > > I'm not convinced this is a good idea.
> > >
> > > First, anything that relies on the order of properties or subnodes in
> > > a dtb is deeply, fundamentally broken.  That can't even really be a
> > > problem with a dtb file itself, only with the code processing it.
> >
> > I agree about the properties, but generally the order of nodes usually
> > implies the order of creation of some devices or objects.
>
> Huh?  From the device tree client's point of view the devices just
> exist - the order of creation should not be visible to it.

I'm not sure if downstream is different, but upstream this stems from
Linux initcalls being processed in link order within a given level.
It's much better than it used to be, but short of randomizing the
ordering, I'm not sure we'll ever find and fix all these hidden
dependencies.

> > This sometimes
> > has some side-effects.
>
> If those side effects matter, your code is broken.  If you need to
> apply an order to nodes, you should be looking at 'reg' or other
> properties.

The general preference is to sort by 'reg'. And we try to catch and
reject any node re-ordering patches.

Rob

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[David Gibson]

[-- Attachment #1: Type: text/plain, Size: 2558 bytes --]

On Tue, Feb 11, 2020 at 02:29:22PM -0600, Rob Herring wrote:
> On Mon, Feb 10, 2020 at 5:44 PM David Gibson
> <david@gibson.dropbear.id.au> wrote:
> >
> > On Mon, Feb 10, 2020 at 12:40:19PM +0100, Marek Szyprowski wrote:
> > > Hi David,
> > >
> > > On 05.02.2020 06:45, David Gibson wrote:
> > > > On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
> > > >> While applying dt-overlays using libfdt code, the order of the applied
> > > >> properties and sub-nodes is reversed. This should not be a problem in
> > > >> ideal world (mainline), but this matters for some vendor specific/custom
> > > >> dtb files. This can be easily fixed by the little change to libfdt code:
> > > >> any new properties and sub-nodes should be added after the parent's node
> > > >> properties and subnodes.
> > > >>
> > > >> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
> > > > I'm not convinced this is a good idea.
> > > >
> > > > First, anything that relies on the order of properties or subnodes in
> > > > a dtb is deeply, fundamentally broken.  That can't even really be a
> > > > problem with a dtb file itself, only with the code processing it.
> > >
> > > I agree about the properties, but generally the order of nodes usually
> > > implies the order of creation of some devices or objects.
> >
> > Huh?  From the device tree client's point of view the devices just
> > exist - the order of creation should not be visible to it.
> 
> I'm not sure if downstream is different, but upstream this stems from
> Linux initcalls being processed in link order within a given level.
> It's much better than it used to be, but short of randomizing the
> ordering, I'm not sure we'll ever find and fix all these hidden
> dependencies.

Uhh... I don't really see how that relates to device tree encoding
order.  That's another source of non-stable device identifications,
which dtb order can also be, but they're not really connected beyond
that as far as I can tell.

> > > This sometimes
> > > has some side-effects.
> >
> > If those side effects matter, your code is broken.  If you need to
> > apply an order to nodes, you should be looking at 'reg' or other
> > properties.
> 
> The general preference is to sort by 'reg'. And we try to catch and
> reject any node re-ordering patches.
> 
> Rob
> 

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[Marek Szyprowski]

Hi Rob,

On 11.02.2020 21:29, Rob Herring wrote:
> On Mon, Feb 10, 2020 at 5:44 PM David Gibson
> <david@gibson.dropbear.id.au> wrote:
>> On Mon, Feb 10, 2020 at 12:40:19PM +0100, Marek Szyprowski wrote:
>>> Hi David,
>>>
>>> On 05.02.2020 06:45, David Gibson wrote:
>>>> On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
>>>>> While applying dt-overlays using libfdt code, the order of the applied
>>>>> properties and sub-nodes is reversed. This should not be a problem in
>>>>> ideal world (mainline), but this matters for some vendor specific/custom
>>>>> dtb files. This can be easily fixed by the little change to libfdt code:
>>>>> any new properties and sub-nodes should be added after the parent's node
>>>>> properties and subnodes.
>>>>>
>>>>> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
>>>> I'm not convinced this is a good idea.
>>>>
>>>> First, anything that relies on the order of properties or subnodes in
>>>> a dtb is deeply, fundamentally broken.  That can't even really be a
>>>> problem with a dtb file itself, only with the code processing it.
>>> I agree about the properties, but generally the order of nodes usually
>>> implies the order of creation of some devices or objects.
>> Huh?  From the device tree client's point of view the devices just
>> exist - the order of creation should not be visible to it.
> I'm not sure if downstream is different, but upstream this stems from
> Linux initcalls being processed in link order within a given level.
> It's much better than it used to be, but short of randomizing the
> ordering, I'm not sure we'll ever find and fix all these hidden
> dependencies.

Downstream is probably much worse, because I've seen a lots of custom 
code iterating over the nodes and doing its initialization.

>>> This sometimes
>>> has some side-effects.
>> If those side effects matter, your code is broken.  If you need to
>> apply an order to nodes, you should be looking at 'reg' or other
>> properties.
> The general preference is to sort by 'reg'. And we try to catch and
> reject any node re-ordering patches.

If one applies an dt-overlay with current libfdt, the order of the all 
nodes from that overlay is reversed.

Best regards
-- 
Marek Szyprowski, PhD
Samsung R&D Institute Poland

Re: [PATCH] libfdt: place new nodes & properties after the parent's ones

[Rob Herring]

On Wed, Feb 12, 2020 at 12:57 AM Marek Szyprowski
<m.szyprowski@samsung.com> wrote:
>
> Hi Rob,
>
> On 11.02.2020 21:29, Rob Herring wrote:
> > On Mon, Feb 10, 2020 at 5:44 PM David Gibson
> > <david@gibson.dropbear.id.au> wrote:
> >> On Mon, Feb 10, 2020 at 12:40:19PM +0100, Marek Szyprowski wrote:
> >>> Hi David,
> >>>
> >>> On 05.02.2020 06:45, David Gibson wrote:
> >>>> On Tue, Feb 04, 2020 at 01:58:44PM +0100, Marek Szyprowski wrote:
> >>>>> While applying dt-overlays using libfdt code, the order of the applied
> >>>>> properties and sub-nodes is reversed. This should not be a problem in
> >>>>> ideal world (mainline), but this matters for some vendor specific/custom
> >>>>> dtb files. This can be easily fixed by the little change to libfdt code:
> >>>>> any new properties and sub-nodes should be added after the parent's node
> >>>>> properties and subnodes.
> >>>>>
> >>>>> Signed-off-by: Marek Szyprowski <m.szyprowski@samsung.com>
> >>>> I'm not convinced this is a good idea.
> >>>>
> >>>> First, anything that relies on the order of properties or subnodes in
> >>>> a dtb is deeply, fundamentally broken.  That can't even really be a
> >>>> problem with a dtb file itself, only with the code processing it.
> >>> I agree about the properties, but generally the order of nodes usually
> >>> implies the order of creation of some devices or objects.
> >> Huh?  From the device tree client's point of view the devices just
> >> exist - the order of creation should not be visible to it.
> > I'm not sure if downstream is different, but upstream this stems from
> > Linux initcalls being processed in link order within a given level.
> > It's much better than it used to be, but short of randomizing the
> > ordering, I'm not sure we'll ever find and fix all these hidden
> > dependencies.
>
> Downstream is probably much worse, because I've seen a lots of custom
> code iterating over the nodes and doing its initialization.
>
> >>> This sometimes
> >>> has some side-effects.
> >> If those side effects matter, your code is broken.  If you need to
> >> apply an order to nodes, you should be looking at 'reg' or other
> >> properties.
> > The general preference is to sort by 'reg'. And we try to catch and
> > reject any node re-ordering patches.
>
> If one applies an dt-overlay with current libfdt, the order of the all
> nodes from that overlay is reversed.

Sure, but my caring about the ordering ends at the source level.

Rob