[RFC PATCH bpf-next 0/4] bpf: Introduce 64bit bitops kfuncs

[Leon Hwang <leon.hwang@linux.dev>]

Introduce the following 64-bit bitops kfuncs for x86_64 and arm64:

* bpf_clz64(): Count leading zeros.
* bpf_ctz64(): Count trailing zeros.
* bpf_ffs64(): Find first set bit, 1-based index, returns 0 when input is 0.
* bpf_fls64(): Find last set bit, 1-based index.
* bpf_bitrev64(): Reverse bits.
* bpf_popcnt64(): Population count.
* bpf_rol64(): Rotate left.
* bpf_ror64(): Rotate right.

Especially,

* bpf_clz64(0) = 64
* bpf_ctz64(0) = 64
* bpf_ffs64(0) = 0
* bpf_fls64(0) = 0

bpf_ffs64() was previously discussed in "bpf: Add generic kfunc bpf_ffs64()" [1].

Background

In the earlier bpf_ffs64() discussion, the main concern with exposing such
operations as generic kfuncs was ABI cost. A normal kfunc call follows the
BPF calling convention, which forces the compiler/JIT to treat R1-R5 as
call-clobbered, resulting in unnecessary spill/fill compared to a dedicated
instruction.

This RFC keeps the user-facing API as kfuncs, but avoids the ABI cost in the
fast path. The verifier rewrites supported bitops kfunc calls into a single
internal ALU64 encoding (BPF_BITOPS with an immediate selector), and JIT
backends emit native instructions directly. As a result, these kfuncs behave
like ISA operations once loaded, rather than real helper calls.

To make this contract explicit, the kfuncs are marked with a new
KF_MUST_INLINE flag: program load fails with -EOPNOTSUPP if the active JIT
backend cannot inline a particular operation. This keeps the cost predictable
and avoids silent slow fallbacks. A weak hook, bpf_jit_inlines_bitops(),
allows each JIT backend to advertise support on a per-operation basis
(and potentially based on CPU features).

Most operations are also tagged KF_FASTCALL to avoid clobbering unused
argument registers. bpf_rol64() and bpf_ror64() are the exception on x86_64,
where variable rotates require CL (BPF_REG_4).

Selftests output

On x86_64:

 #18/1    bitops/clz64:OK
 #18/2    bitops/ctz64:OK
 #18/3    bitops/ffs64:OK
 #18/4    bitops/fls64:OK
 #18/5    bitops/bitrev64:SKIP
 #18/6    bitops/popcnt64:OK
 #18/7    bitops/rol64:OK
 #18/8    bitops/ror64:OK
 #18      bitops:OK (SKIP: 1/8)
 Summary: 1/7 PASSED, 1 SKIPPED, 0 FAILED

On arm64:

 #18/1    bitops/clz64:OK
 #18/2    bitops/ctz64:OK
 #18/3    bitops/ffs64:OK
 #18/4    bitops/fls64:OK
 #18/5    bitops/bitrev64:OK
 #18/6    bitops/popcnt64:SKIP
 #18/7    bitops/rol64:OK
 #18/8    bitops/ror64:OK
 #18      bitops:OK (SKIP: 1/8)
 Summary: 1/7 PASSED, 1 SKIPPED, 0 FAILED

Open questions

1. Should these operations be exposed as a proper BPF ISA extension (new
   ALU64 ops) instead of a kfunc API plus verifier rewrite? This RFC takes
   the kfunc route to iterate without immediately committing to new uapi
   instruction semantics, while still ensuring instruction-like codegen.

2. For operations without a reasonable native implementation on some
   targets (e.g. bitrev64 on x86_64; popcnt64 on arm64 without touching
   SIMD registers), should we allow a true generic fallback by dropping
   KF_MUST_INLINE for those ops, or keep the "no-inline == reject" behavior
   for predictability?

Links:
[1] https://lore.kernel.org/bpf/20240131155607.51157-1-hffilwlqm@gmail.com/

Leon Hwang (4):
  bpf: Introduce 64bit bitops kfuncs
  bpf, x86: Add 64bit bitops kfuncs support for x86_64
  bpf, arm64: Add 64bit bitops kfuncs support
  selftests/bpf: Add tests for 64bit bitops kfuncs

 arch/arm64/net/bpf_jit_comp.c                 | 143 ++++++++++++++
 arch/x86/net/bpf_jit_comp.c                   | 153 ++++++++++++++
 include/linux/btf.h                           |   1 +
 include/linux/filter.h                        |  20 ++
 kernel/bpf/core.c                             |   6 +
 kernel/bpf/helpers.c                          |  50 +++++
 kernel/bpf/verifier.c                         |  65 ++++++
 .../testing/selftests/bpf/bpf_experimental.h  |   9 +
 .../testing/selftests/bpf/prog_tests/bitops.c | 186 ++++++++++++++++++
 tools/testing/selftests/bpf/progs/bitops.c    |  69 +++++++
 10 files changed, 702 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bitops.c
 create mode 100644 tools/testing/selftests/bpf/progs/bitops.c

--
2.52.0