On Thu, 2023-06-08 at 08:43 -0700, Alexei Starovoitov wrote:
> On Thu, Jun 8, 2023 at 5:35 AM Eduard Zingerman <eddyz87@xxxxxxxxx> 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@xxxxxxxxx> 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@xxxxxxxxx>
> > > > ---
> > > > 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.
