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

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

 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