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

3 files changed, 552 insertions, 0 deletions

diff --git a/include/libufdt.h b/include/libufdt.h
new file mode 100644
index 0000000..4fc6965
--- /dev/null
+++ b/include/libufdt.h
@@ -0,0 +1,430 @@
+
+#ifndef LIBUFDT_H
+#define LIBUFDT_H
+
+#include "libufdt_sysdeps.h"
+#include "ufdt_types.h"
+
+/*
+ * BEGIN of ufdt_node_dict methods
+ * Since in the current implementation, it's actually a hash table.
+ * So most of operation's time complexity are O(1) with high probability
+ * (w.h.p.).
+ */
+
+/*
+ * Allocates some new spaces and creates a new ufdt_node_dict.
+ *
+ * @return: a pointer to the newly created ufdt_node_dict or
+ *          NULL if dto_malloc failed
+ */
+struct ufdt_node_dict ufdt_node_dict_construct();
+
+/*
+ * Frees all space dto_malloced, not including ufdt_nodes in the table.
+ */
+void ufdt_node_dict_destruct(struct ufdt_node_dict *dict);
+
+/*
+ * Adds a ufdt_node (as pointer) to the ufdt_node_dict.
+ * @return: 0 if success
+ *          < 0 otherwise
+ *
+ * @Time: O(length of node->name) w.h.p.
+ */
+int ufdt_node_dict_add(struct ufdt_node_dict *dict, struct ufdt_node *node);
+
+/*
+ * Returns the pointer to the entry in ufdt_node_dict with node->name =
+ * name[0..len-1], for direct modification of the entry.
+ * e.g., Delete an entry from the ufdt_node_dict.
+ *
+ * @return: a pointer to the entry in ufdt_node_dict or
+ *          NULL if no such entry.
+ *
+ * @Time: O(len = |name|) w.h.p.
+ */
+struct ufdt_node **ufdt_node_dict_find_len(struct ufdt_node_dict *dict,
+                                           const char *name, int len);
+struct ufdt_node **ufdt_node_dict_find(struct ufdt_node_dict *dict,
+                                       const char *name);
+
+/*
+ * Returns the pointer to the ufdt_node with node->name =
+ * name[0..len-1], for direct modification of the node.
+ *
+ * @return: a pointer to the node or
+ *          NULL if no such node in ufdt_node_dict with same name.
+ *
+ * @Time: O(len = |name|) w.h.p.
+ */
+struct ufdt_node *ufdt_node_dict_find_node_len(struct ufdt_node_dict *dict,
+                                               const char *name, int len);
+struct ufdt_node *ufdt_node_dict_find_node(struct ufdt_node_dict *dict,
+                                           const char *name);
+
+/*
+ * Prints the each (index, node->name) pair in the dict to stdout in the
+ * following format:
+ * ```
+ * [idx0] [name0]
+ * [idx1] [name1]
+ * ...
+ * ```
+ */
+void ufdt_node_dict_print(struct ufdt_node_dict *dict);
+
+/*
+ * END of ufdt_node_dict methods
+ */
+
+/*
+ * BEGIN of ufdt_node methods
+ */
+
+/*
+ * Allocates spaces for new ufdt_node who represents a fdt node at fdt_tag_ptr.
+ * In order to get name pointer, it's neccassary to give the pointer to the
+ * entire fdt it belongs to.
+ *
+ *
+ * @return: a pointer to the newly created ufdt_node or
+ *          NULL if dto_malloc failed
+ */
+struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr);
+
+/*
+ * Frees all nodes in the subtree rooted at *node.
+ * Also dto_frees those ufdt_node_dicts in each node.
+ */
+void ufdt_node_destruct(struct ufdt_node *node);
+
+/*
+ * Adds the child as a subnode of the parent.
+ * It's been done by add entries in parent->prop_list or node_list depending on
+ * the tag type of child.
+ *
+ * @return: 0 if success
+ *          < 0 otherwise
+ *
+ * @Time: O(1) w.h.p.
+ */
+int ufdt_node_add_child(struct ufdt_node *parent, struct ufdt_node *child);
+
+/* BEGIN of FDT_PROP related functions .*/
+
+/*
+ * Gets pointer to FDT_PROP subnode of node with name equals to name[0..len-1]
+ *
+ * @return: a pointer to the subnode or
+ *          NULL if no such subnode.
+ *
+ * @Time: O(len = length of name) w.h.p.
+ */
+struct ufdt_node *ufdt_node_get_property_by_name_len(
+    const struct ufdt_node *node, const char *name, int len);
+struct ufdt_node *ufdt_node_get_property_by_name(const struct ufdt_node *node,
+                                                 const char *name);
+
+/*
+ * Gets the pointer to the FDT_PROP node's data in the corresponding fdt.
+ * Also writes the length of such data to *out_len if out_len is not NULL.
+ *
+ * @return: a pointer to some data located in fdt or
+ *          NULL if *node is not a FDT_PROP
+ */
+char *ufdt_node_get_fdt_prop_data(const struct ufdt_node *node, int *out_len);
+
+/*
+ * Gets pointer to FDT_PROP node's data in fdt with name equals to
+ * name[0..len-1], which is a subnode of *node.
+ * It's actually a composition of ufdt_node_get_property_by_name and
+ * ufdt_node_get_fdt_prop_data
+ *
+ * @return: a pointer to some data located in fdt or
+ *          NULL if no such subnode.
+ *
+ * @Time: O(len = length of name) w.h.p.
+ */
+char *ufdt_node_get_fdt_prop_data_by_name_len(const struct ufdt_node *node,
+                                              const char *name, int len,
+                                              int *out_len);
+char *ufdt_node_get_fdt_prop_data_by_name(const struct ufdt_node *node,
+                                          const char *name, int *out_len);
+
+/* END of FDT_PROP related functions .*/
+
+/*
+ * Gets pointer to FDT_BEGIN_NODE subnode of node with name equals to
+ * name[0..len-1].
+ *
+ * @return: a pointer to the subnode or
+ *          NULL if no such subnode.
+ *
+ * @Time: O(len = length of name) w.h.p.
+ */
+
+struct ufdt_node *ufdt_node_get_subnode_by_name_len(const struct ufdt_node *node,
+                                                    const char *name, int len);
+struct ufdt_node *ufdt_node_get_subnode_by_name(const struct ufdt_node *node,
+                                                const char *name);
+
+/*
+ * Gets the pointer to FDT_NODE node whose relative path to *node is
+ * path[0..len-1].
+ * Note that the relative path doesn't support parent node like:
+ * "../path/to/node".
+ *
+ * @return: a pointer to the node or
+ *          NULL if no such node.
+ *
+ * @Time: O(len = length of path) w.h.p.
+ */
+struct ufdt_node *ufdt_node_get_node_by_path_len(const struct ufdt_node *node,
+                                                 const char *path, int len);
+struct ufdt_node *ufdt_node_get_node_by_path(const struct ufdt_node *node,
+                                             const char *path);
+
+/*
+ * Gets the phandle value of the node if it has.
+ *
+ * @return: phandle value of that node or
+ *          0 if *node is not FDT_NODE or there's no "phandle"/"linux,phandle"
+ *          property.
+ *
+ * @Time: O(1) w.h.p.
+ */
+uint32_t ufdt_node_get_phandle(const struct ufdt_node *node);
+
+/*
+ * END of ufdt_node methods
+ */
+
+/*
+ * BEGIN of ufdt methods.
+ */
+
+/*
+ * Constructs a ufdt whose base fdt is fdtp.
+ * Note that this function doesn't construct the entire tree.
+ * To get the whole tree please call `fdt_to_ufdt(fdtp, fdt_size)`
+ *
+ * @return: an empty ufdt with base fdtp = fdtp
+ */
+struct ufdt *ufdt_construct(void *fdtp);
+
+/*
+ * Frees the space occupied by the ufdt, including all ufdt_nodes and
+ * ufdt_node_dicts along
+ * with static_phandle_table.
+ */
+void ufdt_destruct(struct ufdt *tree);
+
+/*
+ * Gets the pointer to the ufdt_node in tree with phandle = phandle.
+ * The function do a binary search in tree->phandle_table.
+ *
+ * @return: a pointer to the target ufdt_node
+ *          NULL if no ufdt_node has phandle = phandle
+ *
+ * @Time: O(log(# of nodes in tree)) = O(log(size of underlying fdt))
+ */
+struct ufdt_node *ufdt_get_node_by_phandle(struct ufdt *tree, uint32_t phandle);
+
+/*
+ * Gets the pointer to the ufdt_node in tree with absoulte path =
+ * path[0..len-1].
+ * Absolute path has form "/path/to/node" or "some_alias/to/node".
+ * In later example, some_alias is a property in "/aliases" with data is a path
+ * to some node X. Then the funcion will return node with relative
+ * path = "to/node" w.r.t. X.
+ *
+ * @return: a pointer to the target ufdt_node or
+ *          NULL if such dnt doesn't exist.
+ *
+ * @Time: O(len = length of path) w.h.p.
+ */
+struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path,
+                                            int len);
+struct ufdt_node *ufdt_get_node_by_path(struct ufdt *tree, const char *path);
+
+/*
+ * END of ufdt methods.
+ */
+
+/*
+ * Compares function between 2 nodes, compare by name of each node.
+ *
+ * @return: x < 0  if a's name is lexicographically smaller
+ *          x == 0 if a, b has same name
+ *          x > 0  if a's name is lexicographically bigger
+ */
+int node_cmp(const void *a, const void *b);
+
+/*
+ * Determines whether node->name equals to name[0..len-1]
+ *
+ * @return: true if they're equal.
+ *          false otherwise
+ */
+bool node_name_eq(const struct ufdt_node *node, const char *name, int len);
+
+/*
+ * Merges tree_b into tree_a with tree_b has all nodes except root disappeared.
+ * Overwrite property in tree_a if there's one with same name in tree_b.
+ * Otherwise add the property to tree_a.
+ * For subnodes with the same name, recursively run this function.
+ *
+ * Ex:
+ * tree_a : ta {
+ *  b = "b";
+ *  c = "c";
+ *  d {
+ *    e = "g";
+ *  };
+ * };
+ *
+ * tree_b : tb {
+ *  c = "C";
+ *  g = "G";
+ *  d {
+ *    da = "dad";
+ *  };
+ *  h {
+ *    hh = "HH";
+ *  };
+ * };
+ *
+ * The resulting trees will be:
+ *
+ * tree_a : ta {
+ *  b = "b";
+ *  c = "C";
+ *  g = "G";
+ *  d {
+ *    da = "dad";
+ *    e = "g";
+ *  };
+ *  h {
+ *    hh = "HH";
+ *  };
+ * };
+ *
+ * tree_b : tb {
+ * };
+ *
+ *
+ * @return: 0 if merge success
+ *          < 0 otherwise
+ *
+ * @Time: O(# of nodes in tree_b + total length of all names in tree_b) w.h.p.
+ */
+int merge_ufdt_into(struct ufdt_node *tree_a, struct ufdt_node *tree_b);
+
+/*
+ * BEGIN of ufdt output functions
+ */
+
+/*
+ * Builds the ufdt for FDT pointed by fdtp.
+ * This including build all ufdt_nodes and ufdt_node_dicts, and builds the
+ * phandle table as
+ * well.
+ *
+ * @return: the ufdt T representing fdtp or
+ *          T with T.fdtp == NULL if fdtp is unvalid.
+ *
+ * @Time: O(fdt_size + nlogn) where n = # of nodes in fdt.
+ */
+struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size);
+
+/*
+ * Sequentially dumps the tree rooted at *node to FDT buffer fdtp.
+ * Basically it calls functions provided by libfdt/fdt_sw.c.
+ *
+ * All those functions works fast.
+ * But when it comes to dump property node to fdt, the function they
+ * provide(fdt_property()) is really slow. Since it runs through all strings
+ * stored in fdt to find the right `nameoff` for the property node.
+ *
+ * So we implement our own fdt_property() called `output_property_to_fdt()`, the
+ * basic
+ * idea is that we keep a hash table that we can search for the nameoff of the
+ * string in constant time instead of O(total length of strings) search.
+ *
+ * @return: 0 if successfully dump or
+ *          < 0 otherwise
+ *
+ * @Time: O(total length of all names + # of nodes in subtree rooted at *root)
+ */
+int output_ufdt_node_to_fdt(struct ufdt_node *node, void *fdtp,
+                            struct ufdt_node_dict *all_props);
+
+/*
+ * Sequentially dumps the whole ufdt to FDT buffer fdtp with buffer size
+ * buf_size.
+ * Basically it calls functions provided by libfdt/fdt_sw.c.
+ * The main overhead here is to dump the tree to fdtp by calling
+ * output_ufdt_node_to_fdt().
+ *
+ *
+ * @return: 0 if successfully dump or
+ *          < 0 otherwise
+ *
+ * @Time: O(total length of all names + # of nodes in tree)
+ */
+int ufdt_to_fdt(struct ufdt *tree, void *buf, int buf_size);
+
+/*
+ * prints the entire subtree rooted at *node in form:
+ * NODE :[node name]:
+ *   PROP :[prop name]:
+ *   ...
+ *   NODE :[subnode1 name]:
+ *     ...
+ *   NODE :[subnode1 name]:
+ *     ...
+ *   ...
+ * There're (depth * TAB_SIZE) spaces in front of each line.
+ */
+void ufdt_node_print(const struct ufdt_node *node, int depth);
+
+/*
+ * It's just ufdt_node_print(tree->root, 0).
+ */
+void ufdt_print(struct ufdt *tree);
+
+/*
+ * END of ufdt output functions
+ */
+
+/*
+ * Runs closure.func(node, closure.env) for all nodes in subtree rooted at
+ * *node.
+ * The order of each node being applied by the function is depth first.
+ * Basically it's the same order as the order printed in ufdt_node_print().
+ *
+ * Example:
+ *
+ * void print_name(struct ufdt_node *node, void *env) {
+ *   printf("%s\n", node->name);
+ * }
+ *
+ * struct ufdt_node_closure clos;
+ * clos.func = print_name;
+ * clos.env = NULL;
+ * ufdt_map(tree, clos);
+ *
+ * Then you can print all names of nodes in tree.
+ *
+ * @Time: O((# of nodes in subtree rooted at *node) * avg. running time of the
+ * function closure.func)
+ */
+void ufdt_node_map(struct ufdt_node *node, struct ufdt_node_closure closure);
+
+/*
+ * It's just ufdt_node_map(tree->root, closure);
+ */
+void ufdt_map(struct ufdt *tree, struct ufdt_node_closure closure);
+
+#endif /* LIBUFDT_H */
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 */
diff --git a/include/ufdt_types.h b/include/ufdt_types.h
new file mode 100644
index 0000000..2f9f849
--- /dev/null
+++ b/include/ufdt_types.h
@@ -0,0 +1,96 @@
+#ifndef UFDT_TYPES_H
+#define UFDT_TYPES_H
+
+#include <libfdt.h>
+
+#define ASCII_PRINT_S (32)
+#define ASCII_PRINT_E (128)
+#define ASCII_PRINT_SZ (ASCII_PRINT_E - ASCII_PRINT_S)
+
+#define FDT_PROP_DELI ':'
+#define FDT_NODE_DELI '/'
+
+#define DTNL_INIT_SZ 4
+
+/* Empirical values for hash functions. */
+#define HASH_BASE 13131
+
+/* it has type : struct ufdt_node** */
+#define for_each(it, node_dict)                                  \
+  if ((node_dict) != NULL)                                       \
+    for (it = (node_dict)->nodes;                                \
+         it != (node_dict)->nodes + (node_dict)->mem_size; ++it) \
+      if (*it)
+
+#define for_each_child(it, node)                                    \
+  if (tag_of(node) == FDT_BEGIN_NODE)                               \
+    for ((it) = &(((struct fdt_node_ufdt_node *)node)->child); *it; \
+         it = &((*it)->sibling))
+
+#define for_each_prop(it, node) \
+  for_each_child(it, node) if (tag_of(*it) == FDT_PROP)
+
+#define for_each_node(it, node) \
+  for_each_child(it, node) if (tag_of(*it) == FDT_BEGIN_NODE)
+
+/*
+ * Gets prop name from FDT requires complicated manipulation.
+ * To avoid the manipulation, the *name pointer in fdt_prop_ufdt_node
+ * is pointed to the final destination of the prop name in FDT.
+ * For the FDT_BEGIN_NODE name, it can be obtained from FDT directly.
+ */
+#define name_of(node)                                                    \
+  ((tag_of(node) == FDT_BEGIN_NODE)                                      \
+       ? (((const struct fdt_node_header *)((node)->fdt_tag_ptr))->name) \
+       : (((const struct fdt_prop_ufdt_node *)node)->name))
+
+struct ufdt_node {
+  fdt32_t *fdt_tag_ptr;
+  struct ufdt_node *sibling;
+};
+
+struct ufdt_node_dict {
+  int mem_size;
+  int num_used;
+  struct ufdt_node **nodes;
+};
+
+struct fdt_prop_ufdt_node {
+  struct ufdt_node parent;
+  const char *name;
+};
+
+struct fdt_node_ufdt_node {
+  struct ufdt_node parent;
+  struct ufdt_node *child;
+};
+
+struct phandle_table_entry {
+  uint32_t phandle;
+  struct ufdt_node *node;
+};
+
+struct static_phandle_table {
+  int len;
+  struct phandle_table_entry *data;
+};
+
+struct ufdt {
+  void *fdtp;
+  struct ufdt_node *root;
+  struct static_phandle_table phandle_table;
+};
+
+typedef void func_on_ufdt_node(struct ufdt_node *, void *);
+
+struct ufdt_node_closure {
+  func_on_ufdt_node *func;
+  void *env;
+};
+
+static uint32_t tag_of(const struct ufdt_node *node) {
+  if (!node) return FDT_END;
+  return fdt32_to_cpu(*node->fdt_tag_ptr);
+}
+
+#endif /* UFDT_TYPES_H */