[U-Boot-Users] LIBFDT: first version of fdt_find_compatible_node

[Jerry Van Baren <gerald.vanbaren@smiths-aerospace.com>]

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.

--------

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.

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.

Best regards,
gvb