mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: David Gibson <david@gibson.dropbear.id.au>
To: Doug Anderson <dianders@chromium.org>
Cc: Devicetree-compiler@vger.kernel.org,
	"Rob Herring" <robh@kernel.org>,
	"Krzysztof Kozlowski" <krzk+dt@kernel.org>,
	"Conor Dooley" <conor+dt@kernel.org>,
	"Konrad Dybcio" <konradybcio@kernel.org>,
	"Peter Griffin" <peter.griffin@linaro.org>,
	"Saravana Kannan" <saravanak@kernel.org>,
	Devicetree@vger.kernel.org, "Simon Glass" <sjg@chromium.org>,
	"Chen-Yu Tsai" <wenst@chromium.org>,
	"Julius Werner" <jwerner@chromium.org>,
	"Brian Norris" <briannorris@chromium.org>,
	linux-kernel@vger.kernel.org,
	"Tudor Ambarus" <tudor.ambarus@linaro.org>,
	"André Draszik" <andre.draszik@linaro.org>
Subject: Re: [PATCH v3 15/15] fdtfactor: Add compiled FIT factoring support
Date: Mon, 16 Nov 2026 14:44:50 +1100	[thread overview]
Message-ID: <avp8MTOt0KtLJPJW@gractus.seuss> (raw)
In-Reply-To: <CAD=FV=WGTD8FtjPFE5mFSJP343Z9-2HNXHH3g4usqpWPVuwPUg@mail.gmail.com>

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

On Thu, Nov 12, 2026 at 09:23:54PM -0800, Doug Anderson wrote:
11;rgb:1c1c/1c1c/1f1f> Hi David,
> 
> On Wed, Nov 11, 2026 at 6:31 PM David Gibson
> <david@gibson.dropbear.id.au> 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`.

Sounds good.

> > > +* `-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`.

Ok.

> > > +        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.

Since crc32 is not in hashlib, you could even set up the map to go
direct from the FIT name to a function which computes the hash.

> > > +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.

Ok.

> * `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`

Ok.

>   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`.

That makes sense.

> > > +    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.

Ah, right.  I guess I hadn't realised FITs were built containing so
many disparate trees.

> 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.

Feels like there should be a more elegant way, but this will certainly
do for the time being.

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

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

  reply	other threads:[~2026-11-16  4:34 UTC|newest]

Thread overview: 54+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-01 22:01 [PATCH v3 00/15] fdtfactor: Introduce fdtfactor to auto-factor overlays Douglas Anderson
2026-11-01 22:01 ` [PATCH v3 01/15] libfdt: overlay: Fix out-of-bounds write on bad fixup offset Douglas Anderson
2026-11-02  4:29   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 02/15] libfdt: overlay: Drop redundant *sep != ':' checks after memchr() Douglas Anderson
2026-11-02  4:30   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 03/15] pylibfdt: Clarify iterator docstrings and test negative offsets Douglas Anderson
2026-11-02  4:32   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 04/15] pylibfdt: Handle empty properties in as_str() and as_stringlist() Douglas Anderson
2026-11-02  4:33   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 05/15] pylibfdt: Add Fdt.set_boot_cpuid_phys() Douglas Anderson
2026-11-02  4:34   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 06/15] pylibfdt: Support copy.copy() and copy.deepcopy() on Property Douglas Anderson
2026-11-02  4:35   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 07/15] devicetree: Add DeviceTree live tree representation Douglas Anderson
2026-11-02  9:31   ` David Gibson
2026-11-04  4:29     ` Doug Anderson
2026-11-04  6:12       ` David Gibson
2026-11-07  2:43         ` Doug Anderson
2026-11-10  2:10           ` David Gibson
2026-11-04 15:13       ` Simon Glass
2026-11-04 15:14   ` Simon Glass
2026-11-07  2:43     ` Doug Anderson
2026-11-11  2:56       ` David Gibson
2026-11-11 20:15         ` Simon Glass
2026-11-12  1:44           ` David Gibson
2026-11-12 19:28             ` Doug Anderson
2026-11-13  3:26               ` David Gibson
2026-11-13  3:30                 ` Doug Anderson
2026-11-01 22:01 ` [PATCH v3 08/15] libfdt: overlay: Factor out fixup and fragment path parsing helpers Douglas Anderson
2026-11-04  6:29   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 09/15] libfdt: overlay: Prepare fragment path helper for reuse Douglas Anderson
2026-11-04 15:14   ` Simon Glass
2026-11-01 22:01 ` [PATCH v3 10/15] libfdt: overlay: Make fdto const in overlay_apply_node() Douglas Anderson
2026-11-04 15:14   ` Simon Glass
2026-11-01 22:01 ` [PATCH v3 11/15] libfdt: overlay: Update base /__local_fixups__ on apply Douglas Anderson
2026-11-04 15:14   ` Simon Glass
2026-11-07  2:43     ` Doug Anderson
2026-11-01 22:01 ` [PATCH v3 12/15] fdtfactor: Add tool to split DTBs into a base DTB and overlays Douglas Anderson
2026-11-11  4:16   ` David Gibson
2026-11-13  5:22     ` Doug Anderson
2026-11-16  3:35       ` David Gibson
2026-11-01 22:01 ` [PATCH v3 13/15] fdtfactor: Add -S/--strip-local-fixups option Douglas Anderson
2026-11-04 15:14   ` Simon Glass
2026-11-11  4:19   ` David Gibson
2026-11-01 22:01 ` [PATCH v3 14/15] fdtfactor: Support compressed DTB inputs and outputs Douglas Anderson
2026-11-12  2:10   ` David Gibson
2026-11-13  5:23     ` Doug Anderson
2026-11-01 22:01 ` [PATCH v3 15/15] fdtfactor: Add compiled FIT factoring support Douglas Anderson
2026-11-12  2:31   ` David Gibson
2026-11-13  5:23     ` Doug Anderson
2026-11-16  3:44       ` David Gibson [this message]
2026-11-02  4:44 ` [PATCH v3 00/15] fdtfactor: Introduce fdtfactor to auto-factor overlays David Gibson
2026-11-04 15:13 ` Simon Glass
2026-11-07  2:42   ` Doug Anderson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=avp8MTOt0KtLJPJW@gractus.seuss \
    --to=david@gibson.dropbear.id.au \
    --cc=Devicetree-compiler@vger.kernel.org \
    --cc=Devicetree@vger.kernel.org \
    --cc=andre.draszik@linaro.org \
    --cc=briannorris@chromium.org \
    --cc=conor+dt@kernel.org \
    --cc=dianders@chromium.org \
    --cc=jwerner@chromium.org \
    --cc=konradybcio@kernel.org \
    --cc=krzk+dt@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=peter.griffin@linaro.org \
    --cc=robh@kernel.org \
    --cc=saravanak@kernel.org \
    --cc=sjg@chromium.org \
    --cc=tudor.ambarus@linaro.org \
    --cc=wenst@chromium.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®