[PATCH bpf-next v2 02/43] bpf: forbid sleeping in hash map for_each callbacks

From: Josef Bacik <josef@toxicpanda.com>

A sleepable program (e.g. SEC("syscall"), lsm.s, fentry.s) can pass a
callback to bpf_for_each_map_elem() on a hash map and call a sleepable
helper or kfunc such as bpf_copy_from_user() from it. The verifier
accepts this, but at run time the callback is invoked from inside an RCU
read-side critical section:

    bpf_for_each_hash_elem()
      rcu_read_lock();
      callback_fn(map, key, val, ctx, 0);
        bpf_copy_from_user()       <- may fault and sleep
      rcu_read_unlock();

bpf_each_rhash_elem() does the same for BPF_MAP_TYPE_RHASH. Sleeping
there triggers the "Voluntary context switch within RCU read-side
critical section!" warning, delays grace periods, and with
CONFIG_PREEMPT_RCU=n silently ends the read-side critical section that
the bucket walk relies on.

Synchronous callbacks are verified with the caller's state, so
kernel/bpf/verifier.c:in_sleepable_context() only looks at the program's
sleepability and the locks the program took itself, and does not know
that the helper holds rcu_read_lock() around the callback.

With a SEC("syscall") program whose callback reads a page that has to be
read from disk first:

  BUG: sleeping function called from invalid context at include/linux/uaccess.h:169
  RCU nest depth: 1, expected: 0
   __might_fault+0x29/0x80
   _copy_from_user+0x26/0x90
   bpf_copy_from_user+0x23/0x60
   bpf_prog_17d44fa39eebd6cc_cb+0x35/0x46
   bpf_for_each_hash_elem+0xdb/0x280

Fix by marking the callback frame of hash map iteration as running under
RCU and making in_sleepable_context() false while such a frame is on the
call stack, so sleepable helpers, kfuncs and global functions are
rejected there as inside bpf_rcu_read_lock(). The rules for trusting RCU
protected pointers are left alone, which is conservative and keeps
callbacks that verify today and do not sleep working. The flag is
compared in func_states_equal() so that pruning never mixes the two
contexts. Array map callbacks run without any lock and keep the caller's
context.

Fixes: 314ee05e2fc6 ("bpf: Add hashtab support for bpf_for_each_map_elem() helper")
Fixes: 818e00848227 ("bpf: Implement iteration ops for resizable hashtab")
Signed-off-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf_verifier.h |  5 +++++
 kernel/bpf/states.c          |  3 +++
 kernel/bpf/verifier.c        | 28 +++++++++++++++++++++++++++-
 3 files changed, 35 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 112ca1511da4..816948df8fff 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h

@@ -379,6 +379,11 @@ struct bpf_func_state {
 	bool in_async_callback_fn;
 	bool in_exception_callback_fn;
 	bool no_stack_arg_load;
+	/*
+	 * The helper invokes this callback under rcu_read_lock(), so the
+	 * callback and its callees run in an RCU read-side critical section.
+	 */
+	bool in_rcu_callback_fn;
 	/* For callback calling functions that limit number of possible
 	 * callback executions (e.g. bpf_loop) keeps track of current
 	 * simulated iteration number.

diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c
index 953700822fa7..b3d250caaaa6 100644
--- a/kernel/bpf/states.c
+++ b/kernel/bpf/states.c

@@ -995,6 +995,9 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 	if (!old->no_stack_arg_load && cur->no_stack_arg_load)
 		return false;
 
+	if (old->in_rcu_callback_fn != cur->in_rcu_callback_fn)
+		return false;
+
 	for (i = 0; i < MAX_BPF_REG; i++)
 		if (((1 << i) & live_regs) &&
 		    !regsafe(env, &old->regs[i], &cur->regs[i],

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ddfa0c6d2755..883cf148235c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c

@@ -11530,6 +11530,19 @@ static int set_map_elem_callback_state(struct bpf_verifier_env *env,
 	if (err)
 		return err;
 
+	switch (map->map_type) {
+	case BPF_MAP_TYPE_HASH:
+	case BPF_MAP_TYPE_PERCPU_HASH:
+	case BPF_MAP_TYPE_LRU_HASH:
+	case BPF_MAP_TYPE_LRU_PERCPU_HASH:
+	case BPF_MAP_TYPE_RHASH:
+		/* Hash tables run the callback under rcu_read_lock(). */
+		callee->in_rcu_callback_fn = true;
+		break;
+	default:
+		break;
+	}
+
 	callee->in_callback_fn = true;
 	callee->callback_ret_range = retval_range(0, 1);
 	return 0;

@@ -12273,10 +12286,22 @@ int bpf_get_helper_proto(struct bpf_verifier_env *env, int func_id,
 	return *ptr && (*ptr)->func ? 0 : -EINVAL;
 }
 
+/* Is any frame on the current path a callback that runs under RCU? */
+static bool in_rcu_callback(struct bpf_verifier_env *env)
+{
+	struct bpf_verifier_state *state = env->cur_state;
+	int i;
+
+	for (i = 0; i <= state->curframe; i++)
+		if (state->frame[i]->in_rcu_callback_fn)
+			return true;
+	return false;
+}
+
 /* Check if we're in a sleepable context. */
 static inline bool in_sleepable_context(struct bpf_verifier_env *env)
 {
-	return !in_rcu_cs(env);
+	return !in_rcu_cs(env) && !in_rcu_callback(env);
 }
 
 static const char *non_sleepable_context_description(struct bpf_verifier_env *env)

@@ -12290,6 +12315,7 @@ static const char *non_sleepable_context_description(struct bpf_verifier_env *en
 			return "IRQ-disabled region";
 		if (env->cur_state->active_locks)
 			return "lock region";
+		return "callback running under rcu_read_lock";
 	}
 	return "non-sleepable prog";
 }

-- 
2.55.0