Searching for duplicate names scales O(n^2) with the number of names
added to a fdt, which can cause a noticable slowdown with larger device
trees and very slow CPU cores.
Add FDT_CREATE_FLAG_FAST that allow the caller to trade fdt size for
speed in the creation process.
Signed-off-by: Nicholas Piggin <npiggin@xxxxxxxxx>
---
libfdt/fdt_sw.c | 26 +++++++++++++++++++-------
libfdt/libfdt.h | 4 +++-
tests/run_tests.sh | 28 +++++++++++++++-------------
tests/sw_tree1.c | 43 +++++++++++++++++++++++++++++++++++--------
4 files changed, 72 insertions(+), 29 deletions(-)
diff --git a/libfdt/fdt_sw.c b/libfdt/fdt_sw.c
index 5811dc1..3a3da07 100644
--- a/libfdt/fdt_sw.c
+++ b/libfdt/fdt_sw.c
@@ -284,18 +284,13 @@ int fdt_end_node(void *fdt)
return 0;
}
-static int fdt_find_add_string_(void *fdt, const char *s)
+static int fdt_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 = 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);
@@ -307,6 +302,19 @@ static int fdt_find_add_string_(void *fdt, const char *s)
return offset;
}
+static int fdt_find_add_string_(void *fdt, const char *s)
+{
+ char *strtab = (char *)fdt + fdt_totalsize(fdt);
+ int strtabsize = fdt_size_dt_strings(fdt);
+ const char *p;
+
+ p = fdt_find_string_(strtab - strtabsize, strtabsize, s);
+ if (p)
+ return p - strtab;
+
+ return fdt_add_string_(fdt, s);
+}
+
int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp)
{
struct fdt_property *prop;
@@ -314,7 +322,11 @@ int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp)
FDT_SW_PROBE_STRUCT(fdt);
- nameoff = fdt_find_add_string_(fdt, name);
+ /* String de-duplication can be slow, _FAST skips it */
+ if (sw_flags(fdt) & FDT_CREATE_FLAG_FAST)
+ nameoff = fdt_add_string_(fdt, name);
+ else
+ nameoff = fdt_find_add_string_(fdt, name);
if (nameoff == 0)
return -FDT_ERR_NOSPACE;
diff --git a/libfdt/libfdt.h b/libfdt/libfdt.h
index c2dee3e..001b989 100644
--- a/libfdt/libfdt.h
+++ b/libfdt/libfdt.h
@@ -1433,7 +1433,9 @@ int fdt_nop_node(void *fdt, int nodeoffset);
/* Sequential write functions */
/**********************************************************************/
-#define FDT_CREATE_FLAGS_ALL 0
+#define FDT_CREATE_FLAG_FAST 0x1 /* Speed creation at the cost of size */
+
+#define FDT_CREATE_FLAGS_ALL (FDT_CREATE_FLAG_FAST)
/**
* fdt_create_with_flags - begin creation of a new fdt
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 489a3d2..3746c43 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -354,19 +354,21 @@ libfdt_tests () {
run_dtc_test -I dts -O dtb -o stringlist.test.dtb stringlist.dts
run_test stringlist stringlist.test.dtb
- # Sequential write tests
- run_test sw_tree1
- tree1_tests sw_tree1.test.dtb
- tree1_tests unfinished_tree1.test.dtb
- run_test dtbs_equal_ordered test_tree1.dtb sw_tree1.test.dtb
- run_test sw_states
-
- # Resizing tests
- for mode in resize realloc newalloc; do
- run_test sw_tree1 $mode
- tree1_tests sw_tree1.test.dtb
- tree1_tests unfinished_tree1.test.dtb
- run_test dtbs_equal_ordered test_tree1.dtb sw_tree1.test.dtb
+ for flags in default fast; do
+ # Sequential write tests
+ run_test sw_tree1 fixed $flags
+ tree1_tests sw_tree1.test.dtb
+ tree1_tests unfinished_tree1.test.dtb
+ run_test dtbs_equal_ordered test_tree1.dtb sw_tree1.test.dtb
+ run_test sw_states
+
+ # Resizing tests
+ for mode in resize realloc newalloc; do
+ run_test sw_tree1 $mode $flags
+ tree1_tests sw_tree1.test.dtb
+ tree1_tests unfinished_tree1.test.dtb
+ run_test dtbs_equal_ordered test_tree1.dtb sw_tree1.test.dtb
+ done
done
# fdt_move tests
diff --git a/tests/sw_tree1.c b/tests/sw_tree1.c
index 2a67c12..ace242d 100644
--- a/tests/sw_tree1.c
+++ b/tests/sw_tree1.c
@@ -114,14 +114,19 @@ int main(int argc, char *argv[])
void *place;
const char place_str[] = "this is a placeholder string\0string2";
int place_len = sizeof(place_str);
+ int create_flags;
test_init(argc, argv);
- if (argc == 1) {
- alloc_mode = FIXED;
- size = SPACE;
- } else if (argc == 2) {
- if (streq(argv[1], "resize")) {
+ alloc_mode = FIXED;
+ size = SPACE;
+ create_flags = 0;
+
+ if (argc == 2 || argc == 3) {
+ if (streq(argv[1], "fixed")) {
+ alloc_mode = FIXED;
+ size = SPACE;
+ } else if (streq(argv[1], "resize")) {
alloc_mode = REALLOC;
size = 0;
} else if (streq(argv[1], "realloc")) {
@@ -140,12 +145,34 @@ int main(int argc, char *argv[])
CONFIG("Bad allocation mode \"%s\" specified",
argv[1]);
}
- } else {
- CONFIG("sw_tree1 <dtb file> [<allocation mode>]");
+ }
+ if (argc == 3) {
+ char *str = argv[2], *saveptr, *tok;
+ bool default_flag = false;
+
+ while ((tok = strtok_r(str, ",", &saveptr)) != NULL) {
+ str = NULL;
+ if (streq(tok, "default")) {
+ default_flag = true;
+ } else if (streq(tok, "fast")) {
+ create_flags |= FDT_CREATE_FLAG_FAST;
+ } else {
+ CONFIG("Bad creation flags \"%s\" specified",
+ argv[2]);
+ }
+ }
+
+ if (default_flag && create_flags != 0)
+ CONFIG("Bad creation flags \"%s\" specified",
+ argv[2]);
+ }
+
+ if (argc > 3) {
+ CONFIG("sw_tree1 [<allocation mode>] [<create flags>]");
}
fdt = xmalloc(size);
- CHECK(fdt_create(fdt, size));
+ CHECK(fdt_create_with_flags(fdt, size, create_flags));
created = true;
--
2.20.1
