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 --- include/linux/bpf_verifier.h | 2 ++ kernel/bpf/verifier.c | 45 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 47 insertions(+) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 13c7825bb8b5..7e858bb05dd1 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1814,6 +1814,8 @@ struct arg_access_info bpf_kfunc_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *insn, int arg, int insn_idx); int bpf_compute_subprog_arg_access(struct bpf_verifier_env *env); +bool bpf_same_memory_origin(const struct bpf_reg_state *reg_a, + const struct bpf_reg_state *reg_b); int bpf_set_reg_range(struct bpf_verifier_env *env, struct bpf_reg_state *reg, struct cnum64 range, u16 base, u16 step); int bpf_reg_union(struct bpf_verifier_env *env, struct bpf_reg_state *acc, diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 28c16e35b1f3..9e1c08caa0db 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -17153,6 +17153,51 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, 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. */ + if (reg_a->map_ptr->map_type == BPF_MAP_TYPE_ARRAY && + reg_a->map_ptr->max_entries == 1) + 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) { -- 2.53.0