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, 178 insertions, 0 deletions

diff --git a/ufdt_node_dict.c b/ufdt_node_dict.c
new file mode 100644
index 0000000..448bc49
--- /dev/null
+++ b/ufdt_node_dict.c
@@ -0,0 +1,178 @@
+
+#include "libufdt.h"
+#include "ufdt_util.h"
+
+/*
+ * BEGIN of Hash table internal implementations.
+ */
+
+#define DICT_LIMIT_NUM 2
+#define DICT_LIMIT_DEN 3
+
+static bool _ufdt_node_dict_is_too_full(struct ufdt_node_dict *dict) {
+  /*
+   * We say a dict is too full if it's DICT_LIMIT_NUM / DICT_LIMIT_DEN full.
+   */
+  if (dict->num_used * DICT_LIMIT_DEN > dict->mem_size * DICT_LIMIT_NUM)
+    return true;
+  return false;
+}
+
+/*
+ * If collision happened, use linear probing to find idx in the hash table.
+ */
+static int _ufdt_node_dict_find_index_by_name_len(struct ufdt_node **hash_table,
+                                                  int size, const char *name,
+                                                  int len) {
+  if (!name || !size) return -1;
+  /*
+   * All size should be 2^k for some k
+   */
+  int hsh = get_hash_len(name, len);
+  int idx = hsh & (size - 1);
+  for (int cnt = 0; cnt < size; ++cnt) {
+    if (hash_table[idx] == NULL) return idx;
+    if (node_name_eq(hash_table[idx], name, len) == 1) return idx;
+    ++idx;
+    idx &= (size - 1);
+  }
+  return -1;
+}
+
+static int _ufdt_node_dict_find_index_by_name(struct ufdt_node **hash_table,
+                                              int size, const char *name) {
+  return _ufdt_node_dict_find_index_by_name_len(hash_table, size, name,
+                                                dto_strlen(name));
+}
+
+static int _ufdt_node_dict_find_index_in_ht(struct ufdt_node **hash_table,
+                                            int size, struct ufdt_node *x) {
+  if (x == NULL) return -1;
+  return _ufdt_node_dict_find_index_by_name(hash_table, size, name_of(x));
+}
+
+/*
+ * END of Hash table internal implementations.
+ */
+
+/*
+ * ufdt_node_dict methods.
+ */
+
+struct ufdt_node_dict ufdt_node_dict_construct() {
+  struct ufdt_node_dict res;
+  res.mem_size = DTNL_INIT_SZ;
+  res.num_used = 0;
+  res.nodes = dto_malloc(DTNL_INIT_SZ * sizeof(struct ufdt_node *));
+  if (res.nodes == NULL) {
+    res.mem_size = 0;
+    return res;
+  }
+  dto_memset(res.nodes, 0, DTNL_INIT_SZ * sizeof(struct ufdt_node *));
+  return res;
+}
+
+void ufdt_node_dict_destruct(struct ufdt_node_dict *dict) {
+  if (dict == NULL) return;
+  dto_free(dict->nodes);
+  dict->mem_size = dict->num_used = 0;
+}
+
+static int ufdt_node_dict_resize(struct ufdt_node_dict *dict) {
+  if (dict == NULL) return -1;
+
+  int new_size = dict->mem_size << 1;
+
+  struct ufdt_node **new_nodes =
+      dto_malloc(new_size * sizeof(struct ufdt_node *));
+
+  dto_memset(new_nodes, 0, new_size * sizeof(struct ufdt_node *));
+
+  for (int i = 0; i < dict->mem_size; i++) {
+    struct ufdt_node *node = dict->nodes[i];
+    if (node == NULL) continue;
+    int idx = _ufdt_node_dict_find_index_in_ht(new_nodes, new_size, node);
+    if (idx < 0) {
+      dto_error(
+          "failed to find new index in ufdt_node_dict resize for entry :%s:\n",
+          name_of(node));
+      dto_free(new_nodes);
+      return -1;
+    }
+    new_nodes[idx] = node;
+  }
+
+  dto_free(dict->nodes);
+
+  dict->mem_size = new_size;
+  dict->nodes = new_nodes;
+  return 0;
+}
+
+int ufdt_node_dict_add(struct ufdt_node_dict *dict, struct ufdt_node *node) {
+  if (node == NULL) return -1;
+  if (dict == NULL) return -1;
+
+  int idx = _ufdt_node_dict_find_index_in_ht(dict->nodes, dict->mem_size, node);
+  if (idx < 0) {
+    dto_error("failed to find new index in ufdt_node_dict add for entry :%s:\n",
+              name_of(node));
+    return -1;
+  }
+
+  if (dict->nodes[idx] == NULL) ++dict->num_used;
+  dict->nodes[idx] = node;
+
+  /*
+   * When the hash table is too full, double the size and rehashing.
+   */
+  int err = 0;
+  if (_ufdt_node_dict_is_too_full(dict)) {
+    err = ufdt_node_dict_resize(dict);
+  }
+
+  return err;
+}
+
+/*
+ * BEGIN of ufdt_dict searching related methods.
+ */
+
+/*
+ * return a pointer to the hash table entry
+ */
+struct ufdt_node **ufdt_node_dict_find_len(struct ufdt_node_dict *dict,
+                                           const char *name, int len) {
+  if (dict == NULL) return NULL;
+  int idx = _ufdt_node_dict_find_index_by_name_len(dict->nodes, dict->mem_size,
+                                                   name, len);
+  if (idx < 0) return NULL;
+  if (dict->nodes[idx] == NULL) return NULL;
+  return dict->nodes + idx;
+}
+
+struct ufdt_node **ufdt_node_dict_find(struct ufdt_node_dict *dict,
+                                       const char *name) {
+  return ufdt_node_dict_find_len(dict, name, dto_strlen(name));
+}
+
+struct ufdt_node *ufdt_node_dict_find_node_len(struct ufdt_node_dict *dict,
+                                               const char *name, int len) {
+  struct ufdt_node **res = ufdt_node_dict_find_len(dict, name, len);
+  if (res == NULL) return NULL;
+  return *res;
+}
+
+struct ufdt_node *ufdt_node_dict_find_node(struct ufdt_node_dict *dict,
+                                           const char *name) {
+  return ufdt_node_dict_find_node_len(dict, name, dto_strlen(name));
+}
+
+/*
+ * END of ufdt_dict searching related methods.
+ */
+
+void ufdt_node_dict_print(struct ufdt_node_dict *dict) {
+  struct ufdt_node **it;
+  for_each(it, dict) dto_print("%ld -> %s\n", it - dict->nodes, name_of(*it));
+}