bpf: Introduce 64bit bitops kfuncs
cover bpf: Introduce 64bit bitops kfuncs
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/[email protected]/
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
RFC PATCH 1/4 bpf: Introduce 64bit bitops kfuncs
Introduce the following 64bit bitops kfuncs:
* 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
These kfuncs are marked with a new KF_MUST_INLINE flag, which indicates the kfunc must be inlined by the JIT backend. A weak function bpf_jit_inlines_bitops() is introduced for JIT backends to advertise support for individual bitops.
bpf_rol64() and bpf_ror64() kfuncs do not have KF_FASTCALL due to BPF_REG_4 ('cl' actually) will be used on x86_64. The other kfuncs have KF_FASTCALL to avoid clobbering unused registers.
An internal BPF_ALU64 opcode BPF_BITOPS is introduced as the encoding for these operations, with the immediate field selecting the specific operation (BPF_CLZ64, BPF_CTZ64, etc.).
The verifier rejects the kfunc in check_kfunc_call() if the JIT backend does not support it, and rewrites the call to a BPF_BITOPS instruction in fixup_kfunc_call().
--- 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 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 142 insertions(+)
include/linux/btf.h +1 -0
@@ -79,6 +79,7 @@#define KF_ARENA_ARG1 (1 << 14)/* kfunc takes an arena pointer as its first argument */ #define KF_ARENA_ARG2 (1 << 15)/* kfunc takes an arena pointer as its second argument */ #define KF_IMPLICIT_ARGS (1 << 16)/* kfunc has implicit arguments supplied by the verifier */ +#define KF_MUST_INLINE (1 << 17)/* kfunc must be inlined by JIT backend */ /* * Tag marking a kernel function as a kfunc. This is meant to minimize the
include/linux/filter.h +20 -0
@@ -514,6 +514,25 @@ static inline bool insn_is_cast_user(const struct bpf_insn *insn) .off = 0, \ .imm = 0 }) +/* bitops */ +#define BPF_BITOPS 0xe0/* opcode for alu64 */ +#define BPF_CLZ64 0x00/* imm for clz64 */ +#define BPF_CTZ64 0x01/* imm for ctz64 */ +#define BPF_FFS64 0x02/* imm for ffs64 */ +#define BPF_FLS64 0x03/* imm for fls64 */ +#define BPF_BITREV64 0x04/* imm for bitrev64 */ +#define BPF_POPCNT64 0x05/* imm for popcnt64 */ +#define BPF_ROL64 0x06/* imm for rol64 */ +#define BPF_ROR64 0x07/* imm for ror64 */ + +#define BPF_BITOPS_INSN (IMM ) \ + ((struct bpf_insn) { \ + .code = BPF_ALU64 | BPF_BITOPS, \ + .dst_reg = 0, \ + .src_reg = 0, \ + .off = 0, \ + .imm = IMM }) +/* Internal classic blocks for direct assignment */ #define __BPF_STMT (CODE ,K ) \
@@ -1157,6 +1176,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog);void bpf_jit_compile (struct bpf_prog *prog);bool bpf_jit_needs_zext (void );bool bpf_jit_inlines_helper_call (s32 imm); +bool bpf_jit_inlines_bitops (s32 imm);bool bpf_jit_supports_subprog_tailcalls (void );bool bpf_jit_supports_percpu_insn (void );bool bpf_jit_supports_kfunc_call (void );
kernel/bpf/core.c +6 -0
@@ -3113,6 +3113,12 @@ bool __weak bpf_jit_inlines_helper_call(s32 imm)return false; } +/* Return TRUE if the JIT backend inlines the bitops insn. */ +bool __weak bpf_jit_inlines_bitops (s32 imm) +{ +return false; +} +/* Return TRUE if the JIT backend supports mixing bpf2bpf and tailcalls. */ bool __weak bpf_jit_supports_subprog_tailcalls (void ) {
kernel/bpf/helpers.c +50 -0
68 lines not on this page · raw message
kernel/bpf/verifier.c +65 -0
101 lines not on this page · raw message
Signature · 1 line
2.52.0
RFC PATCH 2/4 bpf, x86: Add 64bit bitops kfuncs support for x86_64
In reply to Leon HwangImplement JIT inlining of the 64bit bitops kfuncs on x86_64.
bpf_rol64() and bpf_ror64() are always supported via ROL/ROR.
bpf_clz64(), bpf_ctz64(), bpf_ffs64(), and bpf_fls64() are supported when the CPU has X86_FEATURE_ABM (LZCNT/TZCNT).
bpf_popcnt64() is supported when the CPU has X86_FEATURE_POPCNT.
bpf_bitrev64() is not supported as x86_64 has no native bit-reverse instruction.
--- arch/x86/net/bpf_jit_comp.c | 153 ++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+)
arch/x86/net/bpf_jit_comp.c +153 -0
@@ -19,6 +19,7 @@#include <asm/text-patching.h> #include <asm/unwind.h> #include <asm/cfi.h> +#include <asm/cpufeatures.h> static bool all_callee_regs_used[4 ] = {true, true, true, true};
@@ -1604,6 +1605,134 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr) *pprog = prog; } +static int emit_bitops (u8 **pprog,u32 bitops) +{ +u8 *prog = *pprog; + +/* +* x86 Bit manipulation instruction set +* https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set +*/ + +switch (bitops) { +case BPF_CLZ64 : +/* +* Intel® 64 and IA-32 Architectures Software Developer's Manual (June 2023) +* +* LZCNT - Count the Number of Leading Zero Bits +* +* Opcode/Instruction +* F3 REX.W 0F BD /r +* LZCNT r64, r/m64 +* +* Op/En +* RVM +* +* 64/32-bit Mode +* V/N.E. +* +* CPUID Feature Flag +* LZCNT +* +* Description +* Count the number of leading zero bits in r/m64, return +* result in r64. +*/ +/* emit: x ? 64 - fls64(x) : 64 */ +/* lzcnt rax, rdi */ +EMIT5 (0xF3 ,0x48 ,0x0F ,0xBD ,0xC7 ); +break ; + +case BPF_CTZ64 : +/* +* Intel® 64 and IA-32 Architectures Software Developer's Manual (June 2023) +* +* TZCNT - Count the Number of Trailing Zero Bits +* +* Opcode/Instruction +* F3 REX.W 0F BC /r +* TZCNT r64, r/m64 +* +* Op/En +* RVM +* +* 64/32-bit Mode +* V/N.E. +* +* CPUID Feature Flag +* BMI1 +* +* Description +* Count the number of trailing zero bits in r/m64, return +* result in r64. +*/ +/* emit: x ? __ffs64(x) : 64 */ +/* tzcnt rax, rdi */ +EMIT5 (0xF3 ,0x48 ,0x0F ,0xBC ,0xC7 ); +break ; + +case BPF_FFS64 : +/* emit: __ffs64(x), 'x == 0' was handled by verifier */ +/* tzcnt rax, rdi */ +EMIT5 (0xF3 ,0x48 ,0x0F ,0xBC ,0xC7 ); +break ; + +case BPF_FLS64 : +/* emit: fls64(x) */ +/* lzcnt rax, rdi; neg rax; add rax, 64 */ +EMIT5 (0xF3 ,0x48 ,0x0F ,0xBD ,0xC7 ); +EMIT3 (0x48 ,0xF7 ,0xD8 );/* neg rax */ +EMIT4 (0x48 ,0x83 ,0xC0 ,0x40 );/* add rax, 64 */ +break ; + +case BPF_POPCNT64 : +/* +* Intel® 64 and IA-32 Architectures Software Developer's Manual (June 2023) +* +* POPCNT - Return the Count of Number of Bits Set to 1 +* +* Opcode/Instruction +* F3 REX.W 0F B8 /r +* POPCNT r64, r/m64 +* +* Op/En +* RM +* +* 64 Mode +* Valid +* +* Compat/Leg Mode +* N.E. +* +* Description +* POPCNT on r/m64 +*/ +/* popcnt rax, rdi */ +EMIT5 (0xF3 ,0x48 ,0x0F ,0xB8 ,0xC7 ); +break ; + +case BPF_ROL64 : +/* emit: rol64(x, s) */ +EMIT3 (0x48 ,0x89 ,0xF1 );/* mov rcx, rsi */ +EMIT3 (0x48 ,0x89 ,0xF8 );/* mov rax, rdi */ +EMIT3 (0x48 ,0xD3 ,0xC0 );/* rol rax, cl */ +break ; + +case BPF_ROR64 : +/* emit: ror64(x, s) */ +EMIT3 (0x48 ,0x89 ,0xF1 );/* mov rcx, rsi */ +EMIT3 (0x48 ,0x89 ,0xF8 );/* mov rax, rdi */ +EMIT3 (0x48 ,0xD3 ,0xC8 );/* ror rax, cl */ +break ; + +default : +return -EOPNOTSUPP ; + } + + *pprog = prog; +return 0 ; +} +#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))#define __LOAD_TCC_PTR (off) \
@@ -2113,6 +2242,12 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image }break ; +case BPF_ALU64 |BPF_BITOPS : + err =emit_bitops (&prog, insn->imm); +if (err) +return err; +break ; +/* speculation barrier */ case BPF_ST |BPF_NOSPEC :EMIT_LFENCE ();
@@ -4117,3 +4252,21 @@ bool bpf_jit_supports_fsession(void) {return true; } + +bool bpf_jit_inlines_bitops (s32 imm) +{ +switch (imm) { +case BPF_CLZ64 : +case BPF_CTZ64 : +case BPF_FFS64 : +case BPF_FLS64 : +return boot_cpu_has (X86_FEATURE_ABM ); +case BPF_POPCNT64 : +return boot_cpu_has (X86_FEATURE_POPCNT ); +case BPF_ROL64 : +case BPF_ROR64 : +return true; +default : +return false; + } +}
Signature · 1 line
2.52.0
RFC PATCH 3/4 bpf, arm64: Add 64bit bitops kfuncs support
In reply to Leon HwangImplement JIT inlining of the 64bit bitops kfuncs on arm64.
bpf_clz64(), bpf_ffs64(), bpf_fls64(), and bpf_bitrev64() are always supported using mandatory ARMv8 CLZ/RBIT instructions. bpf_ctz64() is implemented via RBIT + CLZ, or via the native CTZ instruction when FEAT_CSSC is available. bpf_rol64() and bpf_ror64() are always supported via RORV.
bpf_popcnt64() is not supported as the native population count instruction requires NEON/SIMD registers, which should not be touched from BPF programs.
--- arch/arm64/net/bpf_jit_comp.c | 143 ++++++++++++++++++++++++++++++++++ 1 file changed, 143 insertions(+)
arch/arm64/net/bpf_jit_comp.c +143 -0
@@ -1199,6 +1199,123 @@ static int add_exception_handler(const struct bpf_insn *insn,return 0 ; } +static inline u32 a64_clz64 (u8 rd,u8 rn) +{ +/* +* Arm Architecture Reference Manual for A-profile architecture +* (Document number: ARM DDI 0487) +* +* A64 Base Instruction Descriptions +* C6.2 Alphabetical list of A64 base instructions +* +* C6.2.91 CLZ +* +* Count leading zeros +* +* This instruction counts the number of consecutive binary zero bits, +* starting from the most significant bit in the source register, +* and places the count in the destination register. +*/ +/* CLZ Xd, Xn */ +return 0xdac01000 | (rn <<5 ) | rd; +} + +static inline u32 a64_ctz64 (u8 rd,u8 rn) +{ +/* +* Arm Architecture Reference Manual for A-profile architecture +* (Document number: ARM DDI 0487) +* +* A64 Base Instruction Descriptions +* C6.2 Alphabetical list of A64 base instructions +* +* C6.2.144 CTZ +* +* Count trailing zeros +* +* This instruction counts the number of consecutive binary zero bits, +* starting from the least significant bit in the source register, +* and places the count in the destination register. +* +* This instruction requires FEAT_CSSC. +*/ +/* CTZ Xd, Xn */ +return 0xdac01800 | (rn <<5 ) | rd; +} + +static inline u32 a64_rbit64 (u8 rd,u8 rn) +{ +/* +* Arm Architecture Reference Manual for A-profile architecture +* (Document number: ARM DDI 0487) +* +* A64 Base Instruction Descriptions +* C6.2 Alphabetical list of A64 base instructions +* +* C6.2.320 RBIT +* +* Reverse bits +* +* This instruction reverses the bit order in a register. +*/ +/* RBIT Xd, Xn */ +return 0xdac00000 | (rn <<5 ) | rd; +} + +static inline bool supports_cssc (void ) +{ +/* +* Documentation/arch/arm64/cpu-feature-registers.rst +* +* ID_AA64ISAR2_EL1 - Instruction set attribute register 2 +* +* CSSC +*/ +return cpuid_feature_extract_unsigned_field (read_sanitised_ftr_reg (SYS_ID_AA64ISAR2_EL1 ), +ID_AA64ISAR2_EL1_CSSC_SHIFT ); +} + +static int emit_bitops (struct jit_ctx *ctx,s32 imm) +{ +const u8 r0 = bpf2a64[BPF_REG_0 ]; +const u8 r1 = bpf2a64[BPF_REG_1 ]; +const u8 r2 = bpf2a64[BPF_REG_2 ]; +const u8 tmp = bpf2a64[TMP_REG_1 ]; + +switch (imm) { +case BPF_CLZ64 : +emit (a64_clz64 (r0, r1), ctx); +break ; +case BPF_CTZ64 : +case BPF_FFS64 : +if (supports_cssc ()) { +emit (a64_ctz64 (r0, r1), ctx); + }else { +emit (a64_rbit64 (tmp, r1), ctx); +emit (a64_clz64 (r0, tmp), ctx); + } +break ; +case BPF_FLS64 : +emit (a64_clz64 (tmp, r1), ctx); +emit (A64_NEG (1 , tmp, tmp), ctx); +emit (A64_ADD_I (1 , r0, tmp,64 ), ctx); +break ; +case BPF_BITREV64 : +emit (a64_rbit64 (r0, r1), ctx); +break ; +case BPF_ROL64 : +emit (A64_NEG (1 , tmp, r2), ctx); +emit (A64_DATA2 (1 , r0, r1, tmp,RORV ), ctx); +break ; +case BPF_ROR64 : +emit (A64_DATA2 (1 , r0, r1, r2,RORV ), ctx); +break ; +default : +return -EOPNOTSUPP ; + } +return 0 ; +} +/* JITs an eBPF instruction. * Returns: * 0 - successfully JITed an 8-byte eBPF instruction.
@@ -1451,6 +1568,11 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx,case BPF_ALU64 |BPF_ARSH |BPF_K :emit (A64_ASR (is64, dst, dst, imm), ctx);break ; +case BPF_ALU64 |BPF_BITOPS : + ret =emit_bitops (ctx, imm); +if (ret) +return ret; +break ;/* JUMP reg */ case BPF_JMP |BPF_JA |BPF_X :
@@ -3207,3 +3329,24 @@ void bpf_jit_free(struct bpf_prog *prog)bpf_prog_unlock_free (prog); } + +bool bpf_jit_inlines_bitops (s32 imm) +{ +switch (imm) { +case BPF_CLZ64 : +case BPF_CTZ64 : +case BPF_FFS64 : +case BPF_FLS64 : +case BPF_BITREV64 : +/* They use RBIT/CLZ/CTZ which are mandatory in ARM64 */ +return true; +case BPF_POPCNT64 : +/* We should not touch NEON/SIMD register to support popcnt64 */ +return false; +case BPF_ROL64 : +case BPF_ROR64 : +return true; +default : +return false; + } +}
Signature · 1 line
2.52.0
RFC PATCH 4/4 selftests/bpf: Add tests for 64bit bitops kfuncs
In reply to Leon HwangAdd selftests for bpf_clz64(), bpf_ctz64(), bpf_ffs64(), bpf_fls64(), bpf_bitrev64(), bpf_popcnt64(), bpf_rol64(), and bpf_ror64().
Each subtest compares the kfunc result against a userspace reference implementation across a set of test vectors. If the JIT does not support inlining a given kfunc, the subtest is skipped (-EOPNOTSUPP at load time).
--- .../testing/selftests/bpf/bpf_experimental.h | 9 + .../testing/selftests/bpf/prog_tests/bitops.c | 186 ++++++++++++++++++ tools/testing/selftests/bpf/progs/bitops.c | 69 +++++++ 3 files changed, 264 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/bitops.c create mode 100644 tools/testing/selftests/bpf/progs/bitops.c
tools/testing/selftests/bpf/bpf_experimental.h +9 -0
@@ -594,6 +594,15 @@ extern void bpf_iter_dmabuf_destroy(struct bpf_iter_dmabuf *it) __weak __ksym; extern int bpf_cgroup_read_xattr(struct cgroup *cgroup, const char *name__str, struct bpf_dynptr *value_p) __weak __ksym; +extern __u64 bpf_clz64(__u64 x) __weak __ksym; +extern __u64 bpf_ctz64(__u64 x) __weak __ksym; +extern __u64 bpf_ffs64(__u64 x) __weak __ksym; +extern __u64 bpf_fls64(__u64 x) __weak __ksym; +extern __u64 bpf_bitrev64(__u64 x) __weak __ksym; +extern __u64 bpf_popcnt64(__u64 x) __weak __ksym; +extern __u64 bpf_rol64(__u64 x, __u64 s) __weak __ksym; +extern __u64 bpf_ror64(__u64 x, __u64 s) __weak __ksym; +#define PREEMPT_BITS 8#define SOFTIRQ_BITS 8#define HARDIRQ_BITS 4
tools/testing/selftests/bpf/prog_tests/bitops.c new file +186 -0
186 lines not on this page · raw message
tools/testing/selftests/bpf/progs/bitops.c new file +69 -0
69 lines not on this page · raw message
Signature · 1 line
2.52.0
Quoted 51 lines · Leon Hwang
Introduce the following 64bit bitops kfuncs:
*
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)= 0These kfuncs are marked with a new
KF_MUST_INLINEflag, which indicates the kfunc must be inlined by the JIT backend. A weak functionbpf_jit_inlines_bitops()is introduced for JIT backends to advertise support for individual bitops.
bpf_rol64()andbpf_ror64()kfuncs do not haveKF_FASTCALLdue toBPF_REG_4('cl' actually) will be used onx86_64. The other kfuncs haveKF_FASTCALLto avoid clobbering unused registers.An internal
BPF_ALU64opcodeBPF_BITOPSis introduced as the encoding for these operations, with the immediate field selecting the specific operation (BPF_CLZ64,BPF_CTZ64, etc.).The verifier rejects the kfunc in
check_kfunc_call()if the JIT backend does not support it, and rewrites the call to aBPF_BITOPSinstruction infixup_kfunc_call().Signed-off-by Leon Hwang <[email protected]>--- 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 ++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 142 insertions(+)include/linux/btf.h +0
-0
include/linux/btf.h line 82
Quoted 4 lines
include/linux/btf.h +1
-0@@ -79,6 +79,7 @@#define KF_ARENA_ARG1 (1 << 14)/* kfunc takes an arena pointer as its first argument */ #define KF_ARENA_ARG2 (1 << 15)/* kfunc takes an arena pointer as its second argument */ #define KF_IMPLICIT_ARGS (1 << 16)/* kfunc has implicit arguments supplied by the verifier */ +#define KF_MUST_INLINE (1 << 17)/* kfunc must be inlined by JIT backend */
UX is not great.
Just keep kfuncs in C as fallback when JIT cannot inline them and don't remove spill/fills that llvm leaves for fastcall.
Quoted 20 lines
include/linux/btf.h +0
-0/* * Tag marking a kernel function as a kfunc. This is meant to minimize the include/linux/filter.h +9
-0@@ -514,6 +514,25 @@ static inline bool insn_is_cast_user(const struct bpf_insn *insn) .off = 0, \ .imm = 0 }) +/* bitops */ +#define BPF_BITOPS 0xe0/* opcode for alu64 */ +#define BPF_CLZ64 0x00/* imm for clz64 */ +#define BPF_CTZ64 0x01/* imm for ctz64 */ +#define BPF_FFS64 0x02/* imm for ffs64 */ +#define BPF_FLS64 0x03/* imm for fls64 */ +#define BPF_BITREV64 0x04/* imm for bitrev64 */ +#define BPF_POPCNT64 0x05/* imm for popcnt64 */ +#define BPF_ROL64 0x06/* imm for rol64 */
include/linux/filter.h static inline bool insn_is_cast_user(const struct bpf_insn *insn) · line 535
Quoted 10 lines
include/linux/filter.h +10
-0+#define BPF_ROR64 0x07/* imm for ror64 */ + +#define BPF_BITOPS_INSN (IMM ) \ + ((struct bpf_insn) { \ + .code = BPF_ALU64 | BPF_BITOPS, \ + .dst_reg = 0, \ + .src_reg = 0, \ + .off = 0, \ + .imm = IMM }) +
why introduce pseudo instructions and this encoding? Just let JIT identify kfunc calls by address. bpf_jit_get_func_addr()
if (addr == bpf_clz64) ...
Quoted 90 lines
include/linux/filter.h +1
-0/* Internal classic blocks for direct assignment */ #define __BPF_STMT (CODE ,K ) \@@ -1157,6 +1176,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog);void bpf_jit_compile (struct bpf_prog *prog);bool bpf_jit_needs_zext (void );bool bpf_jit_inlines_helper_call (s32 imm); +bool bpf_jit_inlines_bitops (s32 imm);bool bpf_jit_supports_subprog_tailcalls (void );bool bpf_jit_supports_percpu_insn (void );bool bpf_jit_supports_kfunc_call (void );kernel/bpf/core.c +6
-0@@ -3113,6 +3113,12 @@ bool __weak bpf_jit_inlines_helper_call(s32 imm)return false; } +/* Return TRUE if the JIT backend inlines the bitops insn. */ +bool __weak bpf_jit_inlines_bitops (s32 imm) +{ +return false; +} +/* Return TRUE if the JIT backend supports mixing bpf2bpf and tailcalls. */ bool __weak bpf_jit_supports_subprog_tailcalls (void ) {kernel/bpf/helpers.c +42
-0@@ -29,6 +29,8 @@#include <linux/task_work.h> #include <linux/irq_work.h> #include <linux/buildid.h> +#include <linux/bitops.h> +#include <linux/bitrev.h> #include "../../lib/kstrtox.h" @@ -4501,6 +4503,46 @@ __bpf_kfunc int bpf_timer_cancel_async(struct bpf_timer *timer) } } +__bpf_kfunc u64 bpf_clz64(u64 x) +{ +return x ?64 -fls64 (x) :64 ; +} + +__bpf_kfunc u64 bpf_ctz64(u64 x) +{ +return x ?__ffs64 (x) :64 ; +} + +__bpf_kfunc u64 bpf_ffs64(u64 x) +{ +return x ?__ffs64 (x) +1 :0 ; +} + +__bpf_kfunc u64 bpf_fls64(u64 x) +{ +return fls64 (x); +} + +__bpf_kfunc u64 bpf_popcnt64(u64 x) +{ +return hweight64 (x); +} + +__bpf_kfunc u64 bpf_bitrev64(u64 x) +{ +return ((u64 )bitrev32 (x &0xFFFFFFFF ) <<32 ) |bitrev32 (x >>32 ); +} + +__bpf_kfunc u64 bpf_rol64(u64 x, u64 s) +{ +return rol64 (x, s); +} + +__bpf_kfunc u64 bpf_ror64(u64 x, u64 s) +{ +return ror64 (x, s); +} +__bpf_kfunc_end_defs ();static void bpf_task_work_cancel_scheduled (struct irq_work *irq_work)@@ -4578,6 +4620,14 @@ BTF_ID_FLAGS(func, bpf_key_put, KF_RELEASE)BTF_ID_FLAGS (func, bpf_verify_pkcs7_signature,KF_SLEEPABLE )
kernel/bpf/helpers.c BTF_ID_FLAGS(func, bpf_key_put, KF_RELEASE) · line 4630
Quoted 10 lines
kernel/bpf/helpers.c +8
-0#endif #endif +BTF_ID_FLAGS(func, bpf_clz64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_ctz64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_ffs64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_fls64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_popcnt64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_bitrev64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_rol64, KF_MUST_INLINE) +BTF_ID_FLAGS (func, bpf_ror64,KF_MUST_INLINE )
Mark all of them as fastcall and do push/pop in JIT when necessary.
pw-bot: cr
Quoted 2 lines · Alexei Starovoitov
Quoted 1 line · Leon Hwang
[...]
Quoted 5 lines
Quoted 5 lines
include/linux/btf.h +0
-0@@ -79,6 +79,7 @@
Quoted 9 lines
include/linux/btf.h line 82
Quoted 4 lines
include/linux/btf.h +1
-0#define KF_ARENA_ARG1 (1 << 14)/* kfunc takes an arena pointer as its first argument */ #define KF_ARENA_ARG2 (1 << 15)/* kfunc takes an arena pointer as its second argument */ #define KF_IMPLICIT_ARGS (1 << 16)/* kfunc has implicit arguments supplied by the verifier */ +#define KF_MUST_INLINE (1 << 17)/* kfunc must be inlined by JIT backend */ UX is not great.
Just keep kfuncs in C as fallback when JIT cannot inline them and don't remove spill/fills that llvm leaves for fastcall.
Ack.
I’ll drop KF_MUST_INLINE in the next revision and keep the C kfunc implementation as the fallback when the JIT cannot inline it.
Quoted 27 lines
Quoted 27 lines
include/linux/btf.h +0
-0/* * Tag marking a kernel function as a kfunc. This is meant to minimize the include/linux/filter.h +16
-0@@ -514,6 +514,25 @@ static inline bool insn_is_cast_user(const struct bpf_insn *insn) .off = 0, \ .imm = 0 }) +/* bitops */ +#define BPF_BITOPS 0xe0/* opcode for alu64 */ +#define BPF_CLZ64 0x00/* imm for clz64 */ +#define BPF_CTZ64 0x01/* imm for ctz64 */ +#define BPF_FFS64 0x02/* imm for ffs64 */ +#define BPF_FLS64 0x03/* imm for fls64 */ +#define BPF_BITREV64 0x04/* imm for bitrev64 */ +#define BPF_POPCNT64 0x05/* imm for popcnt64 */ +#define BPF_ROL64 0x06/* imm for rol64 */ +#define BPF_ROR64 0x07/* imm for ror64 */ + +#define BPF_BITOPS_INSN (IMM ) \ + ((struct bpf_insn) { \ + .code = BPF_ALU64 | BPF_BITOPS, \ + .dst_reg = 0, \ + .src_reg = 0, \
Quoted 9 lines
include/linux/filter.h static inline bool insn_is_cast_user(const struct bpf_insn *insn) · line 535
Quoted 3 lines
include/linux/filter.h +3
-0+ .off = 0, \ + .imm = IMM }) +why introduce pseudo instructions and this encoding? Just let JIT identify kfunc calls by address.
bpf_jit_get_func_addr()
if (addr ==bpf_clz64) ...
Thanks for pointing me to bpf_jit_get_func_addr().
I’ll drop the BPF_BITOPS encoding and BPF_BITOPS_INSN, and instead let the JIT identify the bitops kfuncs by their resolved function address via bpf_jit_get_func_addr().
That should keep things simpler and avoid introducing a new internal opcode.
Quoted 3 lines
Quoted 3 lines
include/linux/filter.h +0
-0/* Internal classic blocks for direct assignment */ #define __BPF_STMT (CODE ,K ) \
[...]
Quoted 6 lines
Quoted 6 lines
include/linux/filter.h +2
-0@@ -4578,6 +4620,14 @@ BTF_ID_FLAGS(func, bpf_key_put, KF_RELEASE) BTF_ID_FLAGS(func, bpf_verify_pkcs7_signature, KF_SLEEPABLE)#endif #endif +BTF_ID_FLAGS(func, bpf_clz64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS (func, bpf_ctz64,KF_FASTCALL |KF_MUST_INLINE )
Quoted 9 lines
include/linux/filter.h BTF_ID_FLAGS(func, bpf_key_put, KF_RELEASE) · line 4630
Quoted 6 lines
include/linux/filter.h +6
-0+BTF_ID_FLAGS(func, bpf_ffs64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_fls64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_popcnt64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_bitrev64, KF_FASTCALL | KF_MUST_INLINE) +BTF_ID_FLAGS(func, bpf_rol64, KF_MUST_INLINE) +BTF_ID_FLAGS (func, bpf_ror64,KF_MUST_INLINE )Mark all of them as fastcall and do push/pop in JIT when necessary.
Good idea.
I’ll mark all bitops kfuncs as KF_FASTCALL and handle any required save/restore in the JIT.
In particular, for bpf_rol64() and bpf_ror64() on x86_64, we do need to use rcx (CL) for variable rotates, so pushing/popping rcx in the JIT when needed makes sense.
Thanks,
Leon