Re: [PATCH v9 bpf-next 06/11] bpf, x86: add support for indirect jumps

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

On 25/11/01 11:30AM, bot+bpf-ci@kernel.org wrote:
> 
> ```
> commit cb92a900026e1efa9f89af1f2682f1b544cc7e22
> Author: Anton Protopopov <a.s.protopopov@gmail.com>
> 
> bpf, x86: add support for indirect jumps
> 
> This patch adds support for indirect jumps (gotox instruction) in BPF
> programs, introducing a new PTR_TO_INSN register type to ensure jump
> targets are loaded from verified instruction array maps.
> 
> > diff --git a/kernel/bpf/bpf_insn_array.c b/kernel/bpf/bpf_insn_array.c
> > index d29f38721..7bf345a87 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;
> > +}
> 
> The insn_array_alloc_size() function can overflow. It computes:
> 
>   base_size + max_entries * (entry_size + sizeof(long))
> 
> and returns u32. With entry_size=16 and sizeof(long)=8, if max_entries
> exceeds ~178 million, the multiplication overflows u32 before the
> result is widened to u64 in insn_array_alloc(). This could result in
> allocating a buffer much smaller than intended.
> 
> While BPF programs have size limits, max_entries validation in
> insn_array_alloc_check() only checks != 0 without an upper bound. Should
> insn_array_alloc_size() return u64 or add overflow checking?

Yes, however see the comments in the relevant patch, not here.

> [ ... ]
> 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 2b771e2bf..3fdabae07 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> 
> [ ... ]
> 
> > @@ -17833,6 +17861,197 @@ static struct bpf_iarray *iarray_realloc(struct bpf_iarray *old, size_t n_elem)
> >  	return new;
> >  }
> >
> > +static int copy_insn_array(struct bpf_map *map, u32 start, u32 end, u32 *items)
> > +{
> > +	struct bpf_insn_array_value *value;
> > +	u32 i;
> > +
> > +	for (i = start; i <= end; i++) {
> > +		value = map->ops->map_lookup_elem(map, &i);
> > +		if (!value)
> > +			return -EINVAL;
> > +		items[i - start] = value->xlated_off;
> > +	}
> > +	return 0;
> > +}
> > +
> > +static int cmp_ptr_to_u32(const void *a, const void *b)
> > +{
> > +	return *(u32 *)a - *(u32 *)b;
> > +}
> > +
> > +static int sort_insn_array_uniq(u32 *items, int cnt)
> > +{
> > +	int unique = 1;
> > +	int i;
> > +
> > +	sort(items, cnt, sizeof(items[0]), cmp_ptr_to_u32, NULL);
> > +
> > +	for (i = 1; i < cnt; i++)
> > +		if (items[i] != items[unique - 1])
> > +			items[unique++] = items[i];
> > +
> > +	return unique;
> > +}
> > +
> > +/*
> > + * sort_unique({map[start], ..., map[end]}) into off
> > + */
> > +static int copy_insn_array_uniq(struct bpf_map *map, u32 start, u32 end, u32 *off)
> > +{
> > +	u32 n = end - start + 1;
> > +	int err;
> > +
> > +	err = copy_insn_array(map, start, end, off);
> > +	if (err)
> > +		return err;
> > +
> > +	return sort_insn_array_uniq(off, n);
> > +}
> > +
> > +/*
> > + * Copy all unique offsets from the map
> > + */
> > +static struct bpf_iarray *jt_from_map(struct bpf_map *map)
> > +{
> > +	struct bpf_iarray *jt;
> > +	int n;
> > +
> > +	jt = iarray_realloc(NULL, map->max_entries);
> > +	if (!jt)
> > +		return ERR_PTR(-ENOMEM);
> > +
> > +	n = copy_insn_array_uniq(map, 0, map->max_entries - 1, jt->items);
> > +	if (n < 0) {
> > +		kvfree(jt);
> > +		return ERR_PTR(n);
> > +	}
> > +
> > +	return jt;
> > +}
>                   ^^^^
> 
> The iarray_realloc() call sets jt->cnt = map->max_entries, but
> copy_insn_array_uniq() returns n (the actual number of unique items)
> which could be less. The function returns without updating jt->cnt to n.
> 
> In jt_from_subprog()->jt_from_map(), at the check:
> 
>   if (jt_cur->items[0] >= subprog_start && jt_cur->items[0] < subprog_end)
> 
> Can items[0] be accessed when n=0? If the map contains no valid entries,
> jt_cur->cnt still equals max_entries but no items were populated.
> 
> Later at:
> 
>   memcpy(jt->items + old_cnt, jt_cur->items, jt_cur->cnt << 2);
> 
> This copies jt_cur->cnt elements, but cnt=max_entries, not the actual
> count. Does this copy uninitialized memory from the jt_cur->items array?

Right, looks suspicious. No problem, with accessing items[0], as at
least one element will be there. However, it looks like it might
if fact copy duplicated values. Will fix.

> [ ... ]
> 
> > @@ -18855,6 +19074,9 @@ static bool regsafe(struct bpf_verifier_env *env, struct bpf_reg_state *rold,
> >  		return regs_exact(rold, rcur, idmap) && rold->frameno == rcur->frameno;
> >  	case PTR_TO_ARENA:
> >  		return true;
> > +	case PTR_TO_INSN:
> > +		return (rold->off == rcur->off && range_within(rold, rcur) &&
> > +			tnum_in(rold->var_off, rcur->var_off));
> >  	default:
> >  		return regs_exact(rold, rcur, idmap);
> >  	}
>                      ^^^^
> 
> Should PTR_TO_INSN check map_ptr equality like PTR_TO_MAP_VALUE does?
> 
> The PTR_TO_MAP_VALUE case uses memcmp() which compares all fields
> including map_ptr. But this PTR_TO_INSN case only checks off, range, and
> var_off. If a BPF program uses multiple INSN_ARRAY maps with different
> jump tables, could state pruning incorrectly consider two PTR_TO_INSN
> registers equivalent when they point to different maps?

Thanks AI, looks real, will add a fix.

> 
> ```
> 
> ---
> AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
> See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
> 
> In-Reply-To-Subject: `bpf, x86: add support for indirect jumps`
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/18995945884