diff options
| author | LiChen <akaineko@google.com> | 2016-11-28 12:15:33 +0800 |
|---|---|---|
| committer | SzuWei Lin <szuweilin@google.com> | 2016-12-05 23:30:16 +0000 |
| commit | 3084ce7cbdff84093286459758f99c15082e6556 (patch) | |
| tree | a77b76e8f4f75bddc23ccc0ec52c00f2baf94b3d | |
| parent | b53a69fa5218e6a5069d8ce35148ff882b448ac8 (diff) | |
| download | libufdt-3084ce7cbdff84093286459758f99c15082e6556.tar.gz | |
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
33 files changed, 2991 insertions, 0 deletions
diff --git a/Android.mk b/Android.mk new file mode 100644 index 0000000..4b4830f --- /dev/null +++ b/Android.mk @@ -0,0 +1,41 @@ +# Copyright 2016 The Android Open Source Project + +LOCAL_PATH:= $(call my-dir) + +common_src_files := \ + ufdt_overlay.c \ + ufdt_convert.c \ + ufdt_node.c \ + ufdt_node_dict.c + +################################################### + +include $(CLEAR_VARS) + +LOCAL_MODULE := libufdt +LOCAL_C_INCLUDES := $(LOCAL_PATH)/include +LOCAL_SRC_FILES := $(common_src_files) +LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include +LOCAL_STATIC_LIBRARIES := \ + libfdt \ + libufdt_sysdeps + +include $(BUILD_STATIC_LIBRARY) + +#################################################### + +include $(CLEAR_VARS) + +LOCAL_MODULE := libufdt +LOCAL_C_INCLUDES := $(LOCAL_PATH)/include +LOCAL_SRC_FILES := $(common_src_files) +LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include +LOCAL_STATIC_LIBRARIES := \ + libfdt \ + libufdt_sysdeps + +include $(BUILD_HOST_STATIC_LIBRARY) + +################################################### + +include $(call first-makefiles-under, $(LOCAL_PATH)) diff --git a/fdt_internal.h b/fdt_internal.h new file mode 100644 index 0000000..1ac9d68 --- /dev/null +++ b/fdt_internal.h @@ -0,0 +1,145 @@ +#ifndef FDT_INTERNAL_H +#define FDT_INTERNAL_H + +/* + * libfdt - Flat Device Tree manipulation + * Copyright (C) 2006 David Gibson, IBM Corporation. + * + * libfdt is dual licensed: you can use it either under the terms of + * the GPL, or the BSD license, at your option. + * + * a) This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this library; if not, write to the Free + * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, + * MA 02110-1301 USA + * + * Alternatively, + * + * b) Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the following + * disclaimer. + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, + * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "libfdt.h" +#include "libufdt_sysdeps.h" + + +/* + * Most of the codes below are copied from external/dtc/libfdt/libfdt_internal.h + * and external/dtc/libfdt/fdt_sw.c . + */ + +#define FDT_ALIGN(x, a) (((x) + (a)-1) & ~((a)-1)) +#define FDT_TAGALIGN(x) (FDT_ALIGN((x), FDT_TAGSIZE)) + +static inline const void *_fdt_offset_ptr(const void *fdt, int offset) { + return (const char *)fdt + fdt_off_dt_struct(fdt) + offset; +} + +static inline void *_fdt_offset_ptr_w(void *fdt, int offset) { + return (void *)(uintptr_t)_fdt_offset_ptr(fdt, offset); +} + +#define FDT_SW_MAGIC (~FDT_MAGIC) + +static int _fdt_sw_check_header(void *fdt) { + if (fdt_magic(fdt) != FDT_SW_MAGIC) return -FDT_ERR_BADMAGIC; + /* FIXME: should check more details about the header state */ + return 0; +} + +#define FDT_SW_CHECK_HEADER(fdt) \ + { \ + int err; \ + if ((err = _fdt_sw_check_header(fdt)) != 0) return err; \ + } + +static void *_fdt_grab_space(void *fdt, size_t len) { + int offset = fdt_size_dt_struct(fdt); + int spaceleft; + + spaceleft = + fdt_totalsize(fdt) - fdt_off_dt_struct(fdt) - fdt_size_dt_strings(fdt); + + if ((offset + (int)len < offset) || (offset + (int)len > spaceleft)) + return NULL; + + fdt_set_size_dt_struct(fdt, offset + len); + return _fdt_offset_ptr_w(fdt, offset); +} + +static int _fdt_add_string(void *fdt, const char *s) { + char *strtab = (char *)fdt + fdt_totalsize(fdt); + int strtabsize = fdt_size_dt_strings(fdt); + int len = dto_strlen(s) + 1; + int struct_top, offset; + + /* Add it */ + offset = -strtabsize - len; + struct_top = fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt); + if (fdt_totalsize(fdt) + offset < (size_t)struct_top) + return 0; /* no more room :( */ + + dto_memcpy(strtab + offset, s, len); + fdt_set_size_dt_strings(fdt, strtabsize + len); + return offset; +} + +/* + * From Google, speed up fdt_property() by passing nameoff to the function. + * Adds new string to fdt if *pnameoff is 0. + * Otherwise, use the nameoff provided. + */ +static int fast_fdt_sw_property(void *fdt, const char *name, const void *val, + int len, int *pnameoff, + struct fdt_property **prop_ptr) { + FDT_SW_CHECK_HEADER(fdt); + + if (*pnameoff == 0) { + *pnameoff = _fdt_add_string(fdt, name); + if (*pnameoff == 0) return -FDT_ERR_NOSPACE; + } + + *prop_ptr = _fdt_grab_space(fdt, sizeof(**prop_ptr) + FDT_TAGALIGN(len)); + if (*prop_ptr == NULL) return -FDT_ERR_NOSPACE; + + (*prop_ptr)->tag = cpu_to_fdt32(FDT_PROP); + (*prop_ptr)->nameoff = cpu_to_fdt32(*pnameoff); + (*prop_ptr)->len = cpu_to_fdt32(len); + dto_memcpy((*prop_ptr)->data, val, len); + return 0; +} + +#endif /* FDT_INTERNAL_H */ diff --git a/include/libufdt.h b/include/libufdt.h new file mode 100644 index 0000000..4fc6965 --- /dev/null +++ b/include/libufdt.h @@ -0,0 +1,430 @@ + +#ifndef LIBUFDT_H +#define LIBUFDT_H + +#include "libufdt_sysdeps.h" +#include "ufdt_types.h" + +/* + * BEGIN of ufdt_node_dict methods + * Since in the current implementation, it's actually a hash table. + * So most of operation's time complexity are O(1) with high probability + * (w.h.p.). + */ + +/* + * Allocates some new spaces and creates a new ufdt_node_dict. + * + * @return: a pointer to the newly created ufdt_node_dict or + * NULL if dto_malloc failed + */ +struct ufdt_node_dict ufdt_node_dict_construct(); + +/* + * Frees all space dto_malloced, not including ufdt_nodes in the table. + */ +void ufdt_node_dict_destruct(struct ufdt_node_dict *dict); + +/* + * Adds a ufdt_node (as pointer) to the ufdt_node_dict. + * @return: 0 if success + * < 0 otherwise + * + * @Time: O(length of node->name) w.h.p. + */ +int ufdt_node_dict_add(struct ufdt_node_dict *dict, struct ufdt_node *node); + +/* + * Returns the pointer to the entry in ufdt_node_dict with node->name = + * name[0..len-1], for direct modification of the entry. + * e.g., Delete an entry from the ufdt_node_dict. + * + * @return: a pointer to the entry in ufdt_node_dict or + * NULL if no such entry. + * + * @Time: O(len = |name|) w.h.p. + */ +struct ufdt_node **ufdt_node_dict_find_len(struct ufdt_node_dict *dict, + const char *name, int len); +struct ufdt_node **ufdt_node_dict_find(struct ufdt_node_dict *dict, + const char *name); + +/* + * Returns the pointer to the ufdt_node with node->name = + * name[0..len-1], for direct modification of the node. + * + * @return: a pointer to the node or + * NULL if no such node in ufdt_node_dict with same name. + * + * @Time: O(len = |name|) w.h.p. + */ +struct ufdt_node *ufdt_node_dict_find_node_len(struct ufdt_node_dict *dict, + const char *name, int len); +struct ufdt_node *ufdt_node_dict_find_node(struct ufdt_node_dict *dict, + const char *name); + +/* + * Prints the each (index, node->name) pair in the dict to stdout in the + * following format: + * ``` + * [idx0] [name0] + * [idx1] [name1] + * ... + * ``` + */ +void ufdt_node_dict_print(struct ufdt_node_dict *dict); + +/* + * END of ufdt_node_dict methods + */ + +/* + * BEGIN of ufdt_node methods + */ + +/* + * Allocates spaces for new ufdt_node who represents a fdt node at fdt_tag_ptr. + * In order to get name pointer, it's neccassary to give the pointer to the + * entire fdt it belongs to. + * + * + * @return: a pointer to the newly created ufdt_node or + * NULL if dto_malloc failed + */ +struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr); + +/* + * Frees all nodes in the subtree rooted at *node. + * Also dto_frees those ufdt_node_dicts in each node. + */ +void ufdt_node_destruct(struct ufdt_node *node); + +/* + * Adds the child as a subnode of the parent. + * It's been done by add entries in parent->prop_list or node_list depending on + * the tag type of child. + * + * @return: 0 if success + * < 0 otherwise + * + * @Time: O(1) w.h.p. + */ +int ufdt_node_add_child(struct ufdt_node *parent, struct ufdt_node *child); + +/* BEGIN of FDT_PROP related functions .*/ + +/* + * Gets pointer to FDT_PROP subnode of node with name equals to name[0..len-1] + * + * @return: a pointer to the subnode or + * NULL if no such subnode. + * + * @Time: O(len = length of name) w.h.p. + */ +struct ufdt_node *ufdt_node_get_property_by_name_len( + const struct ufdt_node *node, const char *name, int len); +struct ufdt_node *ufdt_node_get_property_by_name(const struct ufdt_node *node, + const char *name); + +/* + * Gets the pointer to the FDT_PROP node's data in the corresponding fdt. + * Also writes the length of such data to *out_len if out_len is not NULL. + * + * @return: a pointer to some data located in fdt or + * NULL if *node is not a FDT_PROP + */ +char *ufdt_node_get_fdt_prop_data(const struct ufdt_node *node, int *out_len); + +/* + * Gets pointer to FDT_PROP node's data in fdt with name equals to + * name[0..len-1], which is a subnode of *node. + * It's actually a composition of ufdt_node_get_property_by_name and + * ufdt_node_get_fdt_prop_data + * + * @return: a pointer to some data located in fdt or + * NULL if no such subnode. + * + * @Time: O(len = length of name) w.h.p. + */ +char *ufdt_node_get_fdt_prop_data_by_name_len(const struct ufdt_node *node, + const char *name, int len, + int *out_len); +char *ufdt_node_get_fdt_prop_data_by_name(const struct ufdt_node *node, + const char *name, int *out_len); + +/* END of FDT_PROP related functions .*/ + +/* + * Gets pointer to FDT_BEGIN_NODE subnode of node with name equals to + * name[0..len-1]. + * + * @return: a pointer to the subnode or + * NULL if no such subnode. + * + * @Time: O(len = length of name) w.h.p. + */ + +struct ufdt_node *ufdt_node_get_subnode_by_name_len(const struct ufdt_node *node, + const char *name, int len); +struct ufdt_node *ufdt_node_get_subnode_by_name(const struct ufdt_node *node, + const char *name); + +/* + * Gets the pointer to FDT_NODE node whose relative path to *node is + * path[0..len-1]. + * Note that the relative path doesn't support parent node like: + * "../path/to/node". + * + * @return: a pointer to the node or + * NULL if no such node. + * + * @Time: O(len = length of path) w.h.p. + */ +struct ufdt_node *ufdt_node_get_node_by_path_len(const struct ufdt_node *node, + const char *path, int len); +struct ufdt_node *ufdt_node_get_node_by_path(const struct ufdt_node *node, + const char *path); + +/* + * Gets the phandle value of the node if it has. + * + * @return: phandle value of that node or + * 0 if *node is not FDT_NODE or there's no "phandle"/"linux,phandle" + * property. + * + * @Time: O(1) w.h.p. + */ +uint32_t ufdt_node_get_phandle(const struct ufdt_node *node); + +/* + * END of ufdt_node methods + */ + +/* + * BEGIN of ufdt methods. + */ + +/* + * Constructs a ufdt whose base fdt is fdtp. + * Note that this function doesn't construct the entire tree. + * To get the whole tree please call `fdt_to_ufdt(fdtp, fdt_size)` + * + * @return: an empty ufdt with base fdtp = fdtp + */ +struct ufdt *ufdt_construct(void *fdtp); + +/* + * Frees the space occupied by the ufdt, including all ufdt_nodes and + * ufdt_node_dicts along + * with static_phandle_table. + */ +void ufdt_destruct(struct ufdt *tree); + +/* + * Gets the pointer to the ufdt_node in tree with phandle = phandle. + * The function do a binary search in tree->phandle_table. + * + * @return: a pointer to the target ufdt_node + * NULL if no ufdt_node has phandle = phandle + * + * @Time: O(log(# of nodes in tree)) = O(log(size of underlying fdt)) + */ +struct ufdt_node *ufdt_get_node_by_phandle(struct ufdt *tree, uint32_t phandle); + +/* + * Gets the pointer to the ufdt_node in tree with absoulte path = + * path[0..len-1]. + * Absolute path has form "/path/to/node" or "some_alias/to/node". + * In later example, some_alias is a property in "/aliases" with data is a path + * to some node X. Then the funcion will return node with relative + * path = "to/node" w.r.t. X. + * + * @return: a pointer to the target ufdt_node or + * NULL if such dnt doesn't exist. + * + * @Time: O(len = length of path) w.h.p. + */ +struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path, + int len); +struct ufdt_node *ufdt_get_node_by_path(struct ufdt *tree, const char *path); + +/* + * END of ufdt methods. + */ + +/* + * Compares function between 2 nodes, compare by name of each node. + * + * @return: x < 0 if a's name is lexicographically smaller + * x == 0 if a, b has same name + * x > 0 if a's name is lexicographically bigger + */ +int node_cmp(const void *a, const void *b); + +/* + * Determines whether node->name equals to name[0..len-1] + * + * @return: true if they're equal. + * false otherwise + */ +bool node_name_eq(const struct ufdt_node *node, const char *name, int len); + +/* + * Merges tree_b into tree_a with tree_b has all nodes except root disappeared. + * Overwrite property in tree_a if there's one with same name in tree_b. + * Otherwise add the property to tree_a. + * For subnodes with the same name, recursively run this function. + * + * Ex: + * tree_a : ta { + * b = "b"; + * c = "c"; + * d { + * e = "g"; + * }; + * }; + * + * tree_b : tb { + * c = "C"; + * g = "G"; + * d { + * da = "dad"; + * }; + * h { + * hh = "HH"; + * }; + * }; + * + * The resulting trees will be: + * + * tree_a : ta { + * b = "b"; + * c = "C"; + * g = "G"; + * d { + * da = "dad"; + * e = "g"; + * }; + * h { + * hh = "HH"; + * }; + * }; + * + * tree_b : tb { + * }; + * + * + * @return: 0 if merge success + * < 0 otherwise + * + * @Time: O(# of nodes in tree_b + total length of all names in tree_b) w.h.p. + */ +int merge_ufdt_into(struct ufdt_node *tree_a, struct ufdt_node *tree_b); + +/* + * BEGIN of ufdt output functions + */ + +/* + * Builds the ufdt for FDT pointed by fdtp. + * This including build all ufdt_nodes and ufdt_node_dicts, and builds the + * phandle table as + * well. + * + * @return: the ufdt T representing fdtp or + * T with T.fdtp == NULL if fdtp is unvalid. + * + * @Time: O(fdt_size + nlogn) where n = # of nodes in fdt. + */ +struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size); + +/* + * Sequentially dumps the tree rooted at *node to FDT buffer fdtp. + * Basically it calls functions provided by libfdt/fdt_sw.c. + * + * All those functions works fast. + * But when it comes to dump property node to fdt, the function they + * provide(fdt_property()) is really slow. Since it runs through all strings + * stored in fdt to find the right `nameoff` for the property node. + * + * So we implement our own fdt_property() called `output_property_to_fdt()`, the + * basic + * idea is that we keep a hash table that we can search for the nameoff of the + * string in constant time instead of O(total length of strings) search. + * + * @return: 0 if successfully dump or + * < 0 otherwise + * + * @Time: O(total length of all names + # of nodes in subtree rooted at *root) + */ +int output_ufdt_node_to_fdt(struct ufdt_node *node, void *fdtp, + struct ufdt_node_dict *all_props); + +/* + * Sequentially dumps the whole ufdt to FDT buffer fdtp with buffer size + * buf_size. + * Basically it calls functions provided by libfdt/fdt_sw.c. + * The main overhead here is to dump the tree to fdtp by calling + * output_ufdt_node_to_fdt(). + * + * + * @return: 0 if successfully dump or + * < 0 otherwise + * + * @Time: O(total length of all names + # of nodes in tree) + */ +int ufdt_to_fdt(struct ufdt *tree, void *buf, int buf_size); + +/* + * prints the entire subtree rooted at *node in form: + * NODE :[node name]: + * PROP :[prop name]: + * ... + * NODE :[subnode1 name]: + * ... + * NODE :[subnode1 name]: + * ... + * ... + * There're (depth * TAB_SIZE) spaces in front of each line. + */ +void ufdt_node_print(const struct ufdt_node *node, int depth); + +/* + * It's just ufdt_node_print(tree->root, 0). + */ +void ufdt_print(struct ufdt *tree); + +/* + * END of ufdt output functions + */ + +/* + * Runs closure.func(node, closure.env) for all nodes in subtree rooted at + * *node. + * The order of each node being applied by the function is depth first. + * Basically it's the same order as the order printed in ufdt_node_print(). + * + * Example: + * + * void print_name(struct ufdt_node *node, void *env) { + * printf("%s\n", node->name); + * } + * + * struct ufdt_node_closure clos; + * clos.func = print_name; + * clos.env = NULL; + * ufdt_map(tree, clos); + * + * Then you can print all names of nodes in tree. + * + * @Time: O((# of nodes in subtree rooted at *node) * avg. running time of the + * function closure.func) + */ +void ufdt_node_map(struct ufdt_node *node, struct ufdt_node_closure closure); + +/* + * It's just ufdt_node_map(tree->root, closure); + */ +void ufdt_map(struct ufdt *tree, struct ufdt_node_closure closure); + +#endif /* LIBUFDT_H */ diff --git a/include/ufdt_overlay.h b/include/ufdt_overlay.h new file mode 100644 index 0000000..ed4bf87 --- /dev/null +++ b/include/ufdt_overlay.h @@ -0,0 +1,26 @@ +#ifndef UFDT_OVERLAY_H +#define UFDT_OVERLAY_H + +#include <libfdt.h> + +/* Given a buffer in RAM containing the contents of a .dtb file, + * it initializes an FDT in-place and returns a pointer to the + * given buffer, or NULL in case of error. + * In case of error, it may printf() diagnostic messages. + */ +struct fdt_header *ufdt_install_blob(void *blob, size_t blob_size); + +/* Given a main_fdt_header buffer and an overlay_fdtp buffer containing the + * contents of a .dtbo file, it creates a new FDT containing the applied + * overlay_fdtp in a dto_malloc'd buffer and returns it, or NULL in case of + * error. + * It is allowed to modify the buffers (both main_fdt_header and overlay_fdtp + * buffer) passed in. + * It does not dto_free main_fdt_header and overlay_fdtp buffer passed in. + */ +struct fdt_header *ufdt_apply_overlay(struct fdt_header *main_fdt_header, + size_t main_fdt_size, + void *overlay_fdtp, + size_t overlay_size); + +#endif /* UFDT_OVERLAY_H */ diff --git a/include/ufdt_types.h b/include/ufdt_types.h new file mode 100644 index 0000000..2f9f849 --- /dev/null +++ b/include/ufdt_types.h @@ -0,0 +1,96 @@ +#ifndef UFDT_TYPES_H +#define UFDT_TYPES_H + +#include <libfdt.h> + +#define ASCII_PRINT_S (32) +#define ASCII_PRINT_E (128) +#define ASCII_PRINT_SZ (ASCII_PRINT_E - ASCII_PRINT_S) + +#define FDT_PROP_DELI ':' +#define FDT_NODE_DELI '/' + +#define DTNL_INIT_SZ 4 + +/* Empirical values for hash functions. */ +#define HASH_BASE 13131 + +/* it has type : struct ufdt_node** */ +#define for_each(it, node_dict) \ + if ((node_dict) != NULL) \ + for (it = (node_dict)->nodes; \ + it != (node_dict)->nodes + (node_dict)->mem_size; ++it) \ + if (*it) + +#define for_each_child(it, node) \ + if (tag_of(node) == FDT_BEGIN_NODE) \ + for ((it) = &(((struct fdt_node_ufdt_node *)node)->child); *it; \ + it = &((*it)->sibling)) + +#define for_each_prop(it, node) \ + for_each_child(it, node) if (tag_of(*it) == FDT_PROP) + +#define for_each_node(it, node) \ + for_each_child(it, node) if (tag_of(*it) == FDT_BEGIN_NODE) + +/* + * Gets prop name from FDT requires complicated manipulation. + * To avoid the manipulation, the *name pointer in fdt_prop_ufdt_node + * is pointed to the final destination of the prop name in FDT. + * For the FDT_BEGIN_NODE name, it can be obtained from FDT directly. + */ +#define name_of(node) \ + ((tag_of(node) == FDT_BEGIN_NODE) \ + ? (((const struct fdt_node_header *)((node)->fdt_tag_ptr))->name) \ + : (((const struct fdt_prop_ufdt_node *)node)->name)) + +struct ufdt_node { + fdt32_t *fdt_tag_ptr; + struct ufdt_node *sibling; +}; + +struct ufdt_node_dict { + int mem_size; + int num_used; + struct ufdt_node **nodes; +}; + +struct fdt_prop_ufdt_node { + struct ufdt_node parent; + const char *name; +}; + +struct fdt_node_ufdt_node { + struct ufdt_node parent; + struct ufdt_node *child; +}; + +struct phandle_table_entry { + uint32_t phandle; + struct ufdt_node *node; +}; + +struct static_phandle_table { + int len; + struct phandle_table_entry *data; +}; + +struct ufdt { + void *fdtp; + struct ufdt_node *root; + struct static_phandle_table phandle_table; +}; + +typedef void func_on_ufdt_node(struct ufdt_node *, void *); + +struct ufdt_node_closure { + func_on_ufdt_node *func; + void *env; +}; + +static uint32_t tag_of(const struct ufdt_node *node) { + if (!node) return FDT_END; + return fdt32_to_cpu(*node->fdt_tag_ptr); +} + +#endif /* UFDT_TYPES_H */ diff --git a/sysdeps/Android.mk b/sysdeps/Android.mk new file mode 100644 index 0000000..a5c16a1 --- /dev/null +++ b/sysdeps/Android.mk @@ -0,0 +1,25 @@ +# Copyright 2016 The Android Open Source Project + +LOCAL_PATH:= $(call my-dir) + +################################################### + +include $(CLEAR_VARS) + +LOCAL_MODULE := libufdt_sysdeps +LOCAL_C_INCLUDES := $(LOCAL_PATH)/include +LOCAL_SRC_FILES := libufdt_sysdeps_posix.c +LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include + +include $(BUILD_STATIC_LIBRARY) + +################################################### + +include $(CLEAR_VARS) + +LOCAL_MODULE := libufdt_sysdeps +LOCAL_C_INCLUDES := $(LOCAL_PATH)/include +LOCAL_SRC_FILES := libufdt_sysdeps_posix.c +LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include + +include $(BUILD_HOST_STATIC_LIBRARY) diff --git a/sysdeps/include/libufdt_sysdeps.h b/sysdeps/include/libufdt_sysdeps.h new file mode 100644 index 0000000..c2682c7 --- /dev/null +++ b/sysdeps/include/libufdt_sysdeps.h @@ -0,0 +1,61 @@ +#ifndef LIBDTOVERLAY_SYSDEPS_H +#define LIBDTOVERLAY_SYSDEPS_H + +/* Change these includes to match your platform to bring in the + * equivalent types available in a normal C runtime. At least things + * like uint8_t, uint64_t, and bool (with |false|, |true| keywords) + * must be present. + */ +#include <inttypes.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +#ifdef DTO_ENABLE_DEBUG +/* Print functions, used for diagnostics. + * + * These have no effect unless FDT_ENABLE_DEBUG is defined. + */ +#define dto_debug(...) \ + do { \ + dto_print("DEBUG: %s():", __func__); \ + dto_print(__VA_ARGS__); \ + } while (0) +#else +#define dto_debug(...) +#endif + +#define dto_error(...) \ + do { \ + dto_print("ERROR: %s():", __func__); \ + dto_print(__VA_ARGS__); \ + } while (0) + +int dto_print(const char *fmt, ...); + +void dto_qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)); + +void *dto_malloc(size_t size); + +void dto_free(void *ptr); + +char *dto_strdup(const char *s); + +char *dto_strchr(const char *s, int c); + +unsigned long int dto_strtoul(const char *nptr, char **endptr, int base); + +size_t dto_strlen(const char *s); + +void *dto_memcpy(void *dest, const void *src, size_t n); + +int dto_strcmp(const char *s1, const char *s2); + +int dto_strncmp(const char *s1, const char *s2, size_t n); + +void *dto_memchr(const void *s, int c, size_t n); + +void *dto_memset(void *s, int c, size_t n); + +#endif /* LIBDTOVERLAY_SYSDEPS_H */ diff --git a/sysdeps/libufdt_sysdeps_posix.c b/sysdeps/libufdt_sysdeps_posix.c new file mode 100644 index 0000000..97e8c4e --- /dev/null +++ b/sysdeps/libufdt_sysdeps_posix.c @@ -0,0 +1,50 @@ + +#include "libufdt_sysdeps.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int dto_print(const char *fmt, ...) { + int err; + + va_list ap; + va_start(ap, fmt); + err = vfprintf(stderr, fmt, ap); + va_end(ap); + + return err; +} + +void dto_qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) { + qsort(base, nmemb, size, compar); +} + +void *dto_malloc(size_t size) { return malloc(size); } + +void dto_free(void *ptr) { free(ptr); } + +char *dto_strdup(const char *s) { return strdup(s); } + +char *dto_strchr(const char *s, int c) { return strchr(s, c); } + +unsigned long int dto_strtoul(const char *nptr, char **endptr, int base) { + return strtoul(nptr, endptr, base); +} + +size_t dto_strlen(const char *s) { return strlen(s); } + +void *dto_memcpy(void *dest, const void *src, size_t n) { + return memcpy(dest, src, n); +} + +int dto_strcmp(const char *s1, const char *s2) { return strcmp(s1, s2); } + +int dto_strncmp(const char *s1, const char *s2, size_t n) { + return strncmp(s1, s2, n); +} + +void *dto_memchr(const void *s, int c, size_t n) { return memchr(s, c, n); } + +void *dto_memset(void *s, int c, size_t n) { return memset(s, c, n); } diff --git a/sysdeps/libufdt_sysdeps_vendor.c b/sysdeps/libufdt_sysdeps_vendor.c new file mode 100644 index 0000000..e21a2e1 --- /dev/null +++ b/sysdeps/libufdt_sysdeps_vendor.c @@ -0,0 +1,209 @@ +#include "libufdt_sysdeps.h" + +#include <debug.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/types.h> + +int dto_print(const char *fmt, ...) { + int err; + + va_list ap; + va_start(ap, fmt); + err = _dvprintf(fmt, ap); + va_end(ap); + + return err; +} + +/* Codes from + * https://android.googlesource.com/platform/bionic.git/+/eclair-release/libc/stdlib/qsort.c + * Start + */ + +/* $OpenBSD: qsort.c,v 1.10 2005/08/08 08:05:37 espie Exp $ */ +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +static __inline char *med3(char *, char *, char *, + int (*)(const void *, const void *)); +static __inline void swapfunc(char *, char *, int, int); +#define min(a, b) (a) < (b) ? a : b + +/* + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + */ +#define swapcode(TYPE, parmi, parmj, n) \ + { \ + long i = (n) / sizeof(TYPE); \ + TYPE *pi = (TYPE *)(parmi); \ + TYPE *pj = (TYPE *)(parmj); \ + do { \ + TYPE t = *pi; \ + *pi++ = *pj; \ + *pj++ = t; \ + } while (--i > 0); \ + } +#define SWAPINIT(a, es) \ + swaptype = ((char *)a - (char *)0) % sizeof(long) || es % sizeof(long) \ + ? 2 \ + : es == sizeof(long) ? 0 : 1; + +static __inline void swapfunc(char *a, char *b, int n, int swaptype) { + if (swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n) +} + +#define swap(a, b) \ + if (swaptype == 0) { \ + long t = *(long *)(a); \ + *(long *)(a) = *(long *)(b); \ + *(long *)(b) = t; \ + } else \ + swapfunc(a, b, es, swaptype) +#define vecswap(a, b, n) \ + if ((n) > 0) swapfunc(a, b, n, swaptype) + +static __inline char *med3(char *a, char *b, char *c, + int (*cmp)(const void *, const void *)) { + return cmp(a, b) < 0 ? (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a)) + : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c)); +} + +void qsort(void *aa, size_t n, size_t es, + int (*cmp)(const void *, const void *)) { + char *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swaptype, swap_cnt; + char *a = aa; +loop: + SWAPINIT(a, es); + swap_cnt = 0; + if (n < 7) { + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) + swap(pl, pl - es); + return; + } + pm = (char *)a + (n / 2) * es; + if (n > 7) { + pl = (char *)a; + pn = (char *)a + (n - 1) * es; + if (n > 40) { + d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp); + pm = med3(pm - d, pm, pm + d, cmp); + pn = med3(pn - 2 * d, pn - d, pn, cmp); + } + pm = med3(pl, pm, pn, cmp); + } + swap(a, pm); + pa = pb = (char *)a + es; + + pc = pd = (char *)a + (n - 1) * es; + for (;;) { + while (pb <= pc && (r = cmp(pb, a)) <= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pa, pb); + pa += es; + } + pb += es; + } + while (pb <= pc && (r = cmp(pc, a)) >= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pc, pd); + pd -= es; + } + pc -= es; + } + if (pb > pc) break; + swap(pb, pc); + swap_cnt = 1; + pb += es; + pc -= es; + } + if (swap_cnt == 0) { /* Switch to insertion sort */ + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) + swap(pl, pl - es); + return; + } + pn = (char *)a + n * es; + r = min(pa - (char *)a, pb - pa); + vecswap(a, pb - r, r); + r = min(pd - pc, pn - pd - (int)es); + vecswap(pb, pn - r, r); + if ((r = pb - pa) > (int)es) qsort(a, r / es, es, cmp); + if ((r = pd - pc) > (int)es) { + /* Iterate rather than recurse to save stack space */ + a = pn - r; + n = r / es; + goto loop; + } + /* qsort(pn - r, r / es, es, cmp); */ +} + +/* End of the copied qsort. */ + +void dto_qsort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) { + qsort(base, nmemb, size, compar); +} + +/* Assuming the following functions are already defined in the + * bootloader source with the names conforming to POSIX. + */ + +void *dto_malloc(size_t size) { return malloc(size); } + +void dto_free(void *ptr) { free(ptr); } + +char *dto_strdup(const char *s) { return strdup(s); } + +char *dto_strchr(const char *s, int c) { return strchr(s, c); } + +unsigned long int dto_strtoul(const char *nptr, char **endptr, int base) { + return strtoul(nptr, endptr, base); +} + +size_t dto_strlen(const char *s) { return strlen(s); } + +void *dto_memcpy(void *dest, const void *src, size_t n) { + return memcpy(dest, src, n); +} + +int dto_strcmp(const char *s1, const char *s2) { return strcmp(s1, s2); } + +int dto_strncmp(const char *s1, const char *s2, size_t n) { + return strncmp(s1, s2, n); +} + +void *dto_memchr(const void *s, int c, size_t n) { return memchr(s, c, n); } + +void *dto_memset(void *s, int c, size_t n) { return memset(s, c, n); } diff --git a/tests/README b/tests/README new file mode 100644 index 0000000..645470d --- /dev/null +++ b/tests/README @@ -0,0 +1,51 @@ +This folder contains scripts and test data to test libufdt. + +# Test scripts + +* run_tests.sh: The main entry to run test cases. Using different + test cases under testdata/*. +* gen_test.sh: The script to run a single test case. +* common.sh: A common lib containing several useful functions. + +# Test data + +testdata/${my_test_case}.base_dts + - Base device tree source. + - Sample format: + ``` + /dts-v1/; + / { + a: a{}; + }; + ``` + +testdata/${my_test_case}.add_dts + - Additional device tree source. + - Sample format: + ``` + &a{ name = "a"; }; + ``` + +testdata/${my_test_case}.add_ov_dts (optional) + - Additional device tree fragment source. + - Sample format: + ``` + /dts-v1/ /plugin/; + / { + fragment@0{ + target = <&a>; + __overlay__ { + name = "a"; + }; + }; + }; + ``` + +# Steps to run the test + +Suppose you are at the root directory of your Android source. + +1. `source build/envsetup.sh` +2. `lunch` +3. `mmma system/libufdt` +4. `system/libufdt/tests/run_tests.sh` diff --git a/tests/common.sh b/tests/common.sh new file mode 100755 index 0000000..4c8ce78 --- /dev/null +++ b/tests/common.sh @@ -0,0 +1,41 @@ +#!/bin/bash + +alert() { + echo "$*" >&2 +} + +die() { + echo "ERROR: $@" + exit 1 +} + +command_exists () { + type "$1" &> /dev/null; +} + +dtb_to_dts () { + dtc -O dts -s $1 + if [ $? -ne 0 ]; then + die "dtb_to_dts $1 failed!" + fi +} + +dts_to_dtb () { + dtc -O dtb -s -@ $1 + if [ $? -ne 0 ]; then + die "dts_to_dtb $1 failed!" + fi +} + +remove_local_fixups() { + sed '/__local_fixups__/ {s/^\s*__local_fixups__\s*//; :again;N; s/{[^{}]*};//; /^$/ !b again; d}' $1 +} + +remove_overlay_stuff() { + # remove __symbols__, phandle, "linux,phandle" and __local_fixups__ + sed "/__symbols__/,/[}];/d" $1 | sed "/\(^[ \t]*phandle\)/d" | sed "/\(^[ \t]*linux,phandle\)/d" | sed '/^\s*$/d' | remove_local_fixups +} + +dt_diff () { + diff -u <(dtb_to_dts "$1" | remove_overlay_stuff) <(dtb_to_dts "$2" | remove_overlay_stuff) +} diff --git a/tests/gen_test.sh b/tests/gen_test.sh new file mode 100755 index 0000000..5f30b71 --- /dev/null +++ b/tests/gen_test.sh @@ -0,0 +1,91 @@ +#!/bin/bash + +# We want to generate two device tree blob (.dtb) files by combining +# the "base" and "add" device tree source (.dts) files in two +# different ways. +# +# 1) /include/ the "add" at the end of the "base" file and +# compile with dtc to make the "gold standard" .dtb +# +# 2) Compile them separately (modifying the "add" file to +# be an overlay file) with dtc, then join them with the +# ov_test program +# +# To do this, we need to generate a lot of files from the .base_dts +# and .add_dts files: +# .base_inc_dts - Has the /include/ "${FILENAME}.add_dts" at the end. +# .base_inc_dtb - The dtc-generated "gold standard" +# .add_ov_dts - Has the /plugin/ at the start +# .base_dtb - Compiled version of just the base +# .add_ov_dtbo - Compiled version of the overlay +# .base_ov_dtb - overlay-test-joined version of the dtb +# +# Then, compare .base_inc_dtb and .base_ov_dtb with dtdiff +# (or maybe diff?) and return 0 iff they are identical. + +# Include some functions from common.sh. +SCRIPT_DIR="$(dirname "$(readlink -f "$0")")" +source ${SCRIPT_DIR}/common.sh + +# Constants +IN_DATA_DIR="testdata" +OUT_DATA_DIR="test-out" + +# Global variables +FILENAME=$1 + +on_exit() { + rm -rf "${OUT_DATA_DIR}" +} + +# Generate test cases to OUT_DATA_DIR +prepare_tests() { + cp "${IN_DATA_DIR}/${FILENAME}.base_dts" "${OUT_DATA_DIR}/${FILENAME}.base_dts" + cp "${IN_DATA_DIR}/${FILENAME}.add_dts" "${OUT_DATA_DIR}/${FILENAME}.add_dts" + + # Add the "include" to make .base_inc_dts + cp "${IN_DATA_DIR}/${FILENAME}.base_dts" "${OUT_DATA_DIR}/${FILENAME}.base_inc_dts" + echo "/include/ \"${FILENAME}.add_dts\"" >> "${OUT_DATA_DIR}/${FILENAME}.base_inc_dts" + + # Generate .base_inc_dtb + dtc -@ -O dtb -s -b 0 -o "${OUT_DATA_DIR}/${FILENAME}.base_inc.dtb" \ + "${OUT_DATA_DIR}/${FILENAME}.base_inc_dts" + + # Add /dts-v1/ /plugin/; in front of .add_dts file. In order to trigger dtc's + # fragment generation mechanism. + if [ -a "${IN_DATA_DIR}/${FILENAME}.add_ov_dts" ]; then + cp "${IN_DATA_DIR}/${FILENAME}.add_ov_dts" "${OUT_DATA_DIR}/${FILENAME}.add_ov_dts" + else + sed "1i/dts-v1/ /plugin/;" "${IN_DATA_DIR}/${FILENAME}.add_dts" > \ + "${OUT_DATA_DIR}/${FILENAME}.add_ov_dts" + fi +} + +# Compile test cases into dtb, and do the diff things. +compile_and_diff() { + # Compile the base to make .base_dtb + dtc -O dtb -b 0 -@ -o "${OUT_DATA_DIR}/${FILENAME}.base_dtb" \ + "${OUT_DATA_DIR}/${FILENAME}.base_dts" + + # Compile the overlay to make .add_ov_dtbo + dtc -O dtb -b 0 -@ -o "${OUT_DATA_DIR}/${FILENAME}.add_ov_dtbo" \ + "${OUT_DATA_DIR}/${FILENAME}.add_ov_dts" + + # Run ov_test to combine .base_dtb and .add_ov_dtbo + # into .base_ov_dtb + ufdt_apply_overlay "${OUT_DATA_DIR}/${FILENAME}.base_dtb" \ + "${OUT_DATA_DIR}/${FILENAME}.add_ov_dtbo" \ + "${OUT_DATA_DIR}/${FILENAME}.base_ov.dtb" + + # Run the diff + dt_diff ${OUT_DATA_DIR}/${FILENAME}.base_inc.dtb ${OUT_DATA_DIR}/${FILENAME}.base_ov.dtb +} + +# The script will exit directly if any command fails. +set -e +trap on_exit EXIT + +mkdir -p "${OUT_DATA_DIR}" >& /dev/null + +prepare_tests +compile_and_diff diff --git a/tests/run_tests.sh b/tests/run_tests.sh new file mode 100755 index 0000000..845f190 --- /dev/null +++ b/tests/run_tests.sh @@ -0,0 +1,68 @@ +#!/bin/bash + +# Include some functions from common.sh. +SCRIPT_DIR="$(dirname "$(readlink -f "$0")")" +source ${SCRIPT_DIR}/common.sh + +# Usage: run_test_case <filename> <description> +# Args: +# filename: The file name for ./gen_test.sh to generate and run the +# test case. Several files under ./testdata subfolder are required: +# - ./testdata/${filename}.base_dts +# - ./testdata/${filename}.add_dts +# - ./testdata/${filename}.add_ov_dts (optional) +# For more details, check ./gen_test.sh. +# description: a description message to be displayed in the terminal +run_test_case() { + local filename="$1" + local description="$2" + + alert "${description}" + ./gen_test.sh "${filename}" >&2 || + die "Test case: ${filename} failed!!" +} + +main() { + alert "========== Running Tests of libufdt ==========" + + if [ -z "${ANDROID_BUILD_TOP}" ]; then + die "Run envsetup.sh / lunch yet?" + fi + + if ! command_exists dtc || + ! command_exists ufdt_apply_overlay; then + die "Run mmma $(dirname ${SCRIPT_DIR}) yet?" + fi + + ( + + # cd to ${SCRIPT_DIR} in a subshell because gen_test.sh uses relative + # paths for dependent files. + cd "${SCRIPT_DIR}" + + run_test_case \ + "no_local_fixup" \ + "Run test about fdt_apply_fragment with no local fixup" + run_test_case \ + "apply_fragment" \ + "Run test about fdt_apply_fragment with phandle update" + run_test_case \ + "libufdt_local_fixup" \ + "Run test about fdt_overlay_do_local_fixups" + run_test_case \ + "dtc_local_fixup" \ + "Run test about local fixup format consistent with current dtc" + run_test_case \ + "local_fixup_with_offset" \ + "Run test about dealing with local fixup with offset > 0" + run_test_case \ + "overlay_2_layers" \ + "Run test about dealing with overlay deep tree" + ) + + if [ $? -ne 0 ]; then + die "Some test cases failed, please check error message..." + fi +} + +main "$@" diff --git a/tests/src/Android.mk b/tests/src/Android.mk new file mode 100644 index 0000000..4239c81 --- /dev/null +++ b/tests/src/Android.mk @@ -0,0 +1,19 @@ +# Copyright 2016 The Android Open Source Project + +LOCAL_PATH:= $(call my-dir) + +################################################### + +include $(CLEAR_VARS) + +LOCAL_MODULE := ufdt_apply_overlay +LOCAL_SRC_FILES := ufdt_overlay_test_app.c +LOCAL_STATIC_LIBRARIES := \ + libufdt \ + libfdt \ + libufdt_sysdeps +LOCAL_REQUIRED_MODULES := dtc + +include $(BUILD_HOST_EXECUTABLE) + +################################################### diff --git a/tests/src/ufdt_overlay_test_app.c b/tests/src/ufdt_overlay_test_app.c new file mode 100644 index 0000000..ce30936 --- /dev/null +++ b/tests/src/ufdt_overlay_test_app.c @@ -0,0 +1,69 @@ +#include "ufdt_overlay.h" + +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +#include "libufdt_sysdeps.h" + + +char *load_file(char *fname, size_t *pLen); + +char *load_file(char *fname, size_t *pLen) { + FILE *f; + f = fopen(fname, "r"); + if (!f) { + printf("Couldn't open file '%s'\n", fname); + exit(1); + } + fseek(f, 0, SEEK_END); + *pLen = ftell(f); + fseek(f, 0, SEEK_SET); + char *buf = dto_malloc(*pLen); + if (fread(buf, *pLen, 1, f) != 1) { + printf("Bad fread"); + exit(1); + } + return buf; +} + +int main(int argc, char **argv) { + char *base_buf, *overlay_buf; + FILE *out_file; + struct fdt_header *blob; + if (argc < 4) { + printf("Usage: ov_test base_file overlay_file out_file\n"); + exit(1); + } + size_t blob_len, overlay_len; + base_buf = load_file(argv[1], &blob_len); + overlay_buf = load_file(argv[2], &overlay_len); + if (!overlay_buf) return 1; + blob = ufdt_install_blob(base_buf, blob_len); + + if (!blob) { + printf("ufdt_install_blob returned null\n"); + exit(1); + } + clock_t start, end; + double cpu_time_used; + start = clock(); + struct fdt_header *new_blob = + ufdt_apply_overlay(blob, blob_len, overlay_buf, overlay_len); + end = clock(); + cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; + + printf("ufdt_apply_overlay took %.9f second\n", cpu_time_used); + + // Do not dto_free(blob) - it's the same as base_buf. + + out_file = fopen(argv[3], "wb"); + if (fwrite(new_blob, 1, fdt_totalsize(new_blob), out_file) < 1) { + printf("fwrite failed\n"); + exit(1); + } + free(new_blob); + free(base_buf); + free(overlay_buf); + return 0; +} diff --git a/tests/testdata/apply_fragment.add_dts b/tests/testdata/apply_fragment.add_dts new file mode 100644 index 0000000..7666089 --- /dev/null +++ b/tests/testdata/apply_fragment.add_dts @@ -0,0 +1,2 @@ +&a { d: d{}; }; +&b { e{}; }; diff --git a/tests/testdata/apply_fragment.base_dts b/tests/testdata/apply_fragment.base_dts new file mode 100644 index 0000000..c116a9b --- /dev/null +++ b/tests/testdata/apply_fragment.base_dts @@ -0,0 +1,6 @@ +/dts-v1/; +/ { + a: a {}; + b: b {}; + c: c {}; +}; diff --git a/tests/testdata/dtc_local_fixup.add_dts b/tests/testdata/dtc_local_fixup.add_dts new file mode 100644 index 0000000..b158cd7 --- /dev/null +++ b/tests/testdata/dtc_local_fixup.add_dts @@ -0,0 +1,5 @@ +&a { + c: c{ + d{ interrupt_parent = <&c>; }; + }; +}; diff --git a/tests/testdata/dtc_local_fixup.base_dts b/tests/testdata/dtc_local_fixup.base_dts new file mode 100644 index 0000000..f5a1086 --- /dev/null +++ b/tests/testdata/dtc_local_fixup.base_dts @@ -0,0 +1,8 @@ +/dts-v1/; +/ { +a: a { + interrupt_parent = <&a>; + }; +}; + + diff --git a/tests/testdata/libufdt_local_fixup.add_dts b/tests/testdata/libufdt_local_fixup.add_dts new file mode 100644 index 0000000..b158cd7 --- /dev/null +++ b/tests/testdata/libufdt_local_fixup.add_dts @@ -0,0 +1,5 @@ +&a { + c: c{ + d{ interrupt_parent = <&c>; }; + }; +}; diff --git a/tests/testdata/libufdt_local_fixup.add_ov_dts b/tests/testdata/libufdt_local_fixup.add_ov_dts new file mode 100644 index 0000000..2734141 --- /dev/null +++ b/tests/testdata/libufdt_local_fixup.add_ov_dts @@ -0,0 +1,11 @@ +/dts-v1/ /plugin/; +/ { + fragment@0 { + target = <&a>; + __overlay__ { + c: c{ + d{ interrupt_parent = <&c>; }; + }; + }; + }; +}; diff --git a/tests/testdata/libufdt_local_fixup.base_dts b/tests/testdata/libufdt_local_fixup.base_dts new file mode 100644 index 0000000..556e3dc --- /dev/null +++ b/tests/testdata/libufdt_local_fixup.base_dts @@ -0,0 +1,8 @@ +/dts-v1/; +/ { + a: a { + interrupt_parent = <&a>; + }; +}; + + diff --git a/tests/testdata/local_fixup_with_offset.add_dts b/tests/testdata/local_fixup_with_offset.add_dts new file mode 100644 index 0000000..f45757e --- /dev/null +++ b/tests/testdata/local_fixup_with_offset.add_dts @@ -0,0 +1,8 @@ +&a { + c: c{ + d{ interrupt_parent = <0 1 &c 2 3>; }; + }; + e: e{ + f{ interrupt_parent = <&c 5 &e>; }; + }; +}; diff --git a/tests/testdata/local_fixup_with_offset.base_dts b/tests/testdata/local_fixup_with_offset.base_dts new file mode 100644 index 0000000..f90145d --- /dev/null +++ b/tests/testdata/local_fixup_with_offset.base_dts @@ -0,0 +1,6 @@ +/dts-v1/; +/ { +a: a { + interrupt_parent = <&a>; + }; +}; diff --git a/tests/testdata/no_local_fixup.add_dts b/tests/testdata/no_local_fixup.add_dts new file mode 100644 index 0000000..2cdf6a4 --- /dev/null +++ b/tests/testdata/no_local_fixup.add_dts @@ -0,0 +1,3 @@ +&a { c = "new-c"; + d: d = "d"; +}; diff --git a/tests/testdata/no_local_fixup.base_dts b/tests/testdata/no_local_fixup.base_dts new file mode 100644 index 0000000..01bad36 --- /dev/null +++ b/tests/testdata/no_local_fixup.base_dts @@ -0,0 +1,7 @@ +/dts-v1/; +/ { + a: a { + b = "b"; + c = "c"; + }; + }; diff --git a/tests/testdata/overlay_2_layers.add_dts b/tests/testdata/overlay_2_layers.add_dts new file mode 100644 index 0000000..952a462 --- /dev/null +++ b/tests/testdata/overlay_2_layers.add_dts @@ -0,0 +1,7 @@ +&a { + g = "g"; + d { + f = "f"; + }; +}; + diff --git a/tests/testdata/overlay_2_layers.base_dts b/tests/testdata/overlay_2_layers.base_dts new file mode 100644 index 0000000..1d7b578 --- /dev/null +++ b/tests/testdata/overlay_2_layers.base_dts @@ -0,0 +1,11 @@ +/dts-v1/; +/ { + a: a { + b = "b"; + c = "c"; + d { + e = "e"; + }; + }; +}; + diff --git a/ufdt_convert.c b/ufdt_convert.c new file mode 100644 index 0000000..caa3ce3 --- /dev/null +++ b/ufdt_convert.c @@ -0,0 +1,294 @@ +#include "libufdt.h" + +#include "fdt_internal.h" +#include "ufdt_util.h" + + +struct ufdt *ufdt_construct(void *fdtp) { + struct ufdt *res_ufdt = dto_malloc(sizeof(struct ufdt)); + res_ufdt->fdtp = fdtp; + res_ufdt->root = NULL; + + return res_ufdt; +} + +void ufdt_destruct(struct ufdt *tree) { + ufdt_node_destruct(tree->root); + dto_free(tree->phandle_table.data); +} + +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"); + return NULL; + } + + fdt32_t *fdt_tag_ptr = + (fdt32_t *)fdt_offset_ptr(fdtp, node_offset, sizeof(fdt32_t)); + struct ufdt_node *res = ufdt_node_construct(fdtp, fdt_tag_ptr); + return res; +} + +static struct ufdt_node *fdt_to_ufdt_tree(void *fdtp, int cur_fdt_tag_offset, + int *next_fdt_tag_offset, + int cur_tag) { + if (fdtp == NULL) { + return NULL; + } + uint32_t tag; + struct ufdt_node *res, *child_node; + + res = NULL; + child_node = NULL; + tag = cur_tag; + + switch (tag) { + case FDT_END_NODE: + case FDT_NOP: + case FDT_END: + break; + + case FDT_PROP: + res = ufdt_new_node(fdtp, cur_fdt_tag_offset); + break; + + case FDT_BEGIN_NODE: + res = ufdt_new_node(fdtp, cur_fdt_tag_offset); + + do { + cur_fdt_tag_offset = *next_fdt_tag_offset; + tag = fdt_next_tag(fdtp, cur_fdt_tag_offset, next_fdt_tag_offset); + child_node = fdt_to_ufdt_tree(fdtp, cur_fdt_tag_offset, + next_fdt_tag_offset, tag); + ufdt_node_add_child(res, child_node); + } while (tag != FDT_END_NODE); + break; + + default: + break; + } + + return res; +} + +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) { + /* + * RARE: aliases + * In device tree, we can assign some alias to specific nodes by defining + * these relation in "/aliases" node. + * The node has the form: + * { + * a = "/a_for_apple"; + * b = "/b_for_banana"; + * }; + * So the path "a/subnode_1" should be expanded to "/a_for_apple/subnode_1". + */ + if (*path != '/') { + const char *end = path + len; + + const char *next_slash; + next_slash = dto_memchr(path, '/', end - path); + if (!next_slash) next_slash = end; + + struct ufdt_node *aliases_node = + ufdt_node_get_node_by_path(tree->root, "/aliases"); + aliases_node = ufdt_node_get_property_by_name_len(aliases_node, path, + next_slash - path); + + int path_len = 0; + const char *alias_path = + ufdt_node_get_fdt_prop_data(aliases_node, &path_len); + + if (alias_path == NULL) { + dto_error("Failed to find alias %s\n", path); + return NULL; + } + + struct ufdt_node *target_node = + ufdt_node_get_node_by_path_len(tree->root, alias_path, path_len); + + return ufdt_node_get_node_by_path_len(target_node, next_slash, + end - next_slash); + } + return ufdt_node_get_node_by_path_len(tree->root, path, len); +} + +struct ufdt_node *ufdt_get_node_by_path(struct ufdt *tree, const char *path) { + return ufdt_get_node_by_path_len(tree, path, dto_strlen(path)); +} + +struct ufdt_node *ufdt_get_node_by_phandle(struct ufdt *tree, + uint32_t phandle) { + struct ufdt_node *res = NULL; + /* + * Do binary search in phandle_table.data. + * [s, e) means the possible range which contains target node. + */ + int s = 0, e = tree->phandle_table.len; + while (e - s > 1) { + int mid = s + ((e - s) >> 1); + uint32_t mid_phandle = tree->phandle_table.data[mid].phandle; + if (phandle < mid_phandle) + e = mid; + else + s = mid; + } + if (e - s > 0) { + res = tree->phandle_table.data[s].node; + } + return res; +} + +int merge_children(struct ufdt_node *node_a, struct ufdt_node *node_b) { + int err = 0; + struct ufdt_node *it; + for (it = ((struct fdt_node_ufdt_node *)node_b)->child; it;) { + struct ufdt_node *cur_node = it; + it = it->sibling; + cur_node->sibling = NULL; + struct ufdt_node *target_node = NULL; + if (tag_of(cur_node) == FDT_BEGIN_NODE) { + target_node = ufdt_node_get_subnode_by_name(node_a, name_of(cur_node)); + } else { + target_node = ufdt_node_get_property_by_name(node_a, name_of(cur_node)); + } + if (target_node == NULL) { + err = ufdt_node_add_child(node_a, cur_node); + } else { + err = merge_ufdt_into(target_node, cur_node); + } + if (err < 0) return -1; + } + /* + * The ufdt_node* in node_b will be copied to node_a. + * To prevent the ufdt_node from being freed twice + * (main_tree and overlay_tree) at the end of function + * ufdt_apply_overlay(), set this node in node_b + * (overlay_tree) to NULL. + */ + ((struct fdt_node_ufdt_node *)node_b)->child = NULL; + + return 0; +} + +int merge_ufdt_into(struct ufdt_node *node_a, struct ufdt_node *node_b) { + if (tag_of(node_a) == FDT_PROP) { + node_a->fdt_tag_ptr = node_b->fdt_tag_ptr; + return 0; + } + + int err = 0; + err = merge_children(node_a, node_b); + if (err < 0) return -1; + + return 0; +} + +void ufdt_map(struct ufdt *tree, struct ufdt_node_closure closure) { + ufdt_node_map(tree->root, closure); +} + +static int count_phandle_node(struct ufdt_node *node) { + if (node == NULL) return 0; + if (tag_of(node) != FDT_BEGIN_NODE) return 0; + int res = 0; + if (ufdt_node_get_phandle(node) > 0) res++; + struct ufdt_node **it; + for_each_child(it, node) { res += count_phandle_node(*it); } + return res; +} + +static void set_phandle_table_entry(struct ufdt_node *node, + struct phandle_table_entry *data, + int *cur) { + if (node == NULL || tag_of(node) != FDT_BEGIN_NODE) return; + int ph = ufdt_node_get_phandle(node); + if (ph > 0) { + data[*cur].phandle = ph; + data[*cur].node = node; + (*cur)++; + } + struct ufdt_node **it; + for_each_node(it, node) set_phandle_table_entry(*it, data, cur); + return; +} + +int phandle_table_entry_cmp(const void *pa, const void *pb) { + uint32_t ph_a = ((const struct phandle_table_entry *)pa)->phandle; + uint32_t ph_b = ((const struct phandle_table_entry *)pb)->phandle; + if (ph_a < ph_b) + return -1; + else if (ph_a == ph_b) + return 0; + else + return 1; +} + +struct static_phandle_table build_phandle_table(struct ufdt *tree) { + struct static_phandle_table res; + res.len = count_phandle_node(tree->root); + res.data = dto_malloc(sizeof(struct phandle_table_entry) * res.len); + int cur = 0; + set_phandle_table_entry(tree->root, res.data, &cur); + dto_qsort(res.data, res.len, sizeof(struct phandle_table_entry), + phandle_table_entry_cmp); + return res; +} + +struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size) { + (void)(fdt_size); // unused parameter + + struct ufdt *res_tree = ufdt_construct(fdtp); + + int start_offset = fdt_path_offset(fdtp, "/"); + if (start_offset < 0) { + res_tree->fdtp = NULL; + return res_tree; + } + + 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); + + res_tree->phandle_table = build_phandle_table(res_tree); + + return res_tree; +} + +int ufdt_to_fdt(struct ufdt *tree, void *buf, int buf_size) { + int err; + err = fdt_create(buf, buf_size); + if (err < 0) return -1; + + int n_mem_rsv = fdt_num_mem_rsv(tree->fdtp); + for (int i = 0; i < n_mem_rsv; i++) { + uint64_t addr, size; + fdt_get_mem_rsv(tree->fdtp, 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); + if (err < 0) return -1; + + ufdt_node_dict_destruct(&all_props); + + err = fdt_finish(buf); + if (err < 0) return -1; + + /* + * IMPORTANT: fdt_totalsize(buf) might be less than buf_size + * so this is needed to make use of remain spaces. + */ + return fdt_open_into(buf, buf, buf_size); +} diff --git a/ufdt_node.c b/ufdt_node.c new file mode 100644 index 0000000..2ffd6a0 --- /dev/null +++ b/ufdt_node.c @@ -0,0 +1,302 @@ +#include "libufdt.h" +#include "ufdt_util.h" + + +int node_cmp(const void *a, const void *b) { + const struct ufdt_node *na = *(struct ufdt_node **)a; + const struct ufdt_node *nb = *(struct ufdt_node **)b; + return dto_strcmp(name_of(na), name_of(nb)); +} + +bool node_name_eq(const struct ufdt_node *node, const char *name, int len) { + if (!node) return false; + if (!name) return false; + if (dto_strncmp(name_of(node), name, len) != 0) return false; + if (name_of(node)[len] != '\0') return false; + return true; +} + +/* + * ufdt_node methods. + */ + +struct ufdt_node *ufdt_node_construct(void *fdtp, fdt32_t *fdt_tag_ptr) { + uint32_t tag = fdt32_to_cpu(*fdt_tag_ptr); + if (tag == FDT_PROP) { + struct fdt_prop_ufdt_node *res = dto_malloc(sizeof(struct fdt_prop_ufdt_node)); + if (res == NULL) return NULL; + res->parent.fdt_tag_ptr = fdt_tag_ptr; + res->parent.sibling = NULL; + res->name = get_name(fdtp, (struct ufdt_node *)res); + return (struct ufdt_node *)res; + } else { + struct fdt_node_ufdt_node *res = dto_malloc(sizeof(struct fdt_node_ufdt_node)); + if (res == NULL) return NULL; + res->parent.fdt_tag_ptr = fdt_tag_ptr; + res->parent.sibling = NULL; + res->child = NULL; + return (struct ufdt_node *)res; + } +} + +void ufdt_node_destruct(struct ufdt_node *node) { + if (node == NULL) return; + + if (tag_of(node) == FDT_BEGIN_NODE) { + ufdt_node_destruct(((struct fdt_node_ufdt_node *)node)->child); + } + + ufdt_node_destruct(node->sibling); + dto_free(node); + + return; +} + +int ufdt_node_add_child(struct ufdt_node *parent, struct ufdt_node *child) { + if (!parent || !child) return -1; + if (tag_of(parent) != FDT_BEGIN_NODE) return -1; + + int err = 0; + uint32_t child_tag = tag_of(child); + + switch (child_tag) { + case FDT_PROP: + case FDT_BEGIN_NODE: + child->sibling = ((struct fdt_node_ufdt_node *)parent)->child; + ((struct fdt_node_ufdt_node *)parent)->child = child; + break; + + default: + err = -1; + dto_error("invalid children tag type\n"); + } + + return err; +} + +/* + * BEGIN of FDT_PROP related methods. + */ + +struct ufdt_node *ufdt_node_get_subnode_by_name_len(const struct ufdt_node *node, + const char *name, int len) { + struct ufdt_node **it = NULL; + for_each_node(it, node) { + if (node_name_eq(*it, name, len)) return *it; + } + return NULL; +} + +struct ufdt_node *ufdt_node_get_subnode_by_name(const struct ufdt_node *node, + const char *name) { + return ufdt_node_get_subnode_by_name_len(node, name, strlen(name)); +} + +struct ufdt_node *ufdt_node_get_property_by_name_len( + const struct ufdt_node *node, const char *name, int len) { + if (!node) return NULL; + + struct ufdt_node **it = NULL; + for_each_prop(it, node) { + if (node_name_eq(*it, name, len)) return *it; + } + return NULL; +} + +struct ufdt_node *ufdt_node_get_property_by_name(const struct ufdt_node *node, + const char *name) { + return ufdt_node_get_property_by_name_len(node, name, dto_strlen(name)); +} + +char *ufdt_node_get_fdt_prop_data(const struct ufdt_node *node, int *out_len) { + if (!node || tag_of(node) != FDT_PROP) { + return NULL; + } + const struct fdt_property *prop = (struct fdt_property *)node->fdt_tag_ptr; + if (out_len != NULL) { + *out_len = fdt32_to_cpu(prop->len); + } + return (char *)prop->data; +} + +char *ufdt_node_get_fdt_prop_data_by_name_len(const struct ufdt_node *node, + const char *name, int len, + int *out_len) { + return ufdt_node_get_fdt_prop_data( + ufdt_node_get_property_by_name_len(node, name, len), out_len); +} + +char *ufdt_node_get_fdt_prop_data_by_name(const struct ufdt_node *node, + const char *name, int *out_len) { + return ufdt_node_get_fdt_prop_data(ufdt_node_get_property_by_name(node, name), + out_len); +} + +/* + * END of FDT_PROP related methods. + */ + +/* + * BEGIN of searching-in-ufdt_node methods. + */ + +uint32_t ufdt_node_get_phandle(const struct ufdt_node *node) { + if (!node || tag_of(node) != FDT_BEGIN_NODE) { + return 0; + } + int len = 0; + void *ptr = ufdt_node_get_fdt_prop_data_by_name(node, "phandle", &len); + if (!ptr || len != sizeof(fdt32_t)) { + ptr = ufdt_node_get_fdt_prop_data_by_name(node, "linux,phandle", &len); + if (!ptr || len != sizeof(fdt32_t)) { + return 0; + } + } + return fdt32_to_cpu(*((fdt32_t *)ptr)); +} + +struct ufdt_node *ufdt_node_get_node_by_path_len(const struct ufdt_node *node, + const char *path, int len) { + const char *end = path + len; + + struct ufdt_node *cur = (struct ufdt_node *)node; + + while (path < end) { + while (path[0] == '/') path++; + if (path == end) return cur; + + const char *next_slash; + next_slash = dto_memchr(path, '/', end - path); + if (!next_slash) next_slash = end; + + struct ufdt_node *next = NULL; + + next = ufdt_node_get_subnode_by_name_len(cur, path, next_slash - path); + + cur = next; + path = next_slash; + if (!cur) return cur; + } + + return cur; +} + +struct ufdt_node *ufdt_node_get_node_by_path(const struct ufdt_node *node, + const char *path) { + return ufdt_node_get_node_by_path_len(node, path, dto_strlen(path)); +} + +/* + * END of searching-in-ufdt_node methods. + */ + +int output_property_to_fdt(struct ufdt_node *prop_node, void *fdtp, + struct ufdt_node_dict *props_dict) { + int err = 0; + int len = 0; + void *data = ufdt_node_get_fdt_prop_data(prop_node, &len); + int nameoff = 0; + struct ufdt_node *same_name_prop = + ufdt_node_dict_find_node(props_dict, name_of(prop_node)); + + /* + * There's already a property with same name, take its nameoff instead. + */ + if (same_name_prop != NULL) { + const struct fdt_property *prop = + (const struct fdt_property *)same_name_prop->fdt_tag_ptr; + nameoff = fdt32_to_cpu(prop->nameoff); + } + /* + * Modifies prop_node->fdt_tag_ptr to point to the node in new fdtp. + */ + err = fast_fdt_sw_property(fdtp, name_of(prop_node), data, len, &nameoff, + (struct fdt_property **)&(prop_node->fdt_tag_ptr)); + + if (err < 0) { + dto_error("Not enough space for the string space: %d\n", + fdt_size_dt_strings(fdtp)); + } + ufdt_node_dict_add(props_dict, prop_node); + return err; +} + +int output_ufdt_node_to_fdt(struct ufdt_node *node, void *fdtp, + struct ufdt_node_dict *props_dict) { + uint32_t tag = tag_of(node); + + if (tag == FDT_PROP) { + int err = output_property_to_fdt(node, fdtp, props_dict); + return err; + } + + int err = fdt_begin_node(fdtp, name_of(node)); + if (err < 0) return -1; + + struct ufdt_node **it; + for_each_prop(it, node) { + err = output_ufdt_node_to_fdt(*it, fdtp, props_dict); + if (err < 0) return -1; + } + + for_each_node(it, node) { + err = output_ufdt_node_to_fdt(*it, fdtp, props_dict); + if (err < 0) return -1; + } + + err = fdt_end_node(fdtp); + if (err < 0) return -1; + + return 0; +} + +#define TAB_SIZE 2 + +void ufdt_node_print(const struct ufdt_node *node, int depth) { + if (!node) return; + + int i; + for (i = 0; i < depth * TAB_SIZE; i++) dto_print(" "); + + uint32_t tag; + tag = tag_of(node); + + switch (tag) { + case FDT_BEGIN_NODE: + dto_print("NODE "); + break; + case FDT_PROP: + dto_print("PROP "); + break; + default: + dto_print("UNKNOWN "); + break; + } + + if (name_of(node)) { + dto_print(":%s:\n", name_of(node)); + } else { + dto_print("node name is NULL.\n"); + } + + if (tag_of(node) == FDT_BEGIN_NODE) { + struct ufdt_node **it; + + for_each_prop(it, node) ufdt_node_print(*it, depth + 1); + + for_each_node(it, node) ufdt_node_print(*it, depth + 1); + } + + return; +} + +void ufdt_node_map(struct ufdt_node *node, struct ufdt_node_closure closure) { + if (node == NULL) return; + closure.func(node, closure.env); + if (tag_of(node) == FDT_BEGIN_NODE) { + struct ufdt_node **it; + for_each_prop(it, node) ufdt_node_map(*it, closure); + for_each_node(it, node) ufdt_node_map(*it, closure); + } + return; +} 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)); +} diff --git a/ufdt_overlay.c b/ufdt_overlay.c new file mode 100644 index 0000000..d581ca7 --- /dev/null +++ b/ufdt_overlay.c @@ -0,0 +1,648 @@ +/*- + * Copyright (c) 2015 Oleksandr Tymoshenko <gonzo@FreeBSD.org> + * All rights reserved. + * + * This software was developed by Semihalf under sponsorship from + * the FreeBSD Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include "ufdt_overlay.h" + +#include "libufdt.h" + + +/* + * The original version of fdt_overlay.c is slow in searching for particular + * nodes and adding subnodes/properties due to the operations on flattened + * device tree (FDT). + * + * Here we introduce `libufdt` which 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. + * + * This file is the improved version of fdt_overlay.c by using the real tree + * structure defined in libufdt. + * + * How the device tree overlay works and some + * special terms (e.g., fixups, local fixups, fragment, etc) + * are described in the document + * external/dtc/Documentation/dt-object-internal.txt. + */ + +/* BEGIN of operations about phandles in ufdt. */ + +/* + * Increases u32 value at pos by offset. + */ +static void fdt_increase_u32(void *pos, uint32_t offset) { + uint32_t val; + + dto_memcpy(&val, pos, sizeof(val)); + val = cpu_to_fdt32(fdt32_to_cpu(val) + offset); + dto_memcpy(pos, &val, sizeof(val)); +} + +/* + * Gets the max phandle of a given ufdt. + */ +static uint32_t ufdt_get_max_phandle(struct ufdt *tree) { + struct static_phandle_table sorted_table = tree->phandle_table; + if (sorted_table.len > 0) + return sorted_table.data[sorted_table.len - 1].phandle; + else + return 0; +} + +/* + * Tries to increase the phandle value of a node + * if the phandle exists. + */ +static void ufdt_node_try_increase_phandle(struct ufdt_node *node, + uint32_t offset) { + int len = 0; + char *prop_data = ufdt_node_get_fdt_prop_data_by_name(node, "phandle", &len); + if (prop_data != NULL && len == sizeof(fdt32_t)) { + fdt_increase_u32(prop_data, offset); + } + prop_data = ufdt_node_get_fdt_prop_data_by_name(node, "linux,phandle", &len); + if (prop_data != NULL && len == sizeof(fdt32_t)) { + fdt_increase_u32(prop_data, offset); + } +} + +/* + * Increases all phandles by offset in a ufdt + * in O(n) time. + */ +static void ufdt_try_increase_phandle(struct ufdt *tree, uint32_t offset) { + struct static_phandle_table sorted_table = tree->phandle_table; + int i; + + for (i = 0; i < sorted_table.len; i++) { + struct ufdt_node *target_node = sorted_table.data[i].node; + + ufdt_node_try_increase_phandle(target_node, offset); + } +} + +/* END of operations about phandles in ufdt. */ + +/* + * In the overlay_tree, there are some references (phandle) + * pointing to somewhere in the main_tree. + * Fix-up operations is to resolve the right address + * in the overlay_tree. + */ + +/* BEGIN of doing fixup in the overlay ufdt. */ + +/* + * Returns exact memory location specified by fixup in format + * /path/to/node:property:offset. + * A property might contain multiple values and the offset is used to locate a + * reference inside the property. + * e.g., + * "property"=<1, 2, &ref, 4>, we can use /path/to/node:property:8 to get ref, + * where 8 is sizeof(uint32) + sizeof(unit32). + */ +static void *ufdt_get_fixup_location(struct ufdt *tree, const char *fixup) { + char *path, *prop_ptr, *offset_ptr, *end_ptr; + int prop_offset, prop_len; + const char *prop_data; + + /* + * TODO(akaineko): Keep track of substring lengths so we don't have to + * dto_malloc a copy and split it up. + */ + path = dto_strdup(fixup); + 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++; + + prop_offset = dto_strtoul(offset_ptr, &end_ptr, 10 /* base */); + if (*end_ptr != '\0') { + dto_error("'%s' is not valid number\n", offset_ptr); + goto fail; + } + + 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); + goto fail; + } + + prop_data = + ufdt_node_get_fdt_prop_data_by_name(target_node, prop_ptr, &prop_len); + if (prop_data == NULL) { + dto_error("Property '%s' not found in '%s' node\n", prop_ptr, path); + goto fail; + } + /* + * Note that prop_offset is the offset inside the property data. + */ + if (prop_len < prop_offset + (int)sizeof(uint32_t)) { + dto_error("%s: property length is too small for fixup\n", path); + goto fail; + } + + dto_free(path); + return (char *)prop_data + prop_offset; + +fail: + dto_free(path); + return NULL; +} + +/* + * Process one entry in __fixups__ { } node. + * @fixups is property value, array of NUL-terminated strings + * with fixup locations. + * @fixups_len length of the fixups array in bytes. + * @phandle is value for these locations. + */ +static int ufdt_do_one_fixup(struct ufdt *tree, const char *fixups, + int fixups_len, int phandle) { + void *fixup_pos; + uint32_t val; + + val = cpu_to_fdt32(phandle); + + while (fixups_len > 0) { + fixup_pos = ufdt_get_fixup_location(tree, fixups); + if (fixup_pos != NULL) { + dto_memcpy(fixup_pos, &val, sizeof(val)); + } else { + return -1; + } + + fixups_len -= dto_strlen(fixups) + 1; + fixups += dto_strlen(fixups) + 1; + } + + return 0; +} + +/* + * Handle __fixups__ node in overlay tree. + */ + +static int ufdt_overlay_do_fixups(struct ufdt *main_tree, + struct ufdt *overlay_tree) { + int len = 0; + struct ufdt_node *main_symbols_node, *overlay_fixups_node; + + main_symbols_node = ufdt_get_node_by_path(main_tree, "/__symbols__"); + overlay_fixups_node = ufdt_get_node_by_path(overlay_tree, "/__fixups__"); + + if (!main_symbols_node) { + dto_error("Bad main_symbols in ufdt_overlay_do_fixups\n"); + return -1; + } + + if (!overlay_fixups_node) { + dto_error("Bad overlay_fixups in ufdt_overlay_do_fixups\n"); + return -1; + } + + struct ufdt_node **it; + for_each_prop(it, overlay_fixups_node) { + /* + * A property in __fixups__ looks like: + * symbol_name = + * "/path/to/node:prop:offset0\x00/path/to/node:prop:offset1..." + * So we firstly find the node "symbol_name" and obtain its phandle in + * __symbols__ of the main_tree. + */ + + struct ufdt_node *fixups = *it; + char *symbol_path = ufdt_node_get_fdt_prop_data_by_name( + main_symbols_node, name_of(fixups), &len); + + if (!symbol_path) { + dto_error("Couldn't find '%s' symbol in main dtb\n", name_of(fixups)); + return -1; + } + + struct ufdt_node *symbol_node; + symbol_node = ufdt_get_node_by_path(main_tree, symbol_path); + + if (!symbol_node) { + dto_error("Couldn't find '%s' path in main dtb\n", symbol_path); + return -1; + } + + uint32_t phandle = ufdt_node_get_phandle(symbol_node); + + const char *fixups_paths = ufdt_node_get_fdt_prop_data(fixups, &len); + + if (ufdt_do_one_fixup(overlay_tree, fixups_paths, len, phandle) < 0) { + dto_error("Failed one fixup in ufdt_do_one_fixup\n"); + return -1; + } + } + + return 0; +} + +/* END of doing fixup in the overlay ufdt. */ + +/* + * Here is to overlay all fragments in the overlay_tree to the main_tree. + * What is "overlay fragment"? The main purpose is to add some subtrees to the + * main_tree in order to complete the entire device tree. + * + * A frgament consists of two parts: 1. the subtree to be added 2. where it + * should be added. + * + * Overlaying a fragment requires: 1. find the node in the main_tree 2. merge + * the subtree into that node in the main_tree. + */ + +/* BEGIN of applying fragments. */ + +/* + * Overlay the overlay_node over target_node. + */ +static int ufdt_overlay_node(struct ufdt_node *target_node, + struct ufdt_node *overlay_node) { + return merge_ufdt_into(target_node, overlay_node); +} + +/* + * Return value of ufdt_apply_fragment(). + */ + +enum overlay_result { + OVERLAY_RESULT_OK, + OVERLAY_RESULT_MISSING_TARGET, + OVERLAY_RESULT_MISSING_OVERLAY, + OVERLAY_RESULT_TARGET_PATH_INVALID, + OVERLAY_RESULT_TARGET_INVALID, + OVERLAY_RESULT_MERGE_FAIL, +}; + +/* + * Apply one overlay fragment (subtree). + */ +static enum overlay_result ufdt_apply_fragment(struct ufdt *tree, + struct ufdt_node *frag_node) { + uint32_t target; + const char *target_path; + const void *val; + struct ufdt_node *target_node = NULL; + struct ufdt_node *overlay_node = NULL; + + val = ufdt_node_get_fdt_prop_data_by_name(frag_node, "target", NULL); + if (val) { + dto_memcpy(&target, val, sizeof(target)); + target = fdt32_to_cpu(target); + target_node = ufdt_get_node_by_phandle(tree, target); + if (target_node == NULL) { + dto_error("failed to find target %04x\n", target); + return OVERLAY_RESULT_TARGET_INVALID; + } + } + + if (target_node == NULL) { + target_path = + ufdt_node_get_fdt_prop_data_by_name(frag_node, "target-path", NULL); + if (target_path == NULL) { + return OVERLAY_RESULT_MISSING_TARGET; + } + + target_node = ufdt_get_node_by_path(tree, target_path); + if (target_node == NULL) { + dto_error("failed to find target-path %s\n", target_path); + return OVERLAY_RESULT_TARGET_PATH_INVALID; + } + } + + 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; + } + + int err = ufdt_overlay_node(target_node, overlay_node); + + if (err < 0) { + dto_error("failed to overlay node %s to target %s\n", name_of(overlay_node), + name_of(target_node)); + return OVERLAY_RESULT_MERGE_FAIL; + } + + return OVERLAY_RESULT_OK; +} + +/* + * Applies all fragments to the main_tree. + */ +static int ufdt_overlay_apply_fragments(struct ufdt *main_tree, + struct ufdt *overlay_tree) { + enum overlay_result err; + struct ufdt_node **it; + /* + * This loop may iterate to subnodes that's not a fragment node. + * In such case, ufdt_apply_fragment would fail with return value = -1. + */ + for_each_node(it, overlay_tree->root) { + err = ufdt_apply_fragment(main_tree, *it); + if (err == OVERLAY_RESULT_MERGE_FAIL) { + return -1; + } + } + return 0; +} + +/* END of applying fragments. */ + +/* + * Since the overlay_tree will be "merged" into the main_tree, some + * references (e.g., phandle values that acts as an unique ID) need to be + * updated so it won't lead to collision that different nodes have the same + * phandle value. + * + * Two things need to be done: + * + * 1. ufdt_try_increase_phandle() + * Update phandle (an unique integer ID of a node in the device tree) of each + * node in the overlay_tree. To achieve this, we simply increase each phandle + * values in the overlay_tree by the max phandle value of the main_tree. + * + * 2. ufdt_overlay_do_local_fixups() + * If there are some reference in the overlay_tree that references nodes + * inside the overlay_tree, we have to modify the reference value (address of + * the referenced node: phandle) so that it corresponds to the right node inside + * the overlay_tree. Where the reference exists is kept in __local_fixups__ node + * in the overlay_tree. + */ + +/* BEGIN of updating local references (phandle values) in the overlay ufdt. */ + +/* + * local fixups + */ +static int ufdt_local_fixup_prop(struct ufdt_node *target_prop_node, + struct ufdt_node *local_fixup_prop_node, + uint32_t phandle_offset) { + /* + * prop_offsets_ptr should be a list of fdt32_t. + * <offset0 offset1 offset2 ...> + */ + char *prop_offsets_ptr; + int len = 0; + prop_offsets_ptr = ufdt_node_get_fdt_prop_data(local_fixup_prop_node, &len); + + char *prop_data; + int target_length = 0; + + prop_data = ufdt_node_get_fdt_prop_data(target_prop_node, &target_length); + + if (prop_offsets_ptr == NULL || prop_data == NULL) return -1; + + int i; + for (i = 0; i < len; i += sizeof(fdt32_t)) { + int offset = fdt32_to_cpu(*(fdt32_t *)(prop_offsets_ptr + i)); + if (offset + sizeof(fdt32_t) > (size_t)target_length) return -1; + fdt_increase_u32((prop_data + offset), phandle_offset); + } + return 0; +} + +static int ufdt_local_fixup_node(struct ufdt_node *target_node, + struct ufdt_node *local_fixups_node, + uint32_t phandle_offset) { + if (local_fixups_node == NULL) return 0; + + struct ufdt_node **it_local_fixups; + struct ufdt_node *sub_target_node; + + for_each_prop(it_local_fixups, local_fixups_node) { + sub_target_node = + ufdt_node_get_property_by_name(target_node, name_of(*it_local_fixups)); + + if (sub_target_node != NULL) { + int err = ufdt_local_fixup_prop(sub_target_node, *it_local_fixups, + phandle_offset); + if (err < 0) return -1; + } else { + return -1; + } + } + + for_each_node(it_local_fixups, local_fixups_node) { + sub_target_node = + ufdt_node_get_node_by_path(target_node, name_of(*it_local_fixups)); + if (sub_target_node != NULL) { + int err = ufdt_local_fixup_node(sub_target_node, *it_local_fixups, + phandle_offset); + if (err < 0) return -1; + } else { + return -1; + } + } + + return 0; +} + +/* + * Handle __local_fixups__ node in overlay DTB + * The __local_fixups__ format we expect is + * __local_fixups__ { + * path { + * to { + * local_ref1 = <offset>; + * }; + * }; + * path2 { + * to2 { + * local_ref2 = <offset1 offset2 ...>; + * }; + * }; + * }; + * + * 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) { + 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__"); + + int err = + ufdt_local_fixup_node(overlay_node, local_fixups_node, phandle_offset); + + if (err < 0) return -1; + + return 0; +} + +static int ufdt_overlay_local_ref_update(struct ufdt *main_tree, + struct ufdt *overlay_tree) { + uint32_t phandle_offset = 0; + + phandle_offset = ufdt_get_max_phandle(main_tree); + if (phandle_offset > 0) { + ufdt_try_increase_phandle(overlay_tree, phandle_offset); + } + + int err = ufdt_overlay_do_local_fixups(overlay_tree, phandle_offset); + if (err < 0) { + dto_error("failed to perform local fixups in overlay\n"); + return -1; + } + return 0; +} + +/* END of updating local references (phandle values) in the overlay ufdt. */ + +static int ufdt_overlay_apply(struct ufdt *main_tree, struct ufdt *overlay_tree, + size_t overlay_length) { + if (overlay_length < sizeof(struct fdt_header)) { + dto_error("Overlay_length %zu smaller than header size %zu\n", + overlay_length, sizeof(struct fdt_header)); + return -1; + } + + if (ufdt_overlay_local_ref_update(main_tree, overlay_tree) < 0) { + dto_error("failed to perform local fixups in overlay\n"); + return -1; + } + + if (ufdt_overlay_do_fixups(main_tree, overlay_tree) < 0) { + dto_error("failed to perform fixups in overlay\n"); + return -1; + } + if (ufdt_overlay_apply_fragments(main_tree, overlay_tree) < 0) { + dto_error("failed to apply fragments\n"); + return -1; + } + + return 0; +} + +struct fdt_header *ufdt_install_blob(void *blob, size_t blob_size) { + struct fdt_header *pHeader; + int err; + + dto_debug("ufdt_install_blob (0x%08jx)\n", (uintmax_t)blob); + + if (blob_size < sizeof(struct fdt_header)) { + dto_error("Blob_size %zu smaller than the header size %zu\n", blob_size, + sizeof(struct fdt_header)); + return NULL; + } + + pHeader = (struct fdt_header *)blob; + err = fdt_check_header(pHeader); + if (err < 0) { + if (err == -FDT_ERR_BADVERSION) { + dto_error("incompatible blob version: %d, should be: %d", + fdt_version(pHeader), FDT_LAST_SUPPORTED_VERSION); + + } else { + dto_error("error validating blob: %s", fdt_strerror(err)); + } + return NULL; + } + + return pHeader; +} + +/* +* From Google, based on dt_overlay_apply() logic +* Will dto_malloc a new fdt blob and return it. Will not dto_free parameters. +*/ +struct fdt_header *ufdt_apply_overlay(struct fdt_header *main_fdt_header, + size_t main_fdt_size, + void *overlay_fdtp, + size_t overlay_size) { + size_t out_fdt_size; + + if (main_fdt_header == NULL) { + return NULL; + } + + if (overlay_size < 8 || overlay_size != fdt_totalsize(overlay_fdtp)) { + dto_error("Bad overlay size!\n"); + return NULL; + } + if (main_fdt_size < 8 || main_fdt_size != fdt_totalsize(main_fdt_header)) { + dto_error("Bad fdt size!\n"); + return NULL; + } + + out_fdt_size = fdt_totalsize(main_fdt_header) + overlay_size; + /* It's actually more than enough */ + struct fdt_header *out_fdt_header = dto_malloc(out_fdt_size); + + if (out_fdt_header == NULL) { + dto_error("failed to allocate memory for DTB blob with overlays\n"); + return NULL; + } + + struct ufdt *main_tree, *overlay_tree; + + main_tree = fdt_to_ufdt(main_fdt_header, main_fdt_size); + + overlay_tree = fdt_to_ufdt(overlay_fdtp, overlay_size); + + int err = ufdt_overlay_apply(main_tree, overlay_tree, overlay_size); + if (err < 0) { + goto fail; + } + + err = ufdt_to_fdt(main_tree, out_fdt_header, out_fdt_size); + if (err < 0) { + dto_error("Failed to dump the device tree to out_fdt_header\n"); + goto fail; + } + + ufdt_destruct(main_tree); + ufdt_destruct(overlay_tree); + return out_fdt_header; + +fail: + ufdt_destruct(main_tree); + ufdt_destruct(overlay_tree); + dto_free(out_fdt_header); + return NULL; +} diff --git a/ufdt_util.h b/ufdt_util.h new file mode 100644 index 0000000..ccd7f76 --- /dev/null +++ b/ufdt_util.h @@ -0,0 +1,60 @@ + +#ifndef UFDT_UTIL_H +#define UFDT_UTIL_H + +#include "fdt_internal.h" +#include "ufdt_types.h" + +static const char *tag_name(uint32_t tag) { + switch (tag) { + case FDT_BEGIN_NODE: + return "FDT_BEGIN_NODE"; + case FDT_END_NODE: + return "FDT_END_NODE"; + case FDT_PROP: + return "FDT_PROP"; + case FDT_END: + return "FDT_END"; + } + return ""; +} + +static const char *get_name(void *fdtp, struct ufdt_node *node) { + if (!fdtp || !node) return NULL; + + const struct fdt_node_header *nh; + const struct fdt_property *prop; + + uint32_t tag = tag_of(node); + + switch (tag) { + case FDT_BEGIN_NODE: + nh = (const struct fdt_node_header *)node->fdt_tag_ptr; + return nh->name; + case FDT_PROP: + prop = (const struct fdt_property *)node->fdt_tag_ptr; + return fdt_string(fdtp, fdt32_to_cpu(prop->nameoff)); + default: + return ""; + } +} + +static const void *value_of(const struct ufdt_node *node) { + if (!node) { + dto_error( "Failed to get value since tree or node is NULL\n"); + return NULL; + } + return node->fdt_tag_ptr; +} + +static int get_hash_len(const char *str, int len) { + int res = 0; + for (int i = 0; i < len; i++) { + res = res * HASH_BASE; + res = res + str[i]; + } + return res; +} +static int get_hash(const char *str) { return get_hash_len(str, dto_strlen(str)); } + +#endif /* UFDT_UTIL_H */ |