Re: [PATCH bpf-next 01/13] bpf: generalize reg_set_min_max() to handle non-const register comparisons

Andrii Nakryiko
2023-11-03T20:39:51Z

On Fri, Nov 3, 2023 at 9:20 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Thu, 2023-11-02 at 17:08 -0700, Andrii Nakryiko wrote:
> > Generalize bounds adjustment logic of reg_set_min_max() to handle not
> > just register vs constant case, but in general any register vs any
> > register cases. For most of the operations it's trivial extension based
> > on range vs range comparison logic, we just need to properly pick
> > min/max of a range to compare against min/max of the other range.
> >
> > For BPF_JSET we keep the original capabilities, just make sure JSET is
> > integrated in the common framework. This is manifested in the
> > internal-only BPF_KSET + BPF_X "opcode" to allow for simpler and more
> > uniform rev_opcode() handling. See the code for details. This allows to
> > reuse the same code exactly both for TRUE and FALSE branches without
> > explicitly handling both conditions with custom code.
> >
> > Note also that now we don't need a special handling of BPF_JEQ/BPF_JNE
> > case none of the registers are constants. This is now just a normal
> > generic case handled by reg_set_min_max().
> >
> > To make tnum handling cleaner, tnum_with_subreg() helper is added, as
> > that's a common operator when dealing with 32-bit subregister bounds.
> > This keeps the overall logic much less noisy when it comes to tnums.
> >
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>
> (With one bit of a bikeshedding below).
>
> > ---
> > include/linux/tnum.h | 4 +
> > kernel/bpf/tnum.c | 7 +-
> > kernel/bpf/verifier.c | 327 ++++++++++++++++++++----------------------
> > 3 files changed, 165 insertions(+), 173 deletions(-)
> >

please trim irrelevant parts

[...]

> > case BPF_JSGE:
> > + if (is_jmp32) {
> > + reg1->s32_min_value = max(reg1->s32_min_value, reg2->s32_min_value);
> > + reg2->s32_max_value = min(reg1->s32_max_value, reg2->s32_max_value);
> > + } else {
> > + reg1->smin_value = max(reg1->smin_value, reg2->smin_value);
> > + reg2->smax_value = min(reg1->smax_value, reg2->smax_value);
> > + }
> > + break;
> > case BPF_JSGT:
>
> It is possible to spare some code by swapping arguments here:
>
> case BPF_JLE:
> case BPF_JLT:
> case BPF_JSLE:
> case BPF_JSLT:
> return regs_refine_cond_op(reg2, reg1, flip_opcode(opcode), is_jmp32);

yep, math is nice like that :) I'm a bit hesitant to add
recursive-looking calls (even though it's not recursion), so maybe
I'll just do:

case BPF_JLE:
case BPF_JLT:
case BPF_JSLE:
case BPF_JSLT:
opcode = flip_opcode(opcode);
swap(reg1, reg2);
goto again;

and goto again will just jump to the beginning of this function?

Oh, and I more naturally think about LT/LE as "base conditions", so
I'll do the above for GE/GT operations.

>
>
> > - {
> > if (is_jmp32) {
> > - s32 false_smax = opcode == BPF_JSGT ? sval32 : sval32 - 1;
> > - s32 true_smin = opcode == BPF_JSGT ? sval32 + 1 : sval32;
> > -
> > - false_reg1->s32_max_value = min(false_reg1->s32_max_value, false_smax);
> > - true_reg1->s32_min_value = max(true_reg1->s32_min_value, true_smin);
> > + reg1->s32_min_value = max(reg1->s32_min_value, reg2->s32_min_value + 1);
> > + reg2->s32_max_value = min(reg1->s32_max_value - 1, reg2->s32_max_value); …