[RFC PATCH bpf-next 00/14] instruction sets and static keys

[RFC PATCH bpf-next 00/14] instruction sets and static keys

[Anton Protopopov]

This patchset implements new type of map, instruction set, and uses
it to build support for BPF static keys. The same map will be later
used to provide support for indirect jumps and indirect calls. See
[1], [2] for more context.

Short table of contents:

  * patches 1, 9, 10, 11 are simple fixes (which can be sent
    independently, if acked)

  * patches 2, 3 add a new map type, BPF_MAP_TYPE_INSN_SET, and
    corresponding selftests. This map is used to track how original
    instructions were relocated into 'xlated' during the verification

  * patches 4, 5, 6, 7, 8 add support for static keys (kernel only)
    using (an extension) to that new map type. Only x86 support is
    added in this RFC

  * patches 12, 13, 14 add libbpf-side support for static keys and
    selftests

It is RFC for a few reasons:

1) The kernel side of the static keys looks clear, however, the
libbpf side is not _that_ clear. I thought that this is better to
commit to a particular userspace design, as any particular design
requires a lot of changes on the libbpf side. See patch 12 for
the details

2) The libbpf part of the series requires a patched LLVM (see [3]),
which adds support for gotol_or_nop/nop_or_gotol instructions, so
selftests would not compile in CI.

3) Patch 4 adds support for a new BPF instruction. It looks
reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
may_goto. Reasons: a follow up will add support for
BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
Then another follow up will add support CALL|BPF_X, for which there's
no corresponding magic instruction (to be discussed at the following
LSF/MM/BPF).

Besides these reasons, there are some questions / known bugs,
which will be fixed once the general plan is confirmed:

  * bpf_jit_blind_constants will patch code, which is ignored in this
    RFC series. The solution would be either moving tracking
    instruction sets to bpf_prog from the verifier environment,
    or moving bpf_jit_blind_constants upper the stack (right now,
    this is the first thing which every jit does, so maybe it can
    be actually executed from the verifier, and provide env context)

  * gen-loader not supported, fd_array usage in libbpf should be
    re-designed (see patch 12 for more details)

  * insn_off -> insn_set map mapping should be optimized (now it is
    brute force)

Links:
  1. http://oldvger.kernel.org/bpfconf2024_material/bpf_static_keys.pdf
  2. https://lpc.events/event/18/contributions/1941/
  3. https://github.com/aspsk/llvm-project/tree/static-keys

Anton Protopopov (14):
  bpf: fix a comment describing bpf_attr
  bpf: add new map type: instructions set
  selftests/bpf: add selftests for new insn_set map
  bpf: add support for an extended JA instruction
  bpf: Add kernel/bpftool asm support for new instructions
  bpf: add BPF_STATIC_KEY_UPDATE syscall
  bpf: save the start of functions in bpf_prog_aux
  bpf, x86: implement static key support
  selftests/bpf: add guard macros around likely/unlikely
  libbpf: add likely/unlikely macros
  selftests/bpf: remove likely/unlikely definitions
  libbpf: BPF Static Keys support
  libbpf: Add bpf_static_key_update() API
  selftests/bpf: Add tests for BPF static calls

 arch/x86/net/bpf_jit_comp.c                   |  65 +-
 include/linux/bpf.h                           |  28 +
 include/linux/bpf_types.h                     |   1 +
 include/linux/bpf_verifier.h                  |   2 +
 include/uapi/linux/bpf.h                      |  40 +-
 kernel/bpf/Makefile                           |   2 +-
 kernel/bpf/bpf_insn_set.c                     | 400 +++++++++++
 kernel/bpf/core.c                             |   5 +
 kernel/bpf/disasm.c                           |  33 +-
 kernel/bpf/syscall.c                          |  28 +
 kernel/bpf/verifier.c                         |  94 ++-
 tools/include/uapi/linux/bpf.h                |  40 +-
 tools/lib/bpf/bpf.c                           |  17 +
 tools/lib/bpf/bpf.h                           |  19 +
 tools/lib/bpf/bpf_helpers.h                   |  63 ++
 tools/lib/bpf/libbpf.c                        | 362 +++++++++-
 tools/lib/bpf/libbpf.map                      |   1 +
 tools/lib/bpf/libbpf_internal.h               |   3 +
 tools/lib/bpf/linker.c                        |   6 +-
 .../selftests/bpf/bpf_arena_spin_lock.h       |   3 -
 .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
 .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++
 .../selftests/bpf/progs/bpf_static_keys.c     | 131 ++++
 tools/testing/selftests/bpf/progs/iters.c     |   2 -
 24 files changed, 2315 insertions(+), 28 deletions(-)
 create mode 100644 kernel/bpf/bpf_insn_set.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c

-- 
2.34.1

[RFC PATCH bpf-next 01/14] bpf: fix a comment describing bpf_attr

[Anton Protopopov]

The map_fd field of the bpf_attr union is used in the BPF_MAP_FREEZE
syscall.  Explicitly mention this in the comments.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 include/uapi/linux/bpf.h       | 2 +-
 tools/include/uapi/linux/bpf.h | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 661de2444965..1388db053d9e 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -1506,7 +1506,7 @@ union bpf_attr {
 		__s32	map_token_fd;
 	};
 
-	struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
+	struct { /* anonymous struct used by BPF_MAP_*_ELEM and BPF_MAP_FREEZE commands */
 		__u32		map_fd;
 		__aligned_u64	key;
 		union {
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 661de2444965..1388db053d9e 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -1506,7 +1506,7 @@ union bpf_attr {
 		__s32	map_token_fd;
 	};
 
-	struct { /* anonymous struct used by BPF_MAP_*_ELEM commands */
+	struct { /* anonymous struct used by BPF_MAP_*_ELEM and BPF_MAP_FREEZE commands */
 		__u32		map_fd;
 		__aligned_u64	key;
 		union {
-- 
2.34.1

[RFC PATCH bpf-next 02/14] bpf: add new map type: instructions set

[Anton Protopopov]

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@isovalent.com>
---
 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;
+}
+
+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;
+}
+
+int bpf_insn_set_init(struct bpf_map *map, const struct bpf_prog *prog)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+	int i;
+
+	if (!is_frozen(map))
+		return -EINVAL;
+
+	if (!valid_offsets(insn_set, prog))
+		return -EINVAL;
+
+	/*
+	 * There can be only one program using the map
+	 */
+	mutex_lock(&insn_set->state_mutex);
+	if (insn_set->state != INSN_SET_STATE_FREE) {
+		mutex_unlock(&insn_set->state_mutex);
+		return -EBUSY;
+	}
+	insn_set->state = INSN_SET_STATE_INIT;
+	mutex_unlock(&insn_set->state_mutex);
+
+	/*
+	 * Reset all the map indexes to the original values.  This is needed,
+	 * e.g., when a replay of verification with different log level should
+	 * be performed.
+	 */
+	for (i = 0; i < map->max_entries; i++)
+		insn_set->ptrs[i].xlated_off = insn_set->ptrs[i].orig_xlated_off;
+
+	return 0;
+}
+
+void bpf_insn_set_ready(struct bpf_map *map)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+
+	insn_set->state = INSN_SET_STATE_READY;
+}
+
+void bpf_insn_set_release(struct bpf_map *map)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+
+	insn_set->state = INSN_SET_STATE_FREE;
+}
+
+#define INSN_DELETED ((u32)-1)
+
+void bpf_insn_set_adjust(struct bpf_map *map, u32 off, u32 len)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+	int i;
+
+	if (len <= 1)
+		return;
+
+	for (i = 0; i < map->max_entries; i++) {
+		if (insn_set->ptrs[i].xlated_off <= off)
+			continue;
+		if (insn_set->ptrs[i].xlated_off == INSN_DELETED)
+			continue;
+		insn_set->ptrs[i].xlated_off += len - 1;
+	}
+}
+
+void bpf_insn_set_adjust_after_remove(struct bpf_map *map, u32 off, u32 len)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+	int i;
+
+	for (i = 0; i < map->max_entries; i++) {
+		if (insn_set->ptrs[i].xlated_off < off)
+			continue;
+		if (insn_set->ptrs[i].xlated_off == INSN_DELETED)
+			continue;
+		if (insn_set->ptrs[i].xlated_off >= off &&
+		    insn_set->ptrs[i].xlated_off < off + len)
+			insn_set->ptrs[i].xlated_off = INSN_DELETED;
+		else
+			insn_set->ptrs[i].xlated_off -= len;
+	}
+}
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 380b445a304c..c417bf5eed74 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1436,6 +1436,7 @@ static int map_create(union bpf_attr *attr, bool kernel)
 	case BPF_MAP_TYPE_STRUCT_OPS:
 	case BPF_MAP_TYPE_CPUMAP:
 	case BPF_MAP_TYPE_ARENA:
+	case BPF_MAP_TYPE_INSN_SET:
 		if (!bpf_token_capable(token, CAP_BPF))
 			goto put_token;
 		break;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 3303a3605ee8..6554f7aea0d8 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9877,6 +9877,8 @@ static int check_map_func_compatibility(struct bpf_verifier_env *env,
 		    func_id != BPF_FUNC_map_push_elem)
 			goto error;
 		break;
+	case BPF_MAP_TYPE_INSN_SET:
+		goto error;
 	default:
 		break;
 	}
@@ -19873,6 +19875,13 @@ static int __add_used_map(struct bpf_verifier_env *env, struct bpf_map *map)
 
 	env->used_maps[env->used_map_cnt++] = map;
 
+	if (map->map_type == BPF_MAP_TYPE_INSN_SET) {
+		err = bpf_insn_set_init(map, env->prog);
+		if (err)
+			return err;
+		env->insn_set_maps[env->insn_set_map_cnt++] = map;
+	}
+
 	return env->used_map_cnt - 1;
 }
 
@@ -20122,6 +20131,41 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
 	}
 }
 
+static void mark_insn_sets_ready(struct bpf_verifier_env *env)
+{
+	int i;
+
+	for (i = 0; i < env->insn_set_map_cnt; i++)
+		bpf_insn_set_ready(env->insn_set_maps[i]);
+}
+
+static void release_insn_sets(struct bpf_verifier_env *env)
+{
+	int i;
+
+	for (i = 0; i < env->insn_set_map_cnt; i++)
+		bpf_insn_set_release(env->insn_set_maps[i]);
+}
+
+static void adjust_insn_sets(struct bpf_verifier_env *env, u32 off, u32 len)
+{
+	int i;
+
+	if (len == 1)
+		return;
+
+	for (i = 0; i < env->insn_set_map_cnt; i++)
+		bpf_insn_set_adjust(env->insn_set_maps[i], off, len);
+}
+
+static void adjust_insn_sets_after_remove(struct bpf_verifier_env *env, u32 off, u32 len)
+{
+	int i;
+
+	for (i = 0; i < env->insn_set_map_cnt; i++)
+		bpf_insn_set_adjust_after_remove(env->insn_set_maps[i], off, len);
+}
+
 static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
 {
 	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
@@ -20160,6 +20204,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	}
 	adjust_insn_aux_data(env, new_data, new_prog, off, len);
 	adjust_subprog_starts(env, off, len);
+	adjust_insn_sets(env, off, len);
 	adjust_poke_descs(new_prog, off, len);
 	return new_prog;
 }
@@ -20343,6 +20388,8 @@ static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
 	if (err)
 		return err;
 
+	adjust_insn_sets_after_remove(env, off, cnt);
+
 	memmove(aux_data + off,	aux_data + off + cnt,
 		sizeof(*aux_data) * (orig_prog_len - off - cnt));
 
@@ -23927,8 +23974,11 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	}
 
 	adjust_btf_func(env);
+	mark_insn_sets_ready(env);
 
 err_release_maps:
+	if (ret)
+		release_insn_sets(env);
 	if (!env->prog->aux->used_maps)
 		/* if we didn't copy map pointers into bpf_prog_info, release
 		 * them now. Otherwise free_used_maps() will release them.
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 1388db053d9e..b8e588ed6406 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/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
 };
 
-- 
2.34.1

Re: [RFC PATCH bpf-next 02/14] bpf: add new map type: instructions set

[Leon Hwang]

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@isovalent.com>
> ---
>  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;
> +}
[...]

Re: [RFC PATCH bpf-next 02/14] bpf: add new map type: instructions set

[Anton Protopopov]

On 25/03/20 03:56PM, Leon Hwang wrote:
> 
> 
> 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@isovalent.com>
> > ---
> >  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! Patchded.

> 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;
> > +}
> [...]
> 

[RFC PATCH bpf-next 03/14] selftests/bpf: add selftests for new insn_set map

[Anton Protopopov]

Tests are split in two parts.

The `bpf_insn_set_ops` test checks that the map is managed properly:

  * Incorrect instruction indexes are rejected
  * Non-sorted and non-unique indexes are rejected
  * Unfrozen maps are not accepted
  * Two programs can't use the same map
  * BPF progs can't operate the map

The `bpf_insn_set_reloc` part validates, as best as it can do it from user
space, that instructions are relocated properly:

  * no relocations => map is the same
  * expected relocations when instructions are added
  * expected relocations when instructions are deleted
  * expected relocations when multiple functions are present

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
 1 file changed, 639 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
new file mode 100644
index 000000000000..796980bd4fcb
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
@@ -0,0 +1,639 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <bpf/bpf.h>
+#include <test_progs.h>
+
+static inline int map_create(__u32 map_type, __u32 max_entries)
+{
+	const char *map_name = "insn_set";
+	__u32 key_size = 4;
+	__u32 value_size = 4;
+
+	return bpf_map_create(map_type, map_name, key_size, value_size, max_entries, NULL);
+}
+
+/*
+ * Load a program, which will not be anyhow mangled by the verifier.  Add an
+ * insn_set map pointing to every instruction. Check that it hasn't changed
+ * after the program load.
+ */
+static void check_one_to_one_mapping(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/*
+ * Try to load a program with a map which points to outside of the program
+ */
+static void check_out_of_bounds_index(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int key, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	key = 0;
+	val = ARRAY_SIZE(insns); /* too big */
+	if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &key, &val, 0), 0, "bpf_map_update_elem"))
+		goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+cleanup:
+	close(map_fd);
+}
+
+/*
+ * Try to load a program with a map which points to the middle of 16-bit insn
+ */
+static void check_mid_insn_index(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_LD_IMM64(BPF_REG_0, 0), /* 2 x 8 */
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int key, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	key = 0;
+	val = 1; /* middle of 16-byte instruction */
+	if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &key, &val, 0), 0, "bpf_map_update_elem"))
+		goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_incorrect_index(void)
+{
+	check_out_of_bounds_index();
+	check_mid_insn_index();
+}
+
+static void check_not_sorted(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int i, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		val = ARRAY_SIZE(insns) - i - 1; /* reverse indexes */
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+	}
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_not_unique(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int i, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		val = 1;
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+	}
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_not_sorted_or_unique(void)
+{
+	check_not_sorted();
+	check_not_unique();
+}
+
+/*
+ * Load a program with two patches (get jiffies, for simplicity). Add an
+ * insn_set map pointing to every instruction. Check how it was relocated
+ * after the program load.
+ */
+static void check_relocate_simple(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	__u32 map_in[] = {0, 1, 2, 3, 4, 5};
+	__u32 map_out[] = {0, 1, 4, 5, 8, 9};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/*
+ * Verifier can delete code in two cases: nops & dead code. From the relocation
+ * point of view, the two cases look the same, so test using the simplest
+ * method: by loading some nops
+ */
+static void check_relocate_deletions(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	__u32 map_in[] = {0, 1, 2, 3, 4, 5};
+	__u32 map_out[] = {0, -1, 1, -1, 2, 3};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_relocate_with_functions(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_EXIT_INSN(),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	__u32 map_in[] =  { 0, 1,  2, 3, 4, 5, /* func */  6, 7,  8, 9, 10};
+	__u32 map_out[] = {-1, 0, -1, 3, 4, 5, /* func */ -1, 6, -1, 9, 10};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/* Once map was initialized, it should be frozen */
+static void check_load_unfrozen_map(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+	/* cirrectness: now freeze the map, the program should load fine */
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/* Map can be used only by one BPF program */
+static void check_no_map_reuse(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd, extra_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+		.fd_array = ptr_to_u64(&map_fd),
+		.fd_array_cnt = 1,
+	};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+	errno = 0;
+	extra_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(extra_fd, -1, "program should have been rejected (extra_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EBUSY, "program should have been rejected (errno != EBUSY)"))
+		goto cleanup;
+
+	/* correctness: check that prog is still loadable without fd_array */
+	attr.fd_array_cnt = 0;
+	extra_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD): expected no error"))
+		goto cleanup;
+	close(extra_fd);
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_bpf_no_lookup(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_LD_MAP_FD(BPF_REG_1, 0),
+		BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+		BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	union bpf_attr attr = {
+		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+		.insns     = ptr_to_u64(insns),
+		.insn_cnt  = ARRAY_SIZE(insns),
+		.license   = ptr_to_u64("GPL"),
+	};
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	/* otherwise will be rejected as unfrozen */
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		return;
+
+	insns[0].imm = map_fd;
+
+	errno = 0;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_EQ(prog_fd, -1, "program should have been rejected (prog_fd != -1)"))
+		goto cleanup;
+	if (!ASSERT_EQ(errno, EINVAL, "program should have been rejected (errno != EINVAL)"))
+		goto cleanup;
+
+	/* correctness: check that prog is still loadable with normal map */
+	close(map_fd);
+	map_fd = map_create(BPF_MAP_TYPE_ARRAY, 1);
+	insns[0].imm = map_fd;
+	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_bpf_side(void)
+{
+	check_bpf_no_lookup();
+}
+
+/* Test how relocations work */
+void test_bpf_insn_set_reloc(void)
+{
+	if (test__start_subtest("one2one"))
+		check_one_to_one_mapping();
+
+	if (test__start_subtest("relocate-simple"))
+		check_relocate_simple();
+
+	if (test__start_subtest("relocate-deletions"))
+		check_relocate_deletions();
+
+	if (test__start_subtest("relocate-multiple-functions"))
+		check_relocate_with_functions();
+}
+
+/* Check all kinds of operations and related restrictions */
+void test_bpf_insn_set_ops(void)
+{
+	if (test__start_subtest("incorrect-index"))
+		check_incorrect_index();
+
+	if (test__start_subtest("not-sorted-or-unique"))
+		check_not_sorted_or_unique();
+
+	if (test__start_subtest("load-unfrozen-map"))
+		check_load_unfrozen_map();
+
+	if (test__start_subtest("no-map-reuse"))
+		check_no_map_reuse();
+
+	if (test__start_subtest("bpf-side-ops"))
+		check_bpf_side();
+}
-- 
2.34.1

Re: [RFC PATCH bpf-next 03/14] selftests/bpf: add selftests for new insn_set map

[Yonghong Song]

On 3/18/25 7:33 AM, Anton Protopopov wrote:
> Tests are split in two parts.
>
> The `bpf_insn_set_ops` test checks that the map is managed properly:
>
>    * Incorrect instruction indexes are rejected
>    * Non-sorted and non-unique indexes are rejected
>    * Unfrozen maps are not accepted
>    * Two programs can't use the same map
>    * BPF progs can't operate the map
>
> The `bpf_insn_set_reloc` part validates, as best as it can do it from user
> space, that instructions are relocated properly:
>
>    * no relocations => map is the same
>    * expected relocations when instructions are added
>    * expected relocations when instructions are deleted
>    * expected relocations when multiple functions are present
>
> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> ---
>   .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
>   1 file changed, 639 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> new file mode 100644
> index 000000000000..796980bd4fcb
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> @@ -0,0 +1,639 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <bpf/bpf.h>
> +#include <test_progs.h>
> +
> +static inline int map_create(__u32 map_type, __u32 max_entries)
> +{
> +	const char *map_name = "insn_set";
> +	__u32 key_size = 4;
> +	__u32 value_size = 4;
> +
> +	return bpf_map_create(map_type, map_name, key_size, value_size, max_entries, NULL);
> +}
> +
> +/*
> + * Load a program, which will not be anyhow mangled by the verifier.  Add an
> + * insn_set map pointing to every instruction. Check that it hasn't changed
> + * after the program load.
> + */
> +static void check_one_to_one_mapping(void)
> +{
> +	struct bpf_insn insns[] = {
> +		BPF_MOV64_IMM(BPF_REG_0, 4),
> +		BPF_MOV64_IMM(BPF_REG_0, 3),
> +		BPF_MOV64_IMM(BPF_REG_0, 2),
> +		BPF_MOV64_IMM(BPF_REG_0, 1),
> +		BPF_MOV64_IMM(BPF_REG_0, 0),
> +		BPF_EXIT_INSN(),
> +	};
> +	int prog_fd, map_fd;

prog_fd needs to be initialized to something like -1.

> +	union bpf_attr attr = {
> +		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
> +		.insns     = ptr_to_u64(insns),
> +		.insn_cnt  = ARRAY_SIZE(insns),
> +		.license   = ptr_to_u64("GPL"),
> +		.fd_array = ptr_to_u64(&map_fd),
> +		.fd_array_cnt = 1,
> +	};
> +	int i;
> +
> +	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
> +	if (!ASSERT_GE(map_fd, 0, "map_create"))
> +		return;
> +
> +	for (i = 0; i < ARRAY_SIZE(insns); i++)
> +		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
> +			goto cleanup;

Otherwise, goto cleanup here will goto cleanup and close(prog_fd) will close
a random prog_fd. Please check the rest of prog_fd usage.

> +
> +	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
> +		return;
> +
> +	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
> +	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
> +		goto cleanup;
> +
> +	for (i = 0; i < ARRAY_SIZE(insns); i++) {
> +		__u32 val;
> +
> +		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
> +			goto cleanup;
> +
> +		ASSERT_EQ(val, i, "val should be equal i");
> +	}
> +
> +cleanup:
> +	close(prog_fd);
> +	close(map_fd);
> +}
> +

[...]

Re: [RFC PATCH bpf-next 03/14] selftests/bpf: add selftests for new insn_set map

[Anton Protopopov]

On 25/03/18 01:56PM, Yonghong Song wrote:
> 
> 
> On 3/18/25 7:33 AM, Anton Protopopov wrote:
> > Tests are split in two parts.
> > 
> > The `bpf_insn_set_ops` test checks that the map is managed properly:
> > 
> >    * Incorrect instruction indexes are rejected
> >    * Non-sorted and non-unique indexes are rejected
> >    * Unfrozen maps are not accepted
> >    * Two programs can't use the same map
> >    * BPF progs can't operate the map
> > 
> > The `bpf_insn_set_reloc` part validates, as best as it can do it from user
> > space, that instructions are relocated properly:
> > 
> >    * no relocations => map is the same
> >    * expected relocations when instructions are added
> >    * expected relocations when instructions are deleted
> >    * expected relocations when multiple functions are present
> > 
> > Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> > ---
> >   .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
> >   1 file changed, 639 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> > 
> > diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> > new file mode 100644
> > index 000000000000..796980bd4fcb
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> > @@ -0,0 +1,639 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +#include <bpf/bpf.h>
> > +#include <test_progs.h>
> > +
> > +static inline int map_create(__u32 map_type, __u32 max_entries)
> > +{
> > +	const char *map_name = "insn_set";
> > +	__u32 key_size = 4;
> > +	__u32 value_size = 4;
> > +
> > +	return bpf_map_create(map_type, map_name, key_size, value_size, max_entries, NULL);
> > +}
> > +
> > +/*
> > + * Load a program, which will not be anyhow mangled by the verifier.  Add an
> > + * insn_set map pointing to every instruction. Check that it hasn't changed
> > + * after the program load.
> > + */
> > +static void check_one_to_one_mapping(void)
> > +{
> > +	struct bpf_insn insns[] = {
> > +		BPF_MOV64_IMM(BPF_REG_0, 4),
> > +		BPF_MOV64_IMM(BPF_REG_0, 3),
> > +		BPF_MOV64_IMM(BPF_REG_0, 2),
> > +		BPF_MOV64_IMM(BPF_REG_0, 1),
> > +		BPF_MOV64_IMM(BPF_REG_0, 0),
> > +		BPF_EXIT_INSN(),
> > +	};
> > +	int prog_fd, map_fd;
> 
> prog_fd needs to be initialized to something like -1.

Thanks! I've fixed this and similar occurrences.

Also replaced syscall(BPF_PROG_LOAD) with libbpf wrappers, so the code
is a bit shorter now.  Will resend the patch to this thread shortly.

> > +	union bpf_attr attr = {
> > +		.prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
> > +		.insns     = ptr_to_u64(insns),
> > +		.insn_cnt  = ARRAY_SIZE(insns),
> > +		.license   = ptr_to_u64("GPL"),
> > +		.fd_array = ptr_to_u64(&map_fd),
> > +		.fd_array_cnt = 1,
> > +	};
> > +	int i;
> > +
> > +	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
> > +	if (!ASSERT_GE(map_fd, 0, "map_create"))
> > +		return;
> > +
> > +	for (i = 0; i < ARRAY_SIZE(insns); i++)
> > +		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
> > +			goto cleanup;
> 
> Otherwise, goto cleanup here will goto cleanup and close(prog_fd) will close
> a random prog_fd. Please check the rest of prog_fd usage.
> 
> > +
> > +	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
> > +		return;
> > +
> > +	prog_fd = syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
> > +	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
> > +		goto cleanup;
> > +
> > +	for (i = 0; i < ARRAY_SIZE(insns); i++) {
> > +		__u32 val;
> > +
> > +		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
> > +			goto cleanup;
> > +
> > +		ASSERT_EQ(val, i, "val should be equal i");
> > +	}
> > +
> > +cleanup:
> > +	close(prog_fd);
> > +	close(map_fd);
> > +}
> > +
> 
> [...]
> 

[RFC PATCH bpf-next 03/14] selftests/bpf: add selftests for new insn_set map

[Anton Protopopov]

Tests are split in two parts.

The `bpf_insn_set_ops` test checks that the map is managed properly:

  * Incorrect instruction indexes are rejected
  * Non-sorted and non-unique indexes are rejected
  * Unfrozen maps are not accepted
  * Two programs can't use the same map
  * BPF progs can't operate the map

The `bpf_insn_set_reloc` part validates, as best as it can do it from user
space, that instructions are relocated properly:

  * no relocations => map is the same
  * expected relocations when instructions are added
  * expected relocations when instructions are deleted
  * expected relocations when multiple functions are present

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 .../selftests/bpf/prog_tests/bpf_insn_set.c   | 556 ++++++++++++++++++
 1 file changed, 556 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
new file mode 100644
index 000000000000..9a9d9f1e9885
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
@@ -0,0 +1,556 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <bpf/bpf.h>
+#include <test_progs.h>
+
+static int map_create(__u32 map_type, __u32 max_entries)
+{
+	const char *map_name = "insn_set";
+	__u32 key_size = 4;
+	__u32 value_size = 4;
+
+	return bpf_map_create(map_type, map_name, key_size, value_size, max_entries, NULL);
+}
+
+static int prog_load(struct bpf_insn *insns, __u32 insn_cnt, int *fd_array, __u32 fd_array_cnt)
+{
+	LIBBPF_OPTS(bpf_prog_load_opts, opts);
+
+	opts.fd_array = fd_array;
+	opts.fd_array_cnt = fd_array_cnt;
+
+	return bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
+}
+
+/*
+ * Load a program, which will not be anyhow mangled by the verifier.  Add an
+ * insn_set map pointing to every instruction. Check that it hasn't changed
+ * after the program load.
+ */
+static void check_one_to_one_mapping(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/*
+ * Try to load a program with a map which points to outside of the program
+ */
+static void check_out_of_bounds_index(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	int key, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	key = 0;
+	val = ARRAY_SIZE(insns); /* too big */
+	if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &key, &val, 0), 0, "bpf_map_update_elem"))
+		goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)")) {
+		close(prog_fd);
+		goto cleanup;
+	}
+
+cleanup:
+	close(map_fd);
+}
+
+/*
+ * Try to load a program with a map which points to the middle of 16-bit insn
+ */
+static void check_mid_insn_index(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_LD_IMM64(BPF_REG_0, 0), /* 2 x 8 */
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	int key, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	key = 0;
+	val = 1; /* middle of 16-byte instruction */
+	if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &key, &val, 0), 0, "bpf_map_update_elem"))
+		goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)")) {
+		close(prog_fd);
+		goto cleanup;
+	}
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_incorrect_index(void)
+{
+	check_out_of_bounds_index();
+	check_mid_insn_index();
+}
+
+static void check_not_sorted(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	int i, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		val = ARRAY_SIZE(insns) - i - 1; /* reverse indexes */
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+	}
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)")) {
+		close(prog_fd);
+		goto cleanup;
+	}
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_not_unique(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 4),
+		BPF_MOV64_IMM(BPF_REG_0, 3),
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd, map_fd;
+	int i, val;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		val = 1;
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+	}
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)")) {
+		close(prog_fd);
+		goto cleanup;
+	}
+
+cleanup:
+	close(map_fd);
+}
+
+static void check_not_sorted_or_unique(void)
+{
+	check_not_sorted();
+	check_not_unique();
+}
+
+/*
+ * Load a program with two patches (get jiffies, for simplicity). Add an
+ * insn_set map pointing to every instruction. Check how it was relocated
+ * after the program load.
+ */
+static void check_relocate_simple(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+	__u32 map_in[] = {0, 1, 2, 3, 4, 5};
+	__u32 map_out[] = {0, 1, 4, 5, 8, 9};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/*
+ * Verifier can delete code in two cases: nops & dead code. From the relocation
+ * point of view, the two cases look the same, so test using the simplest
+ * method: by loading some nops
+ */
+static void check_relocate_deletions(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+	__u32 map_in[] = {0, 1, 2, 3, 4, 5};
+	__u32 map_out[] = {0, -1, 1, -1, 2, 3};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_relocate_with_functions(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 2),
+		BPF_MOV64_IMM(BPF_REG_0, 1),
+		BPF_EXIT_INSN(),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_jiffies64),
+		BPF_JMP_IMM(BPF_JA, 0, 0, 0), /* nop */
+		BPF_MOV64_IMM(BPF_REG_0, 2),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+	__u32 map_in[] =  { 0, 1,  2, 3, 4, 5, /* func */  6, 7,  8, 9, 10};
+	__u32 map_out[] = {-1, 0, -1, 3, 4, 5, /* func */ -1, 6, -1, 9, 10};
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &map_in[i], 0), 0,
+			       "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, map_out[i], "val should be equal map_out[i]");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/* Once map was initialized, it should be frozen */
+static void check_load_unfrozen_map(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)"))
+		goto cleanup;
+
+	/* correctness: now freeze the map, the program should load fine */
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+/* Map can be used only by one BPF program */
+static void check_no_map_reuse(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd, extra_fd = -1;
+	int i;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, ARRAY_SIZE(insns));
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++)
+		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &i, 0), 0, "bpf_map_update_elem"))
+			goto cleanup;
+
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(insns); i++) {
+		__u32 val;
+
+		if (!ASSERT_EQ(bpf_map_lookup_elem(map_fd, &i, &val), 0, "bpf_map_lookup_elem"))
+			goto cleanup;
+
+		ASSERT_EQ(val, i, "val should be equal i");
+	}
+
+	errno = 0;
+	extra_fd = prog_load(insns, ARRAY_SIZE(insns), &map_fd, 1);
+	if (!ASSERT_EQ(extra_fd, -EBUSY, "program should have been rejected (extra_fd != -EBUSY)"))
+		goto cleanup;
+
+	/* correctness: check that prog is still loadable without fd_array */
+	extra_fd = prog_load(insns, ARRAY_SIZE(insns), NULL, 0);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD): expected no error"))
+		goto cleanup;
+
+cleanup:
+	close(extra_fd);
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_bpf_no_lookup(void)
+{
+	struct bpf_insn insns[] = {
+		BPF_LD_MAP_FD(BPF_REG_1, 0),
+		BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+		BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+		BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+		BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+		BPF_EXIT_INSN(),
+	};
+	int prog_fd = -1, map_fd;
+
+	map_fd = map_create(BPF_MAP_TYPE_INSN_SET, 1);
+	if (!ASSERT_GE(map_fd, 0, "map_create"))
+		return;
+
+	/* otherwise will be rejected as unfrozen */
+	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
+		goto cleanup;
+
+	insns[0].imm = map_fd;
+
+	errno = 0;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), NULL, 0);
+	if (!ASSERT_EQ(prog_fd, -EINVAL, "program should have been rejected (prog_fd != -EINVAL)"))
+		goto cleanup;
+
+	/* correctness: check that prog is still loadable with normal map */
+	close(map_fd);
+	map_fd = map_create(BPF_MAP_TYPE_ARRAY, 1);
+	insns[0].imm = map_fd;
+	prog_fd = prog_load(insns, ARRAY_SIZE(insns), NULL, 0);
+	if (!ASSERT_GE(prog_fd, 0, "bpf(BPF_PROG_LOAD)"))
+		goto cleanup;
+
+cleanup:
+	close(prog_fd);
+	close(map_fd);
+}
+
+static void check_bpf_side(void)
+{
+	check_bpf_no_lookup();
+}
+
+/* Test how relocations work */
+void test_bpf_insn_set_reloc(void)
+{
+	if (test__start_subtest("one2one"))
+		check_one_to_one_mapping();
+
+	if (test__start_subtest("relocate-simple"))
+		check_relocate_simple();
+
+	if (test__start_subtest("relocate-deletions"))
+		check_relocate_deletions();
+
+	if (test__start_subtest("relocate-multiple-functions"))
+		check_relocate_with_functions();
+}
+
+/* Check all kinds of operations and related restrictions */
+void test_bpf_insn_set_ops(void)
+{
+	if (test__start_subtest("incorrect-index"))
+		check_incorrect_index();
+
+	if (test__start_subtest("not-sorted-or-unique"))
+		check_not_sorted_or_unique();
+
+	if (test__start_subtest("load-unfrozen-map"))
+		check_load_unfrozen_map();
+
+	if (test__start_subtest("no-map-reuse"))
+		check_no_map_reuse();
+
+	if (test__start_subtest("bpf-side-ops"))
+		check_bpf_side();
+}
-- 
2.34.1

[RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[Anton Protopopov]

Add support for a new version of JA instruction, a static branch JA. Such
instructions may either jump to the specified offset or act as nops. To
distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
should be set for the SRC register.

By default on program load such instructions are jitted as a normal JA.
However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
then the instruction is jitted to a NOP.

In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
instructions will be added:

	asm volatile goto ("nop_or_gotol %l[label]" :::: label);

will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and

	asm volatile goto ("gotol_or_nop %l[label]" :::: label);

will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
The reason for adding two instructions is that both are required to implement
static keys functionality for BPF, namely, to distinguish between likely and
unlikely branches.

The verifier logic is extended to check both possible paths: jump and nop.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 arch/x86/net/bpf_jit_comp.c    | 19 +++++++++++++--
 include/uapi/linux/bpf.h       | 10 ++++++++
 kernel/bpf/verifier.c          | 43 +++++++++++++++++++++++++++-------
 tools/include/uapi/linux/bpf.h | 10 ++++++++
 4 files changed, 71 insertions(+), 11 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index d3491cc0898b..5856ac1aab80 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
 	*pprog = prog;
 }
 
+static bool is_static_ja_nop(const struct bpf_insn *insn)
+{
+	u8 code = insn->code;
+
+	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
+	       (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
+	       (insn->src_reg & BPF_STATIC_BRANCH_NOP);
+}
+
 #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
 
 #define __LOAD_TCC_PTR(off)			\
@@ -2519,9 +2528,15 @@ st:			if (is_imm8(insn->off))
 					}
 					emit_nops(&prog, INSN_SZ_DIFF - 2);
 				}
-				EMIT2(0xEB, jmp_offset);
+				if (is_static_ja_nop(insn))
+					emit_nops(&prog, 2);
+				else
+					EMIT2(0xEB, jmp_offset);
 			} else if (is_simm32(jmp_offset)) {
-				EMIT1_off32(0xE9, jmp_offset);
+				if (is_static_ja_nop(insn))
+					emit_nops(&prog, 5);
+				else
+					EMIT1_off32(0xE9, jmp_offset);
 			} else {
 				pr_err("jmp gen bug %llx\n", jmp_offset);
 				return -EFAULT;
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index b8e588ed6406..57e0fd636a27 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
 	};
 };
 
+/* Flags for JA insn, passed in SRC_REG */
+enum {
+	BPF_STATIC_BRANCH_JA  = 1 << 0,
+	BPF_STATIC_BRANCH_NOP = 1 << 1,
+};
+
+#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
+				BPF_STATIC_BRANCH_NOP)
+
+
 #define BPF_OBJ_NAME_LEN 16U
 
 union bpf_attr {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6554f7aea0d8..0860ef57d5af 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 		else
 			off = insn->imm;
 
-		/* unconditional jump with single edge */
-		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
-		if (ret)
-			return ret;
+		if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
+			/* static branch - jump with two edges */
+			mark_prune_point(env, t);
 
-		mark_prune_point(env, t + off + 1);
-		mark_jmp_point(env, t + off + 1);
+			ret = push_insn(t, t + 1, FALLTHROUGH, env);
+			if (ret)
+				return ret;
+
+			ret = push_insn(t, t + off + 1, BRANCH, env);
+		} else {
+			/* unconditional jump with single edge */
+			ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
+			if (ret)
+				return ret;
 
+			mark_prune_point(env, t + off + 1);
+			mark_jmp_point(env, t + off + 1);
+		}
 		return ret;
 
 	default:
@@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
 
 				mark_reg_scratched(env, BPF_REG_0);
 			} else if (opcode == BPF_JA) {
+				struct bpf_verifier_state *other_branch;
+				u32 jmp_offset;
+
 				if (BPF_SRC(insn->code) != BPF_K ||
-				    insn->src_reg != BPF_REG_0 ||
+				    (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
 				    insn->dst_reg != BPF_REG_0 ||
 				    (class == BPF_JMP && insn->imm != 0) ||
 				    (class == BPF_JMP32 && insn->off != 0)) {
@@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
 				}
 
 				if (class == BPF_JMP)
-					env->insn_idx += insn->off + 1;
+					jmp_offset = insn->off + 1;
 				else
-					env->insn_idx += insn->imm + 1;
+					jmp_offset = insn->imm + 1;
+
+				/* Staic branch can either jump to +off or +0 */
+				if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
+					other_branch = push_stack(env, env->insn_idx + jmp_offset,
+							env->insn_idx, false);
+					if (!other_branch)
+						return -EFAULT;
+
+					jmp_offset = 1;
+				}
+
+				env->insn_idx += jmp_offset;
 				continue;
 
 			} else if (opcode == BPF_EXIT) {
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index b8e588ed6406..57e0fd636a27 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
 	};
 };
 
+/* Flags for JA insn, passed in SRC_REG */
+enum {
+	BPF_STATIC_BRANCH_JA  = 1 << 0,
+	BPF_STATIC_BRANCH_NOP = 1 << 1,
+};
+
+#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
+				BPF_STATIC_BRANCH_NOP)
+
+
 #define BPF_OBJ_NAME_LEN 16U
 
 union bpf_attr {
-- 
2.34.1

Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[David Faust]

On 3/18/25 07:33, Anton Protopopov wrote:
> Add support for a new version of JA instruction, a static branch JA. Such
> instructions may either jump to the specified offset or act as nops. To
> distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
> should be set for the SRC register.
> 
> By default on program load such instructions are jitted as a normal JA.
> However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
> then the instruction is jitted to a NOP.

[adding context from the cover letter:]
> 3) Patch 4 adds support for a new BPF instruction. It looks
> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> may_goto. Reasons: a follow up will add support for
> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> Then another follow up will add support CALL|BPF_X, for which there's
> no corresponding magic instruction (to be discussed at the following
> LSF/MM/BPF).

I don't understand the reasoning to extend JA rather than JCOND.

Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
set to distinguish from the absolute jumps here?
If the problem is that the indirect version will need both reigster
fields and JCOND is using SRC to encode the operation (0 for may_goto),
aren't you going to have exactly the same problem with BPF_JA|BPF_X and
the BPF_STATIC_BRANCH flag?  Or is the plan to stick the flag in another
different field of BPF_JA|BPF_X instruction...?

It seems like the general problem here that there is a growing class of
statically-decided-post-compiler conditional jumps, but no more free
insn class bits to use.  I suggest we try hard to encapsulate them as
much as possible under JCOND rather than (ab)using different fields of
different JMP insns to encode the 'maybe' versions on a case-by-case
basis.

To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
of insn and encode all of these conditional pseudo-jumps under it?

As far as I am aware (I may be out of date), the only JCOND insn
currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
offset. That seems to leave a lot of room (and bits) to design a whole
sub-class of JMP|JCOND instructions in a backwards compatible way...

> 
> In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
> instructions will be added:
> 
> 	asm volatile goto ("nop_or_gotol %l[label]" :::: label);
> 
> will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
> 
> 	asm volatile goto ("gotol_or_nop %l[label]" :::: label);
> 
> will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
> The reason for adding two instructions is that both are required to implement
> static keys functionality for BPF, namely, to distinguish between likely and
> unlikely branches.
> 
> The verifier logic is extended to check both possible paths: jump and nop.
> 
> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> ---
>  arch/x86/net/bpf_jit_comp.c    | 19 +++++++++++++--
>  include/uapi/linux/bpf.h       | 10 ++++++++
>  kernel/bpf/verifier.c          | 43 +++++++++++++++++++++++++++-------
>  tools/include/uapi/linux/bpf.h | 10 ++++++++
>  4 files changed, 71 insertions(+), 11 deletions(-)
> 
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index d3491cc0898b..5856ac1aab80 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
>  	*pprog = prog;
>  }
>  
> +static bool is_static_ja_nop(const struct bpf_insn *insn)
> +{
> +	u8 code = insn->code;
> +
> +	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
> +	       (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
> +	       (insn->src_reg & BPF_STATIC_BRANCH_NOP);
> +}
> +
>  #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
>  
>  #define __LOAD_TCC_PTR(off)			\
> @@ -2519,9 +2528,15 @@ st:			if (is_imm8(insn->off))
>  					}
>  					emit_nops(&prog, INSN_SZ_DIFF - 2);
>  				}
> -				EMIT2(0xEB, jmp_offset);
> +				if (is_static_ja_nop(insn))
> +					emit_nops(&prog, 2);
> +				else
> +					EMIT2(0xEB, jmp_offset);
>  			} else if (is_simm32(jmp_offset)) {
> -				EMIT1_off32(0xE9, jmp_offset);
> +				if (is_static_ja_nop(insn))
> +					emit_nops(&prog, 5);
> +				else
> +					EMIT1_off32(0xE9, jmp_offset);
>  			} else {
>  				pr_err("jmp gen bug %llx\n", jmp_offset);
>  				return -EFAULT;
> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> index b8e588ed6406..57e0fd636a27 100644
> --- a/include/uapi/linux/bpf.h
> +++ b/include/uapi/linux/bpf.h
> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>  	};
>  };
>  
> +/* Flags for JA insn, passed in SRC_REG */
> +enum {
> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> +};
> +
> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> +				BPF_STATIC_BRANCH_NOP)
> +
> +
>  #define BPF_OBJ_NAME_LEN 16U
>  
>  union bpf_attr {
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 6554f7aea0d8..0860ef57d5af 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
>  		else
>  			off = insn->imm;
>  
> -		/* unconditional jump with single edge */
> -		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> -		if (ret)
> -			return ret;
> +		if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> +			/* static branch - jump with two edges */
> +			mark_prune_point(env, t);
>  
> -		mark_prune_point(env, t + off + 1);
> -		mark_jmp_point(env, t + off + 1);
> +			ret = push_insn(t, t + 1, FALLTHROUGH, env);
> +			if (ret)
> +				return ret;
> +
> +			ret = push_insn(t, t + off + 1, BRANCH, env);
> +		} else {
> +			/* unconditional jump with single edge */
> +			ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> +			if (ret)
> +				return ret;
>  
> +			mark_prune_point(env, t + off + 1);
> +			mark_jmp_point(env, t + off + 1);
> +		}
>  		return ret;
>  
>  	default:
> @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
>  
>  				mark_reg_scratched(env, BPF_REG_0);
>  			} else if (opcode == BPF_JA) {
> +				struct bpf_verifier_state *other_branch;
> +				u32 jmp_offset;
> +
>  				if (BPF_SRC(insn->code) != BPF_K ||
> -				    insn->src_reg != BPF_REG_0 ||
> +				    (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
>  				    insn->dst_reg != BPF_REG_0 ||
>  				    (class == BPF_JMP && insn->imm != 0) ||
>  				    (class == BPF_JMP32 && insn->off != 0)) {
> @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
>  				}
>  
>  				if (class == BPF_JMP)
> -					env->insn_idx += insn->off + 1;
> +					jmp_offset = insn->off + 1;
>  				else
> -					env->insn_idx += insn->imm + 1;
> +					jmp_offset = insn->imm + 1;
> +
> +				/* Staic branch can either jump to +off or +0 */
> +				if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> +					other_branch = push_stack(env, env->insn_idx + jmp_offset,
> +							env->insn_idx, false);
> +					if (!other_branch)
> +						return -EFAULT;
> +
> +					jmp_offset = 1;
> +				}
> +
> +				env->insn_idx += jmp_offset;
>  				continue;
>  
>  			} else if (opcode == BPF_EXIT) {
> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> index b8e588ed6406..57e0fd636a27 100644
> --- a/tools/include/uapi/linux/bpf.h
> +++ b/tools/include/uapi/linux/bpf.h
> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>  	};
>  };
>  
> +/* Flags for JA insn, passed in SRC_REG */
> +enum {
> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> +};
> +
> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> +				BPF_STATIC_BRANCH_NOP)
> +
> +
>  #define BPF_OBJ_NAME_LEN 16U
>  
>  union bpf_attr {

Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[Anton Protopopov]

On 25/03/18 12:00PM, David Faust wrote:
> 
> 
> On 3/18/25 07:33, Anton Protopopov wrote:
> > Add support for a new version of JA instruction, a static branch JA. Such
> > instructions may either jump to the specified offset or act as nops. To
> > distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
> > should be set for the SRC register.
> > 
> > By default on program load such instructions are jitted as a normal JA.
> > However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
> > then the instruction is jitted to a NOP.
> 
> [adding context from the cover letter:]
> > 3) Patch 4 adds support for a new BPF instruction. It looks
> > reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> > may_goto. Reasons: a follow up will add support for
> > BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> > Then another follow up will add support CALL|BPF_X, for which there's
> > no corresponding magic instruction (to be discussed at the following
> > LSF/MM/BPF).
> 
> I don't understand the reasoning to extend JA rather than JCOND.
> 
> Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
> set to distinguish from the absolute jumps here?
>
> If the problem is that the indirect version will need both reigster
> fields and JCOND is using SRC to encode the operation (0 for may_goto),
> aren't you going to have exactly the same problem with BPF_JA|BPF_X and
> the BPF_STATIC_BRANCH flag?  Or is the plan to stick the flag in another
> different field of BPF_JA|BPF_X instruction...?
> 
> It seems like the general problem here that there is a growing class of
> statically-decided-post-compiler conditional jumps, but no more free
> insn class bits to use.  I suggest we try hard to encapsulate them as
> much as possible under JCOND rather than (ab)using different fields of
> different JMP insns to encode the 'maybe' versions on a case-by-case
> basis.
> 
> To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
> of insn and encode all of these conditional pseudo-jumps under it?

I agree that the "magic jump" (BPF_STATIC_BRANCH) is, maybe, better to go with
BPF_JMP|BPF_JCOND, as it emphasizes that the instruction is a special one.

However, for indirect jumps the BPF_JMP|BPF_JA|BPF_X looks more natural.

> As far as I am aware (I may be out of date), the only JCOND insn
> currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
> offset. That seems to leave a lot of room (and bits) to design a whole
> sub-class of JMP|JCOND instructions in a backwards compatible way...
> 
> > 
> > In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
> > instructions will be added:
> > 
> > 	asm volatile goto ("nop_or_gotol %l[label]" :::: label);
> > 
> > will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
> > 
> > 	asm volatile goto ("gotol_or_nop %l[label]" :::: label);
> > 
> > will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
> > The reason for adding two instructions is that both are required to implement
> > static keys functionality for BPF, namely, to distinguish between likely and
> > unlikely branches.
> > 
> > The verifier logic is extended to check both possible paths: jump and nop.
> > 
> > Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> > ---
> >  arch/x86/net/bpf_jit_comp.c    | 19 +++++++++++++--
> >  include/uapi/linux/bpf.h       | 10 ++++++++
> >  kernel/bpf/verifier.c          | 43 +++++++++++++++++++++++++++-------
> >  tools/include/uapi/linux/bpf.h | 10 ++++++++
> >  4 files changed, 71 insertions(+), 11 deletions(-)
> > 
> > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> > index d3491cc0898b..5856ac1aab80 100644
> > --- a/arch/x86/net/bpf_jit_comp.c
> > +++ b/arch/x86/net/bpf_jit_comp.c
> > @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
> >  	*pprog = prog;
> >  }
> >  
> > +static bool is_static_ja_nop(const struct bpf_insn *insn)
> > +{
> > +	u8 code = insn->code;
> > +
> > +	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
> > +	       (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
> > +	       (insn->src_reg & BPF_STATIC_BRANCH_NOP);
> > +}
> > +
> >  #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
> >  
> >  #define __LOAD_TCC_PTR(off)			\
> > @@ -2519,9 +2528,15 @@ st:			if (is_imm8(insn->off))
> >  					}
> >  					emit_nops(&prog, INSN_SZ_DIFF - 2);
> >  				}
> > -				EMIT2(0xEB, jmp_offset);
> > +				if (is_static_ja_nop(insn))
> > +					emit_nops(&prog, 2);
> > +				else
> > +					EMIT2(0xEB, jmp_offset);
> >  			} else if (is_simm32(jmp_offset)) {
> > -				EMIT1_off32(0xE9, jmp_offset);
> > +				if (is_static_ja_nop(insn))
> > +					emit_nops(&prog, 5);
> > +				else
> > +					EMIT1_off32(0xE9, jmp_offset);
> >  			} else {
> >  				pr_err("jmp gen bug %llx\n", jmp_offset);
> >  				return -EFAULT;
> > diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> > index b8e588ed6406..57e0fd636a27 100644
> > --- a/include/uapi/linux/bpf.h
> > +++ b/include/uapi/linux/bpf.h
> > @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >  	};
> >  };
> >  
> > +/* Flags for JA insn, passed in SRC_REG */
> > +enum {
> > +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> > +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> > +};
> > +
> > +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> > +				BPF_STATIC_BRANCH_NOP)
> > +
> > +
> >  #define BPF_OBJ_NAME_LEN 16U
> >  
> >  union bpf_attr {
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 6554f7aea0d8..0860ef57d5af 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
> >  		else
> >  			off = insn->imm;
> >  
> > -		/* unconditional jump with single edge */
> > -		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> > -		if (ret)
> > -			return ret;
> > +		if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> > +			/* static branch - jump with two edges */
> > +			mark_prune_point(env, t);
> >  
> > -		mark_prune_point(env, t + off + 1);
> > -		mark_jmp_point(env, t + off + 1);
> > +			ret = push_insn(t, t + 1, FALLTHROUGH, env);
> > +			if (ret)
> > +				return ret;
> > +
> > +			ret = push_insn(t, t + off + 1, BRANCH, env);
> > +		} else {
> > +			/* unconditional jump with single edge */
> > +			ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> > +			if (ret)
> > +				return ret;
> >  
> > +			mark_prune_point(env, t + off + 1);
> > +			mark_jmp_point(env, t + off + 1);
> > +		}
> >  		return ret;
> >  
> >  	default:
> > @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
> >  
> >  				mark_reg_scratched(env, BPF_REG_0);
> >  			} else if (opcode == BPF_JA) {
> > +				struct bpf_verifier_state *other_branch;
> > +				u32 jmp_offset;
> > +
> >  				if (BPF_SRC(insn->code) != BPF_K ||
> > -				    insn->src_reg != BPF_REG_0 ||
> > +				    (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
> >  				    insn->dst_reg != BPF_REG_0 ||
> >  				    (class == BPF_JMP && insn->imm != 0) ||
> >  				    (class == BPF_JMP32 && insn->off != 0)) {
> > @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
> >  				}
> >  
> >  				if (class == BPF_JMP)
> > -					env->insn_idx += insn->off + 1;
> > +					jmp_offset = insn->off + 1;
> >  				else
> > -					env->insn_idx += insn->imm + 1;
> > +					jmp_offset = insn->imm + 1;
> > +
> > +				/* Staic branch can either jump to +off or +0 */
> > +				if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> > +					other_branch = push_stack(env, env->insn_idx + jmp_offset,
> > +							env->insn_idx, false);
> > +					if (!other_branch)
> > +						return -EFAULT;
> > +
> > +					jmp_offset = 1;
> > +				}
> > +
> > +				env->insn_idx += jmp_offset;
> >  				continue;
> >  
> >  			} else if (opcode == BPF_EXIT) {
> > diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> > index b8e588ed6406..57e0fd636a27 100644
> > --- a/tools/include/uapi/linux/bpf.h
> > +++ b/tools/include/uapi/linux/bpf.h
> > @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >  	};
> >  };
> >  
> > +/* Flags for JA insn, passed in SRC_REG */
> > +enum {
> > +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> > +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> > +};
> > +
> > +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> > +				BPF_STATIC_BRANCH_NOP)
> > +
> > +
> >  #define BPF_OBJ_NAME_LEN 16U
> >  
> >  union bpf_attr {
> 

Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[David Faust]

On 3/18/25 12:24, Anton Protopopov wrote:
> On 25/03/18 12:00PM, David Faust wrote:
>>
>>
>> On 3/18/25 07:33, Anton Protopopov wrote:
>>> Add support for a new version of JA instruction, a static branch JA. Such
>>> instructions may either jump to the specified offset or act as nops. To
>>> distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
>>> should be set for the SRC register.
>>>
>>> By default on program load such instructions are jitted as a normal JA.
>>> However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
>>> then the instruction is jitted to a NOP.
>>
>> [adding context from the cover letter:]
>>> 3) Patch 4 adds support for a new BPF instruction. It looks
>>> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
>>> may_goto. Reasons: a follow up will add support for
>>> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
>>> Then another follow up will add support CALL|BPF_X, for which there's
>>> no corresponding magic instruction (to be discussed at the following
>>> LSF/MM/BPF).
>>
>> I don't understand the reasoning to extend JA rather than JCOND.
>>
>> Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
>> set to distinguish from the absolute jumps here?
>>
>> If the problem is that the indirect version will need both reigster
>> fields and JCOND is using SRC to encode the operation (0 for may_goto),
>> aren't you going to have exactly the same problem with BPF_JA|BPF_X and
>> the BPF_STATIC_BRANCH flag?  Or is the plan to stick the flag in another
>> different field of BPF_JA|BPF_X instruction...?
>>
>> It seems like the general problem here that there is a growing class of
>> statically-decided-post-compiler conditional jumps, but no more free
>> insn class bits to use.  I suggest we try hard to encapsulate them as
>> much as possible under JCOND rather than (ab)using different fields of
>> different JMP insns to encode the 'maybe' versions on a case-by-case
>> basis.
>>
>> To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
>> of insn and encode all of these conditional pseudo-jumps under it?
> 
> I agree that the "magic jump" (BPF_STATIC_BRANCH) is, maybe, better to go with
> BPF_JMP|BPF_JCOND, as it emphasizes that the instruction is a special one.
> 
> However, for indirect jumps the BPF_JMP|BPF_JA|BPF_X looks more natural.

Ah, maybe I misunderstood the context; will these BPF_JMP|BPF_JA|BPF_X indirect
jumps exclusively be "real" or was the intent that they also have the "maybe"
variant (could be jitted to no-op)? I was thinking the latter.

For the always-real version I agree BPF_JA|BPF_X makes total sense.
If there is a "maybe" variant that could be jitted to no-op then that should
fall under JCOND.

> 
>> As far as I am aware (I may be out of date), the only JCOND insn
>> currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
>> offset. That seems to leave a lot of room (and bits) to design a whole
>> sub-class of JMP|JCOND instructions in a backwards compatible way...
>>
>>>
>>> In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
>>> instructions will be added:
>>>
>>> 	asm volatile goto ("nop_or_gotol %l[label]" :::: label);
>>>
>>> will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
>>>
>>> 	asm volatile goto ("gotol_or_nop %l[label]" :::: label);
>>>
>>> will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
>>> The reason for adding two instructions is that both are required to implement
>>> static keys functionality for BPF, namely, to distinguish between likely and
>>> unlikely branches.
>>>
>>> The verifier logic is extended to check both possible paths: jump and nop.
>>>
>>> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
>>> ---
>>>  arch/x86/net/bpf_jit_comp.c    | 19 +++++++++++++--
>>>  include/uapi/linux/bpf.h       | 10 ++++++++
>>>  kernel/bpf/verifier.c          | 43 +++++++++++++++++++++++++++-------
>>>  tools/include/uapi/linux/bpf.h | 10 ++++++++
>>>  4 files changed, 71 insertions(+), 11 deletions(-)
>>>
>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>> index d3491cc0898b..5856ac1aab80 100644
>>> --- a/arch/x86/net/bpf_jit_comp.c
>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>> @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
>>>  	*pprog = prog;
>>>  }
>>>  
>>> +static bool is_static_ja_nop(const struct bpf_insn *insn)
>>> +{
>>> +	u8 code = insn->code;
>>> +
>>> +	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
>>> +	       (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
>>> +	       (insn->src_reg & BPF_STATIC_BRANCH_NOP);
>>> +}
>>> +
>>>  #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
>>>  
>>>  #define __LOAD_TCC_PTR(off)			\
>>> @@ -2519,9 +2528,15 @@ st:			if (is_imm8(insn->off))
>>>  					}
>>>  					emit_nops(&prog, INSN_SZ_DIFF - 2);
>>>  				}
>>> -				EMIT2(0xEB, jmp_offset);
>>> +				if (is_static_ja_nop(insn))
>>> +					emit_nops(&prog, 2);
>>> +				else
>>> +					EMIT2(0xEB, jmp_offset);
>>>  			} else if (is_simm32(jmp_offset)) {
>>> -				EMIT1_off32(0xE9, jmp_offset);
>>> +				if (is_static_ja_nop(insn))
>>> +					emit_nops(&prog, 5);
>>> +				else
>>> +					EMIT1_off32(0xE9, jmp_offset);
>>>  			} else {
>>>  				pr_err("jmp gen bug %llx\n", jmp_offset);
>>>  				return -EFAULT;
>>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
>>> index b8e588ed6406..57e0fd636a27 100644
>>> --- a/include/uapi/linux/bpf.h
>>> +++ b/include/uapi/linux/bpf.h
>>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>>>  	};
>>>  };
>>>  
>>> +/* Flags for JA insn, passed in SRC_REG */
>>> +enum {
>>> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
>>> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
>>> +};
>>> +
>>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
>>> +				BPF_STATIC_BRANCH_NOP)
>>> +
>>> +
>>>  #define BPF_OBJ_NAME_LEN 16U
>>>  
>>>  union bpf_attr {
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index 6554f7aea0d8..0860ef57d5af 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
>>>  		else
>>>  			off = insn->imm;
>>>  
>>> -		/* unconditional jump with single edge */
>>> -		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
>>> -		if (ret)
>>> -			return ret;
>>> +		if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
>>> +			/* static branch - jump with two edges */
>>> +			mark_prune_point(env, t);
>>>  
>>> -		mark_prune_point(env, t + off + 1);
>>> -		mark_jmp_point(env, t + off + 1);
>>> +			ret = push_insn(t, t + 1, FALLTHROUGH, env);
>>> +			if (ret)
>>> +				return ret;
>>> +
>>> +			ret = push_insn(t, t + off + 1, BRANCH, env);
>>> +		} else {
>>> +			/* unconditional jump with single edge */
>>> +			ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
>>> +			if (ret)
>>> +				return ret;
>>>  
>>> +			mark_prune_point(env, t + off + 1);
>>> +			mark_jmp_point(env, t + off + 1);
>>> +		}
>>>  		return ret;
>>>  
>>>  	default:
>>> @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
>>>  
>>>  				mark_reg_scratched(env, BPF_REG_0);
>>>  			} else if (opcode == BPF_JA) {
>>> +				struct bpf_verifier_state *other_branch;
>>> +				u32 jmp_offset;
>>> +
>>>  				if (BPF_SRC(insn->code) != BPF_K ||
>>> -				    insn->src_reg != BPF_REG_0 ||
>>> +				    (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
>>>  				    insn->dst_reg != BPF_REG_0 ||
>>>  				    (class == BPF_JMP && insn->imm != 0) ||
>>>  				    (class == BPF_JMP32 && insn->off != 0)) {
>>> @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
>>>  				}
>>>  
>>>  				if (class == BPF_JMP)
>>> -					env->insn_idx += insn->off + 1;
>>> +					jmp_offset = insn->off + 1;
>>>  				else
>>> -					env->insn_idx += insn->imm + 1;
>>> +					jmp_offset = insn->imm + 1;
>>> +
>>> +				/* Staic branch can either jump to +off or +0 */
>>> +				if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
>>> +					other_branch = push_stack(env, env->insn_idx + jmp_offset,
>>> +							env->insn_idx, false);
>>> +					if (!other_branch)
>>> +						return -EFAULT;
>>> +
>>> +					jmp_offset = 1;
>>> +				}
>>> +
>>> +				env->insn_idx += jmp_offset;
>>>  				continue;
>>>  
>>>  			} else if (opcode == BPF_EXIT) {
>>> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
>>> index b8e588ed6406..57e0fd636a27 100644
>>> --- a/tools/include/uapi/linux/bpf.h
>>> +++ b/tools/include/uapi/linux/bpf.h
>>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
>>>  	};
>>>  };
>>>  
>>> +/* Flags for JA insn, passed in SRC_REG */
>>> +enum {
>>> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
>>> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
>>> +};
>>> +
>>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
>>> +				BPF_STATIC_BRANCH_NOP)
>>> +
>>> +
>>>  #define BPF_OBJ_NAME_LEN 16U
>>>  
>>>  union bpf_attr {
>>

Re: [RFC PATCH bpf-next 04/14] bpf: add support for an extended JA instruction

[Anton Protopopov]

On 25/03/18 12:30PM, David Faust wrote:
> 
> 
> On 3/18/25 12:24, Anton Protopopov wrote:
> > On 25/03/18 12:00PM, David Faust wrote:
> >>
> >>
> >> On 3/18/25 07:33, Anton Protopopov wrote:
> >>> Add support for a new version of JA instruction, a static branch JA. Such
> >>> instructions may either jump to the specified offset or act as nops. To
> >>> distinguish such instructions from normal JA the BPF_STATIC_BRANCH_JA flag
> >>> should be set for the SRC register.
> >>>
> >>> By default on program load such instructions are jitted as a normal JA.
> >>> However, if the BPF_STATIC_BRANCH_NOP flag is set in the SRC register,
> >>> then the instruction is jitted to a NOP.
> >>
> >> [adding context from the cover letter:]
> >>> 3) Patch 4 adds support for a new BPF instruction. It looks
> >>> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> >>> may_goto. Reasons: a follow up will add support for
> >>> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> >>> Then another follow up will add support CALL|BPF_X, for which there's
> >>> no corresponding magic instruction (to be discussed at the following
> >>> LSF/MM/BPF).
> >>
> >> I don't understand the reasoning to extend JA rather than JCOND.
> >>
> >> Couldn't the followup for indirect jumps also use JCOND, with BPF_SRC_X
> >> set to distinguish from the absolute jumps here?
> >>
> >> If the problem is that the indirect version will need both reigster
> >> fields and JCOND is using SRC to encode the operation (0 for may_goto),
> >> aren't you going to have exactly the same problem with BPF_JA|BPF_X and
> >> the BPF_STATIC_BRANCH flag?  Or is the plan to stick the flag in another
> >> different field of BPF_JA|BPF_X instruction...?
> >>
> >> It seems like the general problem here that there is a growing class of
> >> statically-decided-post-compiler conditional jumps, but no more free
> >> insn class bits to use.  I suggest we try hard to encapsulate them as
> >> much as possible under JCOND rather than (ab)using different fields of
> >> different JMP insns to encode the 'maybe' versions on a case-by-case
> >> basis.
> >>
> >> To put it another way, why not make BPF_JMP|BPF_JCOND its own "class"
> >> of insn and encode all of these conditional pseudo-jumps under it?
> > 
> > I agree that the "magic jump" (BPF_STATIC_BRANCH) is, maybe, better to go with
> > BPF_JMP|BPF_JCOND, as it emphasizes that the instruction is a special one.
> > 
> > However, for indirect jumps the BPF_JMP|BPF_JA|BPF_X looks more natural.
> 
> Ah, maybe I misunderstood the context; will these BPF_JMP|BPF_JA|BPF_X indirect
> jumps exclusively be "real" or was the intent that they also have the "maybe"
> variant (could be jitted to no-op)? I was thinking the latter.
> 
> For the always-real version I agree BPF_JA|BPF_X makes total sense.
> If there is a "maybe" variant that could be jitted to no-op then that should
> fall under JCOND.

Yes, those are real, no patching: goto rX (where rX is properly loaded
from an instruction set).

> > 
> >> As far as I am aware (I may be out of date), the only JCOND insn
> >> currently is may_goto (src_reg == 0), and may_goto only uses the 16-bit
> >> offset. That seems to leave a lot of room (and bits) to design a whole
> >> sub-class of JMP|JCOND instructions in a backwards compatible way...
> >>
> >>>
> >>> In order to generate BPF_STATIC_BRANCH_JA instructions using llvm two new
> >>> instructions will be added:
> >>>
> >>> 	asm volatile goto ("nop_or_gotol %l[label]" :::: label);
> >>>
> >>> will generate the BPF_STATIC_BRANCH_JA|BPF_STATIC_BRANCH_NOP instuction and
> >>>
> >>> 	asm volatile goto ("gotol_or_nop %l[label]" :::: label);
> >>>
> >>> will generate a BPF_STATIC_BRANCH_JA instruction, without an extra bit set.
> >>> The reason for adding two instructions is that both are required to implement
> >>> static keys functionality for BPF, namely, to distinguish between likely and
> >>> unlikely branches.
> >>>
> >>> The verifier logic is extended to check both possible paths: jump and nop.
> >>>
> >>> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> >>> ---
> >>>  arch/x86/net/bpf_jit_comp.c    | 19 +++++++++++++--
> >>>  include/uapi/linux/bpf.h       | 10 ++++++++
> >>>  kernel/bpf/verifier.c          | 43 +++++++++++++++++++++++++++-------
> >>>  tools/include/uapi/linux/bpf.h | 10 ++++++++
> >>>  4 files changed, 71 insertions(+), 11 deletions(-)
> >>>
> >>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> >>> index d3491cc0898b..5856ac1aab80 100644
> >>> --- a/arch/x86/net/bpf_jit_comp.c
> >>> +++ b/arch/x86/net/bpf_jit_comp.c
> >>> @@ -1482,6 +1482,15 @@ static void emit_priv_frame_ptr(u8 **pprog, void __percpu *priv_frame_ptr)
> >>>  	*pprog = prog;
> >>>  }
> >>>  
> >>> +static bool is_static_ja_nop(const struct bpf_insn *insn)
> >>> +{
> >>> +	u8 code = insn->code;
> >>> +
> >>> +	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
> >>> +	       (insn->src_reg & BPF_STATIC_BRANCH_JA) &&
> >>> +	       (insn->src_reg & BPF_STATIC_BRANCH_NOP);
> >>> +}
> >>> +
> >>>  #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
> >>>  
> >>>  #define __LOAD_TCC_PTR(off)			\
> >>> @@ -2519,9 +2528,15 @@ st:			if (is_imm8(insn->off))
> >>>  					}
> >>>  					emit_nops(&prog, INSN_SZ_DIFF - 2);
> >>>  				}
> >>> -				EMIT2(0xEB, jmp_offset);
> >>> +				if (is_static_ja_nop(insn))
> >>> +					emit_nops(&prog, 2);
> >>> +				else
> >>> +					EMIT2(0xEB, jmp_offset);
> >>>  			} else if (is_simm32(jmp_offset)) {
> >>> -				EMIT1_off32(0xE9, jmp_offset);
> >>> +				if (is_static_ja_nop(insn))
> >>> +					emit_nops(&prog, 5);
> >>> +				else
> >>> +					EMIT1_off32(0xE9, jmp_offset);
> >>>  			} else {
> >>>  				pr_err("jmp gen bug %llx\n", jmp_offset);
> >>>  				return -EFAULT;
> >>> diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
> >>> index b8e588ed6406..57e0fd636a27 100644
> >>> --- a/include/uapi/linux/bpf.h
> >>> +++ b/include/uapi/linux/bpf.h
> >>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >>>  	};
> >>>  };
> >>>  
> >>> +/* Flags for JA insn, passed in SRC_REG */
> >>> +enum {
> >>> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> >>> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> >>> +};
> >>> +
> >>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> >>> +				BPF_STATIC_BRANCH_NOP)
> >>> +
> >>> +
> >>>  #define BPF_OBJ_NAME_LEN 16U
> >>>  
> >>>  union bpf_attr {
> >>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >>> index 6554f7aea0d8..0860ef57d5af 100644
> >>> --- a/kernel/bpf/verifier.c
> >>> +++ b/kernel/bpf/verifier.c
> >>> @@ -17374,14 +17374,24 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
> >>>  		else
> >>>  			off = insn->imm;
> >>>  
> >>> -		/* unconditional jump with single edge */
> >>> -		ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> >>> -		if (ret)
> >>> -			return ret;
> >>> +		if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> >>> +			/* static branch - jump with two edges */
> >>> +			mark_prune_point(env, t);
> >>>  
> >>> -		mark_prune_point(env, t + off + 1);
> >>> -		mark_jmp_point(env, t + off + 1);
> >>> +			ret = push_insn(t, t + 1, FALLTHROUGH, env);
> >>> +			if (ret)
> >>> +				return ret;
> >>> +
> >>> +			ret = push_insn(t, t + off + 1, BRANCH, env);
> >>> +		} else {
> >>> +			/* unconditional jump with single edge */
> >>> +			ret = push_insn(t, t + off + 1, FALLTHROUGH, env);
> >>> +			if (ret)
> >>> +				return ret;
> >>>  
> >>> +			mark_prune_point(env, t + off + 1);
> >>> +			mark_jmp_point(env, t + off + 1);
> >>> +		}
> >>>  		return ret;
> >>>  
> >>>  	default:
> >>> @@ -19414,8 +19424,11 @@ static int do_check(struct bpf_verifier_env *env)
> >>>  
> >>>  				mark_reg_scratched(env, BPF_REG_0);
> >>>  			} else if (opcode == BPF_JA) {
> >>> +				struct bpf_verifier_state *other_branch;
> >>> +				u32 jmp_offset;
> >>> +
> >>>  				if (BPF_SRC(insn->code) != BPF_K ||
> >>> -				    insn->src_reg != BPF_REG_0 ||
> >>> +				    (insn->src_reg & ~BPF_STATIC_BRANCH_MASK) ||
> >>>  				    insn->dst_reg != BPF_REG_0 ||
> >>>  				    (class == BPF_JMP && insn->imm != 0) ||
> >>>  				    (class == BPF_JMP32 && insn->off != 0)) {
> >>> @@ -19424,9 +19437,21 @@ static int do_check(struct bpf_verifier_env *env)
> >>>  				}
> >>>  
> >>>  				if (class == BPF_JMP)
> >>> -					env->insn_idx += insn->off + 1;
> >>> +					jmp_offset = insn->off + 1;
> >>>  				else
> >>> -					env->insn_idx += insn->imm + 1;
> >>> +					jmp_offset = insn->imm + 1;
> >>> +
> >>> +				/* Staic branch can either jump to +off or +0 */
> >>> +				if (insn->src_reg & BPF_STATIC_BRANCH_JA) {
> >>> +					other_branch = push_stack(env, env->insn_idx + jmp_offset,
> >>> +							env->insn_idx, false);
> >>> +					if (!other_branch)
> >>> +						return -EFAULT;
> >>> +
> >>> +					jmp_offset = 1;
> >>> +				}
> >>> +
> >>> +				env->insn_idx += jmp_offset;
> >>>  				continue;
> >>>  
> >>>  			} else if (opcode == BPF_EXIT) {
> >>> diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
> >>> index b8e588ed6406..57e0fd636a27 100644
> >>> --- a/tools/include/uapi/linux/bpf.h
> >>> +++ b/tools/include/uapi/linux/bpf.h
> >>> @@ -1462,6 +1462,16 @@ struct bpf_stack_build_id {
> >>>  	};
> >>>  };
> >>>  
> >>> +/* Flags for JA insn, passed in SRC_REG */
> >>> +enum {
> >>> +	BPF_STATIC_BRANCH_JA  = 1 << 0,
> >>> +	BPF_STATIC_BRANCH_NOP = 1 << 1,
> >>> +};
> >>> +
> >>> +#define BPF_STATIC_BRANCH_MASK (BPF_STATIC_BRANCH_JA | \
> >>> +				BPF_STATIC_BRANCH_NOP)
> >>> +
> >>> +
> >>>  #define BPF_OBJ_NAME_LEN 16U
> >>>  
> >>>  union bpf_attr {
> >>
> 

[RFC PATCH bpf-next 05/14] bpf: Add kernel/bpftool asm support for new instructions

[Anton Protopopov]

Add asm support for new JA* instructions so kernel verifier and bpftool
xlated insn dumps can have proper asm syntax.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 kernel/bpf/disasm.c | 33 +++++++++++++++++++++++++++------
 1 file changed, 27 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/disasm.c b/kernel/bpf/disasm.c
index 20883c6b1546..fd6e0e85412a 100644
--- a/kernel/bpf/disasm.c
+++ b/kernel/bpf/disasm.c
@@ -183,6 +183,30 @@ static inline bool is_mov_percpu_addr(const struct bpf_insn *insn)
 	return insn->code == (BPF_ALU64 | BPF_MOV | BPF_X) && insn->off == BPF_ADDR_PERCPU;
 }
 
+static void print_bpf_ja_insn(bpf_insn_print_t verbose,
+			      void *private_data,
+			      const struct bpf_insn *insn)
+{
+	bool jmp32 = insn->code == (BPF_JMP32 | BPF_JA);
+	int off = jmp32 ? insn->imm : insn->off;
+	const char *suffix = jmp32 ? "l" : "";
+	char op[16];
+
+	switch (insn->src_reg & BPF_STATIC_BRANCH_MASK) {
+	case BPF_STATIC_BRANCH_JA:
+		snprintf(op, sizeof(op), "goto%s_or_nop", suffix);
+		break;
+	case BPF_STATIC_BRANCH_JA | BPF_STATIC_BRANCH_NOP:
+		snprintf(op, sizeof(op), "nop_or_goto%s", suffix);
+		break;
+	default:
+		snprintf(op, sizeof(op), "goto%s", suffix);
+		break;
+	}
+
+	verbose(private_data, "(%02x) %s pc%+d\n", insn->code, op, off);
+}
+
 void print_bpf_insn(const struct bpf_insn_cbs *cbs,
 		    const struct bpf_insn *insn,
 		    bool allow_ptr_leaks)
@@ -355,16 +379,13 @@ void print_bpf_insn(const struct bpf_insn_cbs *cbs,
 							tmp, sizeof(tmp)),
 					insn->imm);
 			}
-		} else if (insn->code == (BPF_JMP | BPF_JA)) {
-			verbose(cbs->private_data, "(%02x) goto pc%+d\n",
-				insn->code, insn->off);
+		} else if (insn->code == (BPF_JMP | BPF_JA) ||
+			   insn->code == (BPF_JMP32 | BPF_JA)) {
+			print_bpf_ja_insn(verbose, cbs->private_data, insn);
 		} else if (insn->code == (BPF_JMP | BPF_JCOND) &&
 			   insn->src_reg == BPF_MAY_GOTO) {
 			verbose(cbs->private_data, "(%02x) may_goto pc%+d\n",
 				insn->code, insn->off);
-		} else if (insn->code == (BPF_JMP32 | BPF_JA)) {
-			verbose(cbs->private_data, "(%02x) gotol pc%+d\n",
-				insn->code, insn->imm);
 		} else if (insn->code == (BPF_JMP | BPF_EXIT)) {
 			verbose(cbs->private_data, "(%02x) exit\n", insn->code);
 		} else if (BPF_SRC(insn->code) == BPF_X) {
-- 
2.34.1

[RFC PATCH bpf-next 06/14] bpf: add BPF_STATIC_KEY_UPDATE syscall

[Anton Protopopov]

Add a new bpf system call, BPF_STATIC_KEY_UPDATE, which allows users
to update static keys in BPF. Namely, this system call is executed as

    bpf(BPF_STATIC_KEY_UPDATE, attrs={map_fd, on})

where map_fd is a BPF static key, i.e., a map of type BPF_MAP_TYPE_INSN_SET
which points to one or more goto_or_nop/nop_or_goto instructions. The "on"
parameter is a boolean value to set this key on or off. if it is true/false,
then goto_or_nop/nop_or_goto instructions controlled by the key are jitted to
jump/nop, correspondingly.

To implement this for a particular architecture, re-define the weak
bpf_arch_poke_static_branch() function in the corresponding bpf_jit_comp.c

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 include/linux/bpf.h            |  16 +++++
 include/uapi/linux/bpf.h       |  27 +++++++
 kernel/bpf/bpf_insn_set.c      | 124 +++++++++++++++++++++++++++++++--
 kernel/bpf/core.c              |   5 ++
 kernel/bpf/syscall.c           |  27 +++++++
 tools/include/uapi/linux/bpf.h |  27 +++++++
 6 files changed, 220 insertions(+), 6 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 0b5f4d4745ee..42ddd2b61866 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -3561,8 +3561,24 @@ 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 {
+	void *jitted_ip;
+	u32 jitted_off;
+	u32 jitted_len;
+	int jitted_jump_offset;
+
 	u32 orig_xlated_off;
 	u32 xlated_off;
+	bool inverse_ja_or_nop;
 };
 
+void bpf_prog_update_insn_ptr(struct bpf_prog *prog,
+			      u32 xlated_off,
+			      u32 jitted_off,
+			      u32 jitted_len,
+			      int jitted_jump_offset,
+			      void *jitted_ip);
+
+int bpf_static_key_set(struct bpf_map *map, bool on);
+int bpf_arch_poke_static_branch(struct bpf_insn_ptr *ptr, bool on);
+
 #endif /* _LINUX_BPF_H */
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 57e0fd636a27..7c4954f93d44 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -906,6 +906,19 @@ union bpf_iter_link_info {
  *		A new file descriptor (a nonnegative integer), or -1 if an
  *		error occurred (in which case, *errno* is set appropriately).
  *
+ * BPF_STATIC_KEY_UPDATE
+ *	Description
+ *		Turn a static key on/off: update jitted code for the specified
+ *		jump instructions controlled by the *map_fd* static key.
+ *		Depending on the type of instruction (goto_or_nop/nop_or_goto)
+ *		and the *on* parameter the binary code of each instruction is
+ *		set to either jump or nop.
+ *
+ *	Return
+ *		Returns zero on success. On error, -1 is returned and *errno*
+ *		is set appropriately.
+ *
+ *
  * NOTES
  *	eBPF objects (maps and programs) can be shared between processes.
  *
@@ -961,6 +974,7 @@ enum bpf_cmd {
 	BPF_LINK_DETACH,
 	BPF_PROG_BIND_MAP,
 	BPF_TOKEN_CREATE,
+	BPF_STATIC_KEY_UPDATE,
 	__MAX_BPF_CMD,
 };
 
@@ -1853,6 +1867,11 @@ union bpf_attr {
 		__u32		bpffs_fd;
 	} token_create;
 
+	struct { /* struct used by BPF_STATIC_KEY_UPDATE command */
+		__u32		map_fd;
+		__u32		on;
+	} static_key;
+
 } __attribute__((aligned(8)));
 
 /* The description below is an attempt at providing documentation to eBPF
@@ -7551,4 +7570,12 @@ enum bpf_kfunc_flags {
 	BPF_F_PAD_ZEROS = (1ULL << 0),
 };
 
+/*
+ * Flags to control creation of BPF Instruction Sets
+ *     - BPF_F_STATIC_KEY: Map will be used as a Static Key.
+ */
+enum bpf_insn_set_flags {
+	BPF_F_STATIC_KEY = (1ULL << 0),
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
diff --git a/kernel/bpf/bpf_insn_set.c b/kernel/bpf/bpf_insn_set.c
index e788dd7109b1..40df7bfcd0be 100644
--- a/kernel/bpf/bpf_insn_set.c
+++ b/kernel/bpf/bpf_insn_set.c
@@ -33,7 +33,8 @@ 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)
+	    attr->map_flags != 0 ||
+	    attr->map_extra & ~BPF_F_STATIC_KEY)
 		return -EINVAL;
 
 	if (attr->max_entries > MAX_ISET_ENTRIES)
@@ -176,6 +177,30 @@ static inline bool is_frozen(struct bpf_map *map)
 	return ret;
 }
 
+static bool is_static_key(const struct bpf_map *map)
+{
+	if (map->map_type != BPF_MAP_TYPE_INSN_SET)
+		return false;
+
+	if (!(map->map_extra & BPF_F_STATIC_KEY))
+		return false;
+
+	return true;
+}
+
+static bool is_ja_or_nop(const struct bpf_insn *insn)
+{
+	u8 code = insn->code;
+
+	return (code == (BPF_JMP | BPF_JA) || code == (BPF_JMP32 | BPF_JA)) &&
+		(insn->src_reg & BPF_STATIC_BRANCH_JA);
+}
+
+static bool is_inverse_ja_or_nop(const struct bpf_insn *insn)
+{
+	return insn->src_reg & BPF_STATIC_BRANCH_NOP;
+}
+
 static inline bool valid_offsets(const struct bpf_insn_set *insn_set,
 				 const struct bpf_prog *prog)
 {
@@ -188,16 +213,17 @@ static inline bool valid_offsets(const struct bpf_insn_set *insn_set,
 		if (off >= prog->len)
 			return false;
 
-		if (off > 0) {
-			if (prog->insnsi[off-1].code == (BPF_LD | BPF_DW | BPF_IMM))
-				return false;
-		}
+		if (off > 0 && 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;
 		}
+
+		if (is_static_key(&insn_set->map) && !is_ja_or_nop(&prog->insnsi[off]))
+			return false;
 	}
 
 	return true;
@@ -206,6 +232,7 @@ static inline bool valid_offsets(const struct bpf_insn_set *insn_set,
 int bpf_insn_set_init(struct bpf_map *map, const struct bpf_prog *prog)
 {
 	struct bpf_insn_set *insn_set = cast_insn_set(map);
+	const struct bpf_insn *insn;
 	int i;
 
 	if (!is_frozen(map))
@@ -228,11 +255,16 @@ int bpf_insn_set_init(struct bpf_map *map, const struct bpf_prog *prog)
 	/*
 	 * Reset all the map indexes to the original values.  This is needed,
 	 * e.g., when a replay of verification with different log level should
-	 * be performed.
+	 * be performed
 	 */
 	for (i = 0; i < map->max_entries; i++)
 		insn_set->ptrs[i].xlated_off = insn_set->ptrs[i].orig_xlated_off;
 
+	for (i = 0; i < map->max_entries; i++) {
+		insn = &prog->insnsi[insn_set->ptrs[i].xlated_off];
+		insn_set->ptrs[i].inverse_ja_or_nop = is_inverse_ja_or_nop(insn);
+	}
+
 	return 0;
 }
 
@@ -286,3 +318,83 @@ void bpf_insn_set_adjust_after_remove(struct bpf_map *map, u32 off, u32 len)
 			insn_set->ptrs[i].xlated_off -= len;
 	}
 }
+
+static struct bpf_insn_ptr *insn_ptr_by_offset(struct bpf_prog *prog, u32 xlated_off)
+{
+	struct bpf_insn_set *insn_set;
+	struct bpf_map *map;
+	int i, j;
+
+	for (i = 0; i < prog->aux->used_map_cnt; i++) {
+		map = prog->aux->used_maps[i];
+		if (!is_static_key(map))
+			continue;
+
+		insn_set = cast_insn_set(map);
+		for (j = 0; j < map->max_entries; j++) {
+			if (insn_set->ptrs[j].xlated_off == xlated_off)
+				return &insn_set->ptrs[j];
+		}
+	}
+
+	return NULL;
+}
+
+void bpf_prog_update_insn_ptr(struct bpf_prog *prog,
+			      u32 xlated_off,
+			      u32 jitted_off,
+			      u32 jitted_len,
+			      int jitted_jump_offset,
+			      void *jitted_ip)
+{
+	struct bpf_insn_ptr *ptr;
+
+	ptr = insn_ptr_by_offset(prog, xlated_off);
+	if (ptr) {
+		ptr->jitted_ip = jitted_ip;
+		ptr->jitted_off = jitted_off;
+		ptr->jitted_len = jitted_len;
+		ptr->jitted_jump_offset = jitted_jump_offset;
+	}
+}
+
+static int check_state(struct bpf_insn_set *insn_set)
+{
+	int ret = 0;
+
+	mutex_lock(&insn_set->state_mutex);
+	if (insn_set->state == INSN_SET_STATE_FREE)
+		ret = -EINVAL;
+	if (insn_set->state == INSN_SET_STATE_INIT)
+		ret = -EBUSY;
+	mutex_unlock(&insn_set->state_mutex);
+
+	return ret;
+}
+
+int bpf_static_key_set(struct bpf_map *map, bool on)
+{
+	struct bpf_insn_set *insn_set = cast_insn_set(map);
+	struct bpf_insn_ptr *ptr;
+	int ret = 0;
+	int i;
+
+	if (!is_static_key(map))
+		return -EINVAL;
+
+	ret = check_state(insn_set);
+	if (ret)
+		return ret;
+
+	for (i = 0; i < map->max_entries && ret == 0; i++) {
+		ptr = &insn_set->ptrs[i];
+		if (ptr->xlated_off == INSN_DELETED)
+			continue;
+
+		ret = bpf_arch_poke_static_branch(ptr, on ^ ptr->inverse_ja_or_nop);
+		if (ret)
+			return ret;
+	}
+
+	return ret;
+}
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 62cb9557ad3b..5c3afbae8ab0 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -3173,6 +3173,11 @@ static int __init bpf_global_ma_init(void)
 late_initcall(bpf_global_ma_init);
 #endif
 
+int __weak bpf_arch_poke_static_branch(struct bpf_insn_ptr *ptr, bool on)
+{
+	return -EOPNOTSUPP;
+}
+
 DEFINE_STATIC_KEY_FALSE(bpf_stats_enabled_key);
 EXPORT_SYMBOL(bpf_stats_enabled_key);
 
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index c417bf5eed74..af9d46aea93a 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1346,6 +1346,7 @@ static int map_create(union bpf_attr *attr, bool kernel)
 
 	if (attr->map_type != BPF_MAP_TYPE_BLOOM_FILTER &&
 	    attr->map_type != BPF_MAP_TYPE_ARENA &&
+	    attr->map_type != BPF_MAP_TYPE_INSN_SET &&
 	    attr->map_extra != 0)
 		return -EINVAL;
 
@@ -1691,6 +1692,29 @@ static int map_lookup_elem(union bpf_attr *attr)
 	return err;
 }
 
+#define BPF_STATIC_KEY_UPDATE_LAST_FIELD static_key.on
+
+static int bpf_static_key_update(const union bpf_attr *attr)
+{
+	bool on = attr->static_key.on & 1;
+	struct bpf_map *map;
+	int ret;
+
+	if (CHECK_ATTR(BPF_STATIC_KEY_UPDATE))
+		return -EINVAL;
+
+	if (attr->static_key.on & ~1)
+		return -EINVAL;
+
+	map = bpf_map_get(attr->static_key.map_fd);
+	if (IS_ERR(map))
+		return PTR_ERR(map);
+
+	ret = bpf_static_key_set(map, on);
+
+	bpf_map_put(map);
+	return ret;
+}
 
 #define BPF_MAP_UPDATE_ELEM_LAST_FIELD flags
 
@@ -5908,6 +5932,9 @@ static int __sys_bpf(enum bpf_cmd cmd, bpfptr_t uattr, unsigned int size)
 	case BPF_TOKEN_CREATE:
 		err = token_create(&attr);
 		break;
+	case BPF_STATIC_KEY_UPDATE:
+		err = bpf_static_key_update(&attr);
+		break;
 	default:
 		err = -EINVAL;
 		break;
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 57e0fd636a27..7c4954f93d44 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -906,6 +906,19 @@ union bpf_iter_link_info {
  *		A new file descriptor (a nonnegative integer), or -1 if an
  *		error occurred (in which case, *errno* is set appropriately).
  *
+ * BPF_STATIC_KEY_UPDATE
+ *	Description
+ *		Turn a static key on/off: update jitted code for the specified
+ *		jump instructions controlled by the *map_fd* static key.
+ *		Depending on the type of instruction (goto_or_nop/nop_or_goto)
+ *		and the *on* parameter the binary code of each instruction is
+ *		set to either jump or nop.
+ *
+ *	Return
+ *		Returns zero on success. On error, -1 is returned and *errno*
+ *		is set appropriately.
+ *
+ *
  * NOTES
  *	eBPF objects (maps and programs) can be shared between processes.
  *
@@ -961,6 +974,7 @@ enum bpf_cmd {
 	BPF_LINK_DETACH,
 	BPF_PROG_BIND_MAP,
 	BPF_TOKEN_CREATE,
+	BPF_STATIC_KEY_UPDATE,
 	__MAX_BPF_CMD,
 };
 
@@ -1853,6 +1867,11 @@ union bpf_attr {
 		__u32		bpffs_fd;
 	} token_create;
 
+	struct { /* struct used by BPF_STATIC_KEY_UPDATE command */
+		__u32		map_fd;
+		__u32		on;
+	} static_key;
+
 } __attribute__((aligned(8)));
 
 /* The description below is an attempt at providing documentation to eBPF
@@ -7551,4 +7570,12 @@ enum bpf_kfunc_flags {
 	BPF_F_PAD_ZEROS = (1ULL << 0),
 };
 
+/*
+ * Flags to control creation of BPF Instruction Sets
+ *     - BPF_F_STATIC_KEY: Map will be used as a Static Key.
+ */
+enum bpf_insn_set_flags {
+	BPF_F_STATIC_KEY = (1ULL << 0),
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
-- 
2.34.1

[RFC PATCH bpf-next 07/14] bpf: save the start of functions in bpf_prog_aux

[Anton Protopopov]

Introduce a new subprog_start field in bpf_prog_aux. This field may
be used by JIT compilers wanting to know the real absolute xlated
offset of the function being jitted. The func_info[func_id] may have
served this purpose, but func_info may be NULL, so JIT compilers
can't rely on it.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 include/linux/bpf.h   | 1 +
 kernel/bpf/verifier.c | 1 +
 2 files changed, 2 insertions(+)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 42ddd2b61866..fb0910083b79 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1524,6 +1524,7 @@ struct bpf_prog_aux {
 	u32 ctx_arg_info_size;
 	u32 max_rdonly_access;
 	u32 max_rdwr_access;
+	u32 subprog_start;
 	struct btf *attach_btf;
 	struct bpf_ctx_arg_aux *ctx_arg_info;
 	void __percpu *priv_stack_ptr;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0860ef57d5af..7f66002071ed 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20999,6 +20999,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		func[i]->aux->func_idx = i;
 		/* Below members will be freed only at prog->aux */
 		func[i]->aux->btf = prog->aux->btf;
+		func[i]->aux->subprog_start = subprog_start;
 		func[i]->aux->func_info = prog->aux->func_info;
 		func[i]->aux->func_info_cnt = prog->aux->func_info_cnt;
 		func[i]->aux->poke_tab = prog->aux->poke_tab;
-- 
2.34.1

[RFC PATCH bpf-next 08/14] bpf, x86: implement static key support

[Anton Protopopov]

Implement bpf_arch_poke_static_branch() for x86. Namely, during each
JIT loop, save IP values and sizes of jump instructions pointed by
static keys. Then use the text_poke_bp() to toggle jumps/nops.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 arch/x86/net/bpf_jit_comp.c | 46 +++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 5856ac1aab80..31cadded820b 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -1569,6 +1569,8 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 		const s32 imm32 = insn->imm;
 		u32 dst_reg = insn->dst_reg;
 		u32 src_reg = insn->src_reg;
+		int adjust_off = 0;
+		int abs_xlated_off;
 		u8 b2 = 0, b3 = 0;
 		u8 *start_of_ldx;
 		s64 jmp_offset;
@@ -1724,6 +1726,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 			emit_mov_imm64(&prog, dst_reg, insn[1].imm, insn[0].imm);
 			insn++;
 			i++;
+			adjust_off = 1;
 			break;
 
 			/* dst %= src, dst /= src, dst %= imm32, dst /= imm32 */
@@ -2595,6 +2598,14 @@ st:			if (is_imm8(insn->off))
 				return -EFAULT;
 			}
 			memcpy(rw_image + proglen, temp, ilen);
+
+			/*
+			 * Static keys need to know how the xlated code
+			 * of static ja instructions maps to jited code
+			 */
+			abs_xlated_off = bpf_prog->aux->subprog_start + i - 1 - adjust_off;
+			bpf_prog_update_insn_ptr(bpf_prog, abs_xlated_off, proglen, ilen,
+						 jmp_offset, image + proglen);
 		}
 		proglen += ilen;
 		addrs[i] = proglen;
@@ -3880,3 +3891,38 @@ bool bpf_jit_supports_timed_may_goto(void)
 {
 	return true;
 }
+
+int bpf_arch_poke_static_branch(struct bpf_insn_ptr *ptr, bool on)
+{
+	int jmp_offset = ptr->jitted_jump_offset;
+	void *ip = ptr->jitted_ip;
+	u32 len = ptr->jitted_len;
+	u8 op[5];
+
+	if (WARN_ON_ONCE(!ip))
+		return -EINVAL;
+
+	if (WARN_ON_ONCE(is_imm8(jmp_offset) && len != 2))
+		return -EINVAL;
+
+	if (WARN_ON_ONCE(!is_imm8(jmp_offset) && len != 5))
+		return -EINVAL;
+
+	if (on) {
+		if (len == 2) {
+			op[0] = 0xEB;
+			op[1] = jmp_offset;
+		} else {
+			op[0] = 0xE9;
+			memcpy(&op[1], &jmp_offset, 4);
+		}
+	} else {
+		memcpy(op, x86_nops[len], len);
+	}
+
+	mutex_lock(&text_mutex);
+	text_poke_bp(ip, op, len, NULL);
+	mutex_unlock(&text_mutex);
+
+	return 0;
+}
-- 
2.34.1

[RFC PATCH bpf-next 09/14] selftests/bpf: add guard macros around likely/unlikely

[Anton Protopopov]

Add guard macros around likely/unlikely definitions such that, if defined
previously, the compilation doesn't break. (Those macros, actually,
will be defined in libbpf in a consequent commit.)

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 tools/testing/selftests/bpf/bpf_arena_spin_lock.h | 5 +++++
 tools/testing/selftests/bpf/progs/iters.c         | 2 ++
 2 files changed, 7 insertions(+)

diff --git a/tools/testing/selftests/bpf/bpf_arena_spin_lock.h b/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
index fb8dc0768999..d60d899dd9da 100644
--- a/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
+++ b/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
@@ -95,8 +95,13 @@ struct arena_qnode {
 #define _Q_LOCKED_VAL		(1U << _Q_LOCKED_OFFSET)
 #define _Q_PENDING_VAL		(1U << _Q_PENDING_OFFSET)
 
+#ifndef likely
 #define likely(x) __builtin_expect(!!(x), 1)
+#endif
+
+#ifndef unlikely
 #define unlikely(x) __builtin_expect(!!(x), 0)
+#endif
 
 struct arena_qnode __arena qnodes[_Q_MAX_CPUS][_Q_MAX_NODES];
 
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 427b72954b87..1b9a908f2607 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -7,7 +7,9 @@
 #include "bpf_misc.h"
 #include "bpf_compiler.h"
 
+#ifndef unlikely
 #define unlikely(x)	__builtin_expect(!!(x), 0)
+#endif
 
 static volatile int zero = 0;
 
-- 
2.34.1

[RFC PATCH bpf-next 10/14] libbpf: add likely/unlikely macros

[Anton Protopopov]

A few selftests and, more importantly, a consequent changes to the
bpf_helpers.h file use likely/unlikely macros. So define them here.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 tools/lib/bpf/bpf_helpers.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
index 686824b8b413..a50773d4616e 100644
--- a/tools/lib/bpf/bpf_helpers.h
+++ b/tools/lib/bpf/bpf_helpers.h
@@ -15,6 +15,14 @@
 #define __array(name, val) typeof(val) *name[]
 #define __ulong(name, val) enum { ___bpf_concat(__unique_value, __COUNTER__) = val } name
 
+#ifndef likely
+#define likely(x)      (__builtin_expect(!!(x), 1))
+#endif
+
+#ifndef unlikely
+#define unlikely(x)    (__builtin_expect(!!(x), 0))
+#endif
+
 /*
  * Helper macro to place programs, maps, license in
  * different sections in elf_bpf file. Section names
-- 
2.34.1

Re: [RFC PATCH bpf-next 10/14] libbpf: add likely/unlikely macros

[Andrii Nakryiko]

On Tue, Mar 18, 2025 at 7:30 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> A few selftests and, more importantly, a consequent changes to the
> bpf_helpers.h file use likely/unlikely macros. So define them here.
>
> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> ---
>  tools/lib/bpf/bpf_helpers.h | 8 ++++++++
>  1 file changed, 8 insertions(+)
>
> diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
> index 686824b8b413..a50773d4616e 100644
> --- a/tools/lib/bpf/bpf_helpers.h
> +++ b/tools/lib/bpf/bpf_helpers.h
> @@ -15,6 +15,14 @@
>  #define __array(name, val) typeof(val) *name[]
>  #define __ulong(name, val) enum { ___bpf_concat(__unique_value, __COUNTER__) = val } name
>
> +#ifndef likely
> +#define likely(x)      (__builtin_expect(!!(x), 1))
> +#endif
> +
> +#ifndef unlikely
> +#define unlikely(x)    (__builtin_expect(!!(x), 0))
> +#endif
> +

this seems useful, maybe send this as a separate patch? I'd roll your
BPF selftests manipulation into the same patch to avoid unnecessary
code churn

>  /*
>   * Helper macro to place programs, maps, license in
>   * different sections in elf_bpf file. Section names
> --
> 2.34.1
>

Re: [RFC PATCH bpf-next 10/14] libbpf: add likely/unlikely macros

[Anton Protopopov]

On 25/03/28 01:57PM, Andrii Nakryiko wrote:
> On Tue, Mar 18, 2025 at 7:30 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > A few selftests and, more importantly, a consequent changes to the
> > bpf_helpers.h file use likely/unlikely macros. So define them here.
> >
> > Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> > ---
> >  tools/lib/bpf/bpf_helpers.h | 8 ++++++++
> >  1 file changed, 8 insertions(+)
> >
> > diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
> > index 686824b8b413..a50773d4616e 100644
> > --- a/tools/lib/bpf/bpf_helpers.h
> > +++ b/tools/lib/bpf/bpf_helpers.h
> > @@ -15,6 +15,14 @@
> >  #define __array(name, val) typeof(val) *name[]
> >  #define __ulong(name, val) enum { ___bpf_concat(__unique_value, __COUNTER__) = val } name
> >
> > +#ifndef likely
> > +#define likely(x)      (__builtin_expect(!!(x), 1))
> > +#endif
> > +
> > +#ifndef unlikely
> > +#define unlikely(x)    (__builtin_expect(!!(x), 0))
> > +#endif
> > +
> 
> this seems useful, maybe send this as a separate patch? I'd roll your
> BPF selftests manipulation into the same patch to avoid unnecessary
> code churn

Yes, let me send it separately (+ a comment fix from the patch 01). 

The reason I've done this in three patches is 1) every separate patch
should build 2) I thought that libbpf patches should be separate from
selftest changes? (= how libbpf changes are pulled to github version of
libvirt?)

> >  /*
> >   * Helper macro to place programs, maps, license in
> >   * different sections in elf_bpf file. Section names
> > --
> > 2.34.1
> >

Re: [RFC PATCH bpf-next 10/14] libbpf: add likely/unlikely macros

[Andrii Nakryiko]

On Sat, Mar 29, 2025 at 6:33 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On 25/03/28 01:57PM, Andrii Nakryiko wrote:
> > On Tue, Mar 18, 2025 at 7:30 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > A few selftests and, more importantly, a consequent changes to the
> > > bpf_helpers.h file use likely/unlikely macros. So define them here.
> > >
> > > Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> > > ---
> > >  tools/lib/bpf/bpf_helpers.h | 8 ++++++++
> > >  1 file changed, 8 insertions(+)
> > >
> > > diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
> > > index 686824b8b413..a50773d4616e 100644
> > > --- a/tools/lib/bpf/bpf_helpers.h
> > > +++ b/tools/lib/bpf/bpf_helpers.h
> > > @@ -15,6 +15,14 @@
> > >  #define __array(name, val) typeof(val) *name[]
> > >  #define __ulong(name, val) enum { ___bpf_concat(__unique_value, __COUNTER__) = val } name
> > >
> > > +#ifndef likely
> > > +#define likely(x)      (__builtin_expect(!!(x), 1))
> > > +#endif
> > > +
> > > +#ifndef unlikely
> > > +#define unlikely(x)    (__builtin_expect(!!(x), 0))
> > > +#endif
> > > +
> >
> > this seems useful, maybe send this as a separate patch? I'd roll your
> > BPF selftests manipulation into the same patch to avoid unnecessary
> > code churn
>
> Yes, let me send it separately (+ a comment fix from the patch 01).
>
> The reason I've done this in three patches is 1) every separate patch
> should build 2) I thought that libbpf patches should be separate from
> selftest changes? (= how libbpf changes are pulled to github version of
> libvirt?)
>

We do try to keep them separate, but if changes in libbpf need
adjustment in selftests, it's fine to do it in one patch. This has no
bad effects for Github sync, the sync script is smart enough to deal
with that.


> > >  /*
> > >   * Helper macro to place programs, maps, license in
> > >   * different sections in elf_bpf file. Section names
> > > --
> > > 2.34.1
> > >

[RFC PATCH bpf-next 11/14] selftests/bpf: remove likely/unlikely definitions

[Anton Protopopov]

Now likely/unlikely macros are defined in tools/lib/bpf/bpf_helpers.h
and thus can be removed from selftests.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 tools/testing/selftests/bpf/bpf_arena_spin_lock.h | 8 --------
 tools/testing/selftests/bpf/progs/iters.c         | 4 ----
 2 files changed, 12 deletions(-)

diff --git a/tools/testing/selftests/bpf/bpf_arena_spin_lock.h b/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
index d60d899dd9da..4e29c31c4ef8 100644
--- a/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
+++ b/tools/testing/selftests/bpf/bpf_arena_spin_lock.h
@@ -95,14 +95,6 @@ struct arena_qnode {
 #define _Q_LOCKED_VAL		(1U << _Q_LOCKED_OFFSET)
 #define _Q_PENDING_VAL		(1U << _Q_PENDING_OFFSET)
 
-#ifndef likely
-#define likely(x) __builtin_expect(!!(x), 1)
-#endif
-
-#ifndef unlikely
-#define unlikely(x) __builtin_expect(!!(x), 0)
-#endif
-
 struct arena_qnode __arena qnodes[_Q_MAX_CPUS][_Q_MAX_NODES];
 
 static inline u32 encode_tail(int cpu, int idx)
diff --git a/tools/testing/selftests/bpf/progs/iters.c b/tools/testing/selftests/bpf/progs/iters.c
index 1b9a908f2607..76adf4a8f2da 100644
--- a/tools/testing/selftests/bpf/progs/iters.c
+++ b/tools/testing/selftests/bpf/progs/iters.c
@@ -7,10 +7,6 @@
 #include "bpf_misc.h"
 #include "bpf_compiler.h"
 
-#ifndef unlikely
-#define unlikely(x)	__builtin_expect(!!(x), 0)
-#endif
-
 static volatile int zero = 0;
 
 int my_pid;
-- 
2.34.1

[RFC PATCH bpf-next 12/14] libbpf: BPF Static Keys support

[Anton Protopopov]

Introduce the DEFINE_STATIC_KEY() and bpf_static_branch_{unlikely,likely}
macros to mimic Linux Kernel Static Keys API in BPF.

Example of usage would be as follows:

    DEFINE_STATIC_KEY(key);

    void prog(void)
    {
            if (bpf_static_branch_unlikely(key))
                    /* rarely used code */
            else
                    /* default hot path code */
    }

or, using the likely variant:

    void prog(void)
    {
            if (bpf_static_branch_likely(key))
                    /* default hot path code */
            else
                    /* rarely used code */
    }

The "unlikely" version of macro compiles in the code where the
else-branch (key is off) is fall-through, the "likely" macro
prioritises the if-branch.

Both macros push an entry in the new ".static_keys" section, which
contains the following information:

               32 bits                   32 bits           64 bits
    offset of jump instruction | offset of jump target |    flags

The corresponding ".rel.static_keys" relocations table entry contains
the static key name. This information is enough to construct corresponding
INSN_SET maps.

NOTE. This is an RFC version of the patch. The main design flow of it
is what to do when a static key is used in a noinline function and/or
in two BPF programs. Consider the following example:

    DEFINE_STATIC_KEY(key);

    static __noinline foo()
    {
            if (bpf_static_key_unlikely(&key)) {
                /* do something special */
            }
            ...
    }

    SEC("xdp")
    int prog1(ctx) {
        foo();
        ...
    }

    SEC("xdp")
    int prog2(ctx) {
        foo();
        ...
    }

The problem here is that when such an ELF object is parsed and loaded
by libbpf, then, from the kernel point of view, two programs are
loaded: prog1 + a copy of "foo", then prog2 + a copy of "foo".
However, the static key "key" can only be used in one program (and,
of course, it will point to different instructions in both cases, as
prog1/prog2 have different sizes + there might be more relocations).
The solution is to actually create private copies of the key "key"
per "load object". This automatically allows to reuse the "same"
static key for multiple programs.

From the uAPI perspective, the bpf_static_key_update() system call
only operates on a particular "atomic" object -- a map representing
the static key. However, there should be a way to toggle all the keys
derived from the "key" (this should looks more natural for a user,
as from the C perspective there is only one object).
So, the following changes to the API should be

  * when libbpf opens an object, it replaces "key" with private per-prog
    instances "prog1_key", "prog2_key", etc. Then these static keys can be
    already set individually by the bpf syscall

  * for "wrapper API", either introduce a helper which takes a skeleton and key
    name, or just generate a helper in the generated skeleton (does this introduce
    new API as well?)

Some other bugs included in this patch (as before the libbpf API is
discussed, this might be painful to re-implement this patch +
selftests). One obvious bug is that gen-loader is not supported.
Another one related to fd_array. Namely, in order to pass static
keys on load, they should be placed in fd_array, and fd_array_cnt
must be set. The current code in libbpf creates an fd_array which
is shared between all the programs in the ELF object, which doesn't
work if fd_array_cnt is set to non-zero, as all maps/btfs in
fd_array[0,...,fd_array_cnt-1] are bound to the program. So instead,
loader should create private copy of fd_array per bpf_prog_load.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 tools/lib/bpf/bpf_helpers.h     |  55 +++++
 tools/lib/bpf/libbpf.c          | 362 +++++++++++++++++++++++++++++++-
 tools/lib/bpf/libbpf_internal.h |   3 +
 tools/lib/bpf/linker.c          |   6 +-
 4 files changed, 423 insertions(+), 3 deletions(-)

diff --git a/tools/lib/bpf/bpf_helpers.h b/tools/lib/bpf/bpf_helpers.h
index a50773d4616e..c66f579d3ddf 100644
--- a/tools/lib/bpf/bpf_helpers.h
+++ b/tools/lib/bpf/bpf_helpers.h
@@ -429,4 +429,59 @@ extern void bpf_iter_num_destroy(struct bpf_iter_num *it) __weak __ksym;
 )
 #endif /* bpf_repeat */
 
+#define DEFINE_STATIC_KEY(NAME)									\
+	struct {										\
+		__uint(type, BPF_MAP_TYPE_INSN_SET);						\
+		__type(key, __u32);								\
+		__type(value, __u32);								\
+		__uint(map_extra, BPF_F_STATIC_KEY);						\
+	} NAME SEC(".maps")
+
+static __always_inline int __bpf_static_branch_nop(void *static_key)
+{
+	asm goto("1:\n\t"
+		"gotol_or_nop %l[l_yes]\n\t"
+		".pushsection .static_keys, \"aw\"\n\t"
+		".balign 8\n\t"
+		".long 1b - .\n\t"
+		".long %l[l_yes] - .\n\t"
+		".quad %c0 - .\n\t"
+		".popsection\n\t"
+		:: "i" (static_key)
+		:: l_yes);
+	return 0;
+l_yes:
+	return 1;
+}
+
+static __always_inline int __bpf_static_branch_jump(void *static_key)
+{
+	asm goto("1:\n\t"
+		"nop_or_gotol %l[l_yes]\n\t"
+		".pushsection .static_keys, \"aw\"\n\t"
+		".balign 8\n\t"
+		".long 1b - .\n\t"
+		".long %l[l_yes] - .\n\t"
+		".quad %c0 - . + 1\n\t"
+		".popsection\n\t"
+		:: "i" (static_key)
+		:: l_yes);
+	return 0;
+l_yes:
+	return 1;
+}
+
+/*
+ * The bpf_static_branch_{unlikely,likely} macros provide a way to utilize BPF
+ * Static Keys in BPF programs in exactly the same manner this is done in the
+ * Linux Kernel.  The "unlikely" macro compiles in the code where the else-branch
+ * (key is off) is prioritized, the "likely" macro prioritises the if-branch.
+ */
+
+#define bpf_static_branch_unlikely(static_key) \
+	unlikely(__bpf_static_branch_nop(static_key))
+
+#define bpf_static_branch_likely(static_key) \
+	likely(!__bpf_static_branch_jump(static_key))
+
 #endif
diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index 6b85060f07b3..fdf00bc32366 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -422,6 +422,17 @@ struct bpf_sec_def {
 	libbpf_prog_attach_fn_t prog_attach_fn;
 };
 
+struct static_key_insn {
+	__u32 insn_offset;
+	__u32 jump_target;
+};
+
+struct static_key {
+	struct bpf_map *map;
+	struct static_key_insn *insns;
+	__u32 insns_cnt;
+};
+
 /*
  * bpf_prog should be a better name but it has been used in
  * linux/filter.h.
@@ -494,6 +505,9 @@ struct bpf_program {
 	__u32 line_info_rec_size;
 	__u32 line_info_cnt;
 	__u32 prog_flags;
+
+	struct static_key *static_keys;
+	__u32 static_keys_cnt;
 };
 
 struct bpf_struct_ops {
@@ -523,6 +537,7 @@ struct bpf_struct_ops {
 #define STRUCT_OPS_SEC ".struct_ops"
 #define STRUCT_OPS_LINK_SEC ".struct_ops.link"
 #define ARENA_SEC ".addr_space.1"
+#define STATIC_KEYS_SEC ".static_keys"
 
 enum libbpf_map_type {
 	LIBBPF_MAP_UNSPEC,
@@ -656,6 +671,7 @@ struct elf_state {
 	Elf64_Ehdr *ehdr;
 	Elf_Data *symbols;
 	Elf_Data *arena_data;
+	Elf_Data *static_keys_data;
 	size_t shstrndx; /* section index for section name strings */
 	size_t strtabidx;
 	struct elf_sec_desc *secs;
@@ -666,6 +682,7 @@ struct elf_state {
 	int symbols_shndx;
 	bool has_st_ops;
 	int arena_data_shndx;
+	int static_keys_data_shndx;
 };
 
 struct usdt_manager;
@@ -763,6 +780,7 @@ void bpf_program__unload(struct bpf_program *prog)
 
 	zfree(&prog->func_info);
 	zfree(&prog->line_info);
+	zfree(&prog->static_keys);
 }
 
 static void bpf_program__exit(struct bpf_program *prog)
@@ -1895,6 +1913,213 @@ static char *internal_map_name(struct bpf_object *obj, const char *real_name)
 	return strdup(map_name);
 }
 
+struct static_keys_table_entry {
+	__u32 insn_offset;
+	__u32 jump_target;
+	union {
+		__u64 map_ptr;	/* map_ptr is always zero, as it is relocated */
+		__u64 flags;	/* so we can reuse it to store flags */
+	};
+};
+
+static struct bpf_program *shndx_to_prog(struct bpf_object *obj,
+					 size_t sec_idx,
+					 struct static_keys_table_entry *entry)
+{
+	__u32 insn_offset = entry->insn_offset / 8;
+	__u32 jump_target = entry->jump_target / 8;
+	struct bpf_program *prog;
+	size_t i;
+
+	for (i = 0; i < obj->nr_programs; i++) {
+		prog = &obj->programs[i];
+		if (prog->sec_idx != sec_idx)
+			continue;
+
+		if (insn_offset < prog->sec_insn_off ||
+		    insn_offset >= prog->sec_insn_off + prog->sec_insn_cnt)
+			continue;
+
+		if (jump_target < prog->sec_insn_off ||
+		    jump_target >= prog->sec_insn_off + prog->sec_insn_cnt) {
+			pr_warn("static key: offset %u is in boundaries, target %u is not\n",
+				insn_offset, jump_target);
+			return NULL;
+		}
+
+		return prog;
+	}
+
+	return NULL;
+}
+
+static struct bpf_program *find_prog_for_jump_entry(struct bpf_object *obj,
+						    int nrels,
+						    Elf_Data *relo_data,
+						    __u32 entry_offset,
+						    struct static_keys_table_entry *entry)
+{
+	struct bpf_program *prog;
+	Elf64_Rel *rel;
+	Elf64_Sym *sym;
+	int i;
+
+	for (i = 0; i < nrels; i++) {
+		rel = elf_rel_by_idx(relo_data, i);
+		if (!rel) {
+			pr_warn("static key: relo #%d: failed to get ELF relo\n", i);
+			return ERR_PTR(-LIBBPF_ERRNO__FORMAT);
+		}
+
+		if ((__u32)rel->r_offset != entry_offset)
+			continue;
+
+		sym = elf_sym_by_idx(obj, ELF64_R_SYM(rel->r_info));
+		if (!sym) {
+			pr_warn("static key: .maps relo #%d: symbol %zx not found\n",
+				i, (size_t)ELF64_R_SYM(rel->r_info));
+			return ERR_PTR(-LIBBPF_ERRNO__FORMAT);
+		}
+
+		prog = shndx_to_prog(obj, sym->st_shndx, entry);
+		if (!prog) {
+			pr_warn("static key: .maps relo #%d: program %zx not found\n",
+				i, (size_t)sym->st_shndx);
+			return ERR_PTR(-LIBBPF_ERRNO__FORMAT);
+		}
+		return prog;
+	}
+	return ERR_PTR(-LIBBPF_ERRNO__FORMAT);
+}
+
+static struct bpf_map *find_map_for_jump_entry(struct bpf_object *obj,
+					       int nrels,
+					       Elf_Data *relo_data,
+					       __u32 entry_offset)
+{
+	struct bpf_map *map;
+	const char *name;
+	Elf64_Rel *rel;
+	Elf64_Sym *sym;
+	int i;
+
+	for (i = 0; i < nrels; i++) {
+		rel = elf_rel_by_idx(relo_data, i);
+		if (!rel) {
+			pr_warn("static key: relo #%d: failed to get ELF relo\n", i);
+			return NULL;
+		}
+
+		if ((__u32)rel->r_offset != entry_offset)
+			continue;
+
+		sym = elf_sym_by_idx(obj, ELF64_R_SYM(rel->r_info));
+		if (!sym) {
+			pr_warn(".maps relo #%d: symbol %zx not found\n",
+				i, (size_t)ELF64_R_SYM(rel->r_info));
+			return NULL;
+		}
+
+		name = elf_sym_str(obj, sym->st_name) ?: "<?>";
+		if (!name || !strcmp(name, "")) {
+			pr_warn(".maps relo #%d: symbol name is zero or empty\n", i);
+			return NULL;
+		}
+
+		map = bpf_object__find_map_by_name(obj, name);
+		if (!map)
+			return NULL;
+		return map;
+	}
+	return NULL;
+}
+
+static struct static_key *find_static_key(struct bpf_program *prog, struct bpf_map *map)
+{
+	__u32 i;
+
+	for (i = 0; i < prog->static_keys_cnt; i++)
+		if (prog->static_keys[i].map == map)
+			return &prog->static_keys[i];
+
+	return NULL;
+}
+
+static int add_static_key_insn(struct bpf_program *prog,
+			       struct static_keys_table_entry *entry,
+			       struct bpf_map *map)
+{
+	struct static_key_insn *insn;
+	struct static_key *key;
+	void *x;
+
+	key = find_static_key(prog, map);
+	if (!key) {
+		__u32 size_old = prog->static_keys_cnt * sizeof(*key);
+
+		x = realloc(prog->static_keys, size_old + sizeof(*key));
+		if (!x)
+			return -ENOMEM;
+
+		prog->static_keys = x;
+		prog->static_keys_cnt += 1;
+
+		key = x + size_old;
+		key->map = map;
+		key->insns = NULL;
+		key->insns_cnt = 0;
+	}
+
+	x = realloc(key->insns, (key->insns_cnt + 1) * sizeof(key->insns[0]));
+	if (!x)
+		return -ENOMEM;
+
+	key->insns = x;
+	insn = &key->insns[key->insns_cnt++];
+	insn->insn_offset = (entry->insn_offset / 8) - prog->sec_insn_off;
+	insn->jump_target = (entry->jump_target / 8) - prog->sec_insn_off;
+	key->map->def.max_entries += 1;
+
+	return 0;
+}
+
+static int
+bpf_object__collect_static_keys_relos(struct bpf_object *obj,
+				      Elf64_Shdr *shdr,
+				      Elf_Data *relo_data)
+{
+	Elf_Data *data = obj->efile.static_keys_data;
+	int nrels = shdr->sh_size / shdr->sh_entsize;
+	struct static_keys_table_entry *entries;
+	size_t i;
+	int err;
+
+	if (!data)
+		return 0;
+
+	entries = (void *)data->d_buf;
+	for (i = 0; i < data->d_size / sizeof(struct static_keys_table_entry); i++) {
+		__u32 entry_offset = i * sizeof(struct static_keys_table_entry);
+		struct bpf_program *prog;
+		struct bpf_map *map;
+
+		prog = find_prog_for_jump_entry(obj, nrels, relo_data, entry_offset, &entries[i]);
+		if (IS_ERR(prog))
+			return PTR_ERR(prog);
+
+		map = find_map_for_jump_entry(obj, nrels, relo_data,
+				entry_offset + offsetof(struct static_keys_table_entry, map_ptr));
+		if (!map)
+			return -EINVAL;
+
+		err = add_static_key_insn(prog, &entries[i], map);
+		if (err)
+			return err;
+	}
+
+	return 0;
+}
+
 static int
 map_fill_btf_type_info(struct bpf_object *obj, struct bpf_map *map);
 
@@ -3951,6 +4176,9 @@ static int bpf_object__elf_collect(struct bpf_object *obj)
 			} else if (strcmp(name, ARENA_SEC) == 0) {
 				obj->efile.arena_data = data;
 				obj->efile.arena_data_shndx = idx;
+			} else if (strcmp(name, STATIC_KEYS_SEC) == 0) {
+				obj->efile.static_keys_data = data;
+				obj->efile.static_keys_data_shndx = idx;
 			} else {
 				pr_info("elf: skipping unrecognized data section(%d) %s\n",
 					idx, name);
@@ -3968,7 +4196,8 @@ static int bpf_object__elf_collect(struct bpf_object *obj)
 			    strcmp(name, ".rel" STRUCT_OPS_LINK_SEC) &&
 			    strcmp(name, ".rel?" STRUCT_OPS_SEC) &&
 			    strcmp(name, ".rel?" STRUCT_OPS_LINK_SEC) &&
-			    strcmp(name, ".rel" MAPS_ELF_SEC)) {
+			    strcmp(name, ".rel" MAPS_ELF_SEC) &&
+			    strcmp(name, ".rel" STATIC_KEYS_SEC)) {
 				pr_info("elf: skipping relo section(%d) %s for section(%d) %s\n",
 					idx, name, targ_sec_idx,
 					elf_sec_name(obj, elf_sec_by_idx(obj, targ_sec_idx)) ?: "<?>");
@@ -5200,6 +5429,69 @@ bpf_object__populate_internal_map(struct bpf_object *obj, struct bpf_map *map)
 	return 0;
 }
 
+static struct static_key *
+bpf_object__find_static_key(struct bpf_object *obj, struct bpf_map *map)
+{
+	struct static_key *key = NULL;
+	int i;
+
+	for (i = 0; i < obj->nr_programs; i++) {
+		key = find_static_key(&obj->programs[i], map);
+		if (key)
+			return key;
+	}
+
+	return NULL;
+}
+
+static int bpf_object__init_static_key_map(struct bpf_object *obj,
+					   struct bpf_map *map)
+{
+	struct static_key *key;
+	__u32 map_key;
+	int err;
+	int i;
+
+	if (obj->gen_loader) {
+		pr_warn("not supported: obj->gen_loader ^ static keys\n");
+		return libbpf_err(-ENOTSUP);
+	}
+
+	key = bpf_object__find_static_key(obj, map);
+	if (!key) {
+		pr_warn("map '%s': static key is not used by any program\n",
+			bpf_map__name(map));
+		return libbpf_err(-EINVAL);
+	}
+
+	if (key->insns_cnt != map->def.max_entries) {
+		pr_warn("map '%s': static key #entries and max_entries differ: %d != %d\n",
+			bpf_map__name(map), key->insns_cnt, map->def.max_entries);
+		return libbpf_err(-EINVAL);
+	}
+
+	for (i = 0; i < key->insns_cnt; i++) {
+		map_key = key->insns[i].insn_offset;
+		err = bpf_map_update_elem(map->fd, &i, &map_key, 0);
+		if (err) {
+			err = -errno;
+			pr_warn("map '%s': failed to set initial contents: %s\n",
+				bpf_map__name(map), errstr(err));
+			return err;
+		}
+	}
+
+	err = bpf_map_freeze(map->fd);
+	if (err) {
+		err = -errno;
+		pr_warn("map '%s': failed to freeze as read-only: %s\n",
+			bpf_map__name(map), errstr(err));
+		return err;
+	}
+
+	return 0;
+}
+
 static void bpf_map__destroy(struct bpf_map *map);
 
 static int bpf_object__create_map(struct bpf_object *obj, struct bpf_map *map, bool is_inner)
@@ -5520,6 +5812,12 @@ bpf_object__create_maps(struct bpf_object *obj)
 					memcpy(map->mmaped, obj->arena_data, obj->arena_data_sz);
 					zfree(&obj->arena_data);
 				}
+			} else if (map->def.type == BPF_MAP_TYPE_INSN_SET) {
+				if (map->map_extra & BPF_F_STATIC_KEY) {
+					err = bpf_object__init_static_key_map(obj, map);
+					if (err < 0)
+						goto err_out;
+				}
 			}
 			if (map->init_slots_sz && map->def.type != BPF_MAP_TYPE_PROG_ARRAY) {
 				err = init_map_in_map_slots(obj, map);
@@ -6344,10 +6642,43 @@ static struct reloc_desc *find_prog_insn_relo(const struct bpf_program *prog, si
 		       sizeof(*prog->reloc_desc), cmp_relo_by_insn_idx);
 }
 
+static int append_subprog_static_keys(struct bpf_program *main_prog,
+				      struct bpf_program *subprog)
+{
+	size_t main_size = main_prog->static_keys_cnt * sizeof(struct static_key);
+	size_t subprog_size = subprog->static_keys_cnt * sizeof(struct static_key);
+	struct static_key *key;
+	void *new_keys;
+	int i, j;
+
+	if (!subprog->static_keys_cnt)
+		return 0;
+
+	new_keys = realloc(main_prog->static_keys, subprog_size + main_size);
+	if (!new_keys)
+		return -ENOMEM;
+
+	memcpy(new_keys + main_size, subprog->static_keys, subprog_size);
+
+	for (i = 0; i < subprog->static_keys_cnt; i++) {
+		key = new_keys + main_size + i * sizeof(struct static_key);
+		for (j = 0; j < key->insns_cnt; j++) {
+			key->insns[j].insn_offset += subprog->sub_insn_off;
+			key->insns[j].jump_target += subprog->sub_insn_off;
+		}
+	}
+
+	main_prog->static_keys = new_keys;
+	main_prog->static_keys_cnt += subprog->static_keys_cnt;
+
+	return 0;
+}
+
 static int append_subprog_relos(struct bpf_program *main_prog, struct bpf_program *subprog)
 {
 	int new_cnt = main_prog->nr_reloc + subprog->nr_reloc;
 	struct reloc_desc *relos;
+	int err;
 	int i;
 
 	if (main_prog == subprog)
@@ -6370,6 +6701,11 @@ static int append_subprog_relos(struct bpf_program *main_prog, struct bpf_progra
 	 */
 	main_prog->reloc_desc = relos;
 	main_prog->nr_reloc = new_cnt;
+
+	err = append_subprog_static_keys(main_prog, subprog);
+	if (err)
+		return err;
+
 	return 0;
 }
 
@@ -7337,6 +7673,8 @@ static int bpf_object__collect_relos(struct bpf_object *obj)
 			err = bpf_object__collect_st_ops_relos(obj, shdr, data);
 		else if (idx == obj->efile.btf_maps_shndx)
 			err = bpf_object__collect_map_relos(obj, shdr, data);
+		else if (idx == obj->efile.static_keys_data_shndx)
+			err = bpf_object__collect_static_keys_relos(obj, shdr, data);
 		else
 			err = bpf_object__collect_prog_relos(obj, shdr, data);
 		if (err)
@@ -7461,6 +7799,7 @@ static int libbpf_prepare_prog_load(struct bpf_program *prog,
 		opts->attach_btf_obj_fd = btf_obj_fd;
 		opts->attach_btf_id = btf_type_id;
 	}
+
 	return 0;
 }
 
@@ -7551,6 +7890,27 @@ static int bpf_object_load_prog(struct bpf_object *obj, struct bpf_program *prog
 		return 0;
 	}
 
+	if (obj->fd_array_cnt) {
+		pr_warn("not supported: fd_array was already present\n");
+		return -ENOTSUP;
+	} else if (prog->static_keys_cnt) {
+		int i, fd, *fd_array;
+
+		fd_array = calloc(prog->static_keys_cnt, sizeof(int));
+		if (!fd_array)
+			return -ENOMEM;
+
+		for (i = 0; i < prog->static_keys_cnt; i++) {
+			fd = prog->static_keys[i].map->fd;
+			if (fd < 0)
+				return -EINVAL;
+			fd_array[i] = fd;
+		}
+
+		load_attr.fd_array = fd_array;
+		load_attr.fd_array_cnt = prog->static_keys_cnt;
+	}
+
 retry_load:
 	/* if log_level is zero, we don't request logs initially even if
 	 * custom log_buf is specified; if the program load fails, then we'll
diff --git a/tools/lib/bpf/libbpf_internal.h b/tools/lib/bpf/libbpf_internal.h
index 76669c73dcd1..0235e85832c2 100644
--- a/tools/lib/bpf/libbpf_internal.h
+++ b/tools/lib/bpf/libbpf_internal.h
@@ -56,6 +56,9 @@
 #ifndef R_BPF_64_ABS32
 #define R_BPF_64_ABS32 3
 #endif
+#ifndef R_BPF_64_NODYLD32
+#define R_BPF_64_NODYLD32 4
+#endif
 #ifndef R_BPF_64_32
 #define R_BPF_64_32 10
 #endif
diff --git a/tools/lib/bpf/linker.c b/tools/lib/bpf/linker.c
index 800e0ef09c37..4bcf122d053c 100644
--- a/tools/lib/bpf/linker.c
+++ b/tools/lib/bpf/linker.c
@@ -28,6 +28,7 @@
 #include "str_error.h"
 
 #define BTF_EXTERN_SEC ".extern"
+#define STATIC_KEYS_REL_SEC ".rel.static_keys"
 
 struct src_sec {
 	const char *sec_name;
@@ -1037,7 +1038,8 @@ static int linker_sanity_check_elf_relos(struct src_obj *obj, struct src_sec *se
 		size_t sym_type = ELF64_R_TYPE(relo->r_info);
 
 		if (sym_type != R_BPF_64_64 && sym_type != R_BPF_64_32 &&
-		    sym_type != R_BPF_64_ABS64 && sym_type != R_BPF_64_ABS32) {
+		    sym_type != R_BPF_64_ABS64 && sym_type != R_BPF_64_ABS32 &&
+		    sym_type != R_BPF_64_NODYLD32 && strcmp(sec->sec_name, STATIC_KEYS_REL_SEC)) {
 			pr_warn("ELF relo #%d in section #%zu has unexpected type %zu in %s\n",
 				i, sec->sec_idx, sym_type, obj->filename);
 			return -EINVAL;
@@ -2272,7 +2274,7 @@ static int linker_append_elf_relos(struct bpf_linker *linker, struct src_obj *ob
 						insn->imm += sec->dst_off / sizeof(struct bpf_insn);
 					else
 						insn->imm += sec->dst_off;
-				} else {
+				} else if (strcmp(src_sec->sec_name, STATIC_KEYS_REL_SEC)) {
 					pr_warn("relocation against STT_SECTION in non-exec section is not supported!\n");
 					return -EINVAL;
 				}
-- 
2.34.1

[RFC PATCH bpf-next 13/14] libbpf: Add bpf_static_key_update() API

[Anton Protopopov]

Add low-level wrapper API for BPF_STATIC_KEY_UPDATE
command in bpf() syscall.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 tools/lib/bpf/bpf.c      | 17 +++++++++++++++++
 tools/lib/bpf/bpf.h      | 19 +++++++++++++++++++
 tools/lib/bpf/libbpf.map |  1 +
 3 files changed, 37 insertions(+)

diff --git a/tools/lib/bpf/bpf.c b/tools/lib/bpf/bpf.c
index a9c3e33d0f8a..330d9523fc2b 100644
--- a/tools/lib/bpf/bpf.c
+++ b/tools/lib/bpf/bpf.c
@@ -1331,3 +1331,20 @@ int bpf_token_create(int bpffs_fd, struct bpf_token_create_opts *opts)
 	fd = sys_bpf_fd(BPF_TOKEN_CREATE, &attr, attr_sz);
 	return libbpf_err_errno(fd);
 }
+
+int bpf_static_key_update(int map_fd, struct bpf_static_key_update_opts *opts)
+{
+	const size_t attr_sz = offsetofend(union bpf_attr, static_key);
+	union bpf_attr attr;
+	int ret;
+
+	if (!OPTS_VALID(opts, bpf_static_key_update_opts))
+		return libbpf_err(-EINVAL);
+
+	memset(&attr, 0, attr_sz);
+	attr.static_key.map_fd = map_fd;
+	attr.static_key.on = OPTS_GET(opts, on, 0);
+
+	ret = sys_bpf(BPF_STATIC_KEY_UPDATE, &attr, attr_sz);
+	return libbpf_err_errno(ret);
+}
diff --git a/tools/lib/bpf/bpf.h b/tools/lib/bpf/bpf.h
index 777627d33d25..c76abfda85f8 100644
--- a/tools/lib/bpf/bpf.h
+++ b/tools/lib/bpf/bpf.h
@@ -704,6 +704,25 @@ struct bpf_token_create_opts {
 LIBBPF_API int bpf_token_create(int bpffs_fd,
 				struct bpf_token_create_opts *opts);
 
+struct bpf_static_key_update_opts {
+	size_t sz; /* size of this struct for forward/backward compatibility */
+	__u32 on;
+	size_t :0;
+};
+#define bpf_static_key_update_opts__last_field on
+
+/**
+ * @brief **bpf_static_key_update()** updates the value of a static key
+ *
+ * @param map_fd FD for the static key.
+ * @param opts optional BPF token creation options, can be NULL
+ *
+ * @return 0 on success; negative error code, otherwise (errno
+ * is also set to the error code)
+ */
+LIBBPF_API int bpf_static_key_update(int map_fd,
+				     struct bpf_static_key_update_opts *opts);
+
 #ifdef __cplusplus
 } /* extern "C" */
 #endif
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index d8b71f22f197..fc8f01d5804a 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -439,4 +439,5 @@ LIBBPF_1.6.0 {
 		bpf_object__prepare;
 		btf__add_decl_attr;
 		btf__add_type_attr;
+		bpf_static_key_update;
 } LIBBPF_1.5.0;
-- 
2.34.1

[RFC PATCH bpf-next 14/14] selftests/bpf: Add tests for BPF static calls

[Anton Protopopov]

Add self-tests to test new BPF_STATIC_BRANCH_JA jump instructions
and the BPF_STATIC_KEY_UPDATE syscall.

Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
 .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++++++++++
 .../selftests/bpf/progs/bpf_static_keys.c     | 131 +++++++
 2 files changed, 490 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
new file mode 100644
index 000000000000..3f105d36743b
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
@@ -0,0 +1,359 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+
+#include <sys/syscall.h>
+#include <bpf/bpf.h>
+
+#include "bpf_static_keys.skel.h"
+
+#define VAL_ON	7
+#define VAL_OFF	3
+
+enum {
+	OFF,
+	ON
+};
+
+static int _bpf_prog_load(struct bpf_insn *insns, __u32 insn_cnt)
+{
+	return bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, NULL);
+}
+
+static int _bpf_static_key_update(int map_fd, __u32 on)
+{
+	LIBBPF_OPTS(bpf_static_key_update_opts, opts);
+
+	opts.on = on;
+
+	return bpf_static_key_update(map_fd, &opts);
+}
+
+#define BPF_JMP32_OR_NOP(IMM, OFF)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
+		.dst_reg = 0,					\
+		.src_reg = BPF_STATIC_BRANCH_JA,		\
+		.off   = OFF,					\
+		.imm   = IMM })
+
+#define BPF_JMP_OR_NOP(IMM, OFF)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_JMP | BPF_JA | BPF_K,		\
+		.dst_reg = 0,					\
+		.src_reg = BPF_STATIC_BRANCH_JA,		\
+		.off   = OFF,					\
+		.imm   = IMM })
+
+#define BPF_NOP_OR_JMP32(IMM, OFF)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
+		.dst_reg = 0,					\
+		.src_reg = BPF_STATIC_BRANCH_JA |		\
+			   BPF_STATIC_BRANCH_NOP,		\
+		.off   = OFF,					\
+		.imm   = IMM })
+
+#define BPF_NOP_OR_JMP(IMM, OFF)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_JMP | BPF_JA | BPF_K,		\
+		.dst_reg = 0,					\
+		.src_reg = BPF_STATIC_BRANCH_JA |		\
+			   BPF_STATIC_BRANCH_NOP,		\
+		.off   = OFF,					\
+		.imm   = IMM })
+
+static const struct bpf_insn insns0[] = {
+	BPF_JMP_OR_NOP(0, 1),
+	BPF_NOP_OR_JMP(0, 1),
+	BPF_JMP32_OR_NOP(1, 0),
+	BPF_NOP_OR_JMP32(1, 0),
+};
+
+/* Lower-level selftests for the gotol_or_nop/nop_or_gotol instructions */
+static void check_insn(void)
+{
+	struct bpf_insn insns[] = {
+		{}, /* we will substitute this by insn0[i], i=0,1,2,3 */
+		BPF_JMP_IMM(BPF_JA, 0, 0, 1),
+		BPF_JMP_IMM(BPF_JA, 0, 0, -2),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	bool stop = false;
+	int prog_fd[4];
+	int i;
+
+	for (i = 0; i < 4; i++) {
+		insns[0] = insns0[i];
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_GE(prog_fd[i], 0, "correct program"))
+			stop = true;
+	}
+
+	for (i = 0; i < 4; i++)
+		close(prog_fd[i]);
+
+	if (stop)
+		return;
+
+	/* load should fail: incorrect SRC */
+	for (i = 0; i < 4; i++) {
+		insns[0] = insns0[i];
+		insns[0].src_reg |= 4;
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect src"))
+			return;
+	}
+
+	/* load should fail: incorrect DST */
+	for (i = 0; i < 4; i++) {
+		insns[0] = insns0[i];
+		insns[0].dst_reg = i + 1; /* non-zero */
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect dst"))
+			return;
+	}
+
+	/* load should fail: both off and imm are set */
+	for (i = 0; i < 4; i++) {
+		insns[0] = insns0[i];
+		insns[0].imm = insns[0].off = insns0[i].imm ?: insns0[i].off;
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect imm/off"))
+			return;
+	}
+
+	/* load should fail: offset is incorrect */
+	for (i = 0; i < 4; i++) {
+		insns[0] = insns0[i];
+
+		if (insns0[i].imm)
+			insns[0].imm = -2;
+		else
+			insns[0].off = -2;
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect imm/off"))
+			return;
+
+		if (insns0[i].imm)
+			insns[0].imm = 42;
+		else
+			insns[0].off = 42;
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect imm/off"))
+			return;
+
+		/* 0 is not allowed */
+		insns[0].imm = insns[0].off = 0;
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect imm/off"))
+			return;
+	}
+
+	/* incorrect field is used */
+	for (i = 0; i < 4; i++) {
+		int tmp;
+
+		insns[0] = insns0[i];
+
+		tmp = insns[0].imm;
+		insns[0].imm = insns[0].off;
+		insns[0].off = tmp;
+
+		prog_fd[i] = _bpf_prog_load(insns, ARRAY_SIZE(insns));
+		if (!ASSERT_EQ(prog_fd[i], -EINVAL, "incorrect field"))
+			return;
+	}
+}
+
+static void trigger_prog(void)
+{
+	usleep(1);
+}
+
+static void __check_one_key(struct bpf_static_keys *skel,
+			    struct bpf_map *key,
+			    int val_off,
+			    int val_on)
+{
+	int map_fd;
+	int ret;
+
+	map_fd = bpf_map__fd(key);
+	if (!ASSERT_GT(map_fd, 0, "key"))
+		return;
+
+	ret = _bpf_static_key_update(map_fd, ON);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(ON)"))
+		return;
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_on, "skel->bss->ret_user"))
+		return;
+
+	_bpf_static_key_update(map_fd, OFF);
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_off, "skel->bss->ret_user"))
+		return;
+}
+
+static void check_one_key(struct bpf_static_keys *skel, struct bpf_program *prog, struct bpf_map *key)
+{
+	struct bpf_link *link;
+
+	link = bpf_program__attach(prog);
+	if (!ASSERT_OK_PTR(link, "link"))
+		return;
+
+	__check_one_key(skel, key, VAL_OFF, VAL_ON);
+
+	bpf_link__destroy(link);
+}
+
+static void check_one_key_multiple(struct bpf_static_keys *skel, struct bpf_map *key)
+{
+	struct bpf_link *link;
+
+	link = bpf_program__attach(skel->progs.check_one_key_multiple);
+	if (!ASSERT_OK_PTR(link, "link"))
+		return;
+
+	__check_one_key(skel, key, VAL_OFF * 3, VAL_ON * 3);
+
+	bpf_link__destroy(link);
+}
+
+static void check_one_key_long_jump(struct bpf_static_keys *skel, struct bpf_map *key)
+{
+	struct bpf_link *link;
+
+	link = bpf_program__attach(skel->progs.check_one_key_long_jump);
+	if (!ASSERT_OK_PTR(link, "link"))
+		return;
+
+	__check_one_key(skel, key, 1000, 2000);
+
+	bpf_link__destroy(link);
+}
+
+static void __check_multiple_keys(struct bpf_static_keys *skel,
+				  struct bpf_map *key1,
+				  struct bpf_map *key2,
+				  int val_off_off,
+				  int val_off_on,
+				  int val_on_off,
+				  int val_on_on)
+{
+	int map_fd1, map_fd2;
+	int ret;
+
+	map_fd1 = bpf_map__fd(key1);
+	if (!ASSERT_GT(map_fd1, 0, "key1"))
+		return;
+
+	map_fd2 = bpf_map__fd(key2);
+	if (!ASSERT_GT(map_fd2, 0, "key2"))
+		return;
+
+	ret = _bpf_static_key_update(map_fd1, OFF);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key1, OFF)"))
+		return;
+	ret = _bpf_static_key_update(map_fd2, OFF);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key2, OFF)"))
+		return;
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_off_off, "skel->bss->ret_user"))
+		return;
+
+	ret = _bpf_static_key_update(map_fd1, ON);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key1, ON)"))
+		return;
+	ret = _bpf_static_key_update(map_fd2, OFF);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key2, OFF)"))
+		return;
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_off_on, "skel->bss->ret_user"))
+		return;
+
+	ret = _bpf_static_key_update(map_fd1, OFF);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key1, OFF)"))
+		return;
+	ret = _bpf_static_key_update(map_fd2, ON);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key2, ON)"))
+		return;
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_on_off, "skel->bss->ret_user"))
+		return;
+
+	ret = _bpf_static_key_update(map_fd1, ON);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key1, ON)"))
+		return;
+	ret = _bpf_static_key_update(map_fd2, ON);
+	if (!ASSERT_EQ(ret, 0, "_bpf_static_key_update(key2, ON)"))
+		return;
+	skel->bss->ret_user = 0;
+	trigger_prog();
+	if (!ASSERT_EQ(skel->bss->ret_user, val_on_on, "skel->bss->ret_user"))
+		return;
+}
+
+static void check_multiple_keys(struct bpf_static_keys *skel,
+				struct bpf_map *key1,
+				struct bpf_map *key2)
+{
+	struct bpf_link *link;
+
+	link = bpf_program__attach(skel->progs.check_multiple_keys);
+	if (!ASSERT_OK_PTR(link, "link"))
+		return;
+
+	__check_multiple_keys(skel, key1, key2, 0, 3, 30, 33);
+
+	bpf_link__destroy(link);
+}
+
+static void check_bpf_to_bpf_call(struct bpf_static_keys *skel,
+				  struct bpf_map *key1,
+				  struct bpf_map *key2)
+{
+	struct bpf_link *link;
+
+	link = bpf_program__attach(skel->progs.check_bpf_to_bpf_call);
+	if (!ASSERT_OK_PTR(link, "link"))
+		return;
+
+	__check_multiple_keys(skel, key1, key2, 0, 303, 3030, 3333);
+
+	bpf_link__destroy(link);
+}
+
+static void check_syscall(void)
+{
+	struct bpf_static_keys *skel;
+
+	skel = bpf_static_keys__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "bpf_static_keys__open_and_load"))
+		return;
+
+	check_one_key(skel, skel->progs.check_one_key_likely, skel->maps.key1);
+	check_one_key(skel, skel->progs.check_one_key_unlikely, skel->maps.key2);
+	check_one_key_multiple(skel, skel->maps.key3);
+	check_one_key_long_jump(skel, skel->maps.key4);
+	check_multiple_keys(skel, skel->maps.key5, skel->maps.key6);
+
+	bpf_static_keys__destroy(skel);
+}
+
+void test_bpf_static_keys(void)
+{
+	if (test__start_subtest("check_insn"))
+		check_insn();
+
+	if (test__start_subtest("check_syscall"))
+		check_syscall();
+}
diff --git a/tools/testing/selftests/bpf/progs/bpf_static_keys.c b/tools/testing/selftests/bpf/progs/bpf_static_keys.c
new file mode 100644
index 000000000000..79272de8e682
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/bpf_static_keys.c
@@ -0,0 +1,131 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, u32);
+	__type(value, u32);
+} just_map SEC(".maps");
+
+int ret_user;
+
+#define VAL_ON	7
+#define VAL_OFF	3
+
+DEFINE_STATIC_KEY(key1);
+
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_one_key_likely(void *ctx)
+{
+	if (bpf_static_branch_likely(&key1))
+		ret_user += VAL_ON;
+	else
+		ret_user += VAL_OFF;
+
+	return 0;
+}
+
+DEFINE_STATIC_KEY(key2);
+
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_one_key_unlikely(void *ctx)
+{
+	if (bpf_static_branch_unlikely(&key2))
+		ret_user += VAL_ON;
+	else
+		ret_user += VAL_OFF;
+
+	return 0;
+}
+
+DEFINE_STATIC_KEY(key3);
+
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_one_key_multiple(void *ctx)
+{
+	if (bpf_static_branch_likely(&key3))
+		ret_user += VAL_ON;
+	else
+		ret_user += VAL_OFF;
+
+	bpf_printk("%lu\n", bpf_jiffies64());
+
+	if (bpf_static_branch_unlikely(&key3))
+		ret_user += VAL_ON;
+	else
+		ret_user += VAL_OFF;
+
+	bpf_printk("%lu\n", bpf_jiffies64());
+
+	if (bpf_static_branch_likely(&key3))
+		ret_user += VAL_ON;
+	else
+		ret_user += VAL_OFF;
+
+	return 0;
+}
+
+static __always_inline int big_chunk_of_code(volatile int *x)
+{
+	#pragma clang loop unroll_count(256)
+	for (int i = 0; i < 256; i++)
+		*x += 1;
+
+	return *x;
+}
+
+DEFINE_STATIC_KEY(key4);
+
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_one_key_long_jump(void *ctx)
+{
+	int x;
+
+	if (bpf_static_branch_unlikely(&key4)) {
+		x = 1744;
+		big_chunk_of_code(&x);
+		ret_user = x;
+	} else {
+		x = 744;
+		big_chunk_of_code(&x);
+		ret_user = x;
+	}
+
+	return 0;
+}
+
+DEFINE_STATIC_KEY(key5);
+DEFINE_STATIC_KEY(key6);
+
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_multiple_keys(void *ctx)
+{
+	__u64 j = bpf_jiffies64();
+
+	if (bpf_static_branch_likely(&key5))
+		ret_user += 1;
+	if (bpf_static_branch_unlikely(&key6))
+		ret_user += 10;
+
+	bpf_printk("%lu\n", j);
+
+	if (bpf_static_branch_unlikely(&key5))
+		ret_user += 1;
+	if (bpf_static_branch_likely(&key6))
+		ret_user += 10;
+
+	bpf_printk("%lu\n", bpf_jiffies64());
+
+	if (bpf_static_branch_likely(&key5))
+		ret_user += 1;
+	if (bpf_static_branch_unlikely(&key6))
+		ret_user += 10;
+
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.34.1

Re: [RFC PATCH bpf-next 14/14] selftests/bpf: Add tests for BPF static calls

[Yonghong Song]

On 3/18/25 7:33 AM, Anton Protopopov wrote:
> Add self-tests to test new BPF_STATIC_BRANCH_JA jump instructions
> and the BPF_STATIC_KEY_UPDATE syscall.
>
> Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> ---
>   .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++++++++++
>   .../selftests/bpf/progs/bpf_static_keys.c     | 131 +++++++
>   2 files changed, 490 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
>   create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> new file mode 100644
> index 000000000000..3f105d36743b
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> @@ -0,0 +1,359 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <test_progs.h>
> +
> +#include <sys/syscall.h>
> +#include <bpf/bpf.h>
> +
> +#include "bpf_static_keys.skel.h"
> +
> +#define VAL_ON	7
> +#define VAL_OFF	3
> +
> +enum {
> +	OFF,
> +	ON
> +};
> +
> +static int _bpf_prog_load(struct bpf_insn *insns, __u32 insn_cnt)
> +{
> +	return bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, NULL);
> +}
> +
> +static int _bpf_static_key_update(int map_fd, __u32 on)
> +{
> +	LIBBPF_OPTS(bpf_static_key_update_opts, opts);
> +
> +	opts.on = on;
> +
> +	return bpf_static_key_update(map_fd, &opts);
> +}
> +
> +#define BPF_JMP32_OR_NOP(IMM, OFF)				\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
> +		.dst_reg = 0,					\
> +		.src_reg = BPF_STATIC_BRANCH_JA,		\
> +		.off   = OFF,					\
> +		.imm   = IMM })
> +
> +#define BPF_JMP_OR_NOP(IMM, OFF)				\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_JMP | BPF_JA | BPF_K,		\
> +		.dst_reg = 0,					\
> +		.src_reg = BPF_STATIC_BRANCH_JA,		\
> +		.off   = OFF,					\
> +		.imm   = IMM })
> +
> +#define BPF_NOP_OR_JMP32(IMM, OFF)				\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
> +		.dst_reg = 0,					\
> +		.src_reg = BPF_STATIC_BRANCH_JA |		\
> +			   BPF_STATIC_BRANCH_NOP,		\
> +		.off   = OFF,					\
> +		.imm   = IMM })
> +
> +#define BPF_NOP_OR_JMP(IMM, OFF)				\
> +	((struct bpf_insn) {					\
> +		.code  = BPF_JMP | BPF_JA | BPF_K,		\
> +		.dst_reg = 0,					\
> +		.src_reg = BPF_STATIC_BRANCH_JA |		\
> +			   BPF_STATIC_BRANCH_NOP,		\
> +		.off   = OFF,					\
> +		.imm   = IMM })
> +
> +static const struct bpf_insn insns0[] = {
> +	BPF_JMP_OR_NOP(0, 1),
> +	BPF_NOP_OR_JMP(0, 1),
> +	BPF_JMP32_OR_NOP(1, 0),
> +	BPF_NOP_OR_JMP32(1, 0),
> +};
> +

[...]

> +
> +static void check_bpf_to_bpf_call(struct bpf_static_keys *skel,
> +				  struct bpf_map *key1,
> +				  struct bpf_map *key2)
> +{
> +	struct bpf_link *link;
> +
> +	link = bpf_program__attach(skel->progs.check_bpf_to_bpf_call);

there is no progcheck_bpf_to_bpf_call. Compilation will fail.

> +	if (!ASSERT_OK_PTR(link, "link"))
> +		return;
> +
> +	__check_multiple_keys(skel, key1, key2, 0, 303, 3030, 3333);
> +
> +	bpf_link__destroy(link);
> +}
> +
[...]

Re: [RFC PATCH bpf-next 14/14] selftests/bpf: Add tests for BPF static calls

[Anton Protopopov]

On 25/03/18 01:53PM, Yonghong Song wrote:
> 
> 
> On 3/18/25 7:33 AM, Anton Protopopov wrote:
> > Add self-tests to test new BPF_STATIC_BRANCH_JA jump instructions
> > and the BPF_STATIC_KEY_UPDATE syscall.
> > 
> > Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
> > ---
> >   .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++++++++++
> >   .../selftests/bpf/progs/bpf_static_keys.c     | 131 +++++++
> >   2 files changed, 490 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> >   create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c
> > 
> > diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> > new file mode 100644
> > index 000000000000..3f105d36743b
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> > @@ -0,0 +1,359 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +#include <test_progs.h>
> > +
> > +#include <sys/syscall.h>
> > +#include <bpf/bpf.h>
> > +
> > +#include "bpf_static_keys.skel.h"
> > +
> > +#define VAL_ON	7
> > +#define VAL_OFF	3
> > +
> > +enum {
> > +	OFF,
> > +	ON
> > +};
> > +
> > +static int _bpf_prog_load(struct bpf_insn *insns, __u32 insn_cnt)
> > +{
> > +	return bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, NULL);
> > +}
> > +
> > +static int _bpf_static_key_update(int map_fd, __u32 on)
> > +{
> > +	LIBBPF_OPTS(bpf_static_key_update_opts, opts);
> > +
> > +	opts.on = on;
> > +
> > +	return bpf_static_key_update(map_fd, &opts);
> > +}
> > +
> > +#define BPF_JMP32_OR_NOP(IMM, OFF)				\
> > +	((struct bpf_insn) {					\
> > +		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
> > +		.dst_reg = 0,					\
> > +		.src_reg = BPF_STATIC_BRANCH_JA,		\
> > +		.off   = OFF,					\
> > +		.imm   = IMM })
> > +
> > +#define BPF_JMP_OR_NOP(IMM, OFF)				\
> > +	((struct bpf_insn) {					\
> > +		.code  = BPF_JMP | BPF_JA | BPF_K,		\
> > +		.dst_reg = 0,					\
> > +		.src_reg = BPF_STATIC_BRANCH_JA,		\
> > +		.off   = OFF,					\
> > +		.imm   = IMM })
> > +
> > +#define BPF_NOP_OR_JMP32(IMM, OFF)				\
> > +	((struct bpf_insn) {					\
> > +		.code  = BPF_JMP32 | BPF_JA | BPF_K,		\
> > +		.dst_reg = 0,					\
> > +		.src_reg = BPF_STATIC_BRANCH_JA |		\
> > +			   BPF_STATIC_BRANCH_NOP,		\
> > +		.off   = OFF,					\
> > +		.imm   = IMM })
> > +
> > +#define BPF_NOP_OR_JMP(IMM, OFF)				\
> > +	((struct bpf_insn) {					\
> > +		.code  = BPF_JMP | BPF_JA | BPF_K,		\
> > +		.dst_reg = 0,					\
> > +		.src_reg = BPF_STATIC_BRANCH_JA |		\
> > +			   BPF_STATIC_BRANCH_NOP,		\
> > +		.off   = OFF,					\
> > +		.imm   = IMM })
> > +
> > +static const struct bpf_insn insns0[] = {
> > +	BPF_JMP_OR_NOP(0, 1),
> > +	BPF_NOP_OR_JMP(0, 1),
> > +	BPF_JMP32_OR_NOP(1, 0),
> > +	BPF_NOP_OR_JMP32(1, 0),
> > +};
> > +
> 
> [...]
> 
> > +
> > +static void check_bpf_to_bpf_call(struct bpf_static_keys *skel,
> > +				  struct bpf_map *key1,
> > +				  struct bpf_map *key2)
> > +{
> > +	struct bpf_link *link;
> > +
> > +	link = bpf_program__attach(skel->progs.check_bpf_to_bpf_call);
> 
> there is no progcheck_bpf_to_bpf_call. Compilation will fail.

Oops, thanks! I haven't cleaned it out (have it in my dev branch)...
(Compilation will fail in the first place in progs/bpf_static_keys.c, as
`asm(gotol_or_nop)` will not compile.

> > +	if (!ASSERT_OK_PTR(link, "link"))
> > +		return;
> > +
> > +	__check_multiple_keys(skel, key1, key2, 0, 303, 3030, 3333);
> > +
> > +	bpf_link__destroy(link);
> > +}
> > +
> [...]

Re: [RFC PATCH bpf-next 00/14] instruction sets and static keys

[Yonghong Song]

On 3/18/25 7:33 AM, Anton Protopopov wrote:
> This patchset implements new type of map, instruction set, and uses
> it to build support for BPF static keys. The same map will be later
> used to provide support for indirect jumps and indirect calls. See
> [1], [2] for more context.
>
> Short table of contents:
>
>    * patches 1, 9, 10, 11 are simple fixes (which can be sent
>      independently, if acked)
>
>    * patches 2, 3 add a new map type, BPF_MAP_TYPE_INSN_SET, and
>      corresponding selftests. This map is used to track how original
>      instructions were relocated into 'xlated' during the verification
>
>    * patches 4, 5, 6, 7, 8 add support for static keys (kernel only)
>      using (an extension) to that new map type. Only x86 support is
>      added in this RFC
>
>    * patches 12, 13, 14 add libbpf-side support for static keys and
>      selftests
>
> It is RFC for a few reasons:
>
> 1) The kernel side of the static keys looks clear, however, the
> libbpf side is not _that_ clear. I thought that this is better to
> commit to a particular userspace design, as any particular design
> requires a lot of changes on the libbpf side. See patch 12 for
> the details
>
> 2) The libbpf part of the series requires a patched LLVM (see [3]),
> which adds support for gotol_or_nop/nop_or_gotol instructions, so
> selftests would not compile in CI.
>
> 3) Patch 4 adds support for a new BPF instruction. It looks
> reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> may_goto. Reasons: a follow up will add support for
> BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> Then another follow up will add support CALL|BPF_X, for which there's
> no corresponding magic instruction (to be discussed at the following
> LSF/MM/BPF).
>
> Besides these reasons, there are some questions / known bugs,
> which will be fixed once the general plan is confirmed:
>
>    * bpf_jit_blind_constants will patch code, which is ignored in this
>      RFC series. The solution would be either moving tracking
>      instruction sets to bpf_prog from the verifier environment,
>      or moving bpf_jit_blind_constants upper the stack (right now,
>      this is the first thing which every jit does, so maybe it can
>      be actually executed from the verifier, and provide env context)
>
>    * gen-loader not supported, fd_array usage in libbpf should be
>      re-designed (see patch 12 for more details)
>
>    * insn_off -> insn_set map mapping should be optimized (now it is
>      brute force)
>
> Links:
>    1. http://oldvger.kernel.org/bpfconf2024_material/bpf_static_keys.pdf
>    2. https://lpc.events/event/18/contributions/1941/
>    3. https://github.com/aspsk/llvm-project/tree/static-keys

For llvm patch in [3], please remove changes in function isValidIdInMiddle()
as gotol_or_nop or nop_or_gotol will not appear in the *middle* of any
instruction. "gotol" should not be there either, I may remove it sometime
later.

>
> Anton Protopopov (14):
>    bpf: fix a comment describing bpf_attr
>    bpf: add new map type: instructions set
>    selftests/bpf: add selftests for new insn_set map
>    bpf: add support for an extended JA instruction
>    bpf: Add kernel/bpftool asm support for new instructions
>    bpf: add BPF_STATIC_KEY_UPDATE syscall
>    bpf: save the start of functions in bpf_prog_aux
>    bpf, x86: implement static key support
>    selftests/bpf: add guard macros around likely/unlikely
>    libbpf: add likely/unlikely macros
>    selftests/bpf: remove likely/unlikely definitions
>    libbpf: BPF Static Keys support
>    libbpf: Add bpf_static_key_update() API
>    selftests/bpf: Add tests for BPF static calls
>
>   arch/x86/net/bpf_jit_comp.c                   |  65 +-
>   include/linux/bpf.h                           |  28 +
>   include/linux/bpf_types.h                     |   1 +
>   include/linux/bpf_verifier.h                  |   2 +
>   include/uapi/linux/bpf.h                      |  40 +-
>   kernel/bpf/Makefile                           |   2 +-
>   kernel/bpf/bpf_insn_set.c                     | 400 +++++++++++
>   kernel/bpf/core.c                             |   5 +
>   kernel/bpf/disasm.c                           |  33 +-
>   kernel/bpf/syscall.c                          |  28 +
>   kernel/bpf/verifier.c                         |  94 ++-
>   tools/include/uapi/linux/bpf.h                |  40 +-
>   tools/lib/bpf/bpf.c                           |  17 +
>   tools/lib/bpf/bpf.h                           |  19 +
>   tools/lib/bpf/bpf_helpers.h                   |  63 ++
>   tools/lib/bpf/libbpf.c                        | 362 +++++++++-
>   tools/lib/bpf/libbpf.map                      |   1 +
>   tools/lib/bpf/libbpf_internal.h               |   3 +
>   tools/lib/bpf/linker.c                        |   6 +-
>   .../selftests/bpf/bpf_arena_spin_lock.h       |   3 -
>   .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
>   .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++
>   .../selftests/bpf/progs/bpf_static_keys.c     | 131 ++++
>   tools/testing/selftests/bpf/progs/iters.c     |   2 -
>   24 files changed, 2315 insertions(+), 28 deletions(-)
>   create mode 100644 kernel/bpf/bpf_insn_set.c
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
>   create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c
>

Re: [RFC PATCH bpf-next 00/14] instruction sets and static keys

[Anton Protopopov]

On 25/03/18 02:00PM, Yonghong Song wrote:
> 
> 
> On 3/18/25 7:33 AM, Anton Protopopov wrote:
> > This patchset implements new type of map, instruction set, and uses
> > it to build support for BPF static keys. The same map will be later
> > used to provide support for indirect jumps and indirect calls. See
> > [1], [2] for more context.
> > 
> > Short table of contents:
> > 
> >    * patches 1, 9, 10, 11 are simple fixes (which can be sent
> >      independently, if acked)
> > 
> >    * patches 2, 3 add a new map type, BPF_MAP_TYPE_INSN_SET, and
> >      corresponding selftests. This map is used to track how original
> >      instructions were relocated into 'xlated' during the verification
> > 
> >    * patches 4, 5, 6, 7, 8 add support for static keys (kernel only)
> >      using (an extension) to that new map type. Only x86 support is
> >      added in this RFC
> > 
> >    * patches 12, 13, 14 add libbpf-side support for static keys and
> >      selftests
> > 
> > It is RFC for a few reasons:
> > 
> > 1) The kernel side of the static keys looks clear, however, the
> > libbpf side is not _that_ clear. I thought that this is better to
> > commit to a particular userspace design, as any particular design
> > requires a lot of changes on the libbpf side. See patch 12 for
> > the details
> > 
> > 2) The libbpf part of the series requires a patched LLVM (see [3]),
> > which adds support for gotol_or_nop/nop_or_gotol instructions, so
> > selftests would not compile in CI.
> > 
> > 3) Patch 4 adds support for a new BPF instruction. It looks
> > reasonable to use an extended BPF_JMP|BPF_JA instruction, and not
> > may_goto. Reasons: a follow up will add support for
> > BPF_JMP|BPF_JA|BPF_X (indirect jumps), which also utilizes INSN_SET maps (see [2]).
> > Then another follow up will add support CALL|BPF_X, for which there's
> > no corresponding magic instruction (to be discussed at the following
> > LSF/MM/BPF).
> > 
> > Besides these reasons, there are some questions / known bugs,
> > which will be fixed once the general plan is confirmed:
> > 
> >    * bpf_jit_blind_constants will patch code, which is ignored in this
> >      RFC series. The solution would be either moving tracking
> >      instruction sets to bpf_prog from the verifier environment,
> >      or moving bpf_jit_blind_constants upper the stack (right now,
> >      this is the first thing which every jit does, so maybe it can
> >      be actually executed from the verifier, and provide env context)
> > 
> >    * gen-loader not supported, fd_array usage in libbpf should be
> >      re-designed (see patch 12 for more details)
> > 
> >    * insn_off -> insn_set map mapping should be optimized (now it is
> >      brute force)
> > 
> > Links:
> >    1. http://oldvger.kernel.org/bpfconf2024_material/bpf_static_keys.pdf
> >    2. https://lpc.events/event/18/contributions/1941/
> >    3. https://github.com/aspsk/llvm-project/tree/static-keys
> 
> For llvm patch in [3], please remove changes in function isValidIdInMiddle()
> as gotol_or_nop or nop_or_gotol will not appear in the *middle* of any
> instruction. "gotol" should not be there either, I may remove it sometime
> later.

Thanks, removed.

> > 
> > Anton Protopopov (14):
> >    bpf: fix a comment describing bpf_attr
> >    bpf: add new map type: instructions set
> >    selftests/bpf: add selftests for new insn_set map
> >    bpf: add support for an extended JA instruction
> >    bpf: Add kernel/bpftool asm support for new instructions
> >    bpf: add BPF_STATIC_KEY_UPDATE syscall
> >    bpf: save the start of functions in bpf_prog_aux
> >    bpf, x86: implement static key support
> >    selftests/bpf: add guard macros around likely/unlikely
> >    libbpf: add likely/unlikely macros
> >    selftests/bpf: remove likely/unlikely definitions
> >    libbpf: BPF Static Keys support
> >    libbpf: Add bpf_static_key_update() API
> >    selftests/bpf: Add tests for BPF static calls
> > 
> >   arch/x86/net/bpf_jit_comp.c                   |  65 +-
> >   include/linux/bpf.h                           |  28 +
> >   include/linux/bpf_types.h                     |   1 +
> >   include/linux/bpf_verifier.h                  |   2 +
> >   include/uapi/linux/bpf.h                      |  40 +-
> >   kernel/bpf/Makefile                           |   2 +-
> >   kernel/bpf/bpf_insn_set.c                     | 400 +++++++++++
> >   kernel/bpf/core.c                             |   5 +
> >   kernel/bpf/disasm.c                           |  33 +-
> >   kernel/bpf/syscall.c                          |  28 +
> >   kernel/bpf/verifier.c                         |  94 ++-
> >   tools/include/uapi/linux/bpf.h                |  40 +-
> >   tools/lib/bpf/bpf.c                           |  17 +
> >   tools/lib/bpf/bpf.h                           |  19 +
> >   tools/lib/bpf/bpf_helpers.h                   |  63 ++
> >   tools/lib/bpf/libbpf.c                        | 362 +++++++++-
> >   tools/lib/bpf/libbpf.map                      |   1 +
> >   tools/lib/bpf/libbpf_internal.h               |   3 +
> >   tools/lib/bpf/linker.c                        |   6 +-
> >   .../selftests/bpf/bpf_arena_spin_lock.h       |   3 -
> >   .../selftests/bpf/prog_tests/bpf_insn_set.c   | 639 ++++++++++++++++++
> >   .../bpf/prog_tests/bpf_static_keys.c          | 359 ++++++++++
> >   .../selftests/bpf/progs/bpf_static_keys.c     | 131 ++++
> >   tools/testing/selftests/bpf/progs/iters.c     |   2 -
> >   24 files changed, 2315 insertions(+), 28 deletions(-)
> >   create mode 100644 kernel/bpf/bpf_insn_set.c
> >   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insn_set.c
> >   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_keys.c
> >   create mode 100644 tools/testing/selftests/bpf/progs/bpf_static_keys.c
> > 
>