[U-Boot] fdt performance

[Simon Glass]

Hi Scott,

On Thu, Nov 14, 2013 at 4:36 PM, Scott Wood <scottwood at freescale.com> wrote:

> On Thu, 2013-10-17 at 16:27 -0600, Simon Glass wrote:
> > Hi Aaron,
> >
> > On Thu, Oct 17, 2013 at 12:24 AM, Aaron Williams
> > <Aaron.Williams at caviumnetworks.com> wrote:
> > > Hi all,
> > >
> > > In our bootloader based off of 2013.07 we make extensive use of the
> flat
> > > device tree. In profiling our bootloader in our simulator I found that
> the
> > > function eating up the most time is fdt_next_tag. Looking at it,
> especially
> > > fdt_offset_ptr, it looks like there is a lot of room for improvement
> > > especially in the skip name section.
> > >
> > > Some of the checks in fdt_offset_ptr also look useless, such as if
> ((offset
> > > + len) < offset) which will always be false, or
> > > if (p + len < p)
> > >
> > > len is always positive.
> >
> > Are you using CONFIG_OF_CONTROL?
> >
> > If so, as a higher-level point, we could bring in an efficient DT
> > library, which converts the the FDT into a tree structure for faster
> > parsing. I can point you to a starting point if you like.
>
> I've also seen it be a noticeable performance problem (in slow
> simulation environments) on the extensive DT fixups we do on FSL PPC
> (repeated calls to functions like fdt_node_offset_by_compat_reg are
> particularly bad).
>
> Though, when it comes to parsing the tree, rather than modifying it, I'm
> not sure that the flattened data structure is all that much worse than
> an unflattened tree.  Lookups by path would be faster, but lookups by
> compatible would still have to visit every node.  I think the usage
>

My thought was that compatible strings would be collated somewhere so there
is an efficient way to find them. However, that might violate the
simplicity rule.


> patterns are at least part of the problem -- repeatedly scanning the
> entire tree, rather than going over it once and assigning node offsets
> to drivers.  The driver model ought to help here.
>
> FWIW, if there is interest in unflattening the device tree, Freescale's
> hypervisor has code for this:
>
> http://git.freescale.com/git/cgit.cgi/ppc/sdk/hypervisor/hypervisor.git/tree/src/livetree.c
>
> http://git.freescale.com/git/cgit.cgi/ppc/sdk/hypervisor/hypervisor.git/tree/include/devtree.h
>
> I'm not sure how it compares to the code Simon had in mind, but it
> supports merging nodes which could be useful for boards that do dynamic
> device tree updates.
>

Well that code looks great. I'm not sure if we have the demand as yet (as
you say driver model should largely allow the tree to be scanned
sequentially and only once) but I am sure it will come up one day.

Regards,
Simon