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

[Masahiro Yamada]

On Tue, Sep 26, 2023 at 5:59 AM Jack Brennen <jbrennen@xxxxxxxxxx> 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.







My previous question about the type inconsistency
was not addressed.

syminfo::symbol_index is unsigned int
symsearch::table_size is size_t


If we encountered a situation where size_t is
really needed for the table_size
(that is, the number of entries does not fit in 32-bit),
syminfo::symbol_index would wrap around.

So, there is no point to use size_t for one,
and (unsigned int) for the other.


In my opinion, (unsigned int) would be enough to count
numbers or index here.

size_t might be 32-bit or 64-bit depending
on the build host architecture.
That is not related to the target architecture
of ELF being processed.




--
Best Regards
Masahiro Yamada