Re: [PATCH] libfdt: Find a node's parent in a single pass

[David Gibson <david@gibson.dropbear.id.au>]

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

On Thu, Aug 06, 2026 at 01:13:14PM -0600, Simon Glass wrote:
> 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.

Right.  Because dtbs typically aren't that large, and the environments
we're targetting, libfdt nearly always prioritizes simplicity and
working memory over runtime.

> 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. Trees deeper than the tracked limit fall 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, in the same way as
> FDT_ASSUME_MASK: 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.

I don't love the extra code complexity this adds, but it looks like
you've thought through the tradeoffs here pretty well with the build
parameter.

It would be interesting to know what the context is where the time
cost of fdt_parent_offset() matters.

Hervé also makes a good point about the test case.

Otherwise, I'm tentatively comfortable with this change.

> Signed-off-by: Simon Glass <sjg@chromium.org>
> ---
> 
>  libfdt/fdt_ro.c          | 32 +++++++++++++++-
>  libfdt/libfdt_internal.h | 14 +++++++
>  tests/parent_offset.c    | 79 ++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 124 insertions(+), 1 deletion(-)
> 
> diff --git a/libfdt/fdt_ro.c b/libfdt/fdt_ro.c
> index 11f2e2e..b84669a 100644
> --- a/libfdt/fdt_ro.c
> +++ b/libfdt/fdt_ro.c
> @@ -674,7 +674,37 @@ int fdt_node_depth(const void *fdt, int nodeoffset)
>  
>  int fdt_parent_offset(const void *fdt, int nodeoffset)
>  {
> -	int nodedepth = fdt_node_depth(fdt, nodeoffset);
> +#if FDT_PARENT_MAX_DEPTH
> +	int supernode[FDT_PARENT_MAX_DEPTH];
> +	int offset, depth;
> +#endif
> +	int nodedepth;
> +
> +#if FDT_PARENT_MAX_DEPTH
> +	FDT_RO_PROBE(fdt);
> +
> +	/*
> +	 * Walk the tree once, remembering the most recent node seen at each
> +	 * depth. On reaching the target node, its parent is the last node
> +	 * seen one level up
> +	 *
> +	 * The depth goes negative once the walk moves past the root, which
> +	 * happens when nodeoffset does not name a node. Fall back in that
> +	 * case, so that the checks below reject it
> +	 */
> +	for (offset = 0, depth = 0;
> +	     offset >= 0 && offset <= nodeoffset;
> +	     offset = fdt_next_node(fdt, offset, &depth)) {
> +		if (depth < 0 || depth >= FDT_PARENT_MAX_DEPTH)
> +			break;
> +		supernode[depth] = offset;
> +		if (offset == nodeoffset)
> +			return depth ? supernode[depth - 1] :
> +				-FDT_ERR_NOTFOUND;
> +	}
> +#endif /* FDT_PARENT_MAX_DEPTH */
> +
> +	nodedepth = fdt_node_depth(fdt, nodeoffset);
>  
>  	if (nodedepth < 0)
>  		return nodedepth;
> diff --git a/libfdt/libfdt_internal.h b/libfdt/libfdt_internal.h
> index 0e103ca..eefea2a 100644
> --- a/libfdt/libfdt_internal.h
> +++ b/libfdt/libfdt_internal.h
> @@ -85,6 +85,20 @@ static inline uint64_t fdt64_ld_(const fdt64_t *p)
>  #define FDT_ASSUME_MASK 0
>  #endif
>  
> +/*
> + * Maximum node depth for which fdt_parent_offset() finds a node's parent in
> + * a single pass over the tree. Deeper nodes fall back to walking the tree
> + * twice, which is correct but slower.
> + *
> + * The single pass needs an int for each level, so this costs that much
> + * stack. Reduce it if that matters more than the speed; no real device tree
> + * comes close to the default. Set it to 0 to leave out the single-pass code
> + * altogether, for the smallest build.
> + */
> +#ifndef FDT_PARENT_MAX_DEPTH
> +#define FDT_PARENT_MAX_DEPTH 32
> +#endif
> +
>  /*
>   * Defines assumptions which can be enabled. Each of these can be enabled
>   * individually. For maximum safety, don't enable any assumptions!
> diff --git a/tests/parent_offset.c b/tests/parent_offset.c
> index a935a53..9850f31 100644
> --- a/tests/parent_offset.c
> +++ b/tests/parent_offset.c
> @@ -56,6 +56,82 @@ static void check_path(struct fdt_header *fdt, const char *path)
>  		     parentoffset, parentpathoffset);
>  }
>  
> +/*
> + * Check that an offset which does not name a node never yields a parent.
> + * Sweep the whole blob, plus a little either side of it
> + */
> +static void check_bad_offsets(struct fdt_header *fdt)
> +{
> +	int offset, size = fdt_totalsize(fdt);
> +
> +	for (offset = -8; offset < size + 64; offset++) {
> +		int parentoffset;
> +
> +		if (fdt_get_name(fdt, offset, NULL))
> +			continue;	/* a real node, checked elsewhere */
> +
> +		parentoffset = fdt_parent_offset(fdt, offset);
> +		if (parentoffset >= 0)
> +			FAIL("fdt_parent_offset(%d) returns %d for an offset "
> +			     "which is not a node", offset, parentoffset);
> +	}
> +}
> +
> +#define DEEP_SPACE	65536
> +#define DEEP_LEVELS	40
> +
> +#define CHECK(code) \
> +	do { \
> +		int err_ = (code); \
> +		if (err_) \
> +			FAIL(#code ": %s", fdt_strerror(err_)); \
> +	} while (0)
> +
> +/*
> + * Check a tree deeper than fdt_parent_offset() may track in one pass, so
> + * that both it and the fallback for deeper nodes are covered
> + */
> +static void check_deep_tree(void)
> +{
> +	int seen[DEEP_LEVELS + 1];
> +	int offset, depth, level;
> +	void *fdt = malloc(DEEP_SPACE);
> +
> +	if (!fdt)
> +		FAIL("malloc()");
> +
> +	CHECK(fdt_create(fdt, DEEP_SPACE));
> +	CHECK(fdt_finish_reservemap(fdt));
> +	CHECK(fdt_begin_node(fdt, ""));
> +	for (level = 0; level < DEEP_LEVELS; level++)
> +		CHECK(fdt_begin_node(fdt, "node"));
> +	for (level = 0; level < DEEP_LEVELS; level++)
> +		CHECK(fdt_end_node(fdt));
> +	CHECK(fdt_end_node(fdt));
> +	CHECK(fdt_finish(fdt));
> +
> +	for (offset = 0, depth = 0; offset >= 0;
> +	     offset = fdt_next_node(fdt, offset, &depth)) {
> +		int parentoffset;
> +
> +		if (depth < 0)
> +			break;
> +		if (depth > DEEP_LEVELS)
> +			FAIL("tree is %d deep, expected %d", depth,
> +			     DEEP_LEVELS);
> +		seen[depth] = offset;
> +		if (!depth)
> +			continue;
> +
> +		parentoffset = fdt_parent_offset(fdt, offset);
> +		if (parentoffset != seen[depth - 1])
> +			FAIL("fdt_parent_offset() returns %d instead of %d "
> +			     "at depth %d", parentoffset, seen[depth - 1],
> +			     depth);
> +	}
> +	free(fdt);
> +}
> +
>  int main(int argc, char *argv[])
>  {
>  	void *fdt;
> @@ -73,5 +149,8 @@ int main(int argc, char *argv[])
>  		FAIL("fdt_parent_offset(/) returns %d instead of "
>  		     "-FDT_ERR_NOTFOUND", err);
>  
> +	check_bad_offsets(fdt);
> +	check_deep_tree();
> +
>  	PASS();
>  }
> ---
> base-commit: 66e1201c3775716607c28afd2bbb2b3afb08b695
> branch: parent-onepass
> 
> -- 
> 2.43.0
> 
> 

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