From: Eduard Zingerman <eddyz87@gmail.com>
To: bpf@vger.kernel.org, ast@kernel.org
Cc: andrii@kernel.org, daniel@iogearbox.net, martin.lau@linux.dev,
kernel-team@fb.com, yonghong.song@linux.dev, memxor@gmail.com,
awerner32@gmail.com, Eduard Zingerman <eddyz87@gmail.com>
Subject: [PATCH bpf v2 08/11] bpf: widening for callback iterators
Date: Sat, 18 Nov 2023 03:33:52 +0200 [thread overview]
Message-ID: <20231118013355.7943-9-eddyz87@gmail.com> (raw)
In-Reply-To: <20231118013355.7943-1-eddyz87@gmail.com>
Callbacks are similar to open coded iterators, so add imprecise
widening logic for callback body processing. This makes callback based
loops behave identically to open coded iterators, e.g. allowing to
verify programs like below:
struct ctx { u32 i; };
int cb(u32 idx, struct ctx* ctx)
{
++ctx->i;
return 0;
}
...
struct ctx ctx = { .i = 0 };
bpf_loop(100, cb, &ctx, 0);
...
Acked-by: Andrii Nakryiko <andrii@kernel.org>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
1 file changed, 22 insertions(+), 2 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 35e137c5f29a..b9e3067890b7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9977,9 +9977,10 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
{
- struct bpf_verifier_state *state = env->cur_state;
+ struct bpf_verifier_state *state = env->cur_state, *prev_st;
struct bpf_func_state *caller, *callee;
struct bpf_reg_state *r0;
+ bool callback_iter;
int err;
callee = state->frame[state->curframe];
@@ -10029,7 +10030,8 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
* there function call logic would reschedule callback visit. If iteration
* converges is_state_visited() would prune that visit eventually.
*/
- if (callee->in_callback_fn && is_callback_iter_next(env, callee->callsite))
+ callback_iter = callee->in_callback_fn && is_callback_iter_next(env, callee->callsite);
+ if (callback_iter)
*insn_idx = callee->callsite;
else
*insn_idx = callee->callsite + 1;
@@ -10044,6 +10046,24 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
* bpf_throw, this will be done by copy_verifier_state for extra frames. */
free_func_state(callee);
state->frame[state->curframe--] = NULL;
+
+ /* for callbacks widen imprecise scalars to make programs like below verify:
+ *
+ * struct ctx { int i; }
+ * void cb(int idx, struct ctx *ctx) { ctx->i++; ... }
+ * ...
+ * struct ctx = { .i = 0; }
+ * bpf_loop(100, cb, &ctx, 0);
+ *
+ * This is similar to what is done in process_iter_next_call() for open
+ * coded iterators.
+ */
+ prev_st = callback_iter ? find_prev_entry(env, state, *insn_idx) : NULL;
+ if (prev_st) {
+ err = widen_imprecise_scalars(env, prev_st, state);
+ if (err)
+ return err;
+ }
return 0;
}
--
2.42.1
next prev parent reply other threads:[~2023-11-18 1:34 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-18 1:33 [PATCH bpf v2 00/11] verify callbacks as if they are called unknown number of times Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 01/11] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 02/11] selftests/bpf: track string payload offset as scalar in strobemeta Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 03/11] selftests/bpf: fix bpf_loop_bench for new callback verification scheme Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 04/11] bpf: extract __check_reg_arg() utility function Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 05/11] bpf: extract setup_func_entry() " Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 06/11] bpf: verify callbacks as if they are called unknown number of times Eduard Zingerman
2023-11-20 1:41 ` Alexei Starovoitov
2023-11-20 1:46 ` Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 07/11] selftests/bpf: tests for iterating callbacks Eduard Zingerman
2023-11-18 1:33 ` Eduard Zingerman [this message]
2023-11-18 1:33 ` [PATCH bpf v2 09/11] selftests/bpf: test widening " Eduard Zingerman
2023-11-18 1:33 ` [PATCH bpf v2 10/11] bpf: keep track of max number of bpf_loop callback iterations Eduard Zingerman
2023-11-20 2:00 ` Alexei Starovoitov
2023-11-20 2:06 ` Eduard Zingerman
2023-11-20 2:11 ` Alexei Starovoitov
2023-11-18 1:33 ` [PATCH bpf v2 11/11] selftests/bpf: check if max number of bpf_loop iterations is tracked Eduard Zingerman
2023-11-20 2:09 ` Alexei Starovoitov
2023-11-20 2:23 ` Eduard Zingerman
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=20231118013355.7943-9-eddyz87@gmail.com \
--to=eddyz87@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=awerner32@gmail.com \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=martin.lau@linux.dev \
--cc=memxor@gmail.com \
--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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox