[PATCH 2/2] libfdt: Use faster algorithm for fdt_node_offset_by_phandle

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]



fdt_node_offset_by_phandle will return the offset of a node pointed to
by a given phandle.

The current implementation is wasteful: We iterate over all nodes (using
fdt_next_node), call fdt_get_phandle on each one to read the phandle
value (if it's there), compare it with the given phandle, and return the
current node's offset if the values are equal.

fdt_get_phandle itself may iterate over the properties of each node
twice (and usually will, since most nodes will have neither the
"phandle" nor the "linux,phandle" property), and advancing to the next
node via fdt_next_node will then iterate over all properties again.

Fix this by implementing a function fdt_node_offset_by_phandle_, which
recursively walks the device tree, checks each encountered property for
equality with either "phandle" or "linux,phandle", compares the
found phandle's value with the given phandle, and returns the currently
traversed node's offset if they're equal.

Since the function uses fdt_next_tag, it encounters each tag at most
once.

Signed-off-by: Mario Six <mario.six@xxxxxxxx>
---
 libfdt/fdt_ro.c | 72 ++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 58 insertions(+), 14 deletions(-)

diff --git a/libfdt/fdt_ro.c b/libfdt/fdt_ro.c
index 7d049fb..51aedbb 100644
--- a/libfdt/fdt_ro.c
+++ b/libfdt/fdt_ro.c
@@ -605,29 +605,73 @@ int fdt_node_offset_by_prop_value(const void *fdt, int startoffset,
 	return offset; /* error from fdt_next_node() */
 }
 
+static int fdt_node_offset_by_phandle_(const void *fdt, uint32_t phandle,
+				       int *next_offset, int cur_node)
+{
+	uint32_t tag;
+
+	do {
+		int offset;
+		const struct fdt_property *prop;
+		const fdt32_t *php = NULL;
+		int res;
+
+		offset = *next_offset;
+		tag = fdt_next_tag(fdt, offset, next_offset);
+
+		switch (tag) {
+		case FDT_NOP:
+			break;
+		case FDT_END_NODE:
+			if (*next_offset > 0)
+				return -FDT_ERR_NOTFOUND;
+			break;
+		case FDT_BEGIN_NODE:
+			res = fdt_node_offset_by_phandle_(fdt, phandle,
+							  next_offset, offset);
+			if (res >= 0)
+				return res;
+			break;
+		case FDT_END:
+			if (*next_offset >= 0 ||
+			    ((*next_offset == -FDT_ERR_TRUNCATED)))
+				return -FDT_ERR_NOTFOUND;
+			break;
+		case FDT_PROP:
+			if (!(prop = fdt_get_property_by_offset(fdt, offset, NULL)))
+				return -FDT_ERR_INTERNAL;
+
+			if (fdt_string_eq_(fdt, fdt32_to_cpu(prop->nameoff),
+					   "phandle", 7))
+				php = (const fdt32_t *)prop->data;
+
+			if (fdt_string_eq_(fdt, fdt32_to_cpu(prop->nameoff),
+					   "linux,phandle", 5 + 1 + 7))
+				php = (const fdt32_t *)prop->data;
+
+			if (php && fdt32_to_cpu(*php) == phandle)
+				return cur_node;
+
+			break;
+		}
+	} while (tag != FDT_END);
+
+	return -FDT_ERR_TRUNCATED;
+}
+
 int fdt_node_offset_by_phandle(const void *fdt, uint32_t phandle)
 {
-	int offset;
+	int res;
+	int next_offset = 0;
 
 	if ((phandle == 0) || (phandle == -1))
 		return -FDT_ERR_BADPHANDLE;
 
 	FDT_CHECK_HEADER(fdt);
 
-	/* FIXME: The algorithm here is pretty horrible: we
-	 * potentially scan each property of a node in
-	 * fdt_get_phandle(), then if that didn't find what
-	 * we want, we scan over them again making our way to the next
-	 * node.  Still it's the easiest to implement approach;
-	 * performance can come later. */
-	for (offset = fdt_next_node(fdt, -1, NULL);
-	     offset >= 0;
-	     offset = fdt_next_node(fdt, offset, NULL)) {
-		if (fdt_get_phandle(fdt, offset) == phandle)
-			return offset;
-	}
+	res = fdt_node_offset_by_phandle_(fdt, phandle, &next_offset, -1);
 
-	return offset; /* error from fdt_next_node() */
+	return res;
 }
 
 int fdt_stringlist_contains(const char *strlist, int listlen, const char *str)
-- 
2.11.0

--
To unsubscribe from this list: send the line "unsubscribe devicetree-compiler" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html



[Index of Archives]     [Device Tree]     [Device Tree Spec]     [Linux Driver Backports]     [Video for Linux]     [Linux USB Devel]     [Linux Audio Users]     [Linux Kernel]     [Linux SCSI]     [Yosemite Backpacking]

  Powered by Linux