libfdt: Add FDT_CREATE_FLAG_NO_NAME_DEDUP flag that trades size for speed

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_NO_NAME_DEDUP that allow the caller to trade fdt size
for speed in the creation process.

Signed-off-by: Nicholas Piggin <npiggin@gmail.com>
Message-Id: <20190509094122.834-4-npiggin@gmail.com>
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>

2 files changed, 52 insertions, 21 deletions

diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index d350c3d..07c3489 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 no_name_dedup; 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..08b39b3 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,36 @@ 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, "no_name_dedup")) {
+				create_flags |= FDT_CREATE_FLAG_NO_NAME_DEDUP;
+			} else if (streq(tok, "bad")) {
+				create_flags |= 0xffffffff;
+			} 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;