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
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.
And, yes, we should probably make the behaviour consistent for
read-write as well.
--
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
