linux-kernel - Re: [PATCH] modpost: Optimize symbol search from linear to binary search

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAK7LNASwcMf4utu238T6xtJwbnFHSvWntLenve4_KXShOJva6A@mail.gmail.com>
Date:   Tue, 26 Sep 2023 18:56:26 +0900
From:   Masahiro Yamada <masahiroy@...nel.org>
To:     Joe Perches <joe@...ches.com>
Cc:     Jack Brennen <jbrennen@...gle.com>,
        Nathan Chancellor <nathan@...nel.org>,
        Nick Desaulniers <ndesaulniers@...gle.com>,
        Nicolas Schier <nicolas@...sle.eu>, Tom Rix <trix@...hat.com>,
        linux-kernel@...r.kernel.org, linux-kbuild@...r.kernel.org,
        llvm@...ts.linux.dev, maskray@...gle.com, cleger@...osinc.com,
        kernel-team@...roid.com
Subject: Re: [PATCH] modpost: Optimize symbol search from linear to binary search

On Tue, Sep 26, 2023 at 4:24 PM Joe Perches <joe@...ches.com> wrote:
>
> On Tue, 2023-09-26 at 15:46 +0900, Masahiro Yamada wrote:
> > On Tue, Sep 26, 2023 at 5:59 AM Jack Brennen <jbrennen@...gle.com> wrote:
> >
> > > +Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr,
> > > +                               unsigned int secndx, bool allow_negative,
> > > +                               Elf_Addr min_distance)
> > > +{
> > > +       size_t hi = elf->symsearch->table_size;
> > > +       size_t lo = 0;
> > > +       struct syminfo *table = elf->symsearch->table;
> > > +       struct syminfo target;
> > > +
> > > +       target.addr = addr;
> > > +       target.section_index = secndx;
> > > +       target.symbol_index = ~0;  /* compares greater than any actual index */
> > > +       while (hi > lo) {
> > > +               size_t mid = lo + (hi-lo)/2;   /* Avoids potential overflow */
> > > +
> > > +               if (syminfo_compare(&table[mid], &target) > 0)
> > > +                       hi = mid;
> > > +               else
> > > +                       lo = mid+1;
> >
> > My preference is "low = mid + 1" over "low = mid+1"
> >
> > Documentation/process/coding-style.rst suggests spaces
> > around binary operators.
> >
> > "
> > Use one space around (on each side of) most binary and ternary operators,
> > such as any of these::
> >
> >         =  +  -  <  >  *  /  %  |  &  ^  <=  >=  ==  !=  ?  :
> > "
> >
> > I can see the corresponding line in the checkpatch tool:
> >
> > https://github.com/torvalds/linux/blob/v6.5/scripts/checkpatch.pl#L5330
> >
> >
> > I wonder why the checkpatch did not detect it.
> >
> > Maybe, Joe Perches may know the reason.
>
> checkpatch requires --strict to emit that message.
>




Ah, now I see it.  I learned a new thing today.



CHECK: spaces preferred around that '+' (ctx:VxV)
#466: FILE: scripts/mod/symsearch.c:172:
+ lo = mid+1;
          ^







--
Best Regards
Masahiro Yamada