On Tue, Apr 30, 2019 at 06:15:35PM +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_FAST that allow the caller to trade fdt size for
> speed in the creation process.
"FAST" is terribly non-specific, I'd prefer to be explict about what
this does. Maybe "SKIP_NAME_DEDUP"?
>
> Signed-off-by: Nicholas Piggin <npiggin@xxxxxxxxx>
> ---
> libfdt/fdt_sw.c | 26 +++++++++++++++++++-------
> libfdt/libfdt.h | 2 ++
> tests/run_tests.sh | 28 +++++++++++++++-------------
> tests/sw_tree1.c | 43 +++++++++++++++++++++++++++++++++++--------
> 4 files changed, 71 insertions(+), 28 deletions(-)
>
> diff --git a/libfdt/fdt_sw.c b/libfdt/fdt_sw.c
> index f162579..6ead5c2 100644
> --- a/libfdt/fdt_sw.c
> +++ b/libfdt/fdt_sw.c
> @@ -281,18 +281,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);
> @@ -304,6 +299,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;
> @@ -311,7 +319,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 (fdt_sw_create_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 574904d..4a1c94d 100644
> --- a/libfdt/libfdt.h
> +++ b/libfdt/libfdt.h
> @@ -1429,6 +1429,8 @@ int fdt_nop_node(void *fdt, int nodeoffset);
> /* Sequential write functions */
> /**********************************************************************/
>
> +#define FDT_CREATE_FLAG_FAST 0x1 /* Speed creation at the cost of size */
> +
> int fdt_create(void *buf, int bufsize);
> int fdt_create_with_flags(void *buf, int bufsize, uint32_t flags);
> int fdt_resize(void *fdt, void *buf, int bufsize);
> 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;
>
--
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
