[PATCH] libfdt: Add fdt_add_subnode_tail()

[PATCH] libfdt: Add fdt_add_subnode_tail()

[Vishal Chourasia]

fdt_add_subnode() always inserts the new node as the first child of its
parent, after the parent's properties. Code that builds a list of nodes
by adding them one at a time therefore ends up with the nodes in reverse
order. That matters when the order is significant, e.g. when a blob is
rebuilt from a live tree.

Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
insert the new node right before the closing tag of the parent, so that
nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
use fdt_splice_struct_() and so leave the blob unmodified if there is
not enough room.

Also add an Fdt.add_subnode_tail() method to pylibfdt.

Add tests for both: a C testcase covering ordering, parents with and
without existing children, the root node, duplicate names and running
out of space, and a short pylibfdt test of the wrapper.

Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
---
 libfdt/fdt_rw.c          |  57 ++++++++++++++++++
 libfdt/libfdt.h          |  37 ++++++++++++
 libfdt/version.lds       |   2 +
 pylibfdt/libfdt.i        |  19 ++++++
 tests/.gitignore         |   1 +
 tests/Makefile.tests     |   2 +-
 tests/add_subnode_tail.c | 123 +++++++++++++++++++++++++++++++++++++++
 tests/meson.build        |   1 +
 tests/pylibfdt_tests.py  |  17 ++++++
 tests/run_tests.sh       |   1 +
 10 files changed, 259 insertions(+), 1 deletion(-)
 create mode 100644 tests/add_subnode_tail.c

diff --git a/libfdt/fdt_rw.c b/libfdt/fdt_rw.c
index 850aafe..a5a6f2a 100644
--- a/libfdt/fdt_rw.c
+++ b/libfdt/fdt_rw.c
@@ -414,6 +414,63 @@ int fdt_add_subnode(void *fdt, int parentoffset, const char *name)
 	return fdt_add_subnode_namelen(fdt, parentoffset, name, strlen(name));
 }
 
+int fdt_add_subnode_namelen_tail(void *fdt, int parentoffset,
+				 const char *name, int namelen)
+{
+	struct fdt_node_header *nh;
+	int offset, nextoffset;
+	int depth = 0;
+	int nodelen;
+	int err;
+	uint32_t tag;
+	fdt32_t *endtag;
+
+	FDT_RW_PROBE(fdt);
+
+	offset = fdt_subnode_offset_namelen(fdt, parentoffset, name, namelen);
+	if (offset >= 0)
+		return -FDT_ERR_EXISTS;
+	else if (offset != -FDT_ERR_NOTFOUND)
+		return offset;
+
+	/* Place the new node right before the parent's closing tag */
+	offset = parentoffset;
+	for (;;) {
+		tag = fdt_next_tag(fdt, offset, &nextoffset);
+		if (tag == FDT_BEGIN_NODE)
+			depth++;
+		else if (tag == FDT_END_NODE)
+			depth--;
+		else if (tag == FDT_END)
+			return -FDT_ERR_BADSTRUCTURE;
+
+		if (!depth)
+			break;
+		offset = nextoffset;
+	}
+
+	nh = fdt_offset_ptr_w_(fdt, offset);
+	nodelen = sizeof(*nh) + FDT_TAGALIGN(namelen+1) + FDT_TAGSIZE;
+
+	err = fdt_splice_struct_(fdt, nh, 0, nodelen);
+	if (err)
+		return err;
+
+	nh->tag = cpu_to_fdt32(FDT_BEGIN_NODE);
+	memset(nh->name, 0, FDT_TAGALIGN(namelen+1));
+	memcpy(nh->name, name, namelen);
+	endtag = (fdt32_t *)((char *)nh + nodelen - FDT_TAGSIZE);
+	*endtag = cpu_to_fdt32(FDT_END_NODE);
+
+	return offset;
+}
+
+int fdt_add_subnode_tail(void *fdt, int parentoffset, const char *name)
+{
+	return fdt_add_subnode_namelen_tail(fdt, parentoffset, name,
+					    strlen(name));
+}
+
 int fdt_del_node(void *fdt, int nodeoffset)
 {
 	int endoffset;
diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
index c69a18e..f78966f 100644
--- a/libfdt/libfdt.h
+++ b/libfdt/libfdt.h
@@ -2441,6 +2441,43 @@ int fdt_add_subnode_namelen(void *fdt, int parentoffset,
  */
 int fdt_add_subnode(void *fdt, int parentoffset, const char *name);
 
+/**
+ * fdt_add_subnode_namelen_tail - creates a new node as the last child
+ * @fdt: pointer to the device tree blob
+ * @parentoffset: structure block offset of a node
+ * @name: name of the subnode to create
+ * @namelen: number of characters of name to consider
+ *
+ * Identical to fdt_add_subnode_tail(), but use only the first @namelen
+ * characters of @name as the name of the new node.  This is useful for
+ * creating subnodes based on a portion of a larger string, such as a
+ * full path.
+ *
+ * Returns: structure block offset of the created subnode (>=0), or a
+ * negative error code, see fdt_add_subnode()
+ */
+int fdt_add_subnode_namelen_tail(void *fdt, int parentoffset,
+				 const char *name, int namelen);
+
+/**
+ * fdt_add_subnode_tail - creates a new node as the last child
+ * @fdt: pointer to the device tree blob
+ * @parentoffset: structure block offset of a node
+ * @name: name of the subnode to create
+ *
+ * fdt_add_subnode() inserts the new node as the first child of the parent,
+ * so nodes added one by one end up in reverse order.
+ * fdt_add_subnode_tail() inserts the new node right before the closing tag
+ * of the parent instead, so nodes added in sequence keep that sequence.
+ *
+ * This function will insert data into the blob, and will therefore
+ * change the offsets of some existing nodes.
+ *
+ * Returns: structure block offset of the created subnode (>=0), or a
+ * negative error code, see fdt_add_subnode()
+ */
+int fdt_add_subnode_tail(void *fdt, int parentoffset, const char *name);
+
 /**
  * fdt_del_node - delete a node (subtree)
  * @fdt: pointer to the device tree blob
diff --git a/libfdt/version.lds b/libfdt/version.lds
index cbfef54..daee653 100644
--- a/libfdt/version.lds
+++ b/libfdt/version.lds
@@ -48,6 +48,8 @@ LIBFDT_1.2 {
 		fdt_delprop;
 		fdt_add_subnode_namelen;
 		fdt_add_subnode;
+		fdt_add_subnode_namelen_tail;
+		fdt_add_subnode_tail;
 		fdt_del_node;
 		fdt_strerror;
 		fdt_offset_ptr;
diff --git a/pylibfdt/libfdt.i b/pylibfdt/libfdt.i
index fa5f499..8db7b47 100644
--- a/pylibfdt/libfdt.i
+++ b/pylibfdt/libfdt.i
@@ -878,6 +878,25 @@ class Fdt(FdtRo):
         """
         return check_err(fdt_add_subnode(self._fdt, parentoffset, name), quiet)
 
+    def add_subnode_tail(self, parentoffset, name, quiet=()):
+        """Add a new subnode to a node, as its last child
+
+        Unlike add_subnode(), which makes the new node the first child,
+        nodes added with this method keep the order in which they were added.
+
+        Args:
+            parentoffset: Parent offset to add the subnode to
+            name: Name of node to add
+
+        Returns:
+            offset of the node created, or negative error code on failure
+
+        Raises:
+            FdtError if there is not enough space, or another error occurs
+        """
+        return check_err(fdt_add_subnode_tail(self._fdt, parentoffset, name),
+                         quiet)
+
     def del_node(self, nodeoffset, quiet=()):
         """Delete a node
 
diff --git a/tests/.gitignore b/tests/.gitignore
index 6969312..103e455 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -5,6 +5,7 @@
 tmp.*
 /fs/
 /add_subnode_with_nops
+/add_subnode_tail
 /addr_size_cells
 /addr_size_cells2
 /appendprop[12]
diff --git a/tests/Makefile.tests b/tests/Makefile.tests
index af5d309..a84edd3 100644
--- a/tests/Makefile.tests
+++ b/tests/Makefile.tests
@@ -22,7 +22,7 @@ LIB_TESTS_L = get_mem_rsv \
 	extra-terminating-null \
 	dtbs_equal_ordered \
 	dtb_reverse dtbs_equal_unordered \
-	add_subnode_with_nops path_offset_aliases \
+	add_subnode_with_nops add_subnode_tail path_offset_aliases \
 	utilfdt_test \
 	integer-expressions \
 	property_iterate \
diff --git a/tests/add_subnode_tail.c b/tests/add_subnode_tail.c
new file mode 100644
index 0000000..8aa499a
--- /dev/null
+++ b/tests/add_subnode_tail.c
@@ -0,0 +1,123 @@
+// SPDX-License-Identifier: LGPL-2.1-or-later
+/*
+ * libfdt - Flat Device Tree manipulation
+ *	Testcase for fdt_add_subnode_tail()
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h>
+
+#include <libfdt.h>
+
+#include "tests.h"
+#include "testdata.h"
+
+#define SPACE	65536
+
+#define CHECK(code) \
+	{ \
+		err = (code); \
+		if (err) \
+			FAIL(#code ": %s", fdt_strerror(err)); \
+	}
+
+#define OFF_CHECK(off, code) \
+	{ \
+		(off) = (code); \
+		if (off < 0) \
+			FAIL(#code ": %s", fdt_strerror(off)); \
+	}
+
+static void check_children(const void *fdt, int parent, int n,
+			   const char * const *names)
+{
+	int i = 0, off;
+
+	fdt_for_each_subnode(off, fdt, parent) {
+		const char *name = fdt_get_name(fdt, off, NULL);
+
+		if (i >= n)
+			FAIL("Too many subnodes, extra \"%s\"", name);
+		if (!name || strcmp(name, names[i]))
+			FAIL("Subnode %d is \"%s\", expected \"%s\"", i,
+			     name ? name : "(null)", names[i]);
+		i++;
+	}
+	if (i != n)
+		FAIL("Found %d subnodes, expected %d", i, n);
+}
+
+int main(int argc, char *argv[])
+{
+	static const char * const order[] = { "a", "b", "c", "d" };
+	void *fdt;
+	int err;
+	int parent, off, child;
+
+	test_init(argc, argv);
+
+	fdt = xmalloc(SPACE);
+
+	CHECK(fdt_create(fdt, SPACE));
+	CHECK(fdt_finish_reservemap(fdt));
+	CHECK(fdt_begin_node(fdt, ""));
+	CHECK(fdt_property_cell(fdt, "prop", TEST_VALUE_1));
+	CHECK(fdt_begin_node(fdt, "parent"));
+	CHECK(fdt_property_cell(fdt, "pprop", TEST_VALUE_2));
+	CHECK(fdt_begin_node(fdt, "a"));
+	CHECK(fdt_property_cell(fdt, "aprop", TEST_VALUE_1));
+	CHECK(fdt_begin_node(fdt, "grandchild"));
+	CHECK(fdt_end_node(fdt));
+	CHECK(fdt_end_node(fdt));
+	CHECK(fdt_end_node(fdt));
+	CHECK(fdt_begin_node(fdt, "sibling"));
+	CHECK(fdt_end_node(fdt));
+	CHECK(fdt_end_node(fdt));
+	CHECK(fdt_finish(fdt));
+
+	CHECK(fdt_open_into(fdt, fdt, SPACE));
+
+	OFF_CHECK(parent, fdt_path_offset(fdt, "/parent"));
+
+	/* Nodes added in sequence must keep that sequence */
+	OFF_CHECK(off, fdt_add_subnode_tail(fdt, parent, "b"));
+	OFF_CHECK(off, fdt_add_subnode_tail(fdt, parent, "c"));
+	OFF_CHECK(off, fdt_add_subnode_namelen_tail(fdt, parent, "dxx", 1));
+
+	OFF_CHECK(parent, fdt_path_offset(fdt, "/parent"));
+	check_children(fdt, parent, 4, order);
+	check_getprop_cell(fdt, parent, "pprop", TEST_VALUE_2);
+
+	/* Existing children are left untouched */
+	OFF_CHECK(child, fdt_path_offset(fdt, "/parent/a"));
+	check_getprop_cell(fdt, child, "aprop", TEST_VALUE_1);
+	OFF_CHECK(child, fdt_path_offset(fdt, "/parent/a/grandchild"));
+	OFF_CHECK(child, fdt_path_offset(fdt, "/sibling"));
+	check_getprop_cell(fdt, 0, "prop", TEST_VALUE_1);
+
+	/* A new node can be added to a node without any children */
+	OFF_CHECK(off, fdt_path_offset(fdt, "/sibling"));
+	OFF_CHECK(child, fdt_add_subnode_tail(fdt, off, "x"));
+	OFF_CHECK(off, fdt_path_offset(fdt, "/sibling/x"));
+
+	/* ... and to the root node */
+	OFF_CHECK(child, fdt_add_subnode_tail(fdt, 0, "last"));
+	OFF_CHECK(off, fdt_path_offset(fdt, "/last"));
+
+	/* Duplicates are rejected */
+	err = fdt_add_subnode_tail(fdt, parent, "a");
+	if (err != -FDT_ERR_EXISTS)
+		FAIL("fdt_add_subnode_tail() of existing node returned %d",
+		     err);
+
+	/* Running out of space must fail without damaging the tree */
+	CHECK(fdt_pack(fdt));
+	err = fdt_add_subnode_tail(fdt, parent, "nospace");
+	if (err != -FDT_ERR_NOSPACE)
+		FAIL("fdt_add_subnode_tail() without space returned %d", err);
+	CHECK(fdt_check_full(fdt, fdt_totalsize(fdt)));
+
+	PASS();
+}
diff --git a/tests/meson.build b/tests/meson.build
index c255006..84eb829 100644
--- a/tests/meson.build
+++ b/tests/meson.build
@@ -24,6 +24,7 @@ testutil_dep = declare_dependency(sources: ['testutils.c'])
 
 tests = [
   'add_subnode_with_nops',
+  'add_subnode_tail',
   'addr_size_cells',
   'addr_size_cells2',
   'appendprop1',
diff --git a/tests/pylibfdt_tests.py b/tests/pylibfdt_tests.py
index ae46b29..d0f6d4a 100644
--- a/tests/pylibfdt_tests.py
+++ b/tests/pylibfdt_tests.py
@@ -613,6 +613,23 @@ class PyLibfdtBasicTests(unittest.TestCase):
         self.assertTrue(offset > 0)
         self.assertEqual(self.GetSubnodes(node_name), ['more', 'ss1'])
 
+    def testAddSubnodeTail(self):
+        """Test that add_subnode_tail() appends nodes in order"""
+        node_name = '/subnode@1'
+        self.fdt.resize(self.fdt.totalsize() + 128)
+        node = self.fdt.path_offset(node_name)
+        self.assertEqual(self.GetSubnodes(node_name), ['subsubnode', 'ss1'])
+        for name in ('x', 'y', 'z'):
+            self.assertTrue(self.fdt.add_subnode_tail(node, name) > 0)
+            node = self.fdt.path_offset(node_name)
+        self.assertEqual(self.GetSubnodes(node_name),
+                         ['subsubnode', 'ss1', 'x', 'y', 'z'])
+
+        with self.assertRaisesRegex(FdtException, get_err(libfdt.EXISTS)):
+            self.fdt.add_subnode_tail(node, 'x')
+        self.assertEqual(self.fdt.add_subnode_tail(node, 'x', (libfdt.EXISTS,)),
+                         -libfdt.EXISTS)
+
 
 class PyLibfdtSwTests(unittest.TestCase):
     """Test class for pylibfdt sequential-write DT creation
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 0d815e3..3698832 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -537,6 +537,7 @@ libfdt_tests () {
 
     # Specific bug tests
     run_test add_subnode_with_nops
+    run_test add_subnode_tail
     run_dtc_test -I dts -O dts -o sourceoutput.test.dts "$SRCDIR/sourceoutput.dts"
     run_dtc_test -I dts -O dtb -o sourceoutput.test.dtb "$SRCDIR/sourceoutput.dts"
     run_dtc_test -I dts -O dtb -o sourceoutput.test.dts.test.dtb sourceoutput.test.dts
-- 
2.54.0

Re: [PATCH] libfdt: Add fdt_add_subnode_tail()

[David Gibson]

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

On Tue, Nov 03, 2026 at 09:44:25PM +0530, Vishal Chourasia wrote:
> fdt_add_subnode() always inserts the new node as the first child of its
> parent, after the parent's properties. Code that builds a list of nodes
> by adding them one at a time therefore ends up with the nodes in reverse
> order. That matters when the order is significant, e.g. when a blob is
> rebuilt from a live tree.
> 
> Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
> insert the new node right before the closing tag of the parent, so that
> nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
> use fdt_splice_struct_() and so leave the blob unmodified if there is
> not enough room.
> 
> Also add an Fdt.add_subnode_tail() method to pylibfdt.
> 
> Add tests for both: a C testcase covering ordering, parents with and
> without existing children, the root node, duplicate names and running
> out of space, and a short pylibfdt test of the wrapper.
> 
> Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>

I'd need a stronger and more specific rationale to consider applying
this.  In general node order should not matter to consumers of the
device tree, which is why we make no attempt to preserve it the
fdt_rw.c interface,

The cited motivation doesn't make much sense to me for at least two
reasons.

1)  Order shouldn't matter in an fdt, but it has to exist as an
    artifact of flattening.  Order should matter even less in a live
    representation, and may not even exist (e.g. subnodes stored as a
    hash table).

2) The usual natural way of flattening a live tree is to use the
   fdt_sw.c interface, which *will* preserve order.
   

-- 
David Gibson (he or they)	| 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: Add fdt_add_subnode_tail()

[Simon Glass]

Hi,

On Tue, 3 Nov 2026 at 22:55, David Gibson <david@gibson.dropbear.id.au> wrote:
>
> On Tue, Nov 03, 2026 at 09:44:25PM +0530, Vishal Chourasia wrote:
> > fdt_add_subnode() always inserts the new node as the first child of its
> > parent, after the parent's properties. Code that builds a list of nodes
> > by adding them one at a time therefore ends up with the nodes in reverse
> > order. That matters when the order is significant, e.g. when a blob is
> > rebuilt from a live tree.
> >
> > Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
> > insert the new node right before the closing tag of the parent, so that
> > nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
> > use fdt_splice_struct_() and so leave the blob unmodified if there is
> > not enough room.
> >
> > Also add an Fdt.add_subnode_tail() method to pylibfdt.
> >
> > Add tests for both: a C testcase covering ordering, parents with and
> > without existing children, the root node, duplicate names and running
> > out of space, and a short pylibfdt test of the wrapper.
> >
> > Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
>
> I'd need a stronger and more specific rationale to consider applying
> this.  In general node order should not matter to consumers of the
> device tree, which is why we make no attempt to preserve it the
> fdt_rw.c interface,

Yes 'when a blob is rebuilt from a live tree' needs more detail. What
is the use case that drove this?

The spec doesn’t say that sibling order is significant, but it doesn’t
say that it isn’t either. It only requires properties to come before
subnodes.

From my side, one use for this new function could be with Binman[1]
which builds firmware images. The nodes describe the ordering of
binaries within the image - example at [2].

Binman knows the current libfdt behaviour and is careful about
ordering when it is generating nodes / processing templates.

Specifically, the code at [3] (a Python interface on pylibfdt which I
am looking forward to replacing with Doug's one) has to add nodes in
reverse order and then rotate its own node list to match what libfdt
produced. Inserting a node anywhere but first means deleting all its
siblings and recreating them ([4]), and template expansion in binman
([5], called from [6]) has to walk its sources backwards.

An fdt_add_subnode_tail() would let this code add nodes in the natural
order, without the reversals or the delete-and-re-add step.

Regards,
Simon

[1] https://github.com/deinde-dev/binman
[2] https://binman.readthedocs.io/en/latest/binman.html#a-first-image
[3] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L684-L696
[4] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L577-L597
[5] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L735-L786
[6] https://github.com/deinde-dev/binman/blob/7a9cfb456ddeaba09f0cefc3dfd6c801978c6509/binman/control.py#L498-L523

Re: [PATCH] libfdt: Add fdt_add_subnode_tail()

[David Gibson]

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

On Wed, Nov 04, 2026 at 05:50:45PM +0000, Simon Glass wrote:
> Hi,
> 
> On Tue, 3 Nov 2026 at 22:55, David Gibson <david@gibson.dropbear.id.au> wrote:
> >
> > On Tue, Nov 03, 2026 at 09:44:25PM +0530, Vishal Chourasia wrote:
> > > fdt_add_subnode() always inserts the new node as the first child of its
> > > parent, after the parent's properties. Code that builds a list of nodes
> > > by adding them one at a time therefore ends up with the nodes in reverse
> > > order. That matters when the order is significant, e.g. when a blob is
> > > rebuilt from a live tree.
> > >
> > > Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
> > > insert the new node right before the closing tag of the parent, so that
> > > nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
> > > use fdt_splice_struct_() and so leave the blob unmodified if there is
> > > not enough room.
> > >
> > > Also add an Fdt.add_subnode_tail() method to pylibfdt.
> > >
> > > Add tests for both: a C testcase covering ordering, parents with and
> > > without existing children, the root node, duplicate names and running
> > > out of space, and a short pylibfdt test of the wrapper.
> > >
> > > Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
> >
> > I'd need a stronger and more specific rationale to consider applying
> > this.  In general node order should not matter to consumers of the
> > device tree, which is why we make no attempt to preserve it the
> > fdt_rw.c interface,
> 
> Yes 'when a blob is rebuilt from a live tree' needs more detail. What
> is the use case that drove this?
> 
> The spec doesn’t say that sibling order is significant, but it doesn’t
> say that it isn’t either. It only requires properties to come before
> subnodes.

I guess not, because the modern(ish) spec is specifically describing
the flattened format, which necessarily has some sort of order.
Non-significance of the order might be implied by compatibility of the
device tree contents with IEEE 1275.  In IEEE 1275 the tree is not
flattened (access is via Forth firmware methods), and I don't think it
precludes an implementation which uses a hash table to store
properties and subnodes.

> rom my side, one use for this new function could be with Binman[1]
> which builds firmware images. The nodes describe the ordering of
> binaries within the image - example at [2].

I would strongly advise you not to design something which relies on
property or node order within the fdt format.

> Binman knows the current libfdt behaviour and is careful about
> ordering when it is generating nodes / processing templates.
> 
> Specifically, the code at [3] (a Python interface on pylibfdt which I
> am looking forward to replacing with Doug's one) has to add nodes in
> reverse order and then rotate its own node list to match what libfdt
> produced. Inserting a node anywhere but first means deleting all its
> siblings and recreating them ([4]), and template expansion in binman
> ([5], called from [6]) has to walk its sources backwards.
> 
> An fdt_add_subnode_tail() would let this code add nodes in the natural
> order, without the reversals or the delete-and-re-add step.
> 
> Regards,
> Simon
> 
> [1] https://github.com/deinde-dev/binman
> [2] https://binman.readthedocs.io/en/latest/binman.html#a-first-image
> [3] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L684-L696
> [4] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L577-L597
> [5] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L735-L786
> [6] https://github.com/deinde-dev/binman/blob/7a9cfb456ddeaba09f0cefc3dfd6c801978c6509/binman/control.py#L498-L523
> 

-- 
David Gibson (he or they)	| 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: Add fdt_add_subnode_tail()

[Simon Glass]

Hi David,

On Tue, 10 Nov 2026 at 19:50, David Gibson <david@gibson.dropbear.id.au> wrote:
>
> On Wed, Nov 04, 2026 at 05:50:45PM +0000, Simon Glass wrote:
> > Hi,
> >
> > On Tue, 3 Nov 2026 at 22:55, David Gibson <david@gibson.dropbear.id.au> wrote:
> > >
> > > On Tue, Nov 03, 2026 at 09:44:25PM +0530, Vishal Chourasia wrote:
> > > > fdt_add_subnode() always inserts the new node as the first child of its
> > > > parent, after the parent's properties. Code that builds a list of nodes
> > > > by adding them one at a time therefore ends up with the nodes in reverse
> > > > order. That matters when the order is significant, e.g. when a blob is
> > > > rebuilt from a live tree.
> > > >
> > > > Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
> > > > insert the new node right before the closing tag of the parent, so that
> > > > nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
> > > > use fdt_splice_struct_() and so leave the blob unmodified if there is
> > > > not enough room.
> > > >
> > > > Also add an Fdt.add_subnode_tail() method to pylibfdt.
> > > >
> > > > Add tests for both: a C testcase covering ordering, parents with and
> > > > without existing children, the root node, duplicate names and running
> > > > out of space, and a short pylibfdt test of the wrapper.
> > > >
> > > > Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
> > >
> > > I'd need a stronger and more specific rationale to consider applying
> > > this.  In general node order should not matter to consumers of the
> > > device tree, which is why we make no attempt to preserve it the
> > > fdt_rw.c interface,
> >
> > Yes 'when a blob is rebuilt from a live tree' needs more detail. What
> > is the use case that drove this?
> >
> > The spec doesn’t say that sibling order is significant, but it doesn’t
> > say that it isn’t either. It only requires properties to come before
> > subnodes.
>
> I guess not, because the modern(ish) spec is specifically describing
> the flattened format, which necessarily has some sort of order.
> Non-significance of the order might be implied by compatibility of the
> device tree contents with IEEE 1275.  In IEEE 1275 the tree is not
> flattened (access is via Forth firmware methods), and I don't think it
> precludes an implementation which uses a hash table to store
> properties and subnodes.

Right. We are only really talking about libfdt here, i.e. what it
happens to implement. I believe this is a case to be made for keeping
the current behaviour. But in any case perhaps we should document
libfdt's intended node-ordering semantics, separate from its actual
behaviour. For example we could say that when adding a node, libfdt
may put it in any order, not necessarily at the start or end.

I actually like the way it works now, but perhaps I've just got used to it.

>
> > rom my side, one use for this new function could be with Binman[1]
> > which builds firmware images. The nodes describe the ordering of
> > binaries within the image - example at [2].
>
> I would strongly advise you not to design something which relies on
> property or node order within the fdt format.

Another option would be to add a sequence numbers as a property to
each node. Depending on where this goes I can update Binman.

>
> > Binman knows the current libfdt behaviour and is careful about
> > ordering when it is generating nodes / processing templates.
> >
> > Specifically, the code at [3] (a Python interface on pylibfdt which I
> > am looking forward to replacing with Doug's one) has to add nodes in
> > reverse order and then rotate its own node list to match what libfdt
> > produced. Inserting a node anywhere but first means deleting all its
> > siblings and recreating them ([4]), and template expansion in binman
> > ([5], called from [6]) has to walk its sources backwards.
> >
> > An fdt_add_subnode_tail() would let this code add nodes in the natural
> > order, without the reversals or the delete-and-re-add step.

Regards,
Simon

> >
> > [1] https://github.com/deinde-dev/binman
> > [2] https://binman.readthedocs.io/en/latest/binman.html#a-first-image
> > [3] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L684-L696
> > [4] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L577-L597
> > [5] https://github.com/deinde-dev/dtoc/blob/1e8b69d7e95970f7c226d1a4d6cb90b3e067ee61/dtoc/fdt.py#L735-L786
> > [6] https://github.com/deinde-dev/binman/blob/7a9cfb456ddeaba09f0cefc3dfd6c801978c6509/binman/control.py#L498-L523
> >

Re: [PATCH] libfdt: Add fdt_add_subnode_tail()

[David Gibson]

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

On Wed, Nov 11, 2026 at 06:24:15PM +0000, Simon Glass wrote:
> Hi David,
> 
> On Tue, 10 Nov 2026 at 19:50, David Gibson <david@gibson.dropbear.id.au> wrote:
> >
> > On Wed, Nov 04, 2026 at 05:50:45PM +0000, Simon Glass wrote:
> > > Hi,
> > >
> > > On Tue, 3 Nov 2026 at 22:55, David Gibson <david@gibson.dropbear.id.au> wrote:
> > > >
> > > > On Tue, Nov 03, 2026 at 09:44:25PM +0530, Vishal Chourasia wrote:
> > > > > fdt_add_subnode() always inserts the new node as the first child of its
> > > > > parent, after the parent's properties. Code that builds a list of nodes
> > > > > by adding them one at a time therefore ends up with the nodes in reverse
> > > > > order. That matters when the order is significant, e.g. when a blob is
> > > > > rebuilt from a live tree.
> > > > >
> > > > > Add fdt_add_subnode_tail() and fdt_add_subnode_namelen_tail(), which
> > > > > insert the new node right before the closing tag of the parent, so that
> > > > > nodes added in sequence keep that sequence. Like fdt_add_subnode(), they
> > > > > use fdt_splice_struct_() and so leave the blob unmodified if there is
> > > > > not enough room.
> > > > >
> > > > > Also add an Fdt.add_subnode_tail() method to pylibfdt.
> > > > >
> > > > > Add tests for both: a C testcase covering ordering, parents with and
> > > > > without existing children, the root node, duplicate names and running
> > > > > out of space, and a short pylibfdt test of the wrapper.
> > > > >
> > > > > Signed-off-by: Vishal Chourasia <vishalc@linux.ibm.com>
> > > >
> > > > I'd need a stronger and more specific rationale to consider applying
> > > > this.  In general node order should not matter to consumers of the
> > > > device tree, which is why we make no attempt to preserve it the
> > > > fdt_rw.c interface,
> > >
> > > Yes 'when a blob is rebuilt from a live tree' needs more detail. What
> > > is the use case that drove this?
> > >
> > > The spec doesn’t say that sibling order is significant, but it doesn’t
> > > say that it isn’t either. It only requires properties to come before
> > > subnodes.
> >
> > I guess not, because the modern(ish) spec is specifically describing
> > the flattened format, which necessarily has some sort of order.
> > Non-significance of the order might be implied by compatibility of the
> > device tree contents with IEEE 1275.  In IEEE 1275 the tree is not
> > flattened (access is via Forth firmware methods), and I don't think it
> > precludes an implementation which uses a hash table to store
> > properties and subnodes.
> 
> Right. We are only really talking about libfdt here, i.e. what it
> happens to implement. I believe this is a case to be made for keeping
> the current behaviour. But in any case perhaps we should document
> libfdt's intended node-ordering semantics, separate from its actual
> behaviour. For example we could say that when adding a node, libfdt
> may put it in any order, not necessarily at the start or end.

Right, certainly the intention was that add_subnode() makes no
guarantee about how it orders the new node.  Nothing that explicitly
might be worthwhile.

> I actually like the way it works now, but perhaps I've just got used to it.
> 
> > > rom my side, one use for this new function could be with Binman[1]
> > > which builds firmware images. The nodes describe the ordering of
> > > binaries within the image - example at [2].
> >
> > I would strongly advise you not to design something which relies on
> > property or node order within the fdt format.
> 
> Another option would be to add a sequence numbers as a property to
> each node. Depending on where this goes I can update Binman.

The other option you could consider is having an explicit (ordered)
list of the things to consider as a different property somewhere.  Or,
having /aliases entries which give the numbers, along the lines of
	'hd0'	=> "/pci@XYZZY/scsi@PQRS/lun@3/..."
	'hd1'	=> "/pci@PLUGH/usb@ABCD/mass-storage@4,3/..."

Fwiw, sometime in the distant past that was suggested as a method that
the device tree could use to advertise a stable device naming/order to
Linux.  Not sure if that was ever implemented, though.

-- 
David Gibson (he or they)	| 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 --]