On 25/06/18 04:03AM, Eduard Zingerman wrote:
> On Sun, 2025-06-15 at 08:59 +0000, Anton Protopopov wrote:
>
> [...]
>
> > 0: r3 = r1 # "switch (r3)"
> > 1: if r3 > 0x13 goto +0x666 # check r3 boundaries
> > 2: r3 <<= 0x3 # r3 is void*, point to an address
> > 3: r1 = 0xbeef ll # r1 is PTR_TO_MAP_VALUE, r1->map_ptr=M
> > 5: r1 += r3 # r1 inherits boundaries from r3
> > 6: r1 = *(u64 *)(r1 + 0x0) # r1 now has type INSN_TO_PTR
> ^^^^^^^^^^^
> PTR_TO_INSN?
Heh, thanks, fill fix. [It's C, so a[1] and 1[a] means the same :-)]
> > 7: gotox r1[,imm=fd(M)] # verifier checks that M == r1->map_ptr
>
> [...]
>
> > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> > index 37dc83d91832..d20f6775605d 100644
> > --- a/arch/x86/net/bpf_jit_comp.c
> > +++ b/arch/x86/net/bpf_jit_comp.c
> > @@ -2520,6 +2520,13 @@ st: if (is_imm8(insn->off))
> >
> > break;
> >
> > + case BPF_JMP | BPF_JA | BPF_X:
> > + case BPF_JMP32 | BPF_JA | BPF_X:
>
> Is it necessary to add both JMP and JMP32 versions?
> Do we need to extend e.g. bpf_jit_supports_insn() and report an error
> in verifier.c or should we rely on individual jits to report unknown
> instruction?
Hmm, should I just leave BPF_JMP? Or just leave as is and do not distinguish?
>
> > + emit_indirect_jump(&prog,
> > + reg2hex[insn->dst_reg],
> > + is_ereg(insn->dst_reg),
> > + image + addrs[i - 1]);
> > + break;
> > case BPF_JMP | BPF_JA:
> > case BPF_JMP32 | BPF_JA:
> > if (BPF_CLASS(insn->code) == BPF_JMP) {
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index 008bcd44c60e..3c5eaea2b476 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -952,6 +952,7 @@ enum bpf_reg_type {
> > PTR_TO_ARENA,
> > PTR_TO_BUF, /* reg points to a read/write buffer */
> > PTR_TO_FUNC, /* reg points to a bpf program function */
> > + PTR_TO_INSN, /* reg points to a bpf program instruction */
> > CONST_PTR_TO_DYNPTR, /* reg points to a const struct bpf_dynptr */
> > __BPF_REG_TYPE_MAX,
> >
> > @@ -3601,6 +3602,7 @@ int bpf_insn_set_ready(struct bpf_map *map);
> > void bpf_insn_set_release(struct bpf_map *map);
> > void bpf_insn_set_adjust(struct bpf_map *map, u32 off, u32 len);
> > void bpf_insn_set_adjust_after_remove(struct bpf_map *map, u32 off, u32 len);
> > +int bpf_insn_set_iter_xlated_offset(struct bpf_map *map, u32 iter_no);
>
> This is a horrible name:
> - this function is not an iterator;
> - it is way too long.
>
> Maybe make it a bit more complex but convenient to use, e.g.:
>
> struct bpf_iarray_iter {
> struct bpf_map *map;
> u32 idx;
> };
>
> struct bpf_iset_iter bpf_iset_make_iter(struct bpf_map *map, u32 lo, u32 hi);
> bool bpf_iset_iter_next(struct bpf_iarray_iter *it, u32 *offset); // still a horrible name
>
> This would hide the manipulation with unique indices from verifier.c.
>
> ?
How about just bpf_insn_set_next[_unique]_offset()?
>
> >
> > struct bpf_insn_ptr {
> > void *jitted_ip;
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 84b5e6b25c52..80d9afcca488 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -229,6 +229,10 @@ struct bpf_reg_state {
> > enum bpf_reg_liveness live;
> > /* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
> > bool precise;
> > +
> > + /* Used to track boundaries of a PTR_TO_INSN */
> > + u32 min_index;
> > + u32 max_index;
>
> Use {umin,umax}_value instead?
Please see my comments in the reply to Alexei.
> > };
> >
> > enum bpf_stack_slot_type {
> > diff --git a/kernel/bpf/bpf_insn_set.c b/kernel/bpf/bpf_insn_set.c
> > index c20e99327118..316cecad60a9 100644
> > --- a/kernel/bpf/bpf_insn_set.c
> > +++ b/kernel/bpf/bpf_insn_set.c
> > @@ -9,6 +9,8 @@ struct bpf_insn_set {
> > struct bpf_map map;
> > struct mutex state_mutex;
> > int state;
> > + u32 **unique_offsets;
>
> Why is this a pointer to pointer?
> bpf_insn_set_iter_xlated_offset() is only used during check_cfg() and
> main verification. At that point no instruction movement occurred yet,
> so no need to track `&insn_set->ptrs[i].user_value.xlated_off`?
>
> > + u32 unique_offsets_cnt;
> > long *ips;
> > DECLARE_FLEX_ARRAY(struct bpf_insn_ptr, ptrs);
> > };
>
> [...]
>
> > @@ -15296,6 +15330,22 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
> > return 0;
> > }
> >
> > + if (dst_reg->type == PTR_TO_MAP_VALUE && map_is_insn_set(dst_reg->map_ptr)) {
> > + if (opcode != BPF_ADD) {
> > + verbose(env, "Operation %s on ptr to instruction set map is prohibited\n",
> > + bpf_alu_string[opcode >> 4]);
> > + return -EACCES;
> > + }
> > + src_reg = ®s[insn->src_reg];
> > + if (src_reg->type != SCALAR_VALUE) {
> > + verbose(env, "Adding non-scalar R%d to an instruction ptr is prohibited\n",
> > + insn->src_reg);
> > + return -EACCES;
> > + }
> > + dst_reg->min_index = src_reg->umin_value / sizeof(long);
> > + dst_reg->max_index = src_reg->umax_value / sizeof(long);
> > + }
> > +
>
> What if there are several BPF_ADD on the same PTR_TO_MAP_VALUE in a row?
> Shouldn't the {min,max}_index be accumulated in that case?
>
> Nit: this should be handled inside adjust_ptr_min_max_vals().
Yes, thanks, I've had this in my TBDs list for the next version. (All
"legal" cases generated by LLVM just do one add, so I've skipped it.)
> > if (dst_reg->type != SCALAR_VALUE)
> > ptr_reg = dst_reg;
> >
>
> [...]
>
> > @@ -17552,6 +17607,62 @@ static int mark_fastcall_patterns(struct bpf_verifier_env *env)
>
> [...]
>
> > +/* "conditional jump with N edges" */
> > +static int visit_goto_x_insn(int t, struct bpf_verifier_env *env, int fd)
> > +{
> > + struct bpf_map *map;
> > + int ret;
> > +
> > + ret = add_used_map(env, fd, &map);
> > + if (ret < 0)
> > + return ret;
> > +
> > + if (map->map_type != BPF_MAP_TYPE_INSN_SET)
> > + return -EINVAL;
>
> Nit: print something in the log?
Yes, thanks.
>
> > +
> > + return push_goto_x_edge(t, env, map);
> > +}
> > +
>
> [...]
>
> > @@ -18786,11 +18904,22 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat
> > struct bpf_func_state *cur, u32 insn_idx, enum exact_level exact)
> > {
> > u16 live_regs = env->insn_aux_data[insn_idx].live_regs_before;
> > + struct bpf_insn *insn;
> > u16 i;
> >
> > if (old->callback_depth > cur->callback_depth)
> > return false;
> >
> > + insn = &env->prog->insnsi[insn_idx];
> > + if (insn_is_gotox(insn)) {
> > + struct bpf_reg_state *old_dst = &old->regs[insn->dst_reg];
> > + struct bpf_reg_state *cur_dst = &cur->regs[insn->dst_reg];
> > +
> > + if (old_dst->min_index != cur_dst->min_index ||
> > + old_dst->max_index != cur_dst->max_index)
> > + return false;
> > + }
> > +
>
> Concur with Alexei, this should be handled by regsafe().
> Also, having cur_dst as a subset of old_dst should be fine.
Thanks, yes to both.
> > for (i = 0; i < MAX_BPF_REG; i++)
> > if (((1 << i) & live_regs) &&
> > !regsafe(env, &old->regs[i], &cur->regs[i],
> > @@ -19654,6 +19783,55 @@ static int process_bpf_exit_full(struct bpf_verifier_env *env,
> > return PROCESS_BPF_EXIT;
> > }
> >
> > +static int check_indirect_jump(struct bpf_verifier_env *env, struct bpf_insn *insn)
> > +{
> > + struct bpf_verifier_state *other_branch;
> > + struct bpf_reg_state *dst_reg;
> > + struct bpf_map *map;
> > + int xoff;
> > + int err;
> > + u32 i;
> > +
> > + /* this map should already have been added */
> > + err = add_used_map(env, insn->imm, &map);
> > + if (err < 0)
> > + return err;
> > +
> > + dst_reg = reg_state(env, insn->dst_reg);
> > + if (dst_reg->type != PTR_TO_INSN) {
> > + verbose(env, "BPF_JA|BPF_X R%d has type %d, expected PTR_TO_INSN\n",
> > + insn->dst_reg, dst_reg->type);
> > + return -EINVAL;
> > + }
> > +
> > + if (dst_reg->map_ptr != map) {
> > + verbose(env, "BPF_JA|BPF_X R%d was loaded from map id=%u, expected id=%u\n",
> > + insn->dst_reg, dst_reg->map_ptr->id, map->id);
> > + return -EINVAL;
> > + }
> > +
> > + if (dst_reg->max_index >= map->max_entries)
> > + return -EINVAL;
> > +
> > + for (i = dst_reg->min_index + 1; i <= dst_reg->max_index; i++) {
>
> Why +1 is needed in `i = dst_reg->min_index + 1`?
We want to "jump" to states {min,min+1,...,max} so we push states
{min+1,...,max} and continue the current state with the `jump
M[min]`:
env->insn_idx = bpf_insn_set_iter_xlated_offset(map, dst_reg->min_index);
> > + xoff = bpf_insn_set_iter_xlated_offset(map, i);
> > + if (xoff == -ENOENT)
> > + break;
> > + if (xoff < 0)
> > + return xoff;
> > +
> > + other_branch = push_stack(env, xoff, env->insn_idx, false);
> > + if (!other_branch)
> > + return -EFAULT;
>
> Nit: `return -ENOMEM`.
Ok, thanks.
>
> > + }
> > +
> > + env->insn_idx = bpf_insn_set_iter_xlated_offset(map, dst_reg->min_index);
> > + if (env->insn_idx < 0)
> > + return env->insn_idx;
> > +
> > + return 0;
> > +}
> > +
> > static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)
> > {
> > int err;
>
> [...]
>
