[v4,bpf-next,0/4] bpf: Introduce may_goto and cond_break

Message

Alexei Starovoitov March 2, 2024, 2 a.m. UTC

From: Alexei Starovoitov <[e-mail]>

v3 -> v4:
- fix drained issue reported by John.
  may_goto insn could be implemented with sticky state (once
  reaches 0 it stays 0), but the verifier shouldn't assume that.
  It has to explore both branches.
  Arguably drained iterator state shouldn't be there at all.
  bpf_iter_css_next() is not sticky. Can be fixed, but auditing all
  iterators for stickiness. That's an orthogonal discussion.
- explained JMA name reasons in patch 1
- fixed test_progs-no_alu32 issue and added another test

v2 -> v3: Major change
- drop bpf_can_loop() kfunc and introduce may_goto instruction instead
  kfunc is a function call while may_goto doesn't consume any registers
  and LLVM can produce much better code due to less register pressure.
- instead of counting from zero to BPF_MAX_LOOPS start from it instead
  and break out of the loop when count reaches zero
- use may_goto instruction in cond_break macro
- recognize that 'exact' state comparison doesn't need to be truly exact.
  regsafe() should ignore precision and liveness marks, but range_within
  logic is safe to use while evaluating open coded iterators.

Alexei Starovoitov (4):
  bpf: Introduce may_goto instruction
  bpf: Recognize that two registers are safe when their ranges match
  bpf: Add cond_break macro
  selftests/bpf: Test may_goto

 include/linux/bpf_verifier.h                  |   2 +
 include/uapi/linux/bpf.h                      |   1 +
 kernel/bpf/core.c                             |   1 +
 kernel/bpf/disasm.c                           |   3 +
 kernel/bpf/verifier.c                         | 280 +++++++++++++-----
 tools/include/uapi/linux/bpf.h                |   1 +
 tools/testing/selftests/bpf/DENYLIST.s390x    |   1 +
 .../testing/selftests/bpf/bpf_experimental.h  |  12 +
 .../bpf/progs/verifier_iterating_callbacks.c  | 103 ++++++-
 9 files changed, 330 insertions(+), 74 deletions(-)

Comments

Dave Thaler March 4, 2024, 4:45 p.m. UTC | #1

Alexei Starovoitov <[e-mail]> writes:
[...]
> Alexei Starovoitov (4):
>   bpf: Introduce may_goto instruction
>   bpf: Recognize that two registers are safe when their ranges match
>   bpf: Add cond_break macro
>   selftests/bpf: Test may_goto
> 
>  include/linux/bpf_verifier.h                  |   2 +
>  include/uapi/linux/bpf.h                      |   1 +
>  kernel/bpf/core.c                             |   1 +
>  kernel/bpf/disasm.c                           |   3 +
>  kernel/bpf/verifier.c                         | 280 +++++++++++++-----
>  tools/include/uapi/linux/bpf.h                |   1 +
>  tools/testing/selftests/bpf/DENYLIST.s390x    |   1 +
>  .../testing/selftests/bpf/bpf_experimental.h  |  12 +
> .../bpf/progs/verifier_iterating_callbacks.c  | 103 ++++++-
>  9 files changed, 330 insertions(+), 74 deletions(-)

Don't we also need to add may_goto to instruction-set.rst?

Dave

Alexei Starovoitov March 4, 2024, 5:05 p.m. UTC | #2

On Mon, Mar 4, 2024 at 8:45 AM <[e-mail]> wrote:
>
> Alexei Starovoitov <[e-mail]> writes:
> [...]
> > Alexei Starovoitov (4):
> >   bpf: Introduce may_goto instruction
> >   bpf: Recognize that two registers are safe when their ranges match
> >   bpf: Add cond_break macro
> >   selftests/bpf: Test may_goto
> >
> >  include/linux/bpf_verifier.h                  |   2 +
> >  include/uapi/linux/bpf.h                      |   1 +
> >  kernel/bpf/core.c                             |   1 +
> >  kernel/bpf/disasm.c                           |   3 +
> >  kernel/bpf/verifier.c                         | 280 +++++++++++++-----
> >  tools/include/uapi/linux/bpf.h                |   1 +
> >  tools/testing/selftests/bpf/DENYLIST.s390x    |   1 +
> >  .../testing/selftests/bpf/bpf_experimental.h  |  12 +
> > .../bpf/progs/verifier_iterating_callbacks.c  | 103 ++++++-
> >  9 files changed, 330 insertions(+), 74 deletions(-)
>
> Don't we also need to add may_goto to instruction-set.rst?

If it was a real insn it would be too early to update the standard,
since it's not in any kernel release yet.

But more importantly it's a pseudo insn. CPUs/JITs won't see it.
I think we need a different document for such pseudo instructions.
Same thing for upcoming nop_or_goto pseudo insn.