Nicholas Piggin's on May 7, 2019 4:07 pm:
> David Gibson's on May 7, 2019 10:00 am:
>> 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).
>
> I initially had a bug in the argument parsing, str was not set to
> NULL for strtok, which caused an infinite loop.
>
>>> + 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;
>
> Did you rebuild tests? Is it hanging in sw_tree1 or infinite looping
> in the harness repeatedly invoking sw_tree1?
Sorry for the noise, found the bug in the resize tests. If we run
out of space adding a property, after you already add the name,
we don't undo the name allocation.
Name dedup papers over the test case because it uses the orphan name
and eventually makes room for the property. No dedup fails because it
keeps eating the new space adding the name again.
This patch seems to fix the existing issue, which fixes the no-dedup
hang when its rebased on top.
The fdt_rw I guess has the same issue, maybe less concerning but it
looks like it could be fixed similarly?
Thanks,
Nick
---
libfdt/fdt_sw.c | 22 +++++++++++++++++++---
1 file changed, 19 insertions(+), 3 deletions(-)
diff --git a/libfdt/fdt_sw.c b/libfdt/fdt_sw.c
index 9fa4a94..3b667e1 100644
--- a/libfdt/fdt_sw.c
+++ b/libfdt/fdt_sw.c
@@ -262,7 +262,15 @@ int fdt_end_node(void *fdt)
return 0;
}
-static int fdt_find_add_string_(void *fdt, const char *s)
+static void fdt_del_last_string_(void *fdt, const char *s)
+{
+ int strtabsize = fdt_size_dt_strings(fdt);
+ int len = strlen(s) + 1;
+
+ fdt_set_size_dt_strings(fdt, strtabsize - len);
+}
+
+static int fdt_find_add_string_(void *fdt, const char *s, int *allocated)
{
char *strtab = (char *)fdt + fdt_totalsize(fdt);
const char *p;
@@ -270,11 +278,15 @@ static int fdt_find_add_string_(void *fdt, const char *s)
int len = strlen(s) + 1;
int struct_top, offset;
+ *allocated = 0;
+
p = fdt_find_string_(strtab - strtabsize, strtabsize, s);
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)
@@ -289,16 +301,20 @@ int fdt_property_placeholder(void *fdt, const char *name, int len, void **valp)
{
struct fdt_property *prop;
int nameoff;
+ int allocated;
FDT_SW_PROBE_STRUCT(fdt);
- nameoff = fdt_find_add_string_(fdt, name);
+ nameoff = fdt_find_add_string_(fdt, name, &allocated);
if (nameoff == 0)
return -FDT_ERR_NOSPACE;
prop = fdt_grab_space_(fdt, sizeof(*prop) + FDT_TAGALIGN(len));
- if (! prop)
+ if (! prop) {
+ if (allocated)
+ fdt_del_last_string_(fdt, name);
return -FDT_ERR_NOSPACE;
+ }
prop->tag = cpu_to_fdt32(FDT_PROP);
prop->nameoff = cpu_to_fdt32(nameoff);
--
2.20.1
