[RFC,bpf-next] bpf, tnums: add bitwise-not helper

Commit Message

Shung-Hsi Yu Nov. 6, 2023, 2:11 a.m. UTC

Note: Andrii' patch mentioned in the Link tag isn't merge yet, I'll
      resend this along with the proposed refactoring once it is merged.
      For now, sending the patch as RFC for feedback and review.

While the BPF instruction set does not contain a bitwise-NOT
instruction, the verifier may still need to compute the bitwise-NOT
result for the value tracked in the register. One such case reference in
the link below is

	u64 val;
	val = reg_const_value(reg2, is_jmp32);
	tnum_ops(..., tnum_const(~val);

Where the value is extract of out tnum, operated with bitwise-NOT, then
simply turned back into tnum again; plus it has the limitation of only
working on constant. This commit adds the tnum_not() helper that compute
the bitwise-NOT result for all the values tracked within the tnum, that
allow us to simplify the above code to

	tnum_ops(..., tnum_not(reg2->var_off));

without being limited to constant, and is general enough to be reused
and composed with other tnum operations.

Link: https://lore.kernel.org/bpf/ZUSwQtfjCsKpbWcL@u94a/
Signed-off-by: Shung-Hsi Yu <[e-mail]>
---

 include/linux/tnum.h | 2 ++
 kernel/bpf/tnum.c    | 5 +++++
 2 files changed, 7 insertions(+)


base-commit: 1a119e269dc69e82217525d92a93e082c4424fc8

Comments

Andrii Nakryiko Nov. 6, 2023, 7:56 p.m. UTC | #1

On Sun, Nov 5, 2023 at 6:11 PM Shung-Hsi Yu <[e-mail]> wrote:
>
> Note: Andrii' patch mentioned in the Link tag isn't merge yet, I'll
>       resend this along with the proposed refactoring once it is merged.
>       For now, sending the patch as RFC for feedback and review.
>
> While the BPF instruction set does not contain a bitwise-NOT
> instruction, the verifier may still need to compute the bitwise-NOT
> result for the value tracked in the register. One such case reference in
> the link below is
>
>         u64 val;
>         val = reg_const_value(reg2, is_jmp32);
>         tnum_ops(..., tnum_const(~val);
>
> Where the value is extract of out tnum, operated with bitwise-NOT, then
> simply turned back into tnum again; plus it has the limitation of only
> working on constant. This commit adds the tnum_not() helper that compute
> the bitwise-NOT result for all the values tracked within the tnum, that
> allow us to simplify the above code to
>
>         tnum_ops(..., tnum_not(reg2->var_off));
>
> without being limited to constant, and is general enough to be reused
> and composed with other tnum operations.
>
> Link: https://lore.kernel.org/bpf/ZUSwQtfjCsKpbWcL@u94a/
> Signed-off-by: Shung-Hsi Yu <[e-mail]>
> ---
>
>  include/linux/tnum.h | 2 ++
>  kernel/bpf/tnum.c    | 5 +++++
>  2 files changed, 7 insertions(+)
>
> diff --git a/include/linux/tnum.h b/include/linux/tnum.h
> index 1c3948a1d6ad..817065df1297 100644
> --- a/include/linux/tnum.h
> +++ b/include/linux/tnum.h
> @@ -46,6 +46,8 @@ struct tnum tnum_and(struct tnum a, struct tnum b);
>  struct tnum tnum_or(struct tnum a, struct tnum b);
>  /* Bitwise-XOR, return @a ^ @b */
>  struct tnum tnum_xor(struct tnum a, struct tnum b);
> +/* Bitwise-NOT, return ~@a */
> +struct tnum tnum_not(struct tnum a);
>  /* Multiply two tnums, return @a * @b */
>  struct tnum tnum_mul(struct tnum a, struct tnum b);
>
> diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> index 3d7127f439a1..b4f4a4beb0c9 100644
> --- a/kernel/bpf/tnum.c
> +++ b/kernel/bpf/tnum.c
> @@ -111,6 +111,11 @@ struct tnum tnum_xor(struct tnum a, struct tnum b)
>         return TNUM(v & ~mu, mu);
>  }
>
> +struct tnum tnum_not(struct tnum a)
> +{
> +       return TNUM(~a.value & ~a.mask, a.mask);
> +}
> +

In isolation this does look like it's implementing the tnum version of
~x, so I have no objections to this. But I'm not sure it actually
simplifies anything in my patches. But let's see, once it lands,
please send a follow up applying this tnum_not().


>  /* Generate partial products by multiplying each bit in the multiplier (tnum a)
>   * with the multiplicand (tnum b), and add the partial products after
>   * appropriately bit-shifting them. Instead of directly performing tnum addition
>
> base-commit: 1a119e269dc69e82217525d92a93e082c4424fc8
> --
> 2.42.0
>

Shung-Hsi Yu Nov. 7, 2023, 4:43 a.m. UTC | #2

On Mon, Nov 06, 2023 at 11:56:22AM -0800, Andrii Nakryiko wrote:
> On Sun, Nov 5, 2023 at 6:11 PM Shung-Hsi Yu <[e-mail]> wrote:
> > Note: Andrii' patch mentioned in the Link tag isn't merge yet, I'll
> >       resend this along with the proposed refactoring once it is merged.
> >       For now, sending the patch as RFC for feedback and review.
> >
> > While the BPF instruction set does not contain a bitwise-NOT
> > instruction, the verifier may still need to compute the bitwise-NOT
> > result for the value tracked in the register. One such case reference in
> > the link below is
> >
> >         u64 val;
> >         val = reg_const_value(reg2, is_jmp32);
> >         tnum_ops(..., tnum_const(~val);
> >
> > Where the value is extract of out tnum, operated with bitwise-NOT, then
> > simply turned back into tnum again; plus it has the limitation of only
> > working on constant. This commit adds the tnum_not() helper that compute
> > the bitwise-NOT result for all the values tracked within the tnum, that
> > allow us to simplify the above code to
> >
> >         tnum_ops(..., tnum_not(reg2->var_off));
> >
> > without being limited to constant, and is general enough to be reused
> > and composed with other tnum operations.
> >
> > Link: https://lore.kernel.org/bpf/ZUSwQtfjCsKpbWcL@u94a/
> > Signed-off-by: Shung-Hsi Yu <[e-mail]>
> > ---

[...]

> > diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
> > index 3d7127f439a1..b4f4a4beb0c9 100644
> > --- a/kernel/bpf/tnum.c
> > +++ b/kernel/bpf/tnum.c
> > @@ -111,6 +111,11 @@ struct tnum tnum_xor(struct tnum a, struct tnum b)
> >         return TNUM(v & ~mu, mu);
> >  }
> >
> > +struct tnum tnum_not(struct tnum a)
> > +{
> > +       return TNUM(~a.value & ~a.mask, a.mask);
> > +}
> > +
> 
> In isolation this does look like it's implementing the tnum version of
> ~x, so I have no objections to this. But I'm not sure it actually
> simplifies anything in my patches. But let's see, once it lands,
> please send a follow up applying this tnum_not().

Okay, will send once it lands.

[...]

Patch

diff --git a/include/linux/tnum.h b/include/linux/tnum.h
index 1c3948a1d6ad..817065df1297 100644
--- a/include/linux/tnum.h
+++ b/include/linux/tnum.h
@@ -46,6 +46,8 @@  struct tnum tnum_and(struct tnum a, struct tnum b);
 struct tnum tnum_or(struct tnum a, struct tnum b);
 /* Bitwise-XOR, return @a ^ @b */
 struct tnum tnum_xor(struct tnum a, struct tnum b);
+/* Bitwise-NOT, return ~@a */
+struct tnum tnum_not(struct tnum a);
 /* Multiply two tnums, return @a * @b */
 struct tnum tnum_mul(struct tnum a, struct tnum b);
 
diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c
index 3d7127f439a1..b4f4a4beb0c9 100644
--- a/kernel/bpf/tnum.c
+++ b/kernel/bpf/tnum.c
@@ -111,6 +111,11 @@  struct tnum tnum_xor(struct tnum a, struct tnum b)
 	return TNUM(v & ~mu, mu);
 }
 
+struct tnum tnum_not(struct tnum a)
+{
+	return TNUM(~a.value & ~a.mask, a.mask);
+}
+
 /* Generate partial products by multiplying each bit in the multiplier (tnum a)
  * with the multiplicand (tnum b), and add the partial products after
  * appropriately bit-shifting them. Instead of directly performing tnum addition