Timed may_goto
Status from this message: This series was applied to bpf/bpf-next.git (master)
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v2 Latest2 patches 1 replyApplied 2/2
- v12 patches 3 repliesSuperseded
Changes in v2 from the cover letter
v1: https://lore.kernel.org/bpf/[email protected]
* Address comments from Alexei
* Use kernel comment style for new code.
* Remove p->count == 0 check in bpf_check_timed_may_goto.
* Add comments on AX as argument/retval calling convention.
* Add comments describing how the counting logic works.
* Use BPF_EMIT_CALL instead of open-coding instruction encoding.
* Change if ax != 1 goto pc+X condition to if ax != 0 goto pc+X.
Patches in v2 All 2 applied
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/2 | bpf: Add verifier support for timed may_gotoinclude/ include/ kernel/ +1 more | +103 | 1 reply | Applied |
| 2/2 | bpf, x86: Add x86 JIT support for timed may_gotoarch/ arch/ arch/ +2 more | +138 | 0 replies | Applied |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.
Cover letter [PATCH bpf-next v2 0/2] Timed may_goto
This series replaces the current implementation of cond_break, which uses the may_goto instruction, and counts 8 million iterations per stack frame, with an implementation based on sampling time locally on the CPU.
This is done to permit a longer time for a given loop per-program invocation. The accounting is still done per-stack frame, but the count is used to instead amortize the cost of the logic to sample and check the time spent since the start.
This is needed for expressing more complicated algorithms (spin locks, waiting loops, etc.) in BPF programs without false positive expiration of the loop. For instance, the plan is to make use of this for implementing spin locks for BPF arena [0].
For the loop as follows:
for (int i = 0;; i++) {}
Testing on a bare-metal Sapphire Rapids Intel server yields the following table (taking an average of 25 runs).
+-----------------------------+--------------+--------------+------------------+ | Loop type | Iterations | Time (ms) | Time/iter (ns) | +-----------------------------|--------------+--------------+------------------+ | may_goto | 8388608 | 3 | 0.36 | | timed_may_goto (count=65535)| 589674932 | 250 | 0.42 | | bpf_for | 8388608 | 10 | 1.19 | +-----------------------------+--------------+--------------+------------------+
Here, count is used to amortize the time sampling and checking logic.
Obviously, this is the limit of an empty loop. Given the complexity of the loop body, the time spent in the loop can be longer. Cancellations will address the task of imposing an upper bound on program runtime.
For now, the implementation only supports x86.
[0]: https://lore.kernel.org/bpf/[email protected]
Changelog:
----------
v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]
* Address comments from Alexei
* Use kernel comment style for new code.
* Remove p->count == 0 check in bpf_check_timed_may_goto.
* Add comments on AX as argument/retval calling convention.
* Add comments describing how the counting logic works.
* Use BPF_EMIT_CALL instead of open-coding instruction encoding.
* Change if ax != 1 goto pc+X condition to if ax != 0 goto pc+X.
Kumar Kartikeya Dwivedi (2):
bpf: Add verifier support for timed may_goto bpf, x86: Add x86 JIT support for timed may_goto
arch/x86/net/Makefile | 2 +- arch/x86/net/bpf_jit_comp.c | 5 ++ arch/x86/net/bpf_timed_may_goto.S | 52 ++++++++++++++ include/linux/bpf.h | 1 + include/linux/filter.h | 8 +++ kernel/bpf/core.c | 32 +++++++++ kernel/bpf/verifier.c | 70 ++++++++++++++++--- .../bpf/progs/verifier_bpf_fastcall.c | 58 ++++++++++++--- .../selftests/bpf/progs/verifier_may_goto_1.c | 34 ++++++++- 9 files changed, 241 insertions(+), 21 deletions(-) create mode 100644 arch/x86/net/bpf_timed_may_goto.S
base-commit: 7586e2169c77a444d235a98ac858272d3dcec16e
Signature · 1 line
2.43.5