linux-kernel - Re: [PATCH] scripts/dtc/flattree.c: stringtable

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CA+hkOd6hcGAgmSsSuFdrXQU2p2OSfeuVL2re-dPzKpA5+DNVUg@mail.gmail.com>
Date: Sat, 23 Aug 2025 00:26:06 -0700
From: Alex Tran <alex.t.tran@...il.com>
To: Rob Herring <robh@...nel.org>
Cc: saravanak@...gle.com, devicetree@...r.kernel.org, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] scripts/dtc/flattree.c: stringtable_insert optimization

I didn't take into account the substring cases. Originally I thought
that incrementing by each string in the table would be more efficient
than by each character to reduce iterations but now with checking for
substrings it is more difficult. I could use strstr(haystack, needle)
to detect substrings and get the position on top of the changes I made
but the performance boost would be negligible. I'll drop this patch.

Thanks for the review.

On Fri, Aug 22, 2025 at 6:34 AM Rob Herring <robh@...nel.org> wrote:
>
> On Fri, Aug 22, 2025 at 1:04 AM Alex Tran <alex.t.tran@...il.com> wrote:
> >
> > Increment string by string instead of character by character.
>
> Why? Are you doing something where this provides measurable improvement?
>
> >
> > Signed-off-by: Alex Tran <alex.t.tran@...il.com>
> > ---
> >  scripts/dtc/flattree.c | 4 +---
> >  1 file changed, 1 insertion(+), 3 deletions(-)
>
> This is a copy of upstream dtc. If you want to make changes to dtc,
> you have to submit them upstream.
>
> >
> > diff --git a/scripts/dtc/flattree.c b/scripts/dtc/flattree.c
> > index 1bcd8089c5b9..156ca5da89b2 100644
> > --- a/scripts/dtc/flattree.c
> > +++ b/scripts/dtc/flattree.c
> > @@ -222,9 +222,7 @@ static int stringtable_insert(struct data *d, const char *str)
> >  {
> >         unsigned int i;
> >
> > -       /* FIXME: do this more efficiently? */
> > -
> > -       for (i = 0; i < d->len; i++) {
> > +       for (i = 0; i < d->len; i += strlen(d->val + i) + 1) {
>
> This isn't equivalent. If 'd' was 'foobar' and 'str' was 'bar', then
> before we'd match. Now you don't.
>
> >                 if (streq(str, d->val + i))
> >                         return i;
> >         }
> > --
> > 2.50.1
> >



-- 
Alex Tran
alex.t.tran@...il.com | 408-406-2417