David Gibson's on May 9, 2019 4:41 pm:
> On Thu, May 09, 2019 at 02:29:07PM +1000, Nicholas Piggin wrote:
>> 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.
>
> Ah! Interesting.
>
>> 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?
>
> I can't remember now if this is just due to an oversight, or if I
> spotted this behaviour but decided it was harmless, since it doesn't
> semantically change the tree (and with de-dup won't blow up either).
>
> It is neater if we rollback all changes on failure though, so I think
> your solution is probably good. The only other way I can really think
Okay.
> of to do it would be to change the no-dedup behaviour to check if
> re-using the *first* thing in the string block, just not scan the
> whole thing, but I think your approach is superior.
Yeah, I'd say it should rarely ever hit outside OOM case, and if we
ask for no dedup, that's what we should get.
> And, yes, we should probably make the behaviour consistent for
> read-write as well.
Sure.
Thanks,
Nick
