Re: [PATCH v3 15/15] fdtfactor: Add compiled FIT factoring support

From: Doug Anderson

Date: Fri Nov 13 2026 - 00:46:22 EST


Hi David,

On Wed, Nov 11, 2026 at 6:31 PM David Gibson
<david@xxxxxxxxxxxxxxxxxxxxx> wrote:
>
> On Sun, Nov 01, 2026 at 02:01:22PM -0800, Douglas Anderson wrote:
> > * `-o`, `--outdir`: Output directory for generated `.dtbo` files and
> > `--output-base-dtb` (default: alongside each input `.dtb` for `.dtbo` files,
> > current directory for `--output-base-dtb`).
>
> Even though one's a directory and one's a file, using different output
> options for the FIT/non-FIT cases seems kind of awkward to me.

Makes sense. In my draft v4 I've unified both into `-o` / `--output`
(output directory in standalone `.dtb` mode; output FIT file path in
`-F` / `--fit` mode, defaulting to updating `--fit` in place) and
dropped `--outfile`.


> > +* `-F`, `--fit`: Factor `/images/fdt-*` blobs inside a compiled FIT
> ...
> > +* `--outfile`: Output FIT path when `--fit` is used (default:
> > + overwrite `--fit` in place).
>
> That's a lot of fiddly detail to fit in the description of a single
> option. Maybe move it out into its own doc section.

Done in my draft v4 -- split the `README.md` options (and `--help`
groups) into common options, a `### Standalone DTB Factoring`
subsection, and a `### FIT Factoring` subsection.


> > if _is_dtbo_overlay(fdt):
> > - raise ValueError(
> > + raise OverlayBlobError(
>
> This change seems unrelated to the rest.

In a FIT `/images` node, both full `.dtb`s and pre-existing `.dtbo`
overlays use `type = "flat_dt"`, so `_extract_fit_fdt_entries()` had
added `OverlayBlobError` to catch and skip `.dtbo` nodes while letting
other `ValueError`s propagate. Using an exception for that control flow
was clunky, though -- in my draft v4 I've dropped `OverlayBlobError` and
check `_is_dtbo_overlay()` directly in `_extract_fit_fdt_entries()`
before constructing `ParsedDtb`.


> > + algo = sub_node.get_str('algo')
> > + sub_node.props['value'] = libfdt.Property(
> > + 'value', _compute_fit_hash(algo, data_bytes)
>
> This assumes the FIT naming of hash algorithms is identical to the
> hashlib one, which seems a bit risky.

Agreed. In my draft v4 I've replaced `hashlib.new(algo_name)` with an
explicit `FIT_HASH_ALGOS` dispatch table mapping the standard FIT `algo`
names (`crc32`, `md5`, `sha1`, `sha256`, `sha384`, `sha512`) to their
`zlib` / `hashlib` implementations and raising `ValueError` on unknown
names.


> > +def group_fit_dtbs(fdt_entries):
> > + """Partition FIT `flat_dt` entries into compatible factor groups.
> > +
> > + DTBs are grouped by `(compression, arch, load, entry, boot_cpuid_phys,
>
> Why should compression play a role in the grouping? The internal dtb
> data doesn't depend on that.
>
> I'm not sure what the 'load' and 'entry' fields do, so it's not
> obvious to me whether they make sense here either.

* `compression`: Agreed -- in my draft v4 I've removed `compression`
from grouping (and from `--single-base-dtb`'s compatibility check),
recompressing each overlay `/images/fdt-*` node according to its own
`compression` property and `fdt-base-N` according to the group's first
entry's `compression` property.
* `entry` and `load`: In the FIT spec, `entry` is the CPU entry-point
address for executable images (`kernel`, `standalone`, `firmware`) and
isn't meaningful on `flat_dt` nodes, so I've dropped `entry`
completely. `load` is an optional physical RAM address telling the
bootloader (e.g. U-Boot's `boot_get_fdt_fit()`) where to load the base
FDT before applying overlays: two `flat_dt` nodes with different
`load` addresses can't share a single `fdt-base-N` node (since
`fdt-base-N` can only carry one `load` address), and `load` is
stripped from the `.dtbo` overlay nodes so a bootloader doesn't copy
an overlay directly on top of the base FDT at `load`. I've added a
comment explaining `load`.


> > + mem_rsv)` and node-path overlap (>= 50%) against the group's common node
>
> Overlap >= 50% seems a very arbitrary condition here.
>
> > + common_nodes = grp['common_nodes']
> > + union_len = len(entry_nodes | common_nodes)
> > + overlap = (
> > + len(entry_nodes & common_nodes) / union_len
> > + if union_len
> > + else 1.0
> > + )
> > + if overlap >= 0.5:
> > + grp['common_nodes'] &= entry_nodes
> > + grp['entries'].append(entry)
> > + placed = True
> > + break
>
> Reimplementing the common path analysis, rather than somehow utilizing
> the calculations you already implemented in the factoring itself seems
> unfortunate.

The usage model for `group_fit_dtbs()` is a multi-SoC kernel FIT (for
example, building `arch/arm64`'s `image.fit` across all enabled Qualcomm
or ARM64 boards, which bundles hundreds of DTBs spanning many distinct
SoC families).

Looking at your two points here, I initially tried dropping the overlap
percentage altogether by running `create_base_dtb_and_overlays()` on
each candidate group and merging whenever factoring reduced total size.
Testing that on a FIT containing all 438 upstream arm64 Qualcomm DTBs
was much too slow, though: rebuilding `base.dtb` and every member's
`.dtbo` on each candidate check (`O(N^2)` `.dtbo` builds) took nearly
90 minutes.

To address both of your points while only building `.dtbo`s once per
final group, in my draft v4 I've:
1. Replaced the unweighted node-path overlap check with byte-weighted
overlap over `ParsedDtb`'s already phandle-normalized `(path, name,
prop, fixups)` properties, reusing `select_best_candidate()`'s
`_prop_byte_cost()` calculation directly and picking whichever
compatible group has the highest overlap.
2. Added `--min-overlap PERCENT` (default `50`) so the overlap threshold
is configurable rather than a hardcoded constant.

Testing `fdtfactor -S -F` on the 438-DTB Qualcomm `image.fit` finishes
in ~12 seconds, grouping 426 of the gzipped DTBs into 41 `fdt-base-*`
groups (leaving 12 single-board SoCs unfactored). Compared to a
standard `image.fit` built without `-@ -L`, that shrinks the embedded
DTBs by 61% (9.27 MB -> 3.59 MB gzipped; overall FIT 22.48 MB ->
16.81 MB including the 13.09 MB kernel).

-Doug