Skip to contentSkip to conversation

libfdt: Document sequential write mechanism

PATCH Superseded Andre Przywara 3 participants 3 messages Oct 12, 2020 1 message not in the archive

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 libfdt: Document sequential write mechanism

When generating a flattened devicetree on the fly, we employ some clever techniques to avoid excessive copying and adjustments of offset values.

To avoid people scratching their heads over all those negative string offsets and weird magic values, let's document the nifty tricks we pull here.

---
Hi,

this is at least my understanding of how it works, by reading the code. Please correct me (and the comment), should I have got something wrong.

Cheers,
Andre

 libfdt/fdt_sw.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
libfdt/fdt_sw.c +26 -0
index 68b543c..1f08a92 100644
@@ -3,6 +3,32 @@
  * libfdt - Flat Device Tree manipulation
  * Copyright (C) 2006 David Gibson, IBM Corporation.
  */
+/**
+ * DOC: libfdt sequential write support
+ *
+ * When creating a flattened device tree on the fly, the fixed structure
+ * of a DTB would require constant adjustment of memory offsets, also copying
+ * of whole regions like the string table.
+ * To avoid this, we use an intermediate representation of a flattened tree,
+ * which needs to be finalised explicitly to create a spec-conformant DTB.
+ *
+ * This is achieved by the following means:
+ * - The magic in the header differs (FDT_SW_MAGIC), to identify such an
+ *   unfinished tree and to avoid it to be mistaken for a proper DTB, should
+ *   the fdt_finish() call have been missed.
+ * - The string table is located at the end of the allocated buffer, and
+ *   is growing *downwards*,  as new strings are *prepended*.
+ * - The string offsets in the dt_struct are expressed as negative offsets,
+ *   measured from the *end* of the string table. This allows offsets to
+ *   stay fixed, even when new strings are added (before the old ones).
+ * - The dt_struct is located at its usual place, but leaves room behind it,
+ *   to grow *upwards* towards the string table.
+ * - Upon finalising the DTB, all negative string offsets in dt_struct will
+ *   be adjusted, by adding the offset of the new end of the string table.
+ * - Eventually the final offset of all structures is written into the
+ *   header, and the magic will be changed to be the spec defined one.
+ */
+
 #include "libfdt_env.h"
 
 #include <fdt.h>
Signature · 1 line
2.17.5

A message that is not in the archive (sent off-list or not yet received): 20201012163801.24730-1-andre.przywara-5wv7dgnIgG8@public.gmane.org

#2 lore raw

Hi Andre,

Quoted 7 lines · Andre Przywara

When generating a flattened devicetree on the fly, we employ some clever techniques to avoid excessive copying and adjustments of offset values.

To avoid people scratching their heads over all those negative string offsets and weird magic values, let's document the nifty tricks we pull here.

Great stuff! Some suggestions below.

Quoted 23 lines

---
Hi,

this is at least my understanding of how it works, by reading the code. Please correct me (and the comment), should I have got something wrong.

Cheers,
Andre

 libfdt/fdt_sw.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
libfdt/fdt_sw.c +1 -0
index 68b543c..1f08a92 100644
@@ -3,6 +3,32 @@
  * libfdt - Flat Device Tree manipulation
  * Copyright (C) 2006 David Gibson, IBM Corporation.
  */
+/**

libfdt/fdt_sw.c line 16

Quoted 10 lines
libfdt/fdt_sw.c +10 -0
+ * DOC: libfdt sequential write support
+ *
+ * When creating a flattened device tree on the fly, the fixed structure
+ * of a DTB would require constant adjustment of memory offsets, also copying
+ * of whole regions like the string table.
+ * To avoid this, we use an intermediate representation of a flattened tree,
+ * which needs to be finalised explicitly to create a spec-conformant DTB.
+ *
+ * This is achieved by the following means:
+ * - The magic in the header differs (FDT_SW_MAGIC), to identify such an

The magic number in the header

libfdt/fdt_sw.c line 24

Quoted 8 lines
libfdt/fdt_sw.c +8 -0
+ *   unfinished tree and to avoid it to be mistaken for a proper DTB, should
+ *   the fdt_finish() call have been missed.
+ * - The string table is located at the end of the allocated buffer, and
+ *   is growing *downwards*,  as new strings are *prepended*.
+ * - The string offsets in the dt_struct are expressed as negative offsets,
+ *   measured from the *end* of the string table. This allows offsets to
+ *   stay fixed, even when new strings are added (before the old ones).
+ * - The dt_struct is located at its usual place, but leaves room behind it,

s/behind/after/

libfdt/fdt_sw.c line 27

Quoted 3 lines
libfdt/fdt_sw.c +3 -0
+ *   to grow *upwards* towards the string table.
+ * - Upon finalising the DTB, all negative string offsets in dt_struct will
+ *   be adjusted, by adding the offset of the new end of the string table.

s/will be/are/

libfdt/fdt_sw.c line 28

Quoted 1 line
libfdt/fdt_sw.c +1 -0
+ * - Eventually the final offset of all structures is written into the

s/Eventually/To finish the tree,/

libfdt/fdt_sw.c line 29

Quoted 1 line
libfdt/fdt_sw.c +1 -0
+ *   header, and the magic will be changed to be the spec defined one.

s/will be/is/

Quoted 8 lines
libfdt/fdt_sw.c +2 -1
+ */
+
 #include "libfdt_env.h"
 
 #include <fdt.h>
--

2.17.5

Regards,
Simon

#3 lore raw
In reply to a message not in the archive
Quoted 36 lines · Andre Przywara

When generating a flattened devicetree on the fly, we employ some clever techniques to avoid excessive copying and adjustments of offset values.

To avoid people scratching their heads over all those negative string offsets and weird magic values, let's document the nifty tricks we pull here.

---
Hi,

this is at least my understanding of how it works, by reading the code. Please correct me (and the comment), should I have got something wrong.

Cheers,
Andre

 libfdt/fdt_sw.c | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)
libfdt/fdt_sw.c +8 -0
index 68b543c..1f08a92 100644
@@ -3,6 +3,32 @@
  * libfdt - Flat Device Tree manipulation
  * Copyright (C) 2006 David Gibson, IBM Corporation.
  */
+/**
+ * DOC: libfdt sequential write support
+ *
+ * When creating a flattened device tree on the fly, the fixed structure
+ * of a DTB would require constant adjustment of memory offsets, also copying
+ * of whole regions like the string table.
+ * To avoid this, we use an intermediate representation of a flattened tree,
+ * which needs to be finalised explicitly to create a spec-conformant DTB.

libfdt/fdt_sw.c line 23

Quoted 10 lines
libfdt/fdt_sw.c +10 -0
+ *
+ * This is achieved by the following means:
+ * - The magic in the header differs (FDT_SW_MAGIC), to identify such an
+ *   unfinished tree and to avoid it to be mistaken for a proper DTB, should
+ *   the fdt_finish() call have been missed.
+ * - The string table is located at the end of the allocated buffer, and
+ *   is growing *downwards*,  as new strings are *prepended*.
+ * - The string offsets in the dt_struct are expressed as negative offsets,
+ *   measured from the *end* of the string table. This allows offsets to
+ *   stay fixed, even when new strings are added (before the old ones).

This is possibly misleading, since it depends how you define "start" and "end". During SW mode, the string table offset also points to the end of the string table, rather than the start, so string offsets, while negative, are still relative to the header string table offset. So, in normal mode the string table occupies (absolute) offsets [fdt_off_dt_strings .. (fdt_off_dt_strings+fdt_size_dt_strings)], but in sw mode it occupies offsets [(fdt_off_dt_strings-fdt_size_dt_strings) .. fdt_off_dt_strings].

libfdt/fdt_sw.c line 30

Quoted 7 lines
libfdt/fdt_sw.c +7 -0
+ * - The dt_struct is located at its usual place, but leaves room behind it,
+ *   to grow *upwards* towards the string table.
+ * - Upon finalising the DTB, all negative string offsets in dt_struct will
+ *   be adjusted, by adding the offset of the new end of the string table.
+ * - Eventually the final offset of all structures is written into the
+ *   header, and the magic will be changed to be the spec defined one.
+ */

It's probably worth mentioning that in SW mode, only the "ro" and "sw" functions can be used. "rw" functions will fail with FDT_ERR_BADSTATE. In fact some "sw" functions may also fail with BADSTATE depending on where you're up to (e.g. trying to create a node before finishing the memreserve block).

Quoted 4 lines
libfdt/fdt_sw.c +1 -0
+
 #include "libfdt_env.h"
 
 #include <fdt.h>
Signature · 4 lines
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