From: Kumar Kartikeya Dwivedi <memxor@gmail.com>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: bpf@vger.kernel.org, Alexei Starovoitov <ast@kernel.org>,
Andrii Nakryiko <andrii@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Dave Marchevsky <davemarchevsky@fb.com>,
Delyan Kratunov <delyank@fb.com>
Subject: Re: [PATCH RFC bpf-next v1 12/32] bpf: Teach verifier about non-size constant arguments
Date: Thu, 8 Sep 2022 04:49:56 +0200 [thread overview]
Message-ID: <CAP01T76wapPi8nGVQLTVVtFPRTf-UFT63=x_+hSRB-oqr+w71g@mail.gmail.com> (raw)
In-Reply-To: <20220907221124.3dmeq2e5lf3mzijd@macbook-pro-4.dhcp.thefacebook.com>
On Thu, 8 Sept 2022 at 00:11, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Sun, Sep 04, 2022 at 10:41:25PM +0200, Kumar Kartikeya Dwivedi wrote:
> > Currently, the verifier has support for various arguments that either
> > describe the size of the memory being passed in to a helper, or describe
> > the size of the memory being returned. When a constant is passed in like
> > this, it is assumed for the purposes of precision tracking that if the
> > value in the already explored safe state is within the value in current
> > state, it would fine to prune the search.
> >
> > While this holds well for size arguments, arguments where each value may
> > denote a distinct meaning and needs to be verified separately needs more
> > work. Search can only be pruned if both are constant values and both are
> > equal. In all other cases, it would be incorrect to treat those two
> > precise registers as equivalent if the new value satisfies the old one
> > (i.e. old <= cur).
> >
> > Hence, make the register precision marker tri-state. There are now three
> > values that reg->precise takes: NOT_PRECISE, PRECISE, PRECISE_ABSOLUTE.
> >
> > Both PRECISE and PRECISE_ABSOLUTE are 'true' values. PRECISE_ABSOLUTE
> > affects how regsafe decides whether both registers are equivalent for
> > the purposes of verifier state equivalence. When it sees that one
> > register has reg->precise == PRECISE_ABSOLUTE, unless both are absolute,
> > it will return false. When both are, it returns true only when both are
> > const and both have the same value. Otherwise, for PRECISE case it falls
> > back to the default check that is present now (i.e. thinking that we're
> > talking about sizes).
> >
> > This is required as a future patch introduces a BPF memory allocator
> > interface, where we take the program BTF's type ID as an argument. Each
> > distinct type ID may result in the returned pointer obtaining a
> > different size, hence precision tracking is needed, and pruning cannot
> > just happen when the old value is within the current value. It must only
> > happen when the type ID is equal. The type ID will always correspond to
> > prog->aux->btf hence actual type match is not required.
> >
> > Finally, change mark_chain_precision to mark_chain_precision_absolute
> > for kfuncs constant non-size scalar arguments (tagged with __k suffix).
> >
> > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> > ---
> > include/linux/bpf_verifier.h | 8 +++-
> > kernel/bpf/verifier.c | 93 ++++++++++++++++++++++++++----------
> > 2 files changed, 76 insertions(+), 25 deletions(-)
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index b4a11ff56054..c4d21568d192 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -43,6 +43,12 @@ enum bpf_reg_liveness {
> > REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */
> > };
> >
> > +enum bpf_reg_precise {
> > + NOT_PRECISE,
> > + PRECISE,
> > + PRECISE_ABSOLUTE,
> > +};
>
> Can we make it less verbose ?
>
> NOT_PRECISE,
> PRECISE,
> EXACT
>
Yes, looks better.
> > +
> > struct bpf_reg_state {
> > /* Ordering of fields matters. See states_equal() */
> > enum bpf_reg_type type;
> > @@ -180,7 +186,7 @@ struct bpf_reg_state {
> > s32 subreg_def;
> > enum bpf_reg_liveness live;
> > /* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
> > - bool precise;
> > + enum bpf_reg_precise precise;
>
> Have been thinking whether
> bool precise;
> bool exact;
> would be better,
> but doesn't look like it.
>
> > };
> >
> > enum bpf_stack_slot_type {
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index b28e88d6fabd..571790ac58d4 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -838,7 +838,7 @@ static void print_verifier_state(struct bpf_verifier_env *env,
> > print_liveness(env, reg->live);
> > verbose(env, "=");
> > if (t == SCALAR_VALUE && reg->precise)
> > - verbose(env, "P");
> > + verbose(env, reg->precise == PRECISE_ABSOLUTE ? "PA" : "P");
>
> and here it would be just 'E'
>
> > if ((t == SCALAR_VALUE || t == PTR_TO_STACK) &&
> > tnum_is_const(reg->var_off)) {
> > /* reg->off should be 0 for SCALAR_VALUE */
> > @@ -935,7 +935,7 @@ static void print_verifier_state(struct bpf_verifier_env *env,
> > t = reg->type;
> > verbose(env, "=%s", t == SCALAR_VALUE ? "" : reg_type_str(env, t));
> > if (t == SCALAR_VALUE && reg->precise)
> > - verbose(env, "P");
> > + verbose(env, reg->precise == PRECISE_ABSOLUTE ? "PA" : "P");
> > if (t == SCALAR_VALUE && tnum_is_const(reg->var_off))
> > verbose(env, "%lld", reg->var_off.value + reg->off);
> > } else {
> > @@ -1668,7 +1668,17 @@ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
> > reg->type = SCALAR_VALUE;
> > reg->var_off = tnum_unknown;
> > reg->frameno = 0;
> > - reg->precise = env->subprog_cnt > 1 || !env->bpf_capable;
> > + /* Helpers requiring PRECISE_ABSOLUTE for constant arguments cannot be
> > + * called from programs without CAP_BPF. This is because we don't
> > + * propagate precision markers for when CAP_BPF is missing. If we
> > + * allowed calling such heleprs in those programs, the default would
> > + * have to be PRECISE_ABSOLUTE for them, which would be too aggresive.
> > + *
> > + * We still propagate PRECISE_ABSOLUTE when subprog_cnt > 1, hence
> > + * those cases would still override the default PRECISE value when
> > + * we propagate the precision markers.
> > + */
> > + reg->precise = (env->subprog_cnt > 1 || !env->bpf_capable) ? PRECISE : NOT_PRECISE;
> > __mark_reg_unbounded(reg);
> > }
> >
> > @@ -2717,7 +2727,8 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx,
> > * For now backtracking falls back into conservative marking.
> > */
> > static void mark_all_scalars_precise(struct bpf_verifier_env *env,
> > - struct bpf_verifier_state *st)
> > + struct bpf_verifier_state *st,
> > + bool absolute)
> > {
> > struct bpf_func_state *func;
> > struct bpf_reg_state *reg;
> > @@ -2733,7 +2744,7 @@ static void mark_all_scalars_precise(struct bpf_verifier_env *env,
> > reg = &func->regs[j];
> > if (reg->type != SCALAR_VALUE)
> > continue;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > }
> > for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
> > if (!is_spilled_reg(&func->stack[j]))
> > @@ -2741,13 +2752,13 @@ static void mark_all_scalars_precise(struct bpf_verifier_env *env,
> > reg = &func->stack[j].spilled_ptr;
> > if (reg->type != SCALAR_VALUE)
> > continue;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > }
> > }
> > }
> >
> > static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > - int spi)
> > + int spi, bool absolute)
>
> instead of bool pls pass enum bpf_reg_precise
>
> > {
> > struct bpf_verifier_state *st = env->cur_state;
> > int first_idx = st->first_insn_idx;
> > @@ -2774,7 +2785,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > new_marks = true;
> > else
> > reg_mask = 0;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > }
> >
> > while (spi >= 0) {
> > @@ -2791,7 +2802,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > new_marks = true;
> > else
> > stack_mask = 0;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > break;
> > }
> >
> > @@ -2813,7 +2824,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > err = backtrack_insn(env, i, ®_mask, &stack_mask);
> > }
> > if (err == -ENOTSUPP) {
> > - mark_all_scalars_precise(env, st);
> > + mark_all_scalars_precise(env, st, absolute);
> > return 0;
> > } else if (err) {
> > return err;
> > @@ -2854,7 +2865,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > }
> > if (!reg->precise)
> > new_marks = true;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > }
> >
> > bitmap_from_u64(mask, stack_mask);
> > @@ -2873,7 +2884,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > * fp-8 and it's "unallocated" stack space.
> > * In such case fallback to conservative.
> > */
> > - mark_all_scalars_precise(env, st);
> > + mark_all_scalars_precise(env, st, absolute);
> > return 0;
> > }
> >
> > @@ -2888,7 +2899,7 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> > }
> > if (!reg->precise)
> > new_marks = true;
> > - reg->precise = true;
> > + reg->precise = absolute ? PRECISE_ABSOLUTE : PRECISE;
> > }
> > if (env->log.level & BPF_LOG_LEVEL2) {
> > verbose(env, "parent %s regs=%x stack=%llx marks:",
> > @@ -2910,12 +2921,24 @@ static int __mark_chain_precision(struct bpf_verifier_env *env, int regno,
> >
> > static int mark_chain_precision(struct bpf_verifier_env *env, int regno)
> > {
> > - return __mark_chain_precision(env, regno, -1);
> > + return __mark_chain_precision(env, regno, -1, false);
> > +}
> > +
> > +static int mark_chain_precision_absolute(struct bpf_verifier_env *env, int regno)
> > +{
> > + WARN_ON_ONCE(!env->bpf_capable);
> > + return __mark_chain_precision(env, regno, -1, true);
> > }
> >
> > static int mark_chain_precision_stack(struct bpf_verifier_env *env, int spi)
> > {
> > - return __mark_chain_precision(env, -1, spi);
> > + return __mark_chain_precision(env, -1, spi, false);
> > +}
>
> No need to fork the functions so much.
> Just add enum bpf_reg_precise to existing two functions.
>
> > +
> > +static int mark_chain_precision_absolute_stack(struct bpf_verifier_env *env, int spi)
> > +{
> > + WARN_ON_ONCE(!env->bpf_capable);
> > + return __mark_chain_precision(env, -1, spi, true);
> > }
> >
> > static bool is_spillable_regtype(enum bpf_reg_type type)
> > @@ -3253,7 +3276,7 @@ static void mark_reg_stack_read(struct bpf_verifier_env *env,
> > * backtracking. Any register that contributed
> > * to const 0 was marked precise before spill.
> > */
> > - state->regs[dst_regno].precise = true;
> > + state->regs[dst_regno].precise = PRECISE;
> > } else {
> > /* have read misc data from the stack */
> > mark_reg_unknown(env, state->regs, dst_regno);
> > @@ -7903,7 +7926,7 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_arg_m
> > verbose(env, "R%d must be a known constant\n", regno);
> > return -EINVAL;
> > }
> > - ret = mark_chain_precision(env, regno);
> > + ret = mark_chain_precision_absolute(env, regno);
> > if (ret < 0)
> > return ret;
> > meta->arg_constant.found = true;
> > @@ -11899,9 +11922,23 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> > if (rcur->type == SCALAR_VALUE) {
> > if (!rold->precise && !rcur->precise)
> > return true;
> > - /* new val must satisfy old val knowledge */
> > - return range_within(rold, rcur) &&
> > - tnum_in(rold->var_off, rcur->var_off);
> > + /* We can only determine safety when type of precision
> > + * needed is same. For absolute, we must compare actual
> > + * value, otherwise old being within the current value
> > + * suffices.
> > + */
> > + if (rold->precise == PRECISE_ABSOLUTE || rcur->precise == PRECISE_ABSOLUTE) {
> > + /* Both should be PRECISE_ABSOLUTE for a comparison */
> > + if (rold->precise != rcur->precise)
> > + return false;
> > + if (!tnum_is_const(rold->var_off) || !tnum_is_const(rcur->var_off))
> > + return false;
> > + return rold->var_off.value == rcur->var_off.value;
>
> Probably better to do
> if (rold->precise == EXACT || rcu->precise == EXACT)
> return false;
>
> because
> if (equal)
> return true;
> should have already happened if they were exact match.
>
I'll add a comment about that, just to make it clear.
and I agree with all the suggestions.
next prev parent reply other threads:[~2022-09-08 2:50 UTC|newest]
Thread overview: 82+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-04 20:41 [PATCH RFC bpf-next v1 00/32] Local kptrs, BPF linked lists Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 01/32] bpf: Add copy_map_value_long to copy to remote percpu memory Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 02/32] bpf: Support kptrs in percpu arraymap Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 03/32] bpf: Add zero_map_value to zero map value with special fields Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 04/32] bpf: Support kptrs in percpu hashmap and percpu LRU hashmap Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 05/32] bpf: Support kptrs in local storage maps Kumar Kartikeya Dwivedi
2022-09-07 19:00 ` Alexei Starovoitov
2022-09-08 2:47 ` Kumar Kartikeya Dwivedi
2022-09-09 5:27 ` Martin KaFai Lau
2022-09-09 11:22 ` Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 06/32] bpf: Annotate data races in bpf_local_storage Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 07/32] bpf: Allow specifying volatile type modifier for kptrs Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 08/32] bpf: Add comment about kptr's PTR_TO_MAP_VALUE handling Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 09/32] bpf: Rewrite kfunc argument handling Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 10/32] bpf: Drop kfunc support from btf_check_func_arg_match Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 11/32] bpf: Support constant scalar arguments for kfuncs Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 12/32] bpf: Teach verifier about non-size constant arguments Kumar Kartikeya Dwivedi
2022-09-07 22:11 ` Alexei Starovoitov
2022-09-08 2:49 ` Kumar Kartikeya Dwivedi [this message]
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 13/32] bpf: Introduce bpf_list_head support for BPF maps Kumar Kartikeya Dwivedi
2022-09-07 22:46 ` Alexei Starovoitov
2022-09-08 2:58 ` Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 14/32] bpf: Introduce bpf_kptr_alloc helper Kumar Kartikeya Dwivedi
2022-09-07 23:30 ` Alexei Starovoitov
2022-09-08 3:01 ` Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 15/32] bpf: Add helper macro bpf_expr_for_each_reg_in_vstate Kumar Kartikeya Dwivedi
2022-09-07 23:48 ` Alexei Starovoitov
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 16/32] bpf: Introduce BPF memory object model Kumar Kartikeya Dwivedi
2022-09-08 0:34 ` Alexei Starovoitov
2022-09-08 2:39 ` Kumar Kartikeya Dwivedi
2022-09-08 3:37 ` Alexei Starovoitov
2022-09-08 11:50 ` Kumar Kartikeya Dwivedi
2022-09-08 14:18 ` Alexei Starovoitov
2022-09-08 14:45 ` Kumar Kartikeya Dwivedi
2022-09-08 15:11 ` Alexei Starovoitov
2022-09-08 15:37 ` Kumar Kartikeya Dwivedi
2022-09-08 15:59 ` Alexei Starovoitov
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 17/32] bpf: Support bpf_list_node in local kptrs Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 18/32] bpf: Support bpf_spin_lock " Kumar Kartikeya Dwivedi
2022-09-08 0:35 ` Alexei Starovoitov
2022-09-09 8:25 ` Dave Marchevsky
2022-09-09 11:20 ` Kumar Kartikeya Dwivedi
2022-09-09 14:26 ` Alexei Starovoitov
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 19/32] bpf: Support bpf_list_head " Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 20/32] bpf: Introduce bpf_kptr_free helper Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 21/32] bpf: Allow locking bpf_spin_lock global variables Kumar Kartikeya Dwivedi
2022-09-08 0:27 ` Alexei Starovoitov
2022-09-08 0:39 ` Kumar Kartikeya Dwivedi
2022-09-08 0:55 ` Alexei Starovoitov
2022-09-08 1:00 ` Kumar Kartikeya Dwivedi
2022-09-08 1:08 ` Alexei Starovoitov
2022-09-08 1:15 ` Kumar Kartikeya Dwivedi
2022-09-08 2:39 ` Alexei Starovoitov
2022-09-09 8:13 ` Dave Marchevsky
2022-09-09 11:05 ` Kumar Kartikeya Dwivedi
2022-09-09 14:24 ` Alexei Starovoitov
2022-09-09 14:50 ` Kumar Kartikeya Dwivedi
2022-09-09 14:58 ` Alexei Starovoitov
2022-09-09 18:32 ` Andrii Nakryiko
2022-09-09 19:25 ` Alexei Starovoitov
2022-09-09 20:21 ` Andrii Nakryiko
2022-09-09 20:57 ` Alexei Starovoitov
2022-09-10 0:21 ` Andrii Nakryiko
2022-09-11 22:31 ` Alexei Starovoitov
2022-09-20 20:55 ` Andrii Nakryiko
2022-10-18 4:06 ` Andrii Nakryiko
2022-09-09 22:30 ` Dave Marchevsky
2022-09-09 22:49 ` Kumar Kartikeya Dwivedi
2022-09-09 22:57 ` Alexei Starovoitov
2022-09-09 23:04 ` Kumar Kartikeya Dwivedi
2022-09-09 22:51 ` Alexei Starovoitov
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 22/32] bpf: Bump BTF_KFUNC_SET_MAX_CNT Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 23/32] bpf: Add single ownership BPF linked list API Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 24/32] bpf: Permit NULL checking pointer with non-zero fixed offset Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 25/32] bpf: Allow storing local kptrs in BPF maps Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 26/32] bpf: Wire up freeing of bpf_list_heads in maps Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 27/32] bpf: Add destructor for bpf_list_head in local kptr Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 28/32] bpf: Remove duplicate PTR_TO_BTF_ID RO check Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 29/32] libbpf: Add support for private BSS map section Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 30/32] selftests/bpf: Add BTF tag macros for local kptrs, BPF linked lists Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 31/32] selftests/bpf: Add BPF linked list API tests Kumar Kartikeya Dwivedi
2022-09-04 20:41 ` [PATCH RFC bpf-next v1 32/32] selftests/bpf: Add referenced local kptr tests Kumar Kartikeya Dwivedi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAP01T76wapPi8nGVQLTVVtFPRTf-UFT63=x_+hSRB-oqr+w71g@mail.gmail.com' \
--to=memxor@gmail.com \
--cc=alexei.starovoitov@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=davemarchevsky@fb.com \
--cc=delyank@fb.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.