Re: [PATCH bpf-next 2/7] bpf: support non-r10 register spill/fill to/from stack in precision tracking

Andrii Nakryiko
2023-11-12T01:57:33Z

On Thu, Nov 9, 2023 at 9:48 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Nov 9, 2023 at 10:20 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > On Thu, 2023-11-09 at 09:20 -0800, Andrii Nakryiko wrote:
> > [...]
> > > > > struct bpf_insn_hist_entry {
> > > > > - u32 prev_idx;
> > > > > u32 idx;
> > > > > + /* insn idx can't be bigger than 1 million */
> > > > > + u32 prev_idx : 22;
> > > > > + /* special flags, e.g., whether insn is doing register stack spill/load */
> > > > > + u32 flags : 10;
> > > > > };
> > > >
> > > > Nitpick: maybe use separate bit-fields for frameno and spi instead of
> > > > flags? Or add dedicated accessor functions?
> > >
> > > I wanted to keep it very uniform so that push_insn_history() doesn't
> > > know about all such details. It just has "flags". We might use these
> > > flags for some other use cases, though if we run out of bits we'll
> > > probably just expand bpf_insn_hist_entry and refactor existing code
> > > anyways. So, basically, I didn't want to over-engineer this bit too
> > > much :)
> >
> > Well, maybe hide "(hist->flags >> INSN_F_SPI_SHIFT) & INSN_F_SPI_MASK"
> > behind an accessor?
>
> I'll add a single line helper function just to not be PITA, but I
> don't think it's worth it. There are two places we do this, one next
> to the other within the same function. This helper is just going to
> add mental overhead and won't really help us with anything.
>
> >
> > [...]
> >
> > > > > +static int push_insn_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
> > > > > + int insn_flags)
> > > > > {
> > > > > struct bpf_insn_hist_entry *p;
> > > > > size_t alloc_size;
> > > > >
> > > > > - if (!is_jmp_point(env, env->insn_idx))
> > > > > + /* combine instruction flags if we already recorded this instruction */
> > > > > + if (cur->insn_hist_end > cur->insn_hist_start &&
> > > > > + (p = &env->insn_hist[cur->insn_hist_end - 1]) &&
> > > > > + p->idx == env->insn_idx &&
> > > > > + p->prev_idx == env->prev_insn_idx) {
> > > > > + p->flags |= insn_flags;
> > > >
> > > > Nitpick: maybe add an assert to check that frameno/spi are not or'ed?
> > >
> > > ok, something like
> > >
> > > WARN_ON_ONCE(p->flags & (INSN_F_STACK_ACCESS | INSN_F_FRAMENOMASK |
> > > (INSN_F_SPI_MASK << INSN_F_SPI_SHIFT)));
> > >
> > > ?
> >
> > Something like this, yes.
> >
>
> I added it, and I hate it. It's just a visual noise. Feels too
> paranoid, I'll probably drop it.
>

I ended up with these changes on top of this patch:

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 23dbfb5022ba..d234c6f53741 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3167,6 +3167,21 @@ static int check_reg_arg(struct
bpf_verifier_env *env, u32 regno,
return 0;
}

+static int insn_stack_access_flags(int frameno, int spi)
+{
+ return INSN_F_STACK_ACCESS | (spi << INSN_F_SPI_SHIFT) | frameno;
+}
+
+static int insn_stack_access_spi(int insn_flags)
+{
+ return (insn_flags >> INSN_F_SPI_SHIFT) & INSN_F_SPI_MASK;
+}
+
+static int insn_stack_access_frameno(int insn_flags)
+{
+ return insn_flags & INSN_F_FRAMENO_MASK;
+}
+
static void mark_jmp_point(struct bpf_verifier_env *env, int idx)
{
env->insn_aux_data[idx].jmp_point = true;
@@ -3187,6 +3202,7 @@ static int push_insn_history(struct
bpf_verifier_env *env, struct bpf_verifier_s

/* combine instruction flags if we already recorded this instruction */
if (env->cur_hist_ent) {
+ WARN_ON_ONCE(env->cur_hist_ent->flags & insn_flags);
env->cur_hist_ent->flags |= insn_flags;
return 0;
}
@@ -3499,8 +3515,8 @@ static int backtrack_insn(struct
bpf_verifier_env *env, int idx, int subseq_idx,
* that [fp - off] slot contains scalar that needs to be
* tracked with precision
*/
- spi = (hist->flags >> INSN_F_SPI_SHIFT) & INSN_F_SPI_MASK;
- fr = hist->flags & INSN_F_FRAMENO_MASK;
+ spi = insn_stack_access_spi(hist->flags);
+ fr = insn_stack_access_frameno(hist->flags);
bt_set_frame_slot(bt, fr, spi);
} else if (class == BPF_STX || class == BPF_ST) {
if (bt_is_reg_set(bt, dreg))
@@ -3512,8 +3528,8 @@ static int backtrack_insn(struct
bpf_verifier_env *env, int idx, int subseq_idx,
/* scalars can only be spilled into stack */
if (!hist || !(hist->flags & INSN_F_STACK_ACCESS))
return 0;
- spi = (hist->flags >> INSN_F_SPI_SHIFT) & INSN_F_SPI_MASK;
- fr = hist->flags & INSN_F_FRAMENO_MASK;
+ spi = insn_stack_access_spi(hist->flags);
+ fr = insn_stack_access_frameno(hist->flags);
if (!bt_is_frame_slot_set(bt, fr, spi))
return 0;
bt_clear_frame_slot(bt, fr, spi);
@@ -4322,7 +4338,7 @@ static int check_stack_write_fixed_off(struct
bpf_verifier_env *env,
int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err;
struct bpf_insn *insn = &env->prog->insnsi[insn_idx];
struct bpf_reg_state *reg = NULL;
- int insn_flags = INSN_F_STACK_ACCESS | (spi <<
INSN_F_SPI_SHIFT) | state->frameno;
+ int insn_flags = insn_stack_access_flags(state->frameno, spi);

err = grow_stack_state(state, round_up(slot + 1, BPF_REG_SIZE));
if (err)
@@ -4618,7 +4634,7 @@ static int check_stack_read_fixed_off(struct
bpf_verifier_env *env,
int i, slot = -off - 1, spi = slot / BPF_REG_SIZE;
struct bpf_reg_state *reg;
u8 *stype, type;
- int insn_flags = INSN_F_STACK_ACCESS | (spi <<
INSN_F_SPI_SHIFT) | reg_state->frameno;
+ int insn_flags = insn_stack_access_flags(reg_state->frameno, spi);

stype = reg_state->stack[spi].slot_type;
reg = &reg_state->stack[spi].spilled_ptr;

> > [...]
> >
> > > > > @@ -4713,9 +4711,12 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
> > > > >
> > > > > /* Mark slots affected by this stack write. */
> > > > > for (i = 0; i < size; i++)
> > > > > - state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] =
> > > > > - type;
> > > > > + state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] = type;
> > > > > + insn_flags = 0; /* not a register spill */
> > > > > }
> > > > > +
> > > > > + if (insn_flags)
> > > > > + return push_insn_history(env, env->cur_state, insn_flags);
> > > >
> > > > Maybe add a check that insn is BPF_ST or BPF_STX here?
> > > > Only these cases are supported by backtrack_insn() while
> > > > check_mem_access() is called from multiple places.
> > >
> > > seems like a wrong place to enforce that check_stack_write_fixed_off()
> > > is called only for those instructions?
> >
> > check_stack_write_fixed_off() is called from check_stack_write() which
> > is called from check_mem_access() which might trigger
> > check_stack_write_fixed_off() when called with BPF_WRITE flag and
> > pointer to stack as an argument.
> > This happens for ST, STX but also in check_helper_call(),
> > process_iter_arg() (maybe other places).
> > Speaking of which, should this be handled in backtrack_insn()?
>
> Note that we set insn_flags only for cases where we do an actual
> register spill (save_register_state calls for non-fake registers). If
> register spill is possible from a helper call somehow, we'll be in
> much bigger trouble elsewhere.
>
> >
> > > [...]
> > >
> > > trimming is good
> >
> > Sigh... sorry, really tried to trim everything today.