| Message ID | 20201006200955.12350-1-alexei.starovoitov@gmail.com |
|---|---|
| Headers | show |
| Series | bpf: Make the verifier recognize llvm register allocation patterns. | expand |
On Tue, Oct 6, 2020 at 7:18 PM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Tue, Oct 06, 2020 at 06:56:14PM -0700, Andrii Nakryiko wrote: > > On Tue, Oct 6, 2020 at 1:14 PM Alexei Starovoitov > > <alexei.starovoitov@gmail.com> 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. > > > > > > Newly allocated register ID is ignored for scalars in regsafe() and doesn't > > > affect state pruning. mark_reg_unknown() also clears the ID. > > > > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > > > --- > > > > I couldn't find the problem with the logic, though it's quite > > non-obvious at times that reg->id will be cleared on BPF_END/BPF_NEG > > and few other operations. But I think naming of this function can be > > improved, see below. > > > > Also, profiler.c is great, but it would still be nice to add selftest > > to test_verifier that will explicitly test the logic in this patch > > the test align.c actualy does the id checking better than I expected. > I'm planning to add more asm tests in the follow up. > ok Acked-by: Andrii Nakryiko <andrii@kernel.org> > > > kernel/bpf/verifier.c | 38 +++++++++++++++++++ > > > .../testing/selftests/bpf/prog_tests/align.c | 16 ++++---- > > > .../bpf/verifier/direct_packet_access.c | 2 +- > > > 3 files changed, 47 insertions(+), 9 deletions(-) > > > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > index 01120acab09a..09e17b483b0b 100644 > > > --- a/kernel/bpf/verifier.c > > > +++ b/kernel/bpf/verifier.c > > > @@ -6432,6 +6432,8 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, > > > src_reg = NULL; > > > if (dst_reg->type != SCALAR_VALUE) > > > ptr_reg = dst_reg; > > > + else > > > + dst_reg->id = 0; > > > if (BPF_SRC(insn->code) == BPF_X) { > > > src_reg = ®s[insn->src_reg]; > > > if (src_reg->type != SCALAR_VALUE) { > > > @@ -6565,6 +6567,8 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > > > /* case: R1 = R2 > > > * copy register state to dest reg > > > */ > > > + if (src_reg->type == SCALAR_VALUE) > > > + src_reg->id = ++env->id_gen; > > > *dst_reg = *src_reg; > > > dst_reg->live |= REG_LIVE_WRITTEN; > > > dst_reg->subreg_def = DEF_NOT_SUBREG; > > > @@ -7365,6 +7369,30 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > > return true; > > > } > > > > > > +static void find_equal_scalars(struct bpf_verifier_state *vstate, > > > + struct bpf_reg_state *known_reg) > > > > this is double-misleading name: > > > > 1) it's not just "find", but also "update" (or rather the purpose of > > this function is specifically to update registers, not find them, as > > we don't really return found register) > > 2) "equal" is not exactly true either. You can have two scalar > > register with exactly the same state, but they might not share ->id. > > So it's less about being equal, rather being "linked" by assignment. > > I don't think I can agree. > We already have find_good_pkt_pointers() that also updates, > so 'find' fits better than 'update'. find_good_pkt_pointers() has similarly confusing name, but sure, consistency rules > 'linked' is also wrong. The regs are exactly equal. > In case of pkt and other pointers two regs will have the same id > as well, but they will not be equal. Here these two scalars are equal > otherwise doing *reg = *known_reg would be wrong. Ok, I guess it also means that "reg->type == SCALAR_VALUE" checks below are unnecessary as well, because if known_reg->id matches, that means register states are exactly the same. > > > > +{ > > > + struct bpf_func_state *state; > > > + struct bpf_reg_state *reg; > > > + int i, j; > > > + > > > + for (i = 0; i <= vstate->curframe; i++) { > > > + state = vstate->frame[i]; > > > + for (j = 0; j < MAX_BPF_REG; j++) { > > > + reg = &state->regs[j]; > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > > + *reg = *known_reg; > > > + } > > > + > > > + bpf_for_each_spilled_reg(j, state, reg) { > > > + if (!reg) > > > + continue; > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > > + *reg = *known_reg; > > > + } > > > + } > > > +} > > > + > > > static int check_cond_jmp_op(struct bpf_verifier_env *env, > > > struct bpf_insn *insn, int *insn_idx) > > > { > > > @@ -7493,6 +7521,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, > > > reg_combine_min_max(&other_branch_regs[insn->src_reg], > > > &other_branch_regs[insn->dst_reg], > > > src_reg, dst_reg, opcode); > > > + if (src_reg->id) { > > > + find_equal_scalars(this_branch, src_reg); > > > + find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]); > > > + } > > > + > > > } > > > } else if (dst_reg->type == SCALAR_VALUE) { > > > reg_set_min_max(&other_branch_regs[insn->dst_reg], > > > @@ -7500,6 +7533,11 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, > > > opcode, is_jmp32); > > > } > > > > > > + if (dst_reg->type == SCALAR_VALUE && dst_reg->id) { > > > + find_equal_scalars(this_branch, dst_reg); > > > + find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]); > > > > will this cover the case above where reg_combine_min_max() can update > > dst_reg's as well? > > yes. > > > Even if yes, it probably would be more > > straightforward to call appropriate updates in the respective if > > branches (it's just a single line for each register, so not like it's > > duplicating tons of code). > > You mean inside reg_set_min_max() and inside reg_combine_min_max() ? > That won't work because find_equal_scalars() needs access to the whole > bpf_verifier_state and not just bpf_reg_state. No, I meant something like this, few lines above: if (BPF_SRC(insn->code) == BPF_X) { if (dst_reg->type == SCALAR_VALUE && src_reg->type == SCALAR_VALUE) { if (...) else if (...) else /* both src/dst regs in both this/other branches could have been updated */ find_equal_scalars(this_branch, src_reg); find_equal_scalars(this_branch, dst_reg); find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]) find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]) } } else if (dst_reg->type == SCALAR_VALUE) { reg_set_min_max(...); /* only dst_reg in both branches could have been updated */ find_equal_scalars(this_branch, dst_reg); find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]); } This keeps find_equal_scalars() for relevant registers very close to places where those registers are updated, instead of jumping back and forth between the complicated if after it, and double-checking under which circumstances dst_reg can be updated, for example. > > > It will make reasoning about this logic > > easier, IMO. Also, moving reg->id check into find_equal_scalars() > > would make the above suggestion even cleaner. > > I don't think so. I think checking for type == SCALAR && dst_reg->id != 0 > should be done outside of that function. It makes the logic cleaner. > For the same reason we check type outside of find_good_pkt_pointers().
On Tue, Oct 06, 2020 at 08:31:23PM -0700, Andrii Nakryiko wrote: > > > 'linked' is also wrong. The regs are exactly equal. > > In case of pkt and other pointers two regs will have the same id > > as well, but they will not be equal. Here these two scalars are equal > > otherwise doing *reg = *known_reg would be wrong. > > Ok, I guess it also means that "reg->type == SCALAR_VALUE" checks > below are unnecessary as well, because if known_reg->id matches, that > means register states are exactly the same. > > > > + for (j = 0; j < MAX_BPF_REG; j++) { > > > > + reg = &state->regs[j]; > > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) Right. The type check is technically unnecessary. It's a safety net in case id assignment goes wrong plus it makes it easier to understand the logic. > > > Even if yes, it probably would be more > > > straightforward to call appropriate updates in the respective if > > > branches (it's just a single line for each register, so not like it's > > > duplicating tons of code). > > > > You mean inside reg_set_min_max() and inside reg_combine_min_max() ? > > That won't work because find_equal_scalars() needs access to the whole > > bpf_verifier_state and not just bpf_reg_state. > > No, I meant something like this, few lines above: > > if (BPF_SRC(insn->code) == BPF_X) { > > if (dst_reg->type == SCALAR_VALUE && src_reg->type == SCALAR_VALUE) { > if (...) > else if (...) > else > > /* both src/dst regs in both this/other branches could have > been updated */ > find_equal_scalars(this_branch, src_reg); > find_equal_scalars(this_branch, dst_reg); > find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]) > find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]) > } > } else if (dst_reg->type == SCALAR_VALUE) { > reg_set_min_max(...); > > /* only dst_reg in both branches could have been updated */ > find_equal_scalars(this_branch, dst_reg); > find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]); > } > > > This keeps find_equal_scalars() for relevant registers very close to > places where those registers are updated, instead of jumping back and > forth between the complicated if after it, and double-checking under > which circumstances dst_reg can be updated, for example. I see it differently. I don't like moving if (reg->id) into find_equal_scalars(). Otherwise it would have to be named something like try_find_equal_scalars(). And even with such "try_" prefix it's still not clean. It's my general dislike of defensive programming. I prefer all functions to be imperative: "do" vs "try_do". There are exception from the rule, of course. Like kfree() that accepts NULL. That's fine. In this case I think if (type == SCALAR && id != 0) should be done by the caller. Note that's different from __update_reg_bounds(). There the bounds may or may not change, but the action is performed. What you're proposing it to make find_equal_scalars() accept any kind of register and do the action only if argument is actual scalar and its "id != 0". That's exactly the defensive programming that I feel make programmers sloppier. Note that's not the same as mark_reg_unknown() doing if (WARN_ON(regno >= MAX_BPF_REG)) check. I hope the difference is clear.
On Tue, Oct 6, 2020 at 9:15 PM Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote: > > On Tue, Oct 06, 2020 at 08:31:23PM -0700, Andrii Nakryiko wrote: > > > > > 'linked' is also wrong. The regs are exactly equal. > > > In case of pkt and other pointers two regs will have the same id > > > as well, but they will not be equal. Here these two scalars are equal > > > otherwise doing *reg = *known_reg would be wrong. > > > > Ok, I guess it also means that "reg->type == SCALAR_VALUE" checks > > below are unnecessary as well, because if known_reg->id matches, that > > means register states are exactly the same. > > > > > + for (j = 0; j < MAX_BPF_REG; j++) { > > > > > + reg = &state->regs[j]; > > > > > + if (reg->type == SCALAR_VALUE && reg->id == known_reg->id) > > Right. The type check is technically unnecessary. It's a safety net in case id > assignment goes wrong plus it makes it easier to understand the logic. > > > > > Even if yes, it probably would be more > > > > straightforward to call appropriate updates in the respective if > > > > branches (it's just a single line for each register, so not like it's > > > > duplicating tons of code). > > > > > > You mean inside reg_set_min_max() and inside reg_combine_min_max() ? > > > That won't work because find_equal_scalars() needs access to the whole > > > bpf_verifier_state and not just bpf_reg_state. > > > > No, I meant something like this, few lines above: > > > > if (BPF_SRC(insn->code) == BPF_X) { > > > > if (dst_reg->type == SCALAR_VALUE && src_reg->type == SCALAR_VALUE) { > > if (...) > > else if (...) > > else > > > > /* both src/dst regs in both this/other branches could have > > been updated */ > > find_equal_scalars(this_branch, src_reg); > > find_equal_scalars(this_branch, dst_reg); > > find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]) > > find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]) > > } > > } else if (dst_reg->type == SCALAR_VALUE) { > > reg_set_min_max(...); > > > > /* only dst_reg in both branches could have been updated */ > > find_equal_scalars(this_branch, dst_reg); > > find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]); > > } > > > > > > This keeps find_equal_scalars() for relevant registers very close to > > places where those registers are updated, instead of jumping back and > > forth between the complicated if after it, and double-checking under > > which circumstances dst_reg can be updated, for example. > > I see it differently. > I don't like moving if (reg->id) into find_equal_scalars(). Otherwise it would > have to be named something like try_find_equal_scalars(). And even with such > "try_" prefix it's still not clean. It's my general dislike of defensive > programming. I prefer all functions to be imperative: "do" vs "try_do". > There are exception from the rule, of course. Like kfree() that accepts NULL. > That's fine. > In this case I think if (type == SCALAR && id != 0) should be done by the caller. There is no need to do (type == SCALAR) check, see pseudo-code above. In all cases where find_equal_scalars() is called we know already that register is SCALAR. As for `if (reg->id)` being moved inside find_equal_scalars(). I didn't mean it as a defensive measure. It just allows to keep higher-level logic in check_cond_jmp_op() a bit more linear. Also, regarding "try_find_equal_scalars". It's not try/attempt to do this, it's do it, similarly to __update_reg_bounds() you explained below. It's just known_reg->id == 0 is a guarantee that there are no other equal registers, so we can skip the work. But of course one can look at this differently. I just prefer less nested ifs, if it's possible to avoid them. But all this is not that important. I suggested, you declined, let's move on. > Note that's different from __update_reg_bounds(). > There the bounds may or may not change, but the action is performed. > What you're proposing it to make find_equal_scalars() accept any kind > of register and do the action only if argument is actual scalar > and its "id != 0". That's exactly the defensive programming > that I feel make programmers sloppier. :) I see a little bit of an irony between this anti-defensive programming manifesto and "safety net in case id assignment goes wrong" above. > Note that's not the same as mark_reg_unknown() doing > if (WARN_ON(regno >= MAX_BPF_REG)) check. I hope the difference is clear.
On Tue, Oct 06, 2020 at 09:42:18PM -0700, Andrii Nakryiko wrote: > > I see it differently. > > I don't like moving if (reg->id) into find_equal_scalars(). Otherwise it would > > have to be named something like try_find_equal_scalars(). And even with such > > "try_" prefix it's still not clean. It's my general dislike of defensive > > programming. I prefer all functions to be imperative: "do" vs "try_do". > > There are exception from the rule, of course. Like kfree() that accepts NULL. > > That's fine. > > In this case I think if (type == SCALAR && id != 0) should be done by the caller. > > There is no need to do (type == SCALAR) check, see pseudo-code above. > In all cases where find_equal_scalars() is called we know already that > register is SCALAR. > > As for `if (reg->id)` being moved inside find_equal_scalars(). I > didn't mean it as a defensive measure. It just allows to keep > higher-level logic in check_cond_jmp_op() a bit more linear. > > Also, regarding "try_find_equal_scalars". It's not try/attempt to do > this, it's do it, similarly to __update_reg_bounds() you explained > below. It's just known_reg->id == 0 is a guarantee that there are no > other equal registers, so we can skip the work. But of course one can > look at this differently. I just prefer less nested ifs, if it's > possible to avoid them. > > But all this is not that important. I suggested, you declined, let's move on. > > > Note that's different from __update_reg_bounds(). > > There the bounds may or may not change, but the action is performed. > > What you're proposing it to make find_equal_scalars() accept any kind > > of register and do the action only if argument is actual scalar > > and its "id != 0". That's exactly the defensive programming > > that I feel make programmers sloppier. > > :) I see a little bit of an irony between this anti-defensive > programming manifesto and "safety net in case id assignment goes > wrong" above. > > > Note that's not the same as mark_reg_unknown() doing > > if (WARN_ON(regno >= MAX_BPF_REG)) check. I hope the difference is clear. Looks like the difference between defensive programming and safety net checks was not clear. The safety net in mark_reg_unknown() will be triggered when things really go wrong. I don't think I've ever seen in production code. I only saw it during the development when my code was badly broken. That check is to prevent security issues in case a bug sneaks in. The defensive programming lets a function accept incorrect arguments. That's normal behavior of such function. Because of such design choice the programers will routinely pass invalid args. That's kfree() checking for NULL and the only exception I can remember in the kernel code base. Arguably NULL is not an invalid value in this case. When people talk about defensive programming the NULL check is brought up as an example, but I think it's important to understand it at deeper level. Letting function accept any register only to > prefer less nested ifs, if it's possible to avoid them is the same thing. It's making code sloppier for esthetics of less nested if-s. There are plenty of projects and people that don't mind such coding style and find it easier to program. That's a disagreement in coding philosophy. It's ok to disagree, but it's important to understand those coding differences.
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? 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 > > Newly allocated register ID is ignored for scalars in regsafe() and doesn't > affect state pruning. mark_reg_unknown() also clears the ID. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > --- > kernel/bpf/verifier.c | 38 +++++++++++++++++++ > .../testing/selftests/bpf/prog_tests/align.c | 16 ++++---- > .../bpf/verifier/direct_packet_access.c | 2 +- > 3 files changed, 47 insertions(+), 9 deletions(-) > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 01120acab09a..09e17b483b0b 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -6432,6 +6432,8 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, > src_reg = NULL; > if (dst_reg->type != SCALAR_VALUE) > ptr_reg = dst_reg; > + else > + dst_reg->id = 0; > if (BPF_SRC(insn->code) == BPF_X) { > src_reg = ®s[insn->src_reg]; > if (src_reg->type != SCALAR_VALUE) { > @@ -6565,6 +6567,8 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > /* case: R1 = R2 > * copy register state to dest reg > */ > + if (src_reg->type == SCALAR_VALUE) > + src_reg->id = ++env->id_gen; > *dst_reg = *src_reg; > dst_reg->live |= REG_LIVE_WRITTEN; > dst_reg->subreg_def = DEF_NOT_SUBREG; > @@ -7365,6 +7369,30 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > return true; > }
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? > > 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. /* 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)); 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? .John > > > > > Newly allocated register ID is ignored for scalars in regsafe() and doesn't > > affect state pruning. mark_reg_unknown() also clears the ID. > > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> > > --- > > kernel/bpf/verifier.c | 38 +++++++++++++++++++ > > .../testing/selftests/bpf/prog_tests/align.c | 16 ++++---- > > .../bpf/verifier/direct_packet_access.c | 2 +- > > 3 files changed, 47 insertions(+), 9 deletions(-) > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 01120acab09a..09e17b483b0b 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -6432,6 +6432,8 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, > > src_reg = NULL; > > if (dst_reg->type != SCALAR_VALUE) > > ptr_reg = dst_reg; > > + else > > + dst_reg->id = 0; > > if (BPF_SRC(insn->code) == BPF_X) { > > src_reg = ®s[insn->src_reg]; > > if (src_reg->type != SCALAR_VALUE) { > > @@ -6565,6 +6567,8 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) > > /* case: R1 = R2 > > * copy register state to dest reg > > */ > > + if (src_reg->type == SCALAR_VALUE) > > + src_reg->id = ++env->id_gen; > > *dst_reg = *src_reg; > > dst_reg->live |= REG_LIVE_WRITTEN; > > dst_reg->subreg_def = DEF_NOT_SUBREG; > > @@ -7365,6 +7369,30 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, > > return true; > > }
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. > > /* 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. > > 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(). 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. 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. I'll add two synthetic tests for these cases. Any other case you can think of ? 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?
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.
On Thu, Oct 08, 2020 at 08:18:46AM -0700, John Fastabend wrote: > > > > 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. Excellent catch! Indeed. id should be cleared for 32-bit move. Will fix. > > > > 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. Right. Since it's easy to support this case I'll add it as well. Though I also never seen llvm generate the code like this and I don't think it will based on my understanding of regalloc. > > 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. Yeah. We also see such patterns only inside the loops with large loop bodies, and especially in unrolled loops. My understanding is that this is normal behavior of the greedy register allocator that introduces register copy for the split ranges. Yonghong sent me that link that explains algorithm in details: http://llvm.org/devmtg/2018-04/slides/Yatsina-LLVM%20Greedy%20Register%20Allocator.pdf The slide 137 and following slides explain exactly this scenario. In other words there is no way to tell llvm 'not to do this', so we have to improve the verifier smartness in such case. I'll add these details to commit log. > 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. The 2 out of 3 patches already landed. Please pull the latest llvm master.
From: Alexei Starovoitov <ast@kernel.org> Make two verifier improvements: - The llvm register allocator may use two different registers representing the same virtual register. Teach the verifier to recognize that. - Track bounded scalar spill/fill. The 'profiler' test in patch 3 will fail to load without patches 1 and 2. Alexei Starovoitov (2): bpf: Propagate scalar ranges through register assignments. selftests/bpf: Add profiler test Yonghong Song (1): bpf: Track spill/fill of bounded scalars. kernel/bpf/verifier.c | 54 +- .../testing/selftests/bpf/prog_tests/align.c | 16 +- .../selftests/bpf/prog_tests/test_profiler.c | 72 ++ tools/testing/selftests/bpf/progs/profiler.h | 177 ++++ .../selftests/bpf/progs/profiler.inc.h | 969 ++++++++++++++++++ tools/testing/selftests/bpf/progs/profiler1.c | 6 + tools/testing/selftests/bpf/progs/profiler2.c | 6 + tools/testing/selftests/bpf/progs/profiler3.c | 6 + .../bpf/verifier/direct_packet_access.c | 2 +- 9 files changed, 1298 insertions(+), 10 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/test_profiler.c create mode 100644 tools/testing/selftests/bpf/progs/profiler.h create mode 100644 tools/testing/selftests/bpf/progs/profiler.inc.h create mode 100644 tools/testing/selftests/bpf/progs/profiler1.c create mode 100644 tools/testing/selftests/bpf/progs/profiler2.c create mode 100644 tools/testing/selftests/bpf/progs/profiler3.c