LIBFDT: first version of fdt_find_compatible_node

Hello,

attached you can find a patch implementing fdt_find_compatible_node():

/*
* Find a node based on its device type and one of the tokens in
* its its "compatible" property. On success, the offset of that
* node is returned or an error code:
*
* startoffset - the node to start searching from or 0, the node

 *                  you pass will not be searched, only the next one
 *                  will; typically, you pass 0 to start the search
 *                  and then what the previous call returned.
 *   type         - the device type string to match against
 *   compat       - the string to match to one of the tokens

* in the "compatible" list.
*/

It should be used as shown below:

    offset = 0;
    do {
        offset = fdt_find_compatible_node(fdt, offset, "type", "comp");
    } while (offset >= 0);

This first hack also implements a cached version as alternative, because tag re-scanning might take quite long. In principle, the cache could also be used for other functions, like fdt_path_offset(), and could be invalidated in case the FDT gets updated.

What do you think?

Thanks.

Wolfgang.

------------------------------------------------------------------------

include/libfdt.h +6 -0

index f8bac73..3fd7c9f 100644
@@ -89,6 +89,12 @@ uint32_t fdt_next_tag(const void *fdt, int offset,
 int fdt_num_reservemap(void *fdt, int *used, int *total);
 int fdt_get_reservemap(void *fdt, int n, struct fdt_reserve_entry *re);
 
+int fdt_node_is_compatible(const void *fdt, int nodeoffset,
+			   const char *compat);
+
+int fdt_find_compatible_node(const void *fdt, int startoffset,
+			     const char *type, const char *compat);
+
 /* Write-in-place functions */
 int fdt_setprop_inplace(void *fdt, int nodeoffset, const char *name,
 			const void *val, int len);

libfdt/fdt_ro.c +2 -0

index 4e2c325..65ede88 100644
@@ -55,6 +55,236 @@ char *fdt_string(const void *fdt, int stroffset)
 	return (char *)fdt + fdt_off_dt_strings(fdt) + stroffset;
 }
 
+#define CONFIG_OF_LIBFDT_TABLE 64
+#if CONFIG_OF_LIBFDT_TABLE > 0

libfdt/fdt_ro.c +19 -0

+#endif  /* CONFIG_OF_LIBFDT_TABLE > 0 */
+
+/*
+ * Check if the specified node is compatible by comparing the
+ * tokens in its "compatible" property with the specified string:
+ *
+ *   nodeoffset - starting place of the node
+ *   compat     - the string to match to one of the tokens
+ *                in the "compatible" list.
+ */
+int fdt_node_is_compatible(const void *fdt, int nodeoffset,
+			   const char *compat)
+{
+	const char* cp;
+	int cplen, l;
+
+	cp = fdt_getprop(fdt, nodeoffset, "compatible", &cplen);
+	if (cp == NULL)
+		return 0;

libfdt/fdt_ro.c +14 -0

+/*
+ * Find a node based on its device type and one of the tokens in
+ * its its "compatible" property. On success, the offset of that
+ * node is return or an error code:
+ *
+ *   startoffset  - the node to start searching from or 0, the node
+ *                  you pass will not be searched, only the next one
+ *                  will; typically, you pass 0 to start the search
+ *                  and then what the previous call returned.
+ *   type         - the device type string to match against
+ *   compat       - the string to match to one of the tokens
+ *                  in the "compatible" list.
+ */
+#if CONFIG_OF_LIBFDT_TABLE > 0

libfdt/fdt_ro.c +64 -0

+#else  /* CONFIG_OF_LIBFDT_TABLE <= 0 */
+int fdt_find_compatible_node(const void *fdt, int startoffset,
+			     const char *type, const char *compat)
+{
+	static int level, typefound;
+	static int nodeoffset, nextoffset;
+	int offset, namestroff;
+	struct fdt_property *prop;
+	uint32_t tag;
+
+	CHECK_HEADER(fdt);
+
+	if (startoffset == 0) {
+		level = 0;
+		tag = fdt_next_tag(fdt, 0, &nextoffset, NULL);
+		if (tag != FDT_BEGIN_NODE)
+			return -FDT_ERR_BADOFFSET;
+	} else if (startoffset != nodeoffset)
+		return -FDT_ERR_BADOFFSET;
+
+	do {
+		offset = nextoffset;
+		tag = fdt_next_tag(fdt, offset, &nextoffset, NULL);
+
+		switch (tag) {
+		case FDT_END:
+			return -FDT_ERR_TRUNCATED;
+
+		case FDT_BEGIN_NODE:
+			level++;
+			nodeoffset = offset;
+			typefound = 0;
+			break;
+
+		case FDT_END_NODE:
+			level--;
+			break;
+
+		case FDT_PROP:
+			if (typefound)
+				continue;
+
+			prop = fdt_offset_ptr_typed(fdt, offset, prop);
+			if (! prop)
+				continue;
+			namestroff = fdt32_to_cpu(prop->nameoff);
+			if (streq(fdt_string(fdt, namestroff), "device_type")) {
+				int len = fdt32_to_cpu(prop->len);
+				typefound = 0;
+				prop = fdt_offset_ptr(fdt, offset,
+						      sizeof(*prop)+len);
+				if (! prop)
+					continue;
+				if (strncasecmp(prop->data, type, len - 1) == 0 &&
+				    fdt_node_is_compatible(fdt, nodeoffset, compat))
+					return nodeoffset;
+			}
+			break;
+
+		case FDT_NOP:
+			break;
+
+		default:
+			return -FDT_ERR_BADSTRUCTURE;

Quoted 3 lines · Wolfgang Grandegger

Hello,

attached you can find a patch implementing fdt_find_compatible_node():

Yeeee-ha! :-)

Quoted 28 lines

/*
* Find a node based on its device type and one of the tokens in
* its its "compatible" property. On success, the offset of that
* node is returned or an error code:
*
* startoffset - the node to start searching from or 0, the node

 *                  you pass will not be searched, only the next one
 *                  will; typically, you pass 0 to start the search
 *                  and then what the previous call returned.
 *   type         - the device type string to match against
 *   compat       - the string to match to one of the tokens

* in the "compatible" list.
*/

It should be used as shown below:

    offset = 0;
    do {
        offset = fdt_find_compatible_node(fdt, offset, "type", "comp");
    } while (offset >= 0);

This first hack also implements a cached version as alternative, because tag re-scanning might take quite long. In principle, the cache could also be used for other functions, like fdt_path_offset(), and could be invalidated in case the FDT gets updated.

What do you think?

Quoted 3 lines

Thanks.

Wolfgang.

Looks good. In the real patch, I would like to see the cache addition split from the fdt_node_is_compatible() fdt_find_compatible_node() and addition.

Quoted 26 lines

(quoted diff) +26 -0

+#endif  /* CONFIG_OF_LIBFDT_TABLE > 0 */
+
+/*
+ * Check if the specified node is compatible by comparing the
+ * tokens in its "compatible" property with the specified string:
+ *
+ *   nodeoffset - starting place of the node
+ *   compat     - the string to match to one of the tokens
+ *                in the "compatible" list.
+ */
+int fdt_node_is_compatible(const void *fdt, int nodeoffset,
+               const char *compat)
+{
+    const char* cp;
+    int cplen, l;
+
+    cp = fdt_getprop(fdt, nodeoffset, "compatible", &cplen);
+    if (cp == NULL)
+        return 0;
+    while (cplen > 0) {
+        if (strncmp(cp, compat, strlen(compat)) == 0)
+            return 1;
+        l = strlen(cp) + 1;
+        cp += l;
+        cplen -= l;
+    }

Review

Quoted 3 lines

(quoted diff) +3 -0

+
+    return 0;
+}

I see this came directly from arch/powerpc/kernel/prom.c, but using "l" for a variable is evil. For a minute, I was wondering how the compiler was compiling "1" (one) as a lvalue. I would prefer it to be "len" or something more descriptive.

For the above version of fdt_find_compatible_node(), as well as the one that fills the cache table (snipped), I'm thinking it would be better to use the function I added:

uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset, char **namep)

I added this to step through the nodes and properties for dumping the tree. Rather than having Yet Another (slightly modified) Copy of the loop & switch, you should be able to use fdt_next_tag() to step through the nodes and properties, doing the
if (streq(fdt_string(fdt, namestroff), "device_type"))
on the **namep parameter on every call to find the device_type properties. Does this make sense?

Quoted 4 lines · Jerry Van Baren

Quoted 3 lines · Wolfgang Grandegger

Hello,

attached you can find a patch implementing fdt_find_compatible_node():

Quoted 7 lines

For the above version of fdt_find_compatible_node(), as well as the one that fills the cache table (snipped), I'm thinking it would be better to use the function I added:

uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset, char **namep)

Quoted 7 lines

I added this to step through the nodes and properties for dumping the tree. Rather than having Yet Another (slightly modified) Copy of the loop & switch, you should be able to use fdt_next_tag() to step through the nodes and properties, doing the
if (streq(fdt_string(fdt, namestroff), "device_type"))
on the **namep parameter on every call to find the device_type properties. Does this make sense?

Yes, my concern was the overhead due to looking up the location of each node name and property. But for fast scanning, the cached version is much better anyhow, I think.

What is your opinion on the cached version? Do we need it? Should we keep both?

Wolfgang.

Quoted 5 lines · Wolfgang Grandegger

Quoted 4 lines · Jerry Van Baren

Quoted 3 lines · Wolfgang Grandegger

Hello,

attached you can find a patch implementing fdt_find_compatible_node():

[snip]

Quoted 15 lines

Quoted 7 lines

For the above version of fdt_find_compatible_node(), as well as the one that fills the cache table (snipped), I'm thinking it would be better to use the function I added:

uint32_t fdt_next_tag(const void *fdt, int offset, int *nextoffset, char **namep)

Quoted 7 lines

I added this to step through the nodes and properties for dumping the tree. Rather than having Yet Another (slightly modified) Copy of the loop & switch, you should be able to use fdt_next_tag() to step through the nodes and properties, doing the
if (streq(fdt_string(fdt, namestroff), "device_type"))
on the **namep parameter on every call to find the device_type properties. Does this make sense?

Quoted 8 lines

Yes, my concern was the overhead due to looking up the location of each node name and property. But for fast scanning, the cached version is much better anyhow, I think.

What is your opinion on the cached version? Do we need it? Should we keep both?

Wolfgang.

Hi wg,

Yes, blob parsing will be done from the start of the blob until an answer is found every time a question is asked of it. Not a paradigm of efficiency. :-/

WRT the cached version, I have doubts about how much time it will save since I expect the "find compatible" will only be used during initialization. Is it worth optimizing? Really slow memory - yes. Fast memory - I doubt it.
a) I don't picture blobs being stored in really slow memory (no i2c memories).
b) If the memory really is slow, it seems like it would be as good or better to copy the blob to RAM and use it out of RAM (but there may be chicken & egg problems with that - I don't know how deeply you are looking to embed this).

I don't know what board/processor/memory you are ultimately targeting with this, so my criticisms may not be valid. I know denx.de support(s|ed) some very slow to boot boards that lots of tricks were done WRT optimization of env variables because they were stored in i2c memory.

--------

Other puzzlements:

You are storing "level" in the cache table, I don't see why. That is only used while scanning the blob to keep track of node nesting and unnesting and exit when we've unnested back out to the original level. Nesting isn't really applicable when it is in the cache.

In fdt_find_compatible_node() you have local static variables:

(quoted diff) +2 -0

+    static int level, typefound;
+    static int nodeoffset, nextoffset;

and I don't understand why. I expected them to be auto variables, initialized on entry and discarded on exit.

Looking closer at your cached version, I see you really are using nodeoffset as a persistent variable there and I cringe a bit. That implementation presumes you ask questions sequentially or always reset to 0. This would prevent you from, for instance, searching for the "/soc8360 at ..." node using fdt_path_offset() and then looking for devices inside that node. Given what is being represented and how, perhaps I'm creating an unreasonable strawman.

Instead of using a static variable, you could scan the cache table for an element whose stored offset is greater than or equal to startoffset, and search the table forward from there (the offsets in the table will be monotonically increasing because of how you build the table). Slightly less efficient, but it will still be pretty good and much better than scanning the whole blob... or maybe I'm complaining based on an unreasonable strawman.

After writing all the above, it bothers me a bit that the hierarchical tree structure of the device tree is getting stuck into a one dimensional cache (the hierarchy is lost), but I cannot think at this point why that would bite us down the road.

Quoted 1 line · Wolfgang Grandegger

Jerry Van Baren wrote:

Quoted 15 lines

Yes, blob parsing will be done from the start of the blob until an answer is found every time a question is asked of it. Not a paradigm of efficiency. :-/

WRT the cached version, I have doubts about how much time it will save since I expect the "find compatible" will only be used during initialization. Is it worth optimizing? Really slow memory - yes. Fast memory - I doubt it.
a) I don't picture blobs being stored in really slow memory (no i2c memories).
b) If the memory really is slow, it seems like it would be as good or better to copy the blob to RAM and use it out of RAM (but there may be chicken & egg problems with that - I don't know how deeply you are looking to embed this).

Quoted 5 lines

I don't know what board/processor/memory you are ultimately targeting with this, so my criticisms may not be valid. I know denx.de support(s|ed) some very slow to boot boards that lots of tricks were done WRT optimization of env variables because they were stored in i2c memory.

I'm doing that for a MPC823 at 50 MHz, a very low-end system, and almost to slow for 2.6. I will do some real measurements when time permits to get a better feeling.

Hi Jerry,

Quoted 2 lines

Quoted 1 line · Wolfgang Grandegger

Jerry Van Baren wrote:

[snip]

Quoted 21 lines

Quoted 15 lines

Yes, blob parsing will be done from the start of the blob until an answer is found every time a question is asked of it. Not a paradigm of efficiency. :-/

WRT the cached version, I have doubts about how much time it will save since I expect the "find compatible" will only be used during initialization. Is it worth optimizing? Really slow memory - yes. Fast memory - I doubt it.
a) I don't picture blobs being stored in really slow memory (no i2c memories).
b) If the memory really is slow, it seems like it would be as good or better to copy the blob to RAM and use it out of RAM (but there may be chicken & egg problems with that - I don't know how deeply you are looking to embed this).

Quoted 5 lines

I don't know what board/processor/memory you are ultimately targeting with this, so my criticisms may not be valid. I know denx.de support(s|ed) some very slow to boot boards that lots of tricks were done WRT optimization of env variables because they were stored in i2c memory.

Quoted 3 lines

I'm doing that for a MPC823 at 50 MHz, a very low-end system, and almost to slow for 2.6. I will do some real measurements when time permits to get a better feeling.

Here are the results of some quick measurements on my MPC855 at 80/40 MHz with the attached code example and my DTS test file:

from FLASH from Memory

Non-cached:    11116 us       1703 us
Cached    :     2800 us       6226 us

Well, I think we can drop the cached version even if its 4 times faster, as it make life more difficult, especially in case the FDT gets updated.

Wolfgang.

Quoted 41 lines · Wolfgang Grandegger

Hi Jerry,

Quoted 2 lines

Quoted 1 line · Wolfgang Grandegger

Jerry Van Baren wrote:

[snip]

Quoted 21 lines

Quoted 15 lines

Yes, blob parsing will be done from the start of the blob until an answer is found every time a question is asked of it. Not a paradigm of efficiency. :-/

WRT the cached version, I have doubts about how much time it will save since I expect the "find compatible" will only be used during initialization. Is it worth optimizing? Really slow memory - yes. Fast memory - I doubt it.
a) I don't picture blobs being stored in really slow memory (no i2c memories).
b) If the memory really is slow, it seems like it would be as good or better to copy the blob to RAM and use it out of RAM (but there may be chicken & egg problems with that - I don't know how deeply you are looking to embed this).

Quoted 5 lines

I don't know what board/processor/memory you are ultimately targeting with this, so my criticisms may not be valid. I know denx.de support(s|ed) some very slow to boot boards that lots of tricks were done WRT optimization of env variables because they were stored in i2c memory.

Quoted 3 lines

I'm doing that for a MPC823 at 50 MHz, a very low-end system, and almost to slow for 2.6. I will do some real measurements when time permits to get a better feeling.

Here are the results of some quick measurements on my MPC855 at 80/40 MHz with the attached code example and my DTS test file:

from FLASH from Memory

Non-cached:    11116 us       1703 us
Cached    :     2800 us       6226 us

Well, I think we can drop the cached version even if its 4 times faster, as it make life more difficult, especially in case the FDT gets updated.

Quoted 1 line

Wolfgang.

Risk & reward. The reward is pretty substantial if you read directly from slow flash, but iffy for faster RAM.

In the "from Memory" column, do you have the numbers switched? The non-cached is shown as being 4x faster than the cached.

To be a fair comparison, the "from Memory" column also needs the time it would take to copy the blob from flash to RAM added, yes? That penalty can be bypassed by loading the blob directly into RAM via tftp or the copy to RAM time may already be part of the boot process, but it should be identified.