From b00040b273a1d72676c80f34a7a4ca6e857ed32b Mon Sep 17 00:00:00 2001 From: Nicholas Piggin Date: Thu, 9 May 2019 19:41:22 +1000 Subject: 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 Message-Id: <20190509094122.834-4-npiggin@gmail.com> Signed-off-by: David Gibson --- cpukit/dtc/libfdt/fdt_sw.c | 39 ++++++++++++++++++++++++++------------- cpukit/include/libfdt.h | 8 +++++++- 2 files changed, 33 insertions(+), 14 deletions(-) diff --git a/cpukit/dtc/libfdt/fdt_sw.c b/cpukit/dtc/libfdt/fdt_sw.c index ba05868845..e773157d0f 100644 --- a/cpukit/dtc/libfdt/fdt_sw.c +++ b/cpukit/dtc/libfdt/fdt_sw.c @@ -284,6 +284,23 @@ int fdt_end_node(void *fdt) return 0; } +static int fdt_add_string_(void *fdt, const char *s) +{ + char *strtab = (char *)fdt + fdt_totalsize(fdt); + int strtabsize = fdt_size_dt_strings(fdt); + int len = strlen(s) + 1; + int struct_top, offset; + + offset = -strtabsize - len; + struct_top = fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt); + if (fdt_totalsize(fdt) + offset < struct_top) + return 0; /* no more room :( */ + + memcpy(strtab + offset, s, len); + fdt_set_size_dt_strings(fdt, strtabsize + len); + return offset; +} + /* Must only be used to roll back in case of error */ static void fdt_del_last_string_(void *fdt, const char *s) { @@ -296,10 +313,8 @@ static void fdt_del_last_string_(void *fdt, const char *s) static int fdt_find_add_string_(void *fdt, const char *s, int *allocated) { 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; + const char *p; *allocated = 0; @@ -307,17 +322,9 @@ static int fdt_find_add_string_(void *fdt, const char *s, int *allocated) if (p) return p - strtab; - /* Add it */ *allocated = 1; - offset = -strtabsize - len; - struct_top = fdt_off_dt_struct(fdt) + fdt_size_dt_struct(fdt); - if (fdt_totalsize(fdt) + offset < struct_top) - return 0; /* no more room :( */ - - memcpy(strtab + offset, s, len); - fdt_set_size_dt_strings(fdt, strtabsize + len); - return offset; + return fdt_add_string_(fdt, s); } int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp) @@ -328,7 +335,13 @@ 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, &allocated); + /* String de-duplication can be slow, _NO_NAME_DEDUP skips it */ + if (sw_flags(fdt) & FDT_CREATE_FLAG_NO_NAME_DEDUP) { + allocated = 1; + nameoff = fdt_add_string_(fdt, name); + } else { + nameoff = fdt_find_add_string_(fdt, name, &allocated); + } if (nameoff == 0) return -FDT_ERR_NOSPACE; diff --git a/cpukit/include/libfdt.h b/cpukit/include/libfdt.h index c2dee3eaa6..0684ec22ed 100644 --- a/cpukit/include/libfdt.h +++ b/cpukit/include/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 -- cgit v1.2.3