On Mon, May 06, 2019 at 08:13:59PM +1000, Nicholas Piggin wrote:
> 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@xxxxxxxxx>
LGTM, but something's clearly wrong: the nodedup testcases, far from
being faster, wedge indefinitely for me (x86 Fedora 30 host).
> ---
> libfdt/fdt_sw.c | 26 +++++++++++++++++++-------
> libfdt/libfdt.h | 8 +++++++-
> tests/run_tests.sh | 28 +++++++++++++++-------------
> tests/sw_tree1.c | 45 +++++++++++++++++++++++++++++++++++++--------
> 4 files changed, 78 insertions(+), 29 deletions(-)
>
> diff --git a/libfdt/fdt_sw.c b/libfdt/fdt_sw.c
> index 5811dc1..8ad1667 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, _NO_NAME_DEDUP skips it */
> + if (sw_flags(fdt) & FDT_CREATE_FLAG_NO_NAME_DEDUP)
> + 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..0684ec2 100644
> --- a/libfdt/libfdt.h
> +++ b/libfdt/libfdt.h
> @@ -1433,7 +1433,13 @@ int fdt_nop_node(void *fdt, int nodeoffset);
> /* Sequential write functions */
> /**********************************************************************/
>
> -#define FDT_CREATE_FLAGS_ALL 0
> +/* fdt_create_with_flags flags */
> +#define FDT_CREATE_FLAG_NO_NAME_DEDUP 0x1
> + /* FDT_CREATE_FLAG_NO_NAME_DEDUP: Do not try to de-duplicate property
> + * names in the fdt. This can result in faster creation times, but
> + * a larger fdt. */
> +
> +#define FDT_CREATE_FLAGS_ALL (FDT_CREATE_FLAG_NO_NAME_DEDUP)
>
> /**
> * fdt_create_with_flags - begin creation of a new fdt
> diff --git a/tests/run_tests.sh b/tests/run_tests.sh
> index 489a3d2..52c7399 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;
>
--
David Gibson | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_
| _way_ _around_!
http://www.ozlabs.org/~dgibson
Attachment:
signature.asc
Description: PGP signature
