On Thu, Nov 9, 2023 at 7:20 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
>
> On Mon, 2023-10-30 at 22:03 -0700, Andrii Nakryiko wrote:
>
> All makes sense, a few nitpicks below.
>
> Acked-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
>
> [...]
>
> > +/* instruction history flags, used in bpf_insn_hist_entry.flags field */
> > +enum {
> > + /* instruction references stack slot through PTR_TO_STACK register;
> > + * we also store stack's frame number in lower 3 bits (MAX_CALL_FRAMES is 8)
> > + * and accessed stack slot's index in next 6 bits (MAX_BPF_STACK is 512,
> > + * 8 bytes per slot, so slot index (spi) is [0, 63])
> > + */
> > + INSN_F_FRAMENO_MASK = 0x7, /* 3 bits */
> > +
> > + INSN_F_SPI_MASK = 0x3f, /* 6 bits */
> > + INSN_F_SPI_SHIFT = 3, /* shifted 3 bits to the left */
> > +
> > + INSN_F_STACK_ACCESS = BIT(9), /* we need 10 bits total */
> > +};
> > +
> > +static_assert(INSN_F_FRAMENO_MASK + 1 >= MAX_CALL_FRAMES);
> > +static_assert(INSN_F_SPI_MASK + 1 >= MAX_BPF_STACK / 8);
> > +
> > 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 :)
>
> >
> > -#define MAX_CALL_FRAMES 8
> > /* Maximum number of register states that can exist at once */
> > #define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES)
> > struct bpf_verifier_state {
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 2905ce2e8b34..fbb779583d52 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -3479,14 +3479,20 @@ static bool is_jmp_point(struct bpf_verifier_env *env, int insn_idx)
> > }
> >
> > /* for any branch, call, exit record the history of jmps in the given state */
> > -static int push_jmp_history(struct bpf_verifier_env *env,
> > - struct bpf_verifier_state *cur)
> > +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)));
?
>
> [...]
>
> > +static struct bpf_insn_hist_entry *get_hist_insn_entry(struct bpf_verifier_env *env,
> > + u32 hist_start, u32 hist_end, int insn_idx)
>
> Nitpick: maybe rename 'hist_insn' to 'insn_hist', i.e. 'get_insn_hist_entry'?
sure, good point, done
>
> [...]
>
> > @@ -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?
>
> > return 0;
> > }
> >
> > @@ -4908,6 +4909,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;
> >
> > stype = reg_state->stack[spi].slot_type;
> > reg = ®_state->stack[spi].spilled_ptr;
[...]
trimming is good
