Jerry Van Baren wrote:
Wolfgang Grandegger wrote:
Jerry Van Baren wrote:
Wolfgang Grandegger wrote:
Hello,
attached you can find a patch implementing fdt_find_compatible_node():
[snip]
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?
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.
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.
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:
- 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.
This is to continue a scan started with startoffset=0.
* 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.
And it could be used in the following way:
offset = 0; do { offset = fdt_find_compatible_node(fdt, offset, "type", "comp"); } while (offset >= 0);
This is to be compatible with the Linux version (prom.c) and to scan for more than one compatible device efficiently (without re-scanning). For example, for the MPC5200 there are 8 compatible GPTs defined. To do so, we must preserve nextoffset and level. I also preserve typefound and nodeoffset for efficiency reasons and to check sub-sequent calls of fdt_find_compatible_node().
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@..." 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.
Yes that's the current behaviour for both versions. I thought a scan will always be started with 0. Nevertheless, as I see it, the Linux version does not use the hierarchy but just scans all device (nodes) sequentially. But this could be changed easily and I was already thinking to do so.
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.
Slightly less efficient, yes, that was my motivation. In U-Boot we access the libfdt always sequentially and therefore the trick with static variables for efficiency seems OK to me.
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.
See above. I have to check my assumption, though. Let's clarify first the intended behavior of fdt_find_compatible_node().
Wolfgang.