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.
