Avoid to re-generate string table from ufdt to fdt

String table contains the strings of all property name in a fdt.

The ufdt_apply_overlay() converts two dtbs from fdt to ufdt,
overlays, and converts merged ufdt to fdt. These operations
shouldn't create new peroperty names, so we can just re-use the
string tables in original dtbs, and just copy them into merged
fdt. This solution can enhance a lot of performance for device
tree overlaying.

To avoid the error that some users could use string offset in
string table, the solution also give a same string offset for
the name properties by ufdt_prop_dict;

Futher, the patch also removed unused header files after
changing algorithm.

Bug: 35255584
Test: ./tests/run_tests.sh
Change-Id: Id422730115531bd20d21117285291bdd860915ff

1 files changed, 208 insertions, 21 deletions

diff --git a/ufdt_convert.c b/ufdt_convert.c
index b990c20..07c489e 100644
--- a/ufdt_convert.c
+++ b/ufdt_convert.c
@@ -1,23 +1,94 @@
 #include "libufdt.h"
 
-#include "fdt_internal.h"
-#include "ufdt_util.h"
-
+#include "ufdt_prop_dict.h"
 
 struct ufdt *ufdt_construct(void *fdtp) {
-  struct ufdt *res_ufdt = dto_malloc(sizeof(struct ufdt));
-  res_ufdt->fdtp = fdtp;
+  /* Inital size is 2, will be exponentially increased when it needed later.
+     (2 -> 4 -> 8 -> ...) */
+  const int DEFAULT_MEM_SIZE_FDTPS = 2;
+
+  void **fdtps = NULL;
+  struct ufdt *res_ufdt = NULL;
+
+  fdtps = (void **)dto_malloc(sizeof(void *) * DEFAULT_MEM_SIZE_FDTPS);
+  if (fdtps == NULL) goto error;
+  fdtps[0] = fdtp;
+
+  res_ufdt = dto_malloc(sizeof(struct ufdt));
+  if (res_ufdt == NULL) goto error;
+
+  res_ufdt->fdtps = fdtps;
+  res_ufdt->mem_size_fdtps = DEFAULT_MEM_SIZE_FDTPS;
+  res_ufdt->num_used_fdtps = (fdtp != NULL ? 1 : 0);
   res_ufdt->root = NULL;
 
   return res_ufdt;
+
+error:
+  if (res_ufdt) dto_free(res_ufdt);
+  if (fdtps) dto_free(fdtps);
+
+  return NULL;
 }
 
 void ufdt_destruct(struct ufdt *tree) {
+  if (tree == NULL) return;
+
   ufdt_node_destruct(tree->root);
+
+  dto_free(tree->fdtps);
   dto_free(tree->phandle_table.data);
   dto_free(tree);
 }
 
+int ufdt_add_fdt(struct ufdt *tree, void *fdtp) {
+  if (fdtp == NULL) {
+    return -1;
+  }
+
+  int i = tree->num_used_fdtps;
+  if (i >= tree->mem_size_fdtps) {
+    int new_size = tree->mem_size_fdtps * 2;
+    void **new_fdtps = dto_malloc(sizeof(void *) * new_size);
+    if (new_fdtps == NULL) return -1;
+
+    dto_memcpy(new_fdtps, tree->fdtps, sizeof(void *) * tree->mem_size_fdtps);
+    dto_free(tree->fdtps);
+
+    tree->fdtps = new_fdtps;
+    tree->mem_size_fdtps = new_size;
+  }
+
+  tree->fdtps[i] = fdtp;
+  tree->num_used_fdtps = i + 1;
+
+  return 0;
+}
+
+int ufdt_get_string_off(const struct ufdt *tree, const char *s) {
+  /* fdt_create() sets the dt_string_off to the end of fdt buffer,
+     and _ufdt_output_strtab_to_fdt() copy all string tables in reversed order.
+     So, here the return offset value is base on the end of all string buffers,
+     and it should be a minus value. */
+  int res_off = 0;
+  for (int i = 0; i < tree->num_used_fdtps; i++) {
+    void *fdt = tree->fdtps[i];
+    const char *strtab_start = (const char *)fdt + fdt_off_dt_strings(fdt);
+    int strtab_size = fdt_size_dt_strings(fdt);
+    const char *strtab_end = strtab_start + strtab_size;
+
+    /* Check if the string is in the string table */
+    if (s >= strtab_start && s < strtab_end) {
+      res_off += (s - strtab_end);
+      return res_off;
+    }
+
+    res_off -= strtab_size;
+  }
+  /* Can not find the string, return 0 */
+  return 0;
+}
+
 static struct ufdt_node *ufdt_new_node(void *fdtp, int node_offset) {
   if (fdtp == NULL) {
     dto_error("Failed to get new_node because tree is NULL\n");
@@ -72,7 +143,9 @@ static struct ufdt_node *fdt_to_ufdt_tree(void *fdtp, int cur_fdt_tag_offset,
   return res;
 }
 
-void ufdt_print(struct ufdt *tree) { ufdt_node_print(tree->root, 0); }
+void ufdt_print(struct ufdt *tree) {
+  ufdt_node_print(tree->root, 0);
+}
 
 struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path,
                                             int len) {
@@ -241,16 +314,14 @@ struct static_phandle_table build_phandle_table(struct ufdt *tree) {
 }
 
 struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size) {
-  (void)(fdt_size); // unused parameter
-
-  struct ufdt *res_tree = ufdt_construct(fdtp);
+  (void)(fdt_size); /* unused parameter */
 
   int start_offset = fdt_path_offset(fdtp, "/");
   if (start_offset < 0) {
-    res_tree->fdtp = NULL;
-    return res_tree;
+    return ufdt_construct(NULL);
   }
 
+  struct ufdt *res_tree = ufdt_construct(fdtp);
   int end_offset;
   int start_tag = fdt_next_tag(fdtp, start_offset, &end_offset);
   res_tree->root = fdt_to_ufdt_tree(fdtp, start_offset, &end_offset, start_tag);
@@ -260,30 +331,146 @@ struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size) {
   return res_tree;
 }
 
-int ufdt_to_fdt(struct ufdt *tree, void *buf, int buf_size) {
+static int _ufdt_get_property_nameoff(const struct ufdt *tree, const char *name,
+                                      const struct ufdt_prop_dict *dict) {
+  int res;
+  const struct fdt_property *same_name_prop = ufdt_prop_dict_find(dict, name);
+  if (same_name_prop != NULL) {
+    /* There is a property with same name, just use its string offset */
+    res = fdt32_to_cpu(same_name_prop->nameoff);
+  } else {
+    /* Get the string offset from the string table of the current tree */
+    res = ufdt_get_string_off(tree, name);
+    if (res == 0) {
+      dto_error("Cannot find property name in string table: %s\n", name);
+      return 0;
+    }
+  }
+  return res;
+}
+
+static int _ufdt_output_property_to_fdt(
+    const struct ufdt *tree, void *fdtp,
+    const struct fdt_prop_ufdt_node *prop_node, struct ufdt_prop_dict *dict) {
+  int nameoff = _ufdt_get_property_nameoff(tree, prop_node->name, dict);
+  if (nameoff == 0) return -1;
+
+  int data_len = 0;
+  void *data = ufdt_node_get_fdt_prop_data(&prop_node->parent, &data_len);
+  int aligned_data_len = (data_len + (FDT_TAGSIZE - 1)) & ~(FDT_TAGSIZE - 1);
+
+  int new_propoff = fdt_size_dt_struct(fdtp);
+  int new_prop_size = sizeof(struct fdt_property) + aligned_data_len;
+  struct fdt_property *new_prop =
+      (struct fdt_property *)((char *)fdtp + fdt_off_dt_struct(fdtp) +
+                              new_propoff);
+  char *fdt_end = (char *)fdtp + fdt_totalsize(fdtp);
+  if ((char *)new_prop + new_prop_size > fdt_end) {
+    dto_error("Not enough space for adding property.\n");
+    return -1;
+  }
+  fdt_set_size_dt_struct(fdtp, new_propoff + new_prop_size);
+
+  new_prop->tag = cpu_to_fdt32(FDT_PROP);
+  new_prop->nameoff = cpu_to_fdt32(nameoff);
+  new_prop->len = cpu_to_fdt32(data_len);
+  dto_memcpy(new_prop->data, data, data_len);
+
+  ufdt_prop_dict_add(dict, new_prop);
+
+  return 0;
+}
+
+static int _ufdt_output_node_to_fdt(const struct ufdt *tree, void *fdtp,
+                                    const struct ufdt_node *node,
+                                    struct ufdt_prop_dict *dict) {
+  uint32_t tag = tag_of(node);
+
+  if (tag == FDT_PROP) {
+    return _ufdt_output_property_to_fdt(
+        tree, fdtp, (const struct fdt_prop_ufdt_node *)node, dict);
+  }
+
+  int err = fdt_begin_node(fdtp, name_of(node));
+  if (err < 0) return -1;
+
+  struct ufdt_node **it;
+  for_each_prop(it, node) {
+    err = _ufdt_output_node_to_fdt(tree, fdtp, *it, dict);
+    if (err < 0) return -1;
+  }
+
+  for_each_node(it, node) {
+    err = _ufdt_output_node_to_fdt(tree, fdtp, *it, dict);
+    if (err < 0) return -1;
+  }
+
+  err = fdt_end_node(fdtp);
+  if (err < 0) return -1;
+
+  return 0;
+}
+
+static int _ufdt_output_strtab_to_fdt(const struct ufdt *tree, void *fdt) {
+  /* Currently, we don't know the final dt_struct size, so we copy all
+     string tables to the end of the target fdt buffer in reversed order.
+     At last, fdt_finish() will adjust dt_string offset */
+  const char *struct_top =
+      (char *)fdt + fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt);
+  char *dest = (char *)fdt + fdt_totalsize(fdt);
+
+  int dest_size = 0;
+  for (int i = 0; i < tree->num_used_fdtps; i++) {
+    void *src_fdt = tree->fdtps[i];
+    const char *src_strtab = (const char *)src_fdt + fdt_off_dt_strings(src_fdt);
+    int strtab_size = fdt_size_dt_strings(src_fdt);
+
+    dest -= strtab_size;
+    if (dest < struct_top) {
+      dto_error("Not enough space for string table.\n");
+      return -1;
+    }
+
+    dto_memcpy(dest, src_strtab, strtab_size);
+
+    dest_size += strtab_size;
+  }
+
+  fdt_set_size_dt_strings(fdt, dest_size);
+
+  return 0;
+}
+
+int ufdt_to_fdt(const struct ufdt *tree, void *buf, int buf_size) {
+  if (tree->num_used_fdtps == 0) return -1;
+
   int err;
   err = fdt_create(buf, buf_size);
   if (err < 0) return -1;
 
-  int n_mem_rsv = fdt_num_mem_rsv(tree->fdtp);
+  /* Here we output the memory reserve map of the ONLY FIRST fdt,
+     to be in compliance with the DTO behavior of libfdt. */
+  int n_mem_rsv = fdt_num_mem_rsv(tree->fdtps[0]);
   for (int i = 0; i < n_mem_rsv; i++) {
     uint64_t addr, size;
-    fdt_get_mem_rsv(tree->fdtp, i, &addr, &size);
+    fdt_get_mem_rsv(tree->fdtps[0], i, &addr, &size);
     fdt_add_reservemap_entry(buf, addr, size);
   }
 
   err = fdt_finish_reservemap(buf);
   if (err < 0) return -1;
 
-  /*
-   * Obtains all props for later use because getting them from
-   * FDT requires complicated manipulation.
-  */
-  struct ufdt_node_dict all_props = ufdt_node_dict_construct();
-  err = output_ufdt_node_to_fdt(tree->root, buf, &all_props);
+  err = _ufdt_output_strtab_to_fdt(tree, buf);
+  if (err < 0) return -1;
+
+  struct ufdt_prop_dict dict;
+  err = ufdt_prop_dict_construct(&dict, buf);
+  if (err < 0) return -1;
+
+  err = _ufdt_output_node_to_fdt(tree, buf, tree->root, &dict);
   if (err < 0) return -1;
 
-  ufdt_node_dict_destruct(&all_props);
+  ufdt_prop_dict_destruct(&dict);
 
   err = fdt_finish(buf);
   if (err < 0) return -1;