| Message ID | 20230606222411.1820404-2-eddyz87@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Delegated to: | BPF |
| Headers | show |
| Series | verify scalar ids mapping in regsafe() | expand |
On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > Change mark_chain_precision() to track precision in situations > like below: > > r2 = unknown value > ... > --- state #0 --- > ... > r1 = r2 // r1 and r2 now share the same ID > ... > --- state #1 {r1.id = A, r2.id = A} --- > ... > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > ... > --- state #2 {r1.id = A, r2.id = A} --- > r3 = r10 > r3 += r1 // need to mark both r1 and r2 > > At the beginning of the processing of each state, ensure that if a > register with a scalar ID is marked as precise, all registers sharing > this ID are also marked as precise. > > This property would be used by a follow-up change in regsafe(). > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > --- > include/linux/bpf_verifier.h | 10 +- > kernel/bpf/verifier.c | 114 ++++++++++++++++++ > .../testing/selftests/bpf/verifier/precise.c | 8 +- > 3 files changed, 127 insertions(+), 5 deletions(-) > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > index ee4cc7471ed9..3f9856baa542 100644 > --- a/include/linux/bpf_verifier.h > +++ b/include/linux/bpf_verifier.h > @@ -559,6 +559,11 @@ struct backtrack_state { > u64 stack_masks[MAX_CALL_FRAMES]; > }; > > +struct reg_id_scratch { > + u32 count; > + u32 ids[BPF_ID_MAP_SIZE]; > +}; > + > /* single container for all structs > * one verifier_env per bpf_check() call > */ > @@ -590,7 +595,10 @@ struct bpf_verifier_env { > const struct bpf_line_info *prev_linfo; > struct bpf_verifier_log log; > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > + union { > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > + struct reg_id_scratch precise_ids_scratch; naming nit: "ids_scratch" or "idset_scratch" to stay in line with "idmap_scratch"? > + }; > struct { > int *insn_state; > int *insn_stack; > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index d117deb03806..2aa60b73f1b5 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ > } > } > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id) > +{ > + u32 i; > + > + for (i = 0; i < s->count; ++i) > + if (s->ids[i] == id) > + return true; > + > + return false; > +} > + > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id) > +{ > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids))) > + return -1; > + s->ids[s->count++] = id; this will allow duplicated IDs to be added? Was it done in the name of speed? > + WARN_ONCE(s->count > 64, > + "reg_id_scratch.count is unreasonably large (%d)", s->count); do we need this one? Especially that it's not _ONCE variant? Maybe the first WARN_ON_ONCE is enough? > + return 0; > +} > + > +static inline void reg_id_scratch_reset(struct reg_id_scratch *s) we probably don't need "inline" for all these helpers? > +{ > + s->count = 0; > +} > + > +/* Collect a set of IDs for all registers currently marked as precise in env->bt. > + * Mark all registers with these IDs as precise. > + */ > +static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st) > +{ > + struct reg_id_scratch *precise_ids = &env->precise_ids_scratch; > + struct backtrack_state *bt = &env->bt; > + struct bpf_func_state *func; > + struct bpf_reg_state *reg; > + DECLARE_BITMAP(mask, 64); > + int i, fr; > + > + reg_id_scratch_reset(precise_ids); > + > + for (fr = bt->frame; fr >= 0; fr--) { > + func = st->frame[fr]; > + > + bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr)); > + for_each_set_bit(i, mask, 32) { > + reg = &func->regs[i]; > + if (!reg->id || reg->type != SCALAR_VALUE) > + continue; > + if (reg_id_scratch_push(precise_ids, reg->id)) > + return; > + } > + > + bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr)); > + for_each_set_bit(i, mask, 64) { > + if (i >= func->allocated_stack / BPF_REG_SIZE) > + break; > + if (!is_spilled_scalar_reg(&func->stack[i])) > + continue; > + reg = &func->stack[i].spilled_ptr; > + if (!reg->id || reg->type != SCALAR_VALUE) is_spilled_scalar_reg() already ensures reg->type is SCALAR_VALUE > + continue; > + if (reg_id_scratch_push(precise_ids, reg->id)) > + return; if push fails (due to overflow of id set), shouldn't we propagate error back and fallback to mark_all_precise? > + } > + } > + > + for (fr = 0; fr <= st->curframe; ++fr) { > + func = st->frame[fr]; > + > + for (i = BPF_REG_0; i < BPF_REG_10; ++i) { > + reg = &func->regs[i]; > + if (!reg->id) > + continue; > + if (!reg_id_scratch_contains(precise_ids, reg->id)) > + continue; > + bt_set_frame_reg(bt, fr, i); > + } > + for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) { > + if (!is_spilled_scalar_reg(&func->stack[i])) > + continue; > + reg = &func->stack[i].spilled_ptr; > + if (!reg->id) > + continue; > + if (!reg_id_scratch_contains(precise_ids, reg->id)) > + continue; > + bt_set_frame_slot(bt, fr, i); > + } > + } > +} > + > /* > * __mark_chain_precision() backtracks BPF program instruction sequence and > * chain of verifier states making sure that register *regno* (if regno >= 0) > @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) > bt->frame, last_idx, first_idx, subseq_idx); > } > > + /* If some register with scalar ID is marked as precise, > + * make sure that all registers sharing this ID are also precise. > + * This is needed to estimate effect of find_equal_scalars(). > + * Do this at the last instruction of each state, > + * bpf_reg_state::id fields are valid for these instructions. > + * > + * Allows to track precision in situation like below: > + * > + * r2 = unknown value > + * ... > + * --- state #0 --- > + * ... > + * r1 = r2 // r1 and r2 now share the same ID > + * ... > + * --- state #1 {r1.id = A, r2.id = A} --- > + * ... > + * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > + * ... > + * --- state #2 {r1.id = A, r2.id = A} --- > + * r3 = r10 > + * r3 += r1 // need to mark both r1 and r2 > + */ > + mark_precise_scalar_ids(env, st); > + > if (last_idx < 0) { > /* we are at the entry into subprog, which > * is expected for global funcs, but only if > diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c > index b8c0aae8e7ec..99272bb890da 100644 > --- a/tools/testing/selftests/bpf/verifier/precise.c > +++ b/tools/testing/selftests/bpf/verifier/precise.c > @@ -46,7 +46,7 @@ > mark_precise: frame0: regs=r2 stack= before 20\ > mark_precise: frame0: parent state regs=r2 stack=:\ > mark_precise: frame0: last_idx 19 first_idx 10\ > - mark_precise: frame0: regs=r2 stack= before 19\ > + mark_precise: frame0: regs=r2,r9 stack= before 19\ > mark_precise: frame0: regs=r9 stack= before 18\ > mark_precise: frame0: regs=r8,r9 stack= before 17\ > mark_precise: frame0: regs=r0,r9 stack= before 15\ > @@ -106,10 +106,10 @@ > mark_precise: frame0: regs=r2 stack= before 22\ > mark_precise: frame0: parent state regs=r2 stack=:\ > mark_precise: frame0: last_idx 20 first_idx 20\ > - mark_precise: frame0: regs=r2 stack= before 20\ > - mark_precise: frame0: parent state regs=r2 stack=:\ > + mark_precise: frame0: regs=r2,r9 stack= before 20\ > + mark_precise: frame0: parent state regs=r2,r9 stack=:\ > mark_precise: frame0: last_idx 19 first_idx 17\ > - mark_precise: frame0: regs=r2 stack= before 19\ > + mark_precise: frame0: regs=r2,r9 stack= before 19\ > mark_precise: frame0: regs=r9 stack= before 18\ > mark_precise: frame0: regs=r8,r9 stack= before 17\ > mark_precise: frame0: parent state regs= stack=:", > -- > 2.40.1 >
On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote: > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > Change mark_chain_precision() to track precision in situations > > like below: > > > > r2 = unknown value > > ... > > --- state #0 --- > > ... > > r1 = r2 // r1 and r2 now share the same ID > > ... > > --- state #1 {r1.id = A, r2.id = A} --- > > ... > > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > > ... > > --- state #2 {r1.id = A, r2.id = A} --- > > r3 = r10 > > r3 += r1 // need to mark both r1 and r2 > > > > At the beginning of the processing of each state, ensure that if a > > register with a scalar ID is marked as precise, all registers sharing > > this ID are also marked as precise. > > > > This property would be used by a follow-up change in regsafe(). > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > --- > > include/linux/bpf_verifier.h | 10 +- > > kernel/bpf/verifier.c | 114 ++++++++++++++++++ > > .../testing/selftests/bpf/verifier/precise.c | 8 +- > > 3 files changed, 127 insertions(+), 5 deletions(-) > > > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > > index ee4cc7471ed9..3f9856baa542 100644 > > --- a/include/linux/bpf_verifier.h > > +++ b/include/linux/bpf_verifier.h > > @@ -559,6 +559,11 @@ struct backtrack_state { > > u64 stack_masks[MAX_CALL_FRAMES]; > > }; > > > > +struct reg_id_scratch { > > + u32 count; > > + u32 ids[BPF_ID_MAP_SIZE]; > > +}; > > + > > /* single container for all structs > > * one verifier_env per bpf_check() call > > */ > > @@ -590,7 +595,10 @@ struct bpf_verifier_env { > > const struct bpf_line_info *prev_linfo; > > struct bpf_verifier_log log; > > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; > > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > + union { > > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > + struct reg_id_scratch precise_ids_scratch; > > naming nit: "ids_scratch" or "idset_scratch" to stay in line with > "idmap_scratch"? Makes sense, will change to "idset_scratch". > > > + }; > > struct { > > int *insn_state; > > int *insn_stack; > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index d117deb03806..2aa60b73f1b5 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ > > } > > } > > > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id) > > +{ > > + u32 i; > > + > > + for (i = 0; i < s->count; ++i) > > + if (s->ids[i] == id) > > + return true; > > + > > + return false; > > +} > > + > > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id) > > +{ > > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids))) > > + return -1; > > + s->ids[s->count++] = id; > > this will allow duplicated IDs to be added? Was it done in the name of speed? tbh, it's an artifact from bsearch/sort migration of a series. While doing test veristat runs I found that maximal value of s->count is 5, so looks like it would be fine the way it is now and it would be fine if linear scan is added to avoid duplicate ids. Don't think I have a preference. > > > + WARN_ONCE(s->count > 64, > > + "reg_id_scratch.count is unreasonably large (%d)", s->count); > > do we need this one? Especially that it's not _ONCE variant? Maybe the > first WARN_ON_ONCE is enough? We make an assumption that linear scans of this array are ok, and it would be scanned often. I'd like to have some indication if this assumption is broken. The s->ids array is large (10 regs + 64 spills) * 8 frames. If you think that this logging is not necessary I'll remove it. > > > + return 0; > > +} > > + > > +static inline void reg_id_scratch_reset(struct reg_id_scratch *s) > > we probably don't need "inline" for all these helpers? Ok, will remove "inline". > > > +{ > > + s->count = 0; > > +} > > + > > +/* Collect a set of IDs for all registers currently marked as precise in env->bt. > > + * Mark all registers with these IDs as precise. > > + */ > > +static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st) > > +{ > > + struct reg_id_scratch *precise_ids = &env->precise_ids_scratch; > > + struct backtrack_state *bt = &env->bt; > > + struct bpf_func_state *func; > > + struct bpf_reg_state *reg; > > + DECLARE_BITMAP(mask, 64); > > + int i, fr; > > + > > + reg_id_scratch_reset(precise_ids); > > + > > + for (fr = bt->frame; fr >= 0; fr--) { > > + func = st->frame[fr]; > > + > > + bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr)); > > + for_each_set_bit(i, mask, 32) { > > + reg = &func->regs[i]; > > + if (!reg->id || reg->type != SCALAR_VALUE) > > + continue; > > + if (reg_id_scratch_push(precise_ids, reg->id)) > > + return; > > + } > > + > > + bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr)); > > + for_each_set_bit(i, mask, 64) { > > + if (i >= func->allocated_stack / BPF_REG_SIZE) > > + break; > > + if (!is_spilled_scalar_reg(&func->stack[i])) > > + continue; > > + reg = &func->stack[i].spilled_ptr; > > + if (!reg->id || reg->type != SCALAR_VALUE) > > is_spilled_scalar_reg() already ensures reg->type is SCALAR_VALUE Yes, my bad. > > > + continue; > > + if (reg_id_scratch_push(precise_ids, reg->id)) > > + return; > > if push fails (due to overflow of id set), shouldn't we propagate > error back and fallback to mark_all_precise? In theory this push should never fail, as we pre-allocate enough slots in the scratch. I'll propagate error to __mark_chain_precision() and exit from that one with -EFAULT. > > > > + } > > + } > > + > > + for (fr = 0; fr <= st->curframe; ++fr) { > > + func = st->frame[fr]; > > + > > + for (i = BPF_REG_0; i < BPF_REG_10; ++i) { > > + reg = &func->regs[i]; > > + if (!reg->id) > > + continue; > > + if (!reg_id_scratch_contains(precise_ids, reg->id)) > > + continue; > > + bt_set_frame_reg(bt, fr, i); > > + } > > + for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) { > > + if (!is_spilled_scalar_reg(&func->stack[i])) > > + continue; > > + reg = &func->stack[i].spilled_ptr; > > + if (!reg->id) > > + continue; > > + if (!reg_id_scratch_contains(precise_ids, reg->id)) > > + continue; > > + bt_set_frame_slot(bt, fr, i); > > + } > > + } > > +} > > + > > /* > > * __mark_chain_precision() backtracks BPF program instruction sequence and > > * chain of verifier states making sure that register *regno* (if regno >= 0) > > @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) > > bt->frame, last_idx, first_idx, subseq_idx); > > } > > > > + /* If some register with scalar ID is marked as precise, > > + * make sure that all registers sharing this ID are also precise. > > + * This is needed to estimate effect of find_equal_scalars(). > > + * Do this at the last instruction of each state, > > + * bpf_reg_state::id fields are valid for these instructions. > > + * > > + * Allows to track precision in situation like below: > > + * > > + * r2 = unknown value > > + * ... > > + * --- state #0 --- > > + * ... > > + * r1 = r2 // r1 and r2 now share the same ID > > + * ... > > + * --- state #1 {r1.id = A, r2.id = A} --- > > + * ... > > + * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > > + * ... > > + * --- state #2 {r1.id = A, r2.id = A} --- > > + * r3 = r10 > > + * r3 += r1 // need to mark both r1 and r2 > > + */ > > + mark_precise_scalar_ids(env, st); > > + > > if (last_idx < 0) { > > /* we are at the entry into subprog, which > > * is expected for global funcs, but only if > > diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c > > index b8c0aae8e7ec..99272bb890da 100644 > > --- a/tools/testing/selftests/bpf/verifier/precise.c > > +++ b/tools/testing/selftests/bpf/verifier/precise.c > > @@ -46,7 +46,7 @@ > > mark_precise: frame0: regs=r2 stack= before 20\ > > mark_precise: frame0: parent state regs=r2 stack=:\ > > mark_precise: frame0: last_idx 19 first_idx 10\ > > - mark_precise: frame0: regs=r2 stack= before 19\ > > + mark_precise: frame0: regs=r2,r9 stack= before 19\ > > mark_precise: frame0: regs=r9 stack= before 18\ > > mark_precise: frame0: regs=r8,r9 stack= before 17\ > > mark_precise: frame0: regs=r0,r9 stack= before 15\ > > @@ -106,10 +106,10 @@ > > mark_precise: frame0: regs=r2 stack= before 22\ > > mark_precise: frame0: parent state regs=r2 stack=:\ > > mark_precise: frame0: last_idx 20 first_idx 20\ > > - mark_precise: frame0: regs=r2 stack= before 20\ > > - mark_precise: frame0: parent state regs=r2 stack=:\ > > + mark_precise: frame0: regs=r2,r9 stack= before 20\ > > + mark_precise: frame0: parent state regs=r2,r9 stack=:\ > > mark_precise: frame0: last_idx 19 first_idx 17\ > > - mark_precise: frame0: regs=r2 stack= before 19\ > > + mark_precise: frame0: regs=r2,r9 stack= before 19\ > > mark_precise: frame0: regs=r9 stack= before 18\ > > mark_precise: frame0: regs=r8,r9 stack= before 17\ > > mark_precise: frame0: parent state regs= stack=:", > > -- > > 2.40.1 > >
On Thu, Jun 8, 2023 at 5:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote: > > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > Change mark_chain_precision() to track precision in situations > > > like below: > > > > > > r2 = unknown value > > > ... > > > --- state #0 --- > > > ... > > > r1 = r2 // r1 and r2 now share the same ID > > > ... > > > --- state #1 {r1.id = A, r2.id = A} --- > > > ... > > > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > > > ... > > > --- state #2 {r1.id = A, r2.id = A} --- > > > r3 = r10 > > > r3 += r1 // need to mark both r1 and r2 > > > > > > At the beginning of the processing of each state, ensure that if a > > > register with a scalar ID is marked as precise, all registers sharing > > > this ID are also marked as precise. > > > > > > This property would be used by a follow-up change in regsafe(). > > > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > > --- > > > include/linux/bpf_verifier.h | 10 +- > > > kernel/bpf/verifier.c | 114 ++++++++++++++++++ > > > .../testing/selftests/bpf/verifier/precise.c | 8 +- > > > 3 files changed, 127 insertions(+), 5 deletions(-) > > > > > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > > > index ee4cc7471ed9..3f9856baa542 100644 > > > --- a/include/linux/bpf_verifier.h > > > +++ b/include/linux/bpf_verifier.h > > > @@ -559,6 +559,11 @@ struct backtrack_state { > > > u64 stack_masks[MAX_CALL_FRAMES]; > > > }; > > > > > > +struct reg_id_scratch { > > > + u32 count; > > > + u32 ids[BPF_ID_MAP_SIZE]; > > > +}; > > > + > > > /* single container for all structs > > > * one verifier_env per bpf_check() call > > > */ > > > @@ -590,7 +595,10 @@ struct bpf_verifier_env { > > > const struct bpf_line_info *prev_linfo; > > > struct bpf_verifier_log log; > > > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; > > > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > > + union { > > > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > > + struct reg_id_scratch precise_ids_scratch; > > > > naming nit: "ids_scratch" or "idset_scratch" to stay in line with > > "idmap_scratch"? > > Makes sense, will change to "idset_scratch". > > > > > > + }; > > > struct { > > > int *insn_state; > > > int *insn_stack; > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > index d117deb03806..2aa60b73f1b5 100644 > > > --- a/kernel/bpf/verifier.c > > > +++ b/kernel/bpf/verifier.c > > > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ > > > } > > > } > > > > > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id) > > > +{ > > > + u32 i; > > > + > > > + for (i = 0; i < s->count; ++i) > > > + if (s->ids[i] == id) > > > + return true; > > > + > > > + return false; > > > +} > > > + > > > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id) > > > +{ > > > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids))) > > > + return -1; > > > + s->ids[s->count++] = id; > > > > this will allow duplicated IDs to be added? Was it done in the name of speed? > > tbh, it's an artifact from bsearch/sort migration of a series. > While doing test veristat runs I found that maximal value of s->count is 5, > so looks like it would be fine the way it is now and it would be fine > if linear scan is added to avoid duplicate ids. Don't think I have a preference. Maybe return -EFAULT for count > 64 and print a verifier error message ? If/when syzbot/human manages to craft such a program we'll know that this is something to address.
On Thu, 2023-06-08 at 08:43 -0700, Alexei Starovoitov wrote: > On Thu, Jun 8, 2023 at 5:35 AM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > On Wed, 2023-06-07 at 14:40 -0700, Andrii Nakryiko wrote: > > > On Tue, Jun 6, 2023 at 3:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote: > > > > > > > > Change mark_chain_precision() to track precision in situations > > > > like below: > > > > > > > > r2 = unknown value > > > > ... > > > > --- state #0 --- > > > > ... > > > > r1 = r2 // r1 and r2 now share the same ID > > > > ... > > > > --- state #1 {r1.id = A, r2.id = A} --- > > > > ... > > > > if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 > > > > ... > > > > --- state #2 {r1.id = A, r2.id = A} --- > > > > r3 = r10 > > > > r3 += r1 // need to mark both r1 and r2 > > > > > > > > At the beginning of the processing of each state, ensure that if a > > > > register with a scalar ID is marked as precise, all registers sharing > > > > this ID are also marked as precise. > > > > > > > > This property would be used by a follow-up change in regsafe(). > > > > > > > > Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> > > > > --- > > > > include/linux/bpf_verifier.h | 10 +- > > > > kernel/bpf/verifier.c | 114 ++++++++++++++++++ > > > > .../testing/selftests/bpf/verifier/precise.c | 8 +- > > > > 3 files changed, 127 insertions(+), 5 deletions(-) > > > > > > > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h > > > > index ee4cc7471ed9..3f9856baa542 100644 > > > > --- a/include/linux/bpf_verifier.h > > > > +++ b/include/linux/bpf_verifier.h > > > > @@ -559,6 +559,11 @@ struct backtrack_state { > > > > u64 stack_masks[MAX_CALL_FRAMES]; > > > > }; > > > > > > > > +struct reg_id_scratch { > > > > + u32 count; > > > > + u32 ids[BPF_ID_MAP_SIZE]; > > > > +}; > > > > + > > > > /* single container for all structs > > > > * one verifier_env per bpf_check() call > > > > */ > > > > @@ -590,7 +595,10 @@ struct bpf_verifier_env { > > > > const struct bpf_line_info *prev_linfo; > > > > struct bpf_verifier_log log; > > > > struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; > > > > - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > > > + union { > > > > + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; > > > > + struct reg_id_scratch precise_ids_scratch; > > > > > > naming nit: "ids_scratch" or "idset_scratch" to stay in line with > > > "idmap_scratch"? > > > > Makes sense, will change to "idset_scratch". > > > > > > > > > + }; > > > > struct { > > > > int *insn_state; > > > > int *insn_stack; > > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > > index d117deb03806..2aa60b73f1b5 100644 > > > > --- a/kernel/bpf/verifier.c > > > > +++ b/kernel/bpf/verifier.c > > > > @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ > > > > } > > > > } > > > > > > > > +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id) > > > > +{ > > > > + u32 i; > > > > + > > > > + for (i = 0; i < s->count; ++i) > > > > + if (s->ids[i] == id) > > > > + return true; > > > > + > > > > + return false; > > > > +} > > > > + > > > > +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id) > > > > +{ > > > > + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids))) > > > > + return -1; > > > > + s->ids[s->count++] = id; > > > > > > this will allow duplicated IDs to be added? Was it done in the name of speed? > > > > tbh, it's an artifact from bsearch/sort migration of a series. > > While doing test veristat runs I found that maximal value of s->count is 5, > > so looks like it would be fine the way it is now and it would be fine > > if linear scan is added to avoid duplicate ids. Don't think I have a preference. > > Maybe return -EFAULT for count > 64 and print a verifier error message ? > If/when syzbot/human manages to craft such a program we'll know that > this is something to address. Sounds a bit heavy-handed. Should the same logic apply to idmap? I did some silly testing, 1'000'000 searches over u32 array of size (10+64)*8: - linear search is done in 0.7s - qsort/bsearch is done in 23s It looks like my concerns are completely overblown. I'm inclined to remove the size warning and just check for array overflow.
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index ee4cc7471ed9..3f9856baa542 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -559,6 +559,11 @@ struct backtrack_state { u64 stack_masks[MAX_CALL_FRAMES]; }; +struct reg_id_scratch { + u32 count; + u32 ids[BPF_ID_MAP_SIZE]; +}; + /* single container for all structs * one verifier_env per bpf_check() call */ @@ -590,7 +595,10 @@ struct bpf_verifier_env { const struct bpf_line_info *prev_linfo; struct bpf_verifier_log log; struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 1]; - struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; + union { + struct bpf_id_pair idmap_scratch[BPF_ID_MAP_SIZE]; + struct reg_id_scratch precise_ids_scratch; + }; struct { int *insn_state; int *insn_stack; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d117deb03806..2aa60b73f1b5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3779,6 +3779,96 @@ static void mark_all_scalars_imprecise(struct bpf_verifier_env *env, struct bpf_ } } +static inline bool reg_id_scratch_contains(struct reg_id_scratch *s, u32 id) +{ + u32 i; + + for (i = 0; i < s->count; ++i) + if (s->ids[i] == id) + return true; + + return false; +} + +static inline int reg_id_scratch_push(struct reg_id_scratch *s, u32 id) +{ + if (WARN_ON_ONCE(s->count >= ARRAY_SIZE(s->ids))) + return -1; + s->ids[s->count++] = id; + WARN_ONCE(s->count > 64, + "reg_id_scratch.count is unreasonably large (%d)", s->count); + return 0; +} + +static inline void reg_id_scratch_reset(struct reg_id_scratch *s) +{ + s->count = 0; +} + +/* Collect a set of IDs for all registers currently marked as precise in env->bt. + * Mark all registers with these IDs as precise. + */ +static void mark_precise_scalar_ids(struct bpf_verifier_env *env, struct bpf_verifier_state *st) +{ + struct reg_id_scratch *precise_ids = &env->precise_ids_scratch; + struct backtrack_state *bt = &env->bt; + struct bpf_func_state *func; + struct bpf_reg_state *reg; + DECLARE_BITMAP(mask, 64); + int i, fr; + + reg_id_scratch_reset(precise_ids); + + for (fr = bt->frame; fr >= 0; fr--) { + func = st->frame[fr]; + + bitmap_from_u64(mask, bt_frame_reg_mask(bt, fr)); + for_each_set_bit(i, mask, 32) { + reg = &func->regs[i]; + if (!reg->id || reg->type != SCALAR_VALUE) + continue; + if (reg_id_scratch_push(precise_ids, reg->id)) + return; + } + + bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr)); + for_each_set_bit(i, mask, 64) { + if (i >= func->allocated_stack / BPF_REG_SIZE) + break; + if (!is_spilled_scalar_reg(&func->stack[i])) + continue; + reg = &func->stack[i].spilled_ptr; + if (!reg->id || reg->type != SCALAR_VALUE) + continue; + if (reg_id_scratch_push(precise_ids, reg->id)) + return; + } + } + + for (fr = 0; fr <= st->curframe; ++fr) { + func = st->frame[fr]; + + for (i = BPF_REG_0; i < BPF_REG_10; ++i) { + reg = &func->regs[i]; + if (!reg->id) + continue; + if (!reg_id_scratch_contains(precise_ids, reg->id)) + continue; + bt_set_frame_reg(bt, fr, i); + } + for (i = 0; i < func->allocated_stack / BPF_REG_SIZE; ++i) { + if (!is_spilled_scalar_reg(&func->stack[i])) + continue; + reg = &func->stack[i].spilled_ptr; + if (!reg->id) + continue; + if (!reg_id_scratch_contains(precise_ids, reg->id)) + continue; + bt_set_frame_slot(bt, fr, i); + } + } +} + /* * __mark_chain_precision() backtracks BPF program instruction sequence and * chain of verifier states making sure that register *regno* (if regno >= 0) @@ -3910,6 +4000,30 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno) bt->frame, last_idx, first_idx, subseq_idx); } + /* If some register with scalar ID is marked as precise, + * make sure that all registers sharing this ID are also precise. + * This is needed to estimate effect of find_equal_scalars(). + * Do this at the last instruction of each state, + * bpf_reg_state::id fields are valid for these instructions. + * + * Allows to track precision in situation like below: + * + * r2 = unknown value + * ... + * --- state #0 --- + * ... + * r1 = r2 // r1 and r2 now share the same ID + * ... + * --- state #1 {r1.id = A, r2.id = A} --- + * ... + * if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 + * ... + * --- state #2 {r1.id = A, r2.id = A} --- + * r3 = r10 + * r3 += r1 // need to mark both r1 and r2 + */ + mark_precise_scalar_ids(env, st); + if (last_idx < 0) { /* we are at the entry into subprog, which * is expected for global funcs, but only if diff --git a/tools/testing/selftests/bpf/verifier/precise.c b/tools/testing/selftests/bpf/verifier/precise.c index b8c0aae8e7ec..99272bb890da 100644 --- a/tools/testing/selftests/bpf/verifier/precise.c +++ b/tools/testing/selftests/bpf/verifier/precise.c @@ -46,7 +46,7 @@ mark_precise: frame0: regs=r2 stack= before 20\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 19 first_idx 10\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: regs=r0,r9 stack= before 15\ @@ -106,10 +106,10 @@ mark_precise: frame0: regs=r2 stack= before 22\ mark_precise: frame0: parent state regs=r2 stack=:\ mark_precise: frame0: last_idx 20 first_idx 20\ - mark_precise: frame0: regs=r2 stack= before 20\ - mark_precise: frame0: parent state regs=r2 stack=:\ + mark_precise: frame0: regs=r2,r9 stack= before 20\ + mark_precise: frame0: parent state regs=r2,r9 stack=:\ mark_precise: frame0: last_idx 19 first_idx 17\ - mark_precise: frame0: regs=r2 stack= before 19\ + mark_precise: frame0: regs=r2,r9 stack= before 19\ mark_precise: frame0: regs=r9 stack= before 18\ mark_precise: frame0: regs=r8,r9 stack= before 17\ mark_precise: frame0: parent state regs= stack=:",
Change mark_chain_precision() to track precision in situations like below: r2 = unknown value ... --- state #0 --- ... r1 = r2 // r1 and r2 now share the same ID ... --- state #1 {r1.id = A, r2.id = A} --- ... if (r2 > 10) goto exit; // find_equal_scalars() assigns range to r1 ... --- state #2 {r1.id = A, r2.id = A} --- r3 = r10 r3 += r1 // need to mark both r1 and r2 At the beginning of the processing of each state, ensure that if a register with a scalar ID is marked as precise, all registers sharing this ID are also marked as precise. This property would be used by a follow-up change in regsafe(). Signed-off-by: Eduard Zingerman <eddyz87@gmail.com> --- include/linux/bpf_verifier.h | 10 +- kernel/bpf/verifier.c | 114 ++++++++++++++++++ .../testing/selftests/bpf/verifier/precise.c | 8 +- 3 files changed, 127 insertions(+), 5 deletions(-)