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