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

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

[Simon Glass]

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));
+
+	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

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

[Herve Codina]

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é

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

[David Gibson]

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