Skip to content

RFC Support for BPF_ST instruction in LLVM C compiler

Eduard Zingerman bpf 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 RFC Latest5 patches 10 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/5bpf: more precise stack write reasoning for BPF_ST instructionkernel/bpf/verifier.c tools/testing/selftests/bpf/verifier/bounds_mix_sign_unsign.c+84 -490 replies
2/5selftests/bpf: check if verifier tracks constants spilled by BPF_ST_MEMtools/testing/selftests/bpf/verifier/bpf_st_mem.c+29 -00 replies
3/5bpf: allow ctx writes using BPF_ST_MEM instructionkernel/bpf/cgroup.c kernel/bpf/verifier.c net/core/filter.c +1 more+108 -1030 replies
4/5selftests/bpf: test if pointer type is tracked for BPF_ST_MEMtools/testing/selftests/bpf/verifier/unpriv.c+23 -00 replies
5/5selftests/bpf: don't match exact insn index in expected error messagetools/testing/selftests/bpf/prog_tests/log_fixup.c tools/testing/selftests/bpf/prog_tests/spin_lock.c+5 -50 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [RFC bpf-next 0/5] Support for BPF_ST instruction in LLVM C compiler

BPF has two documented (non-atomic) memory store instructions:

BPF_STX: *(size *) (dst_reg + off) = src_reg
BPF_ST : *(size *) (dst_reg + off) = imm32

Currently LLVM BPF back-end does not emit BPF_ST instruction and does not allow one to be specified as inline assembly.

Recently I've been exploring ways to port some of the verifier test cases from tools/testing/selftests/bpf/verifier/*.c to use inline assembly and machinery provided in tools/testing/selftests/bpf/test_loader.c (which should hopefully simplify tests maintenance).
The BPF_ST instruction is popular in these tests: used in 52 of 94 files.

While it is possible to adjust LLVM to only support BPF_ST for inline assembly blocks it seems a bit wasteful. This patch-set contains a set of changes to verifier necessary in case when LLVM is allowed to freely emit BPF_ST instructions (source code is available here [1]). The changes include:
- update to verifier.c:check_stack_write_*() functions to track constant values spilled to stack via BPF_ST instruction in a same way stack spills of known registers by BPF_STX are tracked;
- updates to verifier.c:convert_ctx_access() and it's callbacks to handle BPF_ST instruction in a way similar to BPF_STX;
- some test adjustments and a few new tests.

With the above changes applied and LLVM from [1] all test_verifier, test_maps, test_progs and test_progs-no_alu32 test cases are passing.

When built using the LLVM version from [1] BPF programs generated for selftests and Cilium programs (taken from [2]) see certain reduction in size, e.g. below are total numbers of instructions for files with over 5K instructions:

File                                    Insns   Insns   Insns   Diff
                                        w/o     with    diff    pct
                                        BPF_ST  BPF_ST
cilium/bpf_host.o                       44620   43774   -846    -1.90%
cilium/bpf_lxc.o                        36842   36060   -782    -2.12%
cilium/bpf_overlay.o                    23557   23186   -371    -1.57%
cilium/bpf_xdp.o                        26397   25931   -466    -1.77%
selftests/core_kern.bpf.o               12359   12359    0       0.00%
selftests/linked_list_fail.bpf.o        5501    5302    -199    -3.62%
selftests/profiler1.bpf.o               17828   17709   -119    -0.67%
selftests/pyperf100.bpf.o               49793   49268   -525    -1.05%
selftests/pyperf180.bpf.o               88738   87813   -925    -1.04%
selftests/pyperf50.bpf.o                25388   25113   -275    -1.08%
selftests/pyperf600.bpf.o               78330   78300   -30     -0.04%
selftests/pyperf_global.bpf.o           5244    5188    -56     -1.07%
selftests/pyperf_subprogs.bpf.o         5262    5192    -70     -1.33%
selftests/strobemeta.bpf.o              17154   16065   -1089   -6.35%
selftests/test_verif_scale2.bpf.o       11337   11337    0       0.00%

(Instructions are counted by counting the number of instruction lines
in disassembly).

Is community interested in this work?
Are there any omissions in my changes to the verifier?

Known issue:

There are two programs (one Cilium, one selftest) that exhibit anomalous increase in verifier processing time with this patch-set:

 File                 Program                        Insns (A)  Insns (B)  Insns   (DIFF)
 -------------------  -----------------------------  ---------  ---------  --------------
 bpf_host.o           tail_ipv6_host_policy_ingress       1576       2403  +827 (+52.47%)
 map_kptr.bpf.o       test_map_kptr                        400        475   +75 (+18.75%)
 -------------------  -----------------------------  ---------  ---------  --------------

These are under investigation.

Thanks,
Eduard

[1] https://reviews.llvm.org/D140804
[2] [email protected]:anakryiko/cilium.git

Eduard Zingerman (5):
bpf: more precise stack write reasoning for BPF_ST instruction selftests/bpf: check if verifier tracks constants spilled by
BPF_ST_MEM
bpf: allow ctx writes using BPF_ST_MEM instruction selftests/bpf: test if pointer type is tracked for BPF_ST_MEM selftests/bpf: don't match exact insn index in expected error message

 kernel/bpf/cgroup.c                           |  49 +++++---
 kernel/bpf/verifier.c                         | 102 +++++++++-------
 net/core/filter.c                             |  72 ++++++------
 .../selftests/bpf/prog_tests/log_fixup.c      |   2 +-
 .../selftests/bpf/prog_tests/spin_lock.c      |   8 +-
 .../bpf/verifier/bounds_mix_sign_unsign.c     | 110 ++++++++++--------
 .../selftests/bpf/verifier/bpf_st_mem.c       |  29 +++++
 tools/testing/selftests/bpf/verifier/ctx.c    |  11 --
 tools/testing/selftests/bpf/verifier/unpriv.c |  23 ++++
 9 files changed, 249 insertions(+), 157 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/verifier/bpf_st_mem.c
Signature · 1 line
2.39.0