fdt_parent_offset() walks the whole tree from the root twice: once
inside fdt_node_depth() to discover the node's depth, then again in
fdt_supernode_atdepth_offset() to find the ancestor one level up. Both
walks are O(nodes before the target), so a parent lookup costs twice
what it needs to.
This matters in U-Boot, which looks up a node's parent before
relocation, for example to find the cell sizes for a device's address,
and may be reading the devicetree with the caches off at that point. On
a Firefly-RK3399, with a 564-node devicetree, the 17 lookups made before
relocation take about 7.1ms each, 121ms in all. With this change each
takes about 4.3ms, for a total of 73ms.
Walk the tree once instead, remembering the most recent node seen at
each depth. On reaching the target node its parent is the last node seen
one level up. A node deeper than the tracked limit falls back to the
existing code.
The single pass needs an int per level of depth, so it costs that much
stack. FDT_PARENT_MAX_DEPTH sets the limit when libfdt is built: 32 by
default, which no real tree approaches, and lower where stack is tight.
Setting it to 0 leaves the single-pass code out altogether, for callers
who would rather have the smaller build.
Nothing builds libfdt with FDT_PARENT_MAX_DEPTH set to 0, so the
fallback only runs for the deep tree in the parent_offset test. Add a
step to the Meson CI builds which leaves out the single-pass lookup and
runs the libfdt tests, so that every parent lookup there takes the
fallback, including those from fdt_overlay.c
Assisted-by: Claude:claude-opus-5-5
Signed-off-by: Simon Glass <sjg@chromium.org>
Message-ID: <20261026095020.1760446-1-sjg@chromium.org>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
9a712e0c7f