Skip to contentSkip to conversation

bpf: inlinable kfuncs for BPF

RFC In review Eduard Zingerman 6 participants 37 messages Nov 7, 2024 – Nov 15, 2024

Subsystems (6)
Kbuild Kselftest BPF Arm STM32 +2 more subsystems
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: inlinable kfuncs for BPF

Some time ago, in an off-list discussion, Alexei Starovoitov suggested compiling certain kfuncs to BPF to allow inlining calls to such kfuncs during verification. This RFC explores the idea.

This RFC introduces a notion of inlinable BPF kfuncs. Inlinable kfuncs are compiled to BPF and are inlined by verifier after program verification. Inlined kfunc bodies are subject to dead code removal and removal of conditional jumps, if such jumps are proved to always follow a single branch.

Motivation
----------

The patch set uses bpf_dynptr_slice() as guinea pig, as this function is relatively complex and has a few conditionals that could be removed most of the times. The function has the following structure:

    void *bpf_dynptr_slice(const struct bpf_dynptr *p, u32 offset,
                           void *buffer__opt, u32 buffer__szk)
    {
        ...
        type = bpf_dynptr_get_type(ptr);

        switch (type) {
        ...
        case BPF_DYNPTR_TYPE_SKB:
                if (buffer__opt)
                        return skb_header_pointer(...);
                else
                        return skb_pointer_if_linear(...);
        ...
    }

Parameters 'type' and 'buffer__opt' are most likely to be known at callsite, and thus the function could be inlined w/o 'switch' and 'if' checks above.

This has a measurable speedup on microbenchmark, e.g. a simple test measuring number of bpf_dynptr_slice() executions per second shows ~1.5 speedup compared to master (see last patch in the series). Granted, real world programs do some other work beside slice calls.

Mechanism
---------

Implementation pursues three main goals:
- avoid differences in program verification whether or not certain kfunc is inlinable;
- predict branches in inlined kfuncs bodies;
- allow inlined kfunc bodies to do arbitrary computations.

The goals are achieved in the following steps:
- Inlinable kfuncs are defined in kernel/bpf/inlinable_kfuncs.c.
- In order to include kernel headers as-is the C file is compiled to llvm bitcode targeting native architecture and then to BPF elf object using llc utility.
- BPF elf object is embedded in kernel data section.
- At kernel initialization time the elf object is parsed and functions defined in the object are deemed to be inlinable kfuncs.
- Before main verification pass, for each inlinable kfunc callsite, inlinable kfunc is cloned as a hidden subprogram. Such subprograms are called kfunc instances.
- A new KERNEL_VALUE register type is added:
- ALU operations on any type and KERNEL_VALUE return KERNEL_VALUE;
- load / store operations with base register having type KERNEL_VALUE return KERNEL_VALUE.
- During main verification pass:
- inlinable kfunc calls are verified as regular kfunc calls;
- the bodies of the corresponding kfunc instances are visited in a "distilled" context:
- no caller stack frame;
- scalar or null pointer r1-r5 from caller stack frame are copied to instance call frame verbatim;
- pointer to dynptr r1-r5 from caller stack frame are represented in the instance call frame as pointers to a fake stack frame. For each dynptr this fake stack frame contains two register spills:
- one scalar for 'size' field, which also encodes type;
- one KERNEL_VALUE for 'data' field;
- r1-r5 of all other types are represented in the instance call frame as KERNEL_VALUEs;
- when 'exit' instruction within kfunc instance body is processed, verification for the current path is assumed complete.
- After main verification pass:
- rely on existing passes opt_hard_wire_dead_code_branches() and

    opt_remove_dead_code() to simplify kfunc instance bodies;

- calls to inlinable kfuncs are replaced with corresponding kfunc instance bodies, instance subprograms are removed.

Patch-set structure
-------------------

Implementation of the above mechanics is split in several patches to simplify the review. The following patches are most interesting:

- "bpf: shared BPF/native kfuncs":
Build system integration and kfuncs inlining after verification.

- "bpf: KERNEL_VALUE register type"
Adds an opaque type for registers that could be used for ALU and memory access.

- "bpf: allow specifying inlinable kfuncs in modules" This is mostly for tests: for testing purposes it is necessary to control exact assembly code for both test case calling kfunc and kfunc itself.

- "bpf: instantiate inlinable kfuncs before verification" Adds a pass that clones inlinable kfunc bodies as hidden subprograms, one subprogram per callsite.

- "bpf: special rules for kernel function calls inside inlinable kfuncs" Allows to call arbitrary kernel functions from kfunc instances.

Limitations
-----------

Some existing verifier restrictions are not lifted for inlinable kfuncs:
- stack is limited to 512 bytes;
- max 8 call frames (7 with the fake call frame);
- loops are still verified in a "brute force" way;
- instructions processed for kfunc instances are counted in 1M instructions budget.

The list is probably not exhaustive.

TODO items
----------

The following items are currently on the TODO list:
- consider getting rid of bpftool linking phase for BPF elf object;
- consider getting rid of clang->bitcode->llc->elf dance;
- make bpf_dynptr_from_skb() inlinable and allow passing objects state between kfunc instances, thus avoiding special case for dynptr;
- determine the set of kfuncs for which inlining makes sense.

Alternatives
------------

Imo, this RFC is worth following through only if number of kfuncs benefiting from inlining is big. If the set is limited to dynptr family of functions, it is simpler to add a number of hard-coded inlining templates for such functions (similarly to what is currently done for some helpers).

Eduard Zingerman (11):
bpf: use branch predictions in opt_hard_wire_dead_code_branches() selftests/bpf: tests for opt_hard_wire_dead_code_branches()
bpf: shared BPF/native kfuncs
bpf: allow specifying inlinable kfuncs in modules
bpf: dynamic allocation for bpf_verifier_env->subprog_info
bpf: KERNEL_VALUE register type
bpf: instantiate inlinable kfuncs before verification
bpf: special rules for kernel function calls inside inlinable kfuncs
bpf: move selected dynptr kfuncs to inlinable_kfuncs.c selftests/bpf: tests to verify handling of inlined kfuncs selftests/bpf: dynptr_slice benchmark

 Makefile                                      |   22 +-
 include/linux/bpf.h                           |   40 +-
 include/linux/bpf_verifier.h                  |   12 +-
 include/linux/btf.h                           |    7 +
 kernel/bpf/Makefile                           |   25 +-
 kernel/bpf/btf.c                              |    2 +-
 kernel/bpf/helpers.c                          |  130 +-
 kernel/bpf/inlinable_kfuncs.c                 |  113 ++
 kernel/bpf/log.c                              |    1 +
 kernel/bpf/verifier.c                         | 1187 ++++++++++++++++-
 tools/testing/selftests/bpf/Makefile          |    2 +
 tools/testing/selftests/bpf/bench.c           |    2 +
 .../selftests/bpf/benchs/bench_dynptr_slice.c |   76 ++
 .../selftests/bpf/bpf_testmod/Makefile        |   24 +-
 .../{bpf_testmod.c => bpf_testmod_core.c}     |   25 +
 .../bpf/bpf_testmod/test_inlinable_kfuncs.c   |  132 ++
 .../selftests/bpf/prog_tests/verifier.c       |    9 +
 .../selftests/bpf/progs/dynptr_slice_bench.c  |   29 +
 .../selftests/bpf/progs/verifier_dead_code.c  |   63 +
 .../bpf/progs/verifier_inlinable_kfuncs.c     |  253 ++++
 20 files changed, 1970 insertions(+), 184 deletions(-)
 create mode 100644 kernel/bpf/inlinable_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_dynptr_slice.c
 rename tools/testing/selftests/bpf/bpf_testmod/{bpf_testmod.c => bpf_testmod_core.c} (97%)
 create mode 100644 tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/dynptr_slice_bench.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_dead_code.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_inlinable_kfuncs.c
Signature · 1 line
2.47.0
author maintainer
#1 lore raw

RFC 1/11 bpf: use branch predictions in opt_hard_wire_dead_code_branches()

Consider dead code elimination problem for program like below:

    main:
      1: r1 = 42
      2: call <subprogram>;
      3: exit

    subprogram:
      4: r0 = 1
      5: if r1 != 42 goto +1
      6: r0 = 2
      7: exit;

Here verifier would visit every instruction and thus bpf_insn_aux_data->seen flag would be set for both true (7) and falltrhough (6) branches of conditional (5). Hence opt_hard_wire_dead_code_branches() will not replace conditional (5) with unconditional jump.

To cover such cases:
- add two fields in struct bpf_insn_aux_data:
- true_branch_taken;
- false_branch_taken;
- adjust check_cond_jmp_op() to set the fields according to jump predictions;
- handle these flags in the opt_hard_wire_dead_code_branches():
- true_branch_taken && !false_branch_taken

    always jump, replace instruction with 'goto off';
  - !true_branch_taken && false_branch_taken
    always falltrhough, replace with 'goto +0';
  - true_branch_taken && false_branch_taken
    jump and falltrhough are possible, don't change the instruction;

- !true_branch_taken && !false_branch_taken
neither jump, nor falltrhough are possible, if condition itself must be a dead code (should be removed by opt_remove_dead_code).

---
 include/linux/bpf_verifier.h |  4 +++-
 kernel/bpf/verifier.c        | 16 ++++++++++++----
 2 files changed, 15 insertions(+), 5 deletions(-)
include/linux/bpf_verifier.h +3 -1
index 4513372c5bc8..ed4eacfd4db7 100644
@@ -570,7 +570,9 @@ struct bpf_insn_aux_data {
 	struct btf_struct_meta *kptr_struct_meta;
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
-	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
+	bool seen; /* this insn was processed by the verifier at env->pass_cnt */
+	bool true_branch_taken; /* for cond jumps, set if verifier ever took true branch */
+	bool false_branch_taken; /* for cond jumps, set if verifier ever took false branch */
 	bool sanitize_stack_spill; /* subject to Spectre v4 sanitation */
 	bool zext_dst; /* this insn zero extends dst reg */
 	bool needs_zext; /* alu op needs to clear upper bits */
kernel/bpf/verifier.c +12 -4
index 7958d6ff6b73..3bae0bbc1da9 100644
@@ -13265,7 +13265,7 @@ static void sanitize_mark_insn_seen(struct bpf_verifier_env *env)
 	 * rewrite/sanitize them.
 	 */
 	if (!vstate->speculative)
-		env->insn_aux_data[env->insn_idx].seen = env->pass_cnt;
+		env->insn_aux_data[env->insn_idx].seen = env->pass_cnt > 0;
 }
 
 static int sanitize_err(struct bpf_verifier_env *env,
@@ -15484,6 +15484,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 {
 	struct bpf_verifier_state *this_branch = env->cur_state;
 	struct bpf_verifier_state *other_branch;
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[*insn_idx];
 	struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs;
 	struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL;
 	struct bpf_reg_state *eq_branch_regs;
@@ -15510,6 +15511,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 				insn->off, insn->imm);
 			return -EINVAL;
 		}
+		aux->true_branch_taken = true;
+		aux->false_branch_taken = true;
 		prev_st = find_prev_entry(env, cur_st->parent, idx);
 
 		/* branch out 'fallthrough' insn as a new state to explore */
@@ -15579,6 +15582,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		 * the fall-through branch for simulation under speculative
 		 * execution.
 		 */
+		aux->true_branch_taken = true;
 		if (!env->bypass_spec_v1 &&
 		    !sanitize_speculative_path(env, insn, *insn_idx + 1,
 					       *insn_idx))
@@ -15592,6 +15596,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		 * program will go. If needed, push the goto branch for
 		 * simulation under speculative execution.
 		 */
+		aux->false_branch_taken = true;
 		if (!env->bypass_spec_v1 &&
 		    !sanitize_speculative_path(env, insn,
 					       *insn_idx + insn->off + 1,
@@ -15602,6 +15607,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 		return 0;
 	}
 
+	aux->true_branch_taken = true;
+	aux->false_branch_taken = true;
+
 	/* Push scalar registers sharing same ID to jump history,
 	 * do this before creating 'other_branch', so that both
 	 * 'this_branch' and 'other_branch' share this history
@@ -19288,7 +19296,7 @@ static void adjust_insn_aux_data(struct bpf_verifier_env *env,
 {
 	struct bpf_insn_aux_data *old_data = env->insn_aux_data;
 	struct bpf_insn *insn = new_prog->insnsi;
-	u32 old_seen = old_data[off].seen;
+	bool old_seen = old_data[off].seen;
 	u32 prog_len;
 	int i;
 
@@ -19608,9 +19616,9 @@ static void opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env)
 		if (!insn_is_cond_jump(insn->code))
 			continue;
 
-		if (!aux_data[i + 1].seen)
+		if (aux_data[i].true_branch_taken && !aux_data[i].false_branch_taken)
 			ja.off = insn->off;
-		else if (!aux_data[i + 1 + insn->off].seen)
+		else if (!aux_data[i].true_branch_taken && aux_data[i].false_branch_taken)
 			ja.off = 0;
 		else
 			continue;
Signature · 1 line
2.47.0
author maintainer
#13 lore raw

RFC 2/11 selftests/bpf: tests for opt_hard_wire_dead_code_branches()

In reply to Eduard Zingerman

As opt_hard_wire_dead_code_branches() was changed to react to accumulated branch prediction flags for conditional jumps, add tests for various possible predictions.

---
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../selftests/bpf/progs/verifier_dead_code.c  | 63 +++++++++++++++++++
 2 files changed, 65 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_dead_code.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 75f7a2ce334b..efd42c07f58a 100644
@@ -26,6 +26,7 @@
 #include "verifier_ctx.skel.h"
 #include "verifier_ctx_sk_msg.skel.h"
 #include "verifier_d_path.skel.h"
+#include "verifier_dead_code.skel.h"
 #include "verifier_direct_packet_access.skel.h"
 #include "verifier_direct_stack_access_wraparound.skel.h"
 #include "verifier_div0.skel.h"
@@ -154,6 +155,7 @@ void test_verifier_const_or(void)             { RUN(verifier_const_or); }
 void test_verifier_ctx(void)                  { RUN(verifier_ctx); }
 void test_verifier_ctx_sk_msg(void)           { RUN(verifier_ctx_sk_msg); }
 void test_verifier_d_path(void)               { RUN(verifier_d_path); }
+void test_verifier_dead_code(void)            { RUN(verifier_dead_code); }
 void test_verifier_direct_packet_access(void) { RUN(verifier_direct_packet_access); }
 void test_verifier_direct_stack_access_wraparound(void) { RUN(verifier_direct_stack_access_wraparound); }
 void test_verifier_div0(void)                 { RUN(verifier_div0); }
tools/testing/selftests/bpf/progs/verifier_dead_code.c new file +63 -0

63 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#14 lore raw

RFC 3/11 bpf: shared BPF/native kfuncs

In reply to Eduard Zingerman

This commit adds a notion of inlinable kfuncs, compiled both to native code and BPF. BPF-compiled version is embedded in kernel data section and is available to verifier. Verifier uses it to replace calls to such kfuncs with inlined function bodies.

Inlinable kfuncs are available only if CLANG is used for kernel compilation.

In the scope of this commit all inlining happens as last steps of do_check(), after verification is finished. Follow up commits would extend this mechanism to allow removal of some conditional branches inside inlined function bodies.

The commit consists of the following changes:
- main kernel makefile:
modified to compile a bootstrap version of the bpftool;
- kernel/bpf/Makefile:
- a new file inlinable_kfuncs.c is added;
- makefile is modified to compile this file as BPF elf, using the following steps:
- use clang with native target to produce LLVM bitcode;
- compile LLVM bitcode to BPF object file;
- resolve relocations inside BPF object file using bpftool as a linker;
Such arrangement allows including unmodified network related header files.
- verifier.c:
- generated BPF elf is included as a part of kernel data section;
- at kernel initialization phase:
- the elf is parsed and each function declared within it is recorded as an instance of 'inlinable_kfunc' structure;
- calls to extern functions within elf file (pointed to by relocation records) are replaced with kfunc call instructions;
- do_check() is modified to replace calls to kfuncs from inlinable kfunc table with function bodies:
- replacement happens after main verification pass, so the bodies of the kfuncs are not analyzed by verifier;
- if kfunc uses callee saved registers r6-r9 the spill/fill pairs are generated for these register before/after inlined kfunc body at call site;
- if kfunc uses r10 as a base pointer for load or store instructions, offsets of these instructions are adjusted;
- if kfunc uses r10 in other instructions, such r10 is considered as escaping and kfunc is not inlined.

---
 Makefile                      |  22 +-
 kernel/bpf/Makefile           |  24 +-
 kernel/bpf/inlinable_kfuncs.c |   1 +
 kernel/bpf/verifier.c         | 652 +++++++++++++++++++++++++++++++++-
 4 files changed, 680 insertions(+), 19 deletions(-)
 create mode 100644 kernel/bpf/inlinable_kfuncs.c
Makefile +21 -1
index a9a7d9ffaa98..4ded57f4b0c2 100644
@@ -496,6 +496,7 @@ CLIPPY_DRIVER	= clippy-driver
 BINDGEN		= bindgen
 PAHOLE		= pahole
 RESOLVE_BTFIDS	= $(objtree)/tools/bpf/resolve_btfids/resolve_btfids
+BPFTOOL		= $(objtree)/tools/bpf/bpftool/bootstrap/bpftool
 LEX		= flex
 YACC		= bison
 AWK		= awk
@@ -585,7 +586,7 @@ export RUSTC_BOOTSTRAP := 1
 export ARCH SRCARCH CONFIG_SHELL BASH HOSTCC KBUILD_HOSTCFLAGS CROSS_COMPILE LD CC HOSTPKG_CONFIG
 export RUSTC RUSTDOC RUSTFMT RUSTC_OR_CLIPPY_QUIET RUSTC_OR_CLIPPY BINDGEN
 export HOSTRUSTC KBUILD_HOSTRUSTFLAGS
-export CPP AR NM STRIP OBJCOPY OBJDUMP READELF PAHOLE RESOLVE_BTFIDS LEX YACC AWK INSTALLKERNEL
+export CPP AR NM STRIP OBJCOPY OBJDUMP READELF PAHOLE RESOLVE_BTFIDS BPFTOOL LEX YACC AWK INSTALLKERNEL
 export PERL PYTHON3 CHECK CHECKFLAGS MAKE UTS_MACHINE HOSTCXX
 export KGZIP KBZIP2 KLZOP LZMA LZ4 XZ ZSTD
 export KBUILD_HOSTCXXFLAGS KBUILD_HOSTLDFLAGS KBUILD_HOSTLDLIBS LDFLAGS_MODULE
@@ -1356,6 +1357,25 @@ ifneq ($(wildcard $(resolve_btfids_O)),)
 	$(Q)$(MAKE) -sC $(srctree)/tools/bpf/resolve_btfids O=$(resolve_btfids_O) clean
 endif
 
+# TODO: cross compilation?
+# TODO: bootstrap! (to avoid vmlinux.h generation)
+PHONY += bpftool_bootstrap bpftool_clean
+bpftool_O = $(abspath $(objtree))/tools/bpf/bpftool
+
+ifdef CONFIG_BPF
+ifdef CONFIG_CC_IS_CLANG
+prepare: bpftool_bootstrap
+endif
+endif
+
+bpftool_bootstrap:
+	$(Q)$(MAKE) -sC $(srctree)/tools/bpf/bpftool O=$(bpftool_O) srctree=$(abspath $(srctree)) bootstrap
+
+bpftool_clean:
+ifneq ($(wildcard $(bpftool_O)),)
+	$(Q)$(MAKE) -sC $(srctree)/tools/bpf/bpftool O=$(bpftool_O) srctree=$(abspath $(srctree)) clean
+endif
+
 # Clear a bunch of variables before executing the submake
 ifeq ($(quiet),silent_)
 tools_silent=s
kernel/bpf/Makefile +23 -1
index 105328f0b9c0..3d7ee81c8e2e 100644
@@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse
 endif
 CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy)
 
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o tnum.o log.o token.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
 obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o
@@ -53,3 +53,25 @@ obj-$(CONFIG_BPF_SYSCALL) += relo_core.o
 obj-$(CONFIG_BPF_SYSCALL) += btf_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += btf_relocate.o
 obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o
+obj-$(CONFIG_BPF_SYSCALL) += helpers.o inlinable_kfuncs.o
+
+ifdef CONFIG_CC_IS_CLANG
+
+LLC ?= $(LLVM_PREFIX)llc$(LLVM_SUFFIX)
+
+# -mfentry -pg is $(CC_FLAGS_FTRACE)
+# -fpatchable-function-entry=16,16 is $(PADDING_CFLAGS)
+CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(CC_FLAGS_FTRACE)
+CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(PADDING_CFLAGS)
+$(obj)/inlinable_kfuncs.bpf.bc.o: $(src)/inlinable_kfuncs.c
+	$(Q)$(CLANG) $(c_flags) -emit-llvm -c $< -o $@
+
+$(obj)/inlinable_kfuncs.bpf.o: $(obj)/inlinable_kfuncs.bpf.bc.o
+	$(Q)$(LLC) -mcpu=v3 --mtriple=bpf --filetype=obj $< -o $@
+
+$(obj)/inlinable_kfuncs.bpf.linked.o: $(obj)/inlinable_kfuncs.bpf.o
+	$(Q)$(BPFTOOL) gen object $@ $<
+
+$(obj)/verifier.o: $(obj)/inlinable_kfuncs.bpf.linked.o
+
+endif
kernel/bpf/inlinable_kfuncs.c new file +1 -0
new file mode 100644
index 000000000000..7b7dc05fa1a4
@@ -0,0 +1 @@
+// SPDX-License-Identifier: GPL-2.0-only
kernel/bpf/verifier.c +635 -17

683 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#20 lore raw

RFC 4/11 bpf: allow specifying inlinable kfuncs in modules

In reply to Eduard Zingerman

Instead of keeping inlinable kfuncs in a single table, track them as a list of tables, one table per each module providing such kfuncs. Protect the list with an rwlock to safely deal with modules load/unload.

Provide two interface functions for use in modules:
- int bpf_register_inlinable_kfuncs(void *elf_bin, u32 size,

                                    struct module *module);

- void bpf_unregister_inlinable_kfuncs(struct module *module);

With an assumption that each module providing inlinable kfuncs would include BPF elf in the same way verifier.c does, with bpf_register_inlinable_kfuncs() called at load.
The bpf_unregister_inlinable_kfuncs() is supposed to be called before module unload.

Each table holds a reference to btf, the refcount of the btf object is not hold by the table. For lifetime management of module's btf object relies on:
- correct usage of bpf_register_inlinable_kfuncs / bpf_unregister_inlinable_kfuncs to insert/remove tables to the list, so that tables are members of the list only when module is loaded;
- add_kfunc_call(), so that kfuncs referenced from inlined bodies are not unloaded when inlinable kfunc is inlined.

---
 include/linux/bpf.h   |   3 +
 include/linux/btf.h   |   7 +++
 kernel/bpf/btf.c      |   2 +-
 kernel/bpf/verifier.c | 129 +++++++++++++++++++++++++++++++++++-------
 4 files changed, 119 insertions(+), 22 deletions(-)
include/linux/bpf.h +3 -0
index 1b84613b10ac..2bcc9161687b 100644
@@ -3501,4 +3501,7 @@ static inline bool bpf_prog_is_raw_tp(const struct bpf_prog *prog)
 	       prog->expected_attach_type == BPF_TRACE_RAW_TP;
 }
 
+void bpf_unregister_inlinable_kfuncs(struct module *module);
+int bpf_register_inlinable_kfuncs(void *elf_bin, u32 size, struct module *module);
+
 #endif /* _LINUX_BPF_H */
include/linux/btf.h +7 -0
index 4214e76c9168..9e8b27493139 100644
@@ -582,6 +582,7 @@ int get_kern_ctx_btf_id(struct bpf_verifier_log *log, enum bpf_prog_type prog_ty
 bool btf_types_are_same(const struct btf *btf1, u32 id1,
 			const struct btf *btf2, u32 id2);
 int btf_check_iter_arg(struct btf *btf, const struct btf_type *func, int arg_idx);
+struct btf *btf_get_module_btf(const struct module *module);
 
 static inline bool btf_type_is_struct_ptr(struct btf *btf, const struct btf_type *t)
 {
@@ -670,5 +671,11 @@ static inline int btf_check_iter_arg(struct btf *btf, const struct btf_type *fun
 {
 	return -EOPNOTSUPP;
 }
+struct btf *btf_get_module_btf(const struct module *module)
+{
+	return NULL;
+}
+
 #endif
+
 #endif
kernel/bpf/btf.c +1 -1
index e7a59e6462a9..49b25882fa58 100644
@@ -8033,7 +8033,7 @@ struct module *btf_try_get_module(const struct btf *btf)
 /* Returns struct btf corresponding to the struct module.
  * This function can return NULL or ERR_PTR.
  */
-static struct btf *btf_get_module_btf(const struct module *module)
+struct btf *btf_get_module_btf(const struct module *module)
 {
 #ifdef CONFIG_DEBUG_INFO_BTF_MODULES
 	struct btf_module *btf_mod, *tmp;
kernel/bpf/verifier.c +108 -21

212 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#23 lore raw

RFC 5/11 bpf: dynamic allocation for bpf_verifier_env->subprog_info

In reply to Eduard Zingerman

Follow-up patches use add_hidden_subprog() to inject inlinable kfunc bodies into bpf program as subprograms. At the moment only one hidden subprogram is allowed, as bpf_verifier_env->subprog_info is allocated in advance as array of fixed size. This patch removes the limitation by using dynamic memory allocation for this array.

---
 include/linux/bpf_verifier.h |  3 ++-
 kernel/bpf/verifier.c        | 29 ++++++++++++++++++++++-------
 2 files changed, 24 insertions(+), 8 deletions(-)
include/linux/bpf_verifier.h +2 -1
index ed4eacfd4db7..b683dc3ede4a 100644
@@ -738,7 +738,7 @@ struct bpf_verifier_env {
 	struct bpf_insn_aux_data *insn_aux_data; /* array of per-insn state */
 	const struct bpf_line_info *prev_linfo;
 	struct bpf_verifier_log log;
-	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */
+	struct bpf_subprog_info *subprog_info;
 	union {
 		struct bpf_idmap idmap_scratch;
 		struct bpf_idset idset_scratch;
@@ -751,6 +751,7 @@ struct bpf_verifier_env {
 	struct backtrack_state bt;
 	struct bpf_jmp_history_entry *cur_hist_ent;
 	u32 pass_cnt; /* number of times do_check() was called */
+	u32 subprog_cap;
 	u32 subprog_cnt;
 	/* number of instructions analyzed by the verifier */
 	u32 prev_insn_processed, insn_processed;
kernel/bpf/verifier.c +22 -7
index b86308896358..d4ea7fd8a967 100644
@@ -19419,7 +19419,7 @@ static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
 static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 					      u32 off, u32 cnt)
 {
-	int i, j;
+	int i, j, first_hidden = env->subprog_cnt - env->hidden_subprog_cnt;
 
 	/* find first prog starting at or after off (first to remove) */
 	for (i = 0; i < env->subprog_cnt; i++)
@@ -19446,6 +19446,8 @@ static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 			env->subprog_info + j,
 			sizeof(*env->subprog_info) * move);
 		env->subprog_cnt -= j - i;
+		if (first_hidden <= j - 1)
+			env->hidden_subprog_cnt -= j - first_hidden;
 
 		/* remove func_info */
 		if (aux->func_info) {
@@ -21215,15 +21217,20 @@ static int resolve_kfunc_calls(struct bpf_verifier_env *env)
 /* The function requires that first instruction in 'patch' is insnsi[prog->len - 1] */
 static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *patch, int len)
 {
-	struct bpf_subprog_info *info = env->subprog_info;
+	struct bpf_subprog_info *info, *tmp;
 	int cnt = env->subprog_cnt;
 	struct bpf_prog *prog;
 
-	/* We only reserve one slot for hidden subprogs in subprog_info. */
-	if (env->hidden_subprog_cnt) {
-		verbose(env, "verifier internal error: only one hidden subprog supported\n");
-		return -EFAULT;
+	if (cnt == env->subprog_cap) {
+		env->subprog_cap *= 2;
+		tmp = vrealloc(env->subprog_info,
+			       array_size(sizeof(*env->subprog_info), env->subprog_cap + 1),
+			       GFP_KERNEL | __GFP_ZERO);
+		if (!tmp)
+			return -ENOMEM;
+		env->subprog_info = tmp;
 	}
+	info = env->subprog_info;
 	/* We're not patching any existing instruction, just appending the new
 	 * ones for the hidden subprog. Hence all of the adjustment operations
 	 * in bpf_patch_insn_data are no-ops.
@@ -23122,6 +23129,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	ret = -ENOMEM;
 	if (!env->insn_aux_data)
 		goto err_free_env;
+	env->subprog_cap = BPF_MAX_SUBPROGS;
+	env->subprog_info = vzalloc(array_size(sizeof(*env->subprog_info),
+					       env->subprog_cap + 1 /* max + 1 for the fake subprog */));
+	if (!env->subprog_info) {
+		ret = -ENOMEM;
+		goto err_free_env;
+	}
 	for (i = 0; i < len; i++)
 		env->insn_aux_data[i].orig_idx = i;
 	env->prog = *prog;
@@ -23353,8 +23367,9 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 err_unlock:
 	if (!is_priv)
 		mutex_unlock(&bpf_verifier_lock);
-	vfree(env->insn_aux_data);
 err_free_env:
+	vfree(env->subprog_info);
+	vfree(env->insn_aux_data);
 	kvfree(env);
 	return ret;
 }
Signature · 1 line
2.47.0
author maintainer
#24 lore raw

RFC 6/11 bpf: KERNEL_VALUE register type

In reply to Eduard Zingerman

Follow-up patch adds inlinable kfuncs as subprograms of a bpf program being verified. Bodies of these helpers are considered trusted and don't require verification. To facilitate this, add a new register
type: KERNEL_VALUE.
- ALU operations on KERNEL_VALUEs return KERNEL_VALUE;
- stores with KERNEL_VALUE destination registers are legal;
- loads with KERNEL_VALUE source registers are legal and set destination registers to KERNEL_VALUE;
- KERNEL_VALUEs do not have any additional associated information:
no ids, no range, etc.

---
 include/linux/bpf.h   |  1 +
 kernel/bpf/log.c      |  1 +
 kernel/bpf/verifier.c | 24 +++++++++++++++++++++++-
 3 files changed, 25 insertions(+), 1 deletion(-)
include/linux/bpf.h +1 -0
index 2bcc9161687b..75f57f791cd3 100644
@@ -941,6 +941,7 @@ enum bpf_reg_type {
 	PTR_TO_BUF,		 /* reg points to a read/write buffer */
 	PTR_TO_FUNC,		 /* reg points to a bpf program function */
 	CONST_PTR_TO_DYNPTR,	 /* reg points to a const struct bpf_dynptr */
+	KERNEL_VALUE,		 /* pointer or scalar, any operation produces another KERNEL_VALUE */
 	__BPF_REG_TYPE_MAX,
 
 	/* Extended reg_types. */
kernel/bpf/log.c +1 -0
index 4a858fdb6476..87ab01b8fc1a 100644
@@ -463,6 +463,7 @@ const char *reg_type_str(struct bpf_verifier_env *env, enum bpf_reg_type type)
 		[PTR_TO_FUNC]		= "func",
 		[PTR_TO_MAP_KEY]	= "map_key",
 		[CONST_PTR_TO_DYNPTR]	= "dynptr_ptr",
+		[KERNEL_VALUE]		= "kval",
 	};
 
 	if (type & PTR_MAYBE_NULL) {
kernel/bpf/verifier.c +23 -1
index d4ea7fd8a967..f38f73cc740b 100644
@@ -2388,6 +2388,12 @@ static void mark_reg_unknown(struct bpf_verifier_env *env,
 	__mark_reg_unknown(env, regs + regno);
 }
 
+static void mark_reg_kernel_value(struct bpf_reg_state *reg)
+{
+	__mark_reg_unknown_imprecise(reg);
+	reg->type = KERNEL_VALUE;
+}
+
 static int __mark_reg_s32_range(struct bpf_verifier_env *env,
 				struct bpf_reg_state *regs,
 				u32 regno,
@@ -4534,6 +4540,9 @@ static bool __is_pointer_value(bool allow_ptr_leaks,
 	if (allow_ptr_leaks)
 		return false;
 
+	if (reg->type == KERNEL_VALUE)
+		return false;
+
 	return reg->type != SCALAR_VALUE;
 }
 
@@ -7208,6 +7217,9 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
 	} else if (reg->type == PTR_TO_ARENA) {
 		if (t == BPF_READ && value_regno >= 0)
 			mark_reg_unknown(env, regs, value_regno);
+	} else if (reg->type == KERNEL_VALUE) {
+		if (t == BPF_READ && value_regno >= 0)
+			mark_reg_kernel_value(regs + value_regno);
 	} else {
 		verbose(env, "R%d invalid mem access '%s'\n", regno,
 			reg_type_str(env, reg->type));
@@ -14319,6 +14331,13 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
 
 	if (BPF_SRC(insn->code) == BPF_X) {
 		src_reg = &regs[insn->src_reg];
+
+		if (src_reg->type == KERNEL_VALUE || dst_reg->type == KERNEL_VALUE) {
+			mark_reg_kernel_value(src_reg);
+			mark_reg_kernel_value(dst_reg);
+			return 0;
+		}
+
 		if (src_reg->type != SCALAR_VALUE) {
 			if (dst_reg->type != SCALAR_VALUE) {
 				/* Combining two pointers by any ALU op yields
@@ -14358,6 +14377,9 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
 				return err;
 		}
 	} else {
+		if (dst_reg->type == KERNEL_VALUE)
+			return 0;
+
 		/* Pretend the src is a reg with a known value, since we only
 		 * need to be able to read from this state.
 		 */
@@ -15976,7 +15998,7 @@ static int check_return_code(struct bpf_verifier_env *env, int regno, const char
 	}
 
 	if (is_subprog && !frame->in_exception_callback_fn) {
-		if (reg->type != SCALAR_VALUE) {
+		if (reg->type != SCALAR_VALUE && reg->type != KERNEL_VALUE) {
 			verbose(env, "At subprogram exit the register R%d is not a scalar value (%s)\n",
 				regno, reg_type_str(env, reg->type));
 			return -EINVAL;
Signature · 1 line
2.47.0
author maintainer
#25 lore raw

RFC 7/11 bpf: instantiate inlinable kfuncs before verification

In reply to Eduard Zingerman

In order to detect which branches inside kfuncs are always to true or always false (e.g. because of parameters being constants) visit bodies of inlinable kfuncs during main verification pass. Such conditionals would be replaced by gotos before jiting. Verify kfunc calls in (almost) identical way, regardless of kfunc being inlinable or not.

To facilitate this:
- before main verification pass, for each inlinable kfunc callsite, create a hidden subprogram with a body being a copy of inlinable kfunc body; let's call such subprograms inlinable kfunc instances;
- during main verification pass:
- when visiting inlinable kfunc call:
- verify call instruction using regular kfunc rules;
- mark scalar call parameters as precise;
- do a push_stack() for a state visiting kfunc instance body in a distilled context:
- no caller stack frame;
- values of scalar parameters and null pointers from the calling frame are copied as-is (it is ok if some of the scalar parameters would be marked precise during instance body verification, as these parameters are already marked precise at the call site);
- dynptrs are represented as two register spills in a fake stack frame crafted in a way allowing verifier to recover dynptr type when code generated for bpf_dynptr_get_type() is processed;
- all other parameters are passed as registers of type KERNEL_VALUE.
- when 'exit' instruction within instance body is verified, do not

    return to the callsite, assume a valid end of verification path;
- after main verification pass:
  - rely on existing passes opt_hard_wire_dead_code_branches() and
    opt_remove_dead_code() to simplify kfunc instance bodies;
  - adjust inline_kfunc_calls() to copy kfunc instance bodies at the
    corresponding call sites;

- remove kfunc instance bodies before jit.

Note, that steps taken at main verification pass make kfunc instance bodies "hermetic", verification of these bodies does not change state of the call site.

---
 include/linux/bpf_verifier.h |   5 +
 kernel/bpf/verifier.c        | 346 +++++++++++++++++++++++++++++++----
 2 files changed, 317 insertions(+), 34 deletions(-)
include/linux/bpf_verifier.h +5 -0
index b683dc3ede4a..2de3536e4133 100644
@@ -560,6 +560,8 @@ struct bpf_insn_aux_data {
 		 * the state of the relevant registers to make decision about inlining
 		 */
 		struct bpf_loop_inline_state loop_inline_state;
+		/* for kfunc calls, instance of the inlinable kfunc instance subprog */
+		u32 kfunc_instance_subprog;
 	};
 	union {
 		/* remember the size of type passed to bpf_obj_new to rewrite R1 */
@@ -722,6 +724,8 @@ struct bpf_verifier_env {
 	u32 used_btf_cnt;		/* number of used BTF objects */
 	u32 id_gen;			/* used to generate unique reg IDs */
 	u32 hidden_subprog_cnt;		/* number of hidden subprogs */
+	u32 first_kfunc_instance;	/* first inlinable kfunc instance subprog number */
+	u32 last_kfunc_instance;	/* last inlinable kfunc instance subprog number */
 	int exception_callback_subprog;
 	bool explore_alu_limits;
 	bool allow_ptr_leaks;
@@ -785,6 +789,7 @@ struct bpf_verifier_env {
 	 * e.g., in reg_type_str() to generate reg_type string
 	 */
 	char tmp_str_buf[TMP_STR_BUF_LEN];
+	char tmp_str_buf2[TMP_STR_BUF_LEN];
 	struct bpf_insn insn_buf[INSN_BUF_SIZE];
 	struct bpf_insn epilogue_buf[INSN_BUF_SIZE];
 };
kernel/bpf/verifier.c +312 -34

502 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#26 lore raw

RFC 8/11 bpf: special rules for kernel function calls inside inlinable kfuncs

In reply to Eduard Zingerman

Inlinable kfuncs can call arbitrary kernel functions, there is no need to check if these functions conform to kfunc or helper usage rules. Upon seeing such calls:
- mark registers R0-R5 as KERNEL_VALUEs after the call;
- if there are any PTR_TO_STACK parameters, mark all allocated stack slots as KERNEL_VALUEs.

The assumption is that KERNEL_VALUE marks should never escape form kfunc instance body: at the call site R0 is set in accordance to kfunc processing rules, PTR_TO_STACK parameters are never passed from bpf program to inlinable kfunc.

---
 kernel/bpf/verifier.c | 67 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 66 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +66 -1
index 87b6cc8c94f8..5b109139f356 100644
@@ -13209,6 +13209,67 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	return 0;
 }
 
+static int mark_stack_as_kernel_values(struct bpf_verifier_env *env, struct bpf_func_state *func)
+{
+	struct bpf_stack_state *slot;
+	struct bpf_reg_state *spill;
+	int spi, i;
+
+	if (!inside_inlinable_kfunc(env, func->callsite)) {
+		verbose(env, "verifier bug: shouldn't mark frame#%d as kernel values\n",
+			func->frameno);
+		return -EFAULT;
+	}
+
+	for (spi = 0; spi < func->allocated_stack / BPF_REG_SIZE; spi++) {
+		slot = &func->stack[spi];
+		spill = &slot->spilled_ptr;
+		mark_reg_kernel_value(spill);
+		spill->live |= REG_LIVE_WRITTEN;
+		for (i = 0; i < BPF_REG_SIZE; i++)
+			slot->slot_type[i] = STACK_SPILL;
+		mark_stack_slot_scratched(env, spi);
+	}
+
+	return 0;
+}
+
+static int check_internal_call(struct bpf_verifier_env *env, struct bpf_insn *insn)
+{
+	struct bpf_reg_state *reg, *regs = cur_regs(env);
+	struct bpf_kfunc_call_arg_meta meta;
+	int err, i, nargs;
+
+	err = fetch_kfunc_meta(env, insn, &meta, NULL);
+	if (err < 0)
+		return -EFAULT;
+
+	nargs = btf_type_vlen(meta.func_proto);
+	for (i = 0; i < nargs; i++) {
+		reg = &regs[BPF_REG_1 + i];
+		switch (reg->type) {
+		case SCALAR_VALUE:
+		case KERNEL_VALUE:
+			break;
+		case PTR_TO_STACK:
+			err = mark_stack_as_kernel_values(env, func(env, reg));
+			if (err)
+				return err;
+			break;
+		default:
+			verbose(env, "verifier bug: arg#%i unexpected register type %s\n",
+				i, reg_type_str(env, reg->type));
+			return -EFAULT;
+		}
+	}
+	for (i = 0; i < CALLER_SAVED_REGS; i++) {
+		mark_reg_not_init(env, regs, caller_saved[i]);
+		check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
+	}
+	mark_reg_kernel_value(&regs[BPF_REG_0]);
+	return 0;
+}
+
 static bool check_reg_sane_offset(struct bpf_verifier_env *env,
 				  const struct bpf_reg_state *reg,
 				  enum bpf_reg_type type)
@@ -18828,7 +18889,8 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
-				if (env->cur_state->active_lock.ptr) {
+				if (env->cur_state->active_lock.ptr &&
+				    !inside_inlinable_kfunc(env, env->insn_idx)) {
 					if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
 					    (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
 					     (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
@@ -18838,6 +18900,9 @@ static int do_check(struct bpf_verifier_env *env)
 				}
 				if (insn->src_reg == BPF_PSEUDO_CALL) {
 					err = check_func_call(env, insn, &env->insn_idx);
+				} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
+					   inside_inlinable_kfunc(env, env->insn_idx)) {
+					err = check_internal_call(env, insn);
 				} else if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 					err = check_kfunc_call(env, insn, &env->insn_idx);
 					if (!err && is_bpf_throw_kfunc(insn)) {
Signature · 1 line
2.47.0
author maintainer
#27 lore raw

RFC 9/11 bpf: move selected dynptr kfuncs to inlinable_kfuncs.c

In reply to Eduard Zingerman

Namely, move the following kfuncs:
- bpf_dynptr_is_null
- bpf_dynptr_is_rdonly
- bpf_dynptr_size
- bpf_dynptr_slice

Thus allowing verifier to inline these functions.

---
 include/linux/bpf.h           |  36 +++++++++-
 kernel/bpf/Makefile           |   1 +
 kernel/bpf/helpers.c          | 130 +---------------------------------
 kernel/bpf/inlinable_kfuncs.c | 112 +++++++++++++++++++++++++++++
 4 files changed, 148 insertions(+), 131 deletions(-)
include/linux/bpf.h +34 -2
index 75f57f791cd3..7ca53e165ab0 100644
@@ -1319,11 +1319,43 @@ enum bpf_dynptr_type {
 	BPF_DYNPTR_TYPE_XDP,
 };
 
+/* Since the upper 8 bits of dynptr->size is reserved, the
+ * maximum supported size is 2^24 - 1.
+ */
+#define DYNPTR_MAX_SIZE	((1UL << 24) - 1)
+#define DYNPTR_TYPE_SHIFT	28
+#define DYNPTR_SIZE_MASK	0xFFFFFF
+#define DYNPTR_RDONLY_BIT	BIT(31)
+
 int bpf_dynptr_check_size(u32 size);
-u32 __bpf_dynptr_size(const struct bpf_dynptr_kern *ptr);
+
+static inline u32 __bpf_dynptr_size(const struct bpf_dynptr_kern *ptr)
+{
+	return ptr->size & DYNPTR_SIZE_MASK;
+}
+
 const void *__bpf_dynptr_data(const struct bpf_dynptr_kern *ptr, u32 len);
 void *__bpf_dynptr_data_rw(const struct bpf_dynptr_kern *ptr, u32 len);
-bool __bpf_dynptr_is_rdonly(const struct bpf_dynptr_kern *ptr);
+
+static inline bool __bpf_dynptr_is_rdonly(const struct bpf_dynptr_kern *ptr)
+{
+	return ptr->size & DYNPTR_RDONLY_BIT;
+}
+
+static inline enum bpf_dynptr_type bpf_dynptr_get_type(const struct bpf_dynptr_kern *ptr)
+{
+	return (ptr->size & ~(DYNPTR_RDONLY_BIT)) >> DYNPTR_TYPE_SHIFT;
+}
+
+static inline int bpf_dynptr_check_off_len(const struct bpf_dynptr_kern *ptr, u32 offset, u32 len)
+{
+	u32 size = __bpf_dynptr_size(ptr);
+
+	if (len > size || offset > size - len)
+		return -E2BIG;
+
+	return 0;
+}
 
 #ifdef CONFIG_BPF_JIT
 int bpf_trampoline_link_prog(struct bpf_tramp_link *link,
kernel/bpf/Makefile +1 -0
index 3d7ee81c8e2e..e806b2ea5d81 100644
@@ -63,6 +63,7 @@ LLC ?= $(LLVM_PREFIX)llc$(LLVM_SUFFIX)
 # -fpatchable-function-entry=16,16 is $(PADDING_CFLAGS)
 CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(CC_FLAGS_FTRACE)
 CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(PADDING_CFLAGS)
+CFLAGS_inlinable_kfuncs.bpf.bc.o += -D__FOR_BPF
 $(obj)/inlinable_kfuncs.bpf.bc.o: $(src)/inlinable_kfuncs.c
 	$(Q)$(CLANG) $(c_flags) -emit-llvm -c $< -o $@
 
kernel/bpf/helpers.c +1 -129

161 lines not on this page · raw message

kernel/bpf/inlinable_kfuncs.c +112 -0

113 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#28 lore raw

RFC 10/11 selftests/bpf: tests to verify handling of inlined kfuncs

In reply to Eduard Zingerman

Verify that:
- kfunc callsites are treated independently;
- scalar parameters range is known in the inlined body;
- null pointer parameters are known as null in the inlined body;
- type of dynptr parameters is known in the inlined body;
- memory references are passed as KERNEL_VALUE objects;
- callee saved registers r6-r9 are spilled/filled at before/after inlined body;
- r10 escapes in kfunc body.

---
 .../selftests/bpf/bpf_testmod/Makefile        |  24 +-
 .../{bpf_testmod.c => bpf_testmod_core.c}     |  25 ++
 .../bpf/bpf_testmod/test_inlinable_kfuncs.c   | 132 +++++++++
 .../selftests/bpf/prog_tests/verifier.c       |   7 +
 .../bpf/progs/verifier_inlinable_kfuncs.c     | 253 ++++++++++++++++++
 5 files changed, 440 insertions(+), 1 deletion(-)
 rename tools/testing/selftests/bpf/bpf_testmod/{bpf_testmod.c => bpf_testmod_core.c} (97%)
 create mode 100644 tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_inlinable_kfuncs.c
tools/testing/selftests/bpf/bpf_testmod/Makefile +23 -1
index 15cb36c4483a..242669a6954a 100644
@@ -10,7 +10,9 @@ endif
 MODULES = bpf_testmod.ko
 
 obj-m += bpf_testmod.o
-CFLAGS_bpf_testmod.o = -I$(src)
+CFLAGS_bpf_testmod_core.o = -I$(src)
+
+bpf_testmod-y := bpf_testmod_core.o test_inlinable_kfuncs.o
 
 all:
 	+$(Q)make -C $(KDIR) M=$(BPF_TESTMOD_DIR) modules
@@ -18,3 +20,23 @@ all:
 clean:
 	+$(Q)make -C $(KDIR) M=$(BPF_TESTMOD_DIR) clean
 
+ifdef CONFIG_CC_IS_CLANG
+
+CLANG ?= $(LLVM_PREFIX)clang$(LLVM_SUFFIX)
+LLC ?= $(LLVM_PREFIX)llc$(LLVM_SUFFIX)
+
+CFLAGS_REMOVE_test_inlinable_kfuncs.bpf.bc.o += $(CC_FLAGS_FTRACE)
+CFLAGS_REMOVE_test_inlinable_kfuncs.bpf.bc.o += $(PADDING_CFLAGS)
+CFLAGS_test_inlinable_kfuncs.bpf.bc.o += -D__FOR_BPF
+$(obj)/test_inlinable_kfuncs.bpf.bc.o: $(src)/test_inlinable_kfuncs.c
+	$(Q)$(CLANG) $(c_flags) -emit-llvm -c $< -o $@
+
+$(obj)/test_inlinable_kfuncs.bpf.o: $(obj)/test_inlinable_kfuncs.bpf.bc.o
+	$(Q)$(LLC) -mcpu=v3 --mtriple=bpf --filetype=obj $< -o $@
+
+$(obj)/test_inlinable_kfuncs.bpf.linked.o: $(obj)/test_inlinable_kfuncs.bpf.o
+	$(Q)$(BPFTOOL) gen object $@ $<
+
+$(obj)/bpf_testmod_core.o: $(obj)/test_inlinable_kfuncs.bpf.linked.o
+
+endif
tools/testing/selftests/bpf/bpf_testmod/bpf_testmod_core.c renamed from tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c +25 -0
similarity index 97%
rename from tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
rename to tools/testing/selftests/bpf/bpf_testmod/bpf_testmod_core.c
index 987d41af71d2..586b752ad6eb 100644
@@ -586,6 +586,14 @@ BTF_ID_FLAGS(func, bpf_kfunc_trusted_num_test, KF_TRUSTED_ARGS)
 BTF_ID_FLAGS(func, bpf_kfunc_rcu_task_test, KF_RCU)
 BTF_ID_FLAGS(func, bpf_testmod_ctx_create, KF_ACQUIRE | KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_testmod_ctx_release, KF_RELEASE)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc1)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc2)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc3)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc4)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc5)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc6)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc7)
+BTF_ID_FLAGS(func, bpf_test_inline_kfunc8)
 BTF_KFUNCS_END(bpf_testmod_common_kfunc_ids)
 
 BTF_ID_LIST(bpf_testmod_dtor_ids)
@@ -1315,6 +1323,19 @@ static struct bpf_struct_ops testmod_st_ops = {
 
 extern int bpf_fentry_test1(int a);
 
+asm (
+"	.pushsection .data, \"a\"			\n"
+"	.global test_inlinable_kfuncs_data		\n"
+"test_inlinable_kfuncs_data:				\n"
+"	.incbin \"test_inlinable_kfuncs.bpf.linked.o\"	\n"
+"	.global test_inlinable_kfuncs_data_end		\n"
+"test_inlinable_kfuncs_data_end:				\n"
+"	.popsection					\n"
+);
+
+extern void test_inlinable_kfuncs_data;
+extern void test_inlinable_kfuncs_data_end;
+
 static int bpf_testmod_init(void)
 {
 	const struct btf_id_dtor_kfunc bpf_testmod_dtors[] = {
@@ -1337,6 +1358,9 @@ static int bpf_testmod_init(void)
 	ret = ret ?: register_btf_id_dtor_kfuncs(bpf_testmod_dtors,
 						 ARRAY_SIZE(bpf_testmod_dtors),
 						 THIS_MODULE);
+	ret = ret ?: bpf_register_inlinable_kfuncs(&test_inlinable_kfuncs_data,
+						 &test_inlinable_kfuncs_data_end - &test_inlinable_kfuncs_data,
+						 THIS_MODULE);
 	if (ret < 0)
 		return ret;
 	if (bpf_fentry_test1(0) < 0)
@@ -1373,6 +1397,7 @@ static void bpf_testmod_exit(void)
 	bpf_kfunc_close_sock();
 	sysfs_remove_bin_file(kernel_kobj, &bin_attr_bpf_testmod_file);
 	unregister_bpf_testmod_uprobe();
+	bpf_unregister_inlinable_kfuncs(THIS_MODULE);
 }
 
 module_init(bpf_testmod_init);
tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c new file +132 -0

132 lines not on this page · raw message

tools/testing/selftests/bpf/prog_tests/verifier.c +7 -0
index efd42c07f58a..730631603870 100644
@@ -78,6 +78,7 @@
 #include "verifier_spill_fill.skel.h"
 #include "verifier_spin_lock.skel.h"
 #include "verifier_stack_ptr.skel.h"
+#include "verifier_inlinable_kfuncs.skel.h"
 #include "verifier_subprog_precision.skel.h"
 #include "verifier_subreg.skel.h"
 #include "verifier_tailcall_jit.skel.h"
@@ -291,3 +292,9 @@ void test_verifier_value_ptr_arith(void)
 		      verifier_value_ptr_arith__elf_bytes,
 		      init_value_ptr_arith_maps);
 }
+
+/* Do not drop CAP_SYS_ADMIN for these tests */
+void test_verifier_inlinable_kfuncs(void)
+{
+	RUN_TESTS(verifier_inlinable_kfuncs);
+}
tools/testing/selftests/bpf/progs/verifier_inlinable_kfuncs.c new file +253 -0

253 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#33 lore raw

RFC 11/11 selftests/bpf: dynptr_slice benchmark

In reply to Eduard Zingerman

Benchmark to measure execution time of a simple bpf_dynptr_slice() call, when dynptr type is known and buffer__opt parameter is null. Under such conditions verifier inline the kfunc call and delete a couple of conditionals in the body of the kfunc.

---
 tools/testing/selftests/bpf/Makefile          |  2 +
 tools/testing/selftests/bpf/bench.c           |  2 +
 .../selftests/bpf/benchs/bench_dynptr_slice.c | 76 +++++++++++++++++++
 .../selftests/bpf/progs/dynptr_slice_bench.c  | 29 +++++++
 4 files changed, 109 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_dynptr_slice.c
 create mode 100644 tools/testing/selftests/bpf/progs/dynptr_slice_bench.c
tools/testing/selftests/bpf/Makefile +2 -0
index edef5df08cb2..3a938d5b295f 100644
@@ -845,6 +845,7 @@ $(OUTPUT)/bench_local_storage_create.o: $(OUTPUT)/bench_local_storage_create.ske
 $(OUTPUT)/bench_bpf_hashmap_lookup.o: $(OUTPUT)/bpf_hashmap_lookup.skel.h
 $(OUTPUT)/bench_htab_mem.o: $(OUTPUT)/htab_mem_bench.skel.h
 $(OUTPUT)/bench_bpf_crypto.o: $(OUTPUT)/crypto_bench.skel.h
+$(OUTPUT)/bench_dynptr_slice.o: $(OUTPUT)/dynptr_slice_bench.skel.h
 $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ)
 $(OUTPUT)/bench: LDLIBS += -lm
 $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -865,6 +866,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \
 		 $(OUTPUT)/bench_local_storage_create.o \
 		 $(OUTPUT)/bench_htab_mem.o \
 		 $(OUTPUT)/bench_bpf_crypto.o \
+		 $(OUTPUT)/bench_dynptr_slice.o \
 		 #
 	$(call msg,BINARY,,$@)
 	$(Q)$(CC) $(CFLAGS) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +2 -0
index 1bd403a5ef7b..74053665465c 100644
@@ -549,6 +549,7 @@ extern const struct bench bench_local_storage_create;
 extern const struct bench bench_htab_mem;
 extern const struct bench bench_crypto_encrypt;
 extern const struct bench bench_crypto_decrypt;
+extern const struct bench bench_dynptr_slice;
 
 static const struct bench *benchs[] = {
 	&bench_count_global,
@@ -609,6 +610,7 @@ static const struct bench *benchs[] = {
 	&bench_htab_mem,
 	&bench_crypto_encrypt,
 	&bench_crypto_decrypt,
+	&bench_dynptr_slice,
 };
 
 static void find_benchmark(void)
tools/testing/selftests/bpf/benchs/bench_dynptr_slice.c new file +76 -0

76 lines not on this page · raw message

tools/testing/selftests/bpf/progs/dynptr_slice_bench.c new file +29 -0
new file mode 100644
index 000000000000..65a493426b5e
@@ -0,0 +1,29 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include "bpf_compiler.h"
+#include "bpf_kfuncs.h"
+
+long hits = 0;
+
+SEC("tc")
+int dynptr_slice(struct __sk_buff *skb)
+{
+	struct bpf_dynptr psrc;
+	const int N = 100;
+	int i;
+
+	bpf_dynptr_from_skb(skb, 0, &psrc);
+__pragma_loop_unroll_full
+	for (i = 0; i < N; ++i) {
+		bpf_dynptr_slice(&psrc, i, NULL, 1);
+	}
+	__sync_add_and_fetch(&hits, N);
+
+	return 0;
+}
+
+char __license[] SEC("license") = "GPL";
Signature · 1 line
2.47.0
#29 lore raw

Re: [RFC bpf-next 10/11] selftests/bpf: tests to verify handling of inlined kfuncs

In reply to Eduard Zingerman

On 11/7/24 09:50, Eduard Zingerman wrote:
...

Quoted 6 lines
tools/testing/selftests/bpf/bpf_testmod/test_inlinable_kfuncs.c new file +0 -0
new file mode 100644
index 000000000000..d8b90ee7f2b0
@@ -0,0 +1,132 @@

...

Quoted 1 line

+MODULE_LICENSE("Dual BSD/GPL");

Since commit 1fffe7a34c89 ("script: modpost: emit a warning when the description is missing"), a module without a MODULE_DESCRIPTION() will result in a warning when built with make W=1. Not sure if this is applicable to your new module, but if so, please add the missing MODULE_DESCRIPTION().

author maintainer
#30 lore raw

Re: [RFC bpf-next 10/11] selftests/bpf: tests to verify handling of inlined kfuncs

On Thu, 2024-11-07 at 14:04 -0800, Jeff Johnson wrote:

[...]

Quoted 6 lines

Since commit 1fffe7a34c89 ("script: modpost: emit a warning when the description is missing"), a module without a MODULE_DESCRIPTION() will result in a warning when built with make W=1. Not sure if this is applicable to your new module, but if so, please add the missing MODULE_DESCRIPTION().

Hi Jeff,

Thank you for the heads-up.
The MODULE_DESCRIPTION is already present in the bpf_testmod.c (this file is renamed in the RFC, but remains as a part of the module).

#31 lore raw

Re: [RFC bpf-next 10/11] selftests/bpf: tests to verify handling of inlined kfuncs

Quoted 11 lines · Eduard Zingerman

On Thu, 2024-11-07 at 14:04 -0800, Jeff Johnson wrote:

[...]

Quoted 6 lines

Since commit 1fffe7a34c89 ("script: modpost: emit a warning when the description is missing"), a module without a MODULE_DESCRIPTION() will result in a warning when built with make W=1. Not sure if this is applicable to your new module, but if so, please add the missing MODULE_DESCRIPTION().

Quoted 5 lines

Hi Jeff,

Thank you for the heads-up.
The MODULE_DESCRIPTION is already present in the bpf_testmod.c (this file is renamed in the RFC, but remains as a part of the module).

Does bpf_testmod.c already have a MODULE_LICENSE(). If so, then I'd drop the extra one in test_inlinable_kfuncs.c.

My reviews on this subject are triggered by the lore search pattern:
MODULE_LICENSE AND NOT MODULE_DESCRIPTION

Since it is expected that the two should appear together.

author maintainer
#32 lore raw

Re: [RFC bpf-next 10/11] selftests/bpf: tests to verify handling of inlined kfuncs

On Thu, 2024-11-07 at 14:19 -0800, Jeff Johnson wrote:

[...]

Quoted 2 lines

Does bpf_testmod.c already have a MODULE_LICENSE(). If so, then I'd drop the extra one in test_inlinable_kfuncs.c.

It does, will drop the license line from test_inlinable_kfuncs.c.

Quoted 4 lines

My reviews on this subject are triggered by the lore search pattern:
MODULE_LICENSE AND NOT MODULE_DESCRIPTION

Since it is expected that the two should appear together.

Understood, thank you for explaining.

#15 lore raw

Re: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs

In reply to Eduard Zingerman
kernel test robot noticed the following build warnings:

Hi Eduard,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build warnings:

[auto build test WARNING on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Eduard-Zingerman/bpf-use-branch-predictions-in-opt_hard_wire_dead_code_branches/20241108-015243
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20241107175040.1659341-4-eddyz87%40gmail.com
patch subject: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs
config: x86_64-rhel-8.3 (https://download.01.org/0day-ci/archive/20241108/[email protected]/config)
compiler: gcc-12 (Debian 12.2.0-14) 12.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241108/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All warnings (new ones prefixed by >>):

kernel/bpf/verifier.c: In function 'inlinable_kfuncs_init':

>> kernel/bpf/verifier.c:20910:46: warning: taking address of expression of type 'void'
   20910 |         return bpf_register_inlinable_kfuncs(&inlinable_kfuncs_data,
         |                                              ^
   kernel/bpf/verifier.c:20911:44: warning: taking address of expression of type 'void'
   20911 |                                            &inlinable_kfuncs_data_end - &inlinable_kfuncs_data);
         |                                            ^
   kernel/bpf/verifier.c:20911:73: warning: taking address of expression of type 'void'
   20911 |                                            &inlinable_kfuncs_data_end - &inlinable_kfuncs_data);
         |                                                                         ^
   /tmp/cccS126M.s: Assembler messages:
>> /tmp/cccS126M.s:12: Warning: ignoring changed section attributes for .data

/tmp/cccS126M.s:15: Error: file not found: kernel/bpf/inlinable_kfuncs.bpf.linked.o

vim +/void +20910 kernel/bpf/verifier.c

20907
20908 static int __init inlinable_kfuncs_init(void)
20909 {
20910 return bpf_register_inlinable_kfuncs(&inlinable_kfuncs_data,
20911 &inlinable_kfuncs_data_end - &inlinable_kfuncs_data);
20912 }
20913

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#34 lore raw
In reply to Eduard Zingerman
Quoted 9 lines · Eduard Zingerman

Some time ago, in an off-list discussion, Alexei Starovoitov suggested compiling certain kfuncs to BPF to allow inlining calls to such kfuncs during verification. This RFC explores the idea.

This RFC introduces a notion of inlinable BPF kfuncs. Inlinable kfuncs are compiled to BPF and are inlined by verifier after program verification. Inlined kfunc bodies are subject to dead code removal and removal of conditional jumps, if such jumps are proved to always follow a single branch.

Ohh, this is very exciting!

Mostly want to comment on this bit:

Quoted 5 lines

Imo, this RFC is worth following through only if number of kfuncs benefiting from inlining is big. If the set is limited to dynptr family of functions, it is simpler to add a number of hard-coded inlining templates for such functions (similarly to what is currently done for some helpers).

One place where this would definitely be applicable is in all the XDP HW metadata kfuncs. Right now, there's a function call for each piece of HW metadata that an XDP program wants to read, which quickly adds up. And in XDP land we are counting function calls, as the overhead (~1.1 ns) is directly measurable in XDP PPS performance.

Back when we settled on the kfunc approach to reading metadata, we were discussing this overhead, obviously, and whether we should do the bespoke BPF assembly type inlining that we currently do for map lookups and that sort of thing. We were told that the "right" way to do the inlining is something along the lines of what you are proposing here, so I would very much encourage you to continue working on this!

One complication for the XDP kfuncs is that the kfunc that the BPF program calls is actually a stub function in the kernel core; at verification time, the actual function call is replaced with one from the network driver (see bpf_dev_bound_resolve_kfunc()). So somehow supporting this (with kfuncs defined in drivers, i.e., in modules) would be needed for the XDP use case.

Happy to help with benchmarking for the XDP use case when/if this can be supported, of course! :)

(+Jesper, who I'm sure will be happy to help as well)

-Toke

#16 lore raw

Re: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs

In reply to Eduard Zingerman
Quoted 2 lines · Eduard Zingerman

Inlinable kfuncs are available only if CLANG is used for kernel compilation.

To what extent is this a fundamental limitation? AFAIU, this comes from the fact that you are re-using the intermediate compilation stages, right? But if those are absent, couldn't we just invoke a full clang compile from source of the same file (so you could get the inlining even when compiling with GCC)?

-Toke

author maintainer
#17 lore raw

Re: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs

Quoted 8 lines · Toke Høiland-Jørgensen
Quoted 2 lines · Eduard Zingerman

Inlinable kfuncs are available only if CLANG is used for kernel compilation.

To what extent is this a fundamental limitation? AFAIU, this comes from the fact that you are re-using the intermediate compilation stages, right?

Yes, the main obstacle is C --clang--> bitcode as for host --llc--> BPF pipeline. And this intermediate step is needed to include some of the header files as-is (but not all will work, e.g. those where host inline assembly is not dead-code-eliminated by optimizer would error out). The reason why 'clang --target=bpf' can't be used with these headers is that headers check current architecture in various places, however:
- there is no BPF architecture defined at the moment;
- most of the time host architecture is what's needed, e.g.
here is a fragment of arch/x86/include/asm/current.h:

  struct pcpu_hot {
  	union {
  		struct {
  			struct task_struct	*current_task;
  			int			preempt_count;
  			int			cpu_number;
  #ifdef CONFIG_MITIGATION_CALL_DEPTH_TRACKING
  			u64			call_depth;
  #endif
  			unsigned long		top_of_stack;
  			void			*hardirq_stack_ptr;
  			u16			softirq_pending;
  #ifdef CONFIG_X86_64
  			bool			hardirq_stack_inuse;
  #else
  			void			*softirq_stack_ptr;
  #endif
  		};
  		u8	pad[64];
  	};
  };

In case if inlinable kfunc operates on pcpu_hot structure, it has to see same binary layout as the host.
So, technically, 'llc' step is not necessary, but if it is not present something else should be done about header files.

Quoted 3 lines

But if those are absent, couldn't we just invoke a full clang compile from source of the same file (so you could get the inlining even when compiling with GCC)?

Yes, hybrid should work w/o problems if headers are dealt with in some other way.

author maintainer
#35 lore raw
In reply to Toke Høiland-Jørgensen

On Fri, 2024-11-08 at 21:41 +0100, Toke Høiland-Jørgensen wrote:

[...]

Hi Toke,

Quoted 7 lines

Back when we settled on the kfunc approach to reading metadata, we were discussing this overhead, obviously, and whether we should do the bespoke BPF assembly type inlining that we currently do for map lookups and that sort of thing. We were told that the "right" way to do the inlining is something along the lines of what you are proposing here, so I would very much encourage you to continue working on this!

Quoted 6 lines

One complication for the XDP kfuncs is that the kfunc that the BPF program calls is actually a stub function in the kernel core; at verification time, the actual function call is replaced with one from the network driver (see bpf_dev_bound_resolve_kfunc()). So somehow supporting this (with kfuncs defined in drivers, i.e., in modules) would be needed for the XDP use case.

Thank you for the pointer to bpf_dev_bound_resolve_kfunc(). Looking at specialize_kfunc(), I will have to extend the interface for selecting inlinable function body. The inlinable kfuncs already could be defined in modules, so this should be a relatively small adjustment.

Quoted 4 lines

Happy to help with benchmarking for the XDP use case when/if this can be supported, of course! :)

(+Jesper, who I'm sure will be happy to help as well)

Thank you, help with benchmarking is most welcome.
Very interested in real-world benchmarks, as I'm not fully sold on this feature, it adds significant layer of complexity to the verifier. I'll reach to you and Jesper after adding support for inlining of XDP metadata kfuncs.

Thanks,
Eduard

#21 lore raw

Re: [RFC bpf-next 04/11] bpf: allow specifying inlinable kfuncs in modules

In reply to Eduard Zingerman
kernel test robot noticed the following build errors:

Hi Eduard,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Eduard-Zingerman/bpf-use-branch-predictions-in-opt_hard_wire_dead_code_branches/20241108-015243
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20241107175040.1659341-5-eddyz87%40gmail.com
patch subject: [RFC bpf-next 04/11] bpf: allow specifying inlinable kfuncs in modules
config: openrisc-allnoconfig (https://download.01.org/0day-ci/archive/20241109/[email protected]/config)
compiler: or1k-linux-gcc (GCC) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241109/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All error/warnings (new ones prefixed by >>):

In file included from include/linux/bpf.h:28,

                    from include/linux/security.h:35,
                    from include/linux/perf_event.h:62,
                    from include/linux/trace_events.h:10,
                    from include/trace/syscall.h:7,
                    from include/linux/syscalls.h:93,
                    from init/main.c:21:
>> include/linux/btf.h:674:13: warning: no previous prototype for 'btf_get_module_btf' [-Wmissing-prototypes]

674 | struct btf *btf_get_module_btf(const struct module *module)
| ^~~~~~~~~~~~~~~~~~
--
In file included from include/linux/bpf.h:28,

                    from include/linux/security.h:35,
                    from include/net/scm.h:9,
                    from include/linux/netlink.h:9,
                    from include/uapi/linux/neighbour.h:6,
                    from include/linux/netdevice.h:44,
                    from include/net/sock.h:46,
                    from include/linux/tcp.h:19,
                    from include/linux/ipv6.h:102,
                    from include/net/addrconf.h:65,
                    from lib/vsprintf.c:41:
>> include/linux/btf.h:674:13: warning: no previous prototype for 'btf_get_module_btf' [-Wmissing-prototypes]
     674 | struct btf *btf_get_module_btf(const struct module *module)
         |             ^~~~~~~~~~~~~~~~~~
   lib/vsprintf.c: In function 'va_format':
   lib/vsprintf.c:1683:9: warning: function 'va_format' might be a candidate for 'gnu_printf' format attribute [-Wsuggest-attribute=format]
    1683 |         buf += vsnprintf(buf, end > buf ? end - buf : 0, va_fmt->fmt, va);
         |         ^~~

--
In file included from include/linux/bpf.h:28,
from include/linux/security.h:35, from include/linux/perf_event.h:62, from include/linux/trace_events.h:10, from include/trace/syscall.h:7, from include/linux/syscalls.h:93, from kernel/time/hrtimer.c:30:

>> include/linux/btf.h:674:13: warning: no previous prototype for 'btf_get_module_btf' [-Wmissing-prototypes]

674 | struct btf *btf_get_module_btf(const struct module *module)
| ^~~~~~~~~~~~~~~~~~
kernel/time/hrtimer.c:121:35: warning: initialized field overwritten [-Woverride-init]
121 | [CLOCK_REALTIME] = HRTIMER_BASE_REALTIME,
| ^~~~~~~~~~~~~~~~~~~~~
kernel/time/hrtimer.c:121:35: note: (near initialization for 'hrtimer_clock_to_base_table[0]') kernel/time/hrtimer.c:122:35: warning: initialized field overwritten [-Woverride-init]
122 | [CLOCK_MONOTONIC] = HRTIMER_BASE_MONOTONIC,
| ^~~~~~~~~~~~~~~~~~~~~~
kernel/time/hrtimer.c:122:35: note: (near initialization for 'hrtimer_clock_to_base_table[1]') kernel/time/hrtimer.c:123:35: warning: initialized field overwritten [-Woverride-init]
123 | [CLOCK_BOOTTIME] = HRTIMER_BASE_BOOTTIME,
| ^~~~~~~~~~~~~~~~~~~~~
kernel/time/hrtimer.c:123:35: note: (near initialization for 'hrtimer_clock_to_base_table[7]') kernel/time/hrtimer.c:124:35: warning: initialized field overwritten [-Woverride-init]
124 | [CLOCK_TAI] = HRTIMER_BASE_TAI,
| ^~~~~~~~~~~~~~~~
kernel/time/hrtimer.c:124:35: note: (near initialization for 'hrtimer_clock_to_base_table[11]')
--
or1k-linux-ld: init/do_mounts.o: in function `btf_get_module_btf':

>> do_mounts.c:(.text+0x8): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here

or1k-linux-ld: init/noinitramfs.o: in function `btf_get_module_btf':
noinitramfs.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: arch/openrisc/kernel/sys_call_table.o: in function `btf_get_module_btf':
sys_call_table.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: arch/openrisc/mm/fault.o: in function `btf_get_module_btf':
fault.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/fork.o: in function `btf_get_module_btf':
fork.c:(.text+0x1198): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/exec_domain.o: in function `btf_get_module_btf':
exec_domain.c:(.text+0x28): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/cpu.o: in function `btf_get_module_btf':
cpu.c:(.text+0x880): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/exit.o: in function `btf_get_module_btf':
exit.c:(.text+0x99c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/resource.o: in function `btf_get_module_btf':
resource.c:(.text+0x14c8): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sysctl.o: in function `btf_get_module_btf':
sysctl.c:(.text+0x241c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/capability.o: in function `btf_get_module_btf':
capability.c:(.text+0x87c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/ptrace.o: in function `btf_get_module_btf':
ptrace.c:(.text+0x5c0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/signal.o: in function `btf_get_module_btf':
signal.c:(.text+0x1f04): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sys.o: in function `btf_get_module_btf':
sys.c:(.text+0x1548): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/umh.o: in function `btf_get_module_btf':
umh.c:(.text+0x9ac): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/pid.o: in function `btf_get_module_btf':
pid.c:(.text+0x558): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/extable.o: in function `btf_get_module_btf':
extable.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/params.o: in function `btf_get_module_btf':
params.c:(.text+0xcec): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/nsproxy.o: in function `btf_get_module_btf':
nsproxy.c:(.text+0x224): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/cred.o: in function `btf_get_module_btf':
cred.c:(.text+0xa70): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/reboot.o: in function `btf_get_module_btf':
reboot.c:(.text+0x1064): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/ksyms_common.o: in function `btf_get_module_btf':
ksyms_common.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/groups.o: in function `btf_get_module_btf':
groups.c:(.text+0x354): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sched/core.o: in function `btf_get_module_btf':
core.c:(.text+0x604): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sched/fair.o: in function `btf_get_module_btf':
fair.c:(.text+0x2af0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sched/build_policy.o: in function `btf_get_module_btf':
build_policy.c:(.text+0x3f48): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/sched/build_utility.o: in function `btf_get_module_btf':
build_utility.c:(.text+0x1598): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/power/qos.o: in function `btf_get_module_btf':
qos.c:(.text+0x174): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/printk/printk.o: in function `btf_get_module_btf':
printk.c:(.text+0x26a4): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/time.o: in function `btf_get_module_btf':
time.c:(.text+0x1714): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/timer.o: in function `btf_get_module_btf':
timer.c:(.text+0x183c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/hrtimer.o: in function `btf_get_module_btf':
hrtimer.c:(.text+0x1850): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/posix-timers.o: in function `btf_get_module_btf':
posix-timers.c:(.text+0x1230): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/posix-clock.o: in function `btf_get_module_btf':
posix-clock.c:(.text+0x854): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/itimer.o: in function `btf_get_module_btf':
itimer.c:(.text+0x76c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/time/tick-common.o: in function `btf_get_module_btf':
tick-common.c:(.text+0xec): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/futex/syscalls.o: in function `btf_get_module_btf':
syscalls.c:(.text+0x154): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/uid16.o: in function `btf_get_module_btf':
uid16.c:(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: kernel/kallsyms.o: in function `btf_get_module_btf':
kallsyms.c:(.text+0xb08): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/filemap.o: in function `btf_get_module_btf':
filemap.c:(.text+0x4574): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/oom_kill.o: in function `btf_get_module_btf':
oom_kill.c:(.text+0xd8c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/fadvise.o: in function `btf_get_module_btf':
fadvise.c:(.text+0x38c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/page-writeback.o: in function `btf_get_module_btf':
page-writeback.c:(.text+0x29dc): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/readahead.o: in function `btf_get_module_btf':
readahead.c:(.text+0x918): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/truncate.o: in function `btf_get_module_btf':
truncate.c:(.text+0xc10): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/vmscan.o: in function `btf_get_module_btf':
vmscan.c:(.text+0x2c0c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/shmem.o: in function `btf_get_module_btf':
shmem.c:(.text+0x34b0): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/util.o: in function `btf_get_module_btf':
util.c:(.text+0x145c): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/workingset.o: in function `btf_get_module_btf':
workingset.c:(.text+0x380): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/debug.o: in function `btf_get_module_btf':
debug.c:(.text+0x450): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here
or1k-linux-ld: mm/gup.o: in function `btf_get_module_btf':
gup.c:(.text+0x1288): multiple definition of `btf_get_module_btf'; init/main.o:main.c:(.text+0x0): first defined here

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#22 lore raw

Re: [RFC bpf-next 04/11] bpf: allow specifying inlinable kfuncs in modules

In reply to Eduard Zingerman
kernel test robot noticed the following build errors:

Hi Eduard,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Eduard-Zingerman/bpf-use-branch-predictions-in-opt_hard_wire_dead_code_branches/20241108-015243
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20241107175040.1659341-5-eddyz87%40gmail.com
patch subject: [RFC bpf-next 04/11] bpf: allow specifying inlinable kfuncs in modules
config: parisc-allnoconfig (https://download.01.org/0day-ci/archive/20241109/[email protected]/config)
compiler: hppa-linux-gcc (GCC) 14.2.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241109/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

hppa-linux-ld: init/do_mounts.o: in function `btf_get_module_btf':

>> (.text+0x1c): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here

hppa-linux-ld: init/noinitramfs.o: in function `btf_get_module_btf':
(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: arch/parisc/mm/fault.o: in function `btf_get_module_btf':
(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: arch/parisc/kernel/cache.o: in function `btf_get_module_btf':
(.text+0x418): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: arch/parisc/kernel/sys_parisc.o: in function `btf_get_module_btf':
(.text+0x374): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: arch/parisc/kernel/ptrace.o: in function `btf_get_module_btf':
(.text+0x404): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: arch/parisc/kernel/parisc_ksyms.o: in function `btf_get_module_btf':
(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/fork.o: in function `btf_get_module_btf':
(.text+0xf18): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/exec_domain.o: in function `btf_get_module_btf':
(.text+0x28): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/cpu.o: in function `btf_get_module_btf':
(.text+0x720): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/exit.o: in function `btf_get_module_btf':
(.text+0x804): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/resource.o: in function `btf_get_module_btf':
(.text+0x10a4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sysctl.o: in function `btf_get_module_btf':
(.text+0x2010): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/capability.o: in function `btf_get_module_btf':
(.text+0x604): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/ptrace.o: in function `btf_get_module_btf':
(.text+0x4d4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/signal.o: in function `btf_get_module_btf':
(.text+0x19dc): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sys.o: in function `btf_get_module_btf':
(.text+0x11c4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/umh.o: in function `btf_get_module_btf':
(.text+0x8e4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/pid.o: in function `btf_get_module_btf':
(.text+0x49c): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/extable.o: in function `btf_get_module_btf':
(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/params.o: in function `btf_get_module_btf':
(.text+0xcf0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/nsproxy.o: in function `btf_get_module_btf':
(.text+0x200): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/cred.o: in function `btf_get_module_btf':
(.text+0x7e0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/reboot.o: in function `btf_get_module_btf':
(.text+0xfb8): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/ksyms_common.o: in function `btf_get_module_btf':
(.text+0x0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/groups.o: in function `btf_get_module_btf':
(.text+0x2cc): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sched/core.o: in function `btf_get_module_btf':
(.text+0x544): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sched/fair.o: in function `btf_get_module_btf':
(.text+0x1de8): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sched/build_policy.o: in function `btf_get_module_btf':
(.text+0x2ff0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/sched/build_utility.o: in function `btf_get_module_btf':
(.text+0xf00): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/power/qos.o: in function `btf_get_module_btf':
(.text+0x184): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/printk/printk.o: in function `btf_get_module_btf':
(.text+0x2228): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/time.o: in function `btf_get_module_btf':
(.text+0x1f38): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/timer.o: in function `btf_get_module_btf':
(.text+0x1170): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/hrtimer.o: in function `btf_get_module_btf':
(.text+0x1154): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/posix-timers.o: in function `btf_get_module_btf':
(.text+0x13d4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/posix-clock.o: in function `btf_get_module_btf':
(.text+0x7fc): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/itimer.o: in function `btf_get_module_btf':
(.text+0x7b0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/time/tick-common.o: in function `btf_get_module_btf':
(.text+0x178): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/futex/syscalls.o: in function `btf_get_module_btf':
(.text+0x18c): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: kernel/kallsyms.o: in function `btf_get_module_btf':
(.text+0x980): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/filemap.o: in function `btf_get_module_btf':
(.text+0x38f0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/oom_kill.o: in function `btf_get_module_btf':
(.text+0xb48): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/fadvise.o: in function `btf_get_module_btf':
(.text+0x2f8): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/page-writeback.o: in function `btf_get_module_btf':
(.text+0x21b8): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/readahead.o: in function `btf_get_module_btf':
(.text+0x734): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/truncate.o: in function `btf_get_module_btf':
(.text+0x9b4): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/vmscan.o: in function `btf_get_module_btf':
(.text+0x2424): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/shmem.o: in function `btf_get_module_btf':
(.text+0x2cc8): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/util.o: in function `btf_get_module_btf':
(.text+0x101c): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here
hppa-linux-ld: mm/workingset.o: in function `btf_get_module_btf':
(.text+0x2e0): multiple definition of `btf_get_module_btf'; init/main.o:(.text+0x0): first defined here

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#18 lore raw

Re: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs

In reply to Eduard Zingerman
Quoted 42 lines · Eduard Zingerman
Quoted 8 lines · Toke Høiland-Jørgensen
Quoted 2 lines · Eduard Zingerman

Inlinable kfuncs are available only if CLANG is used for kernel compilation.

To what extent is this a fundamental limitation? AFAIU, this comes from the fact that you are re-using the intermediate compilation stages, right?

Yes, the main obstacle is C --clang--> bitcode as for host --llc--> BPF pipeline. And this intermediate step is needed to include some of the header files as-is (but not all will work, e.g. those where host inline assembly is not dead-code-eliminated by optimizer would error out). The reason why 'clang --target=bpf' can't be used with these headers is that headers check current architecture in various places, however:
- there is no BPF architecture defined at the moment;
- most of the time host architecture is what's needed, e.g.
here is a fragment of arch/x86/include/asm/current.h:

  struct pcpu_hot {
  	union {
  		struct {
  			struct task_struct	*current_task;
  			int			preempt_count;
  			int			cpu_number;
  #ifdef CONFIG_MITIGATION_CALL_DEPTH_TRACKING
  			u64			call_depth;
  #endif
  			unsigned long		top_of_stack;
  			void			*hardirq_stack_ptr;
  			u16			softirq_pending;
  #ifdef CONFIG_X86_64
  			bool			hardirq_stack_inuse;
  #else
  			void			*softirq_stack_ptr;
  #endif
  		};
  		u8	pad[64];
  	};
  };
Quoted 4 lines

In case if inlinable kfunc operates on pcpu_hot structure, it has to see same binary layout as the host.
So, technically, 'llc' step is not necessary, but if it is not present something else should be done about header files.

Right, makes sense. Do any of the kfuncs you are targeting currently use headers that have this problem? If not, could a stopgap solution be to just restrict the set of kfuncs that can be inlined to those that can be compiled with clang --target=bpf? That may require moving around some code a bit, but there are other examples where all the kfuncs for a subsystem are kept in a separate .c file anyway (IIRC, netfilter does this).

Quoted 6 lines
Quoted 3 lines

But if those are absent, couldn't we just invoke a full clang compile from source of the same file (so you could get the inlining even when compiling with GCC)?

Yes, hybrid should work w/o problems if headers are dealt with in some other way.

But couldn't a hybrid approach be used even in the case of GCC compilation? I.e., compile it both with GCC (for inclusion into vmlinux/.ko file) and once with clang (in host mode) and then pass it through LLC to generate BPF?

-Toke

#36 lore raw
In reply to Eduard Zingerman
Quoted 20 lines · Eduard Zingerman

On Fri, 2024-11-08 at 21:41 +0100, Toke Høiland-Jørgensen wrote:

[...]

Hi Toke,

Quoted 7 lines

Back when we settled on the kfunc approach to reading metadata, we were discussing this overhead, obviously, and whether we should do the bespoke BPF assembly type inlining that we currently do for map lookups and that sort of thing. We were told that the "right" way to do the inlining is something along the lines of what you are proposing here, so I would very much encourage you to continue working on this!

Quoted 6 lines

One complication for the XDP kfuncs is that the kfunc that the BPF program calls is actually a stub function in the kernel core; at verification time, the actual function call is replaced with one from the network driver (see bpf_dev_bound_resolve_kfunc()). So somehow supporting this (with kfuncs defined in drivers, i.e., in modules) would be needed for the XDP use case.

Quoted 4 lines

Thank you for the pointer to bpf_dev_bound_resolve_kfunc(). Looking at specialize_kfunc(), I will have to extend the interface for selecting inlinable function body. The inlinable kfuncs already could be defined in modules, so this should be a relatively small adjustment.

Awesome!

Quoted 10 lines
Quoted 4 lines

Happy to help with benchmarking for the XDP use case when/if this can be supported, of course! :)

(+Jesper, who I'm sure will be happy to help as well)

Thank you, help with benchmarking is most welcome.
Very interested in real-world benchmarks, as I'm not fully sold on this feature, it adds significant layer of complexity to the verifier. I'll reach to you and Jesper after adding support for inlining of XDP metadata kfuncs.

Sounds good, thanks!

-Toke

author maintainer
#2 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Eduard Zingerman
Quoted 13 lines · Eduard Zingerman

Consider dead code elimination problem for program like below:

    main:
      1: r1 = 42
      2: call <subprogram>;
      3: exit

    subprogram:
      4: r0 = 1
      5: if r1 != 42 goto +1
      6: r0 = 2
      7: exit;
Quoted 5 lines

Here verifier would visit every instruction and thus bpf_insn_aux_data->seen flag would be set for both true (7) and falltrhough (6) branches of conditional (5). Hence opt_hard_wire_dead_code_branches() will not replace conditional (5) with unconditional jump.

[...]

Had an off-list discussion with Alexei yesterday,
here are some answers to questions raised:
- The patches #1,2 with opt_hard_wire_dead_code_branches() changes are not necessary for dynptr_slice kfunc inlining / branch removal. I will drop these patches and adjust test cases.
- Did some measurements for dynptr_slice call using simple benchmark from patch #11:
- baseline:

    76.167 ± 0.030M/s million calls per second;
  - with call inlining, but without branch pruning (only patch #3):
    101.198 ± 0.101M/s million calls per second;
  - with call inlining and with branch pruning (full patch-set):
    116.935 ± 0.142M/s million calls per second.
#12 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Eduard Zingerman
Quoted 48 lines · Eduard Zingerman

Consider dead code elimination problem for program like below:

    main:
      1: r1 = 42
      2: call <subprogram>;
      3: exit

    subprogram:
      4: r0 = 1
      5: if r1 != 42 goto +1
      6: r0 = 2
      7: exit;

Here verifier would visit every instruction and thus bpf_insn_aux_data->seen flag would be set for both true (7) and falltrhough (6) branches of conditional (5). Hence opt_hard_wire_dead_code_branches() will not replace conditional (5) with unconditional jump.

To cover such cases:
- add two fields in struct bpf_insn_aux_data:
- true_branch_taken;
- false_branch_taken;
- adjust check_cond_jmp_op() to set the fields according to jump predictions;
- handle these flags in the opt_hard_wire_dead_code_branches():
- true_branch_taken && !false_branch_taken

    always jump, replace instruction with 'goto off';
  - !true_branch_taken && false_branch_taken
    always falltrhough, replace with 'goto +0';
  - true_branch_taken && false_branch_taken
    jump and falltrhough are possible, don't change the instruction;

- !true_branch_taken && !false_branch_taken
neither jump, nor falltrhough are possible, if condition itself must be a dead code (should be removed by opt_remove_dead_code).

---
 include/linux/bpf_verifier.h |  4 +++-
 kernel/bpf/verifier.c        | 16 ++++++++++++----
 2 files changed, 15 insertions(+), 5 deletions(-)
include/linux/bpf_verifier.h +0 -0
index 4513372c5bc8..ed4eacfd4db7 100644

include/linux/bpf_verifier.h struct bpf_insn_aux_data { · line 575

Quoted 7 lines
include/linux/bpf_verifier.h +3 -1
@@ -570,7 +570,9 @@ struct bpf_insn_aux_data {
        struct btf_struct_meta *kptr_struct_meta;
        u64 map_key_state; /* constant (32 bit) key tracking for maps */
        int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
-       u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
+       bool seen; /* this insn was processed by the verifier at env->pass_cnt */
+       bool true_branch_taken; /* for cond jumps, set if verifier ever took true branch */
+       bool false_branch_taken; /* for cond jumps, set if verifier ever took false branch */

we'll now have 12 bool fields in bpf_insn_aux_data, probably it's time to switch to bitfields for those (even though you are trading 4 for 3 bytes here), 72+ bytes per instruction is not unnoticeable, especially for big BPF programs

Quoted 3 lines
include/linux/bpf_verifier.h +0 -0
        bool sanitize_stack_spill; /* subject to Spectre v4 sanitation */
        bool zext_dst; /* this insn zero extends dst reg */
        bool needs_zext; /* alu op needs to clear upper bits */

[...]

#3 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Eduard Zingerman
Quoted 31 lines · Eduard Zingerman
Quoted 13 lines · Eduard Zingerman

Consider dead code elimination problem for program like below:

    main:
      1: r1 = 42
      2: call <subprogram>;
      3: exit

    subprogram:
      4: r0 = 1
      5: if r1 != 42 goto +1
      6: r0 = 2
      7: exit;
Quoted 5 lines

Here verifier would visit every instruction and thus bpf_insn_aux_data->seen flag would be set for both true (7) and falltrhough (6) branches of conditional (5). Hence opt_hard_wire_dead_code_branches() will not replace conditional (5) with unconditional jump.

[...]

Had an off-list discussion with Alexei yesterday,
here are some answers to questions raised:
- The patches #1,2 with opt_hard_wire_dead_code_branches() changes are not necessary for dynptr_slice kfunc inlining / branch removal. I will drop these patches and adjust test cases.
- Did some measurements for dynptr_slice call using simple benchmark from patch #11:
- baseline:

Quoted 6 lines
    76.167 ± 0.030M/s million calls per second;
  - with call inlining, but without branch pruning (only patch #3):
    101.198 ± 0.101M/s million calls per second;
  - with call inlining and with branch pruning (full patch-set):
    116.935 ± 0.142M/s million calls per second.

This true/false logic seems generally useful not just for this use case, is there anything wrong with landing it? Seems pretty straightforward. I'd split it from the kfunc inlining and land independently.

#4 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

Quoted 40 lines · Andrii Nakryiko
Quoted 31 lines · Eduard Zingerman
Quoted 13 lines · Eduard Zingerman

Consider dead code elimination problem for program like below:

    main:
      1: r1 = 42
      2: call <subprogram>;
      3: exit

    subprogram:
      4: r0 = 1
      5: if r1 != 42 goto +1
      6: r0 = 2
      7: exit;
Quoted 5 lines

Here verifier would visit every instruction and thus bpf_insn_aux_data->seen flag would be set for both true (7) and falltrhough (6) branches of conditional (5). Hence opt_hard_wire_dead_code_branches() will not replace conditional (5) with unconditional jump.

[...]

Had an off-list discussion with Alexei yesterday,
here are some answers to questions raised:
- The patches #1,2 with opt_hard_wire_dead_code_branches() changes are not necessary for dynptr_slice kfunc inlining / branch removal. I will drop these patches and adjust test cases.
- Did some measurements for dynptr_slice call using simple benchmark from patch #11:
- baseline:

Quoted 6 lines
    76.167 ± 0.030M/s million calls per second;
  - with call inlining, but without branch pruning (only patch #3):
    101.198 ± 0.101M/s million calls per second;
  - with call inlining and with branch pruning (full patch-set):
    116.935 ± 0.142M/s million calls per second.
Quoted 4 lines

This true/false logic seems generally useful not just for this use case, is there anything wrong with landing it? Seems pretty straightforward. I'd split it from the kfunc inlining and land independently.

I was also always hoping that we'll eventually optimize the following pattern:

r1 = *(global var)
if r1 == 1 /* always 1 or 0 */
goto +...
...

This is extremely common with .rodata global variables, and while the branches are dead code eliminated, memory reads are not. Not sure how involved it would be to do this.

author maintainer
#7 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Andrii Nakryiko

On Thu, 2024-11-14 at 16:17 -0800, Andrii Nakryiko wrote:

[...]

Quoted 4 lines

This true/false logic seems generally useful not just for this use case, is there anything wrong with landing it? Seems pretty straightforward. I'd split it from the kfunc inlining and land independently.

I don't see anything wrong with it, but Alexei didn't like it. Agree with your comment about organizing flags as bit-fields.

#19 lore raw

Re: [RFC bpf-next 03/11] bpf: shared BPF/native kfuncs

In reply to Eduard Zingerman
Quoted 127 lines · Eduard Zingerman

This commit adds a notion of inlinable kfuncs, compiled both to native code and BPF. BPF-compiled version is embedded in kernel data section and is available to verifier. Verifier uses it to replace calls to such kfuncs with inlined function bodies.

Inlinable kfuncs are available only if CLANG is used for kernel compilation.

In the scope of this commit all inlining happens as last steps of do_check(), after verification is finished. Follow up commits would extend this mechanism to allow removal of some conditional branches inside inlined function bodies.

The commit consists of the following changes:
- main kernel makefile:
modified to compile a bootstrap version of the bpftool;
- kernel/bpf/Makefile:
- a new file inlinable_kfuncs.c is added;
- makefile is modified to compile this file as BPF elf, using the following steps:
- use clang with native target to produce LLVM bitcode;
- compile LLVM bitcode to BPF object file;
- resolve relocations inside BPF object file using bpftool as a linker;
Such arrangement allows including unmodified network related header files.
- verifier.c:
- generated BPF elf is included as a part of kernel data section;
- at kernel initialization phase:
- the elf is parsed and each function declared within it is recorded as an instance of 'inlinable_kfunc' structure;
- calls to extern functions within elf file (pointed to by relocation records) are replaced with kfunc call instructions;
- do_check() is modified to replace calls to kfuncs from inlinable kfunc table with function bodies:
- replacement happens after main verification pass, so the bodies of the kfuncs are not analyzed by verifier;
- if kfunc uses callee saved registers r6-r9 the spill/fill pairs are generated for these register before/after inlined kfunc body at call site;
- if kfunc uses r10 as a base pointer for load or store instructions, offsets of these instructions are adjusted;
- if kfunc uses r10 in other instructions, such r10 is considered as escaping and kfunc is not inlined.

---
 Makefile                      |  22 +-
 kernel/bpf/Makefile           |  24 +-
 kernel/bpf/inlinable_kfuncs.c |   1 +
 kernel/bpf/verifier.c         | 652 +++++++++++++++++++++++++++++++++-
 4 files changed, 680 insertions(+), 19 deletions(-)
 create mode 100644 kernel/bpf/inlinable_kfuncs.c
Makefile +21 -1
index a9a7d9ffaa98..4ded57f4b0c2 100644
@@ -496,6 +496,7 @@ CLIPPY_DRIVER       = clippy-driver
 BINDGEN                = bindgen
 PAHOLE         = pahole
 RESOLVE_BTFIDS = $(objtree)/tools/bpf/resolve_btfids/resolve_btfids
+BPFTOOL                = $(objtree)/tools/bpf/bpftool/bootstrap/bpftool
 LEX            = flex
 YACC           = bison
 AWK            = awk
@@ -585,7 +586,7 @@ export RUSTC_BOOTSTRAP := 1
 export ARCH SRCARCH CONFIG_SHELL BASH HOSTCC KBUILD_HOSTCFLAGS CROSS_COMPILE LD CC HOSTPKG_CONFIG
 export RUSTC RUSTDOC RUSTFMT RUSTC_OR_CLIPPY_QUIET RUSTC_OR_CLIPPY BINDGEN
 export HOSTRUSTC KBUILD_HOSTRUSTFLAGS
-export CPP AR NM STRIP OBJCOPY OBJDUMP READELF PAHOLE RESOLVE_BTFIDS LEX YACC AWK INSTALLKERNEL
+export CPP AR NM STRIP OBJCOPY OBJDUMP READELF PAHOLE RESOLVE_BTFIDS BPFTOOL LEX YACC AWK INSTALLKERNEL
 export PERL PYTHON3 CHECK CHECKFLAGS MAKE UTS_MACHINE HOSTCXX
 export KGZIP KBZIP2 KLZOP LZMA LZ4 XZ ZSTD
 export KBUILD_HOSTCXXFLAGS KBUILD_HOSTLDFLAGS KBUILD_HOSTLDLIBS LDFLAGS_MODULE
@@ -1356,6 +1357,25 @@ ifneq ($(wildcard $(resolve_btfids_O)),)
        $(Q)$(MAKE) -sC $(srctree)/tools/bpf/resolve_btfids O=$(resolve_btfids_O) clean
 endif
 
+# TODO: cross compilation?
+# TODO: bootstrap! (to avoid vmlinux.h generation)
+PHONY += bpftool_bootstrap bpftool_clean
+bpftool_O = $(abspath $(objtree))/tools/bpf/bpftool
+
+ifdef CONFIG_BPF
+ifdef CONFIG_CC_IS_CLANG
+prepare: bpftool_bootstrap
+endif
+endif
+
+bpftool_bootstrap:
+       $(Q)$(MAKE) -sC $(srctree)/tools/bpf/bpftool O=$(bpftool_O) srctree=$(abspath $(srctree)) bootstrap
+
+bpftool_clean:
+ifneq ($(wildcard $(bpftool_O)),)
+       $(Q)$(MAKE) -sC $(srctree)/tools/bpf/bpftool O=$(bpftool_O) srctree=$(abspath $(srctree)) clean
+endif
+
 # Clear a bunch of variables before executing the submake
 ifeq ($(quiet),silent_)
 tools_silent=s
kernel/bpf/Makefile +9 -1
index 105328f0b9c0..3d7ee81c8e2e 100644
@@ -6,7 +6,7 @@ cflags-nogcse-$(CONFIG_X86)$(CONFIG_CC_IS_GCC) := -fno-gcse
 endif
 CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy)
 
-obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o
+obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o tnum.o log.o token.o
 obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
 obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o
@@ -53,3 +53,25 @@ obj-$(CONFIG_BPF_SYSCALL) += relo_core.o
 obj-$(CONFIG_BPF_SYSCALL) += btf_iter.o
 obj-$(CONFIG_BPF_SYSCALL) += btf_relocate.o
 obj-$(CONFIG_BPF_SYSCALL) += kmem_cache_iter.o
+obj-$(CONFIG_BPF_SYSCALL) += helpers.o inlinable_kfuncs.o
+
+ifdef CONFIG_CC_IS_CLANG
+
+LLC ?= $(LLVM_PREFIX)llc$(LLVM_SUFFIX)
+
+# -mfentry -pg is $(CC_FLAGS_FTRACE)
+# -fpatchable-function-entry=16,16 is $(PADDING_CFLAGS)

kernel/bpf/Makefile obj-$(CONFIG_BPF_SYSCALL) += relo_core.o · line 73

Quoted 10 lines
kernel/bpf/Makefile +10 -0
+CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(CC_FLAGS_FTRACE)
+CFLAGS_REMOVE_inlinable_kfuncs.bpf.bc.o += $(PADDING_CFLAGS)
+$(obj)/inlinable_kfuncs.bpf.bc.o: $(src)/inlinable_kfuncs.c
+       $(Q)$(CLANG) $(c_flags) -emit-llvm -c $< -o $@
+
+$(obj)/inlinable_kfuncs.bpf.o: $(obj)/inlinable_kfuncs.bpf.bc.o
+       $(Q)$(LLC) -mcpu=v3 --mtriple=bpf --filetype=obj $< -o $@
+
+$(obj)/inlinable_kfuncs.bpf.linked.o: $(obj)/inlinable_kfuncs.bpf.o
+       $(Q)$(BPFTOOL) gen object $@ $<

what's the point? Just to strip DWARF? strip -g then?

but honestly, why even bother embedding entire ELF? Get binary data from .text, separately record ELF symbols (to know function name, size, and where they start). Keep it simple and minimal.

Quoted 19 lines
kernel/bpf/Makefile +4 -0
+
+$(obj)/verifier.o: $(obj)/inlinable_kfuncs.bpf.linked.o
+
+endif
kernel/bpf/inlinable_kfuncs.c new file +1 -0
new file mode 100644
index 000000000000..7b7dc05fa1a4
@@ -0,0 +1 @@
+// SPDX-License-Identifier: GPL-2.0-only
kernel/bpf/verifier.c +0 -0
index 3bae0bbc1da9..fbf51147f319 100644
@@ -20509,6 +20509,622 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
        return 0;
 }
 

[...]

#8 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Eduard Zingerman
Quoted 5 lines · Eduard Zingerman

On Thu, 2024-11-14 at 16:17 -0800, Andrii Nakryiko wrote:

[...]

Quoted 7 lines
Quoted 4 lines

This true/false logic seems generally useful not just for this use case, is there anything wrong with landing it? Seems pretty straightforward. I'd split it from the kfunc inlining and land independently.

I don't see anything wrong with it, but Alexei didn't like it. Agree with your comment about organizing flags as bit-fields.

Well, I asked whether it makes a difference.
And looks like your numbers show that this optimization adds 101m to 116m ?

If so, it's worth doing. I still don't like two bool flags though.

author maintainer
#9 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

On Thu, 2024-11-14 at 16:27 -0800, Alexei Starovoitov wrote:

[...]

Quoted 2 lines

Well, I asked whether it makes a difference.
And looks like your numbers show that this optimization adds 101m to 116m ?

No, it does not make a difference for dynptr_slice:

Quoted 3 lines
Quoted 3 lines

- The patches #1,2 with opt_hard_wire_dead_code_branches() changes are not necessary for dynptr_slice kfunc inlining / branch removal. I will drop these patches and adjust test cases.

The 101m -> 116m is for inlining w/o known branch removal -> inlining with branch removal. (With 76m being no inlining at all).

Quoted 1 line

If so, it's worth doing. I still don't like two bool flags though.

The peaces of information to encode here are:
- whether the branch is always predicted;
- if so, which branch.

I don't think this could be narrowed down to a single bit.

#10 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

Quoted 9 lines · Eduard Zingerman

On Thu, 2024-11-14 at 16:27 -0800, Alexei Starovoitov wrote:

[...]

Quoted 2 lines

Well, I asked whether it makes a difference.
And looks like your numbers show that this optimization adds 101m to 116m ?

No, it does not make a difference for dynptr_slice:

Then let's not do it. If there is no observable performance difference there is no need to do it just to make selftests shorter.

Quoted 6 lines
Quoted 3 lines
Quoted 3 lines

- The patches #1,2 with opt_hard_wire_dead_code_branches() changes are not necessary for dynptr_slice kfunc inlining / branch removal. I will drop these patches and adjust test cases.

The 101m -> 116m is for inlining w/o known branch removal -> inlining with branch removal. (With 76m being no inlining at all).

Not following. Which patch # does branch removal then?

author maintainer
#11 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

On Thu, 2024-11-14 at 16:38 -0800, Alexei Starovoitov wrote:

[...]

Quoted 4 lines
Quoted 2 lines

The 101m -> 116m is for inlining w/o known branch removal -> inlining with branch removal. (With 76m being no inlining at all).

Not following. Which patch # does branch removal then?

- "bpf: shared BPF/native kfuncs" (patch #3)
Build system integration and kfuncs inlining after verification.

- "bpf: instantiate inlinable kfuncs before verification" (patch #7) Adds a pass that clones inlinable kfunc bodies as hidden subprograms, one subprogram per callsite.

#3 does inlining, but does not remove any branches.
#7 moves where inlining is done which allows to remove branches.

Performance numbers for the simple test:
- #3 alone : 76m -> 101m
- #3 + #7 : 76m -> 116m

author maintainer
#5 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

In reply to Andrii Nakryiko

On Thu, 2024-11-14 at 16:19 -0800, Andrii Nakryiko wrote:

[...]

Quoted 11 lines

I was also always hoping that we'll eventually optimize the following pattern:

r1 = *(global var)
if r1 == 1 /* always 1 or 0 */
goto +...
...

This is extremely common with .rodata global variables, and while the branches are dead code eliminated, memory reads are not. Not sure how involved it would be to do this.

Could you please elaborate a bit.
For a simple test like below compiler replaces 'flag' with 1, so no action is needed from verifier:

    const int flag = 1;

    SEC("socket")
    __success
    __xlated("foobar")
    int rodata_test(void *ctx)
    {
    	if (flag)
    		return 1;
    	return 0;
    }
#6 lore raw

Re: [RFC bpf-next 01/11] bpf: use branch predictions in opt_hard_wire_dead_code_branches()

Quoted 17 lines · Eduard Zingerman

On Thu, 2024-11-14 at 16:19 -0800, Andrii Nakryiko wrote:

[...]

Quoted 11 lines

I was also always hoping that we'll eventually optimize the following pattern:

r1 = *(global var)
if r1 == 1 /* always 1 or 0 */
goto +...
...

This is extremely common with .rodata global variables, and while the branches are dead code eliminated, memory reads are not. Not sure how involved it would be to do this.

Quoted 5 lines

Could you please elaborate a bit.
For a simple test like below compiler replaces 'flag' with 1, so no action is needed from verifier:

    const int flag = 1;

now change this to actual .rodata global variable"

const volatile int flag = 1;

Quoted 11 lines
    SEC("socket")
    __success
    __xlated("foobar")
    int rodata_test(void *ctx)
    {
        if (flag)
                return 1;
        return 0;
    }