Re: [RFC bpf-next 5/9] bpf, x86: add support for indirect jumps

[Eduard Zingerman <eddyz87@gmail.com>]

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?

>     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?

> +			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.

?

>  
>  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?

>  };
>  
>  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 = &regs[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().

>  	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?

> +
> +	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.

>  	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`?

> +		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`.

> +	}
> +
> +	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;

[...]