From: Eduard Zingerman <eddyz87@gmail.com>
To: stable@vger.kernel.org, ast@kernel.org
Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev,
yonghong.song@linux.dev, mykolal@fb.com,
gregkh@linuxfoundation.org, mat.gienieczko@tum.de,
Eduard Zingerman <eddyz87@gmail.com>
Subject: [PATCH 6.6.y 16/17] bpf: keep track of max number of bpf_loop callback iterations
Date: Thu, 25 Jan 2024 02:15:53 +0200 [thread overview]
Message-ID: <20240125001554.25287-17-eddyz87@gmail.com> (raw)
In-Reply-To: <20240125001554.25287-1-eddyz87@gmail.com>
[ Upstream commit bb124da69c47 ]
In some cases verifier can't infer convergence of the bpf_loop()
iteration. E.g. for the following program:
static int cb(__u32 idx, struct num_context* ctx)
{
ctx->i++;
return 0;
}
SEC("?raw_tp")
int prog(void *_)
{
struct num_context ctx = { .i = 0 };
__u8 choice_arr[2] = { 0, 1 };
bpf_loop(2, cb, &ctx, 0);
return choice_arr[ctx.i];
}
Each 'cb' simulation would eventually return to 'prog' and reach
'return choice_arr[ctx.i]' statement. At which point ctx.i would be
marked precise, thus forcing verifier to track multitude of separate
states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.
This commit allows "brute force" handling for such cases by limiting
number of callback body simulations using 'umax' value of the first
bpf_loop() parameter.
For this, extend bpf_func_state with 'callback_depth' field.
Increment this field when callback visiting state is pushed to states
traversal stack. For frame #N it's 'callback_depth' field counts how
many times callback with frame depth N+1 had been executed.
Use bpf_func_state specifically to allow independent tracking of
callback depths when multiple nested bpf_loop() calls are present.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20231121020701.26440-11-eddyz87@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
[ Summary of the conflicts and their resolutions ]
There was one conflict with this patch, related to implementation of
BPF exceptions: the upstream series was developed after BPF exceptions
landed in bpf-next and BPF exceptions are not selected for porting to
6.6.y at the moment.
Conflict was resolved by excluding exceptions related part.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 11 ++++++
kernel/bpf/verifier.c | 19 ++++++++--
.../bpf/progs/verifier_subprog_precision.c | 35 +++++++++++++------
3 files changed, 53 insertions(+), 12 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f3b9550e8ef9..2d84d820a7ba 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -300,6 +300,17 @@ struct bpf_func_state {
bool in_callback_fn;
struct tnum callback_ret_range;
bool in_async_callback_fn;
+ /* For callback calling functions that limit number of possible
+ * callback executions (e.g. bpf_loop) keeps track of current
+ * simulated iteration number.
+ * Value in frame N refers to number of times callback with frame
+ * N+1 was simulated, e.g. for the following call:
+ *
+ * bpf_loop(..., fn, ...); | suppose current frame is N
+ * | fn would be simulated in frame N+1
+ * | number of simulations is tracked in frame N
+ */
+ u32 callback_depth;
/* The following fields should be last. See copy_func_state() */
int acquired_refs;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 638ab1fdf214..da029fc79df1 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9320,6 +9320,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
return err;
callback_state->callback_unroll_depth++;
+ callback_state->frame[callback_state->curframe - 1]->callback_depth++;
+ caller->callback_depth = 0;
return 0;
}
@@ -10102,8 +10104,21 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
break;
case BPF_FUNC_loop:
update_loop_inline_state(env, meta.subprogno);
- err = push_callback_call(env, insn, insn_idx, meta.subprogno,
- set_loop_callback_state);
+ /* Verifier relies on R1 value to determine if bpf_loop() iteration
+ * is finished, thus mark it precise.
+ */
+ err = mark_chain_precision(env, BPF_REG_1);
+ if (err)
+ return err;
+ if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value) {
+ err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+ set_loop_callback_state);
+ } else {
+ cur_func(env)->callback_depth = 0;
+ if (env->log.level & BPF_LOG_LEVEL2)
+ verbose(env, "frame%d bpf_loop iteration limit reached\n",
+ env->cur_state->curframe);
+ }
break;
case BPF_FUNC_dynptr_from_mem:
if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
index da803cffb5ef..f61d623b1ce8 100644
--- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
@@ -119,7 +119,23 @@ __naked int global_subprog_result_precise(void)
SEC("?raw_tp")
__success __log_level(2)
-/* First simulated path does not include callback body */
+/* First simulated path does not include callback body,
+ * r1 and r4 are always precise for bpf_loop() calls.
+ */
+__msg("9: (85) call bpf_loop#181")
+__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
+__msg("mark_precise: frame0: parent state regs=r4 stack=:")
+__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
+__msg("mark_precise: frame0: regs=r4 stack= before 8: (b7) r4 = 0")
+__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
+__msg("mark_precise: frame0: parent state regs=r1 stack=:")
+__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
+__msg("mark_precise: frame0: regs=r1 stack= before 8: (b7) r4 = 0")
+__msg("mark_precise: frame0: regs=r1 stack= before 7: (b7) r3 = 0")
+__msg("mark_precise: frame0: regs=r1 stack= before 6: (bf) r2 = r8")
+__msg("mark_precise: frame0: regs=r1 stack= before 5: (bf) r1 = r6")
+__msg("mark_precise: frame0: regs=r6 stack= before 4: (b7) r6 = 3")
+/* r6 precision propagation */
__msg("14: (0f) r1 += r6")
__msg("mark_precise: frame0: last_idx 14 first_idx 9")
__msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
@@ -134,10 +150,9 @@ __msg("17: (b7) r0 = 0")
__msg("18: (95) exit")
__msg("returning from callee:")
__msg("to caller at 9:")
-/* r4 (flags) is always precise for bpf_loop() */
-__msg("frame 0: propagating r4")
+__msg("frame 0: propagating r1,r4")
__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
-__msg("mark_precise: frame0: regs=r4 stack= before 18: (95) exit")
+__msg("mark_precise: frame0: regs=r1,r4 stack= before 18: (95) exit")
__msg("from 18 to 9: safe")
__naked int callback_result_precise(void)
{
@@ -264,12 +279,12 @@ __msg("15: (b7) r0 = 0")
__msg("16: (95) exit")
__msg("returning from callee:")
__msg("to caller at 9:")
-/* r4 (flags) is always precise for bpf_loop(),
+/* r1, r4 are always precise for bpf_loop(),
* r6 was marked before backtracking to callback body.
*/
-__msg("frame 0: propagating r4,r6")
+__msg("frame 0: propagating r1,r4,r6")
__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
-__msg("mark_precise: frame0: regs=r4,r6 stack= before 16: (95) exit")
+__msg("mark_precise: frame0: regs=r1,r4,r6 stack= before 16: (95) exit")
__msg("mark_precise: frame1: regs= stack= before 15: (b7) r0 = 0")
__msg("mark_precise: frame1: regs= stack= before 9: (85) call bpf_loop")
__msg("mark_precise: frame0: parent state regs= stack=:")
@@ -422,12 +437,12 @@ __msg("17: (b7) r0 = 0")
__msg("18: (95) exit")
__msg("returning from callee:")
__msg("to caller at 10:")
-/* r4 (flags) is always precise for bpf_loop(),
+/* r1, r4 are always precise for bpf_loop(),
* fp-8 was marked before backtracking to callback body.
*/
-__msg("frame 0: propagating r4,fp-8")
+__msg("frame 0: propagating r1,r4,fp-8")
__msg("mark_precise: frame0: last_idx 10 first_idx 10 subseq_idx -1")
-__msg("mark_precise: frame0: regs=r4 stack=-8 before 18: (95) exit")
+__msg("mark_precise: frame0: regs=r1,r4 stack=-8 before 18: (95) exit")
__msg("mark_precise: frame1: regs= stack= before 17: (b7) r0 = 0")
__msg("mark_precise: frame1: regs= stack= before 10: (85) call bpf_loop#181")
__msg("mark_precise: frame0: parent state regs= stack=:")
--
2.43.0
next prev parent reply other threads:[~2024-01-25 0:16 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-01-25 0:15 [PATCH 6.6.y 00/17] bpf: backport of iterator and callback handling fixes Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 01/17] bpf: move explored_state() closer to the beginning of verifier.c Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 02/17] bpf: extract same_callsites() as utility function Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 03/17] bpf: exact states comparison for iterator convergence checks Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 04/17] selftests/bpf: tests with delayed read/precision makrs in loop body Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 05/17] bpf: correct loop detection for iterators convergence Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 06/17] selftests/bpf: test if state loops are detected in a tricky case Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 07/17] bpf: print full verifier states on infinite loop detection Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 08/17] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 09/17] selftests/bpf: track string payload offset as scalar in strobemeta Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 10/17] bpf: extract __check_reg_arg() utility function Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 11/17] bpf: extract setup_func_entry() " Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 12/17] bpf: verify callbacks as if they are called unknown number of times Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 13/17] selftests/bpf: tests for iterating callbacks Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 14/17] bpf: widening for callback iterators Eduard Zingerman
2024-01-25 0:15 ` [PATCH 6.6.y 15/17] selftests/bpf: test widening for iterating callbacks Eduard Zingerman
2024-01-25 0:15 ` Eduard Zingerman [this message]
2024-01-25 0:15 ` [PATCH 6.6.y 17/17] selftests/bpf: check if max number of bpf_loop iterations is tracked Eduard Zingerman
2024-01-27 1:13 ` [PATCH 6.6.y 00/17] bpf: backport of iterator and callback handling fixes Greg KH
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20240125001554.25287-17-eddyz87@gmail.com \
--to=eddyz87@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=daniel@iogearbox.net \
--cc=gregkh@linuxfoundation.org \
--cc=martin.lau@linux.dev \
--cc=mat.gienieczko@tum.de \
--cc=mykolal@fb.com \
--cc=stable@vger.kernel.org \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.