Skip to contentSkip to conversation

bpf: Introduce 64bit bitops kfuncs

RFC PATCH In review Leon Hwang 3 participants 7 messages Feb 9 – Feb 11

Subsystems (8)
x86 Kselftest BPF arm64 +4 more subsystems
lore
Share & tools
lore

Leon Hwang

author
#0 lore raw

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

author
#1 lore raw

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
index 48108471c5b1..8ac1dc59ca85 100644
@@ -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
index 4e1cb4f91f49..ff6c0cf68dd3 100644
@@ -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
index dc906dfdff94..cee90181d169 100644
@@ -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
#2 lore raw
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) = 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 +0 -0
index 48108471c5b1..8ac1dc59ca85 100644

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
index 4e1cb4f91f49..ff6c0cf68dd3 100644
@@ -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
index dc906dfdff94..cee90181d169 100644
@@ -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
index 7ac32798eb04..0a598c800f67 100644
@@ -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

#3 lore raw
Quoted 2 lines · Alexei Starovoitov
Quoted 1 line · Leon Hwang

[...]

Quoted 5 lines
Quoted 5 lines
include/linux/btf.h +0 -0
index 48108471c5b1..8ac1dc59ca85 100644
@@ -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
index 4e1cb4f91f49..ff6c0cf68dd3 100644
@@ -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

author
#4 lore raw

RFC PATCH 2/4 bpf, x86: Add 64bit bitops kfuncs support for x86_64

In reply to Leon Hwang

Implement 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
index 070ba80e39d7..5d6215071cbd 100644
@@ -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
author
#5 lore raw

RFC PATCH 3/4 bpf, arm64: Add 64bit bitops kfuncs support

In reply to Leon Hwang

Implement 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
index 2dc5037694ba..b91896cef247 100644
@@ -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
author
#6 lore raw

RFC PATCH 4/4 selftests/bpf: Add tests for 64bit bitops kfuncs

In reply to Leon Hwang

Add 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
index 4b7210c318dd..3a7d126968b3 100644
@@ -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