On 18/3/25 22:33, Anton Protopopov wrote:
> On the bpf(BPF_PROG_LOAD) syscall a user-supplied BPF program is
> translated by the verifier into an "xlated" BPF program. During this
> process the original instruction offsets might be adjusted and/or
> individual instructions might be replaced by new sets of instructions,
> or deleted. Add new BPF map type which is aimed to keep track of
> how, for a given program, original instructions were relocated during
> the verification.
>
> A map of the BPF_MAP_TYPE_INSN_SET type is created with key and value
> size of 4 (size of u32). One such map can be used to track only one BPF
> program. To do so each element of the map should be initialized to point
> to an instruction offset within the program. Offsets within the map
> should be sorted. Before the program load such maps should be made frozen.
> After the verification xlated offsets can be read via the bpf(2) syscall.
> No BPF-side operations are allowed on the map.
>
> If a tracked instruction is removed by the verifier, then the xlated
> offset is set to (u32)-1 which is considered to be too big for a valid
> BPF program offset.
>
> If the verification process was unsuccessful, then the same map can
> be re-used to verify the program with a different log level. However,
> if the program was loaded fine, then such a map, being frozen in any
> case, can't be reused by other programs even after the program release.
>
> Example. Consider the following original and xlated programs:
>
> Original prog: Xlated prog:
>
> 0: r1 = 0x0 0: r1 = 0
> 1: *(u32 *)(r10 - 0x4) = r1 1: *(u32 *)(r10 -4) = r1
> 2: r2 = r10 2: r2 = r10
> 3: r2 += -0x4 3: r2 += -4
> 4: r1 = 0x0 ll 4: r1 = map[id:88]
> 6: call 0x1 6: r1 += 272
> 7: r0 = *(u32 *)(r2 +0)
> 8: if r0 >= 0x1 goto pc+3
> 9: r0 <<= 3
> 10: r0 += r1
> 11: goto pc+1
> 12: r0 = 0
> 7: r6 = r0 13: r6 = r0
> 8: if r6 == 0x0 goto +0x2 14: if r6 == 0x0 goto pc+4
> 9: call 0x76 15: r0 = 0xffffffff8d2079c0
> 17: r0 = *(u64 *)(r0 +0)
> 10: *(u64 *)(r6 + 0x0) = r0 18: *(u64 *)(r6 +0) = r0
> 11: r0 = 0x0 19: r0 = 0x0
> 12: exit 20: exit
>
> An instruction set map, containing, e.g., indexes [0,4,7,12]
> will be translated by the verifier to [0,4,13,20]. A map with
> index 5 (the middle of 16-byte instruction) or indexes greater than 12
> (outside the program boundaries) would be rejected.
>
> The functionality provided by this patch will be extended in consequent
> patches to implement BPF Static Keys, indirect jumps, and indirect calls.
>
> Signed-off-by: Anton Protopopov <aspsk@xxxxxxxxxxxxx>
> ---
> include/linux/bpf.h | 11 ++
> include/linux/bpf_types.h | 1 +
> include/linux/bpf_verifier.h | 2 +
> include/uapi/linux/bpf.h | 1 +
> kernel/bpf/Makefile | 2 +-
> kernel/bpf/bpf_insn_set.c | 288 +++++++++++++++++++++++++++++++++
> kernel/bpf/syscall.c | 1 +
> kernel/bpf/verifier.c | 50 ++++++
> tools/include/uapi/linux/bpf.h | 1 +
> 9 files changed, 356 insertions(+), 1 deletion(-)
> create mode 100644 kernel/bpf/bpf_insn_set.c
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index 0d7b70124d81..0b5f4d4745ee 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -3554,4 +3554,15 @@ static inline bool bpf_is_subprog(const struct bpf_prog *prog)
> return prog->aux->func_idx != 0;
> }
>
> +int bpf_insn_set_init(struct bpf_map *map, const struct bpf_prog *prog);
> +void 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);
> +
> +struct bpf_insn_ptr {
> + u32 orig_xlated_off;
> + u32 xlated_off;
> +};
> +
> #endif /* _LINUX_BPF_H */
> diff --git a/include/linux/bpf_types.h b/include/linux/bpf_types.h
> index fa78f49d4a9a..01df0e47a3f7 100644
> --- a/include/linux/bpf_types.h
> +++ b/include/linux/bpf_types.h
> @@ -133,6 +133,7 @@ BPF_MAP_TYPE(BPF_MAP_TYPE_RINGBUF, ringbuf_map_ops)
> BPF_MAP_TYPE(BPF_MAP_TYPE_BLOOM_FILTER, bloom_filter_map_ops)
> BPF_MAP_TYPE(BPF_MAP_TYPE_USER_RINGBUF, user_ringbuf_map_ops)
> BPF_MAP_TYPE(BPF_MAP_TYPE_ARENA, arena_map_ops)
> +BPF_MAP_TYPE(BPF_MAP_TYPE_INSN_SET, insn_set_map_ops)
>
> BPF_LINK_TYPE(BPF_LINK_TYPE_RAW_TRACEPOINT, raw_tracepoint)
> BPF_LINK_TYPE(BPF_LINK_TYPE_TRACING, tracing)
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index d6cfc4ee6820..f694c08f39d1 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -722,8 +722,10 @@ struct bpf_verifier_env {
> struct list_head free_list; /* list of struct bpf_verifier_state_list */
> struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
> struct btf_mod_pair used_btfs[MAX_USED_BTFS]; /* array of BTF's used by BPF program */
> + struct bpf_map *insn_set_maps[MAX_USED_MAPS]; /* array of INSN_SET map's to be relocated */
> u32 used_map_cnt; /* number of used maps */
> u32 used_btf_cnt; /* number of used BTF objects */
> + u32 insn_set_map_cnt; /* number of used maps of type BPF_MAP_TYPE_INSN_SET */
> u32 id_gen; /* used to generate unique reg IDs */
> u32 hidden_subprog_cnt; /* number of hidden subprogs */
> int exception_callback_subprog;
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index 1388db053d9e..b8e588ed6406 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -1013,6 +1013,7 @@ enum bpf_map_type {
> BPF_MAP_TYPE_USER_RINGBUF,
> BPF_MAP_TYPE_CGRP_STORAGE,
> BPF_MAP_TYPE_ARENA,
> + BPF_MAP_TYPE_INSN_SET,
> __MAX_BPF_MAP_TYPE
> };
>
> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> index 410028633621..a4399089557b 100644
> --- a/kernel/bpf/Makefile
> +++ b/kernel/bpf/Makefile
> @@ -9,7 +9,7 @@ CFLAGS_core.o += -Wno-override-init $(cflags-nogcse-yy)
> obj-$(CONFIG_BPF_SYSCALL) += syscall.o verifier.o inode.o helpers.o tnum.o log.o token.o
> obj-$(CONFIG_BPF_SYSCALL) += bpf_iter.o map_iter.o task_iter.o prog_iter.o link_iter.o
> obj-$(CONFIG_BPF_SYSCALL) += hashtab.o arraymap.o percpu_freelist.o bpf_lru_list.o lpm_trie.o map_in_map.o bloom_filter.o
> -obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o
> +obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o ringbuf.o bpf_insn_set.o
> obj-$(CONFIG_BPF_SYSCALL) += bpf_local_storage.o bpf_task_storage.o
> obj-${CONFIG_BPF_LSM} += bpf_inode_storage.o
> obj-$(CONFIG_BPF_SYSCALL) += disasm.o mprog.o
> diff --git a/kernel/bpf/bpf_insn_set.c b/kernel/bpf/bpf_insn_set.c
> new file mode 100644
> index 000000000000..e788dd7109b1
> --- /dev/null
> +++ b/kernel/bpf/bpf_insn_set.c
> @@ -0,0 +1,288 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +
> +#include <linux/bpf.h>
> +
> +#define MAX_ISET_ENTRIES 128
> +
> +struct bpf_insn_set {
> + struct bpf_map map;
> + struct mutex state_mutex;
> + int state;
> + DECLARE_FLEX_ARRAY(struct bpf_insn_ptr, ptrs);
> +};
> +
> +enum {
> + INSN_SET_STATE_FREE = 0,
> + INSN_SET_STATE_INIT,
> + INSN_SET_STATE_READY,
> +};
> +
> +#define cast_insn_set(MAP_PTR) \
> + container_of(MAP_PTR, struct bpf_insn_set, map)
> +
> +static inline u32 insn_set_alloc_size(u32 max_entries)
> +{
> + const u32 base_size = sizeof(struct bpf_insn_set);
> + const u32 entry_size = sizeof(struct bpf_insn_ptr);
> +
> + return base_size + entry_size * max_entries;
> +}
> +
> +static int insn_set_alloc_check(union bpf_attr *attr)
> +{
> + if (attr->max_entries == 0 ||
> + attr->key_size != 4 ||
> + attr->value_size != 4 ||
> + attr->map_flags != 0)
> + return -EINVAL;
> +
> + if (attr->max_entries > MAX_ISET_ENTRIES)
> + return -E2BIG;
> +
> + return 0;
> +}
> +
> +static struct bpf_map *insn_set_alloc(union bpf_attr *attr)
> +{
> + u64 size = insn_set_alloc_size(attr->max_entries);
> + struct bpf_insn_set *insn_set;
> +
> + insn_set = bpf_map_area_alloc(size, NUMA_NO_NODE);
> + if (!insn_set)
> + return ERR_PTR(-ENOMEM);
> +
> + bpf_map_init_from_attr(&insn_set->map, attr);
> +
> + mutex_init(&insn_set->state_mutex);> + insn_set->state = INSN_SET_STATE_FREE;
> +
> + return &insn_set->map;
> +}
> +
> +static int insn_set_get_next_key(struct bpf_map *map, void *key, void *next_key)
> +{
> + struct bpf_insn_set *insn_set = cast_insn_set(map);
> + u32 index = key ? *(u32 *)key : U32_MAX;
> + u32 *next = (u32 *)next_key;
> +
> + if (index >= insn_set->map.max_entries) {
> + *next = 0;
> + return 0;
> + }
> +
> + if (index == insn_set->map.max_entries - 1)
> + return -ENOENT;
> +
> + *next = index + 1;
> + return 0;
> +}
> +
> +static void *insn_set_lookup_elem(struct bpf_map *map, void *key)
> +{
> + struct bpf_insn_set *insn_set = cast_insn_set(map);
> + u32 index = *(u32 *)key;
> +
> + if (unlikely(index >= insn_set->map.max_entries))
> + return NULL;
> +
> + return &insn_set->ptrs[index].xlated_off;
> +}
> +
> +static long insn_set_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags)
> +{
> + struct bpf_insn_set *insn_set = cast_insn_set(map);
> + u32 index = *(u32 *)key;
> +
> + if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST))
> + return -EINVAL;
> +
> + if (unlikely(index >= insn_set->map.max_entries))
> + return -E2BIG;
> +
> + if (unlikely(map_flags & BPF_NOEXIST))
> + return -EEXIST;
> +
> + copy_map_value(map, &insn_set->ptrs[index].orig_xlated_off, value);
> + insn_set->ptrs[index].xlated_off = insn_set->ptrs[index].orig_xlated_off;
> +
> + return 0;
> +}
> +
> +static long insn_set_delete_elem(struct bpf_map *map, void *key)
> +{
> + return -EINVAL;
> +}
> +
> +static int insn_set_check_btf(const struct bpf_map *map,
> + const struct btf *btf,
> + const struct btf_type *key_type,
> + const struct btf_type *value_type)
> +{
> + u32 int_data;
> +
> + if (BTF_INFO_KIND(key_type->info) != BTF_KIND_INT)
> + return -EINVAL;
> +
> + if (BTF_INFO_KIND(value_type->info) != BTF_KIND_INT)
> + return -EINVAL;
> +
> + int_data = *(u32 *)(key_type + 1);
> + if (BTF_INT_BITS(int_data) != 32 || BTF_INT_OFFSET(int_data))
> + return -EINVAL;
> +
> + int_data = *(u32 *)(value_type + 1);
> + if (BTF_INT_BITS(int_data) != 32 || BTF_INT_OFFSET(int_data))
> + return -EINVAL;
> +
> + return 0;
> +}
> +
> +static void insn_set_free(struct bpf_map *map)
> +{
> + struct bpf_insn_set *insn_set = cast_insn_set(map);
> +
> + bpf_map_area_free(insn_set);
> +}
> +
> +static u64 insn_set_mem_usage(const struct bpf_map *map)
> +{
> + return insn_set_alloc_size(map->max_entries);
> +}
> +
> +BTF_ID_LIST_SINGLE(insn_set_btf_ids, struct, bpf_insn_set)
> +
> +const struct bpf_map_ops insn_set_map_ops = {
> + .map_alloc_check = insn_set_alloc_check,
> + .map_alloc = insn_set_alloc,
> + .map_free = insn_set_free,
> + .map_get_next_key = insn_set_get_next_key,
> + .map_lookup_elem = insn_set_lookup_elem,
> + .map_update_elem = insn_set_update_elem,
> + .map_delete_elem = insn_set_delete_elem,
> + .map_check_btf = insn_set_check_btf,
> + .map_mem_usage = insn_set_mem_usage,
> + .map_btf_id = &insn_set_btf_ids[0],
> +};
> +
> +static inline bool is_frozen(struct bpf_map *map)
> +{
> + bool ret = true;
> +
> + mutex_lock(&map->freeze_mutex);
> + if (!map->frozen)
> + ret = false;
> + mutex_unlock(&map->freeze_mutex);> +
> + return ret;
> +}
It would be better to use guard(mutex) here:
static inline bool is_frozen(struct bpf_map *map)
{
guard(mutex)(&map->freeze_mutex);
return map->frozen;
}
Thanks,
Leon
> +
> +static inline bool valid_offsets(const struct bpf_insn_set *insn_set,
> + const struct bpf_prog *prog)
> +{
> + u32 off, prev_off;
> + int i;
> +
> + for (i = 0; i < insn_set->map.max_entries; i++) {
> + off = insn_set->ptrs[i].orig_xlated_off;
> +
> + if (off >= prog->len)
> + return false;
> +
> + if (off > 0) {
> + if (prog->insnsi[off-1].code == (BPF_LD | BPF_DW | BPF_IMM))
> + return false;
> + }
> +
> + if (i > 0) {
> + prev_off = insn_set->ptrs[i-1].orig_xlated_off;
> + if (off <= prev_off)
> + return false;
> + }
> + }
> +
> + return true;
> +}
[...]
