Re: [PATCH bpf-next 1/3] bpf: Propagate scalar ranges through register assignments.

[John Fastabend <john.fastabend@gmail.com>]

Alexei Starovoitov wrote:
> On Wed, Oct 07, 2020 at 04:55:24PM -0700, John Fastabend wrote:
> > John Fastabend wrote:
> > > Alexei Starovoitov wrote:
> > > > From: Alexei Starovoitov <ast@kernel.org>
> > > > 
> > > > The llvm register allocator may use two different registers representing the
> > > > same virtual register. In such case the following pattern can be observed:
> > > > 1047: (bf) r9 = r6
> > > > 1048: (a5) if r6 < 0x1000 goto pc+1
> > > > 1050: ...
> > > > 1051: (a5) if r9 < 0x2 goto pc+66
> > > > 1052: ...
> > > > 1053: (bf) r2 = r9 /* r2 needs to have upper and lower bounds */
> > > > 
> > > > In order to track this information without backtracking allocate ID
> > > > for scalars in a similar way as it's done for find_good_pkt_pointers().
> > > > 
> > > > When the verifier encounters r9 = r6 assignment it will assign the same ID
> > > > to both registers. Later if either register range is narrowed via conditional
> > > > jump propagate the register state into the other register.
> > > > 
> > > > Clear register ID in adjust_reg_min_max_vals() for any alu instruction.
> > > 
> > > Do we also need to clear the register ID on reg0 for CALL ops into a
> > > helper?
> 
> Thank you for asking all those questions. Much appreciate it!
> 
> > > 
> > > Looks like check_helper_call might mark reg0 as a scalar, but I don't
> > > see where it would clear the reg->id? Did I miss it. Either way maybe
> > > a comment here would help make it obvious how CALLs are handled?
> > > 
> > > Thanks,
> > > John
> > 
> > OK sorry for the noise found it right after hitting send. Any call to
> > mark_reg_unknown will zero the id.
> 
> 
> Right. The verifier uses mark_reg_unknown() in lots of places,
> so I figured it doesn't make sense to list them all.

Right.

> 
> > 
> > /* Mark a register as having a completely unknown (scalar) value. */
> > static void __mark_reg_unknown(const struct bpf_verifier_env *env,
> > 			       struct bpf_reg_state *reg)
> > {
> > 	/*
> > 	 * Clear type, id, off, and union(map_ptr, range) and
> > 	 * padding between 'type' and union
> > 	 */
> > 	memset(reg, 0, offsetof(struct bpf_reg_state, var_off));
> 
> Excatly and the comment mentions 'id' too.

Yep.

> 
> > 
> > And check_helper_call() does,
> > 
> > 	/* update return register (already marked as written above) */
> > 	if (fn->ret_type == RET_INTEGER) {
> > 		/* sets type to SCALAR_VALUE */
> > 		mark_reg_unknown(env, regs, BPF_REG_0);
> > 
> > so looks good to me. In the check_func_call() case the if is_global
> > branch will mark_reg_unknown(). The other case only seems to do a
> > clear_caller_saved_regs though. Is that enough?
> 
> clear_caller_saved_regs() -> mark_reg_not_init() -> __mark_reg_unknown().

+1

> 
> I couldn't think of any other case where scalar's ID has to be cleared.
> Any kind of assignment and r0 return do it as well.

How about a zero extending move?

 r1 = r2 <- r1.id = r2.id
 w1 = w1

that will narrow the bounds on r1 but r2 should not be narrowed? So
we need to zero the r1.id I believe. But, I don't see where we
would set r1.id = 0 in this case.

> 
> We can clear id in r6 - r10 when we call a helper, but that's a bit
> paranoid, since the registers are still valid and still equal.
> Like:
> r6 = r7
> call foo
> // after the call
> if r6 > 5 goto
> if r7 < 2 goto
> // here both r6 and r7 will have bounds
> 
> I think it's good for the verifier to support that.
> 
> The other case with calls:
> 
> r1 = r2
> call foo
>   // and now inside the callee
>   if r1 > 5 goto
>   if r2 < 2 goto
>   // here both r1 and r2 will have bounds
> 
> This case will also work.
> 
> Both cases are artificial and the verifier doesn't have to be that
> smart, but it doesn't hurt and I don't think it's worth to restrict.

Agree I don't see any advantage to restrict above. I think adding
the restriction would just make it harder to follow.

> 
> I'll add two synthetic tests for these cases.

Thanks.

> 
> Any other case you can think of ?

Still churning on the above zero extending move. Also I thought
it was a bit odd that this wouldn't work,

 r1 = r2
 r0 = r1
 if r0 < 2 goto ...

then r0.id != r2.id because a new id is generated on the second
mov there. I don't actually care that much because I can't recall
seeing this pattern.

> I think some time in the past you've mentioned that you hit
> exactly this greedy register alloc issue in your cilium programs.
> Is it the case or am I misremembering?

Yes, I hit this a lot actually for whatever reason. Something
about the code I write maybe. It also tends to be inside a loop
so messing with volatiles doesn't help. End result is I get
a handful of small asm blocks to force compiler into generating
code the verifier doesn't trip up on. I was going to add I think
the cover letter understates how much this should help.

I still need to try some of Yonghong's latest patches maybe I'll
push this patch on my stack as well and see how much asm I can
delete.

Thanks.