libufdt: device tree overlay via unflattening FDT

The original version of libdtoverlay is slow in searching for
particular nodes and adding subnodes/properties due to the operations
on flattened device tree (FDT).

`libufdt` builds a real tree structure (named ufdt -- unflattned
device tree) from FDT. In the real tree, we can perform certain
operations (e.g., merge 2 subtrees, search for a node by path) in
almost optimal time complexity with acceptable additional memory usage.

With libufdt, we improve the merging of two dtb files from O(N^2) to
O(N), where N is the number of nodes in the tree.

Bug: 30800619
Test: run test scripts (see libufdt/tests/README)
Test: manually ported libufdt into a bootloader,
      checked it can merge a base dtb and a dtbo to generate a final dtb
      to boot the device
Change-Id: I6a282cc99129d5280ecbf40852723f83735fa523

1 files changed, 26 insertions, 0 deletions

diff --git a/include/ufdt_overlay.h b/include/ufdt_overlay.h
new file mode 100644
index 0000000..ed4bf87
--- /dev/null
+++ b/include/ufdt_overlay.h
@@ -0,0 +1,26 @@
+#ifndef UFDT_OVERLAY_H
+#define UFDT_OVERLAY_H
+
+#include <libfdt.h>
+
+/* Given a buffer in RAM containing the contents of a .dtb file,
+ * it initializes an FDT in-place and returns a pointer to the
+ * given buffer, or NULL in case of error.
+ * In case of error, it may printf() diagnostic messages.
+ */
+struct fdt_header *ufdt_install_blob(void *blob, size_t blob_size);
+
+/* Given a main_fdt_header buffer and an overlay_fdtp buffer containing the
+ * contents of a .dtbo file, it creates a new FDT containing the applied
+ * overlay_fdtp in a dto_malloc'd buffer and returns it, or NULL in case of
+ * error.
+ * It is allowed to modify the buffers (both main_fdt_header and overlay_fdtp
+ * buffer) passed in.
+ * It does not dto_free main_fdt_header and overlay_fdtp buffer passed in.
+ */
+struct fdt_header *ufdt_apply_overlay(struct fdt_header *main_fdt_header,
+                                      size_t main_fdt_size,
+                                      void *overlay_fdtp,
+                                      size_t overlay_size);
+
+#endif /* UFDT_OVERLAY_H */