[RFC bpf-next 00/10] initial control flow support for eBPF verifier

[Jiong Wang <jiong.wang@netronome.com>]

This patch introduce initial control flow infrastructure to eBPF verifier.
Various control flow information are built in an incremental way, so they
could be easily maintained at various level.

After this patch set, information collection on eBPF insns are centred at
check_subprogs, check_cfg and related code then are replaced by new
infrastructure.

Checks/Analysis offered by check_cfg are still offered by new
infrastructure. For example loop detection, recursive function call,
unreachable insn, prune heuristic marking.

This infrastructure comes with some memory usage and execution time cost.
Memory pool based allocation is used to avoid frequently calling of
kmalloc/free. Singly linked list and compact pointer are used to reduce
various cfg node size.

data structure size
===
  basic blocks     edge        call-graph edge
  16-bytes         24-bytes    6-bytes

memory usage (test_l4lb_noinline, test_xdp_noinline)
====
(counted all subprogs):

test_l4lb_noinline:

  cfg info:  597 insns, 12 subprogs
             107 basic-blocks, 278 edges, 12 call edges.

  mem usage: 9216(9K)-bytes for memory pool (basic-blocks/edges/call-edges)
             644-bytes for dominator trees.

test_xdp_noinline:

  cfg info:  1029 insns, 21 subprogs
             191 basic-basics, 502 edges, 23 call edges.

  mem usage: 15360(15K)-bytes for memory pool.
             1192-bytes for dominator trees.

The existing check_cfg is using two auxiliary arrays (insn_state and
insn_stack), insn_cnt * sizeof(int) bytes for each, so would use ~5K and
~8K accordingly.  (looks to me insn_state could use 1-byte element,
insn_stack could use 2-byte, so probably could reduced to ~2K and ~3K).

The existing check_cfg is using 8-bytes for each insn during cfg check.
The new infrastructure basically use 2x mems, 16-bytes for each insn.

execution time
===
test_l4lb_noinline:
  existing check_subprog/check_cfg: ~55000 ns
  new infrastructure: ~135000 ns

test_xdp_noinline:
  existing check_subprog/check_cfg: ~52000 ns
  new infrastructure: ~120000 ns

The control flow infrastructure could possibly lay the ground for further
static analysis inside eBPF verifier, for example bounded loop detection,
path-sensitive data-flow analysis etc.

Jiong Wang (10):
  bpf: cfg: partition basic blocks for each subprog
  bpf: cfg: add edges between basic blocks to form CFG
  bpf: cfg: build domination tree using Tarjan algorithm
  bpf: cfg: detect loop use domination information
  bpf: cfg: detect unreachable basic blocks
  bpf: cfg: move find_subprog/add_subprog to cfg.c
  bpf: cfg: build call graph and detect unreachable/recursive call
  bpf: cfg: remove push_insn and check_cfg
  bpf: cfg: reduce k*alloc/free call by using memory pool for allocating
    nodes
  bpf: cfg: reduce memory usage by using singly list + compat pointer

 include/linux/bpf_verifier.h |   8 +
 kernel/bpf/Makefile          |   2 +-
 kernel/bpf/cfg.c             | 956 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/cfg.h             |  42 ++
 kernel/bpf/verifier.c        | 386 ++++++-----------
 5 files changed, 1131 insertions(+), 263 deletions(-)
 create mode 100644 kernel/bpf/cfg.c
 create mode 100644 kernel/bpf/cfg.h

-- 
2.7.4