Re: [RFC][PATCH 07/16] objtool: Optimize find_section_by_index()

[Josh Poimboeuf]

On Thu, Mar 12, 2020 at 02:41:14PM +0100, Peter Zijlstra wrote:
> In order to avoid a linear search (over 20k entries), add an
> section_hash to the elf object.
> 
> This reduces objtool on vmlinux.o from a few minutes to around 45
> seconds.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>
> ---
>  tools/objtool/elf.c |    7 ++++++-
>  tools/objtool/elf.h |    2 ++
>  2 files changed, 8 insertions(+), 1 deletion(-)
> 
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -38,7 +38,7 @@ static struct section *find_section_by_i
>  {
>  	struct section *sec;
>  
> -	list_for_each_entry(sec, &elf->sections, list)
> +	hash_for_each_possible(elf->section_hash, sec, hash, idx)
>  		if (sec->idx == idx)
>  			return sec;
>  
> @@ -191,6 +191,8 @@ static int read_sections(struct elf *elf
>  			}
>  		}
>  		sec->len = sec->sh.sh_size;
> +
> +		hash_add(elf->section_hash, &sec->hash, sec->idx);

Can you move the

  list_add_tail(&sec->list, &elf->sections);

down here so they're done at the same place?

>  	}
>  
>  	if (stats)
> @@ -430,6 +432,7 @@ struct elf *elf_read(const char *name, i
>  	memset(elf, 0, sizeof(*elf));
>  
>  	hash_init(elf->symbol_hash);
> +	hash_init(elf->section_hash);
>  	INIT_LIST_HEAD(&elf->sections);
>  
>  	elf->fd = open(name, flags);
> @@ -570,6 +573,8 @@ struct section *elf_create_section(struc
>  	shstrtab->len += strlen(name) + 1;
>  	shstrtab->changed = true;
>  
> +	hash_add(elf->section_hash, &sec->hash, sec->idx);
> +
>  	return sec;
>  }

Ditto

-- 
Josh