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

[Tom Rini <trini@konsulko.com>]

[-- 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 --]