tests/libufdt_verify/ufdt_test_overlay.cpp - platform/system/libufdt - Git at Google

 /*
  * Copyright (C) 2018 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include <string>
 #include <unordered_map>

 extern "C" {

 #include "libufdt.h"
 #include "ufdt_node_pool.h"
 #include "ufdt_overlay.h"
 #include "ufdt_overlay_internal.h"

 }

 #include "ufdt_test_overlay.h"

 static bool ufdt_node_compare(struct ufdt_node *node_a, struct ufdt_node *node_b,
                               struct ufdt* tree_a, struct ufdt* tree_b);

 /*
  * Helper method to check if the tree rooted at node_b is a subset of the tree rooted
  * at node_a.
  */
 static bool compare_child_nodes(struct ufdt_node *node_a, struct ufdt_node *node_b,
                                 struct ufdt * tree_a, struct ufdt * tree_b) {
     bool result = true;
     struct ufdt_node *it;

     for (it = ((struct ufdt_node_fdt_node *)node_b)->child; it; it = it->sibling) {
         struct ufdt_node *cur_node = it;
         struct ufdt_node *target_node = NULL;

         if (ufdt_node_tag(cur_node) == FDT_BEGIN_NODE) {
             target_node =
                     ufdt_node_get_subnode_by_name(node_a, ufdt_node_name(cur_node));
         } else {
             target_node =
                     ufdt_node_get_property_by_name(node_a, ufdt_node_name(cur_node));
         }

         if (target_node == NULL) {
             result = false;
         } else {
             result = ufdt_node_compare(target_node, cur_node, tree_a, tree_b);
         }

         if (!result) {
             break;
         }
     }

     return result;
 }

 /*
  * Method to compare two nodes with tag FDT_PROP. Also accounts for the cases where
  * the property type is phandle.
  */
 static bool ufdt_compare_property(struct ufdt_node* node_final, struct ufdt_node* node_overlay,
                                   struct ufdt* tree_final, struct ufdt* tree_overlay) {
     if (ufdt_node_tag(node_final) == FDT_PROP) {
         /* Return -1 if property names are differemt */
         if (strcmp(ufdt_node_name(node_final), ufdt_node_name(node_overlay)) != 0)
             return false;

         int length_data_final = 0, length_data_overlay = 0;
         char *prop_data_final = ufdt_node_get_fdt_prop_data(node_final, &length_data_final);
         char *prop_data_overlay = ufdt_node_get_fdt_prop_data(node_overlay,
                                                               &length_data_overlay);

         /* Confirm length for the property values are the same */
         if (length_data_final != length_data_overlay) {
             return false;
         }

         if (((length_data_final == 0) && (length_data_overlay ==0)) ||
             (memcmp(prop_data_final, prop_data_overlay, length_data_final) == 0)) {
             // Return if the properties have same value.
             return true;
         } else {
             /* check for the presence of phandles */
             for (int i = 0; i < length_data_final; i += sizeof(fdt32_t)) {
                 int offset_data_a = fdt32_to_cpu(
                         *reinterpret_cast<fdt32_t *>(prop_data_final + i));
                 int offset_data_b = fdt32_to_cpu(
                         *reinterpret_cast<fdt32_t *>(prop_data_overlay + i));
                 if (offset_data_a == offset_data_b) continue;
                 /* If the offsets have phandles, they would have valid target nodes */
                 struct ufdt_node * target_node_a = ufdt_get_node_by_phandle(tree_final,
                                                                             offset_data_a);
                 struct ufdt_node * target_node_b = ufdt_get_node_by_phandle(tree_overlay,
                                                                             offset_data_b);

                 /*
                  * verify that the target nodes are valid and point to the same node.
                  */
                 if ((target_node_a == NULL) || (target_node_b == NULL) ||
                     strcmp(ufdt_node_name(target_node_a),
                            ufdt_node_name(target_node_b)) != 0) {
                     return false;
                 }
             }
         }
     }

     return true;
 }

 /*
  * Checks if the ufdt tree rooted at node_b is a subtree of the tree rooted at
  * node_a.
  */
 static bool ufdt_node_compare(struct ufdt_node *node_final, struct ufdt_node *node_overlay,
                               struct ufdt * tree_final, struct ufdt * tree_overlay) {
     if (ufdt_node_tag(node_final) == FDT_PROP) {
         return ufdt_compare_property(node_final, node_overlay, tree_final, tree_overlay);
     }

     return compare_child_nodes(node_final, node_overlay, tree_final, tree_overlay);
 }


 /*
  * Multiple fragments may fixup to the same node on the base device tree.
  * Combine these fragments for easier verification.
  */
 void ufdt_combine_fixup(struct ufdt *tree, const char *fixup,
                         struct ufdt_node **prev_node, struct ufdt_node_pool *node_pool) {
     char *path, *prop_ptr, *offset_ptr;
     char path_buf[1024];
     char *path_mem = NULL;
     int result = 0;

     size_t fixup_len = strlen(fixup) + 1;
     if (fixup_len > sizeof(path_buf)) {
         path_mem = static_cast<char *>(dto_malloc(fixup_len));
         path = path_mem;
     } else {
         path = path_buf;
     }
     dto_memcpy(path, fixup, fixup_len);

     prop_ptr = dto_strchr(path, ':');
     if (prop_ptr == NULL) {
         dto_error("Missing property part in '%s'\n", path);
         goto fail;
     }

     *prop_ptr = '\0';
     prop_ptr++;

     offset_ptr = dto_strchr(prop_ptr, ':');
     if (offset_ptr == NULL) {
         dto_error("Missing offset part in '%s'\n", path);
         goto fail;
     }

     *offset_ptr = '\0';
     offset_ptr++;

     result = dto_strcmp(prop_ptr, "target");
     /* If the property being fixed up is not target, ignore and return */
     if (result == 0) {
         struct ufdt_node *target_node;
         target_node = ufdt_get_node_by_path(tree, path);
         if (target_node == NULL) {
             dto_error("Path '%s' not found\n", path);
         } else {
             /* The goal is to combine fragments that have a common target */
             if (*prev_node != NULL) {
                 ufdt_node_merge_into(*prev_node, target_node, node_pool);
             } else {
                 *prev_node = target_node;
             }
         }
     }

 fail:
     if (path_mem) {
         dto_free(path_mem);
     }

     return;
 }

 /*
  * Creates a table of node paths to their corresponding phandles by walking
  * through the 'symbols' node of the main device tree. The table would be
  * used in combining overlay nodes that map to the same nodes in the
  * main device tree.
  */
 void create_path_phandle_map(std::unordered_map<uint32_t, std::string>* phandle_path_map,
                              struct ufdt* main_tree) {
     int len = 0;
     struct ufdt_node *main_symbols_node =
             ufdt_get_node_by_path(main_tree, "/__symbols__");
     if (!main_symbols_node) {
         dto_error("No node __symbols__ in main dtb.\n");
         return;
     }

     struct ufdt_node **it = nullptr;
     for_each_prop(it, main_symbols_node) {
         const char* symbol_path = ufdt_node_get_fdt_prop_data(*it, &len);
         struct ufdt_node* symbol_node = ufdt_get_node_by_path(main_tree, symbol_path);
         uint32_t phandle = ufdt_node_get_phandle(symbol_node);
         (*phandle_path_map)[phandle] = std::string(symbol_path);
     }
 }

 /*
  * Recursively checks whether a node from another overlay fragment had overlaid the
  * target node and if so merges the node into the previous node.
  */
 static void combine_overlay_node(std::unordered_map<std::string,
                                  struct ufdt_node*>* path_node_map,
                                  std::string path,
                                  struct ufdt_node* node,
                                  struct ufdt_node_pool* pool) {
     struct ufdt_node **it = nullptr;
     for_each_node(it, node) {
         //skips properties
         if (ufdt_node_tag(*it) == FDT_BEGIN_NODE) {
             combine_overlay_node(path_node_map, path + "/" + ufdt_node_name(*it), *it, pool);
         }
     }

     if (path_node_map->find(path) != path_node_map->end()) {
         ufdt_node_merge_into((*path_node_map)[path], node, pool);
     } else {
         //This is the first node overlaying the target node, add the same to the
         //table.
         (*path_node_map)[path] = node;
     }
 }

 /* END of doing fixup in the overlay ufdt. */

 static bool ufdt_verify_overlay_node(struct ufdt_node *target_node,
                                      struct ufdt_node *overlay_node,
                                      struct ufdt * target_tree,
                                      struct ufdt * overlay_tree) {
     return ufdt_node_compare(target_node, overlay_node, target_tree, overlay_tree);
 }

 /*
  * verify one overlay fragment (subtree).
  */
 static int ufdt_verify_fragment(struct ufdt *tree,
                                 struct ufdt *overlay_tree,
                                 struct ufdt_node *frag_node) {
     struct ufdt_node *target_node = NULL;
     struct ufdt_node *overlay_node = NULL;
     enum overlay_result target_search_result = ufdt_overlay_get_target(tree, frag_node,
                                                                        &target_node);
     if (target_node == NULL) {
         return target_search_result;
     }

     overlay_node = ufdt_node_get_node_by_path(frag_node, "__overlay__");
     if (overlay_node == NULL) {
         dto_error("missing __overlay__ sub-node\n");
         return OVERLAY_RESULT_MISSING_OVERLAY;
     }

     bool result = ufdt_verify_overlay_node(target_node, overlay_node, tree, overlay_tree);

     if (!result) {
         dto_error("failed to verify overlay node %s to target %s\n",
                   ufdt_node_name(overlay_node), ufdt_node_name(target_node));
         return OVERLAY_RESULT_VERIFY_FAIL;
     }

     return OVERLAY_RESULT_OK;
 }

 /*
  * verify each fragment in overlay.
  */
 static int ufdt_overlay_verify_fragments(struct ufdt *final_tree,
                                          struct ufdt *overlay_tree) {
     enum overlay_result err;
     struct ufdt_node **it;
     for_each_node(it, overlay_tree->root) {
         err = static_cast<enum overlay_result>(ufdt_verify_fragment(final_tree, overlay_tree,
                                                                     *it));
         if (err == OVERLAY_RESULT_VERIFY_FAIL) {
             return -1;
         }
     }
     return 0;
 }

 /*
  * 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* final_tree,
                                               struct ufdt_node_pool* pool
                                              ) {
     std::unordered_map<std::string, struct ufdt_node*> path_node_map;
     std::unordered_map<uint32_t, std::string> phandle_path_map;

     create_path_phandle_map(&phandle_path_map, final_tree);

     struct ufdt_node **it = nullptr;
     for (size_t i = 0; i < overlay_count; i++) {
         for_each_node(it, overlay_trees[i]->root) {
             uint32_t target = 0;
             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);
                 std::string path = phandle_path_map[target];
                 struct ufdt_node* overlay_node = ufdt_node_get_node_by_path(*it, "__overlay__");
                 if (overlay_node != nullptr) {
                     combine_overlay_node(&path_node_map, path, overlay_node, pool);
                 }
             }
         }
     }
 }

 /*
  * 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 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.
      */
     for (size_t i = 0; i < overlay_count; i++) {
         if (ufdt_overlay_do_fixups(final_tree, overlay_trees[i]) < 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, final_tree, 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_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_trees = nullptr;
     int result = 1;

     if (final_fdt_header == NULL) {
         goto fail;
     }

     if (final_fdt_size < min_fdt_size || final_fdt_size != fdt_totalsize(final_fdt_header)) {
         dto_error("Bad fdt size!\n");
         goto fail;
     }

     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 (ufdt_overlay_verify_fragments(final_tree, overlay_trees[0]) < 0) {
         dto_error("Failed to verify overlay application\n");
         goto fail;
     } else {
         result = 0;
     }

 fail:
     if (overlay_trees) {
         for (size_t i = 0; i < overlay_count; i++) {
             ufdt_destruct(overlay_trees[i], &pool);
         }
         delete[] overlay_trees;
     }

     ufdt_destruct(final_tree, &pool);
     ufdt_node_pool_destruct(&pool);
     return result;
 }
	/*
	* Copyright (C) 2018 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include <string>
	#include <unordered_map>

	extern "C" {

	#include "libufdt.h"
	#include "ufdt_node_pool.h"
	#include "ufdt_overlay.h"
	#include "ufdt_overlay_internal.h"

	}

	#include "ufdt_test_overlay.h"

	static bool ufdt_node_compare(struct ufdt_node node_a, struct ufdt_node node_b,
	struct ufdt* tree_a, struct ufdt* tree_b);

	/*
	* Helper method to check if the tree rooted at node_b is a subset of the tree rooted
	* at node_a.
	*/
	static bool compare_child_nodes(struct ufdt_node node_a, struct ufdt_node node_b,
	struct ufdt * tree_a, struct ufdt * tree_b) {
	bool result = true;
	struct ufdt_node *it;

	for (it = ((struct ufdt_node_fdt_node *)node_b)->child; it; it = it->sibling) {
	struct ufdt_node *cur_node = it;
	struct ufdt_node *target_node = NULL;

	if (ufdt_node_tag(cur_node) == FDT_BEGIN_NODE) {
	target_node =
	ufdt_node_get_subnode_by_name(node_a, ufdt_node_name(cur_node));
	} else {
	target_node =
	ufdt_node_get_property_by_name(node_a, ufdt_node_name(cur_node));
	}

	if (target_node == NULL) {
	result = false;
	} else {
	result = ufdt_node_compare(target_node, cur_node, tree_a, tree_b);
	}

	if (!result) {
	break;
	}
	}

	return result;
	}

	/*
	* Method to compare two nodes with tag FDT_PROP. Also accounts for the cases where
	* the property type is phandle.
	*/
	static bool ufdt_compare_property(struct ufdt_node* node_final, struct ufdt_node* node_overlay,
	struct ufdt* tree_final, struct ufdt* tree_overlay) {
	if (ufdt_node_tag(node_final) == FDT_PROP) {
	/* Return -1 if property names are differemt */
	if (strcmp(ufdt_node_name(node_final), ufdt_node_name(node_overlay)) != 0)
	return false;

	int length_data_final = 0, length_data_overlay = 0;
	char *prop_data_final = ufdt_node_get_fdt_prop_data(node_final, &length_data_final);
	char *prop_data_overlay = ufdt_node_get_fdt_prop_data(node_overlay,
	&length_data_overlay);

	/* Confirm length for the property values are the same */
	if (length_data_final != length_data_overlay) {
	return false;
	}

	if (((length_data_final == 0) && (length_data_overlay ==0)) \|\|
	(memcmp(prop_data_final, prop_data_overlay, length_data_final) == 0)) {
	// Return if the properties have same value.
	return true;
	} else {
	/* check for the presence of phandles */
	for (int i = 0; i < length_data_final; i += sizeof(fdt32_t)) {
	int offset_data_a = fdt32_to_cpu(
	reinterpret_cast<fdt32_t >(prop_data_final + i));
	int offset_data_b = fdt32_to_cpu(
	reinterpret_cast<fdt32_t >(prop_data_overlay + i));
	if (offset_data_a == offset_data_b) continue;
	/* If the offsets have phandles, they would have valid target nodes */
	struct ufdt_node * target_node_a = ufdt_get_node_by_phandle(tree_final,
	offset_data_a);
	struct ufdt_node * target_node_b = ufdt_get_node_by_phandle(tree_overlay,
	offset_data_b);

	/*
	* verify that the target nodes are valid and point to the same node.
	*/
	if ((target_node_a == NULL) \|\| (target_node_b == NULL) \|\|
	strcmp(ufdt_node_name(target_node_a),
	ufdt_node_name(target_node_b)) != 0) {
	return false;
	}
	}
	}
	}

	return true;
	}

	/*
	* Checks if the ufdt tree rooted at node_b is a subtree of the tree rooted at
	* node_a.
	*/
	static bool ufdt_node_compare(struct ufdt_node node_final, struct ufdt_node node_overlay,
	struct ufdt * tree_final, struct ufdt * tree_overlay) {
	if (ufdt_node_tag(node_final) == FDT_PROP) {
	return ufdt_compare_property(node_final, node_overlay, tree_final, tree_overlay);
	}

	return compare_child_nodes(node_final, node_overlay, tree_final, tree_overlay);
	}


	/*
	* Multiple fragments may fixup to the same node on the base device tree.
	* Combine these fragments for easier verification.
	*/
	void ufdt_combine_fixup(struct ufdt tree, const char fixup,
	struct ufdt_node *prev_node, struct ufdt_node_pool node_pool) {
	char path, prop_ptr, *offset_ptr;
	char path_buf[1024];
	char *path_mem = NULL;
	int result = 0;

	size_t fixup_len = strlen(fixup) + 1;
	if (fixup_len > sizeof(path_buf)) {
	path_mem = static_cast<char *>(dto_malloc(fixup_len));
	path = path_mem;
	} else {
	path = path_buf;
	}
	dto_memcpy(path, fixup, fixup_len);

	prop_ptr = dto_strchr(path, ':');
	if (prop_ptr == NULL) {
	dto_error("Missing property part in '%s'\n", path);
	goto fail;
	}

	*prop_ptr = '\0';
	prop_ptr++;

	offset_ptr = dto_strchr(prop_ptr, ':');
	if (offset_ptr == NULL) {
	dto_error("Missing offset part in '%s'\n", path);
	goto fail;
	}

	*offset_ptr = '\0';
	offset_ptr++;

	result = dto_strcmp(prop_ptr, "target");
	/* If the property being fixed up is not target, ignore and return */
	if (result == 0) {
	struct ufdt_node *target_node;
	target_node = ufdt_get_node_by_path(tree, path);
	if (target_node == NULL) {
	dto_error("Path '%s' not found\n", path);
	} else {
	/* The goal is to combine fragments that have a common target */
	if (*prev_node != NULL) {
	ufdt_node_merge_into(*prev_node, target_node, node_pool);
	} else {
	*prev_node = target_node;
	}
	}
	}

	fail:
	if (path_mem) {
	dto_free(path_mem);
	}

	return;
	}

	/*
	* Creates a table of node paths to their corresponding phandles by walking
	* through the 'symbols' node of the main device tree. The table would be
	* used in combining overlay nodes that map to the same nodes in the
	* main device tree.
	*/
	void create_path_phandle_map(std::unordered_map<uint32_t, std::string>* phandle_path_map,
	struct ufdt* main_tree) {
	int len = 0;
	struct ufdt_node *main_symbols_node =
	ufdt_get_node_by_path(main_tree, "/__symbols__");
	if (!main_symbols_node) {
	dto_error("No node __symbols__ in main dtb.\n");
	return;
	}

	struct ufdt_node **it = nullptr;
	for_each_prop(it, main_symbols_node) {
	const char* symbol_path = ufdt_node_get_fdt_prop_data(*it, &len);
	struct ufdt_node* symbol_node = ufdt_get_node_by_path(main_tree, symbol_path);
	uint32_t phandle = ufdt_node_get_phandle(symbol_node);
	(*phandle_path_map)[phandle] = std::string(symbol_path);
	}
	}

	/*
	* Recursively checks whether a node from another overlay fragment had overlaid the
	* target node and if so merges the node into the previous node.
	*/
	static void combine_overlay_node(std::unordered_map<std::string,
	struct ufdt_node> path_node_map,
	std::string path,
	struct ufdt_node* node,
	struct ufdt_node_pool* pool) {
	struct ufdt_node **it = nullptr;
	for_each_node(it, node) {
	//skips properties
	if (ufdt_node_tag(*it) == FDT_BEGIN_NODE) {
	combine_overlay_node(path_node_map, path + "/" + ufdt_node_name(it), it, pool);
	}
	}

	if (path_node_map->find(path) != path_node_map->end()) {
	ufdt_node_merge_into((*path_node_map)[path], node, pool);
	} else {
	//This is the first node overlaying the target node, add the same to the
	//table.
	(*path_node_map)[path] = node;
	}
	}

	/* END of doing fixup in the overlay ufdt. */

	static bool ufdt_verify_overlay_node(struct ufdt_node *target_node,
	struct ufdt_node *overlay_node,
	struct ufdt * target_tree,
	struct ufdt * overlay_tree) {
	return ufdt_node_compare(target_node, overlay_node, target_tree, overlay_tree);
	}

	/*
	* verify one overlay fragment (subtree).
	*/
	static int ufdt_verify_fragment(struct ufdt *tree,
	struct ufdt *overlay_tree,
	struct ufdt_node *frag_node) {
	struct ufdt_node *target_node = NULL;
	struct ufdt_node *overlay_node = NULL;
	enum overlay_result target_search_result = ufdt_overlay_get_target(tree, frag_node,
	&target_node);
	if (target_node == NULL) {
	return target_search_result;
	}

	overlay_node = ufdt_node_get_node_by_path(frag_node, "__overlay__");
	if (overlay_node == NULL) {
	dto_error("missing __overlay__ sub-node\n");
	return OVERLAY_RESULT_MISSING_OVERLAY;
	}

	bool result = ufdt_verify_overlay_node(target_node, overlay_node, tree, overlay_tree);

	if (!result) {
	dto_error("failed to verify overlay node %s to target %s\n",
	ufdt_node_name(overlay_node), ufdt_node_name(target_node));
	return OVERLAY_RESULT_VERIFY_FAIL;
	}

	return OVERLAY_RESULT_OK;
	}

	/*
	* verify each fragment in overlay.
	*/
	static int ufdt_overlay_verify_fragments(struct ufdt *final_tree,
	struct ufdt *overlay_tree) {
	enum overlay_result err;
	struct ufdt_node **it;
	for_each_node(it, overlay_tree->root) {
	err = static_cast<enum overlay_result>(ufdt_verify_fragment(final_tree, overlay_tree,
	*it));
	if (err == OVERLAY_RESULT_VERIFY_FAIL) {
	return -1;
	}
	}
	return 0;
	}

	/*
	* 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* final_tree,
	struct ufdt_node_pool* pool
	) {
	std::unordered_map<std::string, struct ufdt_node*> path_node_map;
	std::unordered_map<uint32_t, std::string> phandle_path_map;

	create_path_phandle_map(&phandle_path_map, final_tree);

	struct ufdt_node **it = nullptr;
	for (size_t i = 0; i < overlay_count; i++) {
	for_each_node(it, overlay_trees[i]->root) {
	uint32_t target = 0;
	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);
	std::string path = phandle_path_map[target];
	struct ufdt_node* overlay_node = ufdt_node_get_node_by_path(*it, "__overlay__");
	if (overlay_node != nullptr) {
	combine_overlay_node(&path_node_map, path, overlay_node, pool);
	}
	}
	}
	}
	}

	/*
	* 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 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.
	*/
	for (size_t i = 0; i < overlay_count; i++) {
	if (ufdt_overlay_do_fixups(final_tree, overlay_trees[i]) < 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, final_tree, 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_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_trees = nullptr;
	int result = 1;

	if (final_fdt_header == NULL) {
	goto fail;
	}

	if (final_fdt_size < min_fdt_size \|\| final_fdt_size != fdt_totalsize(final_fdt_header)) {
	dto_error("Bad fdt size!\n");
	goto fail;
	}

	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 (ufdt_overlay_verify_fragments(final_tree, overlay_trees[0]) < 0) {
	dto_error("Failed to verify overlay application\n");
	goto fail;
	} else {
	result = 0;
	}

	fail:
	if (overlay_trees) {
	for (size_t i = 0; i < overlay_count; i++) {
	ufdt_destruct(overlay_trees[i], &pool);
	}
	delete[] overlay_trees;
	}

	ufdt_destruct(final_tree, &pool);
	ufdt_node_pool_destruct(&pool);
	return result;
	}