On 6/13/19 2:46 PM, Andrii Nakryiko wrote:
> On Thu, Jun 13, 2019 at 9:50 AM Alexei Starovoitov <ast@xxxxxxxxxx> wrote:
>>
>> Compilers often spill induction variables into the stack,
>> hence it is necessary for the verifier to track scalar values
>> of the registers through stack slots.
>>
>> Also few bpf programs were incorrectly rejected in the past,
>> since the verifier was not able to track such constants while
>> they were used to compute offsets into packet headers.
>>
>> Tracking constants through the stack significantly decreases
>> the chances of state pruning, since two different constants
>> are considered to be different by state equivalency.
>> End result that cilium tests suffer serious degradation in the number
>> of states processed and corresponding verification time increase.
>>
>> before after
>> bpf_lb-DLB_L3.o 1838 6441
>> bpf_lb-DLB_L4.o 3218 5908
>> bpf_lb-DUNKNOWN.o 1064 1064
>> bpf_lxc-DDROP_ALL.o 26935 93790
>> bpf_lxc-DUNKNOWN.o 34439 123886
>> bpf_netdev.o 9721 31413
>> bpf_overlay.o 6184 18561
>> bpf_lxc_jit.o 39389 359445
>>
>> After further debugging turned out that cillium progs are
>> getting hurt by clang due to the same constant tracking issue.
>> Newer clang generates better code by spilling less to the stack.
>> Instead it keeps more constants in the registers which
>> hurts state pruning since the verifier already tracks constants
>> in the registers:
>> old clang new clang
>> (no spill/fill tracking introduced by this patch)
>> bpf_lb-DLB_L3.o 1838 1923
>> bpf_lb-DLB_L4.o 3218 3077
>> bpf_lb-DUNKNOWN.o 1064 1062
>> bpf_lxc-DDROP_ALL.o 26935 166729
>> bpf_lxc-DUNKNOWN.o 34439 174607
>> bpf_netdev.o 9721 8407
>> bpf_overlay.o 6184 5420
>> bpf_lcx_jit.o 39389 39389
>>
>> The final table is depressing:
>> old clang old clang new clang new clang
>> const spill/fill const spill/fill
>> bpf_lb-DLB_L3.o 1838 6441 1923 8128
>> bpf_lb-DLB_L4.o 3218 5908 3077 6707
>> bpf_lb-DUNKNOWN.o 1064 1064 1062 1062
>> bpf_lxc-DDROP_ALL.o 26935 93790 166729 380712
>> bpf_lxc-DUNKNOWN.o 34439 123886 174607 440652
>> bpf_netdev.o 9721 31413 8407 31904
>> bpf_overlay.o 6184 18561 5420 23569
>> bpf_lxc_jit.o 39389 359445 39389 359445
>>
>> Tracking constants in the registers hurts state pruning already.
>> Adding tracking of constants through stack hurts pruning even more.
>> The later patch address this general constant tracking issue
>> with coarse/precise logic.
>>
>> Signed-off-by: Alexei Starovoitov <ast@xxxxxxxxxx>
>> ---
>> kernel/bpf/verifier.c | 67 +++++++++++++++++++++++++++++++++----------
>> 1 file changed, 52 insertions(+), 15 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 8d1786357a09..a21bafd7d931 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1378,6 +1378,11 @@ static bool register_is_null(struct bpf_reg_state *reg)
>> return reg->type == SCALAR_VALUE && tnum_equals_const(reg->var_off, 0);
>> }
>>
>> +static bool register_is_const(struct bpf_reg_state *reg)
>> +{
>> + return reg->type == SCALAR_VALUE && tnum_is_const(reg->var_off);
>> +}
>> +
>> /* check_stack_read/write functions track spill/fill of registers,
>> * stack boundary and alignment are checked in check_mem_access()
>> */
>> @@ -1387,7 +1392,7 @@ static int check_stack_write(struct bpf_verifier_env *env,
>> {
>> struct bpf_func_state *cur; /* state of the current function */
>> int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err;
>> - enum bpf_reg_type type;
>> + struct bpf_reg_state *reg = NULL;
>>
>> err = realloc_func_state(state, round_up(slot + 1, BPF_REG_SIZE),
>> state->acquired_refs, true);
>> @@ -1404,27 +1409,37 @@ static int check_stack_write(struct bpf_verifier_env *env,
>> }
>>
>> cur = env->cur_state->frame[env->cur_state->curframe];
>> - if (value_regno >= 0 &&
>> - is_spillable_regtype((type = cur->regs[value_regno].type))) {
>> + if (value_regno >= 0)
>> + reg = &cur->regs[value_regno];
>>
>> + if (reg && size == BPF_REG_SIZE && register_is_const(reg) &&
>> + !tnum_equals_const(reg->var_off, 0)) {
>
> nit: using !register_is_null(reg) check instead would be a good
> counterpart to STACK_ZERO logic below.
I wasn't sure that compiler can optimize two == scalar checks into one.
>> + goto save_reg_state;
>
> This goto business is ugly, why not extracting register spilling logic
> into separate function?
>
>> + } else if (reg && is_spillable_regtype(reg->type)) {
>> /* register containing pointer is being spilled into stack */
>> if (size != BPF_REG_SIZE) {
>> + verbose_linfo(env, insn_idx, "; ");
>> verbose(env, "invalid size of register spill\n");
>> return -EACCES;
>> }
>>
>> - if (state != cur && type == PTR_TO_STACK) {
>> + if (state != cur && reg->type == PTR_TO_STACK) {
>> verbose(env, "cannot spill pointers to stack into stack frame of the caller\n");
>> return -EINVAL;
>> }
>>
>> - /* save register state */
>> - state->stack[spi].spilled_ptr = cur->regs[value_regno];
>> - state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
>> + if (!env->allow_ptr_leaks) {
>> + bool sanitize = false;
>>
>> - for (i = 0; i < BPF_REG_SIZE; i++) {
>> - if (state->stack[spi].slot_type[i] == STACK_MISC &&
>> - !env->allow_ptr_leaks) {
>> + if (state->stack[spi].slot_type[0] == STACK_SPILL &&
>> + register_is_const(&state->stack[spi].spilled_ptr))
>> + sanitize = true;
>> + for (i = 0; i < BPF_REG_SIZE; i++)
>> + if (state->stack[spi].slot_type[i] == STACK_MISC) {
>> + sanitize = true;
>> + break;
>> + }
>> + if (sanitize) {
>> int *poff = &env->insn_aux_data[insn_idx].sanitize_stack_off;
>> int soff = (-spi - 1) * BPF_REG_SIZE;
>>
>> @@ -1447,8 +1462,14 @@ static int check_stack_write(struct bpf_verifier_env *env,
>> }
>> *poff = soff;
>> }
>> - state->stack[spi].slot_type[i] = STACK_SPILL;
>> }
>> +save_reg_state:
>> + /* save register state */
>> + state->stack[spi].spilled_ptr = *reg;
>> + state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
>> +
>> + for (i = 0; i < BPF_REG_SIZE; i++)
>> + state->stack[spi].slot_type[i] = STACK_SPILL;
>> } else {
>> u8 type = STACK_MISC;
>>
>> @@ -1471,8 +1492,7 @@ static int check_stack_write(struct bpf_verifier_env *env,
>> state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
>>
>> /* when we zero initialize stack slots mark them as such */
>> - if (value_regno >= 0 &&
>> - register_is_null(&cur->regs[value_regno]))
>> + if (reg && register_is_null(reg))
>> type = STACK_ZERO;
>>
>> /* Mark slots affected by this stack write. */
>> @@ -1501,7 +1521,15 @@ static int check_stack_read(struct bpf_verifier_env *env,
>>
>> if (stype[0] == STACK_SPILL) {
>> if (size != BPF_REG_SIZE) {
>> - verbose(env, "invalid size of register spill\n");
>> + if (reg_state->stack[spi].spilled_ptr.type == SCALAR_VALUE) {
>
> spilled_ptr is misleading now, how about renaming to spilled_reg?
not in this set. we can consider in the future,
but I'd rather leave it alone. Too much code churn.
>> + if (value_regno >= 0) {
>> + mark_reg_unknown(env, state->regs, value_regno);
>> + state->regs[value_regno].live |= REG_LIVE_WRITTEN;
>> + }
>> + goto mark_read;
>
> Again, not liking unnecessary gotos. How about this logic:
>
> if (size != BPF_REG_SIZE && reg_state->stack[spi].spilled_ptr.type !=
> SCALAR_VALUE) {
> ... log and return -EACCESS ...
> }
>
> // loop to check STACK_SPILL (it doesn't hurt for SCALAR_VALUE, right?)
it will hurt, since it cannot do so.
> if (value_regno >= 0) {
> if (size != BPF_REG_SIZE)
> mark_reg_unknown(env, state->regs, value_regno);
also not correct.
> else
> state->regs[value_regno] = reg_state->stack[spi].spilled_ptr;
> state->regs[value_regno].live |= REG_LIVE_WRITTEN;
> }
>
> // mark_reg_read here
>
>
> it's more linear and clearly shows that for partial reads of constants
> we set to unknown, otherwise restore state completely.
I don't share this 'dislike of gotos'.
The books that introduced that notion that gotos are somehow bad
and bad programming style are wrong. In my opinion :)
But I'll see how to reduce them in this case.
Probably will do a helper function.
