| Message ID | 20230713023232.1411523-1-memxor@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Exceptions - 1/2 | expand |
On Thu, Jul 13, 2023 at 08:02:22AM +0530, Kumar Kartikeya Dwivedi wrote: > This series implements the _first_ part of the runtime and verifier > support needed to enable BPF exceptions. Exceptions thrown from programs > are processed as an immediate exit from the program, which unwinds all > the active stack frames until the main stack frame, and returns to the > BPF program's caller. The ability to perform this unwinding safely > allows the program to test conditions that are always true at runtime > but which the verifier has no visibility into. > > Thus, it also reduces verification effort by safely terminating > redundant paths that can be taken within a program. > > The patches to perform runtime resource cleanup during the > frame-by-frame unwinding will be posted as a follow-up to this set. > > It must be noted that exceptions are not an error handling mechanism for > unlikely runtime conditions, but a way to safely terminate the execution > of a program in presence of conditions that should never occur at > runtime. They are meant to serve higher-level primitives such as program > assertions. Sure, that makes sense. > > As such, a program can only install an exception handler once for the > lifetime of a BPF program, and this handler cannot be changed at > runtime. The purpose of the handler is to simply interpret the cookie > value supplied by the bpf_throw call, and execute user-defined logic > corresponding to it. The primary purpose of allowing a handler is to > control the return value of the program. The default handler returns 0 > when from the program when an exception is thrown. > > Fixing the handler for the lifetime of the program eliminates tricky and > expensive handling in case of runtime changes of the handler callback > when programs begin to nest, where it becomes more complex to save and > restore the active handler at runtime. > > The following kfuncs are introduced: > > // Throw a BPF exception, terminating the execution of the program. > // > // @cookie: The cookie that is passed to the exception callback. Without > // an exception callback set by the user, the programs returns > // 0 when an exception is thrown. > void bpf_throw(u64 cookie); If developers are only supposed to use higher level primitives, then why expose a kfunc for it? The above description makes it sound like this should be an implementation detail. [...] Thanks, Daniel
On Mon, 17 Jul 2023 at 23:46, Daniel Xu <dxu@dxuuu.xyz> wrote: > > On Thu, Jul 13, 2023 at 08:02:22AM +0530, Kumar Kartikeya Dwivedi wrote: > > This series implements the _first_ part of the runtime and verifier > > support needed to enable BPF exceptions. Exceptions thrown from programs > > are processed as an immediate exit from the program, which unwinds all > > the active stack frames until the main stack frame, and returns to the > > BPF program's caller. The ability to perform this unwinding safely > > allows the program to test conditions that are always true at runtime > > but which the verifier has no visibility into. > > > > Thus, it also reduces verification effort by safely terminating > > redundant paths that can be taken within a program. > > > > The patches to perform runtime resource cleanup during the > > frame-by-frame unwinding will be posted as a follow-up to this set. > > > > It must be noted that exceptions are not an error handling mechanism for > > unlikely runtime conditions, but a way to safely terminate the execution > > of a program in presence of conditions that should never occur at > > runtime. They are meant to serve higher-level primitives such as program > > assertions. > > Sure, that makes sense. > > > > > As such, a program can only install an exception handler once for the > > lifetime of a BPF program, and this handler cannot be changed at > > runtime. The purpose of the handler is to simply interpret the cookie > > value supplied by the bpf_throw call, and execute user-defined logic > > corresponding to it. The primary purpose of allowing a handler is to > > control the return value of the program. The default handler returns 0 > > when from the program when an exception is thrown. > > > > Fixing the handler for the lifetime of the program eliminates tricky and > > expensive handling in case of runtime changes of the handler callback > > when programs begin to nest, where it becomes more complex to save and > > restore the active handler at runtime. > > > > The following kfuncs are introduced: > > > > // Throw a BPF exception, terminating the execution of the program. > > // > > // @cookie: The cookie that is passed to the exception callback. Without > > // an exception callback set by the user, the programs returns > > // 0 when an exception is thrown. > > void bpf_throw(u64 cookie); > > If developers are only supposed to use higher level primitives, then why > expose a kfunc for it? The above description makes it sound like this > should be an implementation detail. > I can rephrase, but what I meant to say is that it's not an error handling mechanism. But you _can_ directly call bpf_throw as well when failing a condition that you know is always true. It's not necessary to always use the assert macros. That may not be possible as it requires a lvalue, rvalue pair. If the condition is complicated, e.g. the one below, is totally acceptable, if you know it's always going to be true, but the verifier doesn't: if (data + offset > data_end) bpf_throw(XDP_DROP); This can be from a deeply nested callchain, and it eliminates the need to handle this condition all the way back to the main prog. The primary requirement was for implementing assertions within a program, which when untrue still ensure that the program terminates safely. Typically this would require the user to handle the other case, freeing any resources, and returning from a possibly deep callchain back to the kernel. Testing a condition can be used to update the verifier's knowledge about a particular register. By throwing from the other path where the condition is untrue, it's a way to increase the knowledge of the verifier during its symbolic execution while at the same time preserving the safety guarantees.
This series implements the _first_ part of the runtime and verifier support needed to enable BPF exceptions. Exceptions thrown from programs are processed as an immediate exit from the program, which unwinds all the active stack frames until the main stack frame, and returns to the BPF program's caller. The ability to perform this unwinding safely allows the program to test conditions that are always true at runtime but which the verifier has no visibility into. Thus, it also reduces verification effort by safely terminating redundant paths that can be taken within a program. The patches to perform runtime resource cleanup during the frame-by-frame unwinding will be posted as a follow-up to this set. It must be noted that exceptions are not an error handling mechanism for unlikely runtime conditions, but a way to safely terminate the execution of a program in presence of conditions that should never occur at runtime. They are meant to serve higher-level primitives such as program assertions. As such, a program can only install an exception handler once for the lifetime of a BPF program, and this handler cannot be changed at runtime. The purpose of the handler is to simply interpret the cookie value supplied by the bpf_throw call, and execute user-defined logic corresponding to it. The primary purpose of allowing a handler is to control the return value of the program. The default handler returns 0 when from the program when an exception is thrown. Fixing the handler for the lifetime of the program eliminates tricky and expensive handling in case of runtime changes of the handler callback when programs begin to nest, where it becomes more complex to save and restore the active handler at runtime. The following kfuncs are introduced: // Throw a BPF exception, terminating the execution of the program. // // @cookie: The cookie that is passed to the exception callback. Without // an exception callback set by the user, the programs returns // 0 when an exception is thrown. void bpf_throw(u64 cookie); // Set an exception handler globally for the entire program. The handler // is invoked after the unwinding of the stack is finished. The return // value of the handler will be the return value of the program. By // default, without a supplied exception handler, the return value is 0. // // Note that this helper is *idempotent*, and can only be called once in // a program. The exception callback is then set permanently for the // lifetime of the BPF program, and cannot be changed. // // @cb: The exception callback, which receives the cookie paramter // passed to the bpf_throw call which invoked a BPF exception. void bpf_set_exception_callback(int (*cb)(u64 cookie)); This version of offline unwinding based BPF exceptions is truly zero overhead, with the exception of generation of a default callback which contains a few instructions to return a default return value (0) when no exception callback is supplied by the user. A limitation currently exists where all callee-saved registers have to be saved on entry into the main BPF subprog. This will be fixed with a follow-up or in the next revision. Callbacks are disallowed from throwing BPF exceptions for now, since such exceptions need to cross the callback helper boundary (and therefore must care about unwinding kernel state), however it is possible to lift this restriction in the future follow-up. Exceptions terminate propogating at program boundaries, hence both BPF_PROG_TYPE_EXT and tail call targets return to their caller context the return value of the exception callback, in the event that they throw an exception. Thus, exceptions do not cross extension or tail call boundary. However, this is mostly an implementation choice, and can be changed to suit more user-friendly semantics. PS: Patches 2 and 3 have been sent as [0] but are included to allow CI to build the set. [0]: https://lore.kernel.org/bpf/20230713003118.1327943-1-memxor@gmail.com Notes ----- A couple of questions to consider: * Should the default callback simply return the cookie value supplied to bpf_throw? * Should exceptions cross tail call and extension program boundaries? Currently they invoke the exception callback of tail call or extension program (if installed) and return to the caller, aborting propagation. * How should the assertion macros interface look like? It would be great to have more feedback from potential users (David?). A few notes: * I'm working to address the callee-saved register spilling issue on entry into the main subprog as a follow-up. I wanted to send the current version out first. * The resource cleanup patches are based on top of this set, so once we converge on the implementation, they can either be appended to the set or sent as a follow up (whichever occurs first). Known issues ------------ * There is currently a splat when KASAN is enabled, which I believe to be a false positive occuring due to bad interplay between KASAN's stack memory accounting logic and my unwinding logic. I'm investigating it. * 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. Changelog: ---------- RFC v1 -> v1 RFC v1: https://lore.kernel.org/bpf/20230405004239.1375399-1-memxor@gmail.com * Completely rework the unwinding infrastructure to use offline unwinding support. * Remove the runtime exception state and program rewriting code. * Make bpf_set_exception_callback idempotent to avoid vexing synchronization and state clobbering issues in presence of program nesting. * Disable bpf_throw within callback functions, for now. * Allow bpf_throw in tail call programs and extension programs, removing limitations of rewrite based unwinding. * Expand selftests. Kumar Kartikeya Dwivedi (10): bpf: Fix kfunc callback register type handling bpf: Fix subprog idx logic in check_max_stack_depth bpf: Repeat check_max_stack_depth for async callbacks bpf: Add support for inserting new subprogs arch/x86: Implement arch_bpf_stack_walk bpf: Implement bpf_throw kfunc bpf: Ensure IP is within prog->jited_length for bpf_throw calls bpf: Introduce bpf_set_exception_callback selftests/bpf: Add BPF assertion macros selftests/bpf: Add tests for BPF exceptions arch/x86/net/bpf_jit_comp.c | 105 +++- include/linux/bpf.h | 6 + include/linux/bpf_verifier.h | 9 +- include/linux/filter.h | 8 + kernel/bpf/core.c | 15 +- kernel/bpf/helpers.c | 44 ++ kernel/bpf/syscall.c | 19 +- kernel/bpf/verifier.c | 284 +++++++++-- .../testing/selftests/bpf/bpf_experimental.h | 28 ++ .../selftests/bpf/prog_tests/exceptions.c | 272 +++++++++++ .../testing/selftests/bpf/progs/exceptions.c | 450 ++++++++++++++++++ .../selftests/bpf/progs/exceptions_ext.c | 42 ++ .../selftests/bpf/progs/exceptions_fail.c | 311 ++++++++++++ 13 files changed, 1537 insertions(+), 56 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: 0a5550b1165cd60ad6972791eda4a3eb7e347280