Skip to contentSkip to conversation

Verify global subprogs lazily

PATCH Applied Andrii Nakryiko 2 participants 5 messages Nov 24, 2023

Subsystems (4)
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

v2 cover Verify global subprogs lazily

See patch #2 for justification. In few words, current eager verification of global func prevents BPF CO-RE approaches to be applied to global functions.

Patch #1 is just a nicety to emit global subprog names in verifier logs.

Patch #3 adds selftests validating new lazy semantics.

v1->v2:
- rebases on latest bpf-next resolving conflicts with bpf_loop fixes;
- added acks from Eduard and Daniel.

Andrii Nakryiko (3):
bpf: emit global subprog name in verifier logs
bpf: validate global subprogs lazily selftests/bpf: add lazy global subprog validation tests

 include/linux/bpf.h                           |  2 +
 kernel/bpf/verifier.c                         | 83 +++++++++++++----
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../selftests/bpf/progs/test_global_func12.c  |  4 +-
 .../bpf/progs/verifier_global_subprogs.c      | 92 +++++++++++++++++++
 .../bpf/progs/verifier_subprog_precision.c    |  4 +-
 6 files changed, 166 insertions(+), 21 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_global_subprogs.c
Signature · 1 line
2.34.1
author maintainer
#1 lore raw

PATCH v2 1/3 bpf: emit global subprog name in verifier logs

We have the name, instead of emitting just func#N to identify global subprog, augment verifier log messages with actual function name to make it more user-friendly.

---
 kernel/bpf/verifier.c | 35 ++++++++++++++++++++++++-----------
 1 file changed, 24 insertions(+), 11 deletions(-)
kernel/bpf/verifier.c +24 -11
index 405da1f9e724..a2939ebf2638 100644
@@ -339,6 +339,11 @@ struct bpf_kfunc_call_arg_meta {
 
 struct btf *btf_vmlinux;
 
+static const char *btf_type_name(const struct btf *btf, u32 id)
+{
+	return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off);
+}
+
 static DEFINE_MUTEX(bpf_verifier_lock);
 static DEFINE_MUTEX(bpf_percpu_ma_lock);
 
@@ -418,6 +423,17 @@ static bool subprog_is_global(const struct bpf_verifier_env *env, int subprog)
 	return aux && aux[subprog].linkage == BTF_FUNC_GLOBAL;
 }
 
+static const char *subprog_name(const struct bpf_verifier_env *env, int subprog)
+{
+	struct bpf_func_info *info;
+
+	if (!env->prog->aux->func_info)
+		return "";
+
+	info = &env->prog->aux->func_info[subprog];
+	return btf_type_name(env->prog->aux->btf, info->type_id);
+}
+
 static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg)
 {
 	return btf_record_has_field(reg_btf_record(reg), BPF_SPIN_LOCK);
@@ -587,11 +603,6 @@ static int iter_get_spi(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
 	return stack_slot_obj_get_spi(env, reg, "iter", nr_slots);
 }
 
-static const char *btf_type_name(const struct btf *btf, u32 id)
-{
-	return btf_name_by_offset(btf, btf_type_by_id(btf, id)->name_off);
-}
-
 static enum bpf_dynptr_type arg_to_dynptr_type(enum bpf_arg_type arg_type)
 {
 	switch (arg_type & DYNPTR_TYPE_FLAG_MASK) {
@@ -9269,13 +9280,16 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	if (err == -EFAULT)
 		return err;
 	if (subprog_is_global(env, subprog)) {
+		const char *sub_name = subprog_name(env, subprog);
+
 		if (err) {
-			verbose(env, "Caller passes invalid args into func#%d\n", subprog);
+			verbose(env, "Caller passes invalid args into func#%d ('%s')\n",
+				subprog, sub_name);
 			return err;
 		}
 
-		if (env->log.level & BPF_LOG_LEVEL)
-			verbose(env, "Func#%d is global and valid. Skipping.\n", subprog);
+		verbose(env, "Func#%d ('%s') is global and assumed valid.\n",
+			subprog, sub_name);
 		clear_caller_saved_regs(env, caller->regs);
 
 		/* All global functions return a 64-bit SCALAR_VALUE */
@@ -19893,9 +19907,8 @@ static int do_check_subprogs(struct bpf_verifier_env *env)
 		if (ret) {
 			return ret;
 		} else if (env->log.level & BPF_LOG_LEVEL) {
-			verbose(env,
-				"Func#%d is safe for any args that match its prototype\n",
-				i);
+			verbose(env, "Func#%d ('%s') is safe for any args that match its prototype\n",
+				i, subprog_name(env, i));
 		}
 	}
 	return 0;
Signature · 1 line
2.34.1
author maintainer
#2 lore raw

PATCH v2 2/3 bpf: validate global subprogs lazily

In reply to Andrii Nakryiko

Slightly change BPF verifier logic around eagerness and order of global subprog validation. Instead of going over every global subprog eagerly and validating it before main (entry) BPF program is verified, turn it around. Validate main program first, mark subprogs that were called from main program for later verification, but otherwise assume it is valid. Afterwards, go over marked global subprogs and validate those, potentially marking some more global functions as being called. Continue this process until all (transitively) callable global subprogs are validated. It's a BFS traversal at its heart and will always converge.

This is an important change because it allows to feature-gate some subprograms that might not be verifiable on some older kernel, depending on supported set of features.

E.g., at some point, global functions were allowed to accept a pointer to memory, which size is identified by user-provided type. Unfortunately, older kernels don't support this feature. With BPF CO-RE approach, the natural way would be to still compile BPF object file once and guard calls to this global subprog with some CO-RE check or using .rodata variables. That's what people do to guard usage of new helpers or kfuncs, and any other new BPF-side feature that might be missing on old kernels.

That's currently impossible to do with global subprogs, unfortunately, because they are eagerly and unconditionally validated. This patch set aims to change this, so that in the future when global funcs gain new features, those can be guarded using BPF CO-RE techniques in the same fashion as any other new kernel feature.

Two selftests had to be adjusted in sync with these changes.

test_global_func12 relied on eager global subprog validation failing before main program failure is detected (unknown return value). Fix by making sure that main program is always valid.

verifier_subprog_precision's parent_stack_slot_precise subtest relied on verifier checkpointing heuristic to do a checkpoint at instruction #5, but that's no longer true because we don't have enough jumps validated before reaching insn #5 due to global subprogs being validated later.

Other than that, no changes, as one would expect.

---
 include/linux/bpf.h                           |  2 +
 kernel/bpf/verifier.c                         | 48 ++++++++++++++++---
 .../selftests/bpf/progs/test_global_func12.c  |  4 +-
 .../bpf/progs/verifier_subprog_precision.c    |  4 +-
 4 files changed, 48 insertions(+), 10 deletions(-)
include/linux/bpf.h +2 -0
index 258ba232e302..eb447b0a9423 100644
@@ -1347,6 +1347,8 @@ static inline bool bpf_prog_has_trampoline(const struct bpf_prog *prog)
 struct bpf_func_info_aux {
 	u16 linkage;
 	bool unreliable;
+	bool called : 1;
+	bool verified : 1;
 };
 
 enum bpf_jit_poke_reason {
kernel/bpf/verifier.c +42 -6

91 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_global_func12.c +3 -1
index 7f159d83c6f6..6e03d42519a6 100644
@@ -19,5 +19,7 @@ int global_func12(struct __sk_buff *skb)
 {
 	const struct S s = {.x = skb->len };
 
-	return foo(&s);
+	foo(&s);
+
+	return 1;
 }
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 -3
index f61d623b1ce8..b5efcaeaa1ae 100644
@@ -370,12 +370,10 @@ __naked int parent_stack_slot_precise(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("9: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 9 first_idx 6")
+__msg("mark_precise: frame0: last_idx 9 first_idx 0")
 __msg("mark_precise: frame0: regs=r6 stack= before 8: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 7: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 6: (79) r6 = *(u64 *)(r10 -8)")
-__msg("mark_precise: frame0: parent state regs= stack=-8:")
-__msg("mark_precise: frame0: last_idx 5 first_idx 0")
 __msg("mark_precise: frame0: regs= stack=-8 before 5: (85) call pc+6")
 __msg("mark_precise: frame0: regs= stack=-8 before 4: (b7) r1 = 0")
 __msg("mark_precise: frame0: regs= stack=-8 before 3: (7b) *(u64 *)(r10 -8) = r6")
Signature · 1 line
2.34.1
author maintainer
#3 lore raw

PATCH v2 3/3 selftests/bpf: add lazy global subprog validation tests

In reply to Andrii Nakryiko

Add a few test that validate BPF verifier's lazy approach to validating global subprogs.

We check that global subprogs that are called transitively through another global subprog is validated.

We also check that invalid global subprog is not validated, if it's not called from the main program.

And we also check that main program is always validated first, before any of the subprogs.

---
 .../selftests/bpf/prog_tests/verifier.c       |  2 +
 .../bpf/progs/verifier_global_subprogs.c      | 92 +++++++++++++++++++
 2 files changed, 94 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_global_subprogs.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 5cfa7a6316b6..8d746642cbd7 100644
@@ -25,6 +25,7 @@
 #include "verifier_direct_stack_access_wraparound.skel.h"
 #include "verifier_div0.skel.h"
 #include "verifier_div_overflow.skel.h"
+#include "verifier_global_subprogs.skel.h"
 #include "verifier_gotol.skel.h"
 #include "verifier_helper_access_var_len.skel.h"
 #include "verifier_helper_packet_access.skel.h"
@@ -134,6 +135,7 @@ void test_verifier_direct_packet_access(void) { RUN(verifier_direct_packet_acces
 void test_verifier_direct_stack_access_wraparound(void) { RUN(verifier_direct_stack_access_wraparound); }
 void test_verifier_div0(void)                 { RUN(verifier_div0); }
 void test_verifier_div_overflow(void)         { RUN(verifier_div_overflow); }
+void test_verifier_global_subprogs(void)      { RUN(verifier_global_subprogs); }
 void test_verifier_gotol(void)                { RUN(verifier_gotol); }
 void test_verifier_helper_access_var_len(void) { RUN(verifier_helper_access_var_len); }
 void test_verifier_helper_packet_access(void) { RUN(verifier_helper_packet_access); }
tools/testing/selftests/bpf/progs/verifier_global_subprogs.c new file +92 -0

92 lines not on this page · raw message

Signature · 1 line
2.34.1
#4 lore raw
In reply to Andrii Nakryiko
This series was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Daniel Borkmann <[email protected]>:

Quoted 8 lines · On Thu, 23 Nov 2023 19:59:34 -0800 you wrote:

See patch #2 for justification. In few words, current eager verification of global func prevents BPF CO-RE approaches to be applied to global functions.

Patch #1 is just a nicety to emit global subprog names in verifier logs.

Patch #3 adds selftests validating new lazy semantics.

[...]

Here is the summary with links:
- [v2,bpf-next,1/3] bpf: emit global subprog name in verifier logs

    https://git.kernel.org/bpf/bpf-next/c/491dd8edecbc
  - [v2,bpf-next,2/3] bpf: validate global subprogs lazily
    https://git.kernel.org/bpf/bpf-next/c/2afae08c9dcb
  - [v2,bpf-next,3/3] selftests/bpf: add lazy global subprog validation tests
    https://git.kernel.org/bpf/bpf-next/c/e8a339b5235e

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html