[U-Boot] Merging device trees at runtime for module-based systems

[David Gibson]

On Thu, Nov 01, 2012 at 10:24:06AM +0100, Daniel Mack wrote:
> On 01.11.2012 04:26, David Gibson wrote:
> > On Fri, Oct 26, 2012 at 09:24:11AM +0200, Daniel Mack wrote:
> 
> >> I would especially like to know where such a new functionality should
> >> live, which data types it should operate on and what would be an
> >> appropriate name for it.
> > 
> > So.. the first thought I have reading the original mail in the thread
> > is that it's arguable that you really want a more heavyweight firmware
> > for this setup, that actively maintains a live device tree as OF does,
> > rather than u-boot which is pretty oriented towards a close-to-static
> > device setup.  That's just a thought though, I'm not saying that at
> > least some of this functionality doesn't belong in libfdt.
> > 
> > So, my thought would be that stuff for manipulating big chunks of tree
> > should go in a new .c file inside the libfdt tree.  We already have
> > del_node and nop_node of course, which can remove whole subtrees.  I
> > guess the big extra function you'd want would be something like:
> > 
> > fdt_graft(void *fdt, int offset, void *subtree);
> > 
> > Which would graft the tree blob give by subtree into the "master" tree
> > (fdt) at node 'offset'.  Actually that might need to take a name for
> > the top-level of the subtree to take in the new tree too.
> 
> I called the function fdt_overlay, but I guess the implementation is
> similar to what you thought of. I pushed it here, see the topmost 3 commits:
> 
>   https://github.com/zonque/dtc/commits/overlay

Interesting.  So, it seems to me that fdt_graft() and fdt_overlay()
are different operations - both could be potentially useful.
fdt_graft() would attach a new subtree somewhere within the master
tree, with the assumption that the root of the subtree would become a
new node in the resulting tree.  Overwriting an existing subtree with
a new one would be an error for a graft.  fdt_overlay, as you've
implemented, can either add new nodes or modify existing ones by
replacing or adding new properties.

So, some notes on the actual implementation:

The in-place modification of the given path (which should really be
const char *) in your fdt_add_subnode_r() is nasty, nasty, nasty.  And
it's unnecessary because you can use the existing
fdt_add_subnode_namelen() to work with subsections of the path without
needing to either have a temporary buffer or do in-place modification.

...except, I don't think you actually need fdt_add_subnoode_r() for
your overlay implementation in any case.

AFAICT in your fdt_overlay() implementation you're only adding nodes
from the second tree if they contain properties (the
fdt_add_subnode_r() call is under the FDT_PROP case).  I'm not sure if
that was a deliberate policy decision - if so I really can't see a
reason for it.

If instead you *always* add subnodes when they exist in the second
tree, you'll be doing your add nodes from the FDT_BEGIN_NODE tag
case.  And you always get BEGIN_NODE tags for parents before subnodes,
so you can naturally add your new subnode path component by component
without having to walk down the path again in fdt_add_subnode_r().  As
an added bonus you no longer need pathbuf and it's arbitrary size
limit.

Hrm.. wait... I guess you need a stack so you can handle FDT_END_NODE
correctly.  I suspect a recursive solution (effectively using the
machine stack) would still take less (machine) stack space than
pathbuf.  Especially if pathbuf was increased up to PATH_MAX, which is
my usual rule of thumb when I can't avoid an arbitrary buffer size.	


On a tangent, note that fdt_graft() as defined above, unlike
fdt_overlay() would allow a considerably optimized implementation.
Instead of doing lots of individual inserts into the tree (and
therefore a lot of memmove()s), you could do one big _fdt_splice(),
copy in the grafted tree's structure block, then run through it
correcting property name offsets.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson