libfdt - flat tree manipulation library

libfdt - flat tree manipulation library

[David Gibson]

So, Mark Greer has already written some library functions for
handling flat device trees, which are included in
arch/powerpc/boot/flatdevtree.c (but could be used elsewhere).  For
several reasons, I don't like the interface very much though.  So,
here's my own somewhat different approach to a flat device tree
library.  Read-only and some very limited write functions so far -
more complete read-write support still in progress (some prototypes
are there already).

Notable design points:
	- Read-only functions are strictly stateless.  That is they
can be invoked directly on a blob without having to create a context
or any other setup.
	- No context management.  I'm pretty sure I can implement even
the read-write functionality by folding the small amounts of extra
context needed into the blob itself, avoiding the need for the caller
to separately set up a context structure.
	- No allocator callback.  The library functions never use
malloc() / realloc() or similar.  Instead read-write functions rely on
the caller explicitly handing blocks of available memory to the
library.  Expanding write calls can fail with "no space".  This makes
some uses more fiddly (but I think that can be mitigated with some
wrappers), but also means read-only functions can be used without an
allocated at all, and read-write functions can be used in (say) a
bootloader with a trivial allocater tracking only a single allocated
block - or simply by giving the library a block so big reallocation
will never be needed.
	- Multiple interfaces for multiple use-cases.  The functions
are divided into groups for different sorts of device tree
manipulation:  read-only functions, in-place-write functions (changes
such as replacing a property value with another of the same size,
which don't require rearrangement of existing structure), sequential
write functions (for creating a full tree from scratch) and
full random-access read-write functions.
	- No phandles.  Instead the library uses structure offsets to
reference nodes.  These can change when functions which insert or
delete information are used.  Persistent phandles are nice, but IMO
not worth the complexity to implement them.  I do plan to implement
functions that will find nodes via the "linux,phandle" property, but
haven't done so yet.

The code, such as it is, is at:
	git://ozlabs.org/home/dgibson/git/libfdt.git

Distribution notes:
	- I'm thinking about merging the library code into the dtc
tree (if nothing else it will make testing dtc rather easier).
	- License is GPL for now.  I'm looking into the red tape to
get it released as BSD or other non-restrictive license, so that it
can be used in closed bootloaders.
	- It's currently pacakaged as a userspace library, but should
be easy to drop into kernel or bootloader context.
	- The tree includes a small testsuite.
	- I don't consider the API final or stable at this stage.

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

Re: libfdt - flat tree manipulation library

[David Gibson]

On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
[snip]
> The code, such as it is, is at:
> 	git://ozlabs.org/home/dgibson/git/libfdt.git

Code for writing device trees from scratch, sequentially, is now
implemented.

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

Re: libfdt - flat tree manipulation library

[David Gibson]

On Wed, Nov 29, 2006 at 04:59:04PM +1100, David Gibson wrote:
> On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> [snip]
> > The code, such as it is, is at:
> > 	git://ozlabs.org/home/dgibson/git/libfdt.git
> 
> Code for writing device trees from scratch, sequentially, is now
> implemented.

And now support for random access read-write is implemented.  The
library is now close to feature-complete, cleanups and convenience
wrappers remain.

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

Re: libfdt - flat tree manipulation library

[Jerry Van Baren]

David Gibson wrote:
> On Wed, Nov 29, 2006 at 04:59:04PM +1100, David Gibson wrote:
>> On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
>> [snip]
>>> The code, such as it is, is at:
>>> 	git://ozlabs.org/home/dgibson/git/libfdt.git
>> Code for writing device trees from scratch, sequentially, is now
>> implemented.
> 
> And now support for random access read-write is implemented.  The
> library is now close to feature-complete, cleanups and convenience
> wrappers remain.

Hi David,

You have not gotten any feedback on your library efforts.  I just 
thought I would let you know I am interested in your code for possibly 
using it in u-boot.  I have not had time to review it carefully and 
compare it to (a) existing u-boot fdt code and (b) current linux fdt 
support but intend to do that soon.

The existing u-boot fdt code is pretty crude (IMHO - makes (a) above a 
nobrainer) and could bear replacing with something that has more 
widespread support and is more flexible.  Easier to use would be a big 
bonus. :-)

Size looks pretty comparable.
$ wc -l libfdt/*.c
   124 fdt.c
   237 fdt_ro.c
   310 fdt_rw.c
   226 fdt_sw.c
   115 fdt_wip.c
  1012 total

$ wc -l arch/powerpc/boot/flatdevtree*.c
   880 flatdevtree.c
    51 flatdevtree_misc.c
   931 total

For u-boot purposes, I would like to create a command that can dump a 
fdt starting at a give node (a string, e.g. "/" for the whole thing, 
"/cpus" for the entire CPU node and subnodes, or "/cpus/#cpus" to get 
just one property).  I don't see a way of doing that directly with your 
current interface.  Am I missing something or would I have to add 
something?  The kernel doesn't need to support interactive fdt 
manipulation, but that would be very beneficial for a bootrom like 
u-boot.  (FWIIW, I've done a "prototype" ;-) version of this command 
with the existing u-boot code.)

If the linux kernel were to adopt your library, how do you envision this 
happening?  Replace the existing code with wrappers (your "convenience 
wrappers"?) to provide a backwards compatible interface (looks nasty and 
negates your simplification advantages) or rip out 'n replace?

Thanks for your efforts,
gvb

Re: libfdt - flat tree manipulation library

[David Gibson]

On Fri, Dec 01, 2006 at 08:11:35AM -0500, Jerry Van Baren wrote:
> David Gibson wrote:
> > On Wed, Nov 29, 2006 at 04:59:04PM +1100, David Gibson wrote:
> >> On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> >> [snip]
> >>> The code, such as it is, is at:
> >>> 	git://ozlabs.org/home/dgibson/git/libfdt.git
> >> Code for writing device trees from scratch, sequentially, is now
> >> implemented.
> > 
> > And now support for random access read-write is implemented.  The
> > library is now close to feature-complete, cleanups and convenience
> > wrappers remain.
> 
> Hi David,
> 
> You have not gotten any feedback on your library efforts.  

Not until now :).

> I just 
> thought I would let you know I am interested in your code for possibly 
> using it in u-boot.  I have not had time to review it carefully and 
> compare it to (a) existing u-boot fdt code and (b) current linux fdt 
> support but intend to do that soon.

Excellent.

> The existing u-boot fdt code is pretty crude (IMHO - makes (a) above a 
> nobrainer) and could bear replacing with something that has more 
> widespread support and is more flexible.  Easier to use would be a big 
> bonus. :-)
> 
> Size looks pretty comparable.
> $ wc -l libfdt/*.c
>    124 fdt.c
>    237 fdt_ro.c
>    310 fdt_rw.c
>    226 fdt_sw.c
>    115 fdt_wip.c
>   1012 total
> 
> $ wc -l arch/powerpc/boot/flatdevtree*.c
>    880 flatdevtree.c
>     51 flatdevtree_misc.c
>    931 total
> 
> For u-boot purposes, I would like to create a command that can dump a 
> fdt starting at a give node (a string, e.g. "/" for the whole thing, 
> "/cpus" for the entire CPU node and subnodes, or "/cpus/#cpus" to get 
> just one property).  I don't see a way of doing that directly with your 
> current interface.  Am I missing something or would I have to add 
> something?  The kernel doesn't need to support interactive fdt 
> manipulation, but that would be very beneficial for a bootrom like 
> u-boot.  (FWIIW, I've done a "prototype" ;-) version of this command 
> with the existing u-boot code.)

You're right: there's no support for traversing a tree - it's all
based on knowing the names in advance, so far.  Well, except for the
_fdt_next_tag() function which is only really intended for internal
use.  I'd been vaguely intending to add another module with traversal
support functions.

What interface would suit for you?  Would
first_subnode()/next_subnode(), first_property()/next_property() be
what you want?  Or would a depth first approach, something like
_fdt_next_tag() be better?  Or an explicit walk_tree() interface, with
a function pointer callbacks?

> If the linux kernel were to adopt your library, how do you envision this 
> happening?  Replace the existing code with wrappers (your "convenience 
> wrappers"?) to provide a backwards compatible interface (looks nasty and 
> negates your simplification advantages) or rip out 'n replace?

Rip out and replace.  Or possibly, make the PReP code in the pipeline
use the new code.  Then a bit later rip out the flatdevtree code.
Because of the existing dt_ops abstraction in the zImage code, the two
flat tree libraries could co-exist, though I think more than very
briefly would not be a great idea.

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

Re: libfdt - flat tree manipulation library

[Grant Likely]

On 11/30/06, David Gibson <david@gibson.dropbear.id.au> wrote:
> On Wed, Nov 29, 2006 at 04:59:04PM +1100, David Gibson wrote:
> > On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> > [snip]
> > > The code, such as it is, is at:
> > >     git://ozlabs.org/home/dgibson/git/libfdt.git
> >
> > Code for writing device trees from scratch, sequentially, is now
> > implemented.
>
> And now support for random access read-write is implemented.  The
> library is now close to feature-complete, cleanups and convenience
> wrappers remain.

I've run into some problems running this on an amd64 host.  There are
problems with the byte swapping code where libfdt.h is trying to byte
swap the fdt pointer, not the value it points to.

Ie, I think this:
#define fdt_magic(fdt)			(fdt32_to_cpu(fdt)->magic)
should really be this:
#define fdt_magic(fdt)			(fdt32_to_cpu(fdt->magic))

As is it doesn't compile on amd64 (and probably not x86 either).  I
suspect that you want to do your byte swap on the value in the
structure field, not on the pointer to the structure.  :)  However,
the test cases fail spectacularly when I change the byte swap to be on
the value in the structure.  If I comment out the byte swap entirely
in libfdt_env.h; then the test cases unexpectedly pass!  So I did some
digging.  The test cases are generating little-endian device trees;
looks like test/trees.S is at fault.  I would say that a different
mechanism is needed to generate the .dtb files.

For example; here's the first 16 bytes of my lite5200 device tree:
00000000  d0 0d fe ed 00 00 15 b7  00 00 00 38 00 00 14 5c  |...........8...\|
Here's the first 16 bytes of tests/rw_tree1.test.dtb; clearly wrong endian!
00000000  ed fe 0d d0 1a 01 00 00  40 00 00 00 08 01 00 00  |........@.......|

Anyway; I'll send a patch to fix up part of the byte swapping code;
but I haven't looked into other ways of creating the .dtb files.

Cheers,
g.



-- 
Grant Likely, B.Sc. P.Eng.
Secret Lab Technologies Ltd.
grant.likely@secretlab.ca
(403) 399-0195

Re: libfdt - flat tree manipulation library

[David Gibson]

On Sat, Dec 02, 2006 at 01:41:48AM -0700, Grant Likely wrote:
> On 11/30/06, David Gibson <david@gibson.dropbear.id.au> wrote:
> > On Wed, Nov 29, 2006 at 04:59:04PM +1100, David Gibson wrote:
> > > On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> > > [snip]
> > > > The code, such as it is, is at:
> > > >     git://ozlabs.org/home/dgibson/git/libfdt.git
> > >
> > > Code for writing device trees from scratch, sequentially, is now
> > > implemented.
> >
> > And now support for random access read-write is implemented.  The
> > library is now close to feature-complete, cleanups and convenience
> > wrappers remain.
> 
> I've run into some problems running this on an amd64 host.  There are
> problems with the byte swapping code where libfdt.h is trying to byte
> swap the fdt pointer, not the value it points to.
> 
> Ie, I think this:
> #define fdt_magic(fdt)			(fdt32_to_cpu(fdt)->magic)
> should really be this:
> #define fdt_magic(fdt)			(fdt32_to_cpu(fdt->magic))

Erk!  That's.. highly embarrasing.  I was getting to testing on a
little endian machine...

> As is it doesn't compile on amd64 (and probably not x86 either).  I
> suspect that you want to do your byte swap on the value in the
> structure field, not on the pointer to the structure.  :)  However,
> the test cases fail spectacularly when I change the byte swap to be on
> the value in the structure.  If I comment out the byte swap entirely
> in libfdt_env.h; then the test cases unexpectedly pass!  So I did some
> digging.  The test cases are generating little-endian device trees;
> looks like test/trees.S is at fault.  I would say that a different
> mechanism is needed to generate the .dtb files.

Oh, crud.  Yes of course.

> For example; here's the first 16 bytes of my lite5200 device tree:
> 00000000  d0 0d fe ed 00 00 15 b7  00 00 00 38 00 00 14 5c  |...........8...\|
> Here's the first 16 bytes of tests/rw_tree1.test.dtb; clearly wrong endian!
> 00000000  ed fe 0d d0 1a 01 00 00  40 00 00 00 08 01 00 00  |........@.......|

Um.. yes.. but in the case if rw_tree1 this is because you commented
out the byteswaps - this one is generated by the code in fdt_rw.c.
test_tree1.dtb is the only one from trees.S

> Anyway; I'll send a patch to fix up part of the byte swapping code;
> but I haven't looked into other ways of creating the .dtb files.

Um.. yes.  I really don't want to have to fuss with hex editors and
including binary files in the distribution.  Ah, but I think I have
the solution, I can make a macro using .byte directives to explicitly
output things with the correct endianness.

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

Re: libfdt - flat tree manipulation library

[Hollis Blanchard]

On Mon, 2006-11-27 at 16:59 +1100, David Gibson wrote:
> 
>         - License is GPL for now.  I'm looking into the red tape to
> get it released as BSD or other non-restrictive license, so that it
> can be used in closed bootloaders.

A GPL license means it cannot be used in Xen today (that part of the
code is BSD-licensed), nor could it be used in developing non-GPL
firmwares.

-Hollis

Re: libfdt - flat tree manipulation library

[David Gibson]

On Thu, Dec 07, 2006 at 02:35:34PM -0600, Hollis Blanchard wrote:
> On Mon, 2006-11-27 at 16:59 +1100, David Gibson wrote:
> > 
> >         - License is GPL for now.  I'm looking into the red tape to
> > get it released as BSD or other non-restrictive license, so that it
> > can be used in closed bootloaders.
> 
> A GPL license means it cannot be used in Xen today (that part of the
> code is BSD-licensed), nor could it be used in developing non-GPL
> firmwares.

Yes, that's kind of my point.  I'm working on it...

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

Re: libfdt - flat tree manipulation library

[Mark A. Greer]

On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> So, Mark Greer has already written some library functions for
> handling flat device trees, which are included in
> arch/powerpc/boot/flatdevtree.c (but could be used elsewhere).  For
> several reasons, I don't like the interface very much though.  So,
> here's my own somewhat different approach to a flat device tree
> library.  Read-only and some very limited write functions so far -
> more complete read-write support still in progress (some prototypes
> are there already).

Hi David.

I've been on other things for the last several weeks and haven't kept up
with all the volume on linuxppc-dev sooo this may be a stupid question...

Have you done any work integrating libfdt into the arch/powerpc/boot
yet?  If so, can you point me to whatever you have?

Thanks,

Mark

Re: libfdt - flat tree manipulation library

[David Gibson]

On Tue, Jan 02, 2007 at 04:29:51PM -0700, Mark A. Greer wrote:
> On Mon, Nov 27, 2006 at 04:59:05PM +1100, David Gibson wrote:
> > So, Mark Greer has already written some library functions for
> > handling flat device trees, which are included in
> > arch/powerpc/boot/flatdevtree.c (but could be used elsewhere).  For
> > several reasons, I don't like the interface very much though.  So,
> > here's my own somewhat different approach to a flat device tree
> > library.  Read-only and some very limited write functions so far -
> > more complete read-write support still in progress (some prototypes
> > are there already).
> 
> Hi David.
> 
> I've been on other things for the last several weeks and haven't kept up
> with all the volume on linuxppc-dev sooo this may be a stupid question...
> 
> Have you done any work integrating libfdt into the arch/powerpc/boot
> yet?  If so, can you point me to whatever you have?

No, not yet.  I had been hoping to get a little more feedback and with
luck stabilize the interface a bit more before merging into the
kernel.

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