Re: [PATCH v2 02/24] objtool: Introduce CFI hash

[Josh Poimboeuf]

On Thu, Jun 24, 2021 at 11:41:01AM +0200, Peter Zijlstra wrote:
> Andi reported that objtool on vmlinux.o consumes more memory than his
> system has, leading to horrific performance.
> 
> This is in part because we keep a struct instruction for every
> instruction in the file in-memory. Shrink struct instruction by
> removing the CFI state (which includes full register state) from it
> and demand allocating it.
> 
> Given most instructions don't actually change CFI state, there's lots
> of repetition there, so add a hash table to find previous CFI
> instances.
> 
> Reduces memory consumption (and runtime) for processing an
> x86_64-allyesconfig:
> 
>   pre:  4:40.84 real,   143.99 user,    44.18 sys,      30624988 mem
>   post: 2:14.61 real,   108.58 user,    25.04 sys,      16396184 mem

Excellent.

> +static struct cfi_state *cfi_alloc(void)
> +{
> +	struct cfi_state *cfi = calloc(sizeof(struct cfi_state), 1);
> +	if (!cfi) {
> +		WARN("calloc failed");
> +		exit(1);
> +	}
> +	nr_cfi++;
> +	init_cfi_state(cfi);
> +	return cfi;
> +}

I'm thinking this should also add it to the hash.  i.e. I don't think
there's a scenario where you'd alloc a cfi and not want to add it to the
hash.  The more sharing the better.

> +
> +struct cfi_state *insn_get_cfi(struct instruction *insn)
> +{
> +	if (!insn->cfip)
> +		insn->cfip = cfi_alloc();
> +
> +	return insn->cfip;
> +}

Call it something like insn_get_or_alloc_cfi()?

Also, the function can be static.

> +static struct cfi_state *cfi_hash_find(struct cfi_state *cfi)
> +{
> +	struct hlist_head *head = &cfi_hash[hash_min(cfi_key(cfi), cfi_bits)];
> +	struct cfi_state *obj;
> +
> +	hlist_for_each_entry(obj, head, hash) {
> +		if (!cficmp(cfi, obj)) {
> +			nr_cfi_cache++;
> +			return obj;
> +		}
> +	}
> +
> +	obj = cfi_alloc();
> +	*obj = *cfi;
> +	hlist_add_head(&obj->hash, head);
> +
> +	return obj;

cfi_hash_find_or_alloc_cfi()?

> @@ -2725,15 +2820,24 @@ static int validate_branch(struct objtoo
>  
>  			if (insn->visited & visited)
>  				return 0;
> -		}
> +		} else
> +			nr_visited++;
>  
>  		if (state.noinstr)
>  			state.instr += insn->instr;
>  
> -		if (insn->hint)
> -			state.cfi = insn->cfi;
> -		else
> -			insn->cfi = state.cfi;
> +		if (insn->hint) {
> +			state.cfi = *insn->cfip;
> +		} else {
> +			/* XXX track if we actually changed state.cfi */

Why would we do that?

> +++ b/tools/objtool/include/objtool/check.h
> @@ -60,9 +60,11 @@ struct instruction {
>  	struct list_head alts;
>  	struct symbol *func;
>  	struct list_head stack_ops;
> -	struct cfi_state cfi;
> +	struct cfi_state *cfip;

Not sure about this rename.  Pointers generally don't need a 'p' postfix.

-- 
Josh