Skip to contentSkip to conversation

Exceptions - 1/2

RFC PATCH In review Kumar Kartikeya Dwivedi 2 participants 30 messages Apr 5, 2023 – Apr 17, 2023

Subsystems (8)
Networking Kselftest BPF Scheduler +4 more subsystems
lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

cover Exceptions - 1/2

This series implements the bare minimum support for basic BPF exceptions. This is a feature to allow programs to simply throw a valueless exception within a BPF program to abort its execution. Automatic cleanup of held resources and generation of landing pads to unwind program state will be done in the part 2 set.

The exception state is part of the the current task's task_struct's exception_thrown array, which is a set of 4 boolean variables, representing the exception state for each kernel context (Task, SoftIRQ, HardIRQ, NMI). This allows a program interrupting the execution of another program to not corrupt its exception state when throwing.

During program nesting, i.e. a program invoked in the same context while another program is active, an exception can never be in the 'thrown' state, as long as it clears its own exception state when exiting and returning to the kernel, the caller program will be fine.

Hence, the conditions are that a program receives unset exception state on entry, and preserves the unset exception state on exit. Only BPF subprogs avoid resetting exception state on exit, so that they can propagate the modified exception state to their caller. This can be another caller subprog, the caller main prog, or the kernel.

BPF helpers executing callbacks in the kernel are modified to catch and exit early when they detect a thrown exception from the callback. The program will then catch this exception and unwind.

BPF helpers and kfuncs may also throw BPF exceptions, they simply declare their intent to throw using annotations (e.g. predicate function with list of throwing helpers, KF_THROW for kfuncs, etc). The program will automatically be instrumented to detect a thrown exception and unwind the stack.

The following two kfuncs are introduced:

// Throw a BPF exception, terminating execution of the program. void bpf_throw(void);

// Set an exception handler which is invoked after the unwinding of the // stack is finished. The return value of the handler is the value // returned when an exception is thrown, otherwise by default it is 0. void bpf_set_exception_handler(int (*handler)(void));

Dedicated exception state in task_struct vs bpf_run_ctx was chosen primarily for the following reasons:
- Synchronous callbacks semantically execute within programs and affect their state. Hence, exceptions thrown by them should be propagated when invoked from helpers and kfuncs.
- For async callbacks that terminate execution safely using bpf_throw, this would require having a bpf_run_ctx by default (with same semantics as the current solution) or setup by the invoking context for each cb invocation (which breaks cb == func pointer semantics assumed currently within the kernel).
- Avoid setting up bpf_run_ctx for program types (esp. XDP) that don't need it, and no changes are needed for programs that don't use exceptions. Whatever minor overhead there is, is only paid for when they are used.

Restrictions can be imposed on the program to revisit the bpf_run_ctx solution (like forbidding callbacks from using bpf_throw). However, genericity of use of bpf_throw in all possible cases is given preference (so that bpf_assert which is the primary consumer isn't surprising to use when it isn't supported in certain contexts).

The overhead of calling helpers to deal with exception state can be easily forgone by getting direct access to the current task pointer to touch exception state, or using a dedicated callee-saved register to hold it within the program (while relying on task_struct state across BPF-Kernel boundary).

Verification
------------

We rely on the main verifier pass to decide how to rewrite the BPF program to handle thrown exceptions.

The first step of verification in the main pass (do_check) is symbolic execution of the global subprograms. These subprograms are verified independently, and hence, they are not explored whenever there is a call to a global subprog.

We first do 'can_throw' marking for each global subprogram by following its execution, detecting any bpf_throw calls made in any of the paths explored by the verifier. This however does not have full visibility into the thrown exceptions, and only attains markings for exceptions it can see to be thrown by static subprogs, helpers, kfuncs, etc.

For instance:

GF1:
call GF2
exit
GF2:
call GF3
exit
GF3:
call bpf_throw

If all of these are explored in order, only GF3 receives the can_throw marking. To remedy this, we do another pass and follow BPF_PSEUDO_CALL edges to global subprogs in the call graph of global subprogs, and propagate the direct throws in some global subprogs to other global subprogs. Each caller then receives can_throw marking and is marked for rewrite later.

Now, all global functions are annotated correctly with the right can_throw markings, and any calls to them in the main subprog can also be marked for appropriate rewrites later. We now go through the main subprog, and since we have full visibility due to the verifier's path awareness into which paths may throw, we use this to selectively mark every such instruction which has throwing semantics (calls to throwing subprogs (global/static), calls to helper or kfuncs taking callbacks which throw), calls to kfuncs which throw, etc.

If a certain static subprog only throws when called from a certain point in the program, and does not throw in the other, we avoid marking its other callsite as throwing. However, this is unlike global subprogs, where we do not explore them, hence cannot make this distinction. This also means that two calls to the same static subprog may be rewritten differently, and thus may or may not handle the exception.

This becomes a problem if we allow extension programs to attach to such static subprogs. Usually, the use case is to replace global subprogs, and static subprogs are rejected right now. A test case is included to catch the case when things change and prompt appropriate checks in check_ext_prog (as all callsites are not prepared to handle exceptions),

Optimizations
-------------

Currently, exception handling code is generated inline. This was done to keep things simple for now, and since the generated code is typically constant for each type of call instruction.

Generation of dedicated landing pads to unwind program stack and moving it outline to a separate 'invented' subprog or end of subprog has been split into the future set, where the BPF runtime needs to release resources present on the program stack.

Another minor annoyance are the calls to bpf_get_exception to fetch exception state. This call needs to be made unconditionally regardless of whether an exception was thrown or not. It would be much more convenient to have a hidden callee-saved BPF register which holds the exception state, but I'm not using R12 for that (e.g. on x86) hurts some other use case.

Then, checking exceptions thrown within the program becomes much more lightweight, and the use bpf_get_exception is only limited to exceptions thrown by helpers and kfuncs (around their call, and then the exception register can propagate it to callers).

Callbacks invoked by the kernel synchronously will then set both exception register and task-local exception state.

Known issues
------------

* Since bpf_throw is marked noreturn, the compiler sometimes may determine that a function always throws and emit the final instruction as a call to it without emitting an exit in the caller. This leads to an error where the verifier complains about final instruction not being a jump, exit, or bpf_throw call (which gets treated as an exit). This is unlikely to occur as bpf_throw wouldn't be used whenever the condition is already known at compile time, but I could see it when testing with always throwing subprogs and calling into them.

* Just asm volatile ("call bpf_throw" :::) does not emit DATASEC .ksyms for bpf_throw, there needs to be explicit call in C for clang to emit the DATASEC info in BTF, leading to errors during compilation.

Kumar Kartikeya Dwivedi (9):
bpf: Fix kfunc callback handling
bpf: Refactor and generalize optimize_bpf_loop
bpf: Implement bpf_throw kfunc
bpf: Handle throwing BPF callbacks in helpers and kfuncs
bpf: Add pass to fixup global function throw information
bpf: Add KF_THROW annotation for kfuncs
bpf: Introduce bpf_set_exception_callback kfunc
bpf: Introduce BPF assertion macros selftests/bpf: Add tests for BPF exceptions

 include/linux/bpf.h                           |   9 +-
 include/linux/bpf_verifier.h                  |  20 +-
 include/linux/btf.h                           |   1 +
 include/linux/sched.h                         |   1 +
 kernel/bpf/arraymap.c                         |  13 +-
 kernel/bpf/bpf_iter.c                         |   2 +
 kernel/bpf/hashtab.c                          |   4 +-
 kernel/bpf/helpers.c                          |  46 +-
 kernel/bpf/ringbuf.c                          |   4 +
 kernel/bpf/syscall.c                          |  10 +
 kernel/bpf/task_iter.c                        |   2 +
 kernel/bpf/trampoline.c                       |   4 +-
 kernel/bpf/verifier.c                         | 692 +++++++++++++++++-
 net/bpf/test_run.c                            |  12 +
 .../testing/selftests/bpf/bpf_experimental.h  |  37 +
 .../selftests/bpf/prog_tests/exceptions.c     | 240 ++++++
 .../testing/selftests/bpf/progs/exceptions.c  | 218 ++++++
 .../selftests/bpf/progs/exceptions_ext.c      |  42 ++
 .../selftests/bpf/progs/exceptions_fail.c     | 267 +++++++
 19 files changed, 1576 insertions(+), 48 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/exceptions.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_ext.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_fail.c

base-commit: d099f594ad5650e8d8232b5f31f5f90104e65def

Signature · 1 line
2.40.0
author maintainer
#1 lore raw

RFC PATCH 1/9 bpf: Fix kfunc callback handling

The kfunc code to handle KF_ARG_PTR_TO_CALLBACK does not check the reg type before using reg->subprogno. This can accidently permit invalid pointers from being passed into callback helpers (e.g. silently from different paths). We need to reject any other type except PTR_TO_FUNC.

Fixes 5d92ddc3de1b ("bpf: Add callback validation to kfunc verifier logic")
---
 kernel/bpf/verifier.c | 4 ++++
 1 file changed, 4 insertions(+)
kernel/bpf/verifier.c +4 -0
index 56f569811f70..693aeddc9fe2 100644
@@ -10562,6 +10562,10 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 			break;
 		}
 		case KF_ARG_PTR_TO_CALLBACK:
+			if (reg->type != PTR_TO_FUNC) {
+				verbose(env, "arg%d expected pointer to func\n", i);
+				return -EINVAL;
+			}
 			meta->subprogno = reg->subprogno;
 			break;
 		}
Signature · 1 line
2.40.0
author maintainer
#2 lore raw

RFC PATCH 2/9 bpf: Refactor and generalize optimize_bpf_loop

In reply to Kumar Kartikeya Dwivedi

The optimize_bpf_loop pass is currently used to transform calls to the bpf_loop helper function into an inlined instruction sequence which elides the helper call and does the looping directly and emits the call to the loop callback.

The future patches for exception propagation for BPF programs will require similar rewriting which needs access to extra stack space to spill registers which may be clobbered in the emitted sequence.

We wish to reuse the logic of updating subprog stack depth by tracking the extra stack depth needed across all rewrites in a subprog in subseqeunt patches. Hence, refactor the code to make it amenable for plugging extra rewrite passes over other instructions. Note that the stack_depth_extra is now set by a max of existing and required extra stack depth. This allows rewrites to reuse the extra stack depth among themselves, by figuring the maximum depth needed for a subprog.

Note that we only do one rewrite in one loop iteration, and thus new_prog is set only once. This can be used to pull out shared updates of delta, env->prog, etc. into common code that occurs after all cases of possible rewrites are examined, and if application, performed.

---
 kernel/bpf/verifier.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
kernel/bpf/verifier.c +17 -11
index 693aeddc9fe2..8ecd5df73b07 100644
@@ -18024,23 +18024,26 @@ static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
 	return new_prog;
 }
 
-static bool is_bpf_loop_call(struct bpf_insn *insn)
+static bool is_inlineable_bpf_loop_call(struct bpf_insn *insn,
+					struct bpf_insn_aux_data *aux)
 {
 	return insn->code == (BPF_JMP | BPF_CALL) &&
 		insn->src_reg == 0 &&
-		insn->imm == BPF_FUNC_loop;
+		insn->imm == BPF_FUNC_loop &&
+		aux->loop_inline_state.fit_for_inline;
 }
 
 /* For all sub-programs in the program (including main) check
- * insn_aux_data to see if there are bpf_loop calls that require
- * inlining. If such calls are found the calls are replaced with a
+ * insn_aux_data to see if there are any instructions that need to be
+ * transformed into an instruction sequence. E.g. bpf_loop calls that
+ * require inlining. If such calls are found the calls are replaced with a
  * sequence of instructions produced by `inline_bpf_loop` function and
  * subprog stack_depth is increased by the size of 3 registers.
  * This stack space is used to spill values of the R6, R7, R8.  These
  * registers are used to store the loop bound, counter and context
  * variables.
  */
-static int optimize_bpf_loop(struct bpf_verifier_env *env)
+static int do_misc_rewrites(struct bpf_verifier_env *env)
 {
 	struct bpf_subprog_info *subprogs = env->subprog_info;
 	int i, cur_subprog = 0, cnt, delta = 0;
@@ -18051,13 +18054,14 @@ static int optimize_bpf_loop(struct bpf_verifier_env *env)
 	u16 stack_depth_extra = 0;
 
 	for (i = 0; i < insn_cnt; i++, insn++) {
-		struct bpf_loop_inline_state *inline_state =
-			&env->insn_aux_data[i + delta].loop_inline_state;
+		struct bpf_insn_aux_data *insn_aux = &env->insn_aux_data[i + delta];
+		struct bpf_prog *new_prog = NULL;
 
-		if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) {
-			struct bpf_prog *new_prog;
+		if (is_inlineable_bpf_loop_call(insn, insn_aux)) {
+			struct bpf_loop_inline_state *inline_state = &insn_aux->loop_inline_state;
 
-			stack_depth_extra = BPF_REG_SIZE * 3 + stack_depth_roundup;
+			stack_depth_extra = max_t(u16, stack_depth_extra,
+						  BPF_REG_SIZE * 3 + stack_depth_roundup);
 			new_prog = inline_bpf_loop(env,
 						   i + delta,
 						   -(stack_depth + stack_depth_extra),
@@ -18065,7 +18069,9 @@ static int optimize_bpf_loop(struct bpf_verifier_env *env)
 						   &cnt);
 			if (!new_prog)
 				return -ENOMEM;
+		}
 
+		if (new_prog) {
 			delta     += cnt - 1;
 			env->prog  = new_prog;
 			insn       = new_prog->insnsi + i + delta;
@@ -18876,7 +18882,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr)
 
 	/* instruction rewrites happen after this point */
 	if (ret == 0)
-		ret = optimize_bpf_loop(env);
+		ret = do_misc_rewrites(env);
 
 	if (is_priv) {
 		if (ret == 0)
Signature · 1 line
2.40.0
author maintainer
#3 lore raw

RFC PATCH 3/9 bpf: Implement bpf_throw kfunc

In reply to Kumar Kartikeya Dwivedi

Introduce the support for exceptions in BPF runtime. The bpf_throw kfunc is the main helper to be used by programs to throw an exception. In the verifier domain, it will be processed as an immediate main exit for the program, ending exploration of that path.

This proves to be a powerful property: a program can perform a condition check and call bpf_throw for the case that will never occur at runtime, but it's still something it needs to prove to the verifier. The unwinding of the program stack and any resources will automatically be performed by the BPF runtime.

For now, we fail if we see lingering references, locks, etc., but a future patch will extend the current infrastructure to generate the cleanup code for those too.

Programs that do not use exceptions today have no change in their .text and performance, as all extra code generated to throw, propagate, unwind the stack, etc. only applies to programs that use this new facility.

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.
- The other vexing case is of recursion. If a program calls into another program (e.g. call into helper which invokes tracing program eventually), it may throw and clobber the current exception state. To avoid this, an invariant is maintained across the implementation:
Exception state is always cleared on entry and exit of the main BPF program.
This implies that if recursion occurs, the BPF program will clear the current exception state on entry and exit. However, callbacks do not do the same, because they are subprograms. The case for propagating exceptions of callbacks invoked by the kernel back to the BPF program is handled in the next commit. This is also the main reason to clear exception state on entry, asynchronous callbacks can clobber exception state even though we make sure it's always set to be 0 within the kernel.
Anyhow, the only other thing to be kept in mind is to never allow a BPF program to execute when the program is being unwinded. This implies that every function involved in this path must be notrace, which is the case for bpf_throw, bpf_get_exception and bpf_reset_exception.
- Rewrites happen for bpf_throw and call instructions to subprogs. The instructions which are executed in the main frame of the main program (thus, not global functions and extension programs, which end up executing in frame > 0) need to be rewritten differently. This is tracked using BPF_THROW_OUTER vs BPF_THROW_INNER. If not done, a recursing tracing program may set exception state which the main program is instrumented to handle eventually, causing it to unwind when it shouldn't.
- Callsite specific marking is done. It is possible to reduce the instrumentation needed if we were marking callsites. Only all calls to global subprogs would need to be rewritten to handle thrown exceptions, otherwise for each callsite to static subprogs, the verifier's path awareness allows us to skip the handling if all passible paths taken using that callsite never throw. This propagates into all callers and prog may end up having throws_exception as false. Typically this reduces the amount of instrumentation when subprogs throwing are deeply nested and only throw under specific conditions.
- BPF_PROG_TYPE_EXT is special in that it replaces global functions in other BPF programs. A check is added after we know exception specification of a prog (throws_exception) to ensure we don't attach throwing extension to a program not instrumented to handle them, or to main subprog which has BPF_THROW_OUTER handling compared to extension prog's BPF_THROW_INNER handling.

---
 include/linux/bpf.h                           |   9 +-
 include/linux/bpf_verifier.h                  |  13 +
 include/linux/sched.h                         |   1 +
 kernel/bpf/arraymap.c                         |   9 +-
 kernel/bpf/helpers.c                          |  22 ++
 kernel/bpf/syscall.c                          |  10 +
 kernel/bpf/trampoline.c                       |   4 +-
 kernel/bpf/verifier.c                         | 241 ++++++++++++++++--
 .../testing/selftests/bpf/bpf_experimental.h  |   9 +
 9 files changed, 299 insertions(+), 19 deletions(-)
include/linux/bpf.h +8 -1
index 002a811b6b90..04b81f5fe809 100644
@@ -1287,6 +1287,7 @@ static inline bool bpf_prog_has_trampoline(const struct bpf_prog *prog)
 struct bpf_func_info_aux {
 	u16 linkage;
 	bool unreliable;
+	bool throws_exception;
 };
 
 enum bpf_jit_poke_reason {
@@ -1430,7 +1431,8 @@ struct bpf_prog {
 				enforce_expected_attach_type:1, /* Enforce expected_attach_type checking at attach time */
 				call_get_stack:1, /* Do we call bpf_get_stack() or bpf_get_stackid() */
 				call_get_func_ip:1, /* Do we call get_func_ip() */
-				tstamp_type_access:1; /* Accessed __sk_buff->tstamp_type */
+				tstamp_type_access:1, /* Accessed __sk_buff->tstamp_type */
+				throws_exception:1; /* Does this program throw exceptions? */
 	enum bpf_prog_type	type;		/* Type of BPF program */
 	enum bpf_attach_type	expected_attach_type; /* For some prog types */
 	u32			len;		/* Number of filter blocks */
@@ -3035,4 +3037,9 @@ static inline gfp_t bpf_memcg_flags(gfp_t flags)
 	return flags;
 }
 
+/* BPF Exception helpers */
+void bpf_reset_exception(void);
+u64 bpf_get_exception(void);
+void bpf_throw(void);
+
 #endif /* _LINUX_BPF_H */
include/linux/bpf_verifier.h +13 -0
index 81d525d057c7..bc067223d3ee 100644
@@ -430,6 +430,17 @@ struct bpf_loop_inline_state {
 	u32 callback_subprogno; /* valid when fit_for_inline is true */
 };
 
+enum {
+	BPF_THROW_NONE,
+	BPF_THROW_OUTER,
+	BPF_THROW_INNER,
+};
+
+struct bpf_throw_state {
+	int type;
+	bool check_helper_ret_code;
+};
+
 /* Possible states for alu_state member. */
 #define BPF_ALU_SANITIZE_SRC		(1U << 0)
 #define BPF_ALU_SANITIZE_DST		(1U << 1)
@@ -464,6 +475,7 @@ struct bpf_insn_aux_data {
 		 */
 		struct bpf_loop_inline_state loop_inline_state;
 	};
+	struct bpf_throw_state throw_state;
 	u64 obj_new_size; /* remember the size of type passed to bpf_obj_new to rewrite R1 */
 	struct btf_struct_meta *kptr_struct_meta;
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
@@ -537,6 +549,7 @@ struct bpf_subprog_info {
 	bool tail_call_reachable;
 	bool has_ld_abs;
 	bool is_async_cb;
+	bool can_throw;
 };
 
 /* single container for all structs
include/linux/sched.h +1 -0
index b11b4517760f..a568245b59a2 100644
@@ -1480,6 +1480,7 @@ struct task_struct {
 	struct bpf_local_storage __rcu	*bpf_storage;
 	/* Used for BPF run context */
 	struct bpf_run_ctx		*bpf_ctx;
+	bool				bpf_exception_thrown[4];
 #endif
 
 #ifdef CONFIG_GCC_PLUGIN_STACKLEAK
kernel/bpf/arraymap.c +8 -1
index 2058e89b5ddd..de0eadf8706f 100644
@@ -905,7 +905,14 @@ static void *prog_fd_array_get_ptr(struct bpf_map *map,
 	if (IS_ERR(prog))
 		return prog;
 
-	if (!bpf_prog_map_compatible(map, prog)) {
+	/* Programs which throw exceptions are not allowed to be tail call
+	 * targets. This is because it forces us to be conservative for each
+	 * bpf_tail_call invocation and assume it may throw, since we do not
+	 * know what the target program may do, thus causing us to propagate the
+	 * exception and mark calling prog as potentially throwing. Just be
+	 * restrictive for now and disallow this.
+	 */
+	if (prog->throws_exception || !bpf_prog_map_compatible(map, prog)) {
 		bpf_prog_put(prog);
 		return ERR_PTR(-EINVAL);
 	}
kernel/bpf/helpers.c +22 -0
index 6be16db9f188..89e70907257c 100644
@@ -1879,6 +1879,20 @@ void bpf_rb_root_free(const struct btf_field *field, void *rb_root,
 	}
 }
 
+notrace void bpf_reset_exception(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = false;
+}
+
+notrace u64 bpf_get_exception(void)
+{
+	int i = interrupt_context_level();
+
+	return current->bpf_exception_thrown[i];
+}
+
 __diag_push();
 __diag_ignore_all("-Wmissing-prototypes",
 		  "Global functions as their definitions will be in vmlinux BTF");
@@ -2295,6 +2309,13 @@ __bpf_kfunc void bpf_rcu_read_unlock(void)
 	rcu_read_unlock();
 }
 
+__bpf_kfunc notrace void bpf_throw(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = true;
+}
+
 __diag_pop();
 
 BTF_SET8_START(generic_btf_ids)
@@ -2321,6 +2342,7 @@ BTF_ID_FLAGS(func, bpf_cgroup_ancestor, KF_ACQUIRE | KF_RCU | KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_cgroup_from_id, KF_ACQUIRE | KF_RET_NULL)
 #endif
 BTF_ID_FLAGS(func, bpf_task_from_pid, KF_ACQUIRE | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_throw)
 BTF_SET8_END(generic_btf_ids)
 
 static const struct btf_kfunc_id_set generic_kfunc_set = {
kernel/bpf/syscall.c +10 -0
index e18ac7fdc210..f82e7a174d6a 100644
@@ -3144,6 +3144,16 @@ static int bpf_tracing_prog_attach(struct bpf_prog *prog,
 		tgt_prog = prog->aux->dst_prog;
 	}
 
+	/* Don't allow tracing programs to attach to fexit and clear exception
+	 * state when we are unwinding the program.
+	 */
+	if (prog->type == BPF_PROG_TYPE_TRACING &&
+	    (prog->expected_attach_type == BPF_TRACE_FEXIT) &&
+	    tgt_prog && tgt_prog->throws_exception && prog->throws_exception) {
+		err = -EINVAL;
+		goto out_unlock;
+	}
+
 	err = bpf_link_prime(&link->link.link, &link_primer);
 	if (err)
 		goto out_unlock;
kernel/bpf/trampoline.c +3 -1
index f61d5138b12b..e9f9dd52f16c 100644
@@ -514,7 +514,9 @@ static int __bpf_trampoline_link_prog(struct bpf_tramp_link *link, struct bpf_tr
 	kind = bpf_attach_type_to_tramp(link->link.prog);
 	if (tr->extension_prog)
 		/* cannot attach fentry/fexit if extension prog is attached.
-		 * cannot overwrite extension prog either.
+		 * cannot overwrite extension prog either. We rely on this to
+		 * not check extension prog's exception specification (since
+		 * throwing extension may not replace non-throwing).
 		 */
 		return -EBUSY;
 
kernel/bpf/verifier.c +225 -16

416 lines not on this page · raw message

tools/testing/selftests/bpf/bpf_experimental.h +9 -0
index dbd2c729781a..d5de9251e775 100644
@@ -89,4 +89,13 @@ extern void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
  */
 extern struct bpf_rb_node *bpf_rbtree_first(struct bpf_rb_root *root) __ksym;
 
+/* Description
+ *  Throw an exception, terminating the execution of the program immediately.
+ *  The eBPF runtime unwinds the stack automatically and exits the program with
+ *  the default return value of 0.
+ * Returns
+ *  This function never returns.
+ */
+extern void bpf_throw(void) __attribute__((noreturn)) __ksym;
+
 #endif
Signature · 1 line
2.40.0
#4 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Quoted 19 lines

- The other vexing case is of recursion. If a program calls into another program (e.g. call into helper which invokes tracing program eventually), it may throw and clobber the current exception state. To avoid this, an invariant is maintained across the implementation:
Exception state is always cleared on entry and exit of the main BPF program.
This implies that if recursion occurs, the BPF program will clear the current exception state on entry and exit. However, callbacks do not do the same, because they are subprograms. The case for propagating exceptions of callbacks invoked by the kernel back to the BPF program is handled in the next commit. This is also the main reason to clear exception state on entry, asynchronous callbacks can clobber exception state even though we make sure it's always set to be 0 within the kernel.
Anyhow, the only other thing to be kept in mind is to never allow a BPF program to execute when the program is being unwinded. This implies that every function involved in this path must be notrace, which is the case for bpf_throw, bpf_get_exception and bpf_reset_exception.

...

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 17547

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+			struct bpf_insn entry_insns[] = {
+				BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+				BPF_EMIT_CALL(bpf_reset_exception),
+				BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+				insn[i],
+			};

Is not correct in global bpf progs that take more than 1 argument.

How about using a scratch space in prog->aux->exception[] instead of current task?

kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 1894

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+notrace u64 bpf_get_exception(void)
+{
+	int i = interrupt_context_level();
+
+	return current->bpf_exception_thrown[i];
+}

this is too slow to be acceptable.
it needs to be single load plus branch.
with prog->aux->exception approach we can achieve that. Instead of inserting a call to bpf_get_exception() we can do load+cmp. We probably should pass prog->aux into exception callback, so it can know where throw came from.

Quoted 5 lines

- Rewrites happen for bpf_throw and call instructions to subprogs. The instructions which are executed in the main frame of the main program (thus, not global functions and extension programs, which end up executing in frame > 0) need to be rewritten differently. This is tracked using BPF_THROW_OUTER vs BPF_THROW_INNER. If not done, a

how about BPF_THROW_OUTER vs BPF_THROW_ANY_INNER ? would it be more precise ?

kernel/bpf/helpers.c __bpf_kfunc void bpf_rcu_read_unlock(void) · line 2317

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+__bpf_kfunc notrace void bpf_throw(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = true;
+}

I think this needs to take u64 or couple u64 args and store them in the scratch area.
bpf_assert* macros also need a way for bpf prog to specify the reason for the assertion.
Otherwise there won't be any way to debug what happened.

author maintainer
#5 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 9 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Can you elaborate? If a sleepable program blocks, that means the task is scheduled out, so the next program will use the other task's task_struct. Same for preemption for normal progs (under RT or not).

Is there something else that I'm missing?

Quoted 22 lines
Quoted 19 lines

- The other vexing case is of recursion. If a program calls into another program (e.g. call into helper which invokes tracing program eventually), it may throw and clobber the current exception state. To avoid this, an invariant is maintained across the implementation:
Exception state is always cleared on entry and exit of the main BPF program.
This implies that if recursion occurs, the BPF program will clear the current exception state on entry and exit. However, callbacks do not do the same, because they are subprograms. The case for propagating exceptions of callbacks invoked by the kernel back to the BPF program is handled in the next commit. This is also the main reason to clear exception state on entry, asynchronous callbacks can clobber exception state even though we make sure it's always set to be 0 within the kernel.
Anyhow, the only other thing to be kept in mind is to never allow a BPF program to execute when the program is being unwinded. This implies that every function involved in this path must be notrace, which is the case for bpf_throw, bpf_get_exception and bpf_reset_exception.

...

Quoted 9 lines

kernel/bpf/verifier.c static int do_misc_fixups(struct bpf_verifier_env *env) · line 17547

Quoted 6 lines
kernel/bpf/verifier.c +6 -0
+			struct bpf_insn entry_insns[] = {
+				BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+				BPF_EMIT_CALL(bpf_reset_exception),
+				BPF_MOV64_REG(BPF_REG_1, BPF_REG_6),
+				insn[i],
+			};

Is not correct in global bpf progs that take more than 1 argument.

But this is not done for global subprogs, only for the main subprog, it only needs to be done when we enter the program from the kernel.

Quoted 2 lines

How about using a scratch space in prog->aux->exception[] instead of current task?

I actually had this thought. It's even better because we can hardcode the address of the exception state right in the program (since prog->aux remains stable during bpf_patch_insn_data). However, concurrent program invocations on multiple CPUs doesn't work well with this. It's like, one program sets the state while the other tries to check it. It can be per-CPU but then we have to disable preemption (which cannot be done).

Unfortunately per-task state seemed like the only choice which works without complicating things too much.

Quoted 8 lines

kernel/bpf/helpers.c void bpf_rb_root_free(const struct btf_field *field, void *rb_root, · line 1894

Quoted 6 lines
kernel/bpf/helpers.c +6 -0
+notrace u64 bpf_get_exception(void)
+{
+	int i = interrupt_context_level();
+
+	return current->bpf_exception_thrown[i];
+}

this is too slow to be acceptable.

I agree, also partly why I still marked this an RFC.

Quoted 6 lines

it needs to be single load plus branch.
with prog->aux->exception approach we can achieve that. Instead of inserting a call to bpf_get_exception() we can do load+cmp. We probably should pass prog->aux into exception callback, so it can know where throw came from.

IMO prog->aux->exception won't work either (unless I'm missing some way which you can point out). The other option would be that we spill pointer to the per-task exception state to the program's stack on entry, and then every check loads the value and performs the check. It will be a load from stack, load from memory and then a jump instruction. Still not as good as a direct load though, which we'd have with prog->aux, but much better than the current state.

Quoted 8 lines
Quoted 5 lines

- Rewrites happen for bpf_throw and call instructions to subprogs. The instructions which are executed in the main frame of the main program (thus, not global functions and extension programs, which end up executing in frame > 0) need to be rewritten differently. This is tracked using BPF_THROW_OUTER vs BPF_THROW_INNER. If not done, a

how about BPF_THROW_OUTER vs BPF_THROW_ANY_INNER ? would it be more precise ?

I'm fine with the renaming. The only thing the type signifies is if we need to do the rewrite for frame 0 vs frame N.

Quoted 13 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_rcu_read_unlock(void) · line 2317

Quoted 7 lines
kernel/bpf/helpers.c +6 -0
+__bpf_kfunc notrace void bpf_throw(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = true;
+}

I think this needs to take u64 or couple u64 args and store them in the scratch area.
bpf_assert* macros also need a way for bpf prog to specify the reason for the assertion.
Otherwise there won't be any way to debug what happened.

I agree. Should we force it to be a constant value? Then we can hardcode it in the .text without having to save and restore it, but that might end up being a little too restrictive?

#6 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 8 lines · Kumar Kartikeya Dwivedi
Quoted 7 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

Quoted 6 lines
Quoted 2 lines

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Can you elaborate? If a sleepable program blocks, that means the task is scheduled out, so the next program will use the other task's task_struct. Same for preemption for normal progs (under RT or not).

I was worried about the case of the same task but different code paths
in the kernel with tracing prog stepping on preempted lsm.s prog.
I think you point that in this case they gotta be in different interrupt_context_level. I need to think it through a bit more.

Quoted 6 lines
Quoted 2 lines

How about using a scratch space in prog->aux->exception[] instead of current task?

I actually had this thought. It's even better because we can hardcode the address of the exception state right in the program (since prog->aux remains stable during bpf_patch_insn_data).

exactly.

Quoted 3 lines

However, concurrent program invocations on
multiple CPUs doesn't work well with this. It's like, one program sets the state while the other tries to check it.

Right. If it asserts on one cpu all other cpus will unwind as well, since we're saying bpf_assert is for exceptions when user cannot convince the verifier that the program is correct.
So it doesn't matter that it aborted everywhere. It's probably a good thing too.

Quoted 2 lines

It can be per-CPU but then we have to disable
preemption (which cannot be done).

I was thinking to propose a per-cpu prog->aux->exception[] area. Sleepable and not are in migrate_disable(). bpf progs never migrate. So we can do it, but we'd need new pseudo this_cpu_ptr instruction and corresponding JIT support which felt like overkill.

Another idea I contemplated is to do preempt_disable() and local_irq_save() into special field in prog->aux->exception first thing in bpf_throw() and then re-enable everything before entering exception cb.
To avoid races with other progs, but NMI can still happen, so it's pointless. Just non-per-cpu prog->aux->exception seems good enough.

Quoted 11 lines
Quoted 8 lines
Quoted 5 lines

- Rewrites happen for bpf_throw and call instructions to subprogs. The instructions which are executed in the main frame of the main program (thus, not global functions and extension programs, which end up executing in frame > 0) need to be rewritten differently. This is tracked using BPF_THROW_OUTER vs BPF_THROW_INNER. If not done, a

how about BPF_THROW_OUTER vs BPF_THROW_ANY_INNER ? would it be more precise ?

I'm fine with the renaming. The only thing the type signifies is if we need to do the rewrite for frame 0 vs frame N.

Sure. BPF_THROW_FRAME_ZERO and BPF_THROW_FRAME_NON_ZERO also works. Or any name that shows that 2nd includes multiple cases.

Quoted 14 lines
Quoted 13 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_rcu_read_unlock(void) · line 2317

Quoted 7 lines
kernel/bpf/helpers.c +6 -0
+__bpf_kfunc notrace void bpf_throw(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = true;
+}

I think this needs to take u64 or couple u64 args and store them in the scratch area.
bpf_assert* macros also need a way for bpf prog to specify the reason for the assertion.
Otherwise there won't be any way to debug what happened.

Quoted 3 lines

I agree. Should we force it to be a constant value? Then we can hardcode it in the .text without having to save and restore it, but that might end up being a little too restrictive?

with prog->aux->exception approach run-time values works too.

author maintainer
#7 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Kumar Kartikeya Dwivedi
Quoted 9 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Quoted 9 lines
Quoted 3 lines

Can you elaborate? If a sleepable program blocks, that means the task is scheduled out, so the next program will use the other task's task_struct. Same for preemption for normal progs (under RT or not).

I was worried about the case of the same task but different code paths
in the kernel with tracing prog stepping on preempted lsm.s prog.
I think you point that in this case they gotta be in different interrupt_context_level. I need to think it through a bit more.

If there is nesting, the programs always clear their exception state on exit, so the prog that calls into the kernel which then calls into the tracing prog etc. won't see its exception state on return. The only path where attaching programs would screw things up is when we see a thrown exception and start unwinding (where clearing would be a problem since its done frame-by-frame). For that, I already prevent _throwing_ fexit programs from attaching to subprogs in this series (normal ones are still ok and supported, because fentry/fexit is important for stats etc.). There might be some other corner cases I missed but ensuring this property alone in general should make things work correctly.

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

How about using a scratch space in prog->aux->exception[] instead of current task?

I actually had this thought. It's even better because we can hardcode the address of the exception state right in the program (since prog->aux remains stable during bpf_patch_insn_data).

exactly.

Quoted 9 lines
Quoted 3 lines

However, concurrent program invocations on
multiple CPUs doesn't work well with this. It's like, one program sets the state while the other tries to check it.

Right. If it asserts on one cpu all other cpus will unwind as well, since we're saying bpf_assert is for exceptions when user cannot convince the verifier that the program is correct.
So it doesn't matter that it aborted everywhere. It's probably a good thing too.

We can discuss the semantics (this makes bpf_assert more stronger and basically poisons the program globally in some sense), but implementation wise it's going to be a lot more tricky to reason about correctness.

Right now, the verifier follows paths and knows what resources are held when we throw from a nested call chain (to complain on leaks). Callers doing the check for exception state at runtime expect only certain throwing points to trigger the check and rely on that for leak freedom.

With a global prog->aux->exception, things will be ok for the CPU on which the exception was thrown, but some other CPU will see the check returning true in a caller even if the callee subprog for it did not throw and was possibly transferring its acquired references to the caller after completing execution, which now causes leaks (because subprogs are allowed to acquire and return to their caller).

The way to handle this would be that we assume every callee which throws may also notionally throw right when returning (due to some other CPU's throw which we may see). Then every exit from throwing callees may be processed as throwing if we see the global state as set.

However, this completely prevents subprogs from transferring some acquired resource to their caller (which I think is too restrictive). If I'm acquiring memory from static subprog and returning to my caller, I can't any longer since I notionally throw when exiting and holding resources when doing bpf_throw is disallowed, so transfer is out of the question.

In the current scenario it would work, because I threw early on in my subprog when checking some condition (or proving something to the verifier) and after that just chugged along and did my work.

Quoted 20 lines
Quoted 2 lines

It can be per-CPU but then we have to disable
preemption (which cannot be done).

I was thinking to propose a per-cpu prog->aux->exception[] area. Sleepable and not are in migrate_disable(). bpf progs never migrate. So we can do it, but we'd need new pseudo this_cpu_ptr instruction and corresponding JIT support which felt like overkill.

Another idea I contemplated is to do preempt_disable() and local_irq_save() into special field in prog->aux->exception first thing in bpf_throw() and then re-enable everything before entering exception cb.
To avoid races with other progs, but NMI can still happen, so it's pointless. Just non-per-cpu prog->aux->exception seems good enough.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

- Rewrites happen for bpf_throw and call instructions to subprogs. The instructions which are executed in the main frame of the main program (thus, not global functions and extension programs, which end up executing in frame > 0) need to be rewritten differently. This is tracked using BPF_THROW_OUTER vs BPF_THROW_INNER. If not done, a

Quoted 9 lines
Quoted 5 lines
Quoted 2 lines

how about BPF_THROW_OUTER vs BPF_THROW_ANY_INNER ? would it be more precise ?

I'm fine with the renaming. The only thing the type signifies is if we need to do the rewrite for frame 0 vs frame N.

Sure. BPF_THROW_FRAME_ZERO and BPF_THROW_FRAME_NON_ZERO also works. Or any name that shows that 2nd includes multiple cases.

Ack.

Quoted 19 lines
Quoted 14 lines
Quoted 13 lines

kernel/bpf/helpers.c __bpf_kfunc void bpf_rcu_read_unlock(void) · line 2317

Quoted 7 lines
kernel/bpf/helpers.c +6 -0
+__bpf_kfunc notrace void bpf_throw(void)
+{
+	int i = interrupt_context_level();
+
+	current->bpf_exception_thrown[i] = true;
+}

I think this needs to take u64 or couple u64 args and store them in the scratch area.
bpf_assert* macros also need a way for bpf prog to specify the reason for the assertion.
Otherwise there won't be any way to debug what happened.

Quoted 3 lines

I agree. Should we force it to be a constant value? Then we can hardcode it in the .text without having to save and restore it, but that might end up being a little too restrictive?

with prog->aux->exception approach run-time values works too.

#8 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 73 lines · Kumar Kartikeya Dwivedi
Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Kumar Kartikeya Dwivedi
Quoted 9 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Quoted 9 lines
Quoted 3 lines

Can you elaborate? If a sleepable program blocks, that means the task is scheduled out, so the next program will use the other task's task_struct. Same for preemption for normal progs (under RT or not).

I was worried about the case of the same task but different code paths
in the kernel with tracing prog stepping on preempted lsm.s prog.
I think you point that in this case they gotta be in different interrupt_context_level. I need to think it through a bit more.

If there is nesting, the programs always clear their exception state on exit, so the prog that calls into the kernel which then calls into the tracing prog etc. won't see its exception state on return. The only path where attaching programs would screw things up is when we see a thrown exception and start unwinding (where clearing would be a problem since its done frame-by-frame). For that, I already prevent _throwing_ fexit programs from attaching to subprogs in this series (normal ones are still ok and supported, because fentry/fexit is important for stats etc.). There might be some other corner cases I missed but ensuring this property alone in general should make things work correctly.

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

How about using a scratch space in prog->aux->exception[] instead of current task?

I actually had this thought. It's even better because we can hardcode the address of the exception state right in the program (since prog->aux remains stable during bpf_patch_insn_data).

exactly.

Quoted 9 lines
Quoted 3 lines

However, concurrent program invocations on
multiple CPUs doesn't work well with this. It's like, one program sets the state while the other tries to check it.

Right. If it asserts on one cpu all other cpus will unwind as well, since we're saying bpf_assert is for exceptions when user cannot convince the verifier that the program is correct.
So it doesn't matter that it aborted everywhere. It's probably a good thing too.

We can discuss the semantics (this makes bpf_assert more stronger and basically poisons the program globally in some sense), but implementation wise it's going to be a lot more tricky to reason about correctness.

Right now, the verifier follows paths and knows what resources are held when we throw from a nested call chain (to complain on leaks). Callers doing the check for exception state at runtime expect only certain throwing points to trigger the check and rely on that for leak freedom.

With a global prog->aux->exception, things will be ok for the CPU on which the exception was thrown, but some other CPU will see the check returning true in a caller even if the callee subprog for it did not throw and was possibly transferring its acquired references to the caller after completing execution, which now causes leaks (because subprogs are allowed to acquire and return to their caller).

The way to handle this would be that we assume every callee which throws may also notionally throw right when returning (due to some other CPU's throw which we may see). Then every exit from throwing callees may be processed as throwing if we see the global state as set.

Quoted 5 lines

However, this completely prevents subprogs from transferring some acquired resource to their caller (which I think is too restrictive). If I'm acquiring memory from static subprog and returning to my caller, I can't any longer since I notionally throw when exiting and holding resources when doing bpf_throw is disallowed, so transfer is out of the question.

I was under impression that subprogs cannot acquire refs and transfer them
to caller.
Looks like your commit 9d9d00ac29d0 ("bpf: Fix reference state management for synchronous callbacks") allowed too much.
I don't think it's a good idea to support coding patterns like:
void my_alloc_foo(struct foo **ptr)
{
struct foo *p = bpf_obj_new(typeof(*p));
*ptr = p;
}

It's a correct C, of course, but do we really want to support such code?
I don't think the verifier can fully support it anyway.
That commit of yours allowed some of it in theory, but above example probably won't work, since 'transfer' isn't understood by the verifier.

Regardless whether we tighten the verifier now or later such subprogs shouldn't be throwing. So I don't see an issue doing global prog->aux->exception.

author maintainer
#9 lore raw

Re: [PATCH RFC bpf-next v1 3/9] bpf: Implement bpf_throw kfunc

Quoted 80 lines · Alexei Starovoitov
Quoted 73 lines · Kumar Kartikeya Dwivedi
Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Kumar Kartikeya Dwivedi
Quoted 9 lines · Alexei Starovoitov
Quoted 5 lines · Kumar Kartikeya Dwivedi

- The exception state is represented using four booleans in the task_struct of current task. Each boolean corresponds to the exception state for each kernel context. This allows BPF programs to be interrupted and still not clobber the other's exception state.

that doesn't work for sleepable bpf progs and in RT for regular progs too.

Quoted 9 lines
Quoted 3 lines

Can you elaborate? If a sleepable program blocks, that means the task is scheduled out, so the next program will use the other task's task_struct. Same for preemption for normal progs (under RT or not).

I was worried about the case of the same task but different code paths
in the kernel with tracing prog stepping on preempted lsm.s prog.
I think you point that in this case they gotta be in different interrupt_context_level. I need to think it through a bit more.

If there is nesting, the programs always clear their exception state on exit, so the prog that calls into the kernel which then calls into the tracing prog etc. won't see its exception state on return. The only path where attaching programs would screw things up is when we see a thrown exception and start unwinding (where clearing would be a problem since its done frame-by-frame). For that, I already prevent _throwing_ fexit programs from attaching to subprogs in this series (normal ones are still ok and supported, because fentry/fexit is important for stats etc.). There might be some other corner cases I missed but ensuring this property alone in general should make things work correctly.

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

How about using a scratch space in prog->aux->exception[] instead of current task?

I actually had this thought. It's even better because we can hardcode the address of the exception state right in the program (since prog->aux remains stable during bpf_patch_insn_data).

exactly.

Quoted 9 lines
Quoted 3 lines

However, concurrent program invocations on
multiple CPUs doesn't work well with this. It's like, one program sets the state while the other tries to check it.

Right. If it asserts on one cpu all other cpus will unwind as well, since we're saying bpf_assert is for exceptions when user cannot convince the verifier that the program is correct.
So it doesn't matter that it aborted everywhere. It's probably a good thing too.

We can discuss the semantics (this makes bpf_assert more stronger and basically poisons the program globally in some sense), but implementation wise it's going to be a lot more tricky to reason about correctness.

Right now, the verifier follows paths and knows what resources are held when we throw from a nested call chain (to complain on leaks). Callers doing the check for exception state at runtime expect only certain throwing points to trigger the check and rely on that for leak freedom.

With a global prog->aux->exception, things will be ok for the CPU on which the exception was thrown, but some other CPU will see the check returning true in a caller even if the callee subprog for it did not throw and was possibly transferring its acquired references to the caller after completing execution, which now causes leaks (because subprogs are allowed to acquire and return to their caller).

The way to handle this would be that we assume every callee which throws may also notionally throw right when returning (due to some other CPU's throw which we may see). Then every exit from throwing callees may be processed as throwing if we see the global state as set.

Quoted 5 lines

However, this completely prevents subprogs from transferring some acquired resource to their caller (which I think is too restrictive). If I'm acquiring memory from static subprog and returning to my caller, I can't any longer since I notionally throw when exiting and holding resources when doing bpf_throw is disallowed, so transfer is out of the question.

Quoted 4 lines

I was under impression that subprogs cannot acquire refs and transfer them
to caller.
Looks like your commit 9d9d00ac29d0 ("bpf: Fix reference state management for synchronous callbacks") allowed too much.

I think you misunderstood the change in that commit. It was about restricting callback functions from acquiring references and not releasing them before their BPF_EXIT (since our handling is not completely correct for more than one iteration). The verifier has always allowed acquiring references and transferring them to the caller for subprog calls.

Quoted 11 lines

I don't think it's a good idea to support coding patterns like:
void my_alloc_foo(struct foo **ptr)
{
struct foo *p = bpf_obj_new(typeof(*p));
*ptr = p;
}

It's a correct C, of course, but do we really want to support such code?
I don't think the verifier can fully support it anyway.
That commit of yours allowed some of it in theory, but above example probably won't work, since 'transfer' isn't understood by the verifier.

I have no strong opinions about restricting (I think the code for handling transfers is sane and correct, we just transfer the modified reference state, and it's a natural valid form of writing programs), especially since static subprogs do not have the limitations as global subprogs, and you really don't want to inline everything all the time.
But I think we may end up breaking existing code/programs if we do. Whether that fallout will be small or not, I have no data yet to predict.

Quoted 3 lines

Regardless whether we tighten the verifier now or later such subprogs shouldn't be throwing. So I don't see an issue doing global prog->aux->exception.

That's certainly an option, but I still think we need to be a bit careful. The reason is that during analysis, we need to determine that whenever a subprog call exits, are we in a state where we can safely unwind? It might end up restricting a large set of use cases, but I can only say with certainty after I try it out.

Right now, I heavily rely on the assumption that the checks only become true when something throws (to also minimize rewrites, but that's a minor reason). The core reason is being able to argue about correctness. With global exception state, they can become true anytime, so we need to be a lot more conservative even if we e.g. didn't see a subprog as throwing from all callsites.

call subprog(A) // will be rewritten, as using R1=A can throw call subprog(B) // not rewritten, as using R1=B does not throw

author maintainer
#10 lore raw

RFC PATCH 4/9 bpf: Handle throwing BPF callbacks in helpers and kfuncs

In reply to Kumar Kartikeya Dwivedi

Enable handling of callbacks that throw within helpers and kfuncs taking them. The problem with helpers is that exception state can be manipulated by a tracing program which is invoked between the checking of exception after calling callback and returning back to the program. Hence, helpers always return -EJUKEBOX whenever they detect an exception. Only 1 kfunc takes a callback (bpf_rbtree_add), so it is updated to be notrace to avoid this pitfall.

This allows us to use bpf_get_exception to detect the thrown case, and in case we miss exception event we use return code to unwind.

TODO: It might be possible to simply check return code in case of helpers or kfuncs taking callbacks and check_helper_ret_code = true, and not bother with exception state. This should lead to less code being generated per-callsite. For all other cases, we can rely on bpf_get_exception, and ensure that helper/kfunc uses notrace to avoid invocation of tracing programs that clobber exception state on return path. But make this change in v2 after ensuring current->bpf_exception_thrown approach is acceptable.

---
 include/linux/bpf_verifier.h |   1 +
 kernel/bpf/arraymap.c        |   4 +-
 kernel/bpf/bpf_iter.c        |   2 +
 kernel/bpf/hashtab.c         |   4 +-
 kernel/bpf/helpers.c         |  18 +++--
 kernel/bpf/ringbuf.c         |   4 ++
 kernel/bpf/task_iter.c       |   2 +
 kernel/bpf/verifier.c        | 129 +++++++++++++++++++++++++++++++++++
 8 files changed, 156 insertions(+), 8 deletions(-)
include/linux/bpf_verifier.h +1 -0
index bc067223d3ee..a5346a2b7e68 100644
@@ -485,6 +485,7 @@ struct bpf_insn_aux_data {
 	bool zext_dst; /* this insn zero extends dst reg */
 	bool storage_get_func_atomic; /* bpf_*_storage_get() with atomic memory alloc */
 	bool is_iter_next; /* bpf_iter_<type>_next() kfunc call */
+	bool skip_patch_call_imm; /* Skip patch_call_imm phase in do_misc_fixups */
 	u8 alu_state; /* used in combination with alu_limit */
 
 	/* below fields are initialized once */
kernel/bpf/arraymap.c +3 -1
index de0eadf8706f..6c0c5e726ebf 100644
@@ -711,6 +711,8 @@ static long bpf_for_each_array_elem(struct bpf_map *map, bpf_callback_t callback
 		key = i;
 		ret = callback_fn((u64)(long)map, (u64)(long)&key,
 				  (u64)(long)val, (u64)(long)callback_ctx, 0);
+		if (bpf_get_exception())
+			ret = -EJUKEBOX;
 		/* return value: 0 - continue, 1 - stop and return */
 		if (ret)
 			break;
@@ -718,7 +720,7 @@ static long bpf_for_each_array_elem(struct bpf_map *map, bpf_callback_t callback
 
 	if (is_percpu)
 		migrate_enable();
-	return num_elems;
+	return ret == -EJUKEBOX ? ret : num_elems;
 }
 
 static u64 array_map_mem_usage(const struct bpf_map *map)
kernel/bpf/bpf_iter.c +2 -0
index 96856f130cbf..6e4e4b6213f8 100644
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;
 		/* return value: 0 - continue, 1 - stop and return */
 		if (ret)
 			return i + 1;
kernel/bpf/hashtab.c +3 -1
index 00c253b84bf5..5e70151e0414 100644
@@ -2178,6 +2178,8 @@ static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_
 			num_elems++;
 			ret = callback_fn((u64)(long)map, (u64)(long)key,
 					  (u64)(long)val, (u64)(long)callback_ctx, 0);
+			if (bpf_get_exception())
+				ret = -EJUKEBOX;
 			/* return value: 0 - continue, 1 - stop and return */
 			if (ret) {
 				rcu_read_unlock();
@@ -2189,7 +2191,7 @@ static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_
 out:
 	if (is_percpu)
 		migrate_enable();
-	return num_elems;
+	return ret == -EJUKEBOX ? ret : num_elems;
 }
 
 static u64 htab_map_mem_usage(const struct bpf_map *map)
kernel/bpf/helpers.c +12 -6
index 89e70907257c..82db3a64fa3f 100644
@@ -1982,10 +1982,11 @@ __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,
 }
 
 /* Need to copy rbtree_add_cached's logic here because our 'less' is a BPF
- * program
+ * program.
+ * Marked notrace to avoid clobbering of exception state in current by BPF
+ * programs.
  */
-static void __bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
-			     void *less)
+static notrace void __bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node, void *less)
 {
 	struct rb_node **link = &((struct rb_root_cached *)root)->rb_root.rb_node;
 	bpf_callback_t cb = (bpf_callback_t)less;
@@ -1993,8 +1994,13 @@ static void __bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
 	bool leftmost = true;
 
 	while (*link) {
+		u64 cb_res;
+
 		parent = *link;
-		if (cb((uintptr_t)node, (uintptr_t)parent, 0, 0, 0)) {
+		cb_res = cb((uintptr_t)node, (uintptr_t)parent, 0, 0, 0);
+		if (bpf_get_exception())
+			return;
+		if (cb_res) {
 			link = &parent->rb_left;
 		} else {
 			link = &parent->rb_right;
@@ -2007,8 +2013,8 @@ static void __bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
 			       (struct rb_root_cached *)root, leftmost);
 }
 
-__bpf_kfunc void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
-				bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b))
+__bpf_kfunc notrace void bpf_rbtree_add(struct bpf_rb_root *root, struct bpf_rb_node *node,
+					bool (less)(struct bpf_rb_node *a, const struct bpf_rb_node *b))
 {
 	__bpf_rbtree_add(root, node, (void *)less);
 }
kernel/bpf/ringbuf.c +4 -0
index 875ac9b698d9..7f6764ae4fff 100644
@@ -766,6 +766,10 @@ BPF_CALL_4(bpf_user_ringbuf_drain, struct bpf_map *, map,
 
 		bpf_dynptr_init(&dynptr, sample, BPF_DYNPTR_TYPE_LOCAL, 0, size);
 		ret = callback((uintptr_t)&dynptr, (uintptr_t)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception()) {
+			ret = -EJUKEBOX;
+			goto schedule_work_return;
+		}
 		__bpf_user_ringbuf_sample_release(rb, size, flags);
 	}
 	ret = samples - discarded_samples;
kernel/bpf/task_iter.c +2 -0
index c4ab9d6cdbe9..6e8667f03784 100644
@@ -807,6 +807,8 @@ BPF_CALL_5(bpf_find_vma, struct task_struct *, task, u64, start,
 		callback_fn((u64)(long)task, (u64)(long)vma,
 			    (u64)(long)callback_ctx, 0, 0);
 		ret = 0;
+		if (bpf_get_exception())
+			ret = -EJUKEBOX;
 	}
 	bpf_mmap_unlock_mm(work, mm);
 	return ret;
kernel/bpf/verifier.c +129 -0

153 lines not on this page · raw message

Signature · 1 line
2.40.0
#11 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.
Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

The choice of error name is odd, tbh.

author maintainer
#12 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 10 lines · Alexei Starovoitov

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

The choice of error name is odd, tbh.

I was trying to choose something that helpers will never pass back to the program to avoid conflicts. Open to other suggestions (but it may not matter depending on the discussion above).

#13 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.
There is nothing to unwind in the timer case.
Certinaly not allowed to rethrow in exception cb.
less-like rbtree_add should be tiny. And it's gotta to be fast.

author maintainer
#14 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 37 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.

There's also bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain.

Quoted 3 lines

There is nothing to unwind in the timer case. Certinaly not allowed to rethrow in exception cb. less-like rbtree_add should be tiny. And it's gotta to be fast.

I agree for some of the cases above they do not matter too much. The main one was bpf_loop, and the ones I listed (like for_each_map) seem to be those where people may do siginificant work in the callback.

I think we can make it zero cost for programs that don't use it (even for the kernel code), I was just hoping to be able to support it everywhere as a generic helper to abort program execution without any special corner cases during usage. The other main point was about code sharing of functions which makes use of assertions. But I'm ok with dropping support for callbacks if you think it's not worth it in the end.

#15 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 51 lines · Kumar Kartikeya Dwivedi
Quoted 37 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.

There's also bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain.

Quoted 3 lines

There is nothing to unwind in the timer case. Certinaly not allowed to rethrow in exception cb. less-like rbtree_add should be tiny. And it's gotta to be fast.

I agree for some of the cases above they do not matter too much. The main one was bpf_loop, and the ones I listed (like for_each_map) seem to be those where people may do siginificant work in the callback.

Quoted 6 lines

I think we can make it zero cost for programs that don't use it (even for the kernel code), I was just hoping to be able to support it everywhere as a generic helper to abort program execution without any special corner cases during usage. The other main point was about code sharing of functions which makes use of assertions. But I'm ok with dropping support for callbacks if you think it's not worth it in the end.

I think the unexpected run-time slowdown due to checks is a bigger problem. Since bpf_assert is a 'bad program detector' it should be as zero cost to run-time as possible. Hence I'm advocating for single load+jmp approach of prog->aux->exception. The run-time matter more than ability to use assert in all conditions.
I think we'd need two flavors of bpf_assert() asm macros: with and without bpf_throw(). They seem to be useful without actual throw. They will help the verifier understand the ranges of variables in both cases. The macros are the 99% of the feature. The actual throw mechanism is 1%. The unwinding and release of resource is a cost of using macros without explicit control flow in the bpf programs.
The macros without throw might be good enough in many cases.

author maintainer
#16 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 59 lines · Alexei Starovoitov
Quoted 51 lines · Kumar Kartikeya Dwivedi
Quoted 37 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

kernel/bpf/bpf_iter.c BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
kernel/bpf/bpf_iter.c +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.

There's also bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain.

Quoted 3 lines

There is nothing to unwind in the timer case. Certinaly not allowed to rethrow in exception cb. less-like rbtree_add should be tiny. And it's gotta to be fast.

I agree for some of the cases above they do not matter too much. The main one was bpf_loop, and the ones I listed (like for_each_map) seem to be those where people may do siginificant work in the callback.

Quoted 6 lines

I think we can make it zero cost for programs that don't use it (even for the kernel code), I was just hoping to be able to support it everywhere as a generic helper to abort program execution without any special corner cases during usage. The other main point was about code sharing of functions which makes use of assertions. But I'm ok with dropping support for callbacks if you think it's not worth it in the end.

Quoted 3 lines

I think the unexpected run-time slowdown due to checks is a bigger problem. Since bpf_assert is a 'bad program detector' it should be as zero cost to run-time as possible. Hence I'm advocating for single load+jmp approach of prog->aux->exception.

I 100% agree, slow down is a big problem and a downside of the current version. They need to be as lightweight as possible. It's too costly right now in this set.

Quoted 7 lines

The run-time matter more than ability to use assert in all conditions. I think we'd need two flavors of bpf_assert() asm macros: with and without bpf_throw(). They seem to be useful without actual throw. They will help the verifier understand the ranges of variables in both cases. The macros are the 99% of the feature. The actual throw mechanism is 1%. The unwinding and release of resource is a cost of using macros without explicit control flow in the bpf programs. The macros without throw might be good enough in many cases.

Ok, I'll update to allow for both variants. But just to confirm, do you want to shelve automatic cleanup (part 2 for now), or want to add it? I'm not clear on whether you agree or disagree it's necessary.

I'll try the prog->aux->exception route, but I must say that we're sort of trading off simpler semantics/behavior for speedup in that case (which is necessary, but it is a cost IMO). I'll post a version using that, but I'll also add comparisons with the variant where we spill ptr to exception state and load+jmp. It's an extra instruction but I will try to benchmark and see how much difference it causes in practice (probably over the XDP benchmark using such exceptions, since that's one of the most important performance-critical use cases). If you agree, let's double down on whatever approach we choose after analysing the difference?

#17 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 80 lines · Kumar Kartikeya Dwivedi
Quoted 59 lines · Alexei Starovoitov
Quoted 51 lines · Kumar Kartikeya Dwivedi
Quoted 37 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

Review BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
(quoted diff) +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.

There's also bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain.

Quoted 3 lines

There is nothing to unwind in the timer case. Certinaly not allowed to rethrow in exception cb. less-like rbtree_add should be tiny. And it's gotta to be fast.

I agree for some of the cases above they do not matter too much. The main one was bpf_loop, and the ones I listed (like for_each_map) seem to be those where people may do siginificant work in the callback.

Quoted 6 lines

I think we can make it zero cost for programs that don't use it (even for the kernel code), I was just hoping to be able to support it everywhere as a generic helper to abort program execution without any special corner cases during usage. The other main point was about code sharing of functions which makes use of assertions. But I'm ok with dropping support for callbacks if you think it's not worth it in the end.

Quoted 3 lines

I think the unexpected run-time slowdown due to checks is a bigger problem. Since bpf_assert is a 'bad program detector' it should be as zero cost to run-time as possible. Hence I'm advocating for single load+jmp approach of prog->aux->exception.

I 100% agree, slow down is a big problem and a downside of the current version. They need to be as lightweight as possible. It's too costly right now in this set.

Quoted 7 lines

The run-time matter more than ability to use assert in all conditions. I think we'd need two flavors of bpf_assert() asm macros: with and without bpf_throw(). They seem to be useful without actual throw. They will help the verifier understand the ranges of variables in both cases. The macros are the 99% of the feature. The actual throw mechanism is 1%. The unwinding and release of resource is a cost of using macros without explicit control flow in the bpf programs. The macros without throw might be good enough in many cases.

Ok, I'll update to allow for both variants. But just to confirm, do you want to shelve automatic cleanup (part 2 for now), or want to add it? I'm not clear on whether you agree or disagree it's necessary.

Quoted 9 lines

I'll try the prog->aux->exception route, but I must say that we're sort of trading off simpler semantics/behavior for speedup in that case (which is necessary, but it is a cost IMO). I'll post a version using that, but I'll also add comparisons with the variant where we spill ptr to exception state and load+jmp. It's an extra instruction but I will try to benchmark and see how much difference it causes in practice (probably over the XDP benchmark using such exceptions, since that's one of the most important performance-critical use cases). If you agree, let's double down on whatever approach we choose after analysing the difference?

I think performance considerations dominate implementation and ease of use. Could you describe how 'spill to exception state' will look like?
I think the check after bpf_call insn has to be no more than LD + JMP. I was thinking whether we can do static_key like patching of the code. bpf_throw will know all locations that should be converted from nop into check and will do text_poke_bp before throwing.
Maybe we can consider offline unwind and release too. The verifier will prep release tables and throw will execute them. BPF progs always have frame pointers, so walking the stack back is relatively easy. Release per callsite is hard.

As far as benchmarking I'd use selftests/bpf/bench. No need for real network XDP.

author maintainer
#18 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 91 lines · Alexei Starovoitov
Quoted 80 lines · Kumar Kartikeya Dwivedi
Quoted 59 lines · Alexei Starovoitov
Quoted 51 lines · Kumar Kartikeya Dwivedi
Quoted 37 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 10 lines · Alexei Starovoitov

Review BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, · line 763

Quoted 6 lines · Kumar Kartikeya Dwivedi
(quoted diff) +2 -0
@@ -759,6 +759,8 @@ BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx,
 
 	for (i = 0; i < nr_loops; i++) {
 		ret = callback((u64)i, (u64)(long)callback_ctx, 0, 0, 0);
+		if (bpf_get_exception())
+			return -EJUKEBOX;

This is too slow.
We cannot afford a call and conditional here.

There are two more options here: have two variants, one with and without the check (always_inline template and bpf_loop vs bpf_loop_except calling functions which pass false/true) and dispatch to the appropriate one based on if callback throws or not (so the cost is not paid for current users at all). Secondly, we can avoid repeated calls by hoisting the call out and save the pointer to exception state, then it's a bit less costly.

Quoted 8 lines

Some time ago folks tried bpf_loop() and went back to bounded loop, because the overhead of indirect call was not acceptable.
After that we've added inlining of bpf_loop() to make overhead to the minimum. With prog->aux->exception[] approach it might be ok-ish,
but my preference would be to disallow throw in callbacks.
timer cb, rbtree_add cb are typically small.
bpf_loop cb can be big, but we have open coded iterators now.
So disabling asserts in cb-s is probably acceptable trade-off.

Quoted 7 lines

If the only reason to avoid them is the added performance cost, we can work towards eliminating that when bpf_throw is not used (see above). I agree that supporting it everywhere means thinking about a lot more corner cases, but I feel it would be less surprising if doing bpf_assert simply worked everywhere. One of the other reasons is that if it's being used within a shared static function that both main program and callbacks call into, it will be a bit annoying that it doesn't work in one context.

Quoted 2 lines

I hope with open coded iterators the only use case for callbacks will be timers, exception cb and rbtree_add. All three are special cases.

There's also bpf_for_each_map_elem, bpf_find_vma, bpf_user_ringbuf_drain.

Quoted 3 lines

There is nothing to unwind in the timer case. Certinaly not allowed to rethrow in exception cb. less-like rbtree_add should be tiny. And it's gotta to be fast.

I agree for some of the cases above they do not matter too much. The main one was bpf_loop, and the ones I listed (like for_each_map) seem to be those where people may do siginificant work in the callback.

Quoted 6 lines

I think we can make it zero cost for programs that don't use it (even for the kernel code), I was just hoping to be able to support it everywhere as a generic helper to abort program execution without any special corner cases during usage. The other main point was about code sharing of functions which makes use of assertions. But I'm ok with dropping support for callbacks if you think it's not worth it in the end.

Quoted 3 lines

I think the unexpected run-time slowdown due to checks is a bigger problem. Since bpf_assert is a 'bad program detector' it should be as zero cost to run-time as possible. Hence I'm advocating for single load+jmp approach of prog->aux->exception.

I 100% agree, slow down is a big problem and a downside of the current version. They need to be as lightweight as possible. It's too costly right now in this set.

Quoted 7 lines

The run-time matter more than ability to use assert in all conditions. I think we'd need two flavors of bpf_assert() asm macros: with and without bpf_throw(). They seem to be useful without actual throw. They will help the verifier understand the ranges of variables in both cases. The macros are the 99% of the feature. The actual throw mechanism is 1%. The unwinding and release of resource is a cost of using macros without explicit control flow in the bpf programs. The macros without throw might be good enough in many cases.

Ok, I'll update to allow for both variants. But just to confirm, do you want to shelve automatic cleanup (part 2 for now), or want to add it? I'm not clear on whether you agree or disagree it's necessary.

Quoted 9 lines

I'll try the prog->aux->exception route, but I must say that we're sort of trading off simpler semantics/behavior for speedup in that case (which is necessary, but it is a cost IMO). I'll post a version using that, but I'll also add comparisons with the variant where we spill ptr to exception state and load+jmp. It's an extra instruction but I will try to benchmark and see how much difference it causes in practice (probably over the XDP benchmark using such exceptions, since that's one of the most important performance-critical use cases). If you agree, let's double down on whatever approach we choose after analysing the difference?

Quoted 2 lines

I think performance considerations dominate implementation and ease of use. Could you describe how 'spill to exception state' will look like?

It was about spilling pointer to exception state on entry to program (so just main subprog) at a known offset on stack, then instead of LD + JMP, LD from stack + LD + JMP where the check is needed.

Quoted 8 lines

I think the check after bpf_call insn has to be no more than LD + JMP. I was thinking whether we can do static_key like patching of the code. bpf_throw will know all locations that should be converted from nop into check and will do text_poke_bp before throwing.
Maybe we can consider offline unwind and release too. The verifier will prep release tables and throw will execute them. BPF progs always have frame pointers, so walking the stack back is relatively easy. Release per callsite is hard.

After some thought, I think offline unwinding is the way to go. That means no rewrites for the existing code, and we just offload all the cost to the slow path (bpf_throw call) as it should be. There would be no cost at runtime (except the conditional branch, which should be well predicted). The current approach was a bit simpler so I gave it a shot first but I think it's not the way to go. I will rework the set.

Quoted 1 line

As far as benchmarking I'd use selftests/bpf/bench. No need for real network XDP.

Got it.

#19 lore raw

Re: [PATCH RFC bpf-next v1 4/9] bpf: Handle throwing BPF callbacks in helpers and kfuncs

Quoted 10 lines · Kumar Kartikeya Dwivedi
Quoted 9 lines

I think the check after bpf_call insn has to be no more than LD + JMP. I was thinking whether we can do static_key like patching of the code. bpf_throw will know all locations that should be converted from nop into check and will do text_poke_bp before throwing.
Maybe we can consider offline unwind and release too. The verifier will prep release tables and throw will execute them. BPF progs always have frame pointers, so walking the stack back is relatively easy. Release per callsite is hard.

Quoted 6 lines

After some thought, I think offline unwinding is the way to go. That means no rewrites for the existing code, and we just offload all the cost to the slow path (bpf_throw call) as it should be. There would be no cost at runtime (except the conditional branch, which should be well predicted). The current approach was a bit simpler so I gave it a shot first but I think it's not the way to go. I will rework the set.

It seems so indeed. Offline unwinding is more complex for sure. The challenge is to make it mostly arch independent.
Something like get_perf_callchain() followed by lookup IP->release_table and final setjmp() to bpf callback in the last bpf frame. is_bpf_text_address() will help.
We shouldn't gate it by HAVE_RELIABLE_STACKTRACE,
since bpf prog stack walking is reliable on all archs where JIT is enabled. Unwinding won't work reliably in interpreted mode though and it's ok. bpf_throw is a kfunc and it needs prog->jit_requested anyway.

author maintainer
#20 lore raw

RFC PATCH 5/9 bpf: Add pass to fixup global function throw information

In reply to Kumar Kartikeya Dwivedi

Within the do_check pass, we made a core assumption that we have correct can_throw info about all global subprogs and simply used mark_chain_throw without entering them to mark callsites leading up to their call. However, the do_check_subprogs pass of verifier is iterative and does not propagate can_throw information across global subprogs which call into each other. We need an extra pass through all of them to propagate can_throw information visibility throwing global subprogs into global subprogs that call into them.

After doing this pass, do_check_main will directly use mark_chain_throw again and have the correct information about all global subprogs which are called by it.

---
 kernel/bpf/verifier.c | 118 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 117 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +117 -1
index 07d808b05044..acfcaadca3b6 100644
@@ -13664,6 +13664,12 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
 			verbose(env, "missing btf func_info\n");
 			return -EINVAL;
 		}
+		/* NOTE: Do not change this directly, as we rely on only
+		 * BPF_FUNC_STATIC allowed as BPF_PSEUDO_FUNC targets in
+		 * do_check_subprogs, see comment about propagating exception
+		 * information across global functions. When changing this, add
+		 * bpf_pseudo_func handling to the propagating loop as well.
+		 */
 		if (aux->func_info_aux[subprogno].linkage != BTF_FUNC_STATIC) {
 			verbose(env, "callback function not static\n");
 			return -EINVAL;
@@ -18491,6 +18497,110 @@ static int do_check_common(struct bpf_verifier_env *env, int subprog)
 	return ret;
 }
 
+/* We have gone through all global subprogs, and we know which ones were seen as
+ * throwing exceptions. Since calls to other global functions are not explored
+ * and we simply continue exploration at the next instruction, we may have not
+ * fully propagated can_throw information. E.g. consider the case below, where 1
+ * and 2 are verified in order.
+ *
+ * gfunc 1:
+ *	call gfunc2
+ *	exit
+ * gfunc 2:
+ *	call bpf_throw
+ *
+ * At this point, gfunc1 is not marked as throwing, but it calls gfunc2 which
+ * actually throws. The only thing we need to do is go through every global
+ * function, and propagate the information back to their callers. We only care
+ * about BPF_PSEUDO_CALL, as BPF_PSEUDO_FUNC loads cannot have global functions
+ * as targets
+ *
+ * Logic mostly mimics check_max_stack_depth, but adjusted and simplified for
+ * our use case.
+ */
+static int fixup_global_subprog_throw_info(struct bpf_verifier_env *env)
+{
+	struct bpf_func_info_aux *func_info_aux = env->prog->aux->func_info_aux;
+	struct bpf_subprog_info *subprog = env->subprog_info;
+	int frame = 0, idx = 0, i = 0, subprog_end;
+	struct bpf_insn *insn = env->prog->insnsi;
+	int ret_insn[MAX_CALL_FRAMES];
+	int ret_prog[MAX_CALL_FRAMES];
+	bool can_throw;
+	int j, ret;
+
+	/* Start at first global subprog */
+	for (int s = 1; s < env->subprog_cnt; s++) {
+		if (func_info_aux[s].linkage != BTF_FUNC_GLOBAL)
+			continue;
+		idx = s;
+		break;
+	}
+	if (!idx)
+		return -EFAULT;
+	i = subprog[idx].start;
+continue_func:
+	can_throw = false;
+	subprog_end = subprog[idx + 1].start;
+	for (; i < subprog_end; i++) {
+		int next_insn;
+
+		if (!bpf_pseudo_call(insn + i))
+			continue;
+		/* remember insn and function to return to */
+		ret_insn[frame] = i + 1;
+		ret_prog[frame] = idx;
+
+		/* find the callee */
+		next_insn = i + insn[i].imm + 1;
+		idx = find_subprog(env, next_insn);
+		if (idx < 0) {
+			WARN_ONCE(1, "verifier bug. No program starts at insn %d\n", next_insn);
+			return -EFAULT;
+		}
+
+		/* Only follow global subprog calls */
+		if (func_info_aux[idx].linkage != BTF_FUNC_GLOBAL)
+			continue;
+		/* If this subprog already throws, mark all callers and continue
+		 * with next instruction in current subprog.
+		 */
+		if (subprog[idx].can_throw) {
+			/* Include current frame info when marking */
+			for (j = frame; j >= 0; j--) {
+				func_info_aux[ret_prog[j]].throws_exception = subprog[ret_prog[j]].can_throw = true;
+				/* Exception subprog cannot be set in global
+				 * function context, so set_throw_state_type
+				 * will always mark type as BPF_THROW_INNER
+				 * and subprog as -1.
+				 */
+				ret = set_throw_state_type(env, ret_insn[j] - 1, j, ret_prog[j]);
+				if (ret < 0)
+					return ret;
+			}
+			continue;
+		}
+
+		i = next_insn;
+		frame++;
+		if (frame >= MAX_CALL_FRAMES) {
+			verbose(env, "the call stack of %d frames is too deep !\n",
+				frame);
+			return -E2BIG;
+		}
+		goto continue_func;
+	}
+	/* end of for() loop means the last insn of the 'subprog'
+	 * was reached. Doesn't matter whether it was JA or EXIT
+	 */
+	if (frame == 0)
+		return 0;
+	frame--;
+	i = ret_insn[frame];
+	idx = ret_prog[frame];
+	goto continue_func;
+}
+
 /* Verify all global functions in a BPF program one by one based on their BTF.
  * All global functions must pass verification. Otherwise the whole program is rejected.
  * Consider:
@@ -18511,6 +18621,7 @@ static int do_check_common(struct bpf_verifier_env *env, int subprog)
 static int do_check_subprogs(struct bpf_verifier_env *env)
 {
 	struct bpf_prog_aux *aux = env->prog->aux;
+	bool does_anyone_throw = false;
 	int i, ret;
 
 	if (!aux->func_info)
@@ -18535,8 +18646,13 @@ static int do_check_subprogs(struct bpf_verifier_env *env)
 		 * opposite is fine though.
 		 */
 		aux->func_info_aux[i].throws_exception = env->subprog_info[i].can_throw;
+		if (!does_anyone_throw && env->subprog_info[i].can_throw)
+			does_anyone_throw = true;
 	}
-	return 0;
+
+	if (!does_anyone_throw)
+		return 0;
+	return fixup_global_subprog_throw_info(env);
 }
 
 static int do_check_main(struct bpf_verifier_env *env)
Signature · 1 line
2.40.0
author maintainer
#21 lore raw

RFC PATCH 6/9 bpf: Add KF_THROW annotation for kfuncs

In reply to Kumar Kartikeya Dwivedi

Add KF_THROW annotation to kfuncs to indicate that they may throw. This is mostly for testing for now, but in the future it could be used by kfuncs to throw on invalid arguments or invalid conditions based on their input arguments, causing the program to abort, and simplify the overall user experience of kfuncs for the happy case, without having to deal with corner cases that never occur at runtime.

---
 include/linux/btf.h   |  1 +
 kernel/bpf/verifier.c | 12 ++++++++++--
 net/bpf/test_run.c    | 12 ++++++++++++
 3 files changed, 23 insertions(+), 2 deletions(-)
include/linux/btf.h +1 -0
index d53b10cc55f2..8dfa4113822b 100644
@@ -75,6 +75,7 @@
 #define KF_ITER_NEW     (1 << 8) /* kfunc implements BPF iter constructor */
 #define KF_ITER_NEXT    (1 << 9) /* kfunc implements BPF iter next method */
 #define KF_ITER_DESTROY (1 << 10) /* kfunc implements BPF iter destructor */
+#define KF_THROW	(1 << 11) /* kfunc may throw a BPF exception */
 
 /*
  * Tag marking a kernel function as a kfunc. This is meant to minimize the
kernel/bpf/verifier.c +10 -2
index acfcaadca3b6..b9f4b1849647 100644
@@ -9454,6 +9454,11 @@ static bool is_kfunc_arg_kptr_get(struct bpf_kfunc_call_arg_meta *meta, int arg)
 	return arg == 0 && (meta->kfunc_flags & KF_KPTR_GET);
 }
 
+static bool is_kfunc_throwing(struct bpf_kfunc_call_arg_meta *meta)
+{
+	return meta->kfunc_flags & KF_THROW;
+}
+
 static bool __kfunc_param_match_suffix(const struct btf *btf,
 				       const struct btf_param *arg,
 				       const char *suffix)
@@ -10813,11 +10818,14 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		}
 	}
 
-	if (meta.btf == btf_vmlinux && meta.func_id == special_kfunc_list[KF_bpf_throw]) {
+	if (is_kfunc_throwing(&meta) ||
+	    (meta.btf == btf_vmlinux && meta.func_id == special_kfunc_list[KF_bpf_throw])) {
 		err = mark_chain_throw(env, insn_idx);
 		if (err < 0)
 			return err;
-		return 1;
+		/* Halt exploration only for bpf_throw */
+		if (!is_kfunc_throwing(&meta))
+			return 1;
 	}
 
 	for (i = 0; i < CALLER_SAVED_REGS; i++)
net/bpf/test_run.c +12 -0
index f1652f5fbd2e..31f76ee4218b 100644
@@ -766,6 +766,16 @@ __bpf_kfunc static u32 bpf_kfunc_call_test_static_unused_arg(u32 arg, u32 unused
 	return arg;
 }
 
+__bpf_kfunc notrace void bpf_kfunc_call_test_always_throws(void)
+{
+	bpf_throw();
+}
+
+__bpf_kfunc notrace void bpf_kfunc_call_test_never_throws(void)
+{
+	return;
+}
+
 __diag_pop();
 
 BTF_SET8_START(bpf_test_modify_return_ids)
@@ -806,6 +816,8 @@ BTF_ID_FLAGS(func, bpf_kfunc_call_test_ref, KF_TRUSTED_ARGS | KF_RCU)
 BTF_ID_FLAGS(func, bpf_kfunc_call_test_destructive, KF_DESTRUCTIVE)
 BTF_ID_FLAGS(func, bpf_kfunc_call_test_static_unused_arg)
 BTF_ID_FLAGS(func, bpf_kfunc_call_test_offset)
+BTF_ID_FLAGS(func, bpf_kfunc_call_test_always_throws, KF_THROW)
+BTF_ID_FLAGS(func, bpf_kfunc_call_test_never_throws, KF_THROW)
 BTF_SET8_END(test_sk_check_kfunc_ids)
 
 static void *bpf_test_init(const union bpf_attr *kattr, u32 user_size,
Signature · 1 line
2.40.0
author maintainer
#22 lore raw

RFC PATCH 7/9 bpf: Introduce bpf_set_exception_callback kfunc

In reply to Kumar Kartikeya Dwivedi

This patch allows the BPF program to queue the invocation of a callback after an exception has been thrown and the BPF runtime has completed the unwinding of the program stack. This is the last past point before the program returns control back to the kernel.

In the earlier patches, by default, whenever an exception is thrown, we return 0 to the kernel context. However, this is not always desirable and the program may want to customize the default return code or perform some program specific action when an exception is thrown. This commit sets up the infrastructure to allow this. The semantics and implementation notes are as follows.

- The program may use bpf_set_exception_callback to set up the exception callback only once.
- Since this callback is invoked during unwinding, it cannot throw itself.
- The exception state has been reset before it is invoked, hence any program attachments (fentry/fexit) are allowed as usual. The check to disallow throwing FEXIT for throwing program is relaxed at the level of subprog it is attaching to.
- Exception callbacks are disallowed to call bpf_set_exception_callback.
- bpf_set_exception_callback may not be called in global functions or BPF_PROG_TYPE_EXT (because they propagate exception outwards and do not perform the final exit back to the kernel, which is where the callback call is inserted). This can be supported in the future (by verifying that all paths which throw have the same callback set, and remember this in the global subprog/ext prog summary in func_info_aux, but is skipped for simplicity).
- For a given outermost throwing instruction, it cannot see different exception callbacks from different paths, since it has to hardcode one during the rewrite phase.
- From stack depth check point of view, async and exception callbacks are similar in the sense that they don't contribute to current callchain's stack_depth, but they need to be tested against the main subprog's stack depth and the exception callback's stack depth being within MAX_BPF_STACK. The variable in subprog_info is named to reflect this combined meaning, and appropriate handling is introduced.
- frame->in_exception_callback_fn is used to subject the exception callback to the same return code checks as the BPF program's main exit, so that it can return a meaningful return code based on the program type and is not limited to some fixed callback return range.

---
 include/linux/bpf_verifier.h                  |   6 +-
 kernel/bpf/helpers.c                          |   6 +
 kernel/bpf/verifier.c                         | 184 ++++++++++++++++--
 .../testing/selftests/bpf/bpf_experimental.h  |  11 ++
 4 files changed, 188 insertions(+), 19 deletions(-)
include/linux/bpf_verifier.h +5 -1
index a5346a2b7e68..301318ed04f5 100644
@@ -293,6 +293,7 @@ struct bpf_func_state {
 	bool in_callback_fn;
 	struct tnum callback_ret_range;
 	bool in_async_callback_fn;
+	bool in_exception_callback_fn;
 
 	/* The following fields should be last. See copy_func_state() */
 	int acquired_refs;
@@ -370,6 +371,7 @@ struct bpf_verifier_state {
 	struct bpf_active_lock active_lock;
 	bool speculative;
 	bool active_rcu_lock;
+	s32 exception_callback_subprog;
 
 	/* first and last insn idx of this verifier state */
 	u32 first_insn_idx;
@@ -439,6 +441,7 @@ enum {
 struct bpf_throw_state {
 	int type;
 	bool check_helper_ret_code;
+	s32 subprog;
 };
 
 /* Possible states for alu_state member. */
@@ -549,7 +552,8 @@ struct bpf_subprog_info {
 	bool has_tail_call;
 	bool tail_call_reachable;
 	bool has_ld_abs;
-	bool is_async_cb;
+	bool is_async_or_exception_cb;
+	bool is_exception_cb;
 	bool can_throw;
 };
 
kernel/bpf/helpers.c +6 -0
index 82db3a64fa3f..e6f15da8f154 100644
@@ -2322,6 +2322,11 @@ __bpf_kfunc notrace void bpf_throw(void)
 	current->bpf_exception_thrown[i] = true;
 }
 
+__bpf_kfunc notrace void bpf_set_exception_callback(int (*cb)(void))
+{
+	WARN_ON_ONCE(1);
+}
+
 __diag_pop();
 
 BTF_SET8_START(generic_btf_ids)
@@ -2349,6 +2354,7 @@ BTF_ID_FLAGS(func, bpf_cgroup_from_id, KF_ACQUIRE | KF_RET_NULL)
 #endif
 BTF_ID_FLAGS(func, bpf_task_from_pid, KF_ACQUIRE | KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_throw)
+BTF_ID_FLAGS(func, bpf_set_exception_callback)
 BTF_SET8_END(generic_btf_ids)
 
 static const struct btf_kfunc_id_set generic_kfunc_set = {
kernel/bpf/verifier.c +166 -18

343 lines not on this page · raw message

tools/testing/selftests/bpf/bpf_experimental.h +11 -0
index d5de9251e775..a9c75270e49b 100644
@@ -98,4 +98,15 @@ extern struct bpf_rb_node *bpf_rbtree_first(struct bpf_rb_root *root) __ksym;
  */
 extern void bpf_throw(void) __attribute__((noreturn)) __ksym;
 
+/*
+ * Description
+ *  Set the callback which will be invoked after an exception is thrown and the
+ *  eBPF runtime has completely unwinded the program stack. The return value of
+ *  this callback is treated as the return value of the program when the
+ *  exception is thrown.
+ * Returns
+ *  Void
+ */
+extern void bpf_set_exception_callback(int (*)(void)) __ksym;
+
 #endif
Signature · 1 line
2.40.0
author maintainer
#23 lore raw

RFC PATCH 8/9 bpf: Introduce BPF assertion macros

In reply to Kumar Kartikeya Dwivedi

Implement macros that allow for asserting conditions for with a given register and constant value to prove a condition to the verifier, and safely abort the program in case the condition is not true. The verifier can still perform dead code elimination of the bpf_throw call if it can actually prove the condition based on the seen data flow during path exploration, and the function may not be marked as throwing.

---
 tools/testing/selftests/bpf/bpf_experimental.h | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +17 -0
index a9c75270e49b..aae358a8db4b 100644
@@ -109,4 +109,21 @@ extern void bpf_throw(void) __attribute__((noreturn)) __ksym;
  */
 extern void bpf_set_exception_callback(int (*)(void)) __ksym;
 
+#define __bpf_assert_op(LHS, op, RHS)								   \
+	_Static_assert(sizeof(&(LHS)), "1st argument must be an lvalue expression");		   \
+	_Static_assert(__builtin_constant_p((RHS)), "2nd argument must be a constant expression"); \
+	asm volatile ("if %[lhs] " op " %[rhs] goto +1; call bpf_throw"				   \
+		      : : [lhs] "r"(LHS) , [rhs] "i"(RHS) :)
+
+#define bpf_assert_eq(LHS, RHS) __bpf_assert_op(LHS, "==", RHS)
+#define bpf_assert_ne(LHS, RHS) __bpf_assert_op(LHS, "!=", RHS)
+#define bpf_assert_lt(LHS, RHS) __bpf_assert_op(LHS, "<", RHS)
+#define bpf_assert_gt(LHS, RHS) __bpf_assert_op(LHS, ">", RHS)
+#define bpf_assert_le(LHS, RHS) __bpf_assert_op(LHS, "<=", RHS)
+#define bpf_assert_ge(LHS, RHS) __bpf_assert_op(LHS, ">=", RHS)
+#define bpf_assert_slt(LHS, RHS) __bpf_assert_op(LHS, "s<", RHS)
+#define bpf_assert_sgt(LHS, RHS) __bpf_assert_op(LHS, "s>", RHS)
+#define bpf_assert_sle(LHS, RHS) __bpf_assert_op(LHS, "s<=", RHS)
+#define bpf_assert_sge(LHS, RHS) __bpf_assert_op(LHS, "s>=", RHS)
+
 #endif
Signature · 1 line
2.40.0
author maintainer
#24 lore raw

RFC PATCH 9/9 selftests/bpf: Add tests for BPF exceptions

In reply to Kumar Kartikeya Dwivedi

Add selftests to cover success and failure cases of API usage, runtime behavior and invariants that need to be maintained for implementation correctness.

---
 .../selftests/bpf/prog_tests/exceptions.c     | 240 ++++++++++++++++
 .../testing/selftests/bpf/progs/exceptions.c  | 218 ++++++++++++++
 .../selftests/bpf/progs/exceptions_ext.c      |  42 +++
 .../selftests/bpf/progs/exceptions_fail.c     | 267 ++++++++++++++++++
 4 files changed, 767 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/exceptions.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_ext.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_fail.c
tools/testing/selftests/bpf/prog_tests/exceptions.c new file +240 -0
new file mode 100644
index 000000000000..342f44a12c65
@@ -0,0 +1,240 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+#include <network_helpers.h>
+
+#include "exceptions.skel.h"
+#include "exceptions_ext.skel.h"
+#include "exceptions_fail.skel.h"
+
+static char log_buf[1024 * 1024];
+
+static void test_exceptions_failure(void)
+{
+	RUN_TESTS(exceptions_fail);
+}
+
+static void test_exceptions_success(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, ropts,
+		.data_in = &pkt_v4,
+		.data_size_in = sizeof(pkt_v4),
+		.repeat = 1,
+	);
+	struct exceptions_ext *eskel = NULL;
+	struct exceptions *skel;
+	int ret;
+
+	skel = exceptions__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "exceptions__open_and_load"))
+		return;
+
+#define RUN_SUCCESS(_prog, return_val)						  \
+	ret = bpf_prog_test_run_opts(bpf_program__fd(skel->progs._prog), &ropts); \
+	ASSERT_OK(ret, #_prog " prog run ret");					  \
+	ASSERT_EQ(ropts.retval, return_val, #_prog " prog run retval");
+
+	RUN_SUCCESS(exception_throw_subprog, 16);
+	RUN_SUCCESS(exception_throw, 0);
+	RUN_SUCCESS(exception_throw_gfunc1, 1);
+	RUN_SUCCESS(exception_throw_gfunc2, 0);
+	RUN_SUCCESS(exception_throw_gfunc3, 1);
+	RUN_SUCCESS(exception_throw_gfunc4, 0);
+	RUN_SUCCESS(exception_throw_gfunc5, 1);
+	RUN_SUCCESS(exception_throw_gfunc6, 16);
+	RUN_SUCCESS(exception_throw_func1, 1);
+	RUN_SUCCESS(exception_throw_func2, 0);
+	RUN_SUCCESS(exception_throw_func3, 1);
+	RUN_SUCCESS(exception_throw_func4, 0);
+	RUN_SUCCESS(exception_throw_func5, 1);
+	RUN_SUCCESS(exception_throw_func6, 16);
+	RUN_SUCCESS(exception_throw_cb1, 0);
+	RUN_SUCCESS(exception_throw_cb2, 16);
+	RUN_SUCCESS(exception_throw_cb_diff, 16);
+	RUN_SUCCESS(exception_throw_kfunc1, 0);
+	RUN_SUCCESS(exception_throw_kfunc2, 1);
+
+#define RUN_EXT(load_ret, attach_err, expr, msg)				  \
+	{									  \
+		LIBBPF_OPTS(bpf_object_open_opts, o, .kernel_log_buf = log_buf,		 \
+						     .kernel_log_size = sizeof(log_buf), \
+						     .kernel_log_level = 2);		 \
+		exceptions_ext__destroy(eskel);					  \
+		eskel = exceptions_ext__open_opts(&o);				  \
+		struct bpf_program *prog = NULL;				  \
+		struct bpf_link *link = NULL;					  \
+		if (!ASSERT_OK_PTR(eskel, "exceptions_ext__open"))		  \
+			goto done;						  \
+		(expr);								  \
+		ASSERT_OK_PTR(bpf_program__name(prog), bpf_program__name(prog));  \
+		if (!ASSERT_EQ(exceptions_ext__load(eskel), load_ret,		  \
+			       "exceptions_ext__load"))	{			  \
+			printf("%s\n", log_buf);				  \
+			goto done;						  \
+		}								  \
+		if (load_ret != 0) {						  \
+			printf("%s\n", log_buf);				  \
+			if (!ASSERT_OK_PTR(strstr(log_buf, msg), "strstr"))	  \
+				goto done;					  \
+		}								  \
+		if (!load_ret && attach_err) {					  \
+			if (!ASSERT_ERR_PTR(link = bpf_program__attach(prog), "attach err")) \
+				goto done;					  \
+		} else if (!load_ret) {						  \
+			if (!ASSERT_OK_PTR(link = bpf_program__attach(prog), "attach ok"))  \
+				goto done;					  \
+			bpf_link__destroy(link);				  \
+		}								  \
+	}
+
+	/* non-throwing fexit -> non-throwing subprog : OK */
+	RUN_EXT(0, false, ({
+		prog = eskel->progs.pfexit;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* throwing fexit -> non-throwing subprog : BAD */
+	RUN_EXT(0, true, ({
+		prog = eskel->progs.throwing_fexit;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* non-throwing fexit -> throwing subprog : OK */
+	RUN_EXT(0, false, ({
+		prog = eskel->progs.pfexit;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "throwing_subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* throwing fexit -> throwing subprog : BAD */
+	RUN_EXT(0, true, ({
+		prog = eskel->progs.throwing_fexit;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "throwing_subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* fmod_ret not allowed for subprog - Check so we remember to handle its
+	 * throwing specification compatibility with target when supported.
+	 */
+	RUN_EXT(-EINVAL, false, ({
+		prog = eskel->progs.pfmod_ret;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "subprog"), "set_attach_target"))
+			goto done;
+	}), "can't modify return codes of BPF program");
+
+	/* fmod_ret not allowed for global subprog - Check so we remember to
+	 * handle its throwing specification compatibility with target when
+	 * supported.
+	 */
+	RUN_EXT(-EINVAL, false, ({
+		prog = eskel->progs.pfmod_ret;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "global_subprog"), "set_attach_target"))
+			goto done;
+	}), "can't modify return codes of BPF program");
+
+	/* non-throwing extension -> non-throwing subprog : BAD (!global)
+	 * We need to handle and reject it for static subprogs when supported
+	 * when extension is throwing as not all callsites are marked to handle
+	 * them.
+	 */
+	RUN_EXT(-EINVAL, true, ({
+		prog = eskel->progs.extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "subprog"), "set_attach_target"))
+			goto done;
+	}), "subprog() is not a global function");
+
+	/* non-throwing extension -> throwing subprog : BAD (!global)
+	 * We need to handle and reject it for static subprogs when supported
+	 * when extension is throwing as not all callsites are marked to handle
+	 * them.
+	 */
+	RUN_EXT(-EINVAL, true, ({
+		prog = eskel->progs.extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "throwing_subprog"), "set_attach_target"))
+			goto done;
+	}), "throwing_subprog() is not a global function");
+
+	/* non-throwing extension -> non-throwing global subprog : OK */
+	RUN_EXT(0, false, ({
+		prog = eskel->progs.extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "global_subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* non-throwing extension -> throwing global subprog : OK */
+	RUN_EXT(0, false, ({
+		prog = eskel->progs.extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "throwing_global_subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* throwing extension -> throwing global subprog : OK */
+	RUN_EXT(0, false, ({
+		prog = eskel->progs.throwing_extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "throwing_global_subprog"), "set_attach_target"))
+			goto done;
+	}), "");
+
+	/* throwing extension -> main subprog : BAD (OUTER vs INNER mismatch) */
+	RUN_EXT(-EINVAL, false, ({
+		prog = eskel->progs.throwing_extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "exception_throw_subprog"), "set_attach_target"))
+			goto done;
+	}), "Cannot attach throwing extension to main subprog");
+
+	/* throwing extension -> non-throwing global subprog : BAD */
+	RUN_EXT(-EINVAL, false, ({
+		prog = eskel->progs.throwing_extension;
+		bpf_program__set_autoload(prog, true);
+		if (!ASSERT_OK(bpf_program__set_attach_target(prog,
+			       bpf_program__fd(skel->progs.exception_throw_subprog),
+			       "global_subprog"), "set_attach_target"))
+			goto done;
+	}), "Cannot attach throwing extension to non-throwing subprog");
+done:
+	exceptions_ext__destroy(eskel);
+	exceptions__destroy(skel);
+}
+
+void test_exceptions(void)
+{
+	test_exceptions_failure();
+	test_exceptions_success();
+}
tools/testing/selftests/bpf/progs/exceptions.c new file +218 -0

218 lines not on this page · raw message

tools/testing/selftests/bpf/progs/exceptions_ext.c new file +42 -0

42 lines not on this page · raw message

tools/testing/selftests/bpf/progs/exceptions_fail.c new file +267 -0

267 lines not on this page · raw message

Signature · 1 line
2.40.0
#25 lore raw

Re: [PATCH RFC bpf-next v1 9/9] selftests/bpf: Add tests for BPF exceptions

Quoted 42 lines · Kumar Kartikeya Dwivedi
tools/testing/selftests/bpf/progs/exceptions.c new file +42 -0
+static __noinline int throwing_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+__noinline int global_subprog(struct __sk_buff *ctx)
+{
+	return subprog(ctx) + 1;
+}
+
+__noinline int throwing_global_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+static __noinline int exception_cb(void)
+{
+	return 16;
+}
+
+SEC("tc")
+int exception_throw_subprog(struct __sk_buff *ctx)
+{
+	volatile int i;
+
+	exception_cb();
+	bpf_set_exception_callback(exception_cb);
+	i = subprog(ctx);
+	i += global_subprog(ctx) - 1;
+	if (!i)
+		return throwing_global_subprog(ctx);
+	else
+		return throwing_subprog(ctx);
+	bpf_throw();
+	return 0;
+}
+
+__noinline int throwing_gfunc(volatile int i)

tools/testing/selftests/bpf/progs/exceptions.c line 74

Quoted 10 lines
tools/testing/selftests/bpf/progs/exceptions.c new file +10 -0
+{
+	bpf_assert_eq(i, 0);
+	return 1;
+}
+
+__noinline static int throwing_func(volatile int i)
+{
+	bpf_assert_lt(i, 1);
+	return 1;
+}

exception_cb() has no way of knowning which assert statement threw the exception. How about extending a macro:
bpf_assert_eq(i, 0, MY_INT_ERR);
or
bpf_assert_eq(i, 0) {bpf_throw(MY_INT_ERR);}

bpf_throw can store it in prog->aux->exception pass the address to cb.

Also I think we shouldn't complicate the verifier with auto release of resources. If the user really wants to assert when spin_lock is held it should be user's job to specify what resources should be released.
Can we make it look like:

bpf_spin_lock(&lock);
bpf_assert_eq(i, 0) {
bpf_spin_unlock(&lock);
bpf_throw(MY_INT_ERR);
}

author maintainer
#26 lore raw

Re: [PATCH RFC bpf-next v1 9/9] selftests/bpf: Add tests for BPF exceptions

Quoted 60 lines · Alexei Starovoitov
Quoted 42 lines · Kumar Kartikeya Dwivedi
tools/testing/selftests/bpf/progs/exceptions.c new file +42 -0
+static __noinline int throwing_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+__noinline int global_subprog(struct __sk_buff *ctx)
+{
+	return subprog(ctx) + 1;
+}
+
+__noinline int throwing_global_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+static __noinline int exception_cb(void)
+{
+	return 16;
+}
+
+SEC("tc")
+int exception_throw_subprog(struct __sk_buff *ctx)
+{
+	volatile int i;
+
+	exception_cb();
+	bpf_set_exception_callback(exception_cb);
+	i = subprog(ctx);
+	i += global_subprog(ctx) - 1;
+	if (!i)
+		return throwing_global_subprog(ctx);
+	else
+		return throwing_subprog(ctx);
+	bpf_throw();
+	return 0;
+}
+
+__noinline int throwing_gfunc(volatile int i)

tools/testing/selftests/bpf/progs/exceptions.c line 74

Quoted 10 lines
tools/testing/selftests/bpf/progs/exceptions.c new file +10 -0
+{
+	bpf_assert_eq(i, 0);
+	return 1;
+}
+
+__noinline static int throwing_func(volatile int i)
+{
+	bpf_assert_lt(i, 1);
+	return 1;
+}

exception_cb() has no way of knowning which assert statement threw the exception. How about extending a macro:
bpf_assert_eq(i, 0, MY_INT_ERR);
or
bpf_assert_eq(i, 0) {bpf_throw(MY_INT_ERR);}

Quoted 2 lines

bpf_throw can store it in prog->aux->exception pass the address to cb.

I agree and will add passing of a value that gets passed to the callback (probably just set it in the exception state), but I don't think prog->aux will work, see previous mails.

Quoted 10 lines

Also I think we shouldn't complicate the verifier with auto release of resources. If the user really wants to assert when spin_lock is held it should be user's job to specify what resources should be released.
Can we make it look like:

bpf_spin_lock(&lock);
bpf_assert_eq(i, 0) {
bpf_spin_unlock(&lock);
bpf_throw(MY_INT_ERR);
}

Do you mean just locks or all resources? Then it kind of undermines the point of having something like bpf_throw IMO. Since it's easy to insert code from the point of throw but it's not possible to do the same in callers (unless we add a way to 'catch' throws), so it only works for some particular cases where callers don't hold references (or in the main subprog).

There are also other ways to go about this whole thing, like having the compiler emit calls to instrinsics which the BPF runtime provides (or have the call configurable through compiler switches), and it already emits the landing pad code to release stuff and we simply receive the table of pads indexed by each throwing instruction, perform necessary checks to ensure everything is actually released correctly when control flow goes through them (e.g. when exploring multiple paths through the same instruction), and unwind frame by frame. That reduces the burden on both the verifier and user, but then it would be probably need to be BPF C++, or have to be a new language extension for BPF C. E.g. there was something about defer, panic, recover etc. in wg14
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2542.pdf . Having the compiler do it is also probably easier if we want 'catch' style handlers.

#27 lore raw

Re: [PATCH RFC bpf-next v1 9/9] selftests/bpf: Add tests for BPF exceptions

Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 60 lines · Alexei Starovoitov
Quoted 42 lines · Kumar Kartikeya Dwivedi
tools/testing/selftests/bpf/progs/exceptions.c new file +42 -0
+static __noinline int throwing_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+__noinline int global_subprog(struct __sk_buff *ctx)
+{
+	return subprog(ctx) + 1;
+}
+
+__noinline int throwing_global_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+static __noinline int exception_cb(void)
+{
+	return 16;
+}
+
+SEC("tc")
+int exception_throw_subprog(struct __sk_buff *ctx)
+{
+	volatile int i;
+
+	exception_cb();
+	bpf_set_exception_callback(exception_cb);
+	i = subprog(ctx);
+	i += global_subprog(ctx) - 1;
+	if (!i)
+		return throwing_global_subprog(ctx);
+	else
+		return throwing_subprog(ctx);
+	bpf_throw();
+	return 0;
+}
+
+__noinline int throwing_gfunc(volatile int i)

tools/testing/selftests/bpf/progs/exceptions.c line 74

Quoted 10 lines
tools/testing/selftests/bpf/progs/exceptions.c new file +10 -0
+{
+	bpf_assert_eq(i, 0);
+	return 1;
+}
+
+__noinline static int throwing_func(volatile int i)
+{
+	bpf_assert_lt(i, 1);
+	return 1;
+}

exception_cb() has no way of knowning which assert statement threw the exception. How about extending a macro:
bpf_assert_eq(i, 0, MY_INT_ERR);
or
bpf_assert_eq(i, 0) {bpf_throw(MY_INT_ERR);}

Quoted 2 lines

bpf_throw can store it in prog->aux->exception pass the address to cb.

I agree and will add passing of a value that gets passed to the callback (probably just set it in the exception state), but I don't think prog->aux will work, see previous mails.

Quoted 10 lines

Also I think we shouldn't complicate the verifier with auto release of resources. If the user really wants to assert when spin_lock is held it should be user's job to specify what resources should be released.
Can we make it look like:

bpf_spin_lock(&lock);
bpf_assert_eq(i, 0) {
bpf_spin_unlock(&lock);
bpf_throw(MY_INT_ERR);
}

Quoted 5 lines

Do you mean just locks or all resources? Then it kind of undermines the point of having something like bpf_throw IMO. Since it's easy to insert code from the point of throw but it's not possible to do the same in callers (unless we add a way to 'catch' throws), so it only works for some particular cases where callers don't hold references (or in the main subprog).

That's a good point. This approach will force caller of functions that can throw not hold any referenced objects (spin_locks, sk_lookup, obj_new, etc) That indeed might be too restrictive.
It would be great if we could come up with a way for bpf prog to release resources explicitly though. I'm not a fan of magic release of spin locks.

Quoted 4 lines

There are also other ways to go about this whole thing, like having the compiler emit calls to instrinsics which the BPF runtime provides (or have the call configurable through compiler switches), and it already emits the landing pad code to release stuff and we simply receive the table of pads indexed by each

Quoted 8 lines

throwing instruction, perform necessary checks to ensure everything is actually released correctly when control flow goes through them (e.g. when exploring multiple paths through the same instruction), and unwind frame by frame. That reduces the burden on both the verifier and user, but then it would be probably need to be BPF C++, or have to be a new language extension for BPF C. E.g. there was something about defer, panic, recover etc. in wg14
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2542.pdf . Having the compiler do it is also probably easier if we want 'catch' style handlers.

Interesting idea. __attribute__((cleanup(..))) may be handy, but that's a ton of work. I'm in a camp of developers who enforce -fno-exceptions in C++ projects. bpf_assert is not analogous to C++ exceptions. It shouldn't be seen a mechanism to simplify control flow and error handling.

author maintainer
#28 lore raw

Re: [PATCH RFC bpf-next v1 9/9] selftests/bpf: Add tests for BPF exceptions

Quoted 86 lines · Alexei Starovoitov
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 60 lines · Alexei Starovoitov
Quoted 42 lines · Kumar Kartikeya Dwivedi
tools/testing/selftests/bpf/progs/exceptions.c new file +42 -0
+static __noinline int throwing_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+__noinline int global_subprog(struct __sk_buff *ctx)
+{
+	return subprog(ctx) + 1;
+}
+
+__noinline int throwing_global_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+static __noinline int exception_cb(void)
+{
+	return 16;
+}
+
+SEC("tc")
+int exception_throw_subprog(struct __sk_buff *ctx)
+{
+	volatile int i;
+
+	exception_cb();
+	bpf_set_exception_callback(exception_cb);
+	i = subprog(ctx);
+	i += global_subprog(ctx) - 1;
+	if (!i)
+		return throwing_global_subprog(ctx);
+	else
+		return throwing_subprog(ctx);
+	bpf_throw();
+	return 0;
+}
+
+__noinline int throwing_gfunc(volatile int i)

tools/testing/selftests/bpf/progs/exceptions.c line 74

Quoted 10 lines
tools/testing/selftests/bpf/progs/exceptions.c new file +10 -0
+{
+	bpf_assert_eq(i, 0);
+	return 1;
+}
+
+__noinline static int throwing_func(volatile int i)
+{
+	bpf_assert_lt(i, 1);
+	return 1;
+}

exception_cb() has no way of knowning which assert statement threw the exception. How about extending a macro:
bpf_assert_eq(i, 0, MY_INT_ERR);
or
bpf_assert_eq(i, 0) {bpf_throw(MY_INT_ERR);}

Quoted 2 lines

bpf_throw can store it in prog->aux->exception pass the address to cb.

I agree and will add passing of a value that gets passed to the callback (probably just set it in the exception state), but I don't think prog->aux will work, see previous mails.

Quoted 10 lines

Also I think we shouldn't complicate the verifier with auto release of resources. If the user really wants to assert when spin_lock is held it should be user's job to specify what resources should be released.
Can we make it look like:

bpf_spin_lock(&lock);
bpf_assert_eq(i, 0) {
bpf_spin_unlock(&lock);
bpf_throw(MY_INT_ERR);
}

Quoted 5 lines

Do you mean just locks or all resources? Then it kind of undermines the point of having something like bpf_throw IMO. Since it's easy to insert code from the point of throw but it's not possible to do the same in callers (unless we add a way to 'catch' throws), so it only works for some particular cases where callers don't hold references (or in the main subprog).

Quoted 6 lines

That's a good point. This approach will force caller of functions that can throw not hold any referenced objects (spin_locks, sk_lookup, obj_new, etc) That indeed might be too restrictive.
It would be great if we could come up with a way for bpf prog to release resources explicitly though. I'm not a fan of magic release of spin locks.

I think to realize that, we need a way to 'catch' thrown exceptions in the caller. The user will write a block of code that handles release of resources in the current scope and resume unwinding (implicitly by calling into some intrinsics). When we discussed this earlier, you rightly mentioned problems associated with introducing control flow into the program not seen by the compiler (unlike try/catch in something like C++ which has clear semantics).

But to take a step back, and about what you've said below:

Quoted 2 lines

bpf_assert is not analogous to C++ exceptions. It shouldn't be seen a mechanism to simplify control flow and error handling.

When programs get explicit control and handle the 'exceptional' condition, it begins to mimic more of an alternative 'slow path' of the program when it encounters an error, and starts resembling an alternative error handling mechanism pretty much like C++ exceptions.

I think that was not the goal here, and the automatic release of resources is simply supposed to happen to ensure that the kernel's resource safety is not violated when a program is aborting. An assertion's should never occur at runtime 99.9999% of the time, but when it does, the BPF runtime emits code to ensure that the aborting program does not leave the kernel in an inconsistent state (memory leaks, held locks that other programs can never take again, etc.).

So this will involve clean up of every resource it had acquired when it threw. If we cannot ensure that we can safely release resources (e.g. throwing in NMI context where a kptr_xchg'd pointer cannot be freed), we will bail during verification.

Quoted 17 lines
Quoted 4 lines

There are also other ways to go about this whole thing, like having the compiler emit calls to instrinsics which the BPF runtime provides (or have the call configurable through compiler switches), and it already emits the landing pad code to release stuff and we simply receive the table of pads indexed by each

Quoted 8 lines

throwing instruction, perform necessary checks to ensure everything is actually released correctly when control flow goes through them (e.g. when exploring multiple paths through the same instruction), and unwind frame by frame. That reduces the burden on both the verifier and user, but then it would be probably need to be BPF C++, or have to be a new language extension for BPF C. E.g. there was something about defer, panic, recover etc. in wg14
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2542.pdf . Having the compiler do it is also probably easier if we want 'catch' style handlers.

Interesting idea. __attribute__((cleanup(..))) may be handy, but that's a ton of work. I'm in a camp of developers who enforce -fno-exceptions in C++ projects. bpf_assert is not analogous to C++ exceptions. It shouldn't be seen a mechanism to simplify control flow and error handling.

#29 lore raw

Re: [PATCH RFC bpf-next v1 9/9] selftests/bpf: Add tests for BPF exceptions

Quoted 94 lines · Kumar Kartikeya Dwivedi
Quoted 86 lines · Alexei Starovoitov
Quoted 79 lines · Kumar Kartikeya Dwivedi
Quoted 60 lines · Alexei Starovoitov
Quoted 42 lines · Kumar Kartikeya Dwivedi
tools/testing/selftests/bpf/progs/exceptions.c new file +42 -0
+static __noinline int throwing_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+__noinline int global_subprog(struct __sk_buff *ctx)
+{
+	return subprog(ctx) + 1;
+}
+
+__noinline int throwing_global_subprog(struct __sk_buff *ctx)
+{
+	if (ctx)
+		bpf_throw();
+	return 0;
+}
+
+static __noinline int exception_cb(void)
+{
+	return 16;
+}
+
+SEC("tc")
+int exception_throw_subprog(struct __sk_buff *ctx)
+{
+	volatile int i;
+
+	exception_cb();
+	bpf_set_exception_callback(exception_cb);
+	i = subprog(ctx);
+	i += global_subprog(ctx) - 1;
+	if (!i)
+		return throwing_global_subprog(ctx);
+	else
+		return throwing_subprog(ctx);
+	bpf_throw();
+	return 0;
+}
+
+__noinline int throwing_gfunc(volatile int i)

tools/testing/selftests/bpf/progs/exceptions.c line 74

Quoted 10 lines
tools/testing/selftests/bpf/progs/exceptions.c new file +10 -0
+{
+	bpf_assert_eq(i, 0);
+	return 1;
+}
+
+__noinline static int throwing_func(volatile int i)
+{
+	bpf_assert_lt(i, 1);
+	return 1;
+}

exception_cb() has no way of knowning which assert statement threw the exception. How about extending a macro:
bpf_assert_eq(i, 0, MY_INT_ERR);
or
bpf_assert_eq(i, 0) {bpf_throw(MY_INT_ERR);}

Quoted 2 lines

bpf_throw can store it in prog->aux->exception pass the address to cb.

I agree and will add passing of a value that gets passed to the callback (probably just set it in the exception state), but I don't think prog->aux will work, see previous mails.

Quoted 10 lines

Also I think we shouldn't complicate the verifier with auto release of resources. If the user really wants to assert when spin_lock is held it should be user's job to specify what resources should be released.
Can we make it look like:

bpf_spin_lock(&lock);
bpf_assert_eq(i, 0) {
bpf_spin_unlock(&lock);
bpf_throw(MY_INT_ERR);
}

Quoted 5 lines

Do you mean just locks or all resources? Then it kind of undermines the point of having something like bpf_throw IMO. Since it's easy to insert code from the point of throw but it's not possible to do the same in callers (unless we add a way to 'catch' throws), so it only works for some particular cases where callers don't hold references (or in the main subprog).

Quoted 6 lines

That's a good point. This approach will force caller of functions that can throw not hold any referenced objects (spin_locks, sk_lookup, obj_new, etc) That indeed might be too restrictive.
It would be great if we could come up with a way for bpf prog to release resources explicitly though. I'm not a fan of magic release of spin locks.

Quoted 4 lines

I think to realize that, we need a way to 'catch' thrown exceptions in the caller. The user will write a block of code that handles release of resources in the current scope and resume unwinding (implicitly by calling into some intrinsics).

or we simply don't allow calling subprogs that can throw while holding resources.

Quoted 21 lines

When we discussed this earlier, you rightly mentioned problems associated with introducing control flow into the program not seen by the compiler (unlike try/catch in something like C++ which has clear semantics).

But to take a step back, and about what you've said below:

Quoted 2 lines

bpf_assert is not analogous to C++ exceptions. It shouldn't be seen a mechanism to simplify control flow and error handling.

When programs get explicit control and handle the 'exceptional' condition, it begins to mimic more of an alternative 'slow path' of the program when it encounters an error, and starts resembling an alternative error handling mechanism pretty much like C++ exceptions.

I think that was not the goal here, and the automatic release of resources is simply supposed to happen to ensure that the kernel's resource safety is not violated when a program is aborting. An assertion's should never occur at runtime 99.9999% of the time, but when it does, the BPF runtime emits code to ensure that the aborting program does not leave the kernel in an inconsistent state (memory leaks, held locks that other programs can never take again, etc.).

Quoted 4 lines

So this will involve clean up of every resource it had acquired when it threw. If we cannot ensure that we can safely release resources (e.g. throwing in NMI context where a kptr_xchg'd pointer cannot be freed), we will bail during verification.

exactly. +1 to all of the above. the progs shouldn't be paying run-time cost for this 0.0001% case.