[bpf,08/12] bpf: widening for callback iterators

Commit Message

Eduard Zingerman Nov. 16, 2023, 2:17 a.m. UTC

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);
  ...

Signed-off-by: Eduard Zingerman <[e-mail]>
---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

Comments

Andrii Nakryiko Nov. 17, 2023, 4:46 p.m. UTC | #1

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <[e-mail]> wrote:
>
> 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);
>   ...
>
> Signed-off-by: Eduard Zingerman <[e-mail]>
> ---
>  kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
>  1 file changed, 22 insertions(+), 2 deletions(-)
>

Acked-by: Andrii Nakryiko <[e-mail]>

[...]

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 270f7ca3c44d..5b8c0ebcb4f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9974,9 +9974,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];
@@ -10026,7 +10027,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;
@@ -10041,6 +10043,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;
 }