netdev - Re: [PATCH/RFC v2 bpf-next 05/19] bpf: split read liveness into REG_LIVE_READ64 and REG_LIVE

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: <3A9F4205-577C-4E64-8400-0D476F08459E@netronome.com>
Date:   Thu, 11 Apr 2019 07:13:03 +0100
From:   Jiong Wang <jiong.wang@...ronome.com>
To:     Jakub Kicinski <jakub.kicinski@...ronome.com>
Cc:     Alexei Starovoitov <alexei.starovoitov@...il.com>,
        daniel@...earbox.net, bpf@...r.kernel.org, netdev@...r.kernel.org,
        oss-drivers@...ronome.com
Subject: Re: [PATCH/RFC v2 bpf-next 05/19] bpf: split read liveness into
 REG_LIVE_READ64 and REG_LIVE_READ32


> On 11 Apr 2019, at 03:52, Jakub Kicinski <jakub.kicinski@...ronome.com> wrote:
> 
> On Wed, 10 Apr 2019 20:50:19 +0100, Jiong Wang wrote:
>> Register liveness infrastructure doesn't track register read width at the
>> moment, while the width information will be needed for the later 32-bit
>> safety analysis pass.
>> 
>> This patch take the first step to split read liveness into REG_LIVE_READ64
>> and REG_LIVE_READ32.
>> 
>> Liveness propagation code are updated accordingly. They are taught to
>> understand how to propagate REG_LIVE_READ64 and REG_LIVE_READ32 at the same
>> propagation iteration. For example, "mark_reg_read" now propagate "flags"
>> which could be multiple read bits instead of the single REG_LIVE_READ64.
>> 
>> A write still screen off all width of reads.
>> 
>> Signed-off-by: Jiong Wang <jiong.wang@...ronome.com>
>> ---
>> include/linux/bpf_verifier.h |   8 +--
>> kernel/bpf/verifier.c        | 119 +++++++++++++++++++++++++++++++++++++++----
>> 2 files changed, 113 insertions(+), 14 deletions(-)
>> 
>> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
>> index b3ab61f..fba0ebb 100644
>> --- a/include/linux/bpf_verifier.h
>> +++ b/include/linux/bpf_verifier.h
>> @@ -36,9 +36,11 @@
>>  */
>> enum bpf_reg_liveness {
>> 	REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
>> -	REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
>> -	REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
>> -	REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
>> +	REG_LIVE_READ32 = 0x1, /* reg was read, so we're sensitive to initial value */
>> +	REG_LIVE_READ64 = 0x2, /* likewise, but full 64-bit content matters */
>> +	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
>> +	REG_LIVE_WRITTEN = 0x4, /* reg was written first, screening off later reads */
>> +	REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */
>> };
>> 
>> struct bpf_reg_state {
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index bd30a65..44e4278 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1135,7 +1135,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
>>  */
>> static int mark_reg_read(struct bpf_verifier_env *env,
>> 			 const struct bpf_reg_state *state,
>> -			 struct bpf_reg_state *parent)
>> +			 struct bpf_reg_state *parent, u8 flags)
>> {
>> 	bool writes = parent == state->parent; /* Observe write marks */
>> 	int cnt = 0;
>> @@ -1150,17 +1150,17 @@ static int mark_reg_read(struct bpf_verifier_env *env,
>> 				parent->var_off.value, parent->off);
>> 			return -EFAULT;
>> 		}
>> -		if (parent->live & REG_LIVE_READ)
>> +		if ((parent->live & REG_LIVE_READ) == flags)
>> 			/* The parentage chain never changes and
>> -			 * this parent was already marked as LIVE_READ.
>> +			 * this parent was already marked with all read bits.
> 
> Do we have to propagate all read bits?  Read64 is strictly stronger
> than read32, as long as read64 is set on the parent we should be good?

We should be good, but I doubt there is value to differentiate on this in this
kind of HOT function.
 
> 
>> 			 * There is no need to keep walking the chain again and
>> -			 * keep re-marking all parents as LIVE_READ.
>> +			 * keep re-marking all parents with reads bits in flags.
>> 			 * This case happens when the same register is read
>> 			 * multiple times without writes into it in-between.
>> 			 */
>> 			break;
>> 		/* ... then we depend on parent's value */
>> -		parent->live |= REG_LIVE_READ;
>> +		parent->live |= flags;
>> 		state = parent;
>> 		parent = state->parent;
>> 		writes = true;
> 
>> @@ -6196,12 +6286,19 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env,
>> 				  struct bpf_reg_state *reg,
>> 				  struct bpf_reg_state *parent_reg)
>> {
>> +	u8 parent_bits = parent_reg->live & REG_LIVE_READ;
>> +	u8 bits = reg->live & REG_LIVE_READ;
>> +	u8 bits_diff = parent_bits ^ bits;
>> +	u8 bits_prop = bits_diff & bits;
>> 	int err;
>> 
>> -	if (parent_reg->live & REG_LIVE_READ || !(reg->live & REG_LIVE_READ))
>> +	/* "reg" and "parent_reg" has the same read bits, or the bit doesn't
>> +	 * belong to "reg".
>> +	 */
>> +	if (!bits_diff || !bits_prop)
> 
> bits_prop is a subset of bits_diff, no?  !bits_prop is always true
> if !bits_diff is true, no need to check both.

Bits_prop is a subset of bits_diff WHEN it comes from “reg", we don’t want to
do the propagation when the diff comes from “parent_reg”, so, we need to check
both.

Regards,
Jiong
 
> 
>> 		return 0;
>> 
>> -	err = mark_reg_read(env, reg, parent_reg);
>> +	err = mark_reg_read(env, reg, parent_reg, bits_prop);
>> 	if (err)
>> 		return err;