Add capability to verify application of multiple overlays

Bug: 67779848
Test: sh apply_verify_multiple_overlay.sh

Change-Id: I022a9b222161c279cfb7ba8546d465b478786d9c

5 files changed, 162 insertions, 47 deletions

diff --git a/include/ufdt_overlay_internal.h b/include/ufdt_overlay_internal.h
index e370714..cbbb3f5 100644
--- a/include/ufdt_overlay_internal.h
+++ b/include/ufdt_overlay_internal.h
@@ -33,7 +33,12 @@ enum overlay_result {
   OVERLAY_RESULT_MERGE_FAIL,
   OVERLAY_RESULT_VERIFY_FAIL,
 };
+
 enum overlay_result ufdt_overlay_get_target(struct ufdt *tree,
                                             struct ufdt_node *frag_node,
                                             struct ufdt_node **target_node);
+void ufdt_try_increase_phandle(struct ufdt *tree, uint32_t offset);
+uint32_t ufdt_get_max_phandle(struct ufdt *tree);
+struct ufdt_static_phandle_table build_phandle_table(struct ufdt *tree);
+int ufdt_overlay_do_local_fixups(struct ufdt *tree, uint32_t phandle_offset);
 #endif /* UFDT_OVERLAY_INTERNAL_H */
diff --git a/tests/libufdt_verify/include/ufdt_test_overlay.h b/tests/libufdt_verify/include/ufdt_test_overlay.h
index 719d209..6cc65a0 100644
--- a/tests/libufdt_verify/include/ufdt_test_overlay.h
+++ b/tests/libufdt_verify/include/ufdt_test_overlay.h
@@ -23,15 +23,15 @@ extern "C" {
 
 /*
  * Verifies that the FDT described by 'main_fdt_header' has been correctly
- * overlaid by the overlays described in 'overlay_fdtp'.
+ * overlaid by the overlays contained in 'overlay_array'
  *
  * @param main_fdt_header Buffer describing the final FDT.
  * @param main_fdt_size Size of main_fdt_header.
- * @param overlay_fdtp Buffer describing the overlay FDT.
- * @param overlay_size Size of overlay_fdtp.
+ * @param overlay_array Array of buffers containg overlay FDTs.
+ * @param overlay_count Number of overlays.
  *
  * @return Will return 0 if the verification is successful.
  */
 int ufdt_verify_dtbo(struct fdt_header *main_fdt_header, size_t main_fdt_size,
-                     void *overlay_fdtp, size_t overlay_size);
+                     void **overlay_array, size_t overlay_count);
 #endif /* UFDT_TEST_OVERLAY_H */
diff --git a/tests/libufdt_verify/ufdt_test_overlay.cpp b/tests/libufdt_verify/ufdt_test_overlay.cpp
index 9b076c0..b91a509 100644
--- a/tests/libufdt_verify/ufdt_test_overlay.cpp
+++ b/tests/libufdt_verify/ufdt_test_overlay.cpp
@@ -15,6 +15,7 @@
  */
 
 #include <string>
+#include <unordered_map>
 
 extern "C" {
 
@@ -297,56 +298,155 @@ static int ufdt_overlay_verify_fragments(struct ufdt *final_tree,
     return 0;
 }
 
-static int ufdt_overlay_verify(struct ufdt *final_tree, struct ufdt *overlay_tree,
-                               struct ufdt_node_pool *pool) {
-    if (ufdt_overlay_do_fixups_and_combine(final_tree, overlay_tree, pool) < 0) {
-        dto_error("failed to perform fixups in overlay\n");
+/*
+ * Examine target nodes for fragments in all overlays and combine ones with the
+ * same target.
+ */
+static void ufdt_overlay_combine_common_nodes(struct ufdt** overlay_trees, size_t overlay_count,
+                                              struct ufdt_node_pool* pool) {
+    std::unordered_map<uint32_t, ufdt_node*> phandlemap;
+    uint32_t target = 0;
+    for (size_t i = 0; i < overlay_count; i++) {
+        struct ufdt_node **it = nullptr;
+        for_each_node(it, (overlay_trees[i]->root)) {
+            const void* val = ufdt_node_get_fdt_prop_data_by_name(*it, "target", NULL);
+            if (val) {
+                dto_memcpy(&target, val, sizeof(target));
+                target = fdt32_to_cpu(target);
+                if (phandlemap.find(target) != phandlemap.end()) {
+                    ufdt_node_merge_into(phandlemap[target], *it, pool);
+                } else {
+                    phandlemap[target] = *it;
+                }
+            }
+        }
+    }
+}
+
+/*
+ * Makes sure that all phandles in the overlays are unique since they will be
+ * combined before verification.
+ */
+int ufdt_resolve_duplicate_phandles(ufdt** overlay_tree, size_t overlay_count) {
+  size_t phandle_offset = 0;
+  for (size_t i = 0; i < overlay_count; i++) {
+        ufdt_try_increase_phandle(overlay_tree[i], phandle_offset);
+        if (ufdt_overlay_do_local_fixups(overlay_tree[i], phandle_offset) < 0) {
+            return -1;
+        }
+        phandle_offset = ufdt_get_max_phandle(overlay_tree[i]);
+  }
+
+  return 0;
+}
+
+/*
+ * Combines all overlays into a single tree at overlay_trees[0]
+ */
+int ufdt_combine_all_overlays(struct ufdt** overlay_trees, size_t overlay_count,
+                              struct ufdt* final_tree, struct ufdt_node_pool* pool) {
+    struct ufdt* combined_overlay_tree = nullptr;
+
+    if (!overlay_trees || !overlay_count || !final_tree || !pool) {
         return -1;
     }
 
-    if (ufdt_overlay_verify_fragments(final_tree, overlay_tree) < 0) {
-        dto_error("failed to apply fragments\n");
+    /*
+     * If there are duplicate phandles amongst the overlays, replace them with
+     * unique ones.
+     */
+    if (ufdt_resolve_duplicate_phandles(overlay_trees, overlay_count) < 0) {
         return -1;
     }
 
+    /*
+     * For each overlay, perform fixup for each fragment and combine the
+     * fragments that have the same target node.
+     */
+    for (size_t i = 0; i < overlay_count; i++) {
+        if (ufdt_overlay_do_fixups_and_combine(final_tree, overlay_trees[i], pool) < 0) {
+            dto_error("failed to perform fixups in overlay\n");
+            return -1;
+        }
+    }
+
+    /*
+     * Iterate through each overlay and combine all nodes with the same target
+     * node.
+     */
+    ufdt_overlay_combine_common_nodes(overlay_trees, overlay_count, pool);
+
+    /*
+     * Combine all overlays into the tree at overlay_trees[0] for easy
+     * verification.
+     */
+    combined_overlay_tree = overlay_trees[0];
+    struct ufdt_node* combined_root_node = combined_overlay_tree->root;
+
+    for (size_t i = 1; i < overlay_count; i++) {
+        struct ufdt_node** it = nullptr;
+        struct ufdt_node* root_node = overlay_trees[i]->root;
+        for_each_node(it, root_node) {
+            ufdt_node_add_child(combined_root_node, *it);
+        }
+        ((struct ufdt_node_fdt_node *)root_node)->child = nullptr;
+    }
+
+    /*
+     * Rebuild the phandle_table for the combined tree.
+     */
+    combined_overlay_tree->phandle_table = build_phandle_table(combined_overlay_tree);
+
     return 0;
 }
 
 int ufdt_verify_dtbo(struct fdt_header* final_fdt_header,
-                     size_t final_fdt_size, void* overlay_fdtp, size_t overlay_size) {
+                     size_t final_fdt_size, void** overlay_arr,
+                     size_t overlay_count) {
     const size_t min_fdt_size = 8;
     struct ufdt_node_pool pool;
     struct ufdt* final_tree = nullptr;
-    struct ufdt* overlay_tree = nullptr;
+    struct ufdt** overlay_trees = nullptr;
     int result = 1;
 
     if (final_fdt_header == NULL) {
         goto fail;
     }
 
-    if (overlay_size < sizeof(struct fdt_header)) {
-        dto_error("Overlay_length %zu smaller than header size %zu\n",
-                  overlay_size, sizeof(struct fdt_header));
+    if (final_fdt_size < min_fdt_size || final_fdt_size != fdt_totalsize(final_fdt_header)) {
+        dto_error("Bad fdt size!\n");
         goto fail;
     }
 
-    if (overlay_size < min_fdt_size || overlay_size != fdt_totalsize(overlay_fdtp)) {
-        dto_error("Bad overlay size!\n");
+    ufdt_node_pool_construct(&pool);
+    final_tree = ufdt_from_fdt(final_fdt_header, final_fdt_size, &pool);
+
+    overlay_trees = new ufdt*[overlay_count];
+    for (size_t i = 0; i < overlay_count; i++) {
+        size_t fdt_size = fdt_totalsize(overlay_arr[i]);
+        overlay_trees[i] = ufdt_from_fdt(overlay_arr[i], fdt_size, &pool);
+    }
+
+    if (ufdt_combine_all_overlays(overlay_trees, overlay_count, final_tree, &pool) < 0) {
+        dto_error("Unable to combine overlays\n");
         goto fail;
     }
-    if (final_fdt_size < min_fdt_size || final_fdt_size != fdt_totalsize(final_fdt_header)) {
-        dto_error("Bad fdt size!\n");
+    if (ufdt_overlay_verify_fragments(final_tree, overlay_trees[0]) < 0) {
+        dto_error("Failed to verify overlay application\n");
         goto fail;
+    } else {
+        result = 0;
     }
 
-    ufdt_node_pool_construct(&pool);
-    final_tree = ufdt_from_fdt(final_fdt_header, final_fdt_size, &pool);
-    overlay_tree = ufdt_from_fdt(overlay_fdtp, overlay_size, &pool);
+fail:
+    if (overlay_trees) {
+        for (size_t i = 0; i < overlay_count; i++) {
+            ufdt_destruct(overlay_trees[i], &pool);
+        }
+        delete[] overlay_trees;
+    }
 
-    result = ufdt_overlay_verify(final_tree, overlay_tree, &pool);
-    ufdt_destruct(overlay_tree, &pool);
     ufdt_destruct(final_tree, &pool);
     ufdt_node_pool_destruct(&pool);
-fail:
     return result;
 }
diff --git a/tests/src/ufdt_verify_overlay_app.cpp b/tests/src/ufdt_verify_overlay_app.cpp
index 0373cee..ff48c1a 100644
--- a/tests/src/ufdt_verify_overlay_app.cpp
+++ b/tests/src/ufdt_verify_overlay_app.cpp
@@ -45,9 +45,9 @@ size_t read_file_to_buf(const char *filename, char** buf) {
 }
 
 int verify_overlay_files(const char *final_filename,
-                         const char *overlay_filename) {
-    char *final_buf = nullptr;
-    char *overlay_buf = nullptr;
+                         char** overlay_filenames, size_t overlay_count) {
+    char* final_buf = nullptr;
+    void** overlay_buf_array = new void*[overlay_count];
     struct fdt_header *blob = nullptr;
     int result = 1;
     size_t final_size = 0, overlay_size = 0;
@@ -58,10 +58,13 @@ int verify_overlay_files(const char *final_filename,
         goto end;
     }
 
-    overlay_size = read_file_to_buf(overlay_filename, &overlay_buf);
-    if (overlay_size == 0) {
-        fprintf(stderr, "Cannot load DTB Overlay: %s\n", overlay_filename);
-        goto end;
+    for (size_t i = 0; i < overlay_count; i++) {
+        overlay_size = read_file_to_buf(overlay_filenames[i],
+                                        reinterpret_cast<char**>(&overlay_buf_array[i]));
+        if (overlay_size == 0) {
+            fprintf(stderr, "Cannot load DTB Overlay: %s\n", overlay_filenames[i]);
+            goto end;
+        }
     }
 
     blob = ufdt_install_blob(final_buf, final_size);
@@ -70,29 +73,37 @@ int verify_overlay_files(const char *final_filename,
         goto end;
     }
 
-    result = ufdt_verify_dtbo(blob, final_size, overlay_buf, overlay_size);
+    result = ufdt_verify_dtbo(blob, final_size, overlay_buf_array, overlay_count);
 
     if (result != 0) {
-        fprintf(stderr, "bad overlay error: %s\n", overlay_filename);
+        fprintf(stderr, "bad overlay error");
     }
 
 end:
     // Do not dto_free(blob) - it's the same as final_buf.
-    if (overlay_buf) dto_free(overlay_buf);
+    for (size_t i = 0; i < overlay_count; i++) {
+        if (overlay_buf_array[i]) dto_free(overlay_buf_array[i]);
+    }
+    delete[] overlay_buf_array;
+
     if (final_buf) dto_free(final_buf);
 
     return result;
 }
 
 int main(int argc, char **argv) {
-  if (argc < 3) {
-    fprintf(stderr, "Usage: %s <final_file> <overlay_file>\n", argv[0]);
-    return 1;
-  }
+    if (argc < 3) {
+        fprintf(stderr, "Usage: %s <final_file> <overlay_file1> <overlay_file2> ..\n", argv[0]);
+        return 1;
+    }
+
+    const char *final_file = argv[1];
+    char** overlay_file_names = new char*[argc - 2];
 
-  const char *final_file = argv[1];
-  const char *overlay_file = argv[2];
-  int ret = verify_overlay_files(final_file, overlay_file);
+    for(int argv_idx = 2; argv_idx < argc; argv_idx++) {
+        overlay_file_names[argv_idx - 2] = argv[argv_idx];
+    }
+    int ret = verify_overlay_files(final_file, overlay_file_names, argc - 2);
 
-  return ret == 0 ? ret : 1;
+    return ret == 0 ? ret : 1;
 }
diff --git a/ufdt_overlay.c b/ufdt_overlay.c
index bdc7bd6..019545f 100644
--- a/ufdt_overlay.c
+++ b/ufdt_overlay.c
@@ -67,7 +67,7 @@ static void fdt_increase_u32(void *pos, uint32_t offset) {
 /*
  * Gets the max phandle of a given ufdt.
  */
-static uint32_t ufdt_get_max_phandle(struct ufdt *tree) {
+uint32_t ufdt_get_max_phandle(struct ufdt *tree) {
   struct ufdt_static_phandle_table sorted_table = tree->phandle_table;
   if (sorted_table.len > 0)
     return sorted_table.data[sorted_table.len - 1].phandle;
@@ -96,7 +96,7 @@ static void ufdt_node_try_increase_phandle(struct ufdt_node *node,
  * Increases all phandles by offset in a ufdt
  * in O(n) time.
  */
-static void ufdt_try_increase_phandle(struct ufdt *tree, uint32_t offset) {
+void ufdt_try_increase_phandle(struct ufdt *tree, uint32_t offset) {
   struct ufdt_static_phandle_table sorted_table = tree->phandle_table;
   int i;
 
@@ -517,8 +517,7 @@ static int ufdt_local_fixup_node(struct ufdt_node *target_node,
  * which follows the dtc patch from:
  * https://marc.info/?l=devicetree&m=144061468601974&w=4
  */
-static int ufdt_overlay_do_local_fixups(struct ufdt *tree,
-                                        uint32_t phandle_offset) {
+int ufdt_overlay_do_local_fixups(struct ufdt *tree, uint32_t phandle_offset) {
   struct ufdt_node *overlay_node = ufdt_get_node_by_path(tree, "/");
   struct ufdt_node *local_fixups_node =
       ufdt_get_node_by_path(tree, "/__local_fixups__");