Avoid to re-generate string table from ufdt to fdt
String table contains the strings of all property name in a fdt.
The ufdt_apply_overlay() converts two dtbs from fdt to ufdt,
overlays, and converts merged ufdt to fdt. These operations
shouldn't create new peroperty names, so we can just re-use the
string tables in original dtbs, and just copy them into merged
fdt. This solution can enhance a lot of performance for device
tree overlaying.
To avoid the error that some users could use string offset in
string table, the solution also give a same string offset for
the name properties by ufdt_prop_dict;
Futher, the patch also removed unused header files after
changing algorithm.
Bug: 35255584
Test: ./tests/run_tests.sh
Change-Id: Id422730115531bd20d21117285291bdd860915ff
diff --git a/Android.mk b/Android.mk
index 4b4830f..6a1b3a7 100644
--- a/Android.mk
+++ b/Android.mk
@@ -6,7 +6,7 @@
ufdt_overlay.c \
ufdt_convert.c \
ufdt_node.c \
- ufdt_node_dict.c
+ ufdt_prop_dict.c
###################################################
diff --git a/fdt_internal.h b/fdt_internal.h
deleted file mode 100644
index 4d7ca47..0000000
--- a/fdt_internal.h
+++ /dev/null
@@ -1,160 +0,0 @@
-#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 const char *_fdt_find_string(const char *strtab, int tabsize,
- const char *s) {
- int len = dto_strlen(s) + 1;
- const char *last = strtab + tabsize - len;
- const char *p;
-
- for (p = strtab; p <= last; p++)
- if (dto_memcmp(p, s, len) == 0) return p;
- return NULL;
-}
-
-static int _fdt_find_add_string(void *fdt, const char *s) {
- char *strtab = (char *)fdt + fdt_totalsize(fdt);
- const char *p;
- int strtabsize = fdt_size_dt_strings(fdt);
- int len = dto_strlen(s) + 1;
- int struct_top, offset;
-
- p = _fdt_find_string(strtab - strtabsize, strtabsize, s);
- if (p) return p - strtab;
-
- /* 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_find_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
index 4fc6965..c8e879a 100644
--- a/include/libufdt.h
+++ b/include/libufdt.h
@@ -6,79 +6,6 @@
#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
*/
@@ -95,7 +22,6 @@
/*
* 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);
@@ -214,13 +140,31 @@
struct ufdt *ufdt_construct(void *fdtp);
/*
- * Frees the space occupied by the ufdt, including all ufdt_nodes and
- * ufdt_node_dicts along
+ * Frees the space occupied by the ufdt, including all ufdt_nodes
* with static_phandle_table.
*/
void ufdt_destruct(struct ufdt *tree);
/*
+ * Add a fdt into this ufdt.
+ * Note that this function just add the given fdtp into this ufdt,
+ * and doesn't create any node.
+ *
+ * @return: 0 if success.
+ */
+int ufdt_add_fdt(struct ufdt *tree, void *fdtp);
+
+/*
+ * Calculate the offset in the string tables of the given string.
+ * All string tables will be concatenated in reversed order.
+ *
+ * @return: The offset is a negative number, base on the end position of
+ * all concatenated string tables
+ * Return 0 if not in any string table.
+ */
+int ufdt_get_string_off(const struct ufdt *tree, const char *s);
+
+/*
* Gets the pointer to the ufdt_node in tree with phandle = phandle.
* The function do a binary search in tree->phandle_table.
*
@@ -327,9 +271,6 @@
/*
* 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.
@@ -339,41 +280,17 @@
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().
*
+ * Basically using functions provided by libfdt/fdt_sw.c.
*
* @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);
+int ufdt_to_fdt(const struct ufdt *tree, void *buf, int buf_size);
/*
* prints the entire subtree rooted at *node in form:
diff --git a/include/ufdt_types.h b/include/ufdt_types.h
index a1d8118..01c45b9 100644
--- a/include/ufdt_types.h
+++ b/include/ufdt_types.h
@@ -3,23 +3,10 @@
#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) \
+#define for_each(it, node) \
+ if ((node) != NULL) \
+ for (it = (node)->nodes; it != (node)->nodes + (node)->mem_size; ++it) \
if (*it)
#define for_each_child(it, node) \
@@ -49,12 +36,6 @@
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;
@@ -77,7 +58,10 @@
};
struct ufdt {
- void *fdtp;
+ void **fdtps;
+ int mem_size_fdtps;
+ int num_used_fdtps;
+
struct ufdt_node *root;
struct static_phandle_table phandle_table;
};
diff --git a/ufdt_convert.c b/ufdt_convert.c
index b990c20..07c489e 100644
--- a/ufdt_convert.c
+++ b/ufdt_convert.c
@@ -1,23 +1,94 @@
#include "libufdt.h"
-#include "fdt_internal.h"
-#include "ufdt_util.h"
-
+#include "ufdt_prop_dict.h"
struct ufdt *ufdt_construct(void *fdtp) {
- struct ufdt *res_ufdt = dto_malloc(sizeof(struct ufdt));
- res_ufdt->fdtp = fdtp;
+ /* Inital size is 2, will be exponentially increased when it needed later.
+ (2 -> 4 -> 8 -> ...) */
+ const int DEFAULT_MEM_SIZE_FDTPS = 2;
+
+ void **fdtps = NULL;
+ struct ufdt *res_ufdt = NULL;
+
+ fdtps = (void **)dto_malloc(sizeof(void *) * DEFAULT_MEM_SIZE_FDTPS);
+ if (fdtps == NULL) goto error;
+ fdtps[0] = fdtp;
+
+ res_ufdt = dto_malloc(sizeof(struct ufdt));
+ if (res_ufdt == NULL) goto error;
+
+ res_ufdt->fdtps = fdtps;
+ res_ufdt->mem_size_fdtps = DEFAULT_MEM_SIZE_FDTPS;
+ res_ufdt->num_used_fdtps = (fdtp != NULL ? 1 : 0);
res_ufdt->root = NULL;
return res_ufdt;
+
+error:
+ if (res_ufdt) dto_free(res_ufdt);
+ if (fdtps) dto_free(fdtps);
+
+ return NULL;
}
void ufdt_destruct(struct ufdt *tree) {
+ if (tree == NULL) return;
+
ufdt_node_destruct(tree->root);
+
+ dto_free(tree->fdtps);
dto_free(tree->phandle_table.data);
dto_free(tree);
}
+int ufdt_add_fdt(struct ufdt *tree, void *fdtp) {
+ if (fdtp == NULL) {
+ return -1;
+ }
+
+ int i = tree->num_used_fdtps;
+ if (i >= tree->mem_size_fdtps) {
+ int new_size = tree->mem_size_fdtps * 2;
+ void **new_fdtps = dto_malloc(sizeof(void *) * new_size);
+ if (new_fdtps == NULL) return -1;
+
+ dto_memcpy(new_fdtps, tree->fdtps, sizeof(void *) * tree->mem_size_fdtps);
+ dto_free(tree->fdtps);
+
+ tree->fdtps = new_fdtps;
+ tree->mem_size_fdtps = new_size;
+ }
+
+ tree->fdtps[i] = fdtp;
+ tree->num_used_fdtps = i + 1;
+
+ return 0;
+}
+
+int ufdt_get_string_off(const struct ufdt *tree, const char *s) {
+ /* fdt_create() sets the dt_string_off to the end of fdt buffer,
+ and _ufdt_output_strtab_to_fdt() copy all string tables in reversed order.
+ So, here the return offset value is base on the end of all string buffers,
+ and it should be a minus value. */
+ int res_off = 0;
+ for (int i = 0; i < tree->num_used_fdtps; i++) {
+ void *fdt = tree->fdtps[i];
+ const char *strtab_start = (const char *)fdt + fdt_off_dt_strings(fdt);
+ int strtab_size = fdt_size_dt_strings(fdt);
+ const char *strtab_end = strtab_start + strtab_size;
+
+ /* Check if the string is in the string table */
+ if (s >= strtab_start && s < strtab_end) {
+ res_off += (s - strtab_end);
+ return res_off;
+ }
+
+ res_off -= strtab_size;
+ }
+ /* Can not find the string, return 0 */
+ return 0;
+}
+
static struct ufdt_node *ufdt_new_node(void *fdtp, int node_offset) {
if (fdtp == NULL) {
dto_error("Failed to get new_node because tree is NULL\n");
@@ -72,7 +143,9 @@
return res;
}
-void ufdt_print(struct ufdt *tree) { ufdt_node_print(tree->root, 0); }
+void ufdt_print(struct ufdt *tree) {
+ ufdt_node_print(tree->root, 0);
+}
struct ufdt_node *ufdt_get_node_by_path_len(struct ufdt *tree, const char *path,
int len) {
@@ -241,16 +314,14 @@
}
struct ufdt *fdt_to_ufdt(void *fdtp, size_t fdt_size) {
- (void)(fdt_size); // unused parameter
-
- struct ufdt *res_tree = ufdt_construct(fdtp);
+ (void)(fdt_size); /* unused parameter */
int start_offset = fdt_path_offset(fdtp, "/");
if (start_offset < 0) {
- res_tree->fdtp = NULL;
- return res_tree;
+ return ufdt_construct(NULL);
}
+ struct ufdt *res_tree = ufdt_construct(fdtp);
int end_offset;
int start_tag = fdt_next_tag(fdtp, start_offset, &end_offset);
res_tree->root = fdt_to_ufdt_tree(fdtp, start_offset, &end_offset, start_tag);
@@ -260,30 +331,146 @@
return res_tree;
}
-int ufdt_to_fdt(struct ufdt *tree, void *buf, int buf_size) {
+static int _ufdt_get_property_nameoff(const struct ufdt *tree, const char *name,
+ const struct ufdt_prop_dict *dict) {
+ int res;
+ const struct fdt_property *same_name_prop = ufdt_prop_dict_find(dict, name);
+ if (same_name_prop != NULL) {
+ /* There is a property with same name, just use its string offset */
+ res = fdt32_to_cpu(same_name_prop->nameoff);
+ } else {
+ /* Get the string offset from the string table of the current tree */
+ res = ufdt_get_string_off(tree, name);
+ if (res == 0) {
+ dto_error("Cannot find property name in string table: %s\n", name);
+ return 0;
+ }
+ }
+ return res;
+}
+
+static int _ufdt_output_property_to_fdt(
+ const struct ufdt *tree, void *fdtp,
+ const struct fdt_prop_ufdt_node *prop_node, struct ufdt_prop_dict *dict) {
+ int nameoff = _ufdt_get_property_nameoff(tree, prop_node->name, dict);
+ if (nameoff == 0) return -1;
+
+ int data_len = 0;
+ void *data = ufdt_node_get_fdt_prop_data(&prop_node->parent, &data_len);
+ int aligned_data_len = (data_len + (FDT_TAGSIZE - 1)) & ~(FDT_TAGSIZE - 1);
+
+ int new_propoff = fdt_size_dt_struct(fdtp);
+ int new_prop_size = sizeof(struct fdt_property) + aligned_data_len;
+ struct fdt_property *new_prop =
+ (struct fdt_property *)((char *)fdtp + fdt_off_dt_struct(fdtp) +
+ new_propoff);
+ char *fdt_end = (char *)fdtp + fdt_totalsize(fdtp);
+ if ((char *)new_prop + new_prop_size > fdt_end) {
+ dto_error("Not enough space for adding property.\n");
+ return -1;
+ }
+ fdt_set_size_dt_struct(fdtp, new_propoff + new_prop_size);
+
+ new_prop->tag = cpu_to_fdt32(FDT_PROP);
+ new_prop->nameoff = cpu_to_fdt32(nameoff);
+ new_prop->len = cpu_to_fdt32(data_len);
+ dto_memcpy(new_prop->data, data, data_len);
+
+ ufdt_prop_dict_add(dict, new_prop);
+
+ return 0;
+}
+
+static int _ufdt_output_node_to_fdt(const struct ufdt *tree, void *fdtp,
+ const struct ufdt_node *node,
+ struct ufdt_prop_dict *dict) {
+ uint32_t tag = tag_of(node);
+
+ if (tag == FDT_PROP) {
+ return _ufdt_output_property_to_fdt(
+ tree, fdtp, (const struct fdt_prop_ufdt_node *)node, dict);
+ }
+
+ int err = fdt_begin_node(fdtp, name_of(node));
+ if (err < 0) return -1;
+
+ struct ufdt_node **it;
+ for_each_prop(it, node) {
+ err = _ufdt_output_node_to_fdt(tree, fdtp, *it, dict);
+ if (err < 0) return -1;
+ }
+
+ for_each_node(it, node) {
+ err = _ufdt_output_node_to_fdt(tree, fdtp, *it, dict);
+ if (err < 0) return -1;
+ }
+
+ err = fdt_end_node(fdtp);
+ if (err < 0) return -1;
+
+ return 0;
+}
+
+static int _ufdt_output_strtab_to_fdt(const struct ufdt *tree, void *fdt) {
+ /* Currently, we don't know the final dt_struct size, so we copy all
+ string tables to the end of the target fdt buffer in reversed order.
+ At last, fdt_finish() will adjust dt_string offset */
+ const char *struct_top =
+ (char *)fdt + fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt);
+ char *dest = (char *)fdt + fdt_totalsize(fdt);
+
+ int dest_size = 0;
+ for (int i = 0; i < tree->num_used_fdtps; i++) {
+ void *src_fdt = tree->fdtps[i];
+ const char *src_strtab = (const char *)src_fdt + fdt_off_dt_strings(src_fdt);
+ int strtab_size = fdt_size_dt_strings(src_fdt);
+
+ dest -= strtab_size;
+ if (dest < struct_top) {
+ dto_error("Not enough space for string table.\n");
+ return -1;
+ }
+
+ dto_memcpy(dest, src_strtab, strtab_size);
+
+ dest_size += strtab_size;
+ }
+
+ fdt_set_size_dt_strings(fdt, dest_size);
+
+ return 0;
+}
+
+int ufdt_to_fdt(const struct ufdt *tree, void *buf, int buf_size) {
+ if (tree->num_used_fdtps == 0) return -1;
+
int err;
err = fdt_create(buf, buf_size);
if (err < 0) return -1;
- int n_mem_rsv = fdt_num_mem_rsv(tree->fdtp);
+ /* Here we output the memory reserve map of the ONLY FIRST fdt,
+ to be in compliance with the DTO behavior of libfdt. */
+ int n_mem_rsv = fdt_num_mem_rsv(tree->fdtps[0]);
for (int i = 0; i < n_mem_rsv; i++) {
uint64_t addr, size;
- fdt_get_mem_rsv(tree->fdtp, i, &addr, &size);
+ fdt_get_mem_rsv(tree->fdtps[0], i, &addr, &size);
fdt_add_reservemap_entry(buf, addr, size);
}
err = fdt_finish_reservemap(buf);
if (err < 0) return -1;
- /*
- * Obtains all props for later use because getting them from
- * FDT requires complicated manipulation.
- */
- struct ufdt_node_dict all_props = ufdt_node_dict_construct();
- err = output_ufdt_node_to_fdt(tree->root, buf, &all_props);
+ err = _ufdt_output_strtab_to_fdt(tree, buf);
if (err < 0) return -1;
- ufdt_node_dict_destruct(&all_props);
+ struct ufdt_prop_dict dict;
+ err = ufdt_prop_dict_construct(&dict, buf);
+ if (err < 0) return -1;
+
+ err = _ufdt_output_node_to_fdt(tree, buf, tree->root, &dict);
+ if (err < 0) return -1;
+
+ ufdt_prop_dict_destruct(&dict);
err = fdt_finish(buf);
if (err < 0) return -1;
diff --git a/ufdt_node.c b/ufdt_node.c
index 6ff4dc1..5a63df7 100644
--- a/ufdt_node.c
+++ b/ufdt_node.c
@@ -1,6 +1,4 @@
#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;
@@ -23,11 +21,12 @@
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) {
+ const struct fdt_property *prop = (const struct fdt_property *)fdt_tag_ptr;
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);
+ res->name = fdt_string(fdtp, fdt32_to_cpu(prop->nameoff));
return (struct ufdt_node *)res;
} else {
struct fdt_node_ufdt_node *res = dto_malloc(sizeof(struct fdt_node_ufdt_node));
@@ -192,66 +191,6 @@
* 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) {
diff --git a/ufdt_node_dict.c b/ufdt_node_dict.c
deleted file mode 100644
index 448bc49..0000000
--- a/ufdt_node_dict.c
+++ /dev/null
@@ -1,178 +0,0 @@
-
-#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
index 05f949f..d6e250e 100644
--- a/ufdt_overlay.c
+++ b/ufdt_overlay.c
@@ -540,8 +540,24 @@
/* END of updating local references (phandle values) in the overlay ufdt. */
+static int _ufdt_overlay_fdtps(struct ufdt *main_tree,
+ const struct ufdt *overlay_tree) {
+ for (int i = 0; i < overlay_tree->num_used_fdtps; i++) {
+ void *fdt = overlay_tree->fdtps[i];
+ if (ufdt_add_fdt(main_tree, fdt) < 0) {
+ return -1;
+ }
+ }
+ return 0;
+}
+
static int ufdt_overlay_apply(struct ufdt *main_tree, struct ufdt *overlay_tree,
size_t overlay_length) {
+ if (_ufdt_overlay_fdtps(main_tree, overlay_tree) < 0) {
+ dto_error("failed to add more fdt into main ufdt tree.\n");
+ return -1;
+ }
+
if (overlay_length < sizeof(struct fdt_header)) {
dto_error("Overlay_length %zu smaller than header size %zu\n",
overlay_length, sizeof(struct fdt_header));
diff --git a/ufdt_prop_dict.c b/ufdt_prop_dict.c
new file mode 100644
index 0000000..93bdfb3
--- /dev/null
+++ b/ufdt_prop_dict.c
@@ -0,0 +1,131 @@
+#include "ufdt_prop_dict.h"
+
+#include "libfdt.h"
+
+#include "libufdt_sysdeps.h"
+
+#define UFDT_PROP_DICT_INIT_SZ 4
+
+/* Empirical values for hash functions. */
+#define HASH_BASE 13131
+
+#define DICT_LIMIT_NUM 2
+#define DICT_LIMIT_DEN 3
+
+static int _ufdt_prop_dict_str_hash(const char *str) {
+ int res = 0;
+
+ for (; *str != '\0'; str++) {
+ res *= HASH_BASE;
+ res += *str;
+ }
+
+ return res;
+}
+
+static const struct fdt_property **_ufdt_prop_dict_find_index_by_name(
+ const struct ufdt_prop_dict *dict, const char *name) {
+ /* size should be 2^k for some k */
+ int hash = _ufdt_prop_dict_str_hash(name);
+ int size = dict->mem_size;
+ int idx = hash & (size - 1);
+ /* If collision, use linear probing to find idx in the hash table */
+ for (int i = 0; i < size; i++) {
+ const struct fdt_property **prop_ptr = &dict->props[idx];
+ const struct fdt_property *prop = *prop_ptr;
+ if (prop == NULL) return prop_ptr;
+
+ const char *prop_name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
+ if (dto_strcmp(prop_name, name) == 0) return prop_ptr;
+
+ idx = (idx + 1) & (size - 1);
+ }
+ return NULL;
+}
+
+static const struct fdt_property **_ufdt_prop_dict_find_index(
+ struct ufdt_prop_dict *dict, const struct fdt_property *prop) {
+ const char *name = fdt_string(dict->fdtp, fdt32_to_cpu(prop->nameoff));
+
+ return _ufdt_prop_dict_find_index_by_name(dict, name);
+}
+
+int _ufdt_prop_dict_construct_int(struct ufdt_prop_dict *dict, void *fdtp,
+ int size) {
+ const size_t entry_size = sizeof(const struct fdt_property *);
+ const struct fdt_property **props =
+ (const struct fdt_property **)dto_malloc(size * entry_size);
+ if (props == NULL) return -1;
+ dto_memset(props, 0, size * entry_size);
+
+ dict->mem_size = size;
+ dict->num_used = 0;
+ dict->fdtp = fdtp;
+ dict->props = props;
+
+ return 0;
+}
+
+int ufdt_prop_dict_construct(struct ufdt_prop_dict *dict, void *fdtp) {
+ return _ufdt_prop_dict_construct_int(dict, fdtp, UFDT_PROP_DICT_INIT_SZ);
+}
+
+void ufdt_prop_dict_destruct(struct ufdt_prop_dict *dict) {
+ if (dict == NULL) return;
+
+ dto_free(dict->props);
+}
+
+static int _ufdt_prop_dict_enlarge_if_needed(struct ufdt_prop_dict *dict) {
+ if (dict == NULL) return -1;
+
+ /* Enlarge if the used number over than DICT_LIMIT_NUM / DICT_LIMIT_DEN */
+ if (dict->num_used * DICT_LIMIT_DEN <= dict->mem_size * DICT_LIMIT_NUM) {
+ return 0;
+ }
+
+ int new_size = dict->mem_size * 2;
+ struct ufdt_prop_dict temp_dict;
+ _ufdt_prop_dict_construct_int(&temp_dict, dict->fdtp, new_size);
+
+ for (int i = 0; i < dict->mem_size; i++) {
+ const struct fdt_property *prop = dict->props[i];
+ if (prop == NULL) continue;
+ const struct fdt_property **new_prop_ptr =
+ _ufdt_prop_dict_find_index(&temp_dict, prop);
+ if (new_prop_ptr == NULL) {
+ dto_error("ufdt_prop_dict: failed to find new index when enlarging.\n");
+ ufdt_prop_dict_destruct(&temp_dict);
+ return -1;
+ }
+ *new_prop_ptr = prop;
+ }
+
+ dto_free(dict->props);
+
+ dict->mem_size = new_size;
+ dict->props = temp_dict.props;
+
+ return 0;
+}
+
+int ufdt_prop_dict_add(struct ufdt_prop_dict *dict,
+ const struct fdt_property *prop) {
+ const struct fdt_property **prop_ptr = _ufdt_prop_dict_find_index(dict, prop);
+ if (prop_ptr == NULL) {
+ dto_error("ufdt_prop_dict: failed to find new index when adding.\n");
+ return -1;
+ }
+
+ if (*prop_ptr == NULL) dict->num_used++;
+ *prop_ptr = prop;
+
+ return _ufdt_prop_dict_enlarge_if_needed(dict);
+}
+
+const struct fdt_property *ufdt_prop_dict_find(const struct ufdt_prop_dict *dict,
+ const char *name) {
+ const struct fdt_property **prop_ptr =
+ _ufdt_prop_dict_find_index_by_name(dict, name);
+ return prop_ptr ? *prop_ptr : NULL;
+}
diff --git a/ufdt_prop_dict.h b/ufdt_prop_dict.h
new file mode 100644
index 0000000..5f0d84f
--- /dev/null
+++ b/ufdt_prop_dict.h
@@ -0,0 +1,47 @@
+#ifndef UFDT_PROP_DICT_H
+#define UFDT_PROP_DICT_H
+
+struct fdt_property;
+
+struct ufdt_prop_dict {
+ int mem_size;
+ int num_used;
+ void *fdtp;
+ const struct fdt_property **props;
+};
+
+/*
+ * Allocates some new spaces and creates a new ufdt_prop_dict.
+ *
+ * @return: a pointer to the newly created ufdt_prop_dict or
+ * NULL if dto_malloc failed
+ */
+int ufdt_prop_dict_construct(struct ufdt_prop_dict *dict, void *fdtp);
+
+/*
+ * Frees all space dto_malloced, not including ufdt_nodes in the table.
+ */
+void ufdt_prop_dict_destruct(struct ufdt_prop_dict *dict);
+
+/*
+ * Adds a fdt_property (as pointer) to the ufdt_prop_dict.
+ * @return: 0 if success
+ * < 0 otherwise
+ *
+ * @Time: O(length of node->name)
+ */
+int ufdt_prop_dict_add(struct ufdt_prop_dict *dict,
+ const struct fdt_property *prop);
+
+/*
+ * Returns the pointer to the fdt_property with name
+ *
+ * @return: a pointer to the node or
+ * NULL if no such node in ufdt_prop_dict with same name.
+ *
+ * @Time: O(len = |name|)
+ */
+const struct fdt_property *ufdt_prop_dict_find(const struct ufdt_prop_dict *dict,
+ const char *name);
+
+#endif
diff --git a/ufdt_util.h b/ufdt_util.h
deleted file mode 100644
index ccd7f76..0000000
--- a/ufdt_util.h
+++ /dev/null
@@ -1,60 +0,0 @@
-
-#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 */
