From 4c3a56544b65d50b68c48d5d7829feb455ac7ade Mon Sep 17 00:00:00 2001 From: Eduard Zingerman Date: Fri, 9 Oct 2026 03:47:47 -0700 Subject: bpf: Add bpf_same_memory_origin() When dealing with loops like: for (ptr = ...; ptr < end_ptr; ptr += 8) ... Scalar evolution needs to know if ptr and end_ptr identify a same memory location (possibly with different offsets). If they do, it is sound to attempt to infer iteration bounds for such a loop. Signed-off-by: Eduard Zingerman Signed-off-by: Alexei Starovoitov Link: https://patch.msgid.link/20261009-scev-minimal-rebase-v3-29-bcba9bc53ac9@gmail.com --- kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) (limited to 'kernel/bpf') diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index f8e6b40c2121..bf0722752e76 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17280,6 +17280,55 @@ clear_id: return 0; } +/* + * Many checks done by this function are quite conservative. + * This is because main verification pass does not maintain + * enough information to track object identities for some + * of the interesting types, e.g. PTR_TO_MEM. + */ +bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, + const struct bpf_reg_state *reg_b) +{ + if (reg_a == reg_b) + return true; + /* Require matching flags and base types. */ + if (reg_a->type != reg_b->type) + return false; + /* NULL can't be compared to some base+offset pointer. */ + if (type_may_be_null(reg_a->type)) + return false; + + switch (base_type(reg_a->type)) { + case PTR_TO_STACK: + return reg_a->frameno == reg_b->frameno; + case PTR_TO_MAP_VALUE: + if (reg_a->map_ptr != reg_b->map_ptr || reg_a->map_uid != reg_b->map_uid) + return false; + if (reg_a->id && reg_a->id == reg_b->id) + return true; + /* + * A plain single-element array has one stable value address, + * but not when BPF_F_INNER_MAP is set, see arraymap.c:array_map_meta_equal(). + */ + if (reg_a->map_ptr->map_type == BPF_MAP_TYPE_ARRAY && + reg_a->map_ptr->max_entries == 1 && + !(reg_a->map_ptr->map_flags & BPF_F_INNER_MAP)) + return true; + /* + * The rules above can be simplified / relaxed if: + * - fresh IDs would always be assigned for map-value lookups; + * - direct map value loads would always have and ID of zero. + */ + return false; + case PTR_TO_MEM: + case PTR_TO_BUF: + return reg_a->id && reg_a->id == reg_b->id; + + default: + return false; + } +} + int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, struct cnum64 range, u16 base, u16 step) { -- cgit v1.2.3