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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20210820222755.sqtlzframoz7k5cb@treble>
Date:   Fri, 20 Aug 2021 15:27:55 -0700
From:   Josh Poimboeuf <jpoimboe@...hat.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     tglx@...utronix.de, linux-kernel@...r.kernel.org, joro@...tes.org,
        boris.ostrovsky@...cle.com, jgross@...e.com, x86@...nel.org,
        mbenes@...e.com, rostedt@...dmis.org, dvyukov@...gle.com,
        elver@...gle.com, Andi Kleen <andi@...stfloor.org>
Subject: Re: [PATCH v2 02/24] objtool: Introduce CFI hash

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