From: Raj <rjsu26@xxxxxxxxx> Motivation: We propose an enhancement to the BPF infrastructure to address the critical issue of long-running BPF programs [1,2,3,4]. While the verifier ensures termination by restricting instruction count and backward edges, the total execution time of BPF programs is not bounded. Certain helper functions and iterators can result in extended runtimes, affecting system performance. The existing BPF infrastructure verifies that programs will not indefinitely loop or leak resources. However, helper functions such as `bpf_loop`, `bpf_for_each_map_elem`, and other iterative or expensive kernel interactions can cause runtimes that significantly degrade system performance [6]. Current detaching mechanisms do not immediately terminate running instances, monopolizing CPU. Therefore, a termination solution is necessary to swiftly terminate execution while safely releasing resources. Existing termination approach like the BPF Exception or Runtime hooks [5] have the issue of either lack of dynamism or having runtime overheads: BPF Exceptions: Introduces bpf_throw() and exception callbacks, requiring stack unwinding and exception state management. Cleanup can only be done for pre-defined cancellation points. Runtime Hooks: Proposes watchdog timers, which requires resource tracking, though minimal but non-zero runtime overheads. Design: We introduce the Fast-Path termination mechanism, leveraging the verifier's guarantees regarding control flow and resource management. The approach dynamically patches running BPF programs with a stripped-down version that accelerates termination. This can be used to terminate any given instance of a BPF execution. Key elements include: - Implicit Lifetime Management: Utilizing the verifier’s inherent control flow and resource cleanup paths encoded within the BPF program structure, eliminating the need for explicit garbage collection or unwinding tables. - Dynamic Program Patching: At runtime, BPF programs are atomically patched, replacing expensive helper calls with stubbed versions (fast fall-through implementations). This ensures swift termination without compromising safety or leaking resources. - Helper Function Adjustments: Certain helper functions (e.g., `bpf_loop`, `bpf_for_each_map_elem`) include mechanisms to facilitate early exits through modified return values. TODOs: - Termination support for nested BPF programs. - Policy enforcements to control runtime of BPF programs in a system: - Timer based termination (watchdog) - Userspace management to detect low-performing BPF program and terminated them We haven’t added any selftests in the POC as this mail is mainly to get feedback on the design. Attaching link to sample BPF programs to validate the POC [7]. Styling will be taken care in next iteration. References: 1. https://lpc.events/event/17/contributions/1610/attachments/1229/2505/LPC_BPF_termination_Raj_Sahu.pdf 2. https://vtechworks.lib.vt.edu/server/api/core/bitstreams/f0749daa-4560-41c9-9f36-6aa618161665/content 3. https://lore.kernel.org/bpf/AM6PR03MB508011599420DB53480E8BF799F72@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/T/ 4. https://vtechworks.lib.vt.edu/server/api/core/bitstreams/7fb70c04-0736-4e2d-b48b-2d8d012bacfc/content 5. https://lwn.net/ml/all/AM6PR03MB5080513BFAEB54A93CC70D4399FE2@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/#t 6. https://people.cs.vt.edu/djwillia/papers/ebpf23-runtime.pdf 7. https://github.com/sidchintamaneni/os-dev-env/tree/main/bpf-programs-catalog/research/termination/patch_gen_testing arch/x86/kernel/smp.c | 4 +- include/linux/bpf.h | 18 ++ include/linux/filter.h | 16 ++ include/linux/smp.h | 2 +- include/uapi/linux/bpf.h | 13 ++ kernel/bpf/bpf_iter.c | 65 ++++++ kernel/bpf/core.c | 45 ++++ kernel/bpf/helpers.c | 8 + kernel/bpf/syscall.c | 375 +++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 16 +- kernel/smp.c | 22 +- tools/bpf/bpftool/prog.c | 40 ++++ tools/include/uapi/linux/bpf.h | 5 + tools/lib/bpf/bpf.c | 15 ++ tools/lib/bpf/bpf.h | 10 + tools/lib/bpf/libbpf.map | 1 + 16 files changed, 643 insertions(+), 12 deletions(-) -- 2.43.0
