New FDT format

From eLinux.org
Revision as of 08:46, 17 May 2021 by Frowand (talk | contribs) ((3) Devicetree atom table: fix media link)
Jump to: navigation, search


updated: Mon May 17 09:58:48 CDT 2021

'Please do not edit this page. If you have any changes for this page, please send them to frowand.list (at) gmail (dot) com.'
This page may move to a new elinux.org location in the future. Do not expect this elinux.org URL to remain valid.

Purpose of This Page

The intent of this page is to summarize past discussion (starting January 2018) and summarize ongoing discussion of the changes between the Devicetree FDT format versions 17 and 18.

The actual discussion is expected to occur in public, in locations where the actual discussion is captured directly, such as mail lists.

TODO

  • Add items to Devicetree Specification for existing features
    • /plugin/
  • Add items to Devicetree Specification for new features

Location of Ongoing Discussion and Review

TODO: any other locations?

  • devicetree mail list
  • devicetree compiler mail list
  • u-boot mail list ???
  • Linaro DTE bi-weekly conference call (and archives....)
  • any other?

Goals

NOTE: goals may conflict in various portions of the design. If this occurs, the relative importance of the goals will need to be considered for each case.

  • Reduce size of FDT
    • On disk or other storage media
    • In memory
  • Reduce cpu and memory access overhead of accessing FDT
    • Unflattening
    • Direct access of FDT if not unflattening
  • Add functionality related to overlays
    • /delete-node-overlay/
    • /delete-property-overlay/
    • Is anything needed in the FDT format to be able to apply an overlay "plug" node into multiple "socket" nodes (eg "connector" architecture issues)?
  • Improve ability of decompile to reflect original source
    • type info
    • comments
  • In-place modification of existing FDT
    • Choose one of the following:
      • (1) All modifications must be possible in place.
        • Example: A property can be deleted by changing the FDT_PROP tag and all bytes up to, but not including, the following tag to FDT_NOP tags.
      • (2) All modifications must be possible either in place, or by inserting additional information at the end of the relevent block.
        • For the structure block, "at the end of the relevent block" means inserting immediately before the FDT_END at the end of the block.
          • Example: The value of a property can be changed to a value that requires more bytes to contain it by (1) deleting the property in the current node and (2) inserting at the end of the structure block: nested FDT_BEGIN_NODE/node_info/FDT_END_NODE to describe the node that contains the property, and the node_info of the node contains the new value of the property following an FDT_PROP token.
            • CON: The contents of a node can not be determined without scanning the entire structure block since a node may be split into multiple pieces. This seems to be a severe negative.
      • (3) All modifications must be possible either in place, or by inserting additional information 'within an existing node by shifting all following bytes in the structure block "to the right", eg to a higher address.
        • This requires the updating of any reference to the address of any object in the bytes that are shifted.
      • (5) Any modification that can not be performed by overwriting existing data with FDT_NOP tags expects the rewriting of the entire FDT. This is envisioned as unpacking the FDT into whatever data structure the modifying program desires (for example an actual tree data structure), performing the desired modification(s) on the data structure, then re-creating an FDT from the data structure.
      • (6) TODO: any other options?
  • Add signatures
  • Add type info
    • phandle vs. u64 vs. u32
    • bit fields, etc
    • enums? structs?

Non-goals

  • Remain compatible with previous version if possible
    • This version is expected to create a break in compatibility
    • Should attempt to identify all desired features that will break compatibility so next compatibility break will be far in the future

Constraints

  • Will need to support current version for a TBD length of time after new version is completed

Proposals Status

(1) Rowand: overlay metadata, add other sections, etc status: obsolete, augmented or replaced by (1.1)

(1.1) Gibson: follow up to (1) Rowand status: active

(2) Glass: various status: active

(3) Mills: atoms status: active

(4) Mills: signatures status: active NOTES: If this change is backward compatible with version 17, consider creating a version 18 with _only_ this change, then a subsequent version 19 that is _not_ backward compatible.

Stake Holders

  • Linux kernel
  • DTC
    • compiler
    • libfdt
    • fdtoverlay
  • U-Boot
  • BSDs
    • One has its own DTC
  • RTOS
    • Zephyr (mostly DTS)
      • Have their own DTS parser, DOM lib, and code gen
      • Want to make it more generic
    • Vxworks (uses runtime DT of some sort?)
  • Any others?

overlay delete tags

Version 17 of the FDT format does not define a structure block token to delete a node or to delete a property. Thus the source level constructs /delete-node-overlay/ and /delete-property-overlay/ will remove a node or property that is defined within the source of the overlay but will not remove that same node or property from an existing tree that the overlay is applied against.

It should be possible to logically delete a node by setting the node's "status" property value to something other than "okay", such as "disabled". But the current Linux is not consistent in checking node status before using a node.

The current standard specifies values:

  • okay
  • disabled
  • fail
  • fail-sss

The values which the Linux kernel functions of_fdt_device_is_available() and __of_device_is_available() treat as valid node are:

  • okay
  • ok
  • no "status" property

Even if a node is logically deleted by an overlay, the space in the live tree that defines the node, node properties, and sub-nodes remains in the live tree; the amount of memory used does not decrease.

Previous Proposals

This topic has been under discussion for several years. This section is an attempt to document previous proposals as of April 2021.

people involved in the discussions

TODO: add more people

Alan Tull <atull@kernel.org>
Bill Mills <bill.mills@linaro.org>
David Gibson <david@gibson.dropbear.id.au>
Frank Rowand <frowand.list@gmail.com>
Geert Uytterhoeven <geert@linux-m68k.org>
Grant Likely <grant.likely@secretlab.ca>
Jon Loeliger <jdl@jdl.com>
Kyle Evans <kevans@FreeBSD.org>
marek.vasut@gmail.com
Michael Ellerman <mpe@ellerman.id.au>
Pantelis Antoniou <pantelis.antoniou@konsulko.com>
Pantelis Antoniou <panto@antoniou-consulting.com>
Rob Herring <robh+dt@kernel.org>
Simon Glass <sjg@chromium.org>
Tom Rini <trini@konsulko.com>

"devicetree-spec@vger.kernel.org" <devicetree-spec@vger.kernel.org>
"devicetree@vger.kernel.org" <devicetree@vger.kernel.org>,
Devicetree Compiler <devicetree-compiler@vger.kernel.org>

plus Plumbers 2018 attendees



(1) Rowand, overlay metadata, add other sections, etc

initial email, Frank Rowand, Jan 22, 2018

Initial email in the thread. This email asks for other people to suggest their needs that would require an FDT format change and provides some size data for the proposed new format. This email does not describe the new format, which will be done later in the thread. This proposal was focused on changes to better support overlays.

Lore may fail to properly navigate between messages in this thread.
  If so, ignore the Lore lines tagged '[not found]' or use the following list instead.
The following list provides a lore link for each message.
The nesting, ordering, and time stamps are provided by
mutt on my computer, using a local mbox.

  1 180122 02:09  Frank Rowand        [RFC] devicetree: new FDT format version lore link
  2 180122 02:14  Frank Rowand        ├─> lore link
  3 180122 14:08  Frank Rowand        │ └─> lore link
  4 180122 14:08  Frank Rowand        ├─> lore link
  5 180124 18:27  Frank Rowand        │ └─> lore link
  6 180127 02:48  David Gibson        │   └─> lore link
  7 180129 02:08  Frank Rowand        │     └─> lore link
  8 180129 04:56  David Gibson        │       └─> lore link
  9 180129 19:29  Frank Rowand        │         └─> lore link
 10 180122 15:01  Rob Herring         ├─> lore link
 11 180123 06:42  David Gibson        │ └─> lore link
 12 180123 15:17  Frank Rowand        │   └─> lore link
 13 180124 09:47  Rob Herring         │     ├─> lore link
 14 180124 15:16  Frank Rowand        │     │ ├─> lore link
 15 180124 16:27  Alan Tull           │     │ │ ├─> lore link
 16 180124 18:22  Frank Rowand        │     │ │ ├─> lore link
 17 180125 06:29  David Gibson        │     │ │ │ └─> lore link
 18 180125 14:01  Frank Rowand        │     │ │ │   ├─> lore link
 19 180129 12:32  Grant Likely        │     │ │ │   │ └─> lore link
 20 180129 17:15  David Gibson        │     │ │ │   │   └─> lore link
 21 180126 02:56  Geert Uytterhoeven  │     │ │ │   └─> lore link
 22 180126 02:59  Geert Uytterhoeven  │     │ │ │     ├─> lore link
 23 180126 16:08  Frank Rowand        │     │ │ │     ├─> lore link
 24 180127 03:00  David Gibson        │     │ │ │     │ └─> lore link
 25 180127 02:56  David Gibson        │     │ │ │     └─> lore link
 26 180125 17:11  Frank Rowand        │     │ │ └─> lore link
 27 180125 06:22  David Gibson        │     │ └─> lore link
 28 180125 03:14  Marek Vasut         │     └─> lore link
 29 180125 06:37  David Gibson        │       └─> lore link
 30 180127 14:30  Marek Vasut         │         └─> lore link
 31 180128 18:53  David Gibson        │           └─> lore link
 32 180123 06:05  David Gibson        └─> lore link
 33 180123 15:28  Frank Rowand          └─> lore link
proposed implementation

Proposal Summary:

  • new FDT version
  • backward compatible (except for overlays)
  • replace overlay nodes __symbols__, __fixups__, and __local_fixups__ with a symbol table
  • data fields that validation tools could optionally populate, and boot loaders and kernels could optionally require
  • significant size reduction of FDT that contains symbol information needed to apply overlays
    • on storage media
    • in memory
  • small increase in FDT that does not include symbol information for overlays (~ 100 bytes)
  • allows easy implementation of Linux kernel overlay application in early boot, in association with FDT unflattenning
  • simplifies the implementation of the Linux kernel overlay apply to the live tree, post-boot
  • patches were created against Linux 4.15-rc7 to verify the feasibility of the kernel changes, but the patches were not shared

Size reduction data was calculated for all of the .dts files in the Linux kernel source tree at arch/arm/boot/dts/ as of v4.15-rc7. The key column is "saved", which is how many bytes smaller the .dtb with symbols for the new format compared to the existing format.

The following table is sorted from most bytes saved, to least, with
one entry at approximately every 16 percentile:

row   dtb no   delta    delta    delta    saved
      symbols  no_sym   symbols  new fmt
----  -------  -------  -------  -------  -------
 99%    90531      134    42721    15766    26955  am57xx-beagle-x15-revb1.dtb
 83%    44302      139    14582     5163     9419  imx6dl-tx6dl-comtft.dtb
 66%    26277      132    11662     4628     7034  sun6i-a31s-sinovoip-bpi-m2.dtb
 49%    21047      130     7328     2754     4574  imx53-qsb.dtb
 33%    12864      137     4305     1705     2600  kirkwood-netgear_readynas_nv+_v2.dtb
 16%    12009      128     2929     1520     1409  bcm911360k.dtb
  0%     1220      133       68      149      -81  xenvm-4.2.dtb

The full list of size reduction for the arm .dtb files was provided in a
reply to the initial email.

The full list is also shown in graphical form in a Plumbers 2018 presentation,
 [PDF] "Overlay", Frank Rowand, where slide 18 shows the size of
the .dtb files: current FDT format (green) vs proposed format (blue).


The proposed implementation was provided in a reply to the initial email.

For reference, the existing FDT version 17 format contains
* header
* mem_rsvmap block
* dt_struct block
* dt_strings block

The summary here is slightly different than the proposal in the email (removing some ideas that have not aged well).

  • new header field containing the offset of a new block "blocks"
    • this block would contain the offsets of all other blocks, including the blocks present in version 17
    • this would allow the existing block offsets to be removed from the current non-contiguous locations in the header, at the expense of breaking backward compatibility
    • this might allow adding additional blocks in future FDT versions without breaking backward compatibility
    • this adds slight code complexity to accessing the base location of each block (one added level of indirection)
    • REVIEW COMMENTS:
      • just append to header, maybe as an array
      • current scatter of offsets in header is ugly, but not bad enough to warrant the extra complexity of the "blocks" block
      • does not allow adding additional blocks in future FDT versions without breaking backward compatibility
  • new header field "chained" - probably a bad idea
    • REVIEW COMMENTS: negative comments
  • new header field "phandle_delta"
    • to handle a Linux kernel implementation detail, this would be better handled inside a kernel variable
  • new block "csums"
    • contains a separate checksum for each block
    • based on a suggestion by Grant Likely to be able to detect if a bootloader that did not understand the new version modified the FDT in a manner that corrupts the new data
    • probably overkill because the overall FDT checksum should detect the corruption
    • REVIEW COMMENTS:
      • no reason to have an extra block instead of fields in the "blocks" block or extra fields in the main header.
      • need to specify a checksum algorithm
  • three blocks to provide the overlay metadata, in a form that is more compact than the existing form, and easier to parse
    • "ext_phandle_use"
      • analagous to the data in the __fixups__ node
    • "int_phandle_use"
      • analagous to the data in the __local_fixups__ node
    • "symbols"
      • describes the phandle properties in the dt_strings block
    • REVIEW COMMENTS (overlay metadata):
      • need a more coherent description
      • metadata will need updating with any insertion or deletion in the tree, which is a bit of a pain.
      • (dgibson) Instead of adding new blocks, add new tags to the structure block
        • FDT_EXTERNAL_PHANDLE with a property offset and strings table offset would replace a __fixups__ entry
        • FDT_INTERNAL_PHANDLE with just a property offset would replace a __local_fixups__ entry.
          • They don't need an explicit property reference, because they would just apply to the immediately preceding property.
        • That approach means we're back to local data, which can be shuffled around pretty easily for inserts and deletes. You'd have to adjust offsets in the fixups for one property when it was altered but not any further away than that.
        • Whenever you insert and delete (for reals, not with nops) you need to adjust all the offsets in the fixup blocks - and remove any fixups that reference something in a deleted chunk.
        • Nops don't require offset adjustments but you *still* must remove any fixups pointing into the nopped region.
  • new block "validate"
    • information that describes the results of any validation of the FDT and/or the devicetree source that the FDT was created from
    • REVIEW COMMENTS:
      • could go into the main header
      • pretty poorly defined
        • yes, it was presented as a concept that should be considered by people implementing the validation tools/process
  • add a field at the end of the FDT, "footer_magic"
    • a check to determine if a transformation of the FDT (eg by an external tool or by a bootloader) was started but not completed
    • this should not be needed - this situation should be detected by an invalid checksum
    • REVIEW COMMENTS:
      • like the idea of adding a footer, to detect truncated blobs, but poorly worded description in the proposal
      • (comment on a side effect of the "footer_magic" field) I'd be happy enough for the new version to say that totalsize must always be aligned to 32 (or even 64) bits, too
  • General REVIEW COMMENTS:
    • Any addition of blocks to the blob makes libfdt's job a lot harder for write operations. Juggling the 3 existing blocks is already pretty awkward.
    • paraphrase: given challenges to maintain compatibility, wondering how valuable backwards compatibility actually is.
    • If we drop the requirement for backwards compat, it beomces possible to encode the fixup information in a much more natural and easy to handle format. Instead of adding new blocks, we add new tags to the structure block. So, say FDT_EXTERNAL_PHANDLE with a property offset and strings table offset would replace a __fixups__ entry, and an FDT_INTERNAL_PHANDLE with just a property offset would replace a __local_fixups__ entry. They don't need an explicit property reference, because they'd just apply to the immediately preceding property.
      • That approach means we're back to local data, which can be shuffled around pretty easily for inserts and deletes. You'd have to adjust offsets in the fixups for one property when it was altered but not any further away than that.
      • It also extends easily to add path fixups as well.

(2) Linux Plumbers 2018

video note: The video links include timestamps into the one single [video].

  • [video] DT memory (kernel), DT memory (bootloader), storage (FDT) size
    • presentation slides [PDF] "Device tree format v18", Linux Plumbers Devicetree track November 2018, Simon Glass
    • Detailed design document [PDF] "Proposed new DTB format", Linux Plumbers Devicetree track November 2018, Simon Glass
    • [PDF] "Linux kernel memory size, FDT size", Linux Plumbers Devicetree track November 2018, Frank Rowand
  • [video] New FDT format & Overlays
    • [PDF] "FDT Format", Linux Plumbers Devicetree track November 2018, Frank Rowand
Linux Plumbers 2018 etherpad notes

The etherpad notes at openstack.org may fail to properly format. A version reformatted with elinux.org wiki formatting is provided.

elinux.org formatted etherpad notes

local cache of etherpad notes

openstack.org link for etherpad notes

https://etherpad.openstack.org/p/Device_Tree

Linux Plumbers Simon Glass Presentation
  • Frank TODO:
    • summarize Simon Glass proposal
    • view Simon Glass video, summarize discussion where not captured in etherpad notes

Simon presented several possible areas of change to the FDT format.

The following information is extracted from the presentation slides "Device tree format v18" linked above and the design document: "Proposed new DTB format" linked above.

Wish list

  • Type information
    • empty: diff fred.dts <(dtc fred.dts | dtc -O dts)
  • More size-efficient
  • Overlay symbols
  • Import into node <<
  • Delete nodes and properties
  • Lists (anonymous nodes)
  • Little-endian format
  • External data (reference blobs outside DT)
  • Comments / text
  • Next/previous node pointers

Proposal

  • The tag cells are wasteful
    • Most of the 32 bits of tag are unused
    • Encode more of the structure information in the 32 bit tag
      • length
      • string pointer
      • type information (pages 5-7)
      • one-byte value
    • Compatible strings -> 32-bit vendor/product encoding
      • replaces long string with 32-bit constant

Results listed in the above design document: "Proposed new DTB format" (page 4)

Idea Data size (% of baseline) Saving % Affects
A. Status quo, v17 format 100 0
B. Single-cell property metadata 72.6 27.4 fdt_get_property...()
C. Use a value table 97.8 2.2
D. In-place byte 94.9 5.1
E. Narrow u32 94.6 5.4 fdt_getprop()
F. Avoid strings in pinctrl 99.7 0.3 Bindings
G. Replace compatible strings with u32 92.8 7.2 fdt_node_offset_by_compatible(), etc.
H. Drop FDT_END_NODE 97.6 2.4
I. Skip alignment to cell boundaries 97.3 2.7 Caller assumptions / code
J. Bytewise protocol 79.3 20.7 Caller assumptions / code
J'. Bytewise values too 83.4 16.6 Also fdt_getprop()
B + D + G 60.4 39.6
B + C + D + G 59.2 40.8
B + C + D + G + I 58.0 42.0

Suggested choice of options listed in the above design document: "Proposed new DTB format" (page 4)

  • Option B is clearly important for size reduction, but it does prevent use of struct fdt_property (and struct fdt_node_header which is not actually used in the API).
  • Since the value table (C) saves only 2.2% it does not seem worth the extra code cost. Option D does not require an API change.
  • Changing compatible strings provides a good win but introduces an API change to the compatible functions. This requires substantial code changes in clients.
  • Overall B + D + G seems like a reasonable option. It has some API impact, but nothing too great. Option G can be supported in addition to compatible strings. Clients can move over to it when desired.

Observations

  • Frank TODO: provide more details in this section
  • libfdt proof of concept implemented
    • backwards compatibility possible, but adds "quite a bit ... to run-time size"
      • should v17 vs v18 support be a build-time option?

(3) Devicetree atom table

Devicetree Atom Table Format proposal, 2019/16, with confidential marking removed 2021/04.

Allow the use of an optional atom table in place of or in conjunction with the existing string table. String values may be replaced with 32 bit atoms. The strings represented by atom values may be either from a well defined dictionary of standard strings or from an ad-hoc atom space.

See the proposal pdf for a more detailed explanation.

(4) Signatures

TODO: summarize previous discussions