Re: [PATCH v11 bpf-next 08/12] bpf, x86: add support for indirect jumps

[Anton Protopopov <a.s.protopopov@gmail.com>]

On 25/11/05 02:42PM, Alexei Starovoitov wrote:
> On Wed, Nov 5, 2025 at 12:58 AM Anton Protopopov
> <a.s.protopopov@gmail.com> wrote:
> >
> > Add support for a new instruction
> >
> >     BPF_JMP|BPF_X|BPF_JA, SRC=0, DST=Rx, off=0, imm=0
> >
> > which does an indirect jump to a location stored in Rx.  The register
> > Rx should have type PTR_TO_INSN. This new type assures that the Rx
> > register contains a value (or a range of values) loaded from a
> > correct jump table – map of type instruction array.
> >
> > For example, for a C switch LLVM will generate the following code:
> >
> >     0:   r3 = r1                    # "switch (r3)"
> >     1:   if r3 > 0x13 goto +0x666   # check r3 boundaries
> >     2:   r3 <<= 0x3                 # adjust to an index in array of addresses
> >     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
> >     7:   gotox r1                   # jit will generate proper code
> >
> > Here the gotox instruction corresponds to one particular map. This is
> > possible however to have a gotox instruction which can be loaded from
> > different maps, e.g.
> >
> >     0:   r1 &= 0x1
> >     1:   r2 <<= 0x3
> >     2:   r3 = 0x0 ll                # load from map M_1
> >     4:   r3 += r2
> >     5:   if r1 == 0x0 goto +0x4
> >     6:   r1 <<= 0x3
> >     7:   r3 = 0x0 ll                # load from map M_2
> >     9:   r3 += r1
> >     A:   r1 = *(u64 *)(r3 + 0x0)
> >     B:   gotox r1                   # jump to target loaded from M_1 or M_2
> >
> > During check_cfg stage the verifier will collect all the maps which
> > point to inside the subprog being verified. When building the config,
> > the high 16 bytes of the insn_state are used, so this patch
> > (theoretically) supports jump tables of up to 2^16 slots.
> >
> > During the later stage, in check_indirect_jump, it is checked that
> > the register Rx was loaded from a particular instruction array.
> >
> > Signed-off-by: Anton Protopopov <a.s.protopopov@gmail.com>
> > Acked-by: Eduard Zingerman <eddyz87@gmail.com>
> > ---
> >  arch/x86/net/bpf_jit_comp.c  |   3 +
> >  include/linux/bpf.h          |   1 +
> >  include/linux/bpf_verifier.h |   9 +
> >  kernel/bpf/bpf_insn_array.c  |  15 ++
> >  kernel/bpf/core.c            |   1 +
> >  kernel/bpf/liveness.c        |   3 +
> >  kernel/bpf/log.c             |   1 +
> >  kernel/bpf/verifier.c        | 373 ++++++++++++++++++++++++++++++++++-
> >  8 files changed, 400 insertions(+), 6 deletions(-)
> >
> > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> > index bbd2b03d2b74..36a0d4db9f68 100644
> > --- a/arch/x86/net/bpf_jit_comp.c
> > +++ b/arch/x86/net/bpf_jit_comp.c
> > @@ -2628,6 +2628,9 @@ st:                       if (is_imm8(insn->off))
> >
> >                         break;
> >
> > +               case BPF_JMP | BPF_JA | BPF_X:
> > +                       emit_indirect_jump(&prog, 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 9d41a6affcef..09d5dc541d1c 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -1001,6 +1001,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,
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 6b820d8d77af..5441341f1ab9 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -527,6 +527,7 @@ struct bpf_insn_aux_data {
> >                 struct {
> >                         u32 map_index;          /* index into used_maps[] */
> >                         u32 map_off;            /* offset from value base address */
> > +                       struct bpf_iarray *jt;  /* jump table for gotox instruction */
> >                 };
> >                 struct {
> >                         enum bpf_reg_type reg_type;     /* type of pseudo_btf_id */
> > @@ -840,6 +841,7 @@ struct bpf_verifier_env {
> >         struct bpf_scc_info **scc_info;
> >         u32 scc_cnt;
> >         struct bpf_iarray *succ;
> > +       struct bpf_iarray *gotox_tmp_buf;
> >  };
> >
> >  static inline struct bpf_func_info_aux *subprog_aux(struct bpf_verifier_env *env, int subprog)
> > @@ -1050,6 +1052,13 @@ static inline bool bpf_stack_narrow_access_ok(int off, int fill_size, int spill_
> >         return !(off % BPF_REG_SIZE);
> >  }
> >
> > +static inline bool insn_is_gotox(struct bpf_insn *insn)
> > +{
> > +       return BPF_CLASS(insn->code) == BPF_JMP &&
> > +              BPF_OP(insn->code) == BPF_JA &&
> > +              BPF_SRC(insn->code) == BPF_X;
> > +}
> > +
> >  const char *reg_type_str(struct bpf_verifier_env *env, enum bpf_reg_type type);
> >  const char *dynptr_type_str(enum bpf_dynptr_type type);
> >  const char *iter_type_str(const struct btf *btf, u32 btf_id);
> > diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
> > index 2053fda377bb..61ce52882632 100644
> > --- a/kernel/bpf/bpf_insn_array.c
> > +++ b/kernel/bpf/bpf_insn_array.c
> > @@ -114,6 +114,20 @@ static u64 insn_array_mem_usage(const struct bpf_map *map)
> >         return insn_array_alloc_size(map->max_entries);
> >  }
> >
> > +static int insn_array_map_direct_value_addr(const struct bpf_map *map, u64 *imm, u32 off)
> > +{
> > +       struct bpf_insn_array *insn_array = cast_insn_array(map);
> > +
> > +       if ((off % sizeof(long)) != 0 ||
> > +           (off / sizeof(long)) >= map->max_entries)
> > +               return -EINVAL;
> > +
> > +       /* from BPF's point of view, this map is a jump table */
> > +       *imm = (unsigned long)insn_array->ips + off;
> > +
> > +       return 0;
> > +}
> > +
> >  BTF_ID_LIST_SINGLE(insn_array_btf_ids, struct, bpf_insn_array)
> >
> >  const struct bpf_map_ops insn_array_map_ops = {
> > @@ -126,6 +140,7 @@ const struct bpf_map_ops insn_array_map_ops = {
> >         .map_delete_elem = insn_array_delete_elem,
> >         .map_check_btf = insn_array_check_btf,
> >         .map_mem_usage = insn_array_mem_usage,
> > +       .map_direct_value_addr = insn_array_map_direct_value_addr,
> >         .map_btf_id = &insn_array_btf_ids[0],
> >  };
> >
> > diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
> > index 4b62a03d6df5..ef4448f18aad 100644
> > --- a/kernel/bpf/core.c
> > +++ b/kernel/bpf/core.c
> > @@ -1708,6 +1708,7 @@ bool bpf_opcode_in_insntable(u8 code)
> >                 [BPF_LD | BPF_IND | BPF_B] = true,
> >                 [BPF_LD | BPF_IND | BPF_H] = true,
> >                 [BPF_LD | BPF_IND | BPF_W] = true,
> > +               [BPF_JMP | BPF_JA | BPF_X] = true,
> >                 [BPF_JMP | BPF_JCOND] = true,
> >         };
> >  #undef BPF_INSN_3_TBL
> > diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
> > index bffb495bc933..a7240013fd9d 100644
> > --- a/kernel/bpf/liveness.c
> > +++ b/kernel/bpf/liveness.c
> > @@ -485,6 +485,9 @@ bpf_insn_successors(struct bpf_verifier_env *env, u32 idx)
> >         struct bpf_iarray *succ;
> >         int insn_sz;
> >
> > +       if (unlikely(insn_is_gotox(insn)))
> > +               return env->insn_aux_data[idx].jt;
> > +
> >         /* pre-allocated array of size up to 2; reset cnt, as it may have been used already */
> >         succ = env->succ;
> >         succ->cnt = 0;
> > diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c
> > index 70221aafc35c..a0c3b35de2ce 100644
> > --- a/kernel/bpf/log.c
> > +++ b/kernel/bpf/log.c
> > @@ -461,6 +461,7 @@ const char *reg_type_str(struct bpf_verifier_env *env, enum bpf_reg_type type)
> >                 [PTR_TO_ARENA]          = "arena",
> >                 [PTR_TO_BUF]            = "buf",
> >                 [PTR_TO_FUNC]           = "func",
> > +               [PTR_TO_INSN]           = "insn",
> >                 [PTR_TO_MAP_KEY]        = "map_key",
> >                 [CONST_PTR_TO_DYNPTR]   = "dynptr_ptr",
> >         };
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 781669f649f2..1268fa075d4c 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -6006,6 +6006,18 @@ static int check_map_kptr_access(struct bpf_verifier_env *env, u32 regno,
> >         return 0;
> >  }
> >
> > +/*
> > + * Return the size of the memory region accessible from a pointer to map value.
> > + * For INSN_ARRAY maps whole bpf_insn_array->ips array is accessible.
> > + */
> > +static u32 map_mem_size(const struct bpf_map *map)
> > +{
> > +       if (map->map_type == BPF_MAP_TYPE_INSN_ARRAY)
> > +               return map->max_entries * sizeof(long);
> > +
> > +       return map->value_size;
> > +}
> > +
> >  /* check read/write into a map element with possible variable offset */
> >  static int check_map_access(struct bpf_verifier_env *env, u32 regno,
> >                             int off, int size, bool zero_size_allowed,
> > @@ -6015,11 +6027,11 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno,
> >         struct bpf_func_state *state = vstate->frame[vstate->curframe];
> >         struct bpf_reg_state *reg = &state->regs[regno];
> >         struct bpf_map *map = reg->map_ptr;
> > +       u32 mem_size = map_mem_size(map);
> >         struct btf_record *rec;
> >         int err, i;
> >
> > -       err = check_mem_region_access(env, regno, off, size, map->value_size,
> > -                                     zero_size_allowed);
> > +       err = check_mem_region_access(env, regno, off, size, mem_size, zero_size_allowed);
> >         if (err)
> >                 return err;
> >
> > @@ -7481,6 +7493,8 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> >  {
> >         struct bpf_reg_state *regs = cur_regs(env);
> >         struct bpf_reg_state *reg = regs + regno;
> > +       bool insn_array = reg->type == PTR_TO_MAP_VALUE &&
> > +                         reg->map_ptr->map_type == BPF_MAP_TYPE_INSN_ARRAY;
> >         int size, err = 0;
> >
> >         size = bpf_size_to_bytes(bpf_size);
> > @@ -7488,7 +7502,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> >                 return size;
> >
> >         /* alignment checks will add in reg->off themselves */
> > -       err = check_ptr_alignment(env, reg, off, size, strict_alignment_once);
> > +       err = check_ptr_alignment(env, reg, off, size, strict_alignment_once || insn_array);
> >         if (err)
> >                 return err;
> >
> > @@ -7515,6 +7529,11 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> >                         verbose(env, "R%d leaks addr into map\n", value_regno);
> >                         return -EACCES;
> >                 }
> > +               if (t == BPF_WRITE && insn_array) {
> > +                       verbose(env, "writes into insn_array not allowed\n");
> > +                       return -EACCES;
> > +               }
> > +
> >                 err = check_map_access_type(env, regno, off, size, t);
> 
> This is a bit ugly.
> Just set map->map_flags |= BPF_F_RDONLY_PROG;
> at map creation time or check that it's created this way from libbpf.
> And remove the above check.
> check_map_access_type() will do it generically.
> 
> and with that reg->map_ptr->map_type == BPF_MAP_TYPE_INSN_ARRAY ->strict
> can move into check_ptr_alignment().
> Abusing strict_alignment_once for this is wrong.
> 
> Both can be a follow up.

Ok, thanks, will follow up on both issues.