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

[Herve Codina <herve.codina@bootlin.com>]

Hi Simon,

On Thu,  6 Aug 2026 13:13:14 -0600
Simon Glass <sjg@chromium.org> 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.
> 
> 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.
> 
> 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));

The blob used for tests and built here could be improved.

Indeed, it is composed of only one branch:
--- 8< ---
node {
   node {
     node {
       ...
     };
   };
};
--- 8< ---

At a given level, only one node is present.

IMHO, this could be improved in order to have more branches. For instance,
something like this:
--- 8< ---
node {
   node1 {
     node-a{
       ...
     };
   };
   node2 {
     node-b {
       ...
     };
  };
};
--- 8< ---

This allows to check that with several nodes at the same level, the parent
of nodes and sub-nodes are correct.

With given example,
- the parent of node-b must be node2
- the parent of node-a must be node1
- the parent of node1 must be node
- the parent of node2 must be node

Best regards,
Hervé