[RFC PATCH bpf-next v1 10/16] bpf: Let typed_arena_cast copy pointers the verifier already trusts

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

The compiler inserts the cast at every use of a pointer to a struct with
special fields, so that programs never write one, and it cannot tell what
the pointer is: the same struct lives in typed arenas, in allocated objects,
in map values and on the stack. So the verifier decides per path what the
cast takes. A scalar, a raw arena pointer, a typed arena pointer loaded from
a field and not yet sanitized, one of another struct, or one that
arithmetic moved inside its object is sanitized as before. A sanitized
pointer of the struct's own typed arena at offset zero is already what the
cast produces, so it is copied, and since the sequence is a no-op on it,
such a path may share the instruction with sanitizing ones. Any other
verified pointer, to an allocated object, a map value, the stack or
anything else, is copied with its state, offset and references: the cast
has nothing to add to what the verifier knows, so it needs neither an arena
map nor a registration, and a program that only allocates objects of the
struct loads as before. The lowering is per instruction and runs on every
path through it, so a path that copies such a pointer cannot share the
instruction with one that sanitizes, since the sequence would mask a
pointer that is not in the slice; that program is rejected. An instruction
that only copied lowers to a move, or to nothing when dst is src, which
takes removing the instruction, as the nop removal pass has already run.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/fixups.c   | 35 ++++++++++++++++++++++--------
 kernel/bpf/verifier.c | 50 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 76 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index fd0ba8376c1c..a0856bd18ac2 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -897,17 +897,34 @@ int bpf_lower_typed_arena_insns(struct bpf_verifier_env *env)
 	for (i = 0; i < insn_cnt; i++, insn++) {
 		aux = &env->insn_aux_data[i + delta];
 		cnt = 0;
-		if (aux->sanitize_needed)
-			cnt = bpf_typed_arena_cast_insns(aux->sanitize_arena, aux->sanitize_reg,
-							 aux->sanitize_reg, insn_buf);
 		if (insn_is_typed_arena_cast(insn)) {
-			if (!aux->typed_arena) {
-				verifier_bug(env, "typed_arena_cast at insn %d has no typed arena", i);
-				return -EFAULT;
+			/*
+			 * A cast that sanitized on some path lowers to the
+			 * sequence, a no-op on the paths that brought a sanitized
+			 * pointer of the same typed arena. One that only copied
+			 * verified pointers is a move, or nothing at all.
+			 */
+			if (aux->sanitize_needed) {
+				if (!aux->typed_arena) {
+					verifier_bug(env, "typed_arena_cast at insn %d has no typed arena", i);
+					return -EFAULT;
+				}
+				cnt = bpf_typed_arena_cast_insns(aux->typed_arena, insn->dst_reg,
+								 insn->src_reg, insn_buf);
+			} else if (insn->dst_reg != insn->src_reg) {
+				insn_buf[cnt++] = BPF_MOV64_REG(insn->dst_reg, insn->src_reg);
+			} else {
+				int err = verifier_remove_insns(env, i + delta, 1);
+
+				if (err)
+					return err;
+				delta--;
+				insn = env->prog->insnsi + i + delta;
+				continue;
 			}
-			cnt += bpf_typed_arena_cast_insns(aux->typed_arena, insn->dst_reg,
-							  insn->src_reg, insn_buf + cnt);
-		} else if (cnt) {
+		} else if (aux->sanitize_needed) {
+			cnt = bpf_typed_arena_cast_insns(aux->sanitize_arena, aux->sanitize_reg,
+							 aux->sanitize_reg, insn_buf);
 			insn_buf[cnt++] = *insn;
 		}
 		if (!cnt)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b85d99f81ef5..aceb17e62948 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17299,13 +17299,51 @@ static struct bpf_typed_arena *typed_arena_register(struct bpf_verifier_env *env
  * of the instruction, so an instruction casts to one type on every path, and
  * the lowering can be chosen once.
  */
+/*
+ * dst = typed_arena_cast(src, imm) makes a trusted pointer to an object of the
+ * struct imm names out of the value in src. What that takes depends on the
+ * value, and the compiler that inserts the cast at every use of a pointer to
+ * the struct cannot tell, since the same struct lives in typed arenas, in
+ * allocated objects, in map values and on the stack. So the verifier decides
+ * per path. A scalar, a raw arena pointer, or a typed arena pointer that is
+ * unsanitized, of another struct, or moved inside its object is sanitized:
+ * dst becomes a pointer to the start of an object of the struct's typed
+ * arena, and the lowering masks and rebases the value. A sanitized pointer of
+ * that typed arena at offset zero is already what the cast makes, so dst is a
+ * copy of src; the sequence is a no-op on it, which lets such a path share
+ * the instruction with sanitizing ones. Any other verified pointer, to an
+ * allocated object, a map value, the stack, or anything else, is copied as it
+ * is, with its state, offset and references: the cast has nothing to add to
+ * what the verifier already knows, and needs no arena and no registration. A
+ * typed arena pointer that may be NULL, an allocation's result, is one of
+ * these: sanitizing it would turn a failed allocation into object 0, so it is
+ * copied and keeps its check.
+ *
+ * The lowering is per instruction and runs on every path through it, so a
+ * path that copies a verified pointer of another kind cannot share the
+ * instruction with a path that sanitizes: the sequence would mask a pointer
+ * that is not in the slice. Such a program is rejected.
+ */
 static int check_typed_arena_cast(struct bpf_verifier_env *env, struct bpf_insn *insn)
 {
 	struct bpf_insn_aux_data *aux = &env->insn_aux_data[env->insn_idx];
 	struct bpf_reg_state *regs = cur_regs(env);
+	struct bpf_reg_state *src = &regs[insn->src_reg];
 	struct bpf_reg_state *dst = &regs[insn->dst_reg];
 	struct bpf_typed_arena *ta;
 
+	if (src->type != SCALAR_VALUE && base_type(src->type) != PTR_TO_ARENA &&
+	    (!type_is_typed_arena_obj(src->type) || type_flag(src->type) & PTR_MAYBE_NULL)) {
+		if (aux->sanitize_needed) {
+			verbose(env, "insn %d casts values that need different treatment on different paths\n",
+				env->insn_idx);
+			return -EINVAL;
+		}
+		aux->sanitize_plain |= BIT(insn->src_reg);
+		*dst = *src;
+		return 0;
+	}
+
 	/* The arena itself needs CAP_PERFMON, so the leak rules already permit a kernel pointer. */
 	if (!env->prog->aux->arena) {
 		verbose(env, "typed_arena_cast insn can only be used in a program that has an associated arena\n");
@@ -17320,6 +17358,18 @@ static int check_typed_arena_cast(struct bpf_verifier_env *env, struct bpf_insn
 		return PTR_ERR(ta);
 	aux->typed_arena = ta;
 
+	if (src->type == (PTR_TO_BTF_ID | MEM_ARENA) && src->btf_id == ta->btf_id &&
+	    tnum_is_const(src->var_off) && !src->var_off.value) {
+		*dst = *src;
+		return 0;
+	}
+	if (aux->sanitize_plain) {
+		verbose(env, "insn %d casts values that need different treatment on different paths\n",
+			env->insn_idx);
+		return -EINVAL;
+	}
+	aux->sanitize_needed = true;
+
 	mark_reg_known_zero(env, regs, insn->dst_reg);
 	dst->type = PTR_TO_BTF_ID | MEM_ARENA;
 	dst->btf = env->prog->aux->btf;
-- 
2.53.0