[RFC PATCH bpf-next v1 08/16] bpf: Canonicalize loaded typed arena pointers where they are used

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

A typed arena pointer loaded from a typed pointer field is an object of its
type or 0, but it is not canonical: nothing masked it into its slot, and it
may be 0. The previous patch refused to use it as an address. Sanitize it
instead where it is used, in place: when an instruction loads or stores
through such a pointer, or an atomic runs on it, when arithmetic moves it,
or when it goes to a helper or kfunc, the lowering prepends the typed
arena's cast sequence to that instruction, on that register, and on that
path the register is canonical from then on. Compares, copies, spills and
stores of the value as a value need nothing, so a list is walked with plain
loads and ends with the usual test against 0, and a pointer that is only
passed along is never touched.

This is the whole of the NULL question. The field's discipline says the
value is an object or 0. A program that tests for 0 sees the raw value and
takes its branch. A program that does not test, or tests wrongly, uses the
value as an address, the sequence maps 0 to object 0 of the slice, and the
access lands on a whole object of the type, the same outcome as feeding 0
to a cast. Nothing the program does with the value can reach outside the
slice, so the verifier asks for no annotation and no check: the SFI scheme
decides the result, not the type system, and a NULL check is a matter of
program logic alone. The alternative, a maybe-NULL pointer type that must
be checked before every use, would put a check on every hop of a
traversal that the sanitization makes unnecessary.

The sequence is lowered once per instruction and runs on every path through
it, so it must be harmless on every path. It is idempotent on a canonical
pointer of the same typed arena at offset zero, which is what a path that
got its pointer from a cast or from an earlier sanitization brings. It is
wrong on a pointer with an offset into its object, since the mask rounds to
the object base, on a pointer of another typed arena, whose base and mask
differ, and on any other value. So the verifier records the register and
its typed arena in the instruction's aux data when a path needs the
sequence, and rejects the program when another path brings that register
in a form the sequence would corrupt, or when a second register needs it at
the same instruction, which no compiler-generated code does. Arithmetic
sanitizes before it moves the pointer for the same reason: the offset must
be added to the object base, not masked away later.

The later optimization phase builds on the unsanitized form: a load through
such a pointer that nothing writes to can be a probed load instead of a
sanitized one, and a chain of reads then costs nothing beyond the loads. A
store of a typed pointer into a typed object always sanitizes its
destination, since the field's discipline depends on the store landing in a
real object.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/bpf_verifier.h | 10 +++++
 kernel/bpf/fixups.c          | 38 +++++++++++++------
 kernel/bpf/verifier.c        | 71 ++++++++++++++++++++++++++++++++----
 3 files changed, 99 insertions(+), 20 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 77e7c4b45a1f..bf0f23929671 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -662,6 +662,16 @@ struct bpf_insn_aux_data {
 	};
 	struct btf_struct_meta *kptr_struct_meta;
 	struct bpf_typed_arena *typed_arena; /* named by a cast or a typed arena kfunc call */
+	/*
+	 * Lazy sanitization of a typed arena pointer used as an address here:
+	 * the register and its typed arena, whether a path brought the pointer
+	 * unsanitized, and the registers some path brought in a form the
+	 * sanitizing sequence would corrupt.
+	 */
+	struct bpf_typed_arena *sanitize_arena;
+	u16 sanitize_plain;
+	u8 sanitize_reg;
+	bool sanitize_needed;
 	u64 map_key_state; /* constant (32 bit) key tracking for maps */
 	int ctx_field_size; /* the ctx field size for load insn, maybe 0 */
 	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
diff --git a/kernel/bpf/fixups.c b/kernel/bpf/fixups.c
index 0b4636498ddc..fd0ba8376c1c 100644
--- a/kernel/bpf/fixups.c
+++ b/kernel/bpf/fixups.c
@@ -877,27 +877,41 @@ int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
  *     struct bpf_sock_ops -> struct sock
  */
 /*
- * Replace every typed_arena_cast with the sanitizing sequence of the typed
- * arena the verifier registered for it. The type is part of the instruction,
- * so a cast has exactly one typed arena by the time it gets here.
+ * Lower the instructions the verifier tied to a typed arena. A typed_arena_cast
+ * becomes the sanitizing sequence of the typed arena the verifier registered
+ * for it; the type is part of the instruction, so a cast has exactly one. An
+ * instruction that uses a typed pointer loaded from a typed pointer field as
+ * an address gets the same sequence prepended, in place on that register: the
+ * verifier checked that every path brings that register here as an
+ * unsanitized pointer of that typed arena, or as a canonical one at offset
+ * zero, on which the sequence is a no-op.
  */
 int bpf_lower_typed_arena_insns(struct bpf_verifier_env *env)
 {
 	struct bpf_insn *insn = env->prog->insnsi;
 	int i, cnt, delta = 0, insn_cnt = env->prog->len;
-	const struct bpf_typed_arena *ta;
-	struct bpf_insn insn_buf[8];
+	struct bpf_insn insn_buf[16];
+	struct bpf_insn_aux_data *aux;
 	struct bpf_prog *new_prog;
 
 	for (i = 0; i < insn_cnt; i++, insn++) {
-		if (!insn_is_typed_arena_cast(insn))
-			continue;
-		ta = env->insn_aux_data[i + delta].typed_arena;
-		if (!ta) {
-			verifier_bug(env, "typed_arena_cast at insn %d has no typed arena", i);
-			return -EFAULT;
+		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;
+			}
+			cnt += bpf_typed_arena_cast_insns(aux->typed_arena, insn->dst_reg,
+							  insn->src_reg, insn_buf + cnt);
+		} else if (cnt) {
+			insn_buf[cnt++] = *insn;
 		}
-		cnt = bpf_typed_arena_cast_insns(ta, insn->dst_reg, insn->src_reg, insn_buf);
+		if (!cnt)
+			continue;
 		new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
 		if (!new_prog)
 			return -ENOMEM;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5ca5fc4696d9..2d406034556e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -383,20 +383,75 @@ static bool reg_not_null(struct bpf_verifier_env *env, const struct bpf_reg_stat
 }
 
 /*
- * @regno is about to serve as an address, or go to a call. A typed arena
- * pointer loaded from a typed pointer field is not canonical yet: its slice
- * and slot are what the field's discipline promises, not what the lowering has
- * masked, and until the lowering learns to sanitize it in place such a use is
- * refused.
+ * @regno is about to serve as an address, be moved by arithmetic, or go to a
+ * call. A typed arena pointer loaded from a typed pointer field is not
+ * canonical: it is an object of its type or 0, as the field's discipline
+ * promises, but nothing masked it into its slot. Sanitize it here, in place:
+ * the lowering prepends the typed arena's cast sequence to this instruction,
+ * and on this path the register is canonical from here on. The sequence maps
+ * 0 to object 0 of the slice, as the cast maps any value, so a NULL the
+ * program did not test costs no more than a stray cast would.
+ *
+ * The sequence is lowered once per instruction and runs on every path through
+ * it, so it must be harmless on every path. It is a no-op on a canonical
+ * pointer of the same typed arena at offset zero, and wrong on anything else:
+ * a path that brings another typed arena, a pointer with an offset into its
+ * object, or a value of another kind to this register here is rejected, and
+ * so is a second register in need of the sequence at the same instruction.
+ * Where nothing brings an unsanitized pointer, nothing is lowered.
  */
 static int typed_arena_use(struct bpf_verifier_env *env, int regno)
 {
+	struct bpf_insn_aux_data *aux = &env->insn_aux_data[env->insn_idx];
 	struct bpf_reg_state *reg = &cur_regs(env)[regno];
+	struct bpf_typed_arena *ta;
+	bool canonical;
+
+	canonical = !(type_flag(reg->type) & PTR_UNSANITIZED);
+	if (!type_is_typed_arena_obj(reg->type) ||
+	    (canonical && (!tnum_is_const(reg->var_off) || reg->var_off.value))) {
+		if (aux->sanitize_needed && aux->sanitize_reg == regno) {
+			verbose(env, "insn %d sanitizes a typed arena pointer only on some paths\n",
+				env->insn_idx);
+			return -EINVAL;
+		}
+		aux->sanitize_plain |= BIT(regno);
+		return 0;
+	}
 
-	if (!type_is_unsanitized_arena_obj(reg->type))
+	ta = bpf_prog_typed_arena(env->prog->aux, reg->btf_id);
+	if (verifier_bug_if(!ta, env, "R%d typed arena pointer has no typed arena", regno))
+		return -EFAULT;
+	if (aux->sanitize_arena && aux->sanitize_reg == regno && aux->sanitize_arena != ta) {
+		verbose(env, "insn %d sanitizes typed arena pointers of different types on different paths\n",
+			env->insn_idx);
+		return -EINVAL;
+	}
+	if (aux->sanitize_arena && aux->sanitize_reg != regno) {
+		if (canonical)
+			return 0;
+		if (aux->sanitize_needed) {
+			verbose(env, "insn %d needs more than one typed arena pointer sanitized\n",
+				env->insn_idx);
+			return -EINVAL;
+		}
+		/* A canonical pointer only booked the register; the one in need takes it. */
+		aux->sanitize_arena = NULL;
+	}
+	if (!aux->sanitize_arena) {
+		aux->sanitize_arena = ta;
+		aux->sanitize_reg = regno;
+	}
+	if (canonical)
 		return 0;
-	verbose(env, "R%d unsanitized typed arena pointer cannot be dereferenced\n", regno);
-	return -EACCES;
+	if (aux->sanitize_plain & BIT(regno)) {
+		verbose(env, "insn %d sanitizes a typed arena pointer only on some paths\n",
+			env->insn_idx);
+		return -EINVAL;
+	}
+	aux->sanitize_needed = true;
+	reg->type &= ~PTR_UNSANITIZED;
+	return 0;
 }
 
 static struct btf_record *reg_btf_record(const struct bpf_reg_state *reg)
-- 
2.53.0