Re: [PATCH v2 2/2] objtool: optimize add_dead_ends for split sections

[Kees Cook]

On Tue, Apr 21, 2020 at 03:08:43PM -0700, Sami Tolvanen wrote:
> Instead of iterating through all instructions to find the last
> instruction each time .rela.discard.(un)reachable points beyond the
> section, use find_insn to locate the last instruction by looking at
> the last bytes of the section instead.
> 
> Suggested-by: Josh Poimboeuf <jpoimboe@xxxxxxxxxx>
> Signed-off-by: Sami Tolvanen <samitolvanen@xxxxxxxxxx>

Reviewed-by: Kees Cook <keescook@xxxxxxxxxxxx>

-Kees

> ---
>  tools/objtool/check.c | 36 +++++++++++++++++-------------------
>  1 file changed, 17 insertions(+), 19 deletions(-)
> 
> diff --git a/tools/objtool/check.c b/tools/objtool/check.c
> index 4b170fd08a28..4f1d405420a4 100644
> --- a/tools/objtool/check.c
> +++ b/tools/objtool/check.c
> @@ -303,6 +303,19 @@ static int decode_instructions(struct objtool_file *file)
>  	return ret;
>  }
>  
> +static struct instruction *find_last_insn(struct objtool_file *file,
> +					  struct section *sec)
> +{
> +	struct instruction *insn = NULL;
> +	unsigned int offset;
> +	unsigned int end = (sec->len > 10) ? sec->len - 10 : 0;
> +
> +	for (offset = sec->len - 1; offset >= end && !insn; offset--)
> +		insn = find_insn(file, sec, offset);
> +
> +	return insn;
> +}
> +
>  /*
>   * Mark "ud2" instructions and manually annotated dead ends.
>   */
> @@ -311,7 +324,6 @@ static int add_dead_ends(struct objtool_file *file)
>  	struct section *sec;
>  	struct rela *rela;
>  	struct instruction *insn;
> -	bool found;
>  
>  	/*
>  	 * By default, "ud2" is a dead end unless otherwise annotated, because
> @@ -337,15 +349,8 @@ static int add_dead_ends(struct objtool_file *file)
>  		if (insn)
>  			insn = list_prev_entry(insn, list);
>  		else if (rela->addend == rela->sym->sec->len) {
> -			found = false;
> -			list_for_each_entry_reverse(insn, &file->insn_list, list) {
> -				if (insn->sec == rela->sym->sec) {
> -					found = true;
> -					break;
> -				}
> -			}
> -
> -			if (!found) {
> +			insn = find_last_insn(file, rela->sym->sec);
> +			if (!insn) {
>  				WARN("can't find unreachable insn at %s+0x%x",
>  				     rela->sym->sec->name, rela->addend);
>  				return -1;
> @@ -379,15 +384,8 @@ static int add_dead_ends(struct objtool_file *file)
>  		if (insn)
>  			insn = list_prev_entry(insn, list);
>  		else if (rela->addend == rela->sym->sec->len) {
> -			found = false;
> -			list_for_each_entry_reverse(insn, &file->insn_list, list) {
> -				if (insn->sec == rela->sym->sec) {
> -					found = true;
> -					break;
> -				}
> -			}
> -
> -			if (!found) {
> +			insn = find_last_insn(file, rela->sym->sec);
> +			if (!insn) {
>  				WARN("can't find reachable insn at %s+0x%x",
>  				     rela->sym->sec->name, rela->addend);
>  				return -1;
> -- 
> 2.26.1.301.g55bc3eb7cb9-goog
> 

-- 
Kees Cook