mbox series

[bpf-next,v5,00/12] bpf: dead code elimination

Message ID 20190123064529.13518-1-jakub.kicinski@netronome.com
Headers show
Series bpf: dead code elimination | expand

Message

Jakub Kicinski Jan. 23, 2019, 6:45 a.m. UTC 
Hi!

This set adds support for complete removal of dead code.

Patch 3 contains all the code removal logic, patches 2 and 4
additionally optimize branches around and to dead code.

Patches 6 and 7 allow offload JITs to take advantage of the
optimization.  After a few small clean ups (8, 9, 10) nfp
support is added (11, 12).

Removing code directly in the verifier makes it easy to adjust
the relevant metadata (line info, subprogram info).  JITs for
code store constrained architectures would have hard time
performing such adjustments at JIT level.  Removing subprograms
or line info is very hard once BPF core finished the verification.
For user space to perform dead code removal it would have to perform
the execution simulation/analysis similar to what the verifier does.

v3:
 - fix uninitilized var warning in GCC 6 (buildbot).
v4:
 - simplify the linfo-keeping logic (Yonghong).  Instead of
   trying to figure out that we are removing first instruction
   of a subprogram, just always keep last dead line info, if
   first live instruction doesn't have one.
v5:
 - improve comments (Martin Lau).

Jakub Kicinski (12):
  bpf: change parameters of call/branch offset adjustment
  bpf: verifier: hard wire branches to dead code
  bpf: verifier: remove dead code
  bpf: verifier: remove unconditional branches by 0
  selftests: bpf: add tests for dead code removal
  bpf: verifier: record original instruction index
  bpf: notify offload JITs about optimizations
  nfp: bpf: don't use instruction number for jump target
  nfp: bpf: split up the skip flag
  nfp: bpf: save original program length
  nfp: bpf: support optimizing dead branches
  nfp: bpf: support removing dead code

 drivers/net/ethernet/netronome/nfp/bpf/jit.c  |  42 +-
 drivers/net/ethernet/netronome/nfp/bpf/main.h |  33 +-
 .../net/ethernet/netronome/nfp/bpf/offload.c  |   9 +-
 .../net/ethernet/netronome/nfp/bpf/verifier.c |  74 +++-
 include/linux/bpf.h                           |   7 +
 include/linux/bpf_verifier.h                  |   6 +
 include/linux/filter.h                        |   1 +
 kernel/bpf/core.c                             |  52 ++-
 kernel/bpf/offload.c                          |  35 ++
 kernel/bpf/verifier.c                         | 256 ++++++++++-
 tools/testing/selftests/bpf/test_btf.c        | 396 +++++++++++++++++-
 tools/testing/selftests/bpf/test_verifier.c   | 160 +++++++
 12 files changed, 1004 insertions(+), 67 deletions(-)

Comments

Alexei Starovoitov Jan. 24, 2019, 1:42 a.m. UTC | #1 
On Tue, Jan 22, 2019 at 10:45:17PM -0800, Jakub Kicinski wrote:
> Hi!
> 
> This set adds support for complete removal of dead code.
> 
> Patch 3 contains all the code removal logic, patches 2 and 4
> additionally optimize branches around and to dead code.
> 
> Patches 6 and 7 allow offload JITs to take advantage of the
> optimization.  After a few small clean ups (8, 9, 10) nfp
> support is added (11, 12).
> 
> Removing code directly in the verifier makes it easy to adjust
> the relevant metadata (line info, subprogram info).  JITs for
> code store constrained architectures would have hard time
> performing such adjustments at JIT level.  Removing subprograms
> or line info is very hard once BPF core finished the verification.
> For user space to perform dead code removal it would have to perform
> the execution simulation/analysis similar to what the verifier does.
> 
> v3:
>  - fix uninitilized var warning in GCC 6 (buildbot).
> v4:
>  - simplify the linfo-keeping logic (Yonghong).  Instead of
>    trying to figure out that we are removing first instruction
>    of a subprogram, just always keep last dead line info, if
>    first live instruction doesn't have one.
> v5:
>  - improve comments (Martin Lau).

The verifier is taking a page from the dragon book.
Applied to bpf-next.
Thanks!