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

[Clément Léger]

Hi Jack,

On RISC-V builds, we noticed a recent slow down after commit
ddb5cdbafaaa ("kbuild: generate KSYMTAB entries by modpost") was
introduced. We tracked it down to find_nearest_sym() being called a lot
and more specifically since we have a lot of local symbols that are
generated as part of PCREL accesses (even more when building in debug
mode, measured a count of 12964362 symbols in one vmlinux.o).

Without your changes, a typical riscv defconfig build + debug, modpost
took the following amount of time:

$ time scripts/mod/modpost -M -o Module.symvers -T modules.order vmlinux.o
real    4m21,976s
user    4m21,803s
sys     0m0,100s

With your changes:

$ time scripts/mod/modpost -M -o Module.symvers -T modules.order vmlinux.o
real    0m1,077s
user    0m0,980s
sys     0m0,095s

I guess you could further optimize it by allocating a binary tree for
each section since find_nearest_sym() searches for symbols in a specific
section, that would save a few comparisons. Not sure it will be way
faster nor simpler to implement though.

FWIW: Tested-by: Clément Léger <cleger@xxxxxxxxxxxx>

Thanks,

Clément

On 18/09/2023 23:06, Jack Brennen wrote:
> Modify modpost to use binary search for converting addresses back
> into symbol references.  Previously it used linear search.
> 
> This change saves a few seconds of wall time for defconfig builds,
> but can save several minutes on allyesconfigs.
> 
> Before:
> $ make LLVM=1 -j128 allyesconfig vmlinux -s KCFLAGS="-Wno-error"
>         Elapsed (wall clock) time (h:mm:ss or m:ss): 13:30.31
> 
> After:
> $ make LLVM=1 -j128 allyesconfig vmlinux -s KCFLAGS="-Wno-error"
>         Elapsed (wall clock) time (h:mm:ss or m:ss): 11:43.43
> 
> Signed-off-by: Jack Brennen <jbrennen@xxxxxxxxxx>
> Tested-by: Nick Desaulniers <ndesaulniers@xxxxxxxxxx>
> ---
>  scripts/mod/Makefile    |   4 +-
>  scripts/mod/modpost.c   |  60 +----------
>  scripts/mod/modpost.h   |  25 +++++
>  scripts/mod/symsearch.c | 233 ++++++++++++++++++++++++++++++++++++++++
>  4 files changed, 265 insertions(+), 57 deletions(-)
>  create mode 100644 scripts/mod/symsearch.c
> 
> diff --git a/scripts/mod/Makefile b/scripts/mod/Makefile
> index c9e38ad937fd..3c54125eb373 100644
> --- a/scripts/mod/Makefile
> +++ b/scripts/mod/Makefile
> @@ -5,7 +5,7 @@ CFLAGS_REMOVE_empty.o += $(CC_FLAGS_LTO)
>  hostprogs-always-y	+= modpost mk_elfconfig
>  always-y		+= empty.o
>  
> -modpost-objs	:= modpost.o file2alias.o sumversion.o
> +modpost-objs	:= modpost.o file2alias.o sumversion.o symsearch.o
>  
>  devicetable-offsets-file := devicetable-offsets.h
>  
> @@ -16,7 +16,7 @@ targets += $(devicetable-offsets-file) devicetable-offsets.s
>  
>  # dependencies on generated files need to be listed explicitly
>  
> -$(obj)/modpost.o $(obj)/file2alias.o $(obj)/sumversion.o: $(obj)/elfconfig.h
> +$(obj)/modpost.o $(obj)/file2alias.o $(obj)/sumversion.o $(obj)/symsearch.o: $(obj)/elfconfig.h
>  $(obj)/file2alias.o: $(obj)/$(devicetable-offsets-file)
>  
>  quiet_cmd_elfconfig = MKELF   $@
> diff --git a/scripts/mod/modpost.c b/scripts/mod/modpost.c
> index de499dce5265..975f235aca2c 100644
> --- a/scripts/mod/modpost.c
> +++ b/scripts/mod/modpost.c
> @@ -22,7 +22,6 @@
>  #include <errno.h>
>  #include "modpost.h"
>  #include "../../include/linux/license.h"
> -#include "../../include/linux/module_symbol.h"
>  
>  static bool module_enabled;
>  /* Are we using CONFIG_MODVERSIONS? */
> @@ -577,11 +576,14 @@ static int parse_elf(struct elf_info *info, const char *filename)
>  			*p = TO_NATIVE(*p);
>  	}
>  
> +	symsearch_init(info);
> +
>  	return 1;
>  }
>  
>  static void parse_elf_finish(struct elf_info *info)
>  {
> +	symsearch_finish(info);
>  	release_file(info->hdr, info->size);
>  }
>  
> @@ -1039,65 +1041,13 @@ static int secref_whitelist(const char *fromsec, const char *fromsym,
>  	return 1;
>  }
>  
> -/*
> - * If there's no name there, ignore it; likewise, ignore it if it's
> - * one of the magic symbols emitted used by current tools.
> - *
> - * Otherwise if find_symbols_between() returns those symbols, they'll
> - * fail the whitelist tests and cause lots of false alarms ... fixable
> - * only by merging __exit and __init sections into __text, bloating
> - * the kernel (which is especially evil on embedded platforms).
> - */
> -static inline int is_valid_name(struct elf_info *elf, Elf_Sym *sym)
> -{
> -	const char *name = elf->strtab + sym->st_name;
> -
> -	if (!name || !strlen(name))
> -		return 0;
> -	return !is_mapping_symbol(name);
> -}
> -
>  /* Look up the nearest symbol based on the section and the address */
>  static Elf_Sym *find_nearest_sym(struct elf_info *elf, Elf_Addr addr,
>  				 unsigned int secndx, bool allow_negative,
>  				 Elf_Addr min_distance)
>  {
> -	Elf_Sym *sym;
> -	Elf_Sym *near = NULL;
> -	Elf_Addr sym_addr, distance;
> -	bool is_arm = (elf->hdr->e_machine == EM_ARM);
> -
> -	for (sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
> -		if (get_secindex(elf, sym) != secndx)
> -			continue;
> -		if (!is_valid_name(elf, sym))
> -			continue;
> -
> -		sym_addr = sym->st_value;
> -
> -		/*
> -		 * For ARM Thumb instruction, the bit 0 of st_value is set
> -		 * if the symbol is STT_FUNC type. Mask it to get the address.
> -		 */
> -		if (is_arm && ELF_ST_TYPE(sym->st_info) == STT_FUNC)
> -			 sym_addr &= ~1;
> -
> -		if (addr >= sym_addr)
> -			distance = addr - sym_addr;
> -		else if (allow_negative)
> -			distance = sym_addr - addr;
> -		else
> -			continue;
> -
> -		if (distance <= min_distance) {
> -			min_distance = distance;
> -			near = sym;
> -		}
> -
> -		if (min_distance == 0)
> -			break;
> -	}
> -	return near;
> +	return symsearch_find_nearest(elf, addr, secndx,
> +				      allow_negative, min_distance);
>  }
>  
>  static Elf_Sym *find_fromsym(struct elf_info *elf, Elf_Addr addr,
> diff --git a/scripts/mod/modpost.h b/scripts/mod/modpost.h
> index 5f94c2c9f2d9..6413f26fcb6b 100644
> --- a/scripts/mod/modpost.h
> +++ b/scripts/mod/modpost.h
> @@ -10,6 +10,7 @@
>  #include <fcntl.h>
>  #include <unistd.h>
>  #include <elf.h>
> +#include "../../include/linux/module_symbol.h"
>  
>  #include "list.h"
>  #include "elfconfig.h"
> @@ -128,6 +129,8 @@ struct elf_info {
>  	 * take shndx from symtab_shndx_start[N] instead */
>  	Elf32_Word   *symtab_shndx_start;
>  	Elf32_Word   *symtab_shndx_stop;
> +
> +	struct symsearch *symsearch;
>  };
>  
>  /* Accessor for sym->st_shndx, hides ugliness of "64k sections" */
> @@ -154,6 +157,28 @@ static inline unsigned int get_secindex(const struct elf_info *info,
>  	return index;
>  }
>  
> +/*
> + * If there's no name there, ignore it; likewise, ignore it if it's
> + * one of the magic symbols emitted used by current tools.
> + *
> + * Internal symbols created by tools should be ignored by modpost.
> + */
> +static inline int is_valid_name(struct elf_info *elf, Elf_Sym *sym)
> +{
> +	const char *name = elf->strtab + sym->st_name;
> +
> +	if (!name || !strlen(name))
> +		return 0;
> +	return !is_mapping_symbol(name);
> +}
> +
> +/* symsearch.c */
> +void symsearch_init(struct elf_info *elf);
> +void symsearch_finish(struct elf_info *elf);
> +Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr,
> +				unsigned int secndx, bool allow_negative,
> +				Elf_Addr min_distance);
> +
>  /* file2alias.c */
>  void handle_moddevtable(struct module *mod, struct elf_info *info,
>  			Elf_Sym *sym, const char *symname);
> diff --git a/scripts/mod/symsearch.c b/scripts/mod/symsearch.c
> new file mode 100644
> index 000000000000..aab79262512b
> --- /dev/null
> +++ b/scripts/mod/symsearch.c
> @@ -0,0 +1,233 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +/* Helper functions for finding the symbol in an ELF which is "nearest"
> + * to a given address.
> + */
> +
> +#include "modpost.h"
> +
> +/* Struct used for binary search. */
> +struct syminfo {
> +	unsigned int symbol_index;
> +	unsigned int section_index;
> +	Elf_Addr addr;
> +};
> +
> +/* Container used to hold an entire binary search table.
> + * Entries in table are ascending, sorted first by section_index,
> + * then by addr, and last by symbol_index.  The sorting by
> + * symbol_index is used to duplicate the quirks of the prior
> + * find_nearest_sym() function, where exact matches to an address
> + * return the first symtab entry seen, but near misses return the
> + * last symtab entry seen.
> + * The first and last entries of the table are sentinels and their
> + * values only matter in two places:  when we sort the table, and
> + * on lookups, the end sentinel should not have an addr field which
> + * matches its immediate predecessor.  To meet these requirements,
> + * we initialize them to (0,0,0) and (max,max,max), and then after
> + * sorting, we tweak the end sentinel's addr field accordingly.
> + */
> +struct symsearch {
> +	size_t table_size;
> +	struct syminfo table[];
> +};
> +
> +static inline bool is_sym_searchable(struct elf_info *elf, Elf_Sym *sym)
> +{
> +	return is_valid_name(elf, sym) != 0;
> +}
> +
> +static int syminfo_compare(const void *s1, const void *s2)
> +{
> +	const struct syminfo *sym1 = s1;
> +	const struct syminfo *sym2 = s2;
> +
> +	if (sym1->section_index > sym2->section_index)
> +		return 1;
> +	if (sym1->section_index < sym2->section_index)
> +		return -1;
> +	if (sym1->addr > sym2->addr)
> +		return 1;
> +	if (sym1->addr < sym2->addr)
> +		return -1;
> +	if (sym1->symbol_index > sym2->symbol_index)
> +		return 1;
> +	if (sym1->symbol_index < sym2->symbol_index)
> +		return -1;
> +	return 0;
> +}
> +
> +static size_t symbol_count(struct elf_info *elf)
> +{
> +	size_t result = 0;
> +
> +	for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
> +		if (is_sym_searchable(elf, sym))
> +			result++;
> +	}
> +	return result;
> +}
> +
> +/* Populate the search array that we just allocated.
> + * Be slightly paranoid here.  If the ELF file changes during processing,
> + * or if the behavior of is_sym_searchable() changes during processing,
> + * we want to catch it; neither of those is acceptable.
> + */
> +static void symsearch_populate(struct elf_info *elf,
> +			       struct syminfo *table,
> +			       size_t table_size)
> +{
> +	bool is_arm = (elf->hdr->e_machine == EM_ARM);
> +
> +	/* Start sentinel */
> +	if (table_size-- == 0)
> +		fatal("%s: size mismatch\n", __func__);
> +	table->symbol_index = 0;
> +	table->section_index = 0;
> +	table->addr = 0;
> +	table++;
> +
> +	for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
> +		if (is_sym_searchable(elf, sym)) {
> +			if (table_size-- == 0)
> +				fatal("%s: size mismatch\n", __func__);
> +			table->symbol_index = sym - elf->symtab_start;
> +			table->section_index = get_secindex(elf, sym);
> +			table->addr = sym->st_value;
> +
> +			/*
> +			 * For ARM Thumb instruction, the bit 0 of st_value is
> +			 * set if the symbol is STT_FUNC type. Mask it to get
> +			 * the address.
> +			 */
> +			if (is_arm && ELF_ST_TYPE(sym->st_info) == STT_FUNC)
> +				table->addr &= ~1;
> +
> +			table++;
> +		}
> +	}
> +
> +	/* End sentinel; all values are unsigned so -1 wraps to max */
> +	if (table_size != 1)
> +		fatal("%s: size mismatch\n", __func__);
> +	table->symbol_index = -1;
> +	table->section_index = -1;
> +	table->addr = -1;
> +}
> +
> +void symsearch_init(struct elf_info *elf)
> +{
> +	/* +2 here to allocate space for the start and end sentinels */
> +	size_t table_size = symbol_count(elf) + 2;
> +
> +	elf->symsearch = NOFAIL(malloc(
> +					sizeof(struct symsearch) +
> +					sizeof(struct syminfo) * table_size));
> +	elf->symsearch->table_size = table_size;
> +
> +	symsearch_populate(elf, elf->symsearch->table, table_size);
> +	qsort(elf->symsearch->table, table_size,
> +	      sizeof(struct syminfo), syminfo_compare);
> +
> +	/* A bit of paranoia; make sure that the end sentinel's address is
> +	 * different than its predecessor.  Not doing this could cause
> +	 * possible undefined behavior if anybody ever inserts a symbol
> +	 * with section_index and addr both at their max values.
> +	 * Doing this little bit of defensive programming is more efficient
> +	 * than checking for array overruns later.
> +	 */
> +	elf->symsearch->table[table_size - 1].addr =
> +		elf->symsearch->table[table_size - 2].addr + 1;
> +}
> +
> +void symsearch_finish(struct elf_info *elf)
> +{
> +	free(elf->symsearch);
> +	elf->symsearch = NULL;
> +}
> +
> +/* Find the syminfo which is in secndx and "nearest" to addr.
> + * allow_negative: allow returning a symbol whose address is > addr.
> + * min_distance: ignore symbols which are further away than this.
> + *
> + * Returns a nonzero index into the symsearch table for success.
> + * Returns NULL if no legal symbol is found within the requested range.
> + */
> +static size_t symsearch_find_impl(struct elf_info *elf, Elf_Addr addr,
> +				  unsigned int secndx, bool allow_negative,
> +				  Elf_Addr min_distance)
> +{
> +	/* Find the target in the array; it will lie between two elements.
> +	 * Invariant here: table[lo] < target <= table[hi]
> +	 * For the purposes of search, exact hits in the search array are
> +	 * considered greater than the target.	This means that if we do
> +	 * get an exact hit, then once the search terminates, table[hi]
> +	 * will be the exact match which has the lowest symbol index.
> +	 */
> +	struct syminfo *table = elf->symsearch->table;
> +	size_t hi = elf->symsearch->table_size - 1;
> +	size_t lo = 0;
> +	bool hi_is_usable = false;
> +	bool lo_is_usable = false;
> +	Elf_Addr hi_distance = -1;  // max Elf_Addr
> +	Elf_Addr lo_distance = -1;  // max Elf_Addr
> +	Elf_Addr min_distance_lo = min_distance;
> +	Elf_Addr min_distance_hi = allow_negative ? min_distance : 0;
> +
> +	for (;;) {
> +		size_t mid;
> +
> +		mid = lo + (hi - lo) / 2;
> +		if (mid == lo)
> +			break;
> +		if (secndx > table[mid].section_index) {
> +			lo = mid;
> +		} else if (secndx < table[mid].section_index) {
> +			hi = mid;
> +		} else if (addr > table[mid].addr) {
> +			lo = mid;
> +			lo_distance = addr - table[mid].addr;
> +			lo_is_usable = (lo_distance <= min_distance_lo);
> +		} else {
> +			hi = mid;
> +			hi_distance = table[mid].addr - addr;
> +			hi_is_usable = (hi_distance <= min_distance_hi);
> +		}
> +	}
> +
> +	if (hi_is_usable && lo_is_usable) {
> +		lo_is_usable = (lo_distance <= hi_distance);
> +		hi_is_usable = (hi_distance <= lo_distance);
> +	}
> +
> +	if (!hi_is_usable)
> +		return lo_is_usable ? lo : 0;
> +
> +	if (hi_distance == 0)
> +		return hi;
> +
> +	/* Match quirks of existing behavior.  Advance hi to the last
> +	 * matching entry in the search table.	We don't need to worry
> +	 * about running off the end of the array due to the sentinel.
> +	 */
> +	while (table[hi+1].addr == table[hi].addr &&
> +	       table[hi+1].section_index == table[hi].section_index) {
> +		hi++;
> +	}
> +
> +	return (lo_is_usable &&
> +		table[lo].symbol_index > table[hi].symbol_index) ? lo : hi;
> +}
> +
> +Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr,
> +				unsigned int secndx, bool allow_negative,
> +				Elf_Addr min_distance)
> +{
> +	size_t result = symsearch_find_impl(elf, addr, secndx,
> +					    allow_negative, min_distance);
> +
> +	if (result == 0)
> +		return NULL;
> +
> +	return &elf->symtab_start[elf->symsearch->table[result].symbol_index];
> +}