[PATCH bpf-next 0/4] bpf: Track delta between "linked" registers.

[Alexei Starovoitov <alexei.starovoitov@gmail.com>]

From: Alexei Starovoitov <ast@kernel.org>

Compilers can generate the code
  r1 = r2
  r1 += 0x1
  if r2 < 1000 goto ...
  use knowledge of r2 range in subsequent r1 operations

The "undo" pass was introduced in LLVM
https://reviews.llvm.org/D121937
to prevent this optimization, but it cannot cover all cases.
Instead of fighting middle end optimizer in BPF backend teach the verifier
about this pattern.

The veristat difference:
File                                Program             Insns (A)  Insns (B)  Insns     (DIFF)
----------------------------------  ------------------  ---------  ---------  ----------------
arena_htab.bpf.o                    arena_htab_llvm         18656        768  -17888 (-95.88%)
arena_htab_asm.bpf.o                arena_htab_asm          18523        586  -17937 (-96.84%)
iters.bpf.o                         iter_subprog_iters       1109        981    -128 (-11.54%)
verifier_iterating_callbacks.bpf.o  cond_break1               110        121     +11 (+10.00%)
verifier_iterating_callbacks.bpf.o  cond_break2               113         91     -22 (-19.47%)

Alexei Starovoitov (4):
  bpf: Relax tuple len requirement for sk helpers.
  bpf: Track delta between "linked" registers.
  bpf: Support can_loop/cond_break on big endian
  selftests/bpf: Add tests for add_const

 include/linux/bpf_verifier.h                  |  12 +-
 kernel/bpf/log.c                              |   4 +-
 kernel/bpf/verifier.c                         |  90 +++++++++--
 net/core/filter.c                             |  24 +--
 .../testing/selftests/bpf/bpf_experimental.h  |  28 ++++
 .../testing/selftests/bpf/progs/arena_htab.c  |  16 +-
 .../bpf/progs/verifier_iterating_callbacks.c  | 150 ++++++++++++++++++
 7 files changed, 298 insertions(+), 26 deletions(-)

-- 
2.43.0