[bpf-next,v2,14/15] bpf: Optimize state pruning for spilled scalars

Commit Message

Maxim Mikityanskiy Jan. 8, 2024, 8:52 p.m. UTC

From: Eduard Zingerman <[e-mail]>

Changes for scalar ID tracking of spilled unbound scalars lead to
certain verification performance regression. This commit mitigates the
regression by exploiting the following properties maintained by
check_stack_read_fixed_off():
- a mix of STACK_MISC, STACK_ZERO and STACK_INVALID marks is read as
  unbounded scalar register;
- spi with all slots marked STACK_ZERO is read as scalar register with
  value zero.

This commit modifies stacksafe() to consider situations above
equivalent.

Veristat results after this patch show significant gains:

$ ./veristat -e file,prog,states -f '!states_pct<10' -f '!states_b<10' -C not-opt after
File              Program   States (A)  States (B)  States    (DIFF)
----------------  --------  ----------  ----------  ----------------
pyperf180.bpf.o   on_event       10456        8422   -2034 (-19.45%)
pyperf600.bpf.o   on_event       37319       22519  -14800 (-39.66%)
strobemeta.bpf.o  on_event       13435        4703   -8732 (-64.99%)

Signed-off-by: Eduard Zingerman <[e-mail]>
---
 kernel/bpf/verifier.c | 83 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

Comments

Andrii Nakryiko Jan. 10, 2024, 12:22 a.m. UTC | #1

On Mon, Jan 8, 2024 at 12:53 PM Maxim Mikityanskiy <[e-mail]> wrote:
>
> From: Eduard Zingerman <[e-mail]>
>
> Changes for scalar ID tracking of spilled unbound scalars lead to
> certain verification performance regression. This commit mitigates the
> regression by exploiting the following properties maintained by
> check_stack_read_fixed_off():
> - a mix of STACK_MISC, STACK_ZERO and STACK_INVALID marks is read as
>   unbounded scalar register;
> - spi with all slots marked STACK_ZERO is read as scalar register with
>   value zero.
>
> This commit modifies stacksafe() to consider situations above
> equivalent.
>
> Veristat results after this patch show significant gains:
>
> $ ./veristat -e file,prog,states -f '!states_pct<10' -f '!states_b<10' -C not-opt after
> File              Program   States (A)  States (B)  States    (DIFF)
> ----------------  --------  ----------  ----------  ----------------
> pyperf180.bpf.o   on_event       10456        8422   -2034 (-19.45%)
> pyperf600.bpf.o   on_event       37319       22519  -14800 (-39.66%)
> strobemeta.bpf.o  on_event       13435        4703   -8732 (-64.99%)
>
> Signed-off-by: Eduard Zingerman <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 83 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 83 insertions(+)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index aeb3e198a5ea..cb82f8d4226f 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1170,6 +1170,12 @@ static void mark_stack_slot_misc(struct bpf_verifier_env *env, u8 *stype)
>         *stype = STACK_MISC;
>  }
>
> +static bool is_spilled_scalar_reg64(const struct bpf_stack_state *stack)
> +{
> +       return stack->slot_type[0] == STACK_SPILL &&
> +              stack->spilled_ptr.type == SCALAR_VALUE;
> +}
> +
>  static void scrub_spilled_slot(u8 *stype)
>  {
>         if (*stype != STACK_INVALID)
> @@ -16459,11 +16465,45 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
>         }
>  }
>
> +static bool is_stack_zero64(struct bpf_stack_state *stack)
> +{
> +       u32 i;
> +
> +       for (i = 0; i < ARRAY_SIZE(stack->slot_type); ++i)
> +               if (stack->slot_type[i] != STACK_ZERO)
> +                       return false;
> +       return true;
> +}
> +
> +static bool is_stack_unbound_slot64(struct bpf_verifier_env *env,
> +                                   struct bpf_stack_state *stack)
> +{
> +       u32 i;
> +
> +       for (i = 0; i < ARRAY_SIZE(stack->slot_type); ++i)
> +               if (stack->slot_type[i] != STACK_ZERO &&
> +                   stack->slot_type[i] != STACK_MISC &&
> +                   (!env->allow_uninit_stack || stack->slot_type[i] != STACK_INVALID))
> +                       return false;
> +       return true;
> +}
> +
> +static bool is_spilled_unbound_scalar_reg64(struct bpf_stack_state *stack)
> +{
> +       return is_spilled_scalar_reg64(stack) && __is_scalar_unbounded(&stack->spilled_ptr);
> +}
> +
>  static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>                       struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
>  {
> +       struct bpf_reg_state unbound_reg = {};
> +       struct bpf_reg_state zero_reg = {};
>         int i, spi;
>
> +       __mark_reg_unknown(env, &unbound_reg);
> +       __mark_reg_const_zero(env, &zero_reg);
> +       zero_reg.precise = true;

these are immutable, right? Would it make sense to set them up just
once as static variables instead of initializing on each check?

> +
>         /* walk slots of the explored stack and ignore any additional
>          * slots in the current stack, since explored(safe) state
>          * didn't use them
> @@ -16484,6 +16524,49 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
>                         continue;
>                 }
>

we didn't check that cur->stack[spi] is ok to access yet, it's done a
bit later with `if (i >= cur->allocated_stack)`, if I'm not mistaken.
So these checks would need to be moved a bit lower, probably.

> +               /* load of stack value with all MISC and ZERO slots produces unbounded
> +                * scalar value, call regsafe to ensure scalar ids are compared.
> +                */
> +               if (is_spilled_unbound_scalar_reg64(&old->stack[spi]) &&
> +                   is_stack_unbound_slot64(env, &cur->stack[spi])) {
> +                       i += BPF_REG_SIZE - 1;
> +                       if (!regsafe(env, &old->stack[spi].spilled_ptr, &unbound_reg,
> +                                    idmap, exact))
> +                               return false;
> +                       continue;
> +               }
> +
> +               if (is_stack_unbound_slot64(env, &old->stack[spi]) &&
> +                   is_spilled_unbound_scalar_reg64(&cur->stack[spi])) {
> +                       i += BPF_REG_SIZE - 1;
> +                       if (!regsafe(env,  &unbound_reg, &cur->stack[spi].spilled_ptr,
> +                                    idmap, exact))
> +                               return false;
> +                       continue;
> +               }

scalar_old = scalar_cur = NULL;
if (is_spilled_unbound64(&old->..))
    scalar_old = old->stack[spi].slot_type[0] == STACK_SPILL ?
&old->stack[spi].spilled_ptr : &unbound_reg;
if (is_spilled_unbound64(&cur->..))
    scalar_cur = cur->stack[spi].slot_type[0] == STACK_SPILL ?
&cur->stack[spi].spilled_ptr : &unbound_reg;
if (scalar_old && scalar_cur) {
    if (!regsafe(env, scalar_old, scalar_new, idmap, exact)
        return false;
    i += BPF_REG_SIZE - 1;
    continue;
}

where is_spilled_unbound64() would be basically `return
is_spilled_unbound_scalar_reg64(&old->..) ||
is_stack_unbound_slot64(&old->...)`;

Similarly for zero case? Though I'm wondering if zero case should be
checked first, as it's actually a subset of is_spilled_unbound64 when
it comes to STACK_ZERO/STACK_MISC mixes, no?


> +
> +               /* load of stack value with all ZERO slots produces scalar value 0,
> +                * call regsafe to ensure scalar ids are compared and precision
> +                * flags are taken into account.
> +                */
> +               if (is_spilled_scalar_reg64(&old->stack[spi]) &&
> +                   is_stack_zero64(&cur->stack[spi])) {
> +                       if (!regsafe(env, &old->stack[spi].spilled_ptr, &zero_reg,
> +                                    idmap, exact))
> +                               return false;
> +                       i += BPF_REG_SIZE - 1;
> +                       continue;
> +               }
> +
> +               if (is_stack_zero64(&old->stack[spi]) &&
> +                   is_spilled_scalar_reg64(&cur->stack[spi])) {
> +                       if (!regsafe(env, &zero_reg, &cur->stack[spi].spilled_ptr,
> +                                    idmap, exact))
> +                               return false;
> +                       i += BPF_REG_SIZE - 1;
> +                       continue;
> +               }
> +
>                 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
>                         continue;
>
> --
> 2.43.0
>

Eduard Zingerman Jan. 10, 2024, 9:04 p.m. UTC | #2

On Tue, 2024-01-09 at 16:22 -0800, Andrii Nakryiko wrote:
[...]
> >  static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> >                       struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
> >  {
> > +       struct bpf_reg_state unbound_reg = {};
> > +       struct bpf_reg_state zero_reg = {};
> >         int i, spi;
> > 
> > +       __mark_reg_unknown(env, &unbound_reg);
> > +       __mark_reg_const_zero(env, &zero_reg);
> > +       zero_reg.precise = true;
> 
> these are immutable, right? Would it make sense to set them up just
> once as static variables instead of initializing on each check?

Should be possible.

> > +
> >         /* walk slots of the explored stack and ignore any additional
> >          * slots in the current stack, since explored(safe) state
> >          * didn't use them
> > @@ -16484,6 +16524,49 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> >                         continue;
> >                 }
> > 
> 
> we didn't check that cur->stack[spi] is ok to access yet, it's done a
> bit later with `if (i >= cur->allocated_stack)`, if I'm not mistaken.
> So these checks would need to be moved a bit lower, probably.

Right. And it seems the issue is already present:

		if (exact &&
		    old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
		    cur->stack[spi].slot_type[i % BPF_REG_SIZE])
			return false;

This is currently executed before `if (i >= cur->allocated_stack)` check as well.
Introduced by another commit of mine :(

> > +               /* load of stack value with all MISC and ZERO slots produces unbounded
> > +                * scalar value, call regsafe to ensure scalar ids are compared.
> > +                */
> > +               if (is_spilled_unbound_scalar_reg64(&old->stack[spi]) &&
> > +                   is_stack_unbound_slot64(env, &cur->stack[spi])) {
> > +                       i += BPF_REG_SIZE - 1;
> > +                       if (!regsafe(env, &old->stack[spi].spilled_ptr, &unbound_reg,
> > +                                    idmap, exact))
> > +                               return false;
> > +                       continue;
> > +               }
> > +
> > +               if (is_stack_unbound_slot64(env, &old->stack[spi]) &&
> > +                   is_spilled_unbound_scalar_reg64(&cur->stack[spi])) {
> > +                       i += BPF_REG_SIZE - 1;
> > +                       if (!regsafe(env,  &unbound_reg, &cur->stack[spi].spilled_ptr,
> > +                                    idmap, exact))
> > +                               return false;
> > +                       continue;
> > +               }
> 
> scalar_old = scalar_cur = NULL;
> if (is_spilled_unbound64(&old->..))
>     scalar_old = old->stack[spi].slot_type[0] == STACK_SPILL ?
> &old->stack[spi].spilled_ptr : &unbound_reg;
> if (is_spilled_unbound64(&cur->..))
>     scalar_cur = cur->stack[spi].slot_type[0] == STACK_SPILL ?
> &cur->stack[spi].spilled_ptr : &unbound_reg;
> if (scalar_old && scalar_cur) {
>     if (!regsafe(env, scalar_old, scalar_new, idmap, exact)
>         return false;
>     i += BPF_REG_SIZE - 1;
>     continue;
> }

Ok, I'll switch to this.
(Although, I think old variant is a bit simpler to follow).

> where is_spilled_unbound64() would be basically `return
> is_spilled_unbound_scalar_reg64(&old->..) ||
> is_stack_unbound_slot64(&old->...)`;
> 
> Similarly for zero case? Though I'm wondering if zero case should be
> checked first, as it's actually a subset of is_spilled_unbound64 when
> it comes to STACK_ZERO/STACK_MISC mixes, no?

Yes, makes sense.

[...]

Andrii Nakryiko Jan. 10, 2024, 9:52 p.m. UTC | #3

On Wed, Jan 10, 2024 at 1:04 PM Eduard Zingerman <[e-mail]> wrote:
>
> On Tue, 2024-01-09 at 16:22 -0800, Andrii Nakryiko wrote:
> [...]
> > >  static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> > >                       struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
> > >  {
> > > +       struct bpf_reg_state unbound_reg = {};
> > > +       struct bpf_reg_state zero_reg = {};
> > >         int i, spi;
> > >
> > > +       __mark_reg_unknown(env, &unbound_reg);
> > > +       __mark_reg_const_zero(env, &zero_reg);
> > > +       zero_reg.precise = true;
> >
> > these are immutable, right? Would it make sense to set them up just
> > once as static variables instead of initializing on each check?
>
> Should be possible.
>
> > > +
> > >         /* walk slots of the explored stack and ignore any additional
> > >          * slots in the current stack, since explored(safe) state
> > >          * didn't use them
> > > @@ -16484,6 +16524,49 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
> > >                         continue;
> > >                 }
> > >
> >
> > we didn't check that cur->stack[spi] is ok to access yet, it's done a
> > bit later with `if (i >= cur->allocated_stack)`, if I'm not mistaken.
> > So these checks would need to be moved a bit lower, probably.
>
> Right. And it seems the issue is already present:
>
>                 if (exact &&
>                     old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
>                     cur->stack[spi].slot_type[i % BPF_REG_SIZE])
>                         return false;
>
> This is currently executed before `if (i >= cur->allocated_stack)` check as well.
> Introduced by another commit of mine :(

I guess we'll need to move that too, then

>
> > > +               /* load of stack value with all MISC and ZERO slots produces unbounded
> > > +                * scalar value, call regsafe to ensure scalar ids are compared.
> > > +                */
> > > +               if (is_spilled_unbound_scalar_reg64(&old->stack[spi]) &&
> > > +                   is_stack_unbound_slot64(env, &cur->stack[spi])) {
> > > +                       i += BPF_REG_SIZE - 1;
> > > +                       if (!regsafe(env, &old->stack[spi].spilled_ptr, &unbound_reg,
> > > +                                    idmap, exact))
> > > +                               return false;
> > > +                       continue;
> > > +               }
> > > +
> > > +               if (is_stack_unbound_slot64(env, &old->stack[spi]) &&
> > > +                   is_spilled_unbound_scalar_reg64(&cur->stack[spi])) {
> > > +                       i += BPF_REG_SIZE - 1;
> > > +                       if (!regsafe(env,  &unbound_reg, &cur->stack[spi].spilled_ptr,
> > > +                                    idmap, exact))
> > > +                               return false;
> > > +                       continue;
> > > +               }
> >
> > scalar_old = scalar_cur = NULL;
> > if (is_spilled_unbound64(&old->..))
> >     scalar_old = old->stack[spi].slot_type[0] == STACK_SPILL ?
> > &old->stack[spi].spilled_ptr : &unbound_reg;
> > if (is_spilled_unbound64(&cur->..))
> >     scalar_cur = cur->stack[spi].slot_type[0] == STACK_SPILL ?
> > &cur->stack[spi].spilled_ptr : &unbound_reg;
> > if (scalar_old && scalar_cur) {
> >     if (!regsafe(env, scalar_old, scalar_new, idmap, exact)
> >         return false;
> >     i += BPF_REG_SIZE - 1;
> >     continue;
> > }
>
> Ok, I'll switch to this.
> (Although, I think old variant is a bit simpler to follow).

my goal was to eliminate duplicated logic inside each if and kind of
showing at high level that we are comparing two "logically unbound
scalars", regardless of whether that's STACK_xxx mix or spilled
scalar.

I haven't thought this through, but if we can simplify further to
something like this:

if (is_spilled_unbound64(old) && is_spilled_unbound64(cur)) {
  scalar_cur = ...
  scalar_old = ...
  if (!regsafe(...))
    return false;
  i += BPF_REG_SIZE - 1;
}

In general, this symmetry in two consecutive if conditions seems like
an opportunity to simplify. But if you think it's more complicated,
I'm fine with leaving it as is.

>
> > where is_spilled_unbound64() would be basically `return
> > is_spilled_unbound_scalar_reg64(&old->..) ||
> > is_stack_unbound_slot64(&old->...)`;
> >
> > Similarly for zero case? Though I'm wondering if zero case should be
> > checked first, as it's actually a subset of is_spilled_unbound64 when
> > it comes to STACK_ZERO/STACK_MISC mixes, no?
>
> Yes, makes sense.
>
> [...]

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index aeb3e198a5ea..cb82f8d4226f 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1170,6 +1170,12 @@  static void mark_stack_slot_misc(struct bpf_verifier_env *env, u8 *stype)
 	*stype = STACK_MISC;
 }
 
+static bool is_spilled_scalar_reg64(const struct bpf_stack_state *stack)
+{
+	return stack->slot_type[0] == STACK_SPILL &&
+	       stack->spilled_ptr.type == SCALAR_VALUE;
+}
+
 static void scrub_spilled_slot(u8 *stype)
 {
 	if (*stype != STACK_INVALID)
@@ -16459,11 +16465,45 @@  static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 	}
 }
 
+static bool is_stack_zero64(struct bpf_stack_state *stack)
+{
+	u32 i;
+
+	for (i = 0; i < ARRAY_SIZE(stack->slot_type); ++i)
+		if (stack->slot_type[i] != STACK_ZERO)
+			return false;
+	return true;
+}
+
+static bool is_stack_unbound_slot64(struct bpf_verifier_env *env,
+				    struct bpf_stack_state *stack)
+{
+	u32 i;
+
+	for (i = 0; i < ARRAY_SIZE(stack->slot_type); ++i)
+		if (stack->slot_type[i] != STACK_ZERO &&
+		    stack->slot_type[i] != STACK_MISC &&
+		    (!env->allow_uninit_stack || stack->slot_type[i] != STACK_INVALID))
+			return false;
+	return true;
+}
+
+static bool is_spilled_unbound_scalar_reg64(struct bpf_stack_state *stack)
+{
+	return is_spilled_scalar_reg64(stack) && __is_scalar_unbounded(&stack->spilled_ptr);
+}
+
 static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
 		      struct bpf_func_state *cur, struct bpf_idmap *idmap, bool exact)
 {
+	struct bpf_reg_state unbound_reg = {};
+	struct bpf_reg_state zero_reg = {};
 	int i, spi;
 
+	__mark_reg_unknown(env, &unbound_reg);
+	__mark_reg_const_zero(env, &zero_reg);
+	zero_reg.precise = true;
+
 	/* walk slots of the explored stack and ignore any additional
 	 * slots in the current stack, since explored(safe) state
 	 * didn't use them
@@ -16484,6 +16524,49 @@  static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
 			continue;
 		}
 
+		/* load of stack value with all MISC and ZERO slots produces unbounded
+		 * scalar value, call regsafe to ensure scalar ids are compared.
+		 */
+		if (is_spilled_unbound_scalar_reg64(&old->stack[spi]) &&
+		    is_stack_unbound_slot64(env, &cur->stack[spi])) {
+			i += BPF_REG_SIZE - 1;
+			if (!regsafe(env, &old->stack[spi].spilled_ptr, &unbound_reg,
+				     idmap, exact))
+				return false;
+			continue;
+		}
+
+		if (is_stack_unbound_slot64(env, &old->stack[spi]) &&
+		    is_spilled_unbound_scalar_reg64(&cur->stack[spi])) {
+			i += BPF_REG_SIZE - 1;
+			if (!regsafe(env,  &unbound_reg, &cur->stack[spi].spilled_ptr,
+				     idmap, exact))
+				return false;
+			continue;
+		}
+
+		/* load of stack value with all ZERO slots produces scalar value 0,
+		 * call regsafe to ensure scalar ids are compared and precision
+		 * flags are taken into account.
+		 */
+		if (is_spilled_scalar_reg64(&old->stack[spi]) &&
+		    is_stack_zero64(&cur->stack[spi])) {
+			if (!regsafe(env, &old->stack[spi].spilled_ptr, &zero_reg,
+				     idmap, exact))
+				return false;
+			i += BPF_REG_SIZE - 1;
+			continue;
+		}
+
+		if (is_stack_zero64(&old->stack[spi]) &&
+		    is_spilled_scalar_reg64(&cur->stack[spi])) {
+			if (!regsafe(env, &zero_reg, &cur->stack[spi].spilled_ptr,
+				     idmap, exact))
+				return false;
+			i += BPF_REG_SIZE - 1;
+			continue;
+		}
+
 		if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
 			continue;