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

[Eduard Zingerman <eddyz87@gmail.com>]

On Thu, 2023-01-05 at 11:06 +0100, Jose E. Marchesi wrote:
> > On Sat, Dec 31, 2022 at 8:31 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > > 
> > > 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]).
> > 
> > Would we gate LLVM's emitting of BPF_ST for C code behind some new
> > cpu=v4? What is the benefit for compiler to start automatically emit
> > such instructions? Such thinking about logistics, if there isn't much
> > benefit, as BPF application owner I wouldn't bother enabling this
> > behavior risking regressions on old kernels that don't have these
> > changes.
> 
> Hmm, GCC happily generates BPF_ST instructions:
> 
>   $ echo 'int v; void foo () {  v = 666; }' | bpf-unknown-none-gcc -O2 -xc -S -o foo.s -
>   $ cat foo.s
>         .file	"<stdin>"
>         .text
>         .align	3
>         .global	foo
>         .type	foo, @function
>   foo:
>         lddw	%r0,v
>         stw	[%r0+0],666
>         exit
>         .size	foo, .-foo
>         .global	v
>         .type	v, @object
>         .lcomm	v,4,4
>         .ident	"GCC: (GNU) 12.0.0 20211206 (experimental)"
> 
> Been doing that since October 2019, I think before the cpu versioning
> mechanism was got in place?
> 
> We weren't aware this was problematic.  Does the verifier reject such
> instructions?

Interesting, do BPF selftests generated by GCC pass the same way they
do if generated by clang?

I had to do the following changes to the verifier to make the
selftests pass when BPF_ST instruction is allowed for selection:

- patch #1 in this patchset: track values of constants written to
  stack using BPF_ST. Currently these are tracked imprecisely, unlike
  the writes using BPF_STX, e.g.:
  
    fp[-8] = 42;   currently verifier assumes that fp[-8]=mmmmmmmm
                   after such instruction, where m stands for "misc",
                   just a note that something is written at fp[-8].
                   
    r1 = 42;       verifier tracks r1=42 after this instruction.
    fp[-8] = r1;   verifier tracks fp[-8]=42 after this instruction.

  So the patch makes both cases equivalent.
  
- patch #3 in this patchset: adjusts verifier.c:convert_ctx_access()
  to operate on BPF_ST alongside BPF_STX.
  
  Context parameters for some BPF programs types are "fake" data
  structures. The verifier matches all BPF_STX and BPF_LDX
  instructions that operate on pointers to such contexts and rewrites
  these instructions. It might change an offset or add another layer
  of indirection, etc. E.g. see filter.c:bpf_convert_ctx_access().
  (This also implies that verifier forbids writes to non-constant
   offsets inside such structures).
   
  So the patch extends this logic to also handle BPF_ST.

> 
> > So I feel like the biggest benefit is to be able to use this
> > instruction in embedded assembly, to make writing and maintaining
> > tests easier.
> > 
> > > 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] git@github.com: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
> > > 
> > > --
> > > 2.39.0
> > >