[PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Alexey Charkov]

Every expansion copies the whole tree into a freshly allocated buffer, so
growing by a fixed amount makes building a tree cost time quadratic in
its size. This is especially painful when assembling larger FIT images with
binman, as it assembles the image with the data inline.

Grow by at least as much as the tree already holds, which is what variable
sized arrays usually do specifically to avoid such excessive copying.

With this change, building a Rockchip TF-A+Falcon image whose FIT carries
a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
produced are byte-identical and the binman and dtoc test results are
unaffected.

Signed-off-by: Alexey Charkov <alchark@flipper.net>
---
 scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

diff --git a/scripts/dtc/pylibfdt/libfdt.i_shipped b/scripts/dtc/pylibfdt/libfdt.i_shipped
index e4659489a96a..05c1bba78001 100644
--- a/scripts/dtc/pylibfdt/libfdt.i_shipped
+++ b/scripts/dtc/pylibfdt/libfdt.i_shipped
@@ -756,7 +756,7 @@ class FdtSw(FdtRo):
     device tree. This will be increased automatically as needed as new items
     are added to the tree.
     """
-    INC_SIZE = 1024  # Expand size by this much when out of space
+    INC_SIZE = 1024  # Expand size by at least this much when out of space
 
     def __init__(self, size_hint=None):
         """Create a new FdtSw object
@@ -801,6 +801,10 @@ class FdtSw(FdtRo):
         -NOSPACE then the FDT will be expanded to have more space, and True will
         be returned, indicating that the operation needs to be tried again.
 
+        Each expansion copies the whole tree into a new buffer, so the size is
+        at least doubled rather than grown by a fixed amount, to keep the total
+        amount of copying proportional to the size of the tree.
+
         Args:
             val: Return value from the operation that was attempted
 
@@ -808,7 +812,7 @@ class FdtSw(FdtRo):
             True if the operation must be retried, else False
         """
         if check_err(val, QUIET_NOSPACE) < 0:
-            self.resize(len(self._fdt) + self.INC_SIZE)
+            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
             return True
         return False
 

---
base-commit: baa64b2f892890f00a377eac4a3e685472bb56b5
change-id: 20260805-pylibfdt-geo-growth-03a381850866

Best regards,
--  
Alexey Charkov <alchark@flipper.net>

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Simon Glass]

Hi Alexey,

On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> pylibfdt: Grow the FdtSw buffer geometrically
>
> Every expansion copies the whole tree into a freshly allocated buffer, so
> growing by a fixed amount makes building a tree cost time quadratic in
> its size. This is especially painful when assembling larger FIT images with
> binman, as it assembles the image with the data inline.
>
> Grow by at least as much as the tree already holds, which is what variable
> sized arrays usually do specifically to avoid such excessive copying.
>
> With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> produced are byte-identical and the binman and dtoc test results are
> unaffected.
>
> Signed-off-by: Alexey Charkov <alchark@flipper.net>
>
> scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)

This is a _shipped file from upstream dtc, so any change here will be
reverted on the next resync. Please can you send this to the dtc
project first (see https://github.com/dgibson/dtc) and reference the
upstream commit / PR in the U-Boot commit message, similar to how
a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
will be lost.

> @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
>          if check_err(val, QUIET_NOSPACE) < 0:
> -            self.resize(len(self._fdt) + self.INC_SIZE)
> +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))

Logic looks correct - doubling gives amortised O(n) total copying, and
the INC_SIZE floor keeps small trees from taking many tiny growths.
Nice measurement in the commit message too.

Regards,
Simon

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Alexey Charkov]

Hi Simon,

On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
>
> Hi Alexey,
>
> On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > pylibfdt: Grow the FdtSw buffer geometrically
> >
> > Every expansion copies the whole tree into a freshly allocated buffer, so
> > growing by a fixed amount makes building a tree cost time quadratic in
> > its size. This is especially painful when assembling larger FIT images with
> > binman, as it assembles the image with the data inline.
> >
> > Grow by at least as much as the tree already holds, which is what variable
> > sized arrays usually do specifically to avoid such excessive copying.
> >
> > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > produced are byte-identical and the binman and dtoc test results are
> > unaffected.
> >
> > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> >
> > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> >  1 file changed, 6 insertions(+), 2 deletions(-)
>
> This is a _shipped file from upstream dtc, so any change here will be
> reverted on the next resync. Please can you send this to the dtc
> project first (see https://github.com/dgibson/dtc) and reference the
> upstream commit / PR in the U-Boot commit message, similar to how
> a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> will be lost.
>
> > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> >          if check_err(val, QUIET_NOSPACE) < 0:
> > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
>
> Logic looks correct - doubling gives amortised O(n) total copying, and
> the INC_SIZE floor keeps small trees from taking many tiny growths.
> Nice measurement in the commit message too.

Merged upstream: https://github.com/dgibson/dtc/pull/189

Shall I spin a new version of this one to mention the upstream commit?

Best regards,
Alexey

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Tom Rini]

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

On Sat, Aug 08, 2026 at 01:02:02PM +0400, Alexey Charkov wrote:
> Hi Simon,
> 
> On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> >
> > Hi Alexey,
> >
> > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > pylibfdt: Grow the FdtSw buffer geometrically
> > >
> > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > growing by a fixed amount makes building a tree cost time quadratic in
> > > its size. This is especially painful when assembling larger FIT images with
> > > binman, as it assembles the image with the data inline.
> > >
> > > Grow by at least as much as the tree already holds, which is what variable
> > > sized arrays usually do specifically to avoid such excessive copying.
> > >
> > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > produced are byte-identical and the binman and dtoc test results are
> > > unaffected.
> > >
> > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > >
> > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > >  1 file changed, 6 insertions(+), 2 deletions(-)
> >
> > This is a _shipped file from upstream dtc, so any change here will be
> > reverted on the next resync. Please can you send this to the dtc
> > project first (see https://github.com/dgibson/dtc) and reference the
> > upstream commit / PR in the U-Boot commit message, similar to how
> > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > will be lost.
> >
> > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> >
> > Logic looks correct - doubling gives amortised O(n) total copying, and
> > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > Nice measurement in the commit message too.
> 
> Merged upstream: https://github.com/dgibson/dtc/pull/189
> 
> Shall I spin a new version of this one to mention the upstream commit?

Yes please, and are there other changes we need to merge in from
upstream as well, in the pylibfdt portion?

-- 
Tom

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

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Alexey Charkov]

Hi Tom,

On Sat, Aug 8, 2026 at 10:11 PM Tom Rini <trini@konsulko.com> wrote:
>
> On Sat, Aug 08, 2026 at 01:02:02PM +0400, Alexey Charkov wrote:
> > Hi Simon,
> >
> > On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> > >
> > > Hi Alexey,
> > >
> > > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > > pylibfdt: Grow the FdtSw buffer geometrically
> > > >
> > > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > > growing by a fixed amount makes building a tree cost time quadratic in
> > > > its size. This is especially painful when assembling larger FIT images with
> > > > binman, as it assembles the image with the data inline.
> > > >
> > > > Grow by at least as much as the tree already holds, which is what variable
> > > > sized arrays usually do specifically to avoid such excessive copying.
> > > >
> > > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > > produced are byte-identical and the binman and dtoc test results are
> > > > unaffected.
> > > >
> > > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > > >
> > > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > > >  1 file changed, 6 insertions(+), 2 deletions(-)
> > >
> > > This is a _shipped file from upstream dtc, so any change here will be
> > > reverted on the next resync. Please can you send this to the dtc
> > > project first (see https://github.com/dgibson/dtc) and reference the
> > > upstream commit / PR in the U-Boot commit message, similar to how
> > > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > > will be lost.
> > >
> > > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> > >
> > > Logic looks correct - doubling gives amortised O(n) total copying, and
> > > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > > Nice measurement in the commit message too.
> >
> > Merged upstream: https://github.com/dgibson/dtc/pull/189
> >
> > Shall I spin a new version of this one to mention the upstream commit?
>
> Yes please, and are there other changes we need to merge in from
> upstream as well, in the pylibfdt portion?

I've also added public accessors for address-cells, size-cells along
with add/delete methods for memory reservations, which David merged
earlier today [1]. It would be great to pull those in, too, while we
are at it.

They are useful for the Falcon mode via TF-A series I'm working on [2]
but haven't yet posted the new version due to breakage in am335x_evm
which I am yet to fix. I could send them together with this change
here as a separate mini-series if that works (i.e. ahead of the Falcon
changes which rely on them).

[1] https://github.com/dgibson/dtc/pull/190
[2] https://git.u-boot-project.org/u-boot/contributors/alchark/u-boot/-/tree/b4/atf-falcon?ref_type=heads

Best regards,
Alexey

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Simon Glass]

Hi Alexey,

On Sat, 8 Aug 2026 at 03:09, Alexey Charkov <alchark@flipper.net> wrote:
>
> Hi Simon,
>
> On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> >
> > Hi Alexey,
> >
> > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > pylibfdt: Grow the FdtSw buffer geometrically
> > >
> > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > growing by a fixed amount makes building a tree cost time quadratic in
> > > its size. This is especially painful when assembling larger FIT images with
> > > binman, as it assembles the image with the data inline.
> > >
> > > Grow by at least as much as the tree already holds, which is what variable
> > > sized arrays usually do specifically to avoid such excessive copying.
> > >
> > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > produced are byte-identical and the binman and dtoc test results are
> > > unaffected.
> > >
> > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > >
> > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > >  1 file changed, 6 insertions(+), 2 deletions(-)
> >
> > This is a _shipped file from upstream dtc, so any change here will be
> > reverted on the next resync. Please can you send this to the dtc
> > project first (see https://github.com/dgibson/dtc) and reference the
> > upstream commit / PR in the U-Boot commit message, similar to how
> > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > will be lost.
> >
> > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> >
> > Logic looks correct - doubling gives amortised O(n) total copying, and
> > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > Nice measurement in the commit message too.
>
> Merged upstream: https://github.com/dgibson/dtc/pull/189

Nice, that was quick!

>
> Shall I spin a new version of this one to mention the upstream commit?

Reviewed-by: Simon Glass <sjg@chromium.org>

Regards,
SImon

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Tom Rini]

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

On Sat, Aug 08, 2026 at 11:12:47PM +0400, Alexey Charkov wrote:
> Hi Tom,
> 
> On Sat, Aug 8, 2026 at 10:11 PM Tom Rini <trini@konsulko.com> wrote:
> >
> > On Sat, Aug 08, 2026 at 01:02:02PM +0400, Alexey Charkov wrote:
> > > Hi Simon,
> > >
> > > On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> > > >
> > > > Hi Alexey,
> > > >
> > > > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > > > pylibfdt: Grow the FdtSw buffer geometrically
> > > > >
> > > > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > > > growing by a fixed amount makes building a tree cost time quadratic in
> > > > > its size. This is especially painful when assembling larger FIT images with
> > > > > binman, as it assembles the image with the data inline.
> > > > >
> > > > > Grow by at least as much as the tree already holds, which is what variable
> > > > > sized arrays usually do specifically to avoid such excessive copying.
> > > > >
> > > > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > > > produced are byte-identical and the binman and dtoc test results are
> > > > > unaffected.
> > > > >
> > > > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > > > >
> > > > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > > > >  1 file changed, 6 insertions(+), 2 deletions(-)
> > > >
> > > > This is a _shipped file from upstream dtc, so any change here will be
> > > > reverted on the next resync. Please can you send this to the dtc
> > > > project first (see https://github.com/dgibson/dtc) and reference the
> > > > upstream commit / PR in the U-Boot commit message, similar to how
> > > > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > > > will be lost.
> > > >
> > > > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > > > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> > > >
> > > > Logic looks correct - doubling gives amortised O(n) total copying, and
> > > > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > > > Nice measurement in the commit message too.
> > >
> > > Merged upstream: https://github.com/dgibson/dtc/pull/189
> > >
> > > Shall I spin a new version of this one to mention the upstream commit?
> >
> > Yes please, and are there other changes we need to merge in from
> > upstream as well, in the pylibfdt portion?
> 
> I've also added public accessors for address-cells, size-cells along
> with add/delete methods for memory reservations, which David merged
> earlier today [1]. It would be great to pull those in, too, while we
> are at it.
> 
> They are useful for the Falcon mode via TF-A series I'm working on [2]
> but haven't yet posted the new version due to breakage in am335x_evm
> which I am yet to fix. I could send them together with this change
> here as a separate mini-series if that works (i.e. ahead of the Falcon
> changes which rely on them).

That's good to know, and yes we want them. But I'm asking if there's
other outstanding upstream changes to bring it?

-- 
Tom

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

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Alexey Charkov]

On Sat, Aug 8, 2026 at 11:19 PM Tom Rini <trini@konsulko.com> wrote:
>
> On Sat, Aug 08, 2026 at 11:12:47PM +0400, Alexey Charkov wrote:
> > Hi Tom,
> >
> > On Sat, Aug 8, 2026 at 10:11 PM Tom Rini <trini@konsulko.com> wrote:
> > >
> > > On Sat, Aug 08, 2026 at 01:02:02PM +0400, Alexey Charkov wrote:
> > > > Hi Simon,
> > > >
> > > > On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> > > > >
> > > > > Hi Alexey,
> > > > >
> > > > > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > > > > pylibfdt: Grow the FdtSw buffer geometrically
> > > > > >
> > > > > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > > > > growing by a fixed amount makes building a tree cost time quadratic in
> > > > > > its size. This is especially painful when assembling larger FIT images with
> > > > > > binman, as it assembles the image with the data inline.
> > > > > >
> > > > > > Grow by at least as much as the tree already holds, which is what variable
> > > > > > sized arrays usually do specifically to avoid such excessive copying.
> > > > > >
> > > > > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > > > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > > > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > > > > produced are byte-identical and the binman and dtoc test results are
> > > > > > unaffected.
> > > > > >
> > > > > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > > > > >
> > > > > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > > > > >  1 file changed, 6 insertions(+), 2 deletions(-)
> > > > >
> > > > > This is a _shipped file from upstream dtc, so any change here will be
> > > > > reverted on the next resync. Please can you send this to the dtc
> > > > > project first (see https://github.com/dgibson/dtc) and reference the
> > > > > upstream commit / PR in the U-Boot commit message, similar to how
> > > > > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > > > > will be lost.
> > > > >
> > > > > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > > > > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > > > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > > > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> > > > >
> > > > > Logic looks correct - doubling gives amortised O(n) total copying, and
> > > > > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > > > > Nice measurement in the commit message too.
> > > >
> > > > Merged upstream: https://github.com/dgibson/dtc/pull/189
> > > >
> > > > Shall I spin a new version of this one to mention the upstream commit?
> > >
> > > Yes please, and are there other changes we need to merge in from
> > > upstream as well, in the pylibfdt portion?
> >
> > I've also added public accessors for address-cells, size-cells along
> > with add/delete methods for memory reservations, which David merged
> > earlier today [1]. It would be great to pull those in, too, while we
> > are at it.
> >
> > They are useful for the Falcon mode via TF-A series I'm working on [2]
> > but haven't yet posted the new version due to breakage in am335x_evm
> > which I am yet to fix. I could send them together with this change
> > here as a separate mini-series if that works (i.e. ahead of the Falcon
> > changes which rely on them).
>
> That's good to know, and yes we want them. But I'm asking if there's
> other outstanding upstream changes to bring it?

Not for the parts I touched (they are self-contained), but I could go
through the whole diff to see if there is meaningful divergence vs.
the U-Boot shipped version and report back (hopefully with patches if
applicable).

Best regards,
Alexey

Re: [PATCH] pylibfdt: Grow the FdtSw buffer geometrically

[Tom Rini]

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

On Sat, Aug 08, 2026 at 11:26:44PM +0400, Alexey Charkov wrote:
> On Sat, Aug 8, 2026 at 11:19 PM Tom Rini <trini@konsulko.com> wrote:
> >
> > On Sat, Aug 08, 2026 at 11:12:47PM +0400, Alexey Charkov wrote:
> > > Hi Tom,
> > >
> > > On Sat, Aug 8, 2026 at 10:11 PM Tom Rini <trini@konsulko.com> wrote:
> > > >
> > > > On Sat, Aug 08, 2026 at 01:02:02PM +0400, Alexey Charkov wrote:
> > > > > Hi Simon,
> > > > >
> > > > > On Wed, Aug 5, 2026 at 11:34 PM Simon Glass <sjg@chromium.org> wrote:
> > > > > >
> > > > > > Hi Alexey,
> > > > > >
> > > > > > On 2026-08-05T14:47:38, Alexey Charkov <alchark@flipper.net> wrote:
> > > > > > > pylibfdt: Grow the FdtSw buffer geometrically
> > > > > > >
> > > > > > > Every expansion copies the whole tree into a freshly allocated buffer, so
> > > > > > > growing by a fixed amount makes building a tree cost time quadratic in
> > > > > > > its size. This is especially painful when assembling larger FIT images with
> > > > > > > binman, as it assembles the image with the data inline.
> > > > > > >
> > > > > > > Grow by at least as much as the tree already holds, which is what variable
> > > > > > > sized arrays usually do specifically to avoid such excessive copying.
> > > > > > >
> > > > > > > With this change, building a Rockchip TF-A+Falcon image whose FIT carries
> > > > > > > a 31 MiB kernel takes 33.1 s rather than 44.4 s, with binman itself down
> > > > > > > from 25.3 s to 14.0 s, as 7139 reallocations become 187. The images
> > > > > > > produced are byte-identical and the binman and dtoc test results are
> > > > > > > unaffected.
> > > > > > >
> > > > > > > Signed-off-by: Alexey Charkov <alchark@flipper.net>
> > > > > > >
> > > > > > > scripts/dtc/pylibfdt/libfdt.i_shipped | 8 ++++++--
> > > > > > >  1 file changed, 6 insertions(+), 2 deletions(-)
> > > > > >
> > > > > > This is a _shipped file from upstream dtc, so any change here will be
> > > > > > reverted on the next resync. Please can you send this to the dtc
> > > > > > project first (see https://github.com/dgibson/dtc) and reference the
> > > > > > upstream commit / PR in the U-Boot commit message, similar to how
> > > > > > a63456b9191 links to dgibson/dtc PR 154. Otherwise the improvement
> > > > > > will be lost.
> > > > > >
> > > > > > > @@ -808,7 +812,7 @@ class FdtSw(FdtRo):
> > > > > > >          if check_err(val, QUIET_NOSPACE) < 0:
> > > > > > > -            self.resize(len(self._fdt) + self.INC_SIZE)
> > > > > > > +            self.resize(len(self._fdt) + max(len(self._fdt), self.INC_SIZE))
> > > > > >
> > > > > > Logic looks correct - doubling gives amortised O(n) total copying, and
> > > > > > the INC_SIZE floor keeps small trees from taking many tiny growths.
> > > > > > Nice measurement in the commit message too.
> > > > >
> > > > > Merged upstream: https://github.com/dgibson/dtc/pull/189
> > > > >
> > > > > Shall I spin a new version of this one to mention the upstream commit?
> > > >
> > > > Yes please, and are there other changes we need to merge in from
> > > > upstream as well, in the pylibfdt portion?
> > >
> > > I've also added public accessors for address-cells, size-cells along
> > > with add/delete methods for memory reservations, which David merged
> > > earlier today [1]. It would be great to pull those in, too, while we
> > > are at it.
> > >
> > > They are useful for the Falcon mode via TF-A series I'm working on [2]
> > > but haven't yet posted the new version due to breakage in am335x_evm
> > > which I am yet to fix. I could send them together with this change
> > > here as a separate mini-series if that works (i.e. ahead of the Falcon
> > > changes which rely on them).
> >
> > That's good to know, and yes we want them. But I'm asking if there's
> > other outstanding upstream changes to bring it?
> 
> Not for the parts I touched (they are self-contained), but I could go
> through the whole diff to see if there is meaningful divergence vs.
> the U-Boot shipped version and report back (hopefully with patches if
> applicable).

Yes please, we don't intentionally lag behind upstream on that part of
the code.

-- 
Tom

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