Skip to contentSkip to conversation

BPF verifier state equivalence checks improvements

PATCH In review Andrii Nakryiko 4 participants 17 messages Dec 23, 2022 – Jan 11, 2023

Subsystems (2)
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

cover BPF verifier state equivalence checks improvements

This patch set fixes, improves, and refactors parts of BPF verifier's state equivalence checks.

Patch #1 fixes refsafe(), making it take into account ID map when comparing reference IDs. See patch for details.

Patches #2-#7 refactor regsafe() function which compares two register states across old and current states. regsafe() is critical piece of logic, so to make it easier to review and validate refactorings and logic fixes and improvements, each patch makes a small change, explaining why the change is correct and makes sense. Please see individual patches for details.

This patch set is one of the preliminaries required for upcoming BPF open-coded iterators, as with open-coded iterators verifier's loop safety and completion proof is critically dependent on correct state equivalence logic.

Andrii Nakryiko (7):
bpf: teach refsafe() to take into account ID remapping
bpf: reorganize struct bpf_reg_state fields
bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule
bpf: reject non-exact register type matches in regsafe()
bpf: perform byte-by-byte comparison only when necessary in regsafe()
bpf: fix regs_exact() logic in regsafe() to remap IDs correctly
bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

 include/linux/bpf_verifier.h |  40 +++++-----
 kernel/bpf/verifier.c        | 151 +++++++++++++++++++----------------
 2 files changed, 101 insertions(+), 90 deletions(-)
Signature · 1 line
2.30.2
author maintainer
#1 lore raw

PATCH 1/7 bpf: teach refsafe() to take into account ID remapping

states_equal() check performs ID mapping between old and new states to establish a 1-to-1 correspondence between IDs, even if their absolute numberic values across two equivalent states differ. This is important both for correctness and to avoid unnecessary work when two states are equivalent.

With recent changes we partially fixed this logic by maintaining ID map across all function frames. This patch also makes refsafe() check take into account (and maintain) ID map, making states_equal() behavior more optimal and correct.

---
 kernel/bpf/verifier.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +12 -4
index faa358b3d5d7..ab8337f6a576 100644
@@ -13223,12 +13223,20 @@ static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
 	return true;
 }
 
-static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur)
+static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,
+		    struct bpf_id_pair *idmap)
 {
+	int i;
+
 	if (old->acquired_refs != cur->acquired_refs)
 		return false;
-	return !memcmp(old->refs, cur->refs,
-		       sizeof(*old->refs) * old->acquired_refs);
+
+	for (i = 0; i < old->acquired_refs; i++) {
+		if (!check_ids(old->refs[i].id, cur->refs[i].id, idmap))
+			return false;
+	}
+
+	return true;
 }
 
 /* compare two verifier states
@@ -13270,7 +13278,7 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
 	if (!stacksafe(env, old, cur, env->idmap_scratch))
 		return false;
 
-	if (!refsafe(old, cur))
+	if (!refsafe(old, cur, env->idmap_scratch))
 		return false;
 
 	return true;
Signature · 1 line
2.30.2
author maintainer
#2 lore raw

PATCH 2/7 bpf: reorganize struct bpf_reg_state fields

In reply to Andrii Nakryiko

Move id and ref_obj_id fields after scalar data section (var_off and ranges). This is necessary to simplify next patch which will change regsafe()'s logic to be safer, as it makes the contents that has to be an exact match (type-specific parts, off, type, and var_off+ranges) a single sequential block of memory, while id and ref_obj_id should always be remapped and thus can't be memcp()'ed.

There are few places that assume that var_off is after id/ref_obj_id to clear out id/ref_obj_id with the single memset(0). These are changed to explicitly zero-out id/ref_obj_id fields. Other places are adjusted to preserve exact byte-by-byte comparison behavior.

No functional changes.

---
 include/linux/bpf_verifier.h | 40 ++++++++++++++++++------------------
 kernel/bpf/verifier.c        | 17 ++++++++-------
 2 files changed, 28 insertions(+), 29 deletions(-)
include/linux/bpf_verifier.h +20 -20
index 53d175cbaa02..127058cfec47 100644
@@ -92,6 +92,26 @@ struct bpf_reg_state {
 
 		u32 subprogno; /* for PTR_TO_FUNC */
 	};
+	/* For scalar types (SCALAR_VALUE), this represents our knowledge of
+	 * the actual value.
+	 * For pointer types, this represents the variable part of the offset
+	 * from the pointed-to object, and is shared with all bpf_reg_states
+	 * with the same id as us.
+	 */
+	struct tnum var_off;
+	/* Used to determine if any memory access using this register will
+	 * result in a bad access.
+	 * These refer to the same value as var_off, not necessarily the actual
+	 * contents of the register.
+	 */
+	s64 smin_value; /* minimum possible (s64)value */
+	s64 smax_value; /* maximum possible (s64)value */
+	u64 umin_value; /* minimum possible (u64)value */
+	u64 umax_value; /* maximum possible (u64)value */
+	s32 s32_min_value; /* minimum possible (s32)value */
+	s32 s32_max_value; /* maximum possible (s32)value */
+	u32 u32_min_value; /* minimum possible (u32)value */
+	u32 u32_max_value; /* maximum possible (u32)value */
 	/* For PTR_TO_PACKET, used to find other pointers with the same variable
 	 * offset, so they can share range knowledge.
 	 * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we
@@ -144,26 +164,6 @@ struct bpf_reg_state {
 	 * allowed and has the same effect as bpf_sk_release(sk).
 	 */
 	u32 ref_obj_id;
-	/* For scalar types (SCALAR_VALUE), this represents our knowledge of
-	 * the actual value.
-	 * For pointer types, this represents the variable part of the offset
-	 * from the pointed-to object, and is shared with all bpf_reg_states
-	 * with the same id as us.
-	 */
-	struct tnum var_off;
-	/* Used to determine if any memory access using this register will
-	 * result in a bad access.
-	 * These refer to the same value as var_off, not necessarily the actual
-	 * contents of the register.
-	 */
-	s64 smin_value; /* minimum possible (s64)value */
-	s64 smax_value; /* maximum possible (s64)value */
-	u64 umin_value; /* minimum possible (u64)value */
-	u64 umax_value; /* maximum possible (u64)value */
-	s32 s32_min_value; /* minimum possible (s32)value */
-	s32 s32_max_value; /* maximum possible (s32)value */
-	u32 u32_min_value; /* minimum possible (u32)value */
-	u32 u32_max_value; /* maximum possible (u32)value */
 	/* parentage chain for liveness checking */
 	struct bpf_reg_state *parent;
 	/* Inside the callee two registers can be both PTR_TO_STACK like
kernel/bpf/verifier.c +8 -9
index ab8337f6a576..e419e6024251 100644
@@ -1402,9 +1402,11 @@ static void ___mark_reg_known(struct bpf_reg_state *reg, u64 imm)
  */
 static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
 {
-	/* Clear id, off, and union(map_ptr, range) */
+	/* Clear off and union(map_ptr, range) */
 	memset(((u8 *)reg) + sizeof(reg->type), 0,
 	       offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
+	reg->id = 0;
+	reg->ref_obj_id = 0;
 	___mark_reg_known(reg, imm);
 }
 
@@ -1750,11 +1752,13 @@ static void __mark_reg_unknown(const struct bpf_verifier_env *env,
 			       struct bpf_reg_state *reg)
 {
 	/*
-	 * Clear type, id, off, and union(map_ptr, range) and
+	 * Clear type, off, and union(map_ptr, range) and
 	 * padding between 'type' and union
 	 */
 	memset(reg, 0, offsetof(struct bpf_reg_state, var_off));
 	reg->type = SCALAR_VALUE;
+	reg->id = 0;
+	reg->ref_obj_id = 0;
 	reg->var_off = tnum_unknown;
 	reg->frameno = 0;
 	reg->precise = !env->bpf_capable;
@@ -13104,7 +13108,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		if (type_may_be_null(rold->type)) {
 			if (!type_may_be_null(rcur->type))
 				return false;
-			if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)))
+			if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)))
 				return false;
 			/* Check our ids match any regs they're supposed to */
 			return check_ids(rold->id, rcur->id, idmap);
@@ -13112,13 +13116,8 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
 		/* If the new min/max/var_off satisfy the old ones and
 		 * everything else matches, we are OK.
-		 * 'id' is not compared, since it's only used for maps with
-		 * bpf_spin_lock inside map element and in such cases if
-		 * the rest of the prog is valid for one map element then
-		 * it's valid for all map elements regardless of the key
-		 * used in bpf_map_lookup()
 		 */
-		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
+		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
 		       range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off) &&
 		       check_ids(rold->id, rcur->id, idmap);
Signature · 1 line
2.30.2
author maintainer
#3 lore raw

PATCH 3/7 bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule

In reply to Andrii Nakryiko

Make generic check to prevent XXX_OR_NULL and XXX register types to be intermixed. While technically in some situations it could be safe, it's impossible to enforce due to the loss of an ID when converting XXX_OR_NULL to its non-NULL variant. So prevent this in general, not just for PTR_TO_MAP_KEY and PTR_TO_MAP_VALUE.

PTR_TO_MAP_KEY_OR_NULL and PTR_TO_MAP_VALUE_OR_NULL checks, which were previously special-cased, are simplified to generic check that takes into account range_within() and tnum_in(). This is correct as BPF verifier doesn't allow arithmetic on XXX_OR_NULL register types, so var_off and ranges should stay zero. But even if in the future this restriction is lifted, it's even more important to enforce that var_off and ranges are compatible, otherwise it's possible to construct case where this can be exploited to bypass verifier's memory range safety checks.

---
 kernel/bpf/verifier.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)
kernel/bpf/verifier.c +15 -16
index e419e6024251..218a7ace4210 100644
@@ -13074,6 +13074,21 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		return true;
 	if (rcur->type == NOT_INIT)
 		return false;
+
+	/* Register types that are *not* MAYBE_NULL could technically be safe
+	 * to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE  is
+	 * safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point to
+	 * the same map).
+	 * However, if the old MAYBE_NULL register then got NULL checked,
+	 * doing so could have affected others with the same id, and we can't
+	 * check for that because we lost the id when we converted to
+	 * a non-MAYBE_NULL variant.
+	 * So, as a general rule we don't allow mixing MAYBE_NULL and
+	 * non-MAYBE_NULL registers.
+	 */
+	if (type_may_be_null(rold->type) != type_may_be_null(rcur->type))
+		return false;
+
 	switch (base_type(rold->type)) {
 	case SCALAR_VALUE:
 		if (equal)
@@ -13098,22 +13113,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		}
 	case PTR_TO_MAP_KEY:
 	case PTR_TO_MAP_VALUE:
-		/* a PTR_TO_MAP_VALUE could be safe to use as a
-		 * PTR_TO_MAP_VALUE_OR_NULL into the same map.
-		 * However, if the old PTR_TO_MAP_VALUE_OR_NULL then got NULL-
-		 * checked, doing so could have affected others with the same
-		 * id, and we can't check for that because we lost the id when
-		 * we converted to a PTR_TO_MAP_VALUE.
-		 */
-		if (type_may_be_null(rold->type)) {
-			if (!type_may_be_null(rcur->type))
-				return false;
-			if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)))
-				return false;
-			/* Check our ids match any regs they're supposed to */
-			return check_ids(rold->id, rcur->id, idmap);
-		}
-
 		/* If the new min/max/var_off satisfy the old ones and
 		 * everything else matches, we are OK.
 		 */
Signature · 1 line
2.30.2
author maintainer
#4 lore raw

PATCH 4/7 bpf: reject non-exact register type matches in regsafe()

In reply to Andrii Nakryiko

Generalize the (somewhat implicit) rule of regsafe(), which states that if register types in old and current states do not match *exactly*, they can't be safely considered equivalent.

---
 kernel/bpf/verifier.c | 45 ++++++++++++++++++++-----------------------
 1 file changed, 21 insertions(+), 24 deletions(-)
kernel/bpf/verifier.c +21 -24
index 218a7ace4210..5133d0a5b0cb 100644
@@ -13075,18 +13075,28 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 	if (rcur->type == NOT_INIT)
 		return false;
 
-	/* Register types that are *not* MAYBE_NULL could technically be safe
-	 * to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE  is
-	 * safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point to
-	 * the same map).
+	/* Enforce that register types have to match exactly, including their
+	 * modifiers (like PTR_MAYBE_NULL, MEM_RDONLY, etc), as a general
+	 * rule.
+	 *
+	 * One can make a point that using a pointer register as unbounded
+	 * SCALAR would be technically acceptable, but this could lead to
+	 * pointer leaks because scalars are allowed to leak while pointers
+	 * are not. We could make this safe in special cases if root is
+	 * calling us, but it's probably not worth the hassle.
+	 *
+	 * Also, register types that are *not* MAYBE_NULL could technically be
+	 * safe to use as their MAYBE_NULL variants (e.g., PTR_TO_MAP_VALUE
+	 * is safe to be used as PTR_TO_MAP_VALUE_OR_NULL, provided both point
+	 * to the same map).
 	 * However, if the old MAYBE_NULL register then got NULL checked,
 	 * doing so could have affected others with the same id, and we can't
 	 * check for that because we lost the id when we converted to
 	 * a non-MAYBE_NULL variant.
 	 * So, as a general rule we don't allow mixing MAYBE_NULL and
-	 * non-MAYBE_NULL registers.
+	 * non-MAYBE_NULL registers as well.
 	 */
-	if (type_may_be_null(rold->type) != type_may_be_null(rcur->type))
+	if (rold->type != rcur->type)
 		return false;
 
 	switch (base_type(rold->type)) {
@@ -13095,22 +13105,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 			return true;
 		if (env->explore_alu_limits)
 			return false;
-		if (rcur->type == SCALAR_VALUE) {
-			if (!rold->precise)
-				return true;
-			/* new val must satisfy old val knowledge */
-			return range_within(rold, rcur) &&
-			       tnum_in(rold->var_off, rcur->var_off);
-		} else {
-			/* We're trying to use a pointer in place of a scalar.
-			 * Even if the scalar was unbounded, this could lead to
-			 * pointer leaks because scalars are allowed to leak
-			 * while pointers are not. We could make this safe in
-			 * special cases if root is calling us, but it's
-			 * probably not worth the hassle.
-			 */
-			return false;
-		}
+		if (!rold->precise)
+			return true;
+		/* new val must satisfy old val knowledge */
+		return range_within(rold, rcur) &&
+		       tnum_in(rold->var_off, rcur->var_off);
 	case PTR_TO_MAP_KEY:
 	case PTR_TO_MAP_VALUE:
 		/* If the new min/max/var_off satisfy the old ones and
@@ -13122,8 +13121,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		       check_ids(rold->id, rcur->id, idmap);
 	case PTR_TO_PACKET_META:
 	case PTR_TO_PACKET:
-		if (rcur->type != rold->type)
-			return false;
 		/* We must have at least as much range as the old ptr
 		 * did, so that any accesses which were safe before are
 		 * still safe.  This is true even if old range < old off,
Signature · 1 line
2.30.2
author maintainer
#5 lore raw

PATCH 5/7 bpf: perform byte-by-byte comparison only when necessary in regsafe()

In reply to Andrii Nakryiko

Extract byte-by-byte comparison of bpf_reg_state in regsafe() into a helper function, which makes it more convenient to use it "on demand" only for registers that benefit from such checks, instead of doing it all the time, even if result of such comparison is ignored.

Also, remove WARN_ON_ONCE(1)+return false dead code. There is no risk of missing some case as compiler will warn about non-void function not returning value in some branches (and that under assumption that default case is removed in the future).

---
 kernel/bpf/verifier.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +9 -12
index 5133d0a5b0cb..6431b994b3f6 100644
@@ -13057,18 +13057,19 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 	}
 }
 
+static bool regs_exact(const struct bpf_reg_state *rold,
+		       const struct bpf_reg_state *rcur)
+{
+	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
+}
+
 /* Returns true if (rold safe implies rcur safe) */
 static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		    struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)
 {
-	bool equal;
-
 	if (!(rold->live & REG_LIVE_READ))
 		/* explored state didn't use this */
 		return true;
-
-	equal = memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
-
 	if (rold->type == NOT_INIT)
 		/* explored state can't have used this */
 		return true;
@@ -13101,7 +13102,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
 	switch (base_type(rold->type)) {
 	case SCALAR_VALUE:
-		if (equal)
+		if (regs_exact(rold, rcur))
 			return true;
 		if (env->explore_alu_limits)
 			return false;
@@ -13144,15 +13145,11 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		/* two stack pointers are equal only if they're pointing to
 		 * the same stack frame, since fp-8 in foo != fp-8 in bar
 		 */
-		return equal && rold->frameno == rcur->frameno;
+		return regs_exact(rold, rcur) && rold->frameno == rcur->frameno;
 	default:
 		/* Only valid matches are exact, which memcmp() */
-		return equal;
+		return regs_exact(rold, rcur);
 	}
-
-	/* Shouldn't get here; if we do, say it's not safe */
-	WARN_ON_ONCE(1);
-	return false;
 }
 
 static bool stacksafe(struct bpf_verifier_env *env, struct bpf_func_state *old,
Signature · 1 line
2.30.2
author maintainer
#6 lore raw

PATCH 6/7 bpf: fix regs_exact() logic in regsafe() to remap IDs correctly

In reply to Andrii Nakryiko

Comparing IDs exactly between two separate states is not just suboptimal, but also incorrect in some cases. So update regs_exact() check to do byte-by-byte memcmp() only up to id/ref_obj_id. For id and ref_obj_id perform proper check_ids() checks, taking into account idmap.

This change makes more states equivalent improving insns and states stats across a bunch of selftest BPF programs:

File                                         Program                           Insns (A)  Insns (B)  Insns   (DIFF)  States (A)  States (B)  States (DIFF)
-------------------------------------------  --------------------------------  ---------  ---------  --------------  ----------  ----------  -------------
cgrp_kfunc_success.bpf.linked1.o             test_cgrp_get_release                   141        137     -4 (-2.84%)          13          13    +0 (+0.00%)
cgrp_kfunc_success.bpf.linked1.o             test_cgrp_xchg_release                  142        139     -3 (-2.11%)          14          13    -1 (-7.14%)
connect6_prog.bpf.linked1.o                  connect_v6_prog                         139        102   -37 (-26.62%)           9           6   -3 (-33.33%)
ima.bpf.linked1.o                            bprm_creds_for_exec                      68         61    -7 (-10.29%)           6           5   -1 (-16.67%)
linked_list.bpf.linked1.o                    global_list_in_list                     569        499   -70 (-12.30%)          60          52   -8 (-13.33%)
linked_list.bpf.linked1.o                    global_list_push_pop                    167        150   -17 (-10.18%)          18          16   -2 (-11.11%)
linked_list.bpf.linked1.o                    global_list_push_pop_multiple           881        815    -66 (-7.49%)          74          63  -11 (-14.86%)
linked_list.bpf.linked1.o                    inner_map_list_in_list                  579        534    -45 (-7.77%)          61          55    -6 (-9.84%)
linked_list.bpf.linked1.o                    inner_map_list_push_pop                 190        181     -9 (-4.74%)          19          18    -1 (-5.26%)
linked_list.bpf.linked1.o                    inner_map_list_push_pop_multiple        916        850    -66 (-7.21%)          75          64  -11 (-14.67%)
linked_list.bpf.linked1.o                    map_list_in_list                        588        525   -63 (-10.71%)          62          55   -7 (-11.29%)
linked_list.bpf.linked1.o                    map_list_push_pop                       183        174     -9 (-4.92%)          18          17    -1 (-5.56%)
linked_list.bpf.linked1.o                    map_list_push_pop_multiple              909        843    -66 (-7.26%)          75          64  -11 (-14.67%)
map_kptr.bpf.linked1.o                       test_map_kptr                           264        256     -8 (-3.03%)          26          26    +0 (+0.00%)
map_kptr.bpf.linked1.o                       test_map_kptr_ref                        95         91     -4 (-4.21%)           9           8   -1 (-11.11%)
task_kfunc_success.bpf.linked1.o             test_task_xchg_release                  139        136     -3 (-2.16%)          14          13    -1 (-7.14%)
test_bpf_nf.bpf.linked1.o                    nf_skb_ct_test                          815        509  -306 (-37.55%)          57          30  -27 (-47.37%)
test_bpf_nf.bpf.linked1.o                    nf_xdp_ct_test                          815        509  -306 (-37.55%)          57          30  -27 (-47.37%)
test_cls_redirect.bpf.linked1.o              cls_redirect                          78925      78390   -535 (-0.68%)        4782        4704   -78 (-1.63%)
test_cls_redirect_subprogs.bpf.linked1.o     cls_redirect                          64901      63897  -1004 (-1.55%)        4612        4470  -142 (-3.08%)
test_sk_lookup.bpf.linked1.o                 access_ctx_sk                           181         95   -86 (-47.51%)          19          10   -9 (-47.37%)
test_sk_lookup.bpf.linked1.o                 ctx_narrow_access                       447        437    -10 (-2.24%)          38          37    -1 (-2.63%)
test_sk_lookup_kern.bpf.linked1.o            sk_lookup_success                       148        133   -15 (-10.14%)          14          12   -2 (-14.29%)
test_tcp_check_syncookie_kern.bpf.linked1.o  check_syncookie_clsact                  304        300     -4 (-1.32%)          23          22    -1 (-4.35%)
test_tcp_check_syncookie_kern.bpf.linked1.o  check_syncookie_xdp                     304        300     -4 (-1.32%)          23          22    -1 (-4.35%)
test_verify_pkcs7_sig.bpf.linked1.o          bpf                                      87         76   -11 (-12.64%)           7           6   -1 (-14.29%)
-------------------------------------------  --------------------------------  ---------  ---------  --------------  ----------  ----------  -------------
---
 kernel/bpf/verifier.c | 23 ++++++++++++++++-------
 1 file changed, 16 insertions(+), 7 deletions(-)
kernel/bpf/verifier.c +16 -7
index 6431b994b3f6..b23812d2bb49 100644
@@ -12946,6 +12946,13 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)
 {
 	unsigned int i;
 
+	/* either both IDs should be set or both should be zero */
+	if (!!old_id != !!cur_id)
+		return false;
+
+	if (old_id == 0) /* cur_id == 0 as well */
+		return true;
+
 	for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
 		if (!idmap[i].old) {
 			/* Reached an empty slot; haven't seen this id before */
@@ -13058,9 +13065,12 @@ static void clean_live_states(struct bpf_verifier_env *env, int insn,
 }
 
 static bool regs_exact(const struct bpf_reg_state *rold,
-		       const struct bpf_reg_state *rcur)
+		       const struct bpf_reg_state *rcur,
+		       struct bpf_id_pair *idmap)
 {
-	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, parent)) == 0;
+	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 && 
+	       check_ids(rold->id, rcur->id, idmap) &&
+	       check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
 }
 
 /* Returns true if (rold safe implies rcur safe) */
@@ -13102,7 +13112,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 
 	switch (base_type(rold->type)) {
 	case SCALAR_VALUE:
-		if (regs_exact(rold, rcur))
+		if (regs_exact(rold, rcur, idmap))
 			return true;
 		if (env->explore_alu_limits)
 			return false;
@@ -13136,7 +13146,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		if (rold->off != rcur->off)
 			return false;
 		/* id relations must be preserved */
-		if (rold->id && !check_ids(rold->id, rcur->id, idmap))
+		if (!check_ids(rold->id, rcur->id, idmap))
 			return false;
 		/* new val must satisfy old val knowledge */
 		return range_within(rold, rcur) &&
@@ -13145,10 +13155,9 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		/* two stack pointers are equal only if they're pointing to
 		 * the same stack frame, since fp-8 in foo != fp-8 in bar
 		 */
-		return regs_exact(rold, rcur) && rold->frameno == rcur->frameno;
+		return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
 	default:
-		/* Only valid matches are exact, which memcmp() */
-		return regs_exact(rold, rcur);
+		return regs_exact(rold, rcur, idmap);
 	}
 }
 
Signature · 1 line
2.30.2
author maintainer
#7 lore raw

PATCH 7/7 bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

In reply to Andrii Nakryiko

Make default case in regsafe() safer. Instead of doing byte-by-byte comparison, take into account ID remapping and also range and var_off checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.

With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.

With these changes veristat shows no difference in verifier stats across selftests and Cilium BPF programs (which is a good thing).

---
 kernel/bpf/verifier.c | 26 ++++++++++++++------------
 1 file changed, 14 insertions(+), 12 deletions(-)
kernel/bpf/verifier.c +14 -12
index b23812d2bb49..7e0fa3924f01 100644
@@ -12919,8 +12919,8 @@ static int check_btf_info(struct bpf_verifier_env *env,
 }
 
 /* check %cur's range satisfies %old's */
-static bool range_within(struct bpf_reg_state *old,
-			 struct bpf_reg_state *cur)
+static bool range_within(const struct bpf_reg_state *old,
+			 const struct bpf_reg_state *cur)
 {
 	return old->umin_value <= cur->umin_value &&
 	       old->umax_value >= cur->umax_value &&
@@ -13073,6 +13073,17 @@ static bool regs_exact(const struct bpf_reg_state *rold,
 	       check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
 }
 
+static bool regs_equal(const struct bpf_reg_state *rold,
+		       const struct bpf_reg_state *rcur,
+		       struct bpf_id_pair *idmap)
+{
+	return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
+	       range_within(rold, rcur) &&
+	       tnum_in(rold->var_off, rcur->var_off) &&
+	       check_ids(rold->id, rcur->id, idmap) &&
+	       check_ids(rold->ref_obj_id, rcur->ref_obj_id, idmap);
+}
+
 /* Returns true if (rold safe implies rcur safe) */
 static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		    struct bpf_reg_state *rcur, struct bpf_id_pair *idmap)
@@ -13121,15 +13132,6 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		/* new val must satisfy old val knowledge */
 		return range_within(rold, rcur) &&
 		       tnum_in(rold->var_off, rcur->var_off);
-	case PTR_TO_MAP_KEY:
-	case PTR_TO_MAP_VALUE:
-		/* If the new min/max/var_off satisfy the old ones and
-		 * everything else matches, we are OK.
-		 */
-		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, var_off)) == 0 &&
-		       range_within(rold, rcur) &&
-		       tnum_in(rold->var_off, rcur->var_off) &&
-		       check_ids(rold->id, rcur->id, idmap);
 	case PTR_TO_PACKET_META:
 	case PTR_TO_PACKET:
 		/* We must have at least as much range as the old ptr
@@ -13157,7 +13159,7 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
 		 */
 		return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
 	default:
-		return regs_exact(rold, rcur, idmap);
+		return regs_equal(rold, rcur, idmap);
 	}
 }
 
Signature · 1 line
2.30.2
#8 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 1 line · Andrii Nakryiko

Make default case in regsafe() safer. Instead of doing byte-by-byte

I love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.

Quoted 1 line

comparison, take into account ID remapping and also range and var_off

ID remapping is handled by the patch 6 in regs_exact(). This patch adds range and var_off check as default. Which might not be correct in the future.

Quoted 5 lines

checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.

That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.

Quoted 5 lines

With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.

PTR_TO_BTF_ID with var_off would be a counter example where
such default of comparing ranges and var_off would lead to issues. Currently PTR_TO_BTF_ID doesn't allow var_off, but folks requested this support. The range_within() logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes. PTR_TO_BTF_ID with var_off would be wrong to do with just range_within().

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.
I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR, PTR_TO_BTF_ID and PTR_TO_MAP will be the majority of types we can special case them and refactor comparison to only things
that matter to these types. var_off and min/max_value are the biggest part of bpf_reg_state. They should be zero for PTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottest regsafe() function.
Same thing for SCALAR. Doing regs_exact() with big memcmp and then finer range_within() on the same bytes is probably wasteful and can be optimized.
We might consider reshuffling bpf_reg_state fields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.

I've applied the first 6 patches.

#9 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko

Make default case in regsafe() safer. Instead of doing byte-by-byte

I love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.

Quoted 1 line

comparison, take into account ID remapping and also range and var_off

ID remapping is handled by the patch 6 in regs_exact(). This patch adds range and var_off check as default. Which might not be correct in the future.

Quoted 8 lines
Quoted 5 lines

checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.

That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.

True, I think I had regs_exact() and regs_equals() change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.

Quoted 7 lines
Quoted 6 lines

With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.

Quoted 6 lines

PTR_TO_BTF_ID with var_off would be a counter example where
such default of comparing ranges and var_off would lead to issues. Currently PTR_TO_BTF_ID doesn't allow var_off, but folks requested this support. The range_within() logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes. PTR_TO_BTF_ID with var_off would be wrong to do with just range_within().

I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined var_off and range_within() would be incorrect.

Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?

Quoted 3 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 5 lines

Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.

yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.

Quoted 4 lines

I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR, PTR_TO_BTF_ID and PTR_TO_MAP will be the majority of types we can special case them and refactor comparison to only things
that matter to these types. var_off and min/max_value are the biggest part

Quoted 8 lines

of bpf_reg_state. They should be zero for PTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottest regsafe() function.
Same thing for SCALAR. Doing regs_exact() with big memcmp and then finer range_within() on the same bytes is probably wasteful and can be optimized.
We might consider reshuffling bpf_reg_state fields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.

I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.

Quoted 2 lines

I've applied the first 6 patches.

Cool, thanks, less patches to carry around. If you don't mind, let's look at this var_off concern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.

#10 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 49 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko

Make default case in regsafe() safer. Instead of doing byte-by-byte

I love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.

Quoted 1 line

comparison, take into account ID remapping and also range and var_off

ID remapping is handled by the patch 6 in regs_exact(). This patch adds range and var_off check as default. Which might not be correct in the future.

Quoted 8 lines
Quoted 5 lines

checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.

That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.

True, I think I had regs_exact() and regs_equals() change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.

Quoted 7 lines
Quoted 6 lines

With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.

Quoted 6 lines

PTR_TO_BTF_ID with var_off would be a counter example where
such default of comparing ranges and var_off would lead to issues. Currently PTR_TO_BTF_ID doesn't allow var_off, but folks requested this support. The range_within() logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes. PTR_TO_BTF_ID with var_off would be wrong to do with just range_within().

I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined var_off and range_within() would be incorrect.

Quoted 5 lines

Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?

Kumar's example was for a constant. range_within is the same as equality check, so we concluded it's safe for that case.
I'm worried about non uniformity of structs with types and general comparison of ranges.
I guess you're arguing that if old state had wider range than every single possible value from that range was already validated to be safe and hence new narrow range is safe too.
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'
// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)
More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Quoted 24 lines
Quoted 6 lines

Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.

yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.

Quoted 4 lines

I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR, PTR_TO_BTF_ID and PTR_TO_MAP will be the majority of types we can special case them and refactor comparison to only things
that matter to these types. var_off and min/max_value are the biggest part

Quoted 8 lines

of bpf_reg_state. They should be zero for PTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottest regsafe() function.
Same thing for SCALAR. Doing regs_exact() with big memcmp and then finer range_within() on the same bytes is probably wasteful and can be optimized.
We might consider reshuffling bpf_reg_state fields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.

Quoted 7 lines

I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.

Thank you. Lorenz was pondering at it at some point, but lost interest. I guess. I did a bunch of perf runs with our test_verif_scale* long ago.
The perf report used to be the same and stable for them. processed_insn and number of states affects both memory and speed and % wise have higher contribution to verifier speed, so any improvements there help more. Optimizing the actual regsafe() is secondary.
Just something to put on todo list.

Quoted 8 lines
Quoted 2 lines

I've applied the first 6 patches.

Cool, thanks, less patches to carry around. If you don't mind, let's look at this var_off concern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.

#11 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 57 lines · Alexei Starovoitov
Quoted 49 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 1 line · Andrii Nakryiko

Make default case in regsafe() safer. Instead of doing byte-by-byte

I love the patches 1-6, but this one is not making it safer. It looks to be going less safe route.
More below.

Quoted 1 line

comparison, take into account ID remapping and also range and var_off

ID remapping is handled by the patch 6 in regs_exact(). This patch adds range and var_off check as default. Which might not be correct in the future.

Quoted 8 lines
Quoted 5 lines

checks. For most of registers range and var_off will be zero (not set), which doesn't matter. For some, like PTR_TO_MAP_{KEY,VALUE}, this generalized logic is exactly matching what regsafe() was doing as a special case. But in any case, if register has id and/or ref_obj_id set, check it using check_ids() logic, taking into account idmap.

That was already done in patch 6. So the commit log is misleading. It's arguing that it's a benefit of this change while it was in the previous patch.

True, I think I had regs_exact() and regs_equals() change in one commit and split it at the last minute before submitting (I felt like patch #7 will be controversial ;) ), should have proofread messages more carefully. Sorry about that.

Quoted 7 lines
Quoted 6 lines

With these changes, default case should be handling most registers more correctly, and even for future register would be a good default. For some special cases, like PTR_TO_PACKET, one would still need to implement extra checks (like special handling of reg->range) to get better state equivalence, but default logic shouldn't be wrong.

Quoted 6 lines

PTR_TO_BTF_ID with var_off would be a counter example where
such default of comparing ranges and var_off would lead to issues. Currently PTR_TO_BTF_ID doesn't allow var_off, but folks requested this support. The range_within() logic is safe only for types like PTR_TO_MAP_KEY/VALUE that start from zero and have uniform typeless blob of bytes. PTR_TO_BTF_ID with var_off would be wrong to do with just range_within().

I'm trying to understand this future problem. I think this is the same issue that Kumar was trying to fix before, but when I asked for more specifics I didn't really get good answer of when this combined var_off and range_within() would be incorrect.

Quoted 5 lines

Do you mind showing (even if hypothetically) an example when var_off+range_within() won't work? I'm trying to understand this. We should either document why this is not safe, in general, or come to conclusion that it is safe. It's second time this comes up, so let's spend a bit of time getting to the bottom of this?

Quoted 11 lines

Kumar's example was for a constant. range_within is the same as equality check, so we concluded it's safe for that case.
I'm worried about non uniformity of structs with types and general comparison of ranges.
I guess you're arguing that if old state had wider range than every single possible value from that range was already validated to be safe and hence new narrow range is safe too.
It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'

a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.

But I probably misunderstood your example, sorry.

Quoted 11 lines

// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)

No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.

So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).

Quoted 13 lines

More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 4 lines

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.

For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.

But just to take a step back, from my perspective var_off and range_within are complementary and solve slightly different uses, but should be both satisfied:
- var_off is not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.
- range_within() can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.

So while I previously thought that we can do away without var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possible var_off + range_within situation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.

Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.

Quoted 33 lines
Quoted 25 lines
Quoted 7 lines

Having said all that the focus on safety should be balanced with focus on performance of the verifier itself.
The regsafe is the hottest function.
That first memcmp used to be the hottest part of the whole verifier.

yeah, and it was done unconditionally even if not needed, which was kind of weird when I started looking at this. Probably some refactoring leftover.

Quoted 4 lines

I suspect this refactoring won't change the perf profile, but we can optimize it. Assuming that SCALAR, PTR_TO_BTF_ID and PTR_TO_MAP will be the majority of types we can special case them and refactor comparison to only things
that matter to these types. var_off and min/max_value are the biggest part

Quoted 8 lines

of bpf_reg_state. They should be zero for PTR_TO_BTF_ID, but we already check that in other parts of the verifier. There is no need to compare zeros again in the hottest regsafe() function.
Same thing for SCALAR. Doing regs_exact() with big memcmp and then finer range_within() on the same bytes is probably wasteful and can be optimized.
We might consider reshuffling bpf_reg_state fields again depending on cache line usage. I suspect doing "smart" reg comparison we will be able to significantly improve verification speed. Please consider for a follow up.

Quoted 7 lines

I agree. Perf wasn't the point for me (this is a preliminary for iterator stuff to improve state equivalence checks), so I didn't want to spend extra time on this (especially that benchmarking this properly is time consuming, as benchmarking under QEMU isn't representative (from me experiences with BPF ringbuf benchmarking). But I'll keep it on TODO list, either for me or anyone interested in contributing.

Quoted 7 lines

Thank you. Lorenz was pondering at it at some point, but lost interest. I guess. I did a bunch of perf runs with our test_verif_scale* long ago.
The perf report used to be the same and stable for them. processed_insn and number of states affects both memory and speed and % wise have higher contribution to verifier speed, so any improvements there help more. Optimizing the actual regsafe() is secondary.
Just something to put on todo list.

Sure. With veristat we can also have a more aggregated view across multiple object files (and we can add some mode to veristat to repeatedly load each program for N times to help with profile collection).

Quoted 9 lines
Quoted 9 lines
Quoted 3 lines

I've applied the first 6 patches.

Cool, thanks, less patches to carry around. If you don't mind, let's look at this var_off concern in details. I can send PTR_TO_MEM-specific follow up fix, but if we can convince ourselves that generic logic is safe and future-proof, I'd rather do a generic change.

#12 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines

It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'

a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.

Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.

Quoted 14 lines

But I probably misunderstood your example, sorry.

Quoted 11 lines

// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)

Quoted 6 lines

No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.

Correct. The issue would apply to regular scalar if such 'within' operation was available.

Quoted 4 lines

So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).

Yes. I personally don't believe that doing range_within for all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example with range_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.

Quoted 18 lines
Quoted 13 lines

More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 4 lines

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Quoted 7 lines

Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.

For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.

Likely yes, but why?
You're trying hard to collapse the switch statement in regsafe() while claiming it's a safer way. I don't see it this way.
For example the upcoming active_lock_id would need its own check_ids() call. It will be necessary for PTR_TO_BTF_ID only.
Why collapse the switch into 'default:' just to bring some back? The default without checking active_lock_id through check_ids would be wrong, so collapsed switch doesn't make things safer.

Quoted 10 lines

But just to take a step back, from my perspective var_off and range_within are complementary and solve slightly different uses, but should be both satisfied:
- var_off is not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.

Right. var_off is used for alignment checking too. grep tnum_is_aligned. We have bare minimum of testing for that though.
Only few tests in the test_verifier use BPF_F_STRICT_ALIGNMENT

Quoted 2 lines

- range_within() can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.

Right.

Quoted 6 lines

So while I previously thought that we can do away without var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possible var_off + range_within situation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.

Right. Likely true.

Quoted 2 lines

Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.

Not sure what conclusion you're looking for.

#13 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines

It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'

a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.

Quoted 2 lines

Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.

I just don't know what kind of instruction has this "within" semantics, that's why I was confused.

Quoted 30 lines
Quoted 15 lines

But I probably misunderstood your example, sorry.

Quoted 11 lines

// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)

Quoted 6 lines

No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.

Correct. The issue would apply to regular scalar if such 'within' operation was available.

Quoted 4 lines

So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).

Quoted 6 lines

Yes. I personally don't believe that doing range_within for all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example with range_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.

Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.

Quoted 22 lines
Quoted 22 lines
Quoted 14 lines

More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 4 lines

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.

Quoted 6 lines
Quoted 4 lines

For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.

Likely yes, but why?

No reason, just seems sane. But it also doesn't matter for the discussion at hand.

Quoted 7 lines

You're trying hard to collapse the switch statement in regsafe() while claiming it's a safer way. I don't see it this way.
For example the upcoming active_lock_id would need its own check_ids() call. It will be necessary for PTR_TO_BTF_ID only.
Why collapse the switch into 'default:' just to bring some back? The default without checking active_lock_id through check_ids would be wrong, so collapsed switch doesn't make things safer.

I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like PTR_TO_MEM and PTR_TO_BUF in the future.

Your point is that some register will need a custom/extra check is correct, obviously (just like we have PTR_TO_STACK extra frameno check), and doesn't contradict what I'm saying. We still need to be careful for new register types or further changes to existing ones.

Quoted 28 lines
Quoted 11 lines

But just to take a step back, from my perspective var_off and range_within are complementary and solve slightly different uses, but should be both satisfied:
- var_off is not precise with range boundaries (due to some bits too
coarsely marked as unknown), but it's useful to enforce having a value being a multiple of some power-of-2 (e.g., knowing for sure that lowest 2 bits are zero means that value is multiple of 4; I haven't checked, but I assume we check with for various pointer accesses to ensure we don't have misaligned reads). They can be only approximately used for actual possible range of values.

Right. var_off is used for alignment checking too. grep tnum_is_aligned. We have bare minimum of testing for that though.
Only few tests in the test_verifier use BPF_F_STRICT_ALIGNMENT

Quoted 2 lines

- range_within() can and should be used for *precise* range of value
tracking, but it can't express that alignment restriction.

Right.

Quoted 6 lines

So while I previously thought that we can do away without var_off, I now think there are cases when it's necessary. But if we are sure that we handle any SCALAR case correctly for any possible var_off + range_within situation, it should be fine to do that for any mem-like pointer just as much, as var_off+range_within is basically a MEM + SCALAR combined case.

Quoted 6 lines

Right. Likely true.

Quoted 2 lines

Anyways, I'm not blocked on this, but I think we'll benefit from taking this discussion to its logical conclusion.

Not sure what conclusion you're looking for.

Seeing if I'm missing something. Now I don't think I am. That's the conclusion I was looking for.

We don't have to make the default case do range_within(), I'll just explicitly add PTR_TO_MEM and PTR_TO_BUF into PTR_TO_MAP_{VALUE,KEY} case in a future patch set.

#14 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 103 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines

It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'

a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.

Quoted 2 lines

Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.

I just don't know what kind of instruction has this "within" semantics, that's why I was confused.

Quoted 30 lines
Quoted 15 lines

But I probably misunderstood your example, sorry.

Quoted 11 lines

// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)

Quoted 6 lines

No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.

Correct. The issue would apply to regular scalar if such 'within' operation was available.

Quoted 4 lines

So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).

Quoted 6 lines

Yes. I personally don't believe that doing range_within for all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example with range_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.

Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.

Quoted 22 lines
Quoted 22 lines
Quoted 14 lines

More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 4 lines

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.

Quoted 6 lines
Quoted 4 lines

For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.

Likely yes, but why?

No reason, just seems sane. But it also doesn't matter for the discussion at hand.

Quoted 7 lines

You're trying hard to collapse the switch statement in regsafe() while claiming it's a safer way. I don't see it this way.
For example the upcoming active_lock_id would need its own check_ids() call. It will be necessary for PTR_TO_BTF_ID only.
Why collapse the switch into 'default:' just to bring some back? The default without checking active_lock_id through check_ids would be wrong, so collapsed switch doesn't make things safer.

Quoted 4 lines

I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like PTR_TO_MEM and PTR_TO_BUF in the future.

Wait. What do you mean 'miss cases like PTR_TO_MEM' ?
With 'switch() default: regs_exact()'
it's not a safety issue that PTR_TO_MEM doesn't do range_within() like PTR_TO_MAP_KEY. The verifier is unnecessary conservative with PTR_TO_MEM.
Applying range_within() will allow more valid programs to be accepted. What did I miss?
Or all this time I've been misreading your 'saner' default as 'safer' default?

#15 lore raw

Re: [PATCH bpf-next 7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe()

Quoted 110 lines · Alexei Starovoitov
Quoted 103 lines · Andrii Nakryiko
Quoted 14 lines · Alexei Starovoitov
Quoted 11 lines · Andrii Nakryiko
Quoted 4 lines

It sounds logical, but it can get tricky with ranges and branch taken logic. Consider something like:
R1=(min=2,max=8), R2=(min=1, max=10)
if (R1 within R2) // bpf prog is doing its own 'within'

a bit confused what is "R1 within R2" here and what you mean "bpf prog is doing its own 'within'"? Any sort of R1 < R2 checks (and any other op: <=, >=, etc) can't really kick in branch elimination because R2_min=1 < R1_max=8, so arithmetically speaking we can't conclude that "R1 is always smaller than R2", so both branches would have to be examined.

Quoted 2 lines

Something like that. Details didn't matter to me.
It was hypothetical 'within' operation just to illustrate the point.

I just don't know what kind of instruction has this "within" semantics, that's why I was confused.

Quoted 30 lines
Quoted 15 lines

But I probably misunderstood your example, sorry.

Quoted 11 lines

// branch taken kicks in
else
// issues that were never checked

Now new state has:
R1=(min=4,max=6), R2=(min=5, max=5)

Both R1 and R2 of new state individually range_within of old safe state, but together the prog may go to the unverified path.
Not sure whether it's practical today.
You asked for hypothetical, so here it goes :)

Quoted 6 lines

No problem with "hypothetical-ness". But my confusion and argument is similarly "in principle"-like. Because if such an example above can be constructed then this would be an issue for SCALAR as well, right? And if you can bypass verifier's safety with SCALAR, you (hypothetically) could use that SCALAR to do out-of-bounds memory access by adding this SCALAR to some mem-like register.

Correct. The issue would apply to regular scalar if such 'within' operation was available.

Quoted 4 lines

So that's my point and my source of confusion: if we don't trust var_off+range_within() logic to handle *all* situations correctly, then we should be worried about SCALARs just as much as anything else (unless, as usual, I missed something).

Quoted 6 lines

Yes. I personally don't believe that doing range_within for all regtypes by default is a safer way forward.
The example wasn't real. It was trying to demonstrate a possible issue. You insist to see a real example with range_within.
I don't have it. It's a gut feel that it could be there because I could construct it with fake 'within'.

Ok, so some new instruction with "within" semantics would be necessary. I was just trying to see if I'm missing some existing potential case. Seems like not, that's fine.

Quoted 22 lines
Quoted 22 lines
Quoted 14 lines

More gut feel than real issue.

Quoted 10 lines
Quoted 4 lines

SCALARS and PTR_TO_BTF_ID will likely dominate future bpf progs. Keeping default as regs_exact (that does ID match) is safer default.

It's fine, though the point of this patch set was patch #7, enabling logic similar to PTR_TO_MAP_VALUE for PTR_TO_MEM and PTR_TO_BUF. I can send specific fixes for that, no problem. But as I said above, I'm really curious to understand what kind of situations will lead to unsafety if we do var_off+range_within checks.

Quoted 4 lines

PTR_TO_MEM and PTR_TO_BUF explicitly are likely ok despite my convoluted example above.
I'm less sure about PTR_TO_BTF_ID. It could be ok.
Just feels safer to opt-in each type explicitly.

Sure, I can just do a simple opt-in, no problem. As I said, mostly trying to understand the issue overall.

Quoted 6 lines
Quoted 4 lines

For PTR_TO_BTF_ID specifically, I can see how we can enable var_off+range_within for cases when we access some array, right? But then I think we'll be enforcing that we are staying within the boundaries of a single array field, never crossing into another field.

Likely yes, but why?

No reason, just seems sane. But it also doesn't matter for the discussion at hand.

Quoted 7 lines

You're trying hard to collapse the switch statement in regsafe() while claiming it's a safer way. I don't see it this way.
For example the upcoming active_lock_id would need its own check_ids() call. It will be necessary for PTR_TO_BTF_ID only.
Why collapse the switch into 'default:' just to bring some back? The default without checking active_lock_id through check_ids would be wrong, so collapsed switch doesn't make things safer.

Quoted 4 lines

I'm saying it's sane default and is better than what we have today. The reason I want(ed) to make default case doing proper range checks (if they are set) is so that we don't miss cases like PTR_TO_MEM and PTR_TO_BUF in the future.

Quoted 6 lines

Wait. What do you mean 'miss cases like PTR_TO_MEM' ?
With 'switch() default: regs_exact()'
it's not a safety issue that PTR_TO_MEM doesn't do range_within() like PTR_TO_MAP_KEY. The verifier is unnecessary conservative with PTR_TO_MEM.
Applying range_within() will allow more valid programs to be accepted. What did I miss?

I don't think you missed anything. This was all exactly to allow the verifier to see that two PTR_TO_MEM (and PTR_TO_BUF, and whatnot) registers are compatible, even if their ranges are not exactly matching. This is just an inefficiency in state comparison right now (and potentially missed infinite loop detection, but that's also just inefficiency), but it becomes an issue with open-coded iterators because state equivalence is necessary to conclude that loop actually terminates safely.

Quoted 1 line

Or all this time I've been misreading your 'saner' default as 'safer' default?

I meant "saner" (with 'n') as "better and more flexible without
compromising safety".

#16 lore raw
In reply to Andrii Nakryiko
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 6 lines · On Thu, 22 Dec 2022 21:49:14 -0800 you wrote:

This patch set fixes, improves, and refactors parts of BPF verifier's state equivalence checks.

Patch #1 fixes refsafe(), making it take into account ID map when comparing reference IDs. See patch for details.

Quoted 7 lines

Patches #2-#7 refactor regsafe() function which compares two register states across old and current states. regsafe() is critical piece of logic, so to make it easier to review and validate refactorings and logic fixes and improvements, each patch makes a small change, explaining why the change is correct and makes sense. Please see individual patches for details.

[...]

Here is the summary with links:
- [bpf-next,1/7] bpf: teach refsafe() to take into account ID remapping

    https://git.kernel.org/bpf/bpf-next/c/e8f55fcf7779
  - [bpf-next,2/7] bpf: reorganize struct bpf_reg_state fields
    https://git.kernel.org/bpf/bpf-next/c/a73bf9f2d969
  - [bpf-next,3/7] bpf: generalize MAYBE_NULL vs non-MAYBE_NULL rule
    https://git.kernel.org/bpf/bpf-next/c/7f4ce97cd5ed
  - [bpf-next,4/7] bpf: reject non-exact register type matches in regsafe()
    https://git.kernel.org/bpf/bpf-next/c/910f69996674
  - [bpf-next,5/7] bpf: perform byte-by-byte comparison only when necessary in regsafe()
    https://git.kernel.org/bpf/bpf-next/c/4a95c85c9948
  - [bpf-next,6/7] bpf: fix regs_exact() logic in regsafe() to remap IDs correctly
    https://git.kernel.org/bpf/bpf-next/c/4633a0068258

- [bpf-next,7/7] bpf: unify PTR_TO_MAP_{KEY,VALUE} with default case in regsafe() (no matching commit)

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html