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

[Daniel Mack]

On 03.11.2012 16:25, David Gibson wrote:
> 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.

Ok - thanks for the hint. I was looking for a nicer way as I also was
really unhappy about the implementation, but without access to heap
operations and avoid eating up too much stack, I thought this is a nasty
but working solution.

After all, that whole hacking was just meant as a proof of concept for
the result, which failed ;)

> ...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.

That was merely to spare some cycles, as fdt_add_subnode_r() turned out
not to be free of costs.

> 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.

Yes, I had something like that in mind, but that requires keeping the
state of both trees around and care for the stacking etc.

> 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.

Given the fact that this implementation turns out to be inappropriate as
solution to my actual problem, I'm uncertain whether it should be merged
at all. Dunno of how much use that would be for others after all.


Many thanks for you input,
Daniel