/*
* 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;
}