Subject: Re: [PATH bpf-next 11/13] bpf: verifier support JMP32

From: Jiong Wang <[email-masked]>
Date: Tue, 08 Jan 2019 15:23:15 +0000

Jakub Kicinski writes:

> On Wed, 19 Dec 2018 17:44:18 -0500, Jiong Wang wrote:
>> Verifier is doing some runtime optimizations based on the extra info
>> conditional jump instruction could offer, especially when the comparison
>> is between constant and register for which case the value range of the
>> register could be improved.
>> 
>>   is_branch_taken/reg_set_min_max/reg_set_min_max_inv
>> 
>> are the three functions that needs updating.
>> 
>> There are some other conditional jump related optimizations but they
>> are with pointer types comparison which JMP32 won't be generated for.
>> 
>> Signed-off-by: Jiong Wang <[email-masked]>
>> ---
>>  kernel/bpf/verifier.c | 178 ++++++++++++++++++++++++++++++++++++++------------
>>  1 file changed, 137 insertions(+), 41 deletions(-)
>> 
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index e0e77ff..3123c91 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -3919,7 +3919,7 @@ static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode)
>>   */
>>  static void reg_set_min_max(struct bpf_reg_state *true_reg,
>>  			    struct bpf_reg_state *false_reg, u64 val,
>> -			    u8 opcode)
>> +			    u8 opcode, bool is_jmp32)
>>  {
>>  	/* If the dst_reg is a pointer, we can't learn anything about its
>>  	 * variable offset from the compare (unless src_reg were a pointer into
>> @@ -3935,45 +3935,69 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
>>  		/* If this is false then we know nothing Jon Snow, but if it is
>>  		 * true then we know for sure.
>>  		 */
>> -		__mark_reg_known(true_reg, val);
>> +		if (is_jmp32)
>> +			true_reg->var_off = tnum_or(true_reg->var_off,
>> +						    tnum_const(val));
>
> These tnum updates look strange, if the jump is 32bit we know the
> bottom bits.  So:
>
> 	tnum.m &= GENMASK(63, 32);
> 	tnum.v = upper_32_bits(tnum.v) | lower_32_bits(val);

Ack.

By the way, I also fixed range deduction for some other operations which
eventually fixed the only regression on bpf_flow.o mentioned in the cover
letter. Now the processed insn number looks in general a consistent win
against either alu32 or default.

Processed insn number
===
LLVM code-gen option   default  alu32  alu32/jmp32  change Vs.  change Vs.
                                                    alu32       default
bpf_lb-DLB_L3.o:       1579     1281   1295         +1.09%      -17.99%
bpf_lb-DLB_L4.o:       2045     1663   1556         -6.43%      -23.91%
bpf_lb-DUNKNOWN.o:     606      513    501          -2.34%      -17.33%
bpf_lxc.o:             85381    103218 84236        -18.39%     -1.34%
bpf_netdev.o:          5246     5809   5200         -10.48%     -0.08%
bpf_overlay.o:         2443     2705   2456         -9.02%      -0.53%

Will included all fixes in v2.

Regards,
Jiong