* [PATCH v1 bpf-next 1/9] bpf: fix potential error return
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 2/9] bpf: keep track of and expose xlated insn offsets Anton Protopopov
` (8 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
The bpf_remove_insns() function returns WARN_ON_ONCE(error), where
error is a result of bpf_adj_branches(), and thus should be always 0
However, if for any reason it is not 0, then it will be converted to
boolean by WARN_ON_ONCE and returned to user space as 1, not an actual
error value. Fix this by returning the original err after the WARN check.
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
Acked-by: Jiri Olsa <jolsa@kernel.org>
---
kernel/bpf/core.c | 9 ++++++++-
1 file changed, 8 insertions(+), 1 deletion(-)
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 71c459a51d9e..ad8e6f7e0886 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -532,6 +532,8 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
{
+ int err;
+
/* Branch offsets can't overflow when program is shrinking, no need
* to call bpf_adj_branches(..., true) here
*/
@@ -539,7 +541,12 @@ int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
sizeof(struct bpf_insn) * (prog->len - off - cnt));
prog->len -= cnt;
- return WARN_ON_ONCE(bpf_adj_branches(prog, off, off + cnt, off, false));
+ err = bpf_adj_branches(prog, off, off + cnt, off, false);
+ WARN_ON_ONCE(err);
+ if (err)
+ return err;
+
+ return 0;
}
static void bpf_prog_kallsyms_del_subprogs(struct bpf_prog *fp)
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 2/9] bpf: keep track of and expose xlated insn offsets
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 1/9] bpf: fix potential error return Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns Anton Protopopov
` (7 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
On bpf(BPF_PROG_LOAD) syscall a user-supplied program is translated by
the verifier into an "xlated" program. During this process the original
instruction offsets might be adjusted and/or individual instructions
might be replaced by a new set of instructions:
User-supplied prog: ---> Xlated prog:
-- func 0 -- -- func 0 --
insn insn'
... ...
insn insn'
-- func 1 -- -- func 1 --
insn insn'
... ...
insn insn'
-- func N -- -- func N --
insn insn'
... ...
insn insn'
We want to provide users (and ourselves) with the off(insn') -> off(insn)
mapping so that when an xlated program is returned to the userspace by the
bpf_prog_get_info_by_fd() function, users can determine the real offsets
of instructions of interest.
Since commit 9e4c24e7ee7d ("bpf: verifier: record original instruction index")
the verifier saves the original instruction index in env->insn_aux_data.
This information was, however, lost when we patched instructions. Also, the
information about original index was kept in the verifier env only, so was
inaccessible by later stages, like constants blinding during the jit stage.
To address the above issues save the information about the original
indexes in a separate array inside the prog->aux so that it doesn't
depend on the verifier environment and can be adjusted, and accessed,
during later stages.
To let users access the information after the program was loaded, add new
fields, orig_idx_len and orig_idx to struct bpf_prog_info and patch the
bpf_prog_get_info_by_fd function correspondingly.
Example mapping would be something like this:
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
Here the orig_idx array has length 21 and is equal to
(0, 1, 2, 3, 4, 0/*undefined*/, 6, 6, 6, 6, 6, 6, 6, 7, 8, 9, 9, 10, 11, 12)
The item 6 is undefined because the r1=0ll occupies 16 bytes.
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
include/linux/bpf.h | 2 ++
include/linux/bpf_verifier.h | 1 -
include/uapi/linux/bpf.h | 2 ++
kernel/bpf/core.c | 29 +++++++++++++++++++++++++++++
kernel/bpf/syscall.c | 30 ++++++++++++++++++++++++++++++
kernel/bpf/verifier.c | 6 ++----
tools/include/uapi/linux/bpf.h | 2 ++
7 files changed, 67 insertions(+), 5 deletions(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 1ebbee1d648e..4def3dde35f6 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1522,6 +1522,8 @@ struct bpf_prog_aux {
struct work_struct work;
struct rcu_head rcu;
};
+ /* an array of original indexes for all xlated instructions */
+ u32 *orig_idx;
};
struct bpf_prog {
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0dcde339dc7e..8348de569f11 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -553,7 +553,6 @@ struct bpf_insn_aux_data {
u8 alu_state; /* used in combination with alu_limit */
/* below fields are initialized once */
- unsigned int orig_idx; /* original instruction index */
bool jmp_point;
bool prune_point;
/* ensure we check state equivalence and save state checkpoint and
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index d96708380e52..b929523444b0 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -6533,6 +6533,8 @@ struct bpf_prog_info {
__u32 verified_insns;
__u32 attach_btf_obj_id;
__u32 attach_btf_id;
+ __u32 orig_idx_len;
+ __aligned_u64 orig_idx;
} __attribute__((aligned(8)));
struct bpf_map_info {
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index ad8e6f7e0886..f0086925b810 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -469,6 +469,30 @@ static void bpf_adj_linfo(struct bpf_prog *prog, u32 off, u32 delta)
linfo[i].insn_off += delta;
}
+static int bpf_prog_realloc_orig_idx(struct bpf_prog *prog, u32 off, u32 patch_len)
+{
+ u32 *old_idx = prog->aux->orig_idx, *new_idx;
+ u32 new_prog_len = prog->len + patch_len - 1;
+ int i;
+
+ if (patch_len <= 1)
+ return 0;
+
+ new_idx = kzalloc(array_size(new_prog_len, sizeof(u32)), GFP_KERNEL);
+ if (!new_idx)
+ return -ENOMEM;
+
+ memcpy(new_idx, old_idx, sizeof(*old_idx) * off);
+ for (i = off; i < off + patch_len; i++)
+ new_idx[i] = old_idx[off];
+ memcpy(new_idx + off + patch_len, old_idx + off + 1,
+ sizeof(*old_idx) * (prog->len - off));
+
+ prog->aux->orig_idx = new_idx;
+ kfree(old_idx);
+ return 0;
+}
+
struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
const struct bpf_insn *patch, u32 len)
{
@@ -494,6 +518,10 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
(err = bpf_adj_branches(prog, off, off + 1, off + len, true)))
return ERR_PTR(err);
+ err = bpf_prog_realloc_orig_idx(prog, off, len);
+ if (err)
+ return ERR_PTR(err);
+
/* Several new instructions need to be inserted. Make room
* for them. Likely, there's no need for a new allocation as
* last page could have large enough tailroom.
@@ -2778,6 +2806,7 @@ static void bpf_prog_free_deferred(struct work_struct *work)
} else {
bpf_jit_free(aux->prog);
}
+ kfree(aux->orig_idx);
}
void bpf_prog_free(struct bpf_prog *fp)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index b2750b79ac80..172bf8d3aef2 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -2625,6 +2625,18 @@ static bool is_perfmon_prog_type(enum bpf_prog_type prog_type)
}
}
+static void *bpf_prog_alloc_orig_idx(u32 insn_cnt)
+{
+ u32 *orig_idx;
+ int i;
+
+ orig_idx = kcalloc(insn_cnt, sizeof(*orig_idx), GFP_KERNEL);
+ if (orig_idx)
+ for (i = 0; i < insn_cnt; i++)
+ orig_idx[i] = i;
+ return orig_idx;
+}
+
/* last field in 'union bpf_attr' used by this command */
#define BPF_PROG_LOAD_LAST_FIELD prog_token_fd
@@ -2760,6 +2772,12 @@ static int bpf_prog_load(union bpf_attr *attr, bpfptr_t uattr, u32 uattr_size)
goto put_token;
}
+ prog->aux->orig_idx = bpf_prog_alloc_orig_idx(attr->insn_cnt);
+ if (!prog->aux->orig_idx) {
+ err = -ENOMEM;
+ goto free_prog;
+ }
+
prog->expected_attach_type = attr->expected_attach_type;
prog->aux->attach_btf = attach_btf;
prog->aux->attach_btf_id = attr->attach_btf_id;
@@ -4541,6 +4559,18 @@ static int bpf_prog_get_info_by_fd(struct file *file,
return -EFAULT;
}
+ ulen = info.orig_idx_len;
+ if (prog->aux->orig_idx)
+ info.orig_idx_len = prog->len * sizeof(*prog->aux->orig_idx);
+ else
+ info.orig_idx_len = 0;
+ if (info.orig_idx_len && ulen) {
+ if (copy_to_user(u64_to_user_ptr(info.orig_idx),
+ prog->aux->orig_idx,
+ min_t(u32, info.orig_idx_len, ulen)))
+ return -EFAULT;
+ }
+
if (bpf_prog_is_offloaded(prog->aux)) {
err = bpf_prog_offload_info_fill(&info, prog);
if (err)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index cd4d780e5400..2dc48f88f43c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18289,7 +18289,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
if (PTR_ERR(new_prog) == -ERANGE)
verbose(env,
"insn %d cannot be patched due to 16-bit range\n",
- env->insn_aux_data[off].orig_idx);
+ env->prog->aux->orig_idx[off]);
vfree(new_data);
return NULL;
}
@@ -20829,7 +20829,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
{
u64 start_time = ktime_get_ns();
struct bpf_verifier_env *env;
- int i, len, ret = -EINVAL, err;
+ int len, ret = -EINVAL, err;
u32 log_true_size;
bool is_priv;
@@ -20852,8 +20852,6 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
ret = -ENOMEM;
if (!env->insn_aux_data)
goto err_free_env;
- for (i = 0; i < len; i++)
- env->insn_aux_data[i].orig_idx = i;
env->prog = *prog;
env->ops = bpf_verifier_ops[env->prog->type];
env->fd_array = make_bpfptr(attr->fd_array, uattr.is_kernel);
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index d96708380e52..b929523444b0 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -6533,6 +6533,8 @@ struct bpf_prog_info {
__u32 verified_insns;
__u32 attach_btf_obj_id;
__u32 attach_btf_id;
+ __u32 orig_idx_len;
+ __aligned_u64 orig_idx;
} __attribute__((aligned(8)));
struct bpf_map_info {
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 1/9] bpf: fix potential error return Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 2/9] bpf: keep track of and expose xlated insn offsets Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-06 1:09 ` Alexei Starovoitov
2024-02-02 16:28 ` [PATCH v1 bpf-next 4/9] selftests/bpf: Add tests for instructions mappings Anton Protopopov
` (6 subsequent siblings)
9 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
Allow users to get the exact xlated -> jitted instructions mapping.
This is done by using a new field xlated_to_jit in bpf_prog_info
which can return up to prog->len
struct bpf_xlated_to_jit {
u32 off;
u32 len;
};
elements. The xlated_to_jit[insn_off] contains jitted offset within
a function and the length of the resulting jitted instruction.
Example:
Original: Xlated: Jitted:
0: nopl (%rax,%rax)
5: nop
7: pushq %rbp
8: movq %rsp, %rbp
0: call 0x76 0: r0 = 0xfffffbeef b: movabsq $-1923847220, %rax
2: r0 = *(u64 *)(r0 +0) 15: movq (%rax), %rax
1: r1 = 0x9 ll 3: r1 = map[id:666][0]+9 19: movabsq $-102223334445559, %rdi
3: r2 = 0x6 5: r2 = 6 23: movl $6, %esi
4: r3 = r0 6: r3 = r0 28: movq %rax, %rdx
5: call 0x6 7: call bpf_trace_printk 2b: callq 0xffffffffcdead4dc
6: call pc+2 8: call pc+2 30: callq 0x7c
7: r0 = 0x0 9: r0 = 0 35: xorl %eax, %eax
8: exit 10: exit 37: leave
38: jmp 0xffffffffcbeeffbc
--- --- ---
0: nopl (%rax,%rax)
5: nop
7: pushq %rbp
8: movq %rsp, %rbp
9: goto +0x1 11: goto pc+1 b: jmp 0xf
10: goto +0x1 12: goto pc+1 d: jmp 0x11
11: goto -0x2 13: goto pc-2 f: jmp 0xd
12: r0 = 0x0 14: r0 = 0 11: xorl %eax, %eax
13: exit 15: exit 13: leave
14: jmp 0xffffffffcbffbeef
Here the xlated_to_jit array will be of length 16 (11 + 6) and equal to
0: (0xb, 10)
1: (0,0) /* undefined, as the previous instruction is 16 bytes */
2: (0x15, 4)
3: (0x19, 10)
4: (0,0) /* undefined, as the previous instruction is 16 bytes */
5: (0x23, 5)
6: (0x28, 3)
7: (0x2b, 5)
8: (0x30, 5)
9: (0x35, 2)
10: (0x37, 6)
11: (0xb, 2)
12: (0xd, 2)
13: (0xf, 2)
14: (0x11, 2)
15: (0x13, 6)
The prologues are "unmapped": no mapping exists for xlated -> [0,b)
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
arch/x86/net/bpf_jit_comp.c | 14 ++++++++++++++
include/linux/bpf.h | 7 +++++++
include/uapi/linux/bpf.h | 7 +++++++
kernel/bpf/core.c | 24 ++++++++++++++++++++++++
kernel/bpf/syscall.c | 25 +++++++++++++++++++++++++
kernel/bpf/verifier.c | 9 +++++++++
tools/include/uapi/linux/bpf.h | 7 +++++++
7 files changed, 93 insertions(+)
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index e1390d1e331b..a80b8c1e7afe 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -1186,6 +1186,7 @@ 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;
u8 b2 = 0, b3 = 0;
u8 *start_of_ldx;
s64 jmp_offset;
@@ -1290,6 +1291,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 */
@@ -2073,6 +2075,18 @@ st: if (is_imm8(insn->off))
return -EFAULT;
}
memcpy(rw_image + proglen, temp, ilen);
+
+ if (bpf_prog->aux->xlated_to_jit) {
+ u32 func_idx = bpf_prog->aux->func_idx;
+ int off;
+
+ off = i - 1 - adjust_off;
+ if (func_idx)
+ off += bpf_prog->aux->func_info[func_idx].insn_off;
+
+ bpf_prog->aux->xlated_to_jit[off].off = proglen;
+ bpf_prog->aux->xlated_to_jit[off].len = ilen;
+ }
}
proglen += ilen;
addrs[i] = proglen;
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 4def3dde35f6..bdd6be718e82 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
};
/* an array of original indexes for all xlated instructions */
u32 *orig_idx;
+ /* for every xlated instruction point to all generated jited
+ * instructions, if allocated
+ */
+ struct {
+ u32 off; /* local offset in the jitted code */
+ u32 len; /* the total len of generated jit code */
+ } *xlated_to_jit;
};
struct bpf_prog {
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index b929523444b0..c874f354c290 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -6493,6 +6493,11 @@ struct sk_reuseport_md {
#define BPF_TAG_SIZE 8
+struct bpf_xlated_to_jit {
+ __u32 off;
+ __u32 len;
+};
+
struct bpf_prog_info {
__u32 type;
__u32 id;
@@ -6535,6 +6540,8 @@ struct bpf_prog_info {
__u32 attach_btf_id;
__u32 orig_idx_len;
__aligned_u64 orig_idx;
+ __u32 xlated_to_jit_len;
+ __aligned_u64 xlated_to_jit;
} __attribute__((aligned(8)));
struct bpf_map_info {
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index f0086925b810..8e99c1563a7f 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -493,6 +493,26 @@ static int bpf_prog_realloc_orig_idx(struct bpf_prog *prog, u32 off, u32 patch_l
return 0;
}
+static void adjust_func_info(struct bpf_prog *prog, u32 off, u32 insn_delta)
+{
+ int i;
+
+ if (insn_delta == 0)
+ return;
+
+ for (i = 0; i < prog->aux->func_info_cnt; i++) {
+ if (prog->aux->func_info[i].insn_off <= off)
+ continue;
+ prog->aux->func_info[i].insn_off += insn_delta;
+ }
+}
+
+static void bpf_prog_adj_orig_idx_after_remove(struct bpf_prog *prog, u32 off, u32 len)
+{
+ memmove(prog->aux->orig_idx + off, prog->aux->orig_idx + off + len,
+ sizeof(*prog->aux->orig_idx) * (prog->len - off));
+}
+
struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
const struct bpf_insn *patch, u32 len)
{
@@ -554,6 +574,7 @@ struct bpf_prog *bpf_patch_insn_single(struct bpf_prog *prog, u32 off,
BUG_ON(bpf_adj_branches(prog_adj, off, off + 1, off + len, false));
bpf_adj_linfo(prog_adj, off, insn_delta);
+ adjust_func_info(prog_adj, off, insn_delta);
return prog_adj;
}
@@ -574,6 +595,8 @@ int bpf_remove_insns(struct bpf_prog *prog, u32 off, u32 cnt)
if (err)
return err;
+ bpf_prog_adj_orig_idx_after_remove(prog, off, cnt);
+
return 0;
}
@@ -2807,6 +2830,7 @@ static void bpf_prog_free_deferred(struct work_struct *work)
bpf_jit_free(aux->prog);
}
kfree(aux->orig_idx);
+ kfree(aux->xlated_to_jit);
}
void bpf_prog_free(struct bpf_prog *fp)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 172bf8d3aef2..36b8fdcfba75 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -4571,6 +4571,31 @@ static int bpf_prog_get_info_by_fd(struct file *file,
return -EFAULT;
}
+ ulen = info.xlated_to_jit_len;
+ if (prog->aux->xlated_to_jit)
+ info.xlated_to_jit_len = prog->len * sizeof(struct bpf_xlated_to_jit);
+ else
+ info.xlated_to_jit_len = 0;
+ if (info.xlated_to_jit_len && ulen) {
+ struct bpf_xlated_to_jit *xlated_to_jit;
+ int i;
+
+ xlated_to_jit = kzalloc(info.xlated_to_jit_len, GFP_KERNEL);
+ if (!xlated_to_jit)
+ return -ENOMEM;
+ for (i = 0; i < prog->len; i++) {
+ xlated_to_jit[i].off = prog->aux->xlated_to_jit[i].off;
+ xlated_to_jit[i].len = prog->aux->xlated_to_jit[i].len;
+ }
+ if (copy_to_user(u64_to_user_ptr(info.xlated_to_jit),
+ xlated_to_jit,
+ min_t(u32, info.xlated_to_jit_len, ulen))) {
+ kfree(xlated_to_jit);
+ return -EFAULT;
+ }
+ kfree(xlated_to_jit);
+ }
+
if (bpf_prog_is_offloaded(prog->aux)) {
err = bpf_prog_offload_info_fill(&info, prog);
if (err)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2dc48f88f43c..270dc0a26d03 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -18974,6 +18974,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
func[i]->aux->exception_cb = env->subprog_info[i].is_exception_cb;
if (!i)
func[i]->aux->exception_boundary = env->seen_exception;
+ func[i]->aux->xlated_to_jit = prog->aux->xlated_to_jit;
func[i] = bpf_int_jit_compile(func[i]);
if (!func[i]->jited) {
err = -ENOTSUPP;
@@ -20832,6 +20833,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
int len, ret = -EINVAL, err;
u32 log_true_size;
bool is_priv;
+ u32 size;
/* no program is valid */
if (ARRAY_SIZE(bpf_verifier_ops) == 0)
@@ -20981,6 +20983,13 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
: false;
}
+ if (ret == 0) {
+ size = array_size(sizeof(*env->prog->aux->xlated_to_jit), env->prog->len);
+ env->prog->aux->xlated_to_jit = kzalloc(size, GFP_KERNEL);
+ if (!env->prog->aux->xlated_to_jit)
+ ret = -ENOMEM;
+ }
+
if (ret == 0)
ret = fixup_call_args(env);
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index b929523444b0..c874f354c290 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -6493,6 +6493,11 @@ struct sk_reuseport_md {
#define BPF_TAG_SIZE 8
+struct bpf_xlated_to_jit {
+ __u32 off;
+ __u32 len;
+};
+
struct bpf_prog_info {
__u32 type;
__u32 id;
@@ -6535,6 +6540,8 @@ struct bpf_prog_info {
__u32 attach_btf_id;
__u32 orig_idx_len;
__aligned_u64 orig_idx;
+ __u32 xlated_to_jit_len;
+ __aligned_u64 xlated_to_jit;
} __attribute__((aligned(8)));
struct bpf_map_info {
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-02 16:28 ` [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns Anton Protopopov
@ 2024-02-06 1:09 ` Alexei Starovoitov
2024-02-06 10:02 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-02-06 1:09 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index 4def3dde35f6..bdd6be718e82 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> };
> /* an array of original indexes for all xlated instructions */
> u32 *orig_idx;
> + /* for every xlated instruction point to all generated jited
> + * instructions, if allocated
> + */
> + struct {
> + u32 off; /* local offset in the jitted code */
> + u32 len; /* the total len of generated jit code */
> + } *xlated_to_jit;
Simply put Nack to this approach.
Patches 2 and 3 add an extreme amount of memory overhead.
As we discussed during office hours we need a "pointer to insn" concept
aka "index on insn".
The verifier would need to track that such things exist and adjust
indices of insns when patching affects those indices.
For every static branch there will be one such "pointer to insn".
Different algorithms can be used to keep them correct.
The simplest 'lets iterate over all such pointers and update them'
during patch_insn() may even be ok to start.
Such "pointer to insn" won't add any memory overhead.
When patch+jit is done all such "pointer to insn" are fixed value.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-06 1:09 ` Alexei Starovoitov
@ 2024-02-06 10:02 ` Anton Protopopov
2024-02-07 2:26 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-02-06 10:02 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index 4def3dde35f6..bdd6be718e82 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > };
> > /* an array of original indexes for all xlated instructions */
> > u32 *orig_idx;
> > + /* for every xlated instruction point to all generated jited
> > + * instructions, if allocated
> > + */
> > + struct {
> > + u32 off; /* local offset in the jitted code */
> > + u32 len; /* the total len of generated jit code */
> > + } *xlated_to_jit;
>
> Simply put Nack to this approach.
>
> Patches 2 and 3 add an extreme amount of memory overhead.
>
> As we discussed during office hours we need a "pointer to insn" concept
> aka "index on insn".
> The verifier would need to track that such things exist and adjust
> indices of insns when patching affects those indices.
>
> For every static branch there will be one such "pointer to insn".
> Different algorithms can be used to keep them correct.
> The simplest 'lets iterate over all such pointers and update them'
> during patch_insn() may even be ok to start.
>
> Such "pointer to insn" won't add any memory overhead.
> When patch+jit is done all such "pointer to insn" are fixed value.
Ok, thanks for looking, this makes sense.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-06 10:02 ` Anton Protopopov
@ 2024-02-07 2:26 ` Alexei Starovoitov
2024-02-08 11:05 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-02-07 2:26 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > index 4def3dde35f6..bdd6be718e82 100644
> > > --- a/include/linux/bpf.h
> > > +++ b/include/linux/bpf.h
> > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > };
> > > /* an array of original indexes for all xlated instructions */
> > > u32 *orig_idx;
> > > + /* for every xlated instruction point to all generated jited
> > > + * instructions, if allocated
> > > + */
> > > + struct {
> > > + u32 off; /* local offset in the jitted code */
> > > + u32 len; /* the total len of generated jit code */
> > > + } *xlated_to_jit;
> >
> > Simply put Nack to this approach.
> >
> > Patches 2 and 3 add an extreme amount of memory overhead.
> >
> > As we discussed during office hours we need a "pointer to insn" concept
> > aka "index on insn".
> > The verifier would need to track that such things exist and adjust
> > indices of insns when patching affects those indices.
> >
> > For every static branch there will be one such "pointer to insn".
> > Different algorithms can be used to keep them correct.
> > The simplest 'lets iterate over all such pointers and update them'
> > during patch_insn() may even be ok to start.
> >
> > Such "pointer to insn" won't add any memory overhead.
> > When patch+jit is done all such "pointer to insn" are fixed value.
>
> Ok, thanks for looking, this makes sense.
Before jumping into coding I think it would be good to discuss
the design first.
I'm thinking such "address of insn" will be similar to
existing "address of subprog",
which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
"address of insn" would be a bit more involved to track
during JIT and likely trivial during insn patching,
since we're already doing imm adjustment for pseudo_func.
So that part of design is straightforward.
Implementation in the kernel and libbpf can copy paste from pseudo_func too.
The question is whether such "address of insn" should be allowed
in the data section. If so, we need to brainstorm how to
do it cleanly.
We had various hacks for similar things in the past. Like prog_array.
Let's not repeat such mistakes.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-07 2:26 ` Alexei Starovoitov
@ 2024-02-08 11:05 ` Anton Protopopov
2024-02-15 6:48 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-02-08 11:05 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > >
> > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > --- a/include/linux/bpf.h
> > > > +++ b/include/linux/bpf.h
> > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > };
> > > > /* an array of original indexes for all xlated instructions */
> > > > u32 *orig_idx;
> > > > + /* for every xlated instruction point to all generated jited
> > > > + * instructions, if allocated
> > > > + */
> > > > + struct {
> > > > + u32 off; /* local offset in the jitted code */
> > > > + u32 len; /* the total len of generated jit code */
> > > > + } *xlated_to_jit;
> > >
> > > Simply put Nack to this approach.
> > >
> > > Patches 2 and 3 add an extreme amount of memory overhead.
> > >
> > > As we discussed during office hours we need a "pointer to insn" concept
> > > aka "index on insn".
> > > The verifier would need to track that such things exist and adjust
> > > indices of insns when patching affects those indices.
> > >
> > > For every static branch there will be one such "pointer to insn".
> > > Different algorithms can be used to keep them correct.
> > > The simplest 'lets iterate over all such pointers and update them'
> > > during patch_insn() may even be ok to start.
> > >
> > > Such "pointer to insn" won't add any memory overhead.
> > > When patch+jit is done all such "pointer to insn" are fixed value.
> >
> > Ok, thanks for looking, this makes sense.
>
> Before jumping into coding I think it would be good to discuss
> the design first.
> I'm thinking such "address of insn" will be similar to
> existing "address of subprog",
> which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> "address of insn" would be a bit more involved to track
> during JIT and likely trivial during insn patching,
> since we're already doing imm adjustment for pseudo_func.
> So that part of design is straightforward.
> Implementation in the kernel and libbpf can copy paste from pseudo_func too.
To implement the "primitive version" of static branches, where the
only API is `static_branch_update(xlated off, on/off)` the only
requirement is to build `xlated -> jitted` mapping (which is done
in JIT, after the verification). This can be done in a simplified
version of this patch, without xlated->orig mapping and with
xlated->jit mapping only done to gotol_or_nop instructions.
The "address of insn" appears when we want to provide a more
higher-level API when some object (in user-space or in kernel) keeps
track of one or more gotol_or_nop instructions so that after the
program load this controlling object has a list of xlated offsets.
But this would be a follow-up to the initial static branches patch.
> The question is whether such "address of insn" should be allowed
> in the data section. If so, we need to brainstorm how to
> do it cleanly.
> We had various hacks for similar things in the past. Like prog_array.
> Let's not repeat such mistakes.
So, data section is required for implementing jump tables? Like,
to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
corresponding "ptr to insn" object for every occurence of &&label,
which will be adjusted during verification.
Looks to me like this one doesn't require any more API than specifying
a list of &&label occurencies on program load.
For "static keys" though (a feature on top of this patch series) we
need to have access to the corresponding set of adjusted pointers.
Isn't this enough to add something like an array of
struct insn_ptr {
u32 type; /* LABEL, STATIC_BRANCH,... */
u32 insn_off; /* original offset on load */
union {
struct label {...};
struct st_branch { u32 key_id, ..};
};
};
to load attrs and then get the xlated list after the program is
loaded? Then no new maps/APIs are needed and this can be extended.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-08 11:05 ` Anton Protopopov
@ 2024-02-15 6:48 ` Alexei Starovoitov
2024-02-16 13:57 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-02-15 6:48 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > >
> > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > --- a/include/linux/bpf.h
> > > > > +++ b/include/linux/bpf.h
> > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > };
> > > > > /* an array of original indexes for all xlated instructions */
> > > > > u32 *orig_idx;
> > > > > + /* for every xlated instruction point to all generated jited
> > > > > + * instructions, if allocated
> > > > > + */
> > > > > + struct {
> > > > > + u32 off; /* local offset in the jitted code */
> > > > > + u32 len; /* the total len of generated jit code */
> > > > > + } *xlated_to_jit;
> > > >
> > > > Simply put Nack to this approach.
> > > >
> > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > >
> > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > aka "index on insn".
> > > > The verifier would need to track that such things exist and adjust
> > > > indices of insns when patching affects those indices.
> > > >
> > > > For every static branch there will be one such "pointer to insn".
> > > > Different algorithms can be used to keep them correct.
> > > > The simplest 'lets iterate over all such pointers and update them'
> > > > during patch_insn() may even be ok to start.
> > > >
> > > > Such "pointer to insn" won't add any memory overhead.
> > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > >
> > > Ok, thanks for looking, this makes sense.
> >
> > Before jumping into coding I think it would be good to discuss
> > the design first.
> > I'm thinking such "address of insn" will be similar to
> > existing "address of subprog",
> > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > "address of insn" would be a bit more involved to track
> > during JIT and likely trivial during insn patching,
> > since we're already doing imm adjustment for pseudo_func.
> > So that part of design is straightforward.
> > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
>
> To implement the "primitive version" of static branches, where the
> only API is `static_branch_update(xlated off, on/off)` the only
> requirement is to build `xlated -> jitted` mapping (which is done
> in JIT, after the verification). This can be done in a simplified
> version of this patch, without xlated->orig mapping and with
> xlated->jit mapping only done to gotol_or_nop instructions.
yes. The array of insn->jit_addr sized with as many goto_or_nop-s
the prog will work for user space to flip them, but...
> The "address of insn" appears when we want to provide a more
> higher-level API when some object (in user-space or in kernel) keeps
> track of one or more gotol_or_nop instructions so that after the
> program load this controlling object has a list of xlated offsets.
> But this would be a follow-up to the initial static branches patch.
this won't work as a follow up,
since such an array won't work for bpf prog that wants to flip branches.
There is nothing that associates static_branch name/id with
particular goto_or_nop.
There could be a kfunc that bpf prog calls, but it can only
flip all of such insns in the prog.
Unless we start encoding a special id inside goto_or_nop or other hacks.
> > The question is whether such "address of insn" should be allowed
> > in the data section. If so, we need to brainstorm how to
> > do it cleanly.
> > We had various hacks for similar things in the past. Like prog_array.
> > Let's not repeat such mistakes.
>
> So, data section is required for implementing jump tables? Like,
> to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> corresponding "ptr to insn" object for every occurence of &&label,
> which will be adjusted during verification.
> Looks to me like this one doesn't require any more API than specifying
> a list of &&label occurencies on program load.
>
> For "static keys" though (a feature on top of this patch series) we
> need to have access to the corresponding set of adjusted pointers.
>
> Isn't this enough to add something like an array of
>
> struct insn_ptr {
> u32 type; /* LABEL, STATIC_BRANCH,... */
> u32 insn_off; /* original offset on load */
> union {
> struct label {...};
> struct st_branch { u32 key_id, ..};
> };
> };
which I don't like because it hard codes static_branch needs into
insn->jit_addr association.
"address of insn" should be an individual building block without
bolted on parts.
A data section with a set of such "address of insn"
can be a description of one static_branch.
There will be different ways to combine such building blocks.
For example:
static_branch(foo) can emit goto_or_nop into bpf code
and add "address of insn" into a section '.insn_addrs.foo".
This section is what libbpf and bpf prog will recognize as a set
of "address of insn" that can be passed into static_branch_update kfunc
or static_branch_update sys_bpf command.
The question is whether we need a new map type (array derivative)
to hold a set of "address of insn" or it can be a part of an existing
global data array.
A new map type is easier to reason about.
Notice how such a new map type is not a map type of static branches.
It's not a map type of goto_or_nop instructions either.
At load time libbpf can populate this array with indices of insns
that the verifier and JIT need to track. Once JITed the array is readonly
for bpf prog and for user space.
With that mechanism compilers can generate a proper switch() jmp table.
llvm work can be a follow up, of course, but the whole design needs
to be thought through to cover all use cases.
To summarize, here's what I'm proposing:
- PTR_TO_INSN verifier regtype that can be passed to static_branch_update kfunc
- new map type (array) that holds objects that are PTR_TO_INSN for the verifier
libbpf populates this array with indices of insn it wants to track.
bpf prog needs to "use" this array, so prog/map association is built.
- verifier/JIT update each PTR_TO_INSN during transformations.
- static_branch(foo) macro emits goto_or_nop insn and adds 8 bytes
into ".insn_addrs.foo" section with an ELF relocation that
libbpf will convert into index.
When compilers implement jmptables for switch(key) they will generate
".insn_addrs.uniq_suffix" sections and emit
rX = ld_imm64 that_section
rX += switch_key
rY = *(u64 *)rX
jmpx rY
The verifier would need to do push_stack() for this indirect jmp insn
as many times as there are elements in ".insn_addrs.uniq_suffix" array.
And similar for indirect calls.
That section becomes an array of pointers to functions.
We can make it more flexible for indirect callx by
storing BTF func proto and allowing global subprogs with same proto
to match as safe call targets.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-15 6:48 ` Alexei Starovoitov
@ 2024-02-16 13:57 ` Anton Protopopov
2024-02-21 1:09 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-02-16 13:57 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > >
> > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > >
> > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > --- a/include/linux/bpf.h
> > > > > > +++ b/include/linux/bpf.h
> > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > };
> > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > u32 *orig_idx;
> > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > + * instructions, if allocated
> > > > > > + */
> > > > > > + struct {
> > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > + } *xlated_to_jit;
> > > > >
> > > > > Simply put Nack to this approach.
> > > > >
> > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > >
> > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > aka "index on insn".
> > > > > The verifier would need to track that such things exist and adjust
> > > > > indices of insns when patching affects those indices.
> > > > >
> > > > > For every static branch there will be one such "pointer to insn".
> > > > > Different algorithms can be used to keep them correct.
> > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > during patch_insn() may even be ok to start.
> > > > >
> > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > >
> > > > Ok, thanks for looking, this makes sense.
> > >
> > > Before jumping into coding I think it would be good to discuss
> > > the design first.
> > > I'm thinking such "address of insn" will be similar to
> > > existing "address of subprog",
> > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > "address of insn" would be a bit more involved to track
> > > during JIT and likely trivial during insn patching,
> > > since we're already doing imm adjustment for pseudo_func.
> > > So that part of design is straightforward.
> > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> >
> > To implement the "primitive version" of static branches, where the
> > only API is `static_branch_update(xlated off, on/off)` the only
> > requirement is to build `xlated -> jitted` mapping (which is done
> > in JIT, after the verification). This can be done in a simplified
> > version of this patch, without xlated->orig mapping and with
> > xlated->jit mapping only done to gotol_or_nop instructions.
>
> yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> the prog will work for user space to flip them, but...
>
> > The "address of insn" appears when we want to provide a more
> > higher-level API when some object (in user-space or in kernel) keeps
> > track of one or more gotol_or_nop instructions so that after the
> > program load this controlling object has a list of xlated offsets.
> > But this would be a follow-up to the initial static branches patch.
>
> this won't work as a follow up,
> since such an array won't work for bpf prog that wants to flip branches.
> There is nothing that associates static_branch name/id with
> particular goto_or_nop.
> There could be a kfunc that bpf prog calls, but it can only
> flip all of such insns in the prog.
> Unless we start encoding a special id inside goto_or_nop or other hacks.
>
> > > The question is whether such "address of insn" should be allowed
> > > in the data section. If so, we need to brainstorm how to
> > > do it cleanly.
> > > We had various hacks for similar things in the past. Like prog_array.
> > > Let's not repeat such mistakes.
> >
> > So, data section is required for implementing jump tables? Like,
> > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > corresponding "ptr to insn" object for every occurence of &&label,
> > which will be adjusted during verification.
> > Looks to me like this one doesn't require any more API than specifying
> > a list of &&label occurencies on program load.
> >
> > For "static keys" though (a feature on top of this patch series) we
> > need to have access to the corresponding set of adjusted pointers.
> >
> > Isn't this enough to add something like an array of
> >
> > struct insn_ptr {
> > u32 type; /* LABEL, STATIC_BRANCH,... */
> > u32 insn_off; /* original offset on load */
> > union {
> > struct label {...};
> > struct st_branch { u32 key_id, ..};
> > };
> > };
>
> which I don't like because it hard codes static_branch needs into
> insn->jit_addr association.
> "address of insn" should be an individual building block without
> bolted on parts.
>
> A data section with a set of such "address of insn"
> can be a description of one static_branch.
> There will be different ways to combine such building blocks.
> For example:
> static_branch(foo) can emit goto_or_nop into bpf code
> and add "address of insn" into a section '.insn_addrs.foo".
> This section is what libbpf and bpf prog will recognize as a set
> of "address of insn" that can be passed into static_branch_update kfunc
> or static_branch_update sys_bpf command.
> The question is whether we need a new map type (array derivative)
> to hold a set of "address of insn" or it can be a part of an existing
> global data array.
> A new map type is easier to reason about.
> Notice how such a new map type is not a map type of static branches.
> It's not a map type of goto_or_nop instructions either.
>
> At load time libbpf can populate this array with indices of insns
> that the verifier and JIT need to track. Once JITed the array is readonly
> for bpf prog and for user space.
So this will be a map per .insn_addrs.X section (where X is key or
a pre-defined suffix for jump tables or indirect calls). And to tell
the verifier about these maps we will need to pass an array of
struct {
u32 map_fd;
u32 type; /* static key, jump table, etc. */
}
on program load. Is this correct?
> With that mechanism compilers can generate a proper switch() jmp table.
> llvm work can be a follow up, of course, but the whole design needs
> to be thought through to cover all use cases.
>
> To summarize, here's what I'm proposing:
> - PTR_TO_INSN verifier regtype that can be passed to static_branch_update kfunc
If we have a set of pointers to jump instructions, generated from
static_branch(foo) for same foo, then this makes more sense to
provide a
static_branch_update(foo)
(where foo is substituted by libbpf with a map fd of .insn_addrs.foo
on load). The same for userspace:
bpf(STATIC_BRANCH_UPDATE, .attrs={.map_fd=foo})
> - new map type (array) that holds objects that are PTR_TO_INSN for the verifier
> libbpf populates this array with indices of insn it wants to track.
> bpf prog needs to "use" this array, so prog/map association is built.
> - verifier/JIT update each PTR_TO_INSN during transformations.
> - static_branch(foo) macro emits goto_or_nop insn and adds 8 bytes
> into ".insn_addrs.foo" section with an ELF relocation that
> libbpf will convert into index.
>
> When compilers implement jmptables for switch(key) they will generate
> ".insn_addrs.uniq_suffix" sections and emit
> rX = ld_imm64 that_section
> rX += switch_key
> rY = *(u64 *)rX
> jmpx rY
What are the types for rX and rY? I thought that we will need to do
smth like
rX = .insn_addrs.uniq_suffix[switch_key] /* rX has type PTR_TO_INSN */
...
jmpx rX
this can be done if for switch cases (or any other goto *label alike) we generate
rX = map_lookup_elem(.insn_addrs.uniq_suffix, index)
jmpx rX
> The verifier would need to do push_stack() for this indirect jmp insn
> as many times as there are elements in ".insn_addrs.uniq_suffix" array.
>
> And similar for indirect calls.
> That section becomes an array of pointers to functions.
> We can make it more flexible for indirect callx by
> storing BTF func proto and allowing global subprogs with same proto
> to match as safe call targets.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-16 13:57 ` Anton Protopopov
@ 2024-02-21 1:09 ` Alexei Starovoitov
2024-03-06 10:44 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-02-21 1:09 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > >
> > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > >
> > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > --- a/include/linux/bpf.h
> > > > > > > +++ b/include/linux/bpf.h
> > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > };
> > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > u32 *orig_idx;
> > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > + * instructions, if allocated
> > > > > > > + */
> > > > > > > + struct {
> > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > + } *xlated_to_jit;
> > > > > >
> > > > > > Simply put Nack to this approach.
> > > > > >
> > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > >
> > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > aka "index on insn".
> > > > > > The verifier would need to track that such things exist and adjust
> > > > > > indices of insns when patching affects those indices.
> > > > > >
> > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > Different algorithms can be used to keep them correct.
> > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > during patch_insn() may even be ok to start.
> > > > > >
> > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > >
> > > > > Ok, thanks for looking, this makes sense.
> > > >
> > > > Before jumping into coding I think it would be good to discuss
> > > > the design first.
> > > > I'm thinking such "address of insn" will be similar to
> > > > existing "address of subprog",
> > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > "address of insn" would be a bit more involved to track
> > > > during JIT and likely trivial during insn patching,
> > > > since we're already doing imm adjustment for pseudo_func.
> > > > So that part of design is straightforward.
> > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > >
> > > To implement the "primitive version" of static branches, where the
> > > only API is `static_branch_update(xlated off, on/off)` the only
> > > requirement is to build `xlated -> jitted` mapping (which is done
> > > in JIT, after the verification). This can be done in a simplified
> > > version of this patch, without xlated->orig mapping and with
> > > xlated->jit mapping only done to gotol_or_nop instructions.
> >
> > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > the prog will work for user space to flip them, but...
> >
> > > The "address of insn" appears when we want to provide a more
> > > higher-level API when some object (in user-space or in kernel) keeps
> > > track of one or more gotol_or_nop instructions so that after the
> > > program load this controlling object has a list of xlated offsets.
> > > But this would be a follow-up to the initial static branches patch.
> >
> > this won't work as a follow up,
> > since such an array won't work for bpf prog that wants to flip branches.
> > There is nothing that associates static_branch name/id with
> > particular goto_or_nop.
> > There could be a kfunc that bpf prog calls, but it can only
> > flip all of such insns in the prog.
> > Unless we start encoding a special id inside goto_or_nop or other hacks.
> >
> > > > The question is whether such "address of insn" should be allowed
> > > > in the data section. If so, we need to brainstorm how to
> > > > do it cleanly.
> > > > We had various hacks for similar things in the past. Like prog_array.
> > > > Let's not repeat such mistakes.
> > >
> > > So, data section is required for implementing jump tables? Like,
> > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > corresponding "ptr to insn" object for every occurence of &&label,
> > > which will be adjusted during verification.
> > > Looks to me like this one doesn't require any more API than specifying
> > > a list of &&label occurencies on program load.
> > >
> > > For "static keys" though (a feature on top of this patch series) we
> > > need to have access to the corresponding set of adjusted pointers.
> > >
> > > Isn't this enough to add something like an array of
> > >
> > > struct insn_ptr {
> > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > u32 insn_off; /* original offset on load */
> > > union {
> > > struct label {...};
> > > struct st_branch { u32 key_id, ..};
> > > };
> > > };
> >
> > which I don't like because it hard codes static_branch needs into
> > insn->jit_addr association.
> > "address of insn" should be an individual building block without
> > bolted on parts.
> >
> > A data section with a set of such "address of insn"
> > can be a description of one static_branch.
> > There will be different ways to combine such building blocks.
> > For example:
> > static_branch(foo) can emit goto_or_nop into bpf code
> > and add "address of insn" into a section '.insn_addrs.foo".
> > This section is what libbpf and bpf prog will recognize as a set
> > of "address of insn" that can be passed into static_branch_update kfunc
> > or static_branch_update sys_bpf command.
> > The question is whether we need a new map type (array derivative)
> > to hold a set of "address of insn" or it can be a part of an existing
> > global data array.
> > A new map type is easier to reason about.
> > Notice how such a new map type is not a map type of static branches.
> > It's not a map type of goto_or_nop instructions either.
> >
> > At load time libbpf can populate this array with indices of insns
> > that the verifier and JIT need to track. Once JITed the array is readonly
> > for bpf prog and for user space.
>
> So this will be a map per .insn_addrs.X section (where X is key or
> a pre-defined suffix for jump tables or indirect calls). And to tell
> the verifier about these maps we will need to pass an array of
>
> struct {
> u32 map_fd;
> u32 type; /* static key, jump table, etc. */
> }
>
> on program load. Is this correct?
Probably not.
Since we're going with a new map type (at least for the sake of this
discussion) it shouldn't need a new way to tell the verifier about it.
If .insn_addrs.jmp_table_A was a section generated for switch() statement
by llvm it will be created as a map by libbpf,
and there will be an ld_imm64 insn generated by llvm that points
to that map.
libbpf will populate ld_imm64 insn with map_fd, just like it does
for global data.
> > With that mechanism compilers can generate a proper switch() jmp table.
> > llvm work can be a follow up, of course, but the whole design needs
> > to be thought through to cover all use cases.
> >
> > To summarize, here's what I'm proposing:
> > - PTR_TO_INSN verifier regtype that can be passed to static_branch_update kfunc
>
> If we have a set of pointers to jump instructions, generated from
> static_branch(foo) for same foo, then this makes more sense to
> provide a
>
> static_branch_update(foo)
For bpf_static_branch_update(&foo) kfunc there will be another
ld_imm64 insn that points to that map.
No need for new interface here either.
> (where foo is substituted by libbpf with a map fd of .insn_addrs.foo
> on load). The same for userspace:
>
> bpf(STATIC_BRANCH_UPDATE, .attrs={.map_fd=foo})
but for libbpf it would be nice to have a helper that knows
this .insn_addrs section details.
> > - new map type (array) that holds objects that are PTR_TO_INSN for the verifier
> > libbpf populates this array with indices of insn it wants to track.
> > bpf prog needs to "use" this array, so prog/map association is built.
> > - verifier/JIT update each PTR_TO_INSN during transformations.
> > - static_branch(foo) macro emits goto_or_nop insn and adds 8 bytes
> > into ".insn_addrs.foo" section with an ELF relocation that
> > libbpf will convert into index.
> >
> > When compilers implement jmptables for switch(key) they will generate
> > ".insn_addrs.uniq_suffix" sections and emit
> > rX = ld_imm64 that_section
> > rX += switch_key
> > rY = *(u64 *)rX
> > jmpx rY
>
> What are the types for rX and rY? I thought that we will need to do
> smth like
>
> rX = .insn_addrs.uniq_suffix[switch_key] /* rX has type PTR_TO_INSN */
> ...
> jmpx rX
right. That ".insn_addrs.uniq_suffix[switch_key]" C syntax is exactly:
rX = ld_imm64 that_section
rX += switch_key
in assembly.
>
> this can be done if for switch cases (or any other goto *label alike) we generate
>
> rX = map_lookup_elem(.insn_addrs.uniq_suffix, index)
> jmpx rX
No need for function calls.
rX = ld_imm64 that_section
rX += switch_key
should work.
It works for global variables already, like:
rX = ld_imm64 global_data_array_map
rX += 8 // address of 2nd u64 in global data
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-02-21 1:09 ` Alexei Starovoitov
@ 2024-03-06 10:44 ` Anton Protopopov
2024-03-14 1:56 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-03-06 10:44 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Tue, Feb 20, 2024 at 05:09:36PM -0800, Alexei Starovoitov wrote:
> On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > >
> > > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > >
> > > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > >
> > > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > > --- a/include/linux/bpf.h
> > > > > > > > +++ b/include/linux/bpf.h
> > > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > > };
> > > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > > u32 *orig_idx;
> > > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > > + * instructions, if allocated
> > > > > > > > + */
> > > > > > > > + struct {
> > > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > > + } *xlated_to_jit;
> > > > > > >
> > > > > > > Simply put Nack to this approach.
> > > > > > >
> > > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > > >
> > > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > > aka "index on insn".
> > > > > > > The verifier would need to track that such things exist and adjust
> > > > > > > indices of insns when patching affects those indices.
> > > > > > >
> > > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > > Different algorithms can be used to keep them correct.
> > > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > > during patch_insn() may even be ok to start.
> > > > > > >
> > > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > > >
> > > > > > Ok, thanks for looking, this makes sense.
> > > > >
> > > > > Before jumping into coding I think it would be good to discuss
> > > > > the design first.
> > > > > I'm thinking such "address of insn" will be similar to
> > > > > existing "address of subprog",
> > > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > > "address of insn" would be a bit more involved to track
> > > > > during JIT and likely trivial during insn patching,
> > > > > since we're already doing imm adjustment for pseudo_func.
> > > > > So that part of design is straightforward.
> > > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > > >
> > > > To implement the "primitive version" of static branches, where the
> > > > only API is `static_branch_update(xlated off, on/off)` the only
> > > > requirement is to build `xlated -> jitted` mapping (which is done
> > > > in JIT, after the verification). This can be done in a simplified
> > > > version of this patch, without xlated->orig mapping and with
> > > > xlated->jit mapping only done to gotol_or_nop instructions.
> > >
> > > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > > the prog will work for user space to flip them, but...
> > >
> > > > The "address of insn" appears when we want to provide a more
> > > > higher-level API when some object (in user-space or in kernel) keeps
> > > > track of one or more gotol_or_nop instructions so that after the
> > > > program load this controlling object has a list of xlated offsets.
> > > > But this would be a follow-up to the initial static branches patch.
> > >
> > > this won't work as a follow up,
> > > since such an array won't work for bpf prog that wants to flip branches.
> > > There is nothing that associates static_branch name/id with
> > > particular goto_or_nop.
> > > There could be a kfunc that bpf prog calls, but it can only
> > > flip all of such insns in the prog.
> > > Unless we start encoding a special id inside goto_or_nop or other hacks.
> > >
> > > > > The question is whether such "address of insn" should be allowed
> > > > > in the data section. If so, we need to brainstorm how to
> > > > > do it cleanly.
> > > > > We had various hacks for similar things in the past. Like prog_array.
> > > > > Let's not repeat such mistakes.
> > > >
> > > > So, data section is required for implementing jump tables? Like,
> > > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > > corresponding "ptr to insn" object for every occurence of &&label,
> > > > which will be adjusted during verification.
> > > > Looks to me like this one doesn't require any more API than specifying
> > > > a list of &&label occurencies on program load.
> > > >
> > > > For "static keys" though (a feature on top of this patch series) we
> > > > need to have access to the corresponding set of adjusted pointers.
> > > >
> > > > Isn't this enough to add something like an array of
> > > >
> > > > struct insn_ptr {
> > > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > > u32 insn_off; /* original offset on load */
> > > > union {
> > > > struct label {...};
> > > > struct st_branch { u32 key_id, ..};
> > > > };
> > > > };
> > >
> > > which I don't like because it hard codes static_branch needs into
> > > insn->jit_addr association.
> > > "address of insn" should be an individual building block without
> > > bolted on parts.
> > >
> > > A data section with a set of such "address of insn"
> > > can be a description of one static_branch.
> > > There will be different ways to combine such building blocks.
> > > For example:
> > > static_branch(foo) can emit goto_or_nop into bpf code
> > > and add "address of insn" into a section '.insn_addrs.foo".
> > > This section is what libbpf and bpf prog will recognize as a set
> > > of "address of insn" that can be passed into static_branch_update kfunc
> > > or static_branch_update sys_bpf command.
> > > The question is whether we need a new map type (array derivative)
> > > to hold a set of "address of insn" or it can be a part of an existing
> > > global data array.
> > > A new map type is easier to reason about.
> > > Notice how such a new map type is not a map type of static branches.
> > > It's not a map type of goto_or_nop instructions either.
> > >
> > > At load time libbpf can populate this array with indices of insns
> > > that the verifier and JIT need to track. Once JITed the array is readonly
> > > for bpf prog and for user space.
> >
> > So this will be a map per .insn_addrs.X section (where X is key or
> > a pre-defined suffix for jump tables or indirect calls). And to tell
> > the verifier about these maps we will need to pass an array of
> >
> > struct {
> > u32 map_fd;
> > u32 type; /* static key, jump table, etc. */
> > }
> >
> > on program load. Is this correct?
>
>
> Probably not.
> Since we're going with a new map type (at least for the sake of this
> discussion) it shouldn't need a new way to tell the verifier about it.
> If .insn_addrs.jmp_table_A was a section generated for switch() statement
> by llvm it will be created as a map by libbpf,
> and there will be an ld_imm64 insn generated by llvm that points
> to that map.
> libbpf will populate ld_imm64 insn with map_fd, just like it does
> for global data.
I understand how this works for indirect jumps (and for the
bpf_static_branch_update(&foo) kfunc) where we have a ld_imm64 with a
map, however, I am still not sure how this will work for static
branches where we just have a 8 byte JA insn + an index in the
corresponding ".insn_addrs.foo" section. How kernel will know that the
program is using a corresponding map which we create from
".insn_addrs.foo" without specifying this on program load?
(Sorry for replying late, catching up after [simultaneous] pto &
covid.)
> > > With that mechanism compilers can generate a proper switch() jmp table.
> > > llvm work can be a follow up, of course, but the whole design needs
> > > to be thought through to cover all use cases.
> > >
> > > To summarize, here's what I'm proposing:
> > > - PTR_TO_INSN verifier regtype that can be passed to static_branch_update kfunc
> >
> > If we have a set of pointers to jump instructions, generated from
> > static_branch(foo) for same foo, then this makes more sense to
> > provide a
> >
> > static_branch_update(foo)
>
> For bpf_static_branch_update(&foo) kfunc there will be another
> ld_imm64 insn that points to that map.
> No need for new interface here either.
>
> > (where foo is substituted by libbpf with a map fd of .insn_addrs.foo
> > on load). The same for userspace:
> >
> > bpf(STATIC_BRANCH_UPDATE, .attrs={.map_fd=foo})
>
> but for libbpf it would be nice to have a helper that knows
> this .insn_addrs section details.
>
> > > - new map type (array) that holds objects that are PTR_TO_INSN for the verifier
> > > libbpf populates this array with indices of insn it wants to track.
> > > bpf prog needs to "use" this array, so prog/map association is built.
> > > - verifier/JIT update each PTR_TO_INSN during transformations.
> > > - static_branch(foo) macro emits goto_or_nop insn and adds 8 bytes
> > > into ".insn_addrs.foo" section with an ELF relocation that
> > > libbpf will convert into index.
> > >
> > > When compilers implement jmptables for switch(key) they will generate
> > > ".insn_addrs.uniq_suffix" sections and emit
> > > rX = ld_imm64 that_section
> > > rX += switch_key
> > > rY = *(u64 *)rX
> > > jmpx rY
> >
> > What are the types for rX and rY? I thought that we will need to do
> > smth like
> >
> > rX = .insn_addrs.uniq_suffix[switch_key] /* rX has type PTR_TO_INSN */
> > ...
> > jmpx rX
>
> right. That ".insn_addrs.uniq_suffix[switch_key]" C syntax is exactly:
> rX = ld_imm64 that_section
> rX += switch_key
> in assembly.
>
> >
> > this can be done if for switch cases (or any other goto *label alike) we generate
> >
> > rX = map_lookup_elem(.insn_addrs.uniq_suffix, index)
> > jmpx rX
>
> No need for function calls.
> rX = ld_imm64 that_section
> rX += switch_key
>
> should work.
>
> It works for global variables already, like:
> rX = ld_imm64 global_data_array_map
> rX += 8 // address of 2nd u64 in global data
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-06 10:44 ` Anton Protopopov
@ 2024-03-14 1:56 ` Alexei Starovoitov
2024-03-14 9:03 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-03-14 1:56 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Wed, Mar 6, 2024 at 2:51 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On Tue, Feb 20, 2024 at 05:09:36PM -0800, Alexei Starovoitov wrote:
> > On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > > > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > >
> > > > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > >
> > > > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > >
> > > > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > > > --- a/include/linux/bpf.h
> > > > > > > > > +++ b/include/linux/bpf.h
> > > > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > > > };
> > > > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > > > u32 *orig_idx;
> > > > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > > > + * instructions, if allocated
> > > > > > > > > + */
> > > > > > > > > + struct {
> > > > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > > > + } *xlated_to_jit;
> > > > > > > >
> > > > > > > > Simply put Nack to this approach.
> > > > > > > >
> > > > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > > > >
> > > > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > > > aka "index on insn".
> > > > > > > > The verifier would need to track that such things exist and adjust
> > > > > > > > indices of insns when patching affects those indices.
> > > > > > > >
> > > > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > > > Different algorithms can be used to keep them correct.
> > > > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > > > during patch_insn() may even be ok to start.
> > > > > > > >
> > > > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > > > >
> > > > > > > Ok, thanks for looking, this makes sense.
> > > > > >
> > > > > > Before jumping into coding I think it would be good to discuss
> > > > > > the design first.
> > > > > > I'm thinking such "address of insn" will be similar to
> > > > > > existing "address of subprog",
> > > > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > > > "address of insn" would be a bit more involved to track
> > > > > > during JIT and likely trivial during insn patching,
> > > > > > since we're already doing imm adjustment for pseudo_func.
> > > > > > So that part of design is straightforward.
> > > > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > > > >
> > > > > To implement the "primitive version" of static branches, where the
> > > > > only API is `static_branch_update(xlated off, on/off)` the only
> > > > > requirement is to build `xlated -> jitted` mapping (which is done
> > > > > in JIT, after the verification). This can be done in a simplified
> > > > > version of this patch, without xlated->orig mapping and with
> > > > > xlated->jit mapping only done to gotol_or_nop instructions.
> > > >
> > > > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > > > the prog will work for user space to flip them, but...
> > > >
> > > > > The "address of insn" appears when we want to provide a more
> > > > > higher-level API when some object (in user-space or in kernel) keeps
> > > > > track of one or more gotol_or_nop instructions so that after the
> > > > > program load this controlling object has a list of xlated offsets.
> > > > > But this would be a follow-up to the initial static branches patch.
> > > >
> > > > this won't work as a follow up,
> > > > since such an array won't work for bpf prog that wants to flip branches.
> > > > There is nothing that associates static_branch name/id with
> > > > particular goto_or_nop.
> > > > There could be a kfunc that bpf prog calls, but it can only
> > > > flip all of such insns in the prog.
> > > > Unless we start encoding a special id inside goto_or_nop or other hacks.
> > > >
> > > > > > The question is whether such "address of insn" should be allowed
> > > > > > in the data section. If so, we need to brainstorm how to
> > > > > > do it cleanly.
> > > > > > We had various hacks for similar things in the past. Like prog_array.
> > > > > > Let's not repeat such mistakes.
> > > > >
> > > > > So, data section is required for implementing jump tables? Like,
> > > > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > > > corresponding "ptr to insn" object for every occurence of &&label,
> > > > > which will be adjusted during verification.
> > > > > Looks to me like this one doesn't require any more API than specifying
> > > > > a list of &&label occurencies on program load.
> > > > >
> > > > > For "static keys" though (a feature on top of this patch series) we
> > > > > need to have access to the corresponding set of adjusted pointers.
> > > > >
> > > > > Isn't this enough to add something like an array of
> > > > >
> > > > > struct insn_ptr {
> > > > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > > > u32 insn_off; /* original offset on load */
> > > > > union {
> > > > > struct label {...};
> > > > > struct st_branch { u32 key_id, ..};
> > > > > };
> > > > > };
> > > >
> > > > which I don't like because it hard codes static_branch needs into
> > > > insn->jit_addr association.
> > > > "address of insn" should be an individual building block without
> > > > bolted on parts.
> > > >
> > > > A data section with a set of such "address of insn"
> > > > can be a description of one static_branch.
> > > > There will be different ways to combine such building blocks.
> > > > For example:
> > > > static_branch(foo) can emit goto_or_nop into bpf code
> > > > and add "address of insn" into a section '.insn_addrs.foo".
> > > > This section is what libbpf and bpf prog will recognize as a set
> > > > of "address of insn" that can be passed into static_branch_update kfunc
> > > > or static_branch_update sys_bpf command.
> > > > The question is whether we need a new map type (array derivative)
> > > > to hold a set of "address of insn" or it can be a part of an existing
> > > > global data array.
> > > > A new map type is easier to reason about.
> > > > Notice how such a new map type is not a map type of static branches.
> > > > It's not a map type of goto_or_nop instructions either.
> > > >
> > > > At load time libbpf can populate this array with indices of insns
> > > > that the verifier and JIT need to track. Once JITed the array is readonly
> > > > for bpf prog and for user space.
> > >
> > > So this will be a map per .insn_addrs.X section (where X is key or
> > > a pre-defined suffix for jump tables or indirect calls). And to tell
> > > the verifier about these maps we will need to pass an array of
> > >
> > > struct {
> > > u32 map_fd;
> > > u32 type; /* static key, jump table, etc. */
> > > }
> > >
> > > on program load. Is this correct?
> >
> >
> > Probably not.
> > Since we're going with a new map type (at least for the sake of this
> > discussion) it shouldn't need a new way to tell the verifier about it.
> > If .insn_addrs.jmp_table_A was a section generated for switch() statement
> > by llvm it will be created as a map by libbpf,
> > and there will be an ld_imm64 insn generated by llvm that points
> > to that map.
> > libbpf will populate ld_imm64 insn with map_fd, just like it does
> > for global data.
>
> I understand how this works for indirect jumps (and for the
> bpf_static_branch_update(&foo) kfunc) where we have a ld_imm64 with a
> map, however, I am still not sure how this will work for static
> branches where we just have a 8 byte JA insn + an index in the
> corresponding ".insn_addrs.foo" section. How kernel will know that the
> program is using a corresponding map which we create from
> ".insn_addrs.foo" without specifying this on program load?
>
> (Sorry for replying late, catching up after [simultaneous] pto &
> covid.)
sorry. ctx switch takes time.
libbpf can just bpf_prog_bind_map to associate this new map type
of ptr_to_insn with a program.
Or I misunderstood the question?
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 1:56 ` Alexei Starovoitov
@ 2024-03-14 9:03 ` Anton Protopopov
2024-03-14 17:07 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-03-14 9:03 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Wed, Mar 13, 2024 at 06:56:34PM -0700, Alexei Starovoitov wrote:
> On Wed, Mar 6, 2024 at 2:51 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On Tue, Feb 20, 2024 at 05:09:36PM -0800, Alexei Starovoitov wrote:
> > > On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > >
> > > > On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > > > > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > >
> > > > > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > >
> > > > > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > > >
> > > > > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > > > > --- a/include/linux/bpf.h
> > > > > > > > > > +++ b/include/linux/bpf.h
> > > > > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > > > > };
> > > > > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > > > > u32 *orig_idx;
> > > > > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > > > > + * instructions, if allocated
> > > > > > > > > > + */
> > > > > > > > > > + struct {
> > > > > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > > > > + } *xlated_to_jit;
> > > > > > > > >
> > > > > > > > > Simply put Nack to this approach.
> > > > > > > > >
> > > > > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > > > > >
> > > > > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > > > > aka "index on insn".
> > > > > > > > > The verifier would need to track that such things exist and adjust
> > > > > > > > > indices of insns when patching affects those indices.
> > > > > > > > >
> > > > > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > > > > Different algorithms can be used to keep them correct.
> > > > > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > > > > during patch_insn() may even be ok to start.
> > > > > > > > >
> > > > > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > > > > >
> > > > > > > > Ok, thanks for looking, this makes sense.
> > > > > > >
> > > > > > > Before jumping into coding I think it would be good to discuss
> > > > > > > the design first.
> > > > > > > I'm thinking such "address of insn" will be similar to
> > > > > > > existing "address of subprog",
> > > > > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > > > > "address of insn" would be a bit more involved to track
> > > > > > > during JIT and likely trivial during insn patching,
> > > > > > > since we're already doing imm adjustment for pseudo_func.
> > > > > > > So that part of design is straightforward.
> > > > > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > > > > >
> > > > > > To implement the "primitive version" of static branches, where the
> > > > > > only API is `static_branch_update(xlated off, on/off)` the only
> > > > > > requirement is to build `xlated -> jitted` mapping (which is done
> > > > > > in JIT, after the verification). This can be done in a simplified
> > > > > > version of this patch, without xlated->orig mapping and with
> > > > > > xlated->jit mapping only done to gotol_or_nop instructions.
> > > > >
> > > > > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > > > > the prog will work for user space to flip them, but...
> > > > >
> > > > > > The "address of insn" appears when we want to provide a more
> > > > > > higher-level API when some object (in user-space or in kernel) keeps
> > > > > > track of one or more gotol_or_nop instructions so that after the
> > > > > > program load this controlling object has a list of xlated offsets.
> > > > > > But this would be a follow-up to the initial static branches patch.
> > > > >
> > > > > this won't work as a follow up,
> > > > > since such an array won't work for bpf prog that wants to flip branches.
> > > > > There is nothing that associates static_branch name/id with
> > > > > particular goto_or_nop.
> > > > > There could be a kfunc that bpf prog calls, but it can only
> > > > > flip all of such insns in the prog.
> > > > > Unless we start encoding a special id inside goto_or_nop or other hacks.
> > > > >
> > > > > > > The question is whether such "address of insn" should be allowed
> > > > > > > in the data section. If so, we need to brainstorm how to
> > > > > > > do it cleanly.
> > > > > > > We had various hacks for similar things in the past. Like prog_array.
> > > > > > > Let's not repeat such mistakes.
> > > > > >
> > > > > > So, data section is required for implementing jump tables? Like,
> > > > > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > > > > corresponding "ptr to insn" object for every occurence of &&label,
> > > > > > which will be adjusted during verification.
> > > > > > Looks to me like this one doesn't require any more API than specifying
> > > > > > a list of &&label occurencies on program load.
> > > > > >
> > > > > > For "static keys" though (a feature on top of this patch series) we
> > > > > > need to have access to the corresponding set of adjusted pointers.
> > > > > >
> > > > > > Isn't this enough to add something like an array of
> > > > > >
> > > > > > struct insn_ptr {
> > > > > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > > > > u32 insn_off; /* original offset on load */
> > > > > > union {
> > > > > > struct label {...};
> > > > > > struct st_branch { u32 key_id, ..};
> > > > > > };
> > > > > > };
> > > > >
> > > > > which I don't like because it hard codes static_branch needs into
> > > > > insn->jit_addr association.
> > > > > "address of insn" should be an individual building block without
> > > > > bolted on parts.
> > > > >
> > > > > A data section with a set of such "address of insn"
> > > > > can be a description of one static_branch.
> > > > > There will be different ways to combine such building blocks.
> > > > > For example:
> > > > > static_branch(foo) can emit goto_or_nop into bpf code
> > > > > and add "address of insn" into a section '.insn_addrs.foo".
> > > > > This section is what libbpf and bpf prog will recognize as a set
> > > > > of "address of insn" that can be passed into static_branch_update kfunc
> > > > > or static_branch_update sys_bpf command.
> > > > > The question is whether we need a new map type (array derivative)
> > > > > to hold a set of "address of insn" or it can be a part of an existing
> > > > > global data array.
> > > > > A new map type is easier to reason about.
> > > > > Notice how such a new map type is not a map type of static branches.
> > > > > It's not a map type of goto_or_nop instructions either.
> > > > >
> > > > > At load time libbpf can populate this array with indices of insns
> > > > > that the verifier and JIT need to track. Once JITed the array is readonly
> > > > > for bpf prog and for user space.
> > > >
> > > > So this will be a map per .insn_addrs.X section (where X is key or
> > > > a pre-defined suffix for jump tables or indirect calls). And to tell
> > > > the verifier about these maps we will need to pass an array of
> > > >
> > > > struct {
> > > > u32 map_fd;
> > > > u32 type; /* static key, jump table, etc. */
> > > > }
> > > >
> > > > on program load. Is this correct?
> > >
> > >
> > > Probably not.
> > > Since we're going with a new map type (at least for the sake of this
> > > discussion) it shouldn't need a new way to tell the verifier about it.
> > > If .insn_addrs.jmp_table_A was a section generated for switch() statement
> > > by llvm it will be created as a map by libbpf,
> > > and there will be an ld_imm64 insn generated by llvm that points
> > > to that map.
> > > libbpf will populate ld_imm64 insn with map_fd, just like it does
> > > for global data.
> >
> > I understand how this works for indirect jumps (and for the
> > bpf_static_branch_update(&foo) kfunc) where we have a ld_imm64 with a
> > map, however, I am still not sure how this will work for static
> > branches where we just have a 8 byte JA insn + an index in the
> > corresponding ".insn_addrs.foo" section. How kernel will know that the
> > program is using a corresponding map which we create from
> > ".insn_addrs.foo" without specifying this on program load?
> >
> > (Sorry for replying late, catching up after [simultaneous] pto &
> > covid.)
>
> sorry. ctx switch takes time.
> libbpf can just bpf_prog_bind_map to associate this new map type
> of ptr_to_insn with a program.
> Or I misunderstood the question?
All ptr_to_insn maps are required during the verification. So
bpf_prog_bind_map can't be used as it requires an existing program.
What could work and what I am proposing is to pass a list of bound
maps in prog_load attributes. Then such maps can be used during the
verification. For normal maps
prog = prog_load(attr={.bound_maps=maps})
will be semantically the same as
prog = prog_load()
bpf_prog_bind_map(prog, maps)
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 9:03 ` Anton Protopopov
@ 2024-03-14 17:07 ` Alexei Starovoitov
2024-03-14 20:06 ` Andrii Nakryiko
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-03-14 17:07 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 14, 2024 at 2:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On Wed, Mar 13, 2024 at 06:56:34PM -0700, Alexei Starovoitov wrote:
> > On Wed, Mar 6, 2024 at 2:51 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > >
> > > On Tue, Feb 20, 2024 at 05:09:36PM -0800, Alexei Starovoitov wrote:
> > > > On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > >
> > > > > On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > > > > > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > >
> > > > > > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > > > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > >
> > > > > > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > > > >
> > > > > > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > > > > > --- a/include/linux/bpf.h
> > > > > > > > > > > +++ b/include/linux/bpf.h
> > > > > > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > > > > > };
> > > > > > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > > > > > u32 *orig_idx;
> > > > > > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > > > > > + * instructions, if allocated
> > > > > > > > > > > + */
> > > > > > > > > > > + struct {
> > > > > > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > > > > > + } *xlated_to_jit;
> > > > > > > > > >
> > > > > > > > > > Simply put Nack to this approach.
> > > > > > > > > >
> > > > > > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > > > > > >
> > > > > > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > > > > > aka "index on insn".
> > > > > > > > > > The verifier would need to track that such things exist and adjust
> > > > > > > > > > indices of insns when patching affects those indices.
> > > > > > > > > >
> > > > > > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > > > > > Different algorithms can be used to keep them correct.
> > > > > > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > > > > > during patch_insn() may even be ok to start.
> > > > > > > > > >
> > > > > > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > > > > > >
> > > > > > > > > Ok, thanks for looking, this makes sense.
> > > > > > > >
> > > > > > > > Before jumping into coding I think it would be good to discuss
> > > > > > > > the design first.
> > > > > > > > I'm thinking such "address of insn" will be similar to
> > > > > > > > existing "address of subprog",
> > > > > > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > > > > > "address of insn" would be a bit more involved to track
> > > > > > > > during JIT and likely trivial during insn patching,
> > > > > > > > since we're already doing imm adjustment for pseudo_func.
> > > > > > > > So that part of design is straightforward.
> > > > > > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > > > > > >
> > > > > > > To implement the "primitive version" of static branches, where the
> > > > > > > only API is `static_branch_update(xlated off, on/off)` the only
> > > > > > > requirement is to build `xlated -> jitted` mapping (which is done
> > > > > > > in JIT, after the verification). This can be done in a simplified
> > > > > > > version of this patch, without xlated->orig mapping and with
> > > > > > > xlated->jit mapping only done to gotol_or_nop instructions.
> > > > > >
> > > > > > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > > > > > the prog will work for user space to flip them, but...
> > > > > >
> > > > > > > The "address of insn" appears when we want to provide a more
> > > > > > > higher-level API when some object (in user-space or in kernel) keeps
> > > > > > > track of one or more gotol_or_nop instructions so that after the
> > > > > > > program load this controlling object has a list of xlated offsets.
> > > > > > > But this would be a follow-up to the initial static branches patch.
> > > > > >
> > > > > > this won't work as a follow up,
> > > > > > since such an array won't work for bpf prog that wants to flip branches.
> > > > > > There is nothing that associates static_branch name/id with
> > > > > > particular goto_or_nop.
> > > > > > There could be a kfunc that bpf prog calls, but it can only
> > > > > > flip all of such insns in the prog.
> > > > > > Unless we start encoding a special id inside goto_or_nop or other hacks.
> > > > > >
> > > > > > > > The question is whether such "address of insn" should be allowed
> > > > > > > > in the data section. If so, we need to brainstorm how to
> > > > > > > > do it cleanly.
> > > > > > > > We had various hacks for similar things in the past. Like prog_array.
> > > > > > > > Let's not repeat such mistakes.
> > > > > > >
> > > > > > > So, data section is required for implementing jump tables? Like,
> > > > > > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > > > > > corresponding "ptr to insn" object for every occurence of &&label,
> > > > > > > which will be adjusted during verification.
> > > > > > > Looks to me like this one doesn't require any more API than specifying
> > > > > > > a list of &&label occurencies on program load.
> > > > > > >
> > > > > > > For "static keys" though (a feature on top of this patch series) we
> > > > > > > need to have access to the corresponding set of adjusted pointers.
> > > > > > >
> > > > > > > Isn't this enough to add something like an array of
> > > > > > >
> > > > > > > struct insn_ptr {
> > > > > > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > > > > > u32 insn_off; /* original offset on load */
> > > > > > > union {
> > > > > > > struct label {...};
> > > > > > > struct st_branch { u32 key_id, ..};
> > > > > > > };
> > > > > > > };
> > > > > >
> > > > > > which I don't like because it hard codes static_branch needs into
> > > > > > insn->jit_addr association.
> > > > > > "address of insn" should be an individual building block without
> > > > > > bolted on parts.
> > > > > >
> > > > > > A data section with a set of such "address of insn"
> > > > > > can be a description of one static_branch.
> > > > > > There will be different ways to combine such building blocks.
> > > > > > For example:
> > > > > > static_branch(foo) can emit goto_or_nop into bpf code
> > > > > > and add "address of insn" into a section '.insn_addrs.foo".
> > > > > > This section is what libbpf and bpf prog will recognize as a set
> > > > > > of "address of insn" that can be passed into static_branch_update kfunc
> > > > > > or static_branch_update sys_bpf command.
> > > > > > The question is whether we need a new map type (array derivative)
> > > > > > to hold a set of "address of insn" or it can be a part of an existing
> > > > > > global data array.
> > > > > > A new map type is easier to reason about.
> > > > > > Notice how such a new map type is not a map type of static branches.
> > > > > > It's not a map type of goto_or_nop instructions either.
> > > > > >
> > > > > > At load time libbpf can populate this array with indices of insns
> > > > > > that the verifier and JIT need to track. Once JITed the array is readonly
> > > > > > for bpf prog and for user space.
> > > > >
> > > > > So this will be a map per .insn_addrs.X section (where X is key or
> > > > > a pre-defined suffix for jump tables or indirect calls). And to tell
> > > > > the verifier about these maps we will need to pass an array of
> > > > >
> > > > > struct {
> > > > > u32 map_fd;
> > > > > u32 type; /* static key, jump table, etc. */
> > > > > }
> > > > >
> > > > > on program load. Is this correct?
> > > >
> > > >
> > > > Probably not.
> > > > Since we're going with a new map type (at least for the sake of this
> > > > discussion) it shouldn't need a new way to tell the verifier about it.
> > > > If .insn_addrs.jmp_table_A was a section generated for switch() statement
> > > > by llvm it will be created as a map by libbpf,
> > > > and there will be an ld_imm64 insn generated by llvm that points
> > > > to that map.
> > > > libbpf will populate ld_imm64 insn with map_fd, just like it does
> > > > for global data.
> > >
> > > I understand how this works for indirect jumps (and for the
> > > bpf_static_branch_update(&foo) kfunc) where we have a ld_imm64 with a
> > > map, however, I am still not sure how this will work for static
> > > branches where we just have a 8 byte JA insn + an index in the
> > > corresponding ".insn_addrs.foo" section. How kernel will know that the
> > > program is using a corresponding map which we create from
> > > ".insn_addrs.foo" without specifying this on program load?
> > >
> > > (Sorry for replying late, catching up after [simultaneous] pto &
> > > covid.)
> >
> > sorry. ctx switch takes time.
> > libbpf can just bpf_prog_bind_map to associate this new map type
> > of ptr_to_insn with a program.
> > Or I misunderstood the question?
>
> All ptr_to_insn maps are required during the verification. So
> bpf_prog_bind_map can't be used as it requires an existing program.
I see.
> What could work and what I am proposing is to pass a list of bound
> maps in prog_load attributes. Then such maps can be used during the
> verification. For normal maps
>
> prog = prog_load(attr={.bound_maps=maps})
>
> will be semantically the same as
>
> prog = prog_load()
> bpf_prog_bind_map(prog, maps)
Instead of a whole new api, let's make libbpf insert
ld_imm64 r0, map
as the first insn for this case for now.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 17:07 ` Alexei Starovoitov
@ 2024-03-14 20:06 ` Andrii Nakryiko
2024-03-14 21:41 ` Alexei Starovoitov
0 siblings, 1 reply; 32+ messages in thread
From: Andrii Nakryiko @ 2024-03-14 20:06 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Anton Protopopov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 14, 2024 at 10:07 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Mar 14, 2024 at 2:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On Wed, Mar 13, 2024 at 06:56:34PM -0700, Alexei Starovoitov wrote:
> > > On Wed, Mar 6, 2024 at 2:51 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > >
> > > > On Tue, Feb 20, 2024 at 05:09:36PM -0800, Alexei Starovoitov wrote:
> > > > > On Fri, Feb 16, 2024 at 6:04 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > >
> > > > > > On Wed, Feb 14, 2024 at 10:48:26PM -0800, Alexei Starovoitov wrote:
> > > > > > > On Thu, Feb 8, 2024 at 3:11 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > >
> > > > > > > > On Tue, Feb 06, 2024 at 06:26:12PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > On Tue, Feb 6, 2024 at 2:08 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > > >
> > > > > > > > > > On Mon, Feb 05, 2024 at 05:09:51PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > > > On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> > > > > > > > > > > >
> > > > > > > > > > > > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > > > > > > > > > > > index 4def3dde35f6..bdd6be718e82 100644
> > > > > > > > > > > > --- a/include/linux/bpf.h
> > > > > > > > > > > > +++ b/include/linux/bpf.h
> > > > > > > > > > > > @@ -1524,6 +1524,13 @@ struct bpf_prog_aux {
> > > > > > > > > > > > };
> > > > > > > > > > > > /* an array of original indexes for all xlated instructions */
> > > > > > > > > > > > u32 *orig_idx;
> > > > > > > > > > > > + /* for every xlated instruction point to all generated jited
> > > > > > > > > > > > + * instructions, if allocated
> > > > > > > > > > > > + */
> > > > > > > > > > > > + struct {
> > > > > > > > > > > > + u32 off; /* local offset in the jitted code */
> > > > > > > > > > > > + u32 len; /* the total len of generated jit code */
> > > > > > > > > > > > + } *xlated_to_jit;
> > > > > > > > > > >
> > > > > > > > > > > Simply put Nack to this approach.
> > > > > > > > > > >
> > > > > > > > > > > Patches 2 and 3 add an extreme amount of memory overhead.
> > > > > > > > > > >
> > > > > > > > > > > As we discussed during office hours we need a "pointer to insn" concept
> > > > > > > > > > > aka "index on insn".
> > > > > > > > > > > The verifier would need to track that such things exist and adjust
> > > > > > > > > > > indices of insns when patching affects those indices.
> > > > > > > > > > >
> > > > > > > > > > > For every static branch there will be one such "pointer to insn".
> > > > > > > > > > > Different algorithms can be used to keep them correct.
> > > > > > > > > > > The simplest 'lets iterate over all such pointers and update them'
> > > > > > > > > > > during patch_insn() may even be ok to start.
> > > > > > > > > > >
> > > > > > > > > > > Such "pointer to insn" won't add any memory overhead.
> > > > > > > > > > > When patch+jit is done all such "pointer to insn" are fixed value.
> > > > > > > > > >
> > > > > > > > > > Ok, thanks for looking, this makes sense.
> > > > > > > > >
> > > > > > > > > Before jumping into coding I think it would be good to discuss
> > > > > > > > > the design first.
> > > > > > > > > I'm thinking such "address of insn" will be similar to
> > > > > > > > > existing "address of subprog",
> > > > > > > > > which is encoded in ld_imm64 as BPF_PSEUDO_FUNC.
> > > > > > > > > "address of insn" would be a bit more involved to track
> > > > > > > > > during JIT and likely trivial during insn patching,
> > > > > > > > > since we're already doing imm adjustment for pseudo_func.
> > > > > > > > > So that part of design is straightforward.
> > > > > > > > > Implementation in the kernel and libbpf can copy paste from pseudo_func too.
> > > > > > > >
> > > > > > > > To implement the "primitive version" of static branches, where the
> > > > > > > > only API is `static_branch_update(xlated off, on/off)` the only
> > > > > > > > requirement is to build `xlated -> jitted` mapping (which is done
> > > > > > > > in JIT, after the verification). This can be done in a simplified
> > > > > > > > version of this patch, without xlated->orig mapping and with
> > > > > > > > xlated->jit mapping only done to gotol_or_nop instructions.
> > > > > > >
> > > > > > > yes. The array of insn->jit_addr sized with as many goto_or_nop-s
> > > > > > > the prog will work for user space to flip them, but...
> > > > > > >
> > > > > > > > The "address of insn" appears when we want to provide a more
> > > > > > > > higher-level API when some object (in user-space or in kernel) keeps
> > > > > > > > track of one or more gotol_or_nop instructions so that after the
> > > > > > > > program load this controlling object has a list of xlated offsets.
> > > > > > > > But this would be a follow-up to the initial static branches patch.
> > > > > > >
> > > > > > > this won't work as a follow up,
> > > > > > > since such an array won't work for bpf prog that wants to flip branches.
> > > > > > > There is nothing that associates static_branch name/id with
> > > > > > > particular goto_or_nop.
> > > > > > > There could be a kfunc that bpf prog calls, but it can only
> > > > > > > flip all of such insns in the prog.
> > > > > > > Unless we start encoding a special id inside goto_or_nop or other hacks.
> > > > > > >
> > > > > > > > > The question is whether such "address of insn" should be allowed
> > > > > > > > > in the data section. If so, we need to brainstorm how to
> > > > > > > > > do it cleanly.
> > > > > > > > > We had various hacks for similar things in the past. Like prog_array.
> > > > > > > > > Let's not repeat such mistakes.
> > > > > > > >
> > > > > > > > So, data section is required for implementing jump tables? Like,
> > > > > > > > to add a new PTR_TO_LABEL or PTR_TO_INSN data type, and a
> > > > > > > > corresponding "ptr to insn" object for every occurence of &&label,
> > > > > > > > which will be adjusted during verification.
> > > > > > > > Looks to me like this one doesn't require any more API than specifying
> > > > > > > > a list of &&label occurencies on program load.
> > > > > > > >
> > > > > > > > For "static keys" though (a feature on top of this patch series) we
> > > > > > > > need to have access to the corresponding set of adjusted pointers.
> > > > > > > >
> > > > > > > > Isn't this enough to add something like an array of
> > > > > > > >
> > > > > > > > struct insn_ptr {
> > > > > > > > u32 type; /* LABEL, STATIC_BRANCH,... */
> > > > > > > > u32 insn_off; /* original offset on load */
> > > > > > > > union {
> > > > > > > > struct label {...};
> > > > > > > > struct st_branch { u32 key_id, ..};
> > > > > > > > };
> > > > > > > > };
> > > > > > >
> > > > > > > which I don't like because it hard codes static_branch needs into
> > > > > > > insn->jit_addr association.
> > > > > > > "address of insn" should be an individual building block without
> > > > > > > bolted on parts.
> > > > > > >
> > > > > > > A data section with a set of such "address of insn"
> > > > > > > can be a description of one static_branch.
> > > > > > > There will be different ways to combine such building blocks.
> > > > > > > For example:
> > > > > > > static_branch(foo) can emit goto_or_nop into bpf code
> > > > > > > and add "address of insn" into a section '.insn_addrs.foo".
> > > > > > > This section is what libbpf and bpf prog will recognize as a set
> > > > > > > of "address of insn" that can be passed into static_branch_update kfunc
> > > > > > > or static_branch_update sys_bpf command.
> > > > > > > The question is whether we need a new map type (array derivative)
> > > > > > > to hold a set of "address of insn" or it can be a part of an existing
> > > > > > > global data array.
> > > > > > > A new map type is easier to reason about.
> > > > > > > Notice how such a new map type is not a map type of static branches.
> > > > > > > It's not a map type of goto_or_nop instructions either.
> > > > > > >
> > > > > > > At load time libbpf can populate this array with indices of insns
> > > > > > > that the verifier and JIT need to track. Once JITed the array is readonly
> > > > > > > for bpf prog and for user space.
> > > > > >
> > > > > > So this will be a map per .insn_addrs.X section (where X is key or
> > > > > > a pre-defined suffix for jump tables or indirect calls). And to tell
> > > > > > the verifier about these maps we will need to pass an array of
> > > > > >
> > > > > > struct {
> > > > > > u32 map_fd;
> > > > > > u32 type; /* static key, jump table, etc. */
> > > > > > }
> > > > > >
> > > > > > on program load. Is this correct?
> > > > >
> > > > >
> > > > > Probably not.
> > > > > Since we're going with a new map type (at least for the sake of this
> > > > > discussion) it shouldn't need a new way to tell the verifier about it.
> > > > > If .insn_addrs.jmp_table_A was a section generated for switch() statement
> > > > > by llvm it will be created as a map by libbpf,
> > > > > and there will be an ld_imm64 insn generated by llvm that points
> > > > > to that map.
> > > > > libbpf will populate ld_imm64 insn with map_fd, just like it does
> > > > > for global data.
> > > >
> > > > I understand how this works for indirect jumps (and for the
> > > > bpf_static_branch_update(&foo) kfunc) where we have a ld_imm64 with a
> > > > map, however, I am still not sure how this will work for static
> > > > branches where we just have a 8 byte JA insn + an index in the
> > > > corresponding ".insn_addrs.foo" section. How kernel will know that the
> > > > program is using a corresponding map which we create from
> > > > ".insn_addrs.foo" without specifying this on program load?
> > > >
> > > > (Sorry for replying late, catching up after [simultaneous] pto &
> > > > covid.)
> > >
> > > sorry. ctx switch takes time.
> > > libbpf can just bpf_prog_bind_map to associate this new map type
> > > of ptr_to_insn with a program.
> > > Or I misunderstood the question?
> >
> > All ptr_to_insn maps are required during the verification. So
> > bpf_prog_bind_map can't be used as it requires an existing program.
>
> I see.
>
> > What could work and what I am proposing is to pass a list of bound
> > maps in prog_load attributes. Then such maps can be used during the
> > verification. For normal maps
> >
> > prog = prog_load(attr={.bound_maps=maps})
> >
> > will be semantically the same as
> >
> > prog = prog_load()
> > bpf_prog_bind_map(prog, maps)
>
> Instead of a whole new api, let's make libbpf insert
> ld_imm64 r0, map
> as the first insn for this case for now.
This sounds like a big hack and unnecessary complication, tbh. I'd
like to avoid having to do this in libbpf.
But I think we almost have this already supported. In BPF_PROG_LOAD
UAPI we have fd_array property, right? I think right now we lazily
refcnt referenced maps. But I think it makes total sense to just
define that bpf_prog will keep references to all BPF objects passed in
through fd_array, WDYT? Verifier will just iterate all provided FDs,
determine kind of BPF object it is (and reject unknown ones), and then
just take refcnts on each of them once. On prog free we'll just do the
same in reverse and be done with it.
It also can be used as a batch and single-step (in the sense it will
be done as part of program load instead of a separate command)
alternative for bpf_prog_bind_map(), I suppose.
Thoughts?
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 20:06 ` Andrii Nakryiko
@ 2024-03-14 21:41 ` Alexei Starovoitov
2024-03-15 13:11 ` Anton Protopopov
2024-03-15 16:32 ` Andrii Nakryiko
0 siblings, 2 replies; 32+ messages in thread
From: Alexei Starovoitov @ 2024-03-14 21:41 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Anton Protopopov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
> >
> > > What could work and what I am proposing is to pass a list of bound
> > > maps in prog_load attributes. Then such maps can be used during the
> > > verification. For normal maps
> > >
> > > prog = prog_load(attr={.bound_maps=maps})
> > >
> > > will be semantically the same as
> > >
> > > prog = prog_load()
> > > bpf_prog_bind_map(prog, maps)
> >
> > Instead of a whole new api, let's make libbpf insert
> > ld_imm64 r0, map
> > as the first insn for this case for now.
>
> This sounds like a big hack and unnecessary complication, tbh. I'd
> like to avoid having to do this in libbpf.
>
> But I think we almost have this already supported. In BPF_PROG_LOAD
> UAPI we have fd_array property, right? I think right now we lazily
> refcnt referenced maps. But I think it makes total sense to just
> define that bpf_prog will keep references to all BPF objects passed in
> through fd_array, WDYT? Verifier will just iterate all provided FDs,
> determine kind of BPF object it is (and reject unknown ones), and then
> just take refcnts on each of them once. On prog free we'll just do the
> same in reverse and be done with it.
>
> It also can be used as a batch and single-step (in the sense it will
> be done as part of program load instead of a separate command)
> alternative for bpf_prog_bind_map(), I suppose.
fd_array approach also works. There can be map and btf fds in there.
I would only bind maps this way.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 21:41 ` Alexei Starovoitov
@ 2024-03-15 13:11 ` Anton Protopopov
2024-03-15 16:32 ` Andrii Nakryiko
1 sibling, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-03-15 13:11 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Andrii Nakryiko, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 14, 2024 at 02:41:36PM -0700, Alexei Starovoitov wrote:
> On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> > >
> > > > What could work and what I am proposing is to pass a list of bound
> > > > maps in prog_load attributes. Then such maps can be used during the
> > > > verification. For normal maps
> > > >
> > > > prog = prog_load(attr={.bound_maps=maps})
> > > >
> > > > will be semantically the same as
> > > >
> > > > prog = prog_load()
> > > > bpf_prog_bind_map(prog, maps)
> > >
> > > Instead of a whole new api, let's make libbpf insert
> > > ld_imm64 r0, map
> > > as the first insn for this case for now.
> >
> > This sounds like a big hack and unnecessary complication, tbh. I'd
> > like to avoid having to do this in libbpf.
> >
> > But I think we almost have this already supported. In BPF_PROG_LOAD
> > UAPI we have fd_array property, right? I think right now we lazily
> > refcnt referenced maps. But I think it makes total sense to just
> > define that bpf_prog will keep references to all BPF objects passed in
> > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > determine kind of BPF object it is (and reject unknown ones), and then
> > just take refcnts on each of them once. On prog free we'll just do the
> > same in reverse and be done with it.
> >
> > It also can be used as a batch and single-step (in the sense it will
> > be done as part of program load instead of a separate command)
> > alternative for bpf_prog_bind_map(), I suppose.
>
> fd_array approach also works. There can be map and btf fds in there.
> I would only bind maps this way.
Ok, thanks, this approach looks good
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-14 21:41 ` Alexei Starovoitov
2024-03-15 13:11 ` Anton Protopopov
@ 2024-03-15 16:32 ` Andrii Nakryiko
2024-03-15 17:22 ` Alexei Starovoitov
1 sibling, 1 reply; 32+ messages in thread
From: Andrii Nakryiko @ 2024-03-15 16:32 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Anton Protopopov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> > >
> > > > What could work and what I am proposing is to pass a list of bound
> > > > maps in prog_load attributes. Then such maps can be used during the
> > > > verification. For normal maps
> > > >
> > > > prog = prog_load(attr={.bound_maps=maps})
> > > >
> > > > will be semantically the same as
> > > >
> > > > prog = prog_load()
> > > > bpf_prog_bind_map(prog, maps)
> > >
> > > Instead of a whole new api, let's make libbpf insert
> > > ld_imm64 r0, map
> > > as the first insn for this case for now.
> >
> > This sounds like a big hack and unnecessary complication, tbh. I'd
> > like to avoid having to do this in libbpf.
> >
> > But I think we almost have this already supported. In BPF_PROG_LOAD
> > UAPI we have fd_array property, right? I think right now we lazily
> > refcnt referenced maps. But I think it makes total sense to just
> > define that bpf_prog will keep references to all BPF objects passed in
> > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > determine kind of BPF object it is (and reject unknown ones), and then
> > just take refcnts on each of them once. On prog free we'll just do the
> > same in reverse and be done with it.
> >
> > It also can be used as a batch and single-step (in the sense it will
> > be done as part of program load instead of a separate command)
> > alternative for bpf_prog_bind_map(), I suppose.
>
> fd_array approach also works. There can be map and btf fds in there.
> I would only bind maps this way.
Any reason why we should have non-uniform behavior between maps and
BTFs? Seems more error-prone to have a difference here, tbh.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-15 16:32 ` Andrii Nakryiko
@ 2024-03-15 17:22 ` Alexei Starovoitov
2024-03-15 17:29 ` Andrii Nakryiko
0 siblings, 1 reply; 32+ messages in thread
From: Alexei Starovoitov @ 2024-03-15 17:22 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Anton Protopopov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Fri, Mar 15, 2024 at 9:33 AM Andrii Nakryiko
<andrii.nakryiko@gmail.com> wrote:
>
> On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > > What could work and what I am proposing is to pass a list of bound
> > > > > maps in prog_load attributes. Then such maps can be used during the
> > > > > verification. For normal maps
> > > > >
> > > > > prog = prog_load(attr={.bound_maps=maps})
> > > > >
> > > > > will be semantically the same as
> > > > >
> > > > > prog = prog_load()
> > > > > bpf_prog_bind_map(prog, maps)
> > > >
> > > > Instead of a whole new api, let's make libbpf insert
> > > > ld_imm64 r0, map
> > > > as the first insn for this case for now.
> > >
> > > This sounds like a big hack and unnecessary complication, tbh. I'd
> > > like to avoid having to do this in libbpf.
> > >
> > > But I think we almost have this already supported. In BPF_PROG_LOAD
> > > UAPI we have fd_array property, right? I think right now we lazily
> > > refcnt referenced maps. But I think it makes total sense to just
> > > define that bpf_prog will keep references to all BPF objects passed in
> > > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > > determine kind of BPF object it is (and reject unknown ones), and then
> > > just take refcnts on each of them once. On prog free we'll just do the
> > > same in reverse and be done with it.
> > >
> > > It also can be used as a batch and single-step (in the sense it will
> > > be done as part of program load instead of a separate command)
> > > alternative for bpf_prog_bind_map(), I suppose.
> >
> > fd_array approach also works. There can be map and btf fds in there.
> > I would only bind maps this way.
>
> Any reason why we should have non-uniform behavior between maps and
> BTFs? Seems more error-prone to have a difference here, tbh.
because maps are only held in used_maps while btfs are held
in used_btfs and in kfunc_btf_tab.
And looking at btf_fd it's not clear whether it will be in ld_imm64
and hence used_btf or it's kfunc and will be in kfunc_btf_tab.
All btfs can be stored unconditionally in used_btf,
but that's unnecessary refcnt inc and module_get too.
Doesn't hurt, but makes it harder to reason about everything.
At least to me.
I guess if the whole refcnt of maps and btfs is factored out
and cleaned up into uniform used_maps/used_btf then it's ok,
but fd_array is optional. So it feels messy.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-15 17:22 ` Alexei Starovoitov
@ 2024-03-15 17:29 ` Andrii Nakryiko
2024-03-28 16:37 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Andrii Nakryiko @ 2024-03-15 17:29 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Anton Protopopov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Fri, Mar 15, 2024 at 10:23 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Mar 15, 2024 at 9:33 AM Andrii Nakryiko
> <andrii.nakryiko@gmail.com> wrote:
> >
> > On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > > What could work and what I am proposing is to pass a list of bound
> > > > > > maps in prog_load attributes. Then such maps can be used during the
> > > > > > verification. For normal maps
> > > > > >
> > > > > > prog = prog_load(attr={.bound_maps=maps})
> > > > > >
> > > > > > will be semantically the same as
> > > > > >
> > > > > > prog = prog_load()
> > > > > > bpf_prog_bind_map(prog, maps)
> > > > >
> > > > > Instead of a whole new api, let's make libbpf insert
> > > > > ld_imm64 r0, map
> > > > > as the first insn for this case for now.
> > > >
> > > > This sounds like a big hack and unnecessary complication, tbh. I'd
> > > > like to avoid having to do this in libbpf.
> > > >
> > > > But I think we almost have this already supported. In BPF_PROG_LOAD
> > > > UAPI we have fd_array property, right? I think right now we lazily
> > > > refcnt referenced maps. But I think it makes total sense to just
> > > > define that bpf_prog will keep references to all BPF objects passed in
> > > > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > > > determine kind of BPF object it is (and reject unknown ones), and then
> > > > just take refcnts on each of them once. On prog free we'll just do the
> > > > same in reverse and be done with it.
> > > >
> > > > It also can be used as a batch and single-step (in the sense it will
> > > > be done as part of program load instead of a separate command)
> > > > alternative for bpf_prog_bind_map(), I suppose.
> > >
> > > fd_array approach also works. There can be map and btf fds in there.
> > > I would only bind maps this way.
> >
> > Any reason why we should have non-uniform behavior between maps and
> > BTFs? Seems more error-prone to have a difference here, tbh.
>
> because maps are only held in used_maps while btfs are held
> in used_btfs and in kfunc_btf_tab.
> And looking at btf_fd it's not clear whether it will be in ld_imm64
> and hence used_btf or it's kfunc and will be in kfunc_btf_tab.
> All btfs can be stored unconditionally in used_btf,
> but that's unnecessary refcnt inc and module_get too.
> Doesn't hurt, but makes it harder to reason about everything.
> At least to me.
> I guess if the whole refcnt of maps and btfs is factored out
> and cleaned up into uniform used_maps/used_btf then it's ok,
> but fd_array is optional. So it feels messy.
Yeah, I was imagining that we'd iterate fd_array (if it's provided)
and add any map/btf into used_{map,btf}, refcnt. Then during
verification we'll just know that any referenced map or btf from
fd_array is already refcounted, so we wouldn't do it there. But I
haven't looked at kfunc_btf_tab, if that's causing some troubles with
this approach, then it's fine by me.
The assumption was that a uniform approach will be less messy and
simplify code and reasoning about the behavior, not the other way. If
that's not the case we can do it just for maps for now.
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-15 17:29 ` Andrii Nakryiko
@ 2024-03-28 16:37 ` Anton Protopopov
2024-03-29 22:44 ` Andrii Nakryiko
0 siblings, 1 reply; 32+ messages in thread
From: Anton Protopopov @ 2024-03-28 16:37 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Alexei Starovoitov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On 24/03/15 10:29, Andrii Nakryiko wrote:
> On Fri, Mar 15, 2024 at 10:23 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Mar 15, 2024 at 9:33 AM Andrii Nakryiko
> > <andrii.nakryiko@gmail.com> wrote:
> > >
> > > On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > > >
> > > > > > > What could work and what I am proposing is to pass a list of bound
> > > > > > > maps in prog_load attributes. Then such maps can be used during the
> > > > > > > verification. For normal maps
> > > > > > >
> > > > > > > prog = prog_load(attr={.bound_maps=maps})
> > > > > > >
> > > > > > > will be semantically the same as
> > > > > > >
> > > > > > > prog = prog_load()
> > > > > > > bpf_prog_bind_map(prog, maps)
> > > > > >
> > > > > > Instead of a whole new api, let's make libbpf insert
> > > > > > ld_imm64 r0, map
> > > > > > as the first insn for this case for now.
> > > > >
> > > > > This sounds like a big hack and unnecessary complication, tbh. I'd
> > > > > like to avoid having to do this in libbpf.
> > > > >
> > > > > But I think we almost have this already supported. In BPF_PROG_LOAD
> > > > > UAPI we have fd_array property, right? I think right now we lazily
> > > > > refcnt referenced maps. But I think it makes total sense to just
> > > > > define that bpf_prog will keep references to all BPF objects passed in
> > > > > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > > > > determine kind of BPF object it is (and reject unknown ones), and then
> > > > > just take refcnts on each of them once. On prog free we'll just do the
> > > > > same in reverse and be done with it.
> > > > >
> > > > > It also can be used as a batch and single-step (in the sense it will
> > > > > be done as part of program load instead of a separate command)
> > > > > alternative for bpf_prog_bind_map(), I suppose.
> > > >
> > > > fd_array approach also works. There can be map and btf fds in there.
> > > > I would only bind maps this way.
> > >
> > > Any reason why we should have non-uniform behavior between maps and
> > > BTFs? Seems more error-prone to have a difference here, tbh.
> >
> > because maps are only held in used_maps while btfs are held
> > in used_btfs and in kfunc_btf_tab.
> > And looking at btf_fd it's not clear whether it will be in ld_imm64
> > and hence used_btf or it's kfunc and will be in kfunc_btf_tab.
> > All btfs can be stored unconditionally in used_btf,
> > but that's unnecessary refcnt inc and module_get too.
> > Doesn't hurt, but makes it harder to reason about everything.
> > At least to me.
> > I guess if the whole refcnt of maps and btfs is factored out
> > and cleaned up into uniform used_maps/used_btf then it's ok,
> > but fd_array is optional. So it feels messy.
>
> Yeah, I was imagining that we'd iterate fd_array (if it's provided)
> and add any map/btf into used_{map,btf}, refcnt. Then during
> verification we'll just know that any referenced map or btf from
> fd_array is already refcounted, so we wouldn't do it there. But I
> haven't looked at kfunc_btf_tab, if that's causing some troubles with
> this approach, then it's fine by me.
>
> The assumption was that a uniform approach will be less messy and
> simplify code and reasoning about the behavior, not the other way. If
> that's not the case we can do it just for maps for now.
fd_array is sent in attrs without specifying its size, so individual
fds are copied to kernel as needed. Therefore, this is not possible
to pass extra fds (not used directly by the program) without changing
the API. So either a pair of new fields, say, (fd_extra,fd_extra_len),
or just another field fd_array_len should be added. What sounds better?
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-28 16:37 ` Anton Protopopov
@ 2024-03-29 22:44 ` Andrii Nakryiko
2024-04-01 9:47 ` Anton Protopopov
0 siblings, 1 reply; 32+ messages in thread
From: Andrii Nakryiko @ 2024-03-29 22:44 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Thu, Mar 28, 2024 at 9:37 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> On 24/03/15 10:29, Andrii Nakryiko wrote:
> > On Fri, Mar 15, 2024 at 10:23 AM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Fri, Mar 15, 2024 at 9:33 AM Andrii Nakryiko
> > > <andrii.nakryiko@gmail.com> wrote:
> > > >
> > > > On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
> > > > <alexei.starovoitov@gmail.com> wrote:
> > > > >
> > > > > On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> > > > > <andrii.nakryiko@gmail.com> wrote:
> > > > > > >
> > > > > > > > What could work and what I am proposing is to pass a list of bound
> > > > > > > > maps in prog_load attributes. Then such maps can be used during the
> > > > > > > > verification. For normal maps
> > > > > > > >
> > > > > > > > prog = prog_load(attr={.bound_maps=maps})
> > > > > > > >
> > > > > > > > will be semantically the same as
> > > > > > > >
> > > > > > > > prog = prog_load()
> > > > > > > > bpf_prog_bind_map(prog, maps)
> > > > > > >
> > > > > > > Instead of a whole new api, let's make libbpf insert
> > > > > > > ld_imm64 r0, map
> > > > > > > as the first insn for this case for now.
> > > > > >
> > > > > > This sounds like a big hack and unnecessary complication, tbh. I'd
> > > > > > like to avoid having to do this in libbpf.
> > > > > >
> > > > > > But I think we almost have this already supported. In BPF_PROG_LOAD
> > > > > > UAPI we have fd_array property, right? I think right now we lazily
> > > > > > refcnt referenced maps. But I think it makes total sense to just
> > > > > > define that bpf_prog will keep references to all BPF objects passed in
> > > > > > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > > > > > determine kind of BPF object it is (and reject unknown ones), and then
> > > > > > just take refcnts on each of them once. On prog free we'll just do the
> > > > > > same in reverse and be done with it.
> > > > > >
> > > > > > It also can be used as a batch and single-step (in the sense it will
> > > > > > be done as part of program load instead of a separate command)
> > > > > > alternative for bpf_prog_bind_map(), I suppose.
> > > > >
> > > > > fd_array approach also works. There can be map and btf fds in there.
> > > > > I would only bind maps this way.
> > > >
> > > > Any reason why we should have non-uniform behavior between maps and
> > > > BTFs? Seems more error-prone to have a difference here, tbh.
> > >
> > > because maps are only held in used_maps while btfs are held
> > > in used_btfs and in kfunc_btf_tab.
> > > And looking at btf_fd it's not clear whether it will be in ld_imm64
> > > and hence used_btf or it's kfunc and will be in kfunc_btf_tab.
> > > All btfs can be stored unconditionally in used_btf,
> > > but that's unnecessary refcnt inc and module_get too.
> > > Doesn't hurt, but makes it harder to reason about everything.
> > > At least to me.
> > > I guess if the whole refcnt of maps and btfs is factored out
> > > and cleaned up into uniform used_maps/used_btf then it's ok,
> > > but fd_array is optional. So it feels messy.
> >
> > Yeah, I was imagining that we'd iterate fd_array (if it's provided)
> > and add any map/btf into used_{map,btf}, refcnt. Then during
> > verification we'll just know that any referenced map or btf from
> > fd_array is already refcounted, so we wouldn't do it there. But I
> > haven't looked at kfunc_btf_tab, if that's causing some troubles with
> > this approach, then it's fine by me.
> >
> > The assumption was that a uniform approach will be less messy and
> > simplify code and reasoning about the behavior, not the other way. If
> > that's not the case we can do it just for maps for now.
>
> fd_array is sent in attrs without specifying its size, so individual
> fds are copied to kernel as needed. Therefore, this is not possible
> to pass extra fds (not used directly by the program) without changing
> the API. So either a pair of new fields, say, (fd_extra,fd_extra_len),
> or just another field fd_array_len should be added. What sounds better?
I'd say we should extend fd_array with (optional) fd_array_cnt and
have the following logic:
- if fd_array != NULL and fd_array_cnt == 0, then only maps/btfs
referenced from BPF program instructions should be refcnt/fetched;
- if fd_array != NULL and fd_array_cnt > 0, we can eagerly fetch all
FDs and refcnt, as discussed. If any instruction uses the fd index
which is >= fd_array_cnt, that's an error (the user didn't provide a
big enough FD array and we can now detect this).
WDYT?
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns
2024-03-29 22:44 ` Andrii Nakryiko
@ 2024-04-01 9:47 ` Anton Protopopov
0 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-04-01 9:47 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Alexei Starovoitov, Alexei Starovoitov, Andrii Nakryiko,
Daniel Borkmann, Jiri Olsa, Martin KaFai Lau, Stanislav Fomichev,
Yonghong Song, Eduard Zingerman, Quentin Monnet, bpf
On Fri, Mar 29, 2024 at 03:44:04PM -0700, Andrii Nakryiko wrote:
> On Thu, Mar 28, 2024 at 9:37 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > On 24/03/15 10:29, Andrii Nakryiko wrote:
> > > On Fri, Mar 15, 2024 at 10:23 AM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Fri, Mar 15, 2024 at 9:33 AM Andrii Nakryiko
> > > > <andrii.nakryiko@gmail.com> wrote:
> > > > >
> > > > > On Thu, Mar 14, 2024 at 2:41 PM Alexei Starovoitov
> > > > > <alexei.starovoitov@gmail.com> wrote:
> > > > > >
> > > > > > On Thu, Mar 14, 2024 at 1:06 PM Andrii Nakryiko
> > > > > > <andrii.nakryiko@gmail.com> wrote:
> > > > > > > >
> > > > > > > > > What could work and what I am proposing is to pass a list of bound
> > > > > > > > > maps in prog_load attributes. Then such maps can be used during the
> > > > > > > > > verification. For normal maps
> > > > > > > > >
> > > > > > > > > prog = prog_load(attr={.bound_maps=maps})
> > > > > > > > >
> > > > > > > > > will be semantically the same as
> > > > > > > > >
> > > > > > > > > prog = prog_load()
> > > > > > > > > bpf_prog_bind_map(prog, maps)
> > > > > > > >
> > > > > > > > Instead of a whole new api, let's make libbpf insert
> > > > > > > > ld_imm64 r0, map
> > > > > > > > as the first insn for this case for now.
> > > > > > >
> > > > > > > This sounds like a big hack and unnecessary complication, tbh. I'd
> > > > > > > like to avoid having to do this in libbpf.
> > > > > > >
> > > > > > > But I think we almost have this already supported. In BPF_PROG_LOAD
> > > > > > > UAPI we have fd_array property, right? I think right now we lazily
> > > > > > > refcnt referenced maps. But I think it makes total sense to just
> > > > > > > define that bpf_prog will keep references to all BPF objects passed in
> > > > > > > through fd_array, WDYT? Verifier will just iterate all provided FDs,
> > > > > > > determine kind of BPF object it is (and reject unknown ones), and then
> > > > > > > just take refcnts on each of them once. On prog free we'll just do the
> > > > > > > same in reverse and be done with it.
> > > > > > >
> > > > > > > It also can be used as a batch and single-step (in the sense it will
> > > > > > > be done as part of program load instead of a separate command)
> > > > > > > alternative for bpf_prog_bind_map(), I suppose.
> > > > > >
> > > > > > fd_array approach also works. There can be map and btf fds in there.
> > > > > > I would only bind maps this way.
> > > > >
> > > > > Any reason why we should have non-uniform behavior between maps and
> > > > > BTFs? Seems more error-prone to have a difference here, tbh.
> > > >
> > > > because maps are only held in used_maps while btfs are held
> > > > in used_btfs and in kfunc_btf_tab.
> > > > And looking at btf_fd it's not clear whether it will be in ld_imm64
> > > > and hence used_btf or it's kfunc and will be in kfunc_btf_tab.
> > > > All btfs can be stored unconditionally in used_btf,
> > > > but that's unnecessary refcnt inc and module_get too.
> > > > Doesn't hurt, but makes it harder to reason about everything.
> > > > At least to me.
> > > > I guess if the whole refcnt of maps and btfs is factored out
> > > > and cleaned up into uniform used_maps/used_btf then it's ok,
> > > > but fd_array is optional. So it feels messy.
> > >
> > > Yeah, I was imagining that we'd iterate fd_array (if it's provided)
> > > and add any map/btf into used_{map,btf}, refcnt. Then during
> > > verification we'll just know that any referenced map or btf from
> > > fd_array is already refcounted, so we wouldn't do it there. But I
> > > haven't looked at kfunc_btf_tab, if that's causing some troubles with
> > > this approach, then it's fine by me.
> > >
> > > The assumption was that a uniform approach will be less messy and
> > > simplify code and reasoning about the behavior, not the other way. If
> > > that's not the case we can do it just for maps for now.
> >
> > fd_array is sent in attrs without specifying its size, so individual
> > fds are copied to kernel as needed. Therefore, this is not possible
> > to pass extra fds (not used directly by the program) without changing
> > the API. So either a pair of new fields, say, (fd_extra,fd_extra_len),
> > or just another field fd_array_len should be added. What sounds better?
>
> I'd say we should extend fd_array with (optional) fd_array_cnt and
> have the following logic:
>
> - if fd_array != NULL and fd_array_cnt == 0, then only maps/btfs
> referenced from BPF program instructions should be refcnt/fetched;
> - if fd_array != NULL and fd_array_cnt > 0, we can eagerly fetch all
> FDs and refcnt, as discussed. If any instruction uses the fd index
> which is >= fd_array_cnt, that's an error (the user didn't provide a
> big enough FD array and we can now detect this).
>
> WDYT?
Yes, thanks, I've thought the same way. I will use this API
^ permalink raw reply [flat|nested] 32+ messages in thread
* [PATCH v1 bpf-next 4/9] selftests/bpf: Add tests for instructions mappings
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (2 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 3/9] bpf: expose how xlated insns map to jitted insns Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 5/9] bpftool: dump new fields of bpf prog info Anton Protopopov
` (5 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
Add several self-tests to test the instructions mappings from xlated
to original:
* check that mappings work for a program without patches
* same for a program with patches to insns
* same for a program with patches to insns and bpf-to-bpf calls
* same for a program with patches and deletions
* same for a program with patches, deletions, and bpf-to-bpf calls
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
.../bpf/prog_tests/bpf_insns_mappings.c | 156 ++++++++++++++++++
.../selftests/bpf/progs/bpf_insns_mappings.c | 155 +++++++++++++++++
2 files changed, 311 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c
create mode 100644 tools/testing/selftests/bpf/progs/bpf_insns_mappings.c
diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c b/tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c
new file mode 100644
index 000000000000..2a7b53231080
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c
@@ -0,0 +1,156 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Isovalent */
+
+#include <test_progs.h>
+#include "bpf_insns_mappings.skel.h"
+
+#define MAX_INSNS 4096
+
+static struct bpf_prog_info *prog_info_and_mappings(int prog_fd)
+{
+ static __thread struct bpf_prog_info prog_info;
+ static __thread char xlated_insns[MAX_INSNS];
+ static __thread __u32 orig_idx[MAX_INSNS];
+ __u32 prog_info_len;
+ __u32 orig_idx_len;
+ int err;
+
+ prog_info_len = sizeof(prog_info);
+
+ memset(&prog_info, 0, sizeof(prog_info));
+ err = bpf_prog_get_info_by_fd(prog_fd, &prog_info, &prog_info_len);
+ if (!ASSERT_GE(err, 0, "bpf_prog_get_info_by_fd"))
+ return NULL;
+
+ orig_idx_len = prog_info.orig_idx_len;
+ memset(&prog_info, 0, sizeof(prog_info));
+
+ if (orig_idx_len) {
+ prog_info.orig_idx_len = orig_idx_len;
+ prog_info.orig_idx = ptr_to_u64(orig_idx);
+ }
+
+ prog_info.xlated_prog_insns = ptr_to_u64(xlated_insns);
+ prog_info.xlated_prog_len = sizeof(xlated_insns);
+
+ err = bpf_prog_get_info_by_fd(prog_fd, &prog_info, &prog_info_len);
+ if (!ASSERT_GE(err, 0, "bpf_prog_get_info_by_fd"))
+ return NULL;
+
+ return &prog_info;
+}
+
+static int beef_search_original(const struct bpf_insn *insns, int n_insns, int *idx, int n_max)
+{
+ int i, n_found = 0;
+
+ for (i = 0; i < n_insns; i++) {
+ if (insns[i].imm == 0xbeef) {
+ if (!ASSERT_LT(n_found, n_max, "beef"))
+ return -1;
+ idx[n_found++] = i;
+ }
+ }
+
+ return n_found;
+}
+
+static int beef_search_xlated(struct bpf_prog_info *info, int *idx, int len)
+{
+ struct bpf_insn *insns = u64_to_ptr(info->xlated_prog_insns);
+ int tot = info->xlated_prog_len / 8;
+ int i, n = 0;
+
+ for (i = 0; i < tot; i++) {
+ if (insns[i].imm == 0xbeef) {
+ if (!ASSERT_LT(n, len, "beef"))
+ return -1;
+ idx[n++] = ((__u32 *)u64_to_ptr(info->orig_idx))[i];
+ }
+ }
+
+ return n;
+}
+
+static void beef_check(const struct bpf_program *prog, int n_expected)
+{
+ struct bpf_prog_info *prog_info;
+ int idx_expected[MAX_INSNS];
+ int idx[MAX_INSNS];
+ int prog_fd;
+ int n, i;
+
+ /*
+ * Find all beef instructions in the original program
+ */
+
+ n = beef_search_original(bpf_program__insns(prog),
+ bpf_program__insn_cnt(prog),
+ idx_expected, MAX_INSNS);
+ if (!ASSERT_EQ(n, n_expected, "search original insns"))
+ return;
+
+ /*
+ * Now find all the beef instructions in the xlated program and extract
+ * corresponding orig_idx mappings
+ */
+ prog_fd = bpf_program__fd(prog);
+ if (!ASSERT_GE(prog_fd, 0, "bpf_program__fd"))
+ return;
+
+ prog_info = prog_info_and_mappings(prog_fd);
+ if (!ASSERT_OK_PTR(prog_info, "prog_info_and_mappings"))
+ return;
+
+ if (!ASSERT_EQ(beef_search_xlated(prog_info, idx, n), n, "total # of beef"))
+ return;
+
+ /*
+ * Check that the orig_idx points to the correct original indexes
+ */
+ for (i = 0; i < n; i++)
+ ASSERT_EQ(idx[i], idx_expected[i], "beef index");
+}
+
+static void check_prog(const struct bpf_program *prog, int n_expected)
+{
+ struct bpf_link *link;
+
+ link = bpf_program__attach(prog);
+ if (!ASSERT_OK_PTR(link, "link"))
+ return;
+
+ beef_check(prog, n_expected);
+
+ bpf_link__destroy(link);
+}
+
+void test_bpf_insns_mappings(void)
+{
+ struct bpf_insns_mappings *skel;
+
+ skel = bpf_insns_mappings__open();
+ if (!ASSERT_OK_PTR(skel, "bpf_insns_mappings__open"))
+ return;
+
+ if (!ASSERT_OK(bpf_insns_mappings__load(skel),
+ "bpf_insns_mappings__load"))
+ return;
+
+ if (test__start_subtest("check_trivial_prog"))
+ check_prog(skel->progs.check_trivial_prog, 3);
+
+ if (test__start_subtest("check_simple_prog"))
+ check_prog(skel->progs.check_simple_prog, 3);
+
+ if (test__start_subtest("check_bpf_to_bpf"))
+ check_prog(skel->progs.check_bpf_to_bpf, 6);
+
+ if (test__start_subtest("check_prog_dead_code"))
+ check_prog(skel->progs.check_prog_dead_code, 13);
+
+ if (test__start_subtest("check_prog_dead_code_bpf_to_bpf"))
+ check_prog(skel->progs.check_prog_dead_code_bpf_to_bpf, 26);
+
+ bpf_insns_mappings__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/bpf_insns_mappings.c b/tools/testing/selftests/bpf/progs/bpf_insns_mappings.c
new file mode 100644
index 000000000000..f6ff690801ea
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/bpf_insns_mappings.c
@@ -0,0 +1,155 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Isovalent */
+
+#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, u64);
+} just_a_map SEC(".maps");
+
+static inline void beef(void)
+{
+ asm volatile("r8 = 0xbeef" ::: "r8");
+}
+
+static inline void cafe(void)
+{
+ asm volatile("r7 = 0xcafe" ::: "r7");
+}
+
+/*
+ * Trivial program: every insn maps to the original index
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_trivial_prog(void *ctx)
+{
+ beef();
+ cafe();
+ beef();
+ cafe();
+ beef();
+
+ return 0;
+}
+
+/* Some random instructions which will be patched for sure */
+static inline void beefify(void)
+{
+ __u32 key = 0;
+ __u64 *x;
+
+ beef();
+ bpf_printk("%llx", bpf_jiffies64());
+ beef();
+
+ key = !!bpf_jiffies64();
+ x = bpf_map_lookup_elem(&just_a_map, &key);
+ if (!x)
+ return;
+
+ beef();
+}
+
+/*
+ * Simple program: one section, no bpf-to-bpf calls, some patches
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_simple_prog(void *ctx)
+{
+ beefify();
+ return 0;
+}
+
+int __noinline foobar(int x)
+{
+ beefify();
+ return x;
+}
+
+/*
+ * Same simple program + a bpf-to-bpf call
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_bpf_to_bpf(void *ctx)
+{
+ beefify();
+
+ return foobar(0);
+}
+
+static inline void dead_code1(void)
+{
+ asm volatile("goto +0");
+}
+
+static inline void dead_code100(void)
+{
+# if defined(__clang__)
+# pragma clang loop unroll_count(100)
+# elif defined(__GNUC__)
+# pragma GCC unroll 100
+# else
+# error "unroll this loop, please"
+# endif
+ for (int i = 0; i < 100; i++)
+ asm volatile("goto +0");
+}
+
+/*
+ * Some beef instructions, patches, plus dead code
+ */
+static __always_inline void dead_beef(void)
+{
+ beef(); /* 1 beef */
+ dead_code1();
+ beef(); /* 1 beef */
+ dead_code1();
+ beef(); /* 1 beef */
+ dead_code100();
+ beef(); /* 1 beef */
+
+ dead_code100();
+ beefify(); /* 3 beef */
+ dead_code100();
+ beefify(); /* 3 beef */
+ dead_code1();
+ beefify(); /* 3 beef */
+
+ /* 13 beef insns total */
+}
+
+/*
+ * A program with some nops to be removed
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_prog_dead_code(void *ctx)
+{
+ dead_beef();
+
+ return 0;
+}
+
+int __noinline foobar2(int x)
+{
+ dead_beef();
+
+ return x;
+}
+
+/*
+ * A program with some nops to be removed + a bpf-to-bpf call to a similar func
+ */
+SEC("fentry/" SYS_PREFIX "sys_nanosleep")
+int check_prog_dead_code_bpf_to_bpf(void *ctx)
+{
+ dead_beef();
+
+ return foobar2(0);
+}
+
+char _license[] SEC("license") = "GPL";
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 5/9] bpftool: dump new fields of bpf prog info
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (3 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 4/9] selftests/bpf: Add tests for instructions mappings Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 6/9] bpf: add support for an extended JA instruction Anton Protopopov
` (4 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
When dumping prog info in JSON format add two new fields: "orig_insn"
and "jit". The former field maps the xlated instruction to the original
instruction (which was loaded via the bpf(2) syscall). The latter maps
the xlated instruction to the jitted instruction; as jited instructions
lengths may vary both the offset and length are specified.
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
tools/bpf/bpftool/prog.c | 14 ++++++++++++++
tools/bpf/bpftool/xlated_dumper.c | 18 ++++++++++++++++++
tools/bpf/bpftool/xlated_dumper.h | 2 ++
3 files changed, 34 insertions(+)
diff --git a/tools/bpf/bpftool/prog.c b/tools/bpf/bpftool/prog.c
index 9cb42a3366c0..d3fd7d699574 100644
--- a/tools/bpf/bpftool/prog.c
+++ b/tools/bpf/bpftool/prog.c
@@ -119,6 +119,12 @@ static int prep_prog_info(struct bpf_prog_info *const info, enum dump_mode mode,
holder.jited_line_info_rec_size = info->jited_line_info_rec_size;
needed += info->nr_jited_line_info * info->jited_line_info_rec_size;
+ holder.orig_idx_len = info->orig_idx_len;
+ needed += info->orig_idx_len;
+
+ holder.xlated_to_jit_len = info->xlated_to_jit_len;
+ needed += info->xlated_to_jit_len;
+
if (needed > *info_data_sz) {
ptr = realloc(*info_data, needed);
if (!ptr)
@@ -152,6 +158,12 @@ static int prep_prog_info(struct bpf_prog_info *const info, enum dump_mode mode,
holder.jited_line_info = ptr_to_u64(ptr);
ptr += holder.nr_jited_line_info * holder.jited_line_info_rec_size;
+ holder.orig_idx = ptr_to_u64(ptr);
+ ptr += holder.orig_idx_len;
+
+ holder.xlated_to_jit = ptr_to_u64(ptr);
+ ptr += holder.xlated_to_jit_len;
+
*info = holder;
return 0;
}
@@ -852,6 +864,8 @@ prog_dump(struct bpf_prog_info *info, enum dump_mode mode,
dd.func_info = func_info;
dd.finfo_rec_size = info->func_info_rec_size;
dd.prog_linfo = prog_linfo;
+ dd.orig_idx = u64_to_ptr(info->orig_idx);
+ dd.xlated_to_jit = u64_to_ptr(info->xlated_to_jit);
if (json_output)
dump_xlated_json(&dd, buf, member_len, opcodes, linum);
diff --git a/tools/bpf/bpftool/xlated_dumper.c b/tools/bpf/bpftool/xlated_dumper.c
index 567f56dfd9f1..fcc1c4a96178 100644
--- a/tools/bpf/bpftool/xlated_dumper.c
+++ b/tools/bpf/bpftool/xlated_dumper.c
@@ -270,6 +270,24 @@ void dump_xlated_json(struct dump_data *dd, void *buf, unsigned int len,
jsonw_name(json_wtr, "disasm");
print_bpf_insn(&cbs, insn + i, true);
+ if (dd->orig_idx) {
+ jsonw_name(json_wtr, "orig_insn");
+ jsonw_printf(json_wtr, "\"0x%x\"", dd->orig_idx[i]);
+ }
+
+ if (dd->xlated_to_jit) {
+ jsonw_name(json_wtr, "jit");
+ jsonw_start_object(json_wtr);
+
+ jsonw_name(json_wtr, "off");
+ jsonw_printf(json_wtr, "\"0x%x\"", dd->xlated_to_jit[i].off);
+
+ jsonw_name(json_wtr, "len");
+ jsonw_printf(json_wtr, "\"%d\"", dd->xlated_to_jit[i].len);
+
+ jsonw_end_object(json_wtr);
+ }
+
if (opcodes) {
jsonw_name(json_wtr, "opcodes");
jsonw_start_object(json_wtr);
diff --git a/tools/bpf/bpftool/xlated_dumper.h b/tools/bpf/bpftool/xlated_dumper.h
index db3ba0671501..078430fada17 100644
--- a/tools/bpf/bpftool/xlated_dumper.h
+++ b/tools/bpf/bpftool/xlated_dumper.h
@@ -26,6 +26,8 @@ struct dump_data {
__u32 finfo_rec_size;
const struct bpf_prog_linfo *prog_linfo;
char scratch_buff[SYM_MAX_NAME + 8];
+ unsigned int *orig_idx;
+ struct bpf_xlated_to_jit *xlated_to_jit;
};
void kernel_syms_load(struct dump_data *dd);
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 6/9] bpf: add support for an extended JA instruction
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (4 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 5/9] bpftool: dump new fields of bpf prog info Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 7/9] bpf: Add kernel/bpftool asm support for new instructions Anton Protopopov
` (3 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: 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 were 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.
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 a80b8c1e7afe..b291b5c79d26 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -1131,6 +1131,15 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op)
*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)))
/* mov rax, qword ptr [rbp - rounded_stack_depth - 8] */
@@ -2016,9 +2025,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 c874f354c290..aca5ed065731 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -1412,6 +1412,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 270dc0a26d03..003b54fbc6d9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -15630,14 +15630,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);
+
+ ret = push_insn(t, t + 1, FALLTHROUGH, env);
+ if (ret)
+ return ret;
- mark_prune_point(env, t + off + 1);
- mark_jmp_point(env, t + off + 1);
+ 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:
@@ -17607,8 +17617,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)) {
@@ -17617,9 +17630,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 c874f354c290..aca5ed065731 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -1412,6 +1412,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
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 7/9] bpf: Add kernel/bpftool asm support for new instructions
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (5 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 6/9] bpf: add support for an extended JA instruction Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 8/9] bpf: add BPF_STATIC_BRANCH_UPDATE syscall Anton Protopopov
` (2 subsequent siblings)
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: 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 49940c26a227..5c8ee230ee5a 100644
--- a/kernel/bpf/disasm.c
+++ b/kernel/bpf/disasm.c
@@ -166,6 +166,30 @@ static bool is_movsx(const struct bpf_insn *insn)
(insn->off == 8 || insn->off == 16 || insn->off == 32);
}
+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)
@@ -319,12 +343,9 @@ 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_JMP32 | BPF_JA)) {
- verbose(cbs->private_data, "(%02x) gotol pc%+d\n",
- insn->code, insn->imm);
+ } 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_EXIT)) {
verbose(cbs->private_data, "(%02x) exit\n", insn->code);
} else if (BPF_SRC(insn->code) == BPF_X) {
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 8/9] bpf: add BPF_STATIC_BRANCH_UPDATE syscall
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (6 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 7/9] bpf: Add kernel/bpftool asm support for new instructions Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 16:28 ` [PATCH v1 bpf-next 9/9] selftests/bpf: Add tests for new ja* instructions Anton Protopopov
2024-02-02 22:39 ` [PATCH v1 bpf-next 0/9] BPF static branches Andrii Nakryiko
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
Add a new bpf system call, BPF_STATIC_BRANCH_UPDATE, which allows users to
update static branches in BPF. Namely, this system call is executed as
bpf(BPF_STATIC_BRANCH_UPDATE, attrs={prog_fd, insn_off, on})
where prog_fd points to a BPF program, insn_off is an _xlated_ offset in
this program, on is a boolean value to set this branch on or off.
The instruction at insn_off must be a JA with SRC_REG or'ed with
BPF_STATIC_BRANCH_JA and, optionally, with BPF_STATIC_BRANCH_INVERSE.
To implement this for a particular architecture, re-define the weak
bpf_arch_poke_static_branch() function in the corresponding bpf_jit_comp.c
This patch adds x86 implementation.
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
arch/x86/net/bpf_jit_comp.c | 40 +++++++++++++++++++++++
include/linux/bpf.h | 2 ++
include/linux/filter.h | 1 +
include/uapi/linux/bpf.h | 7 ++++
kernel/bpf/core.c | 5 +++
kernel/bpf/syscall.c | 60 ++++++++++++++++++++++++++++++++++
tools/include/uapi/linux/bpf.h | 7 ++++
7 files changed, 122 insertions(+)
diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index b291b5c79d26..2090713e4126 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -2099,8 +2099,17 @@ st: if (is_imm8(insn->off))
if (func_idx)
off += bpf_prog->aux->func_info[func_idx].insn_off;
+ bpf_prog->aux->xlated_to_jit[off].ip = image + proglen;
bpf_prog->aux->xlated_to_jit[off].off = proglen;
bpf_prog->aux->xlated_to_jit[off].len = ilen;
+
+ /*
+ * Save the offset so that it can later be accessed
+ * by the bpf(BPF_STATIC_BRANCH_UPDATE) syscall
+ */
+ if (insn->code == (BPF_JMP | BPF_JA) ||
+ insn->code == (BPF_JMP32 | BPF_JA))
+ bpf_prog->aux->xlated_to_jit[off].jmp_offset = jmp_offset;
}
}
proglen += ilen;
@@ -3276,3 +3285,34 @@ bool bpf_jit_supports_ptr_xchg(void)
{
return true;
}
+
+int bpf_arch_poke_static_branch(struct bpf_prog *prog,
+ u32 insn_off,
+ bool on)
+{
+ int jmp_offset = prog->aux->xlated_to_jit[insn_off].jmp_offset;
+ u32 len = prog->aux->xlated_to_jit[insn_off].len;
+ u8 op[5];
+
+ 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);
+ }
+
+ text_poke_bp(prog->aux->xlated_to_jit[insn_off].ip, op, len, NULL);
+
+ return 0;
+}
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index bdd6be718e82..1363b1fc8c09 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1528,8 +1528,10 @@ struct bpf_prog_aux {
* instructions, if allocated
*/
struct {
+ void *ip; /* the address of the jitted insn */
u32 off; /* local offset in the jitted code */
u32 len; /* the total len of generated jit code */
+ u32 jmp_offset; /* jitted jump offset for BPF_JA insns */
} *xlated_to_jit;
};
diff --git a/include/linux/filter.h b/include/linux/filter.h
index fee070b9826e..0dad44fa3af2 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -957,6 +957,7 @@ bool bpf_jit_supports_far_kfunc_call(void);
bool bpf_jit_supports_exceptions(void);
bool bpf_jit_supports_ptr_xchg(void);
void arch_bpf_stack_walk(bool (*consume_fn)(void *cookie, u64 ip, u64 sp, u64 bp), void *cookie);
+int bpf_arch_poke_static_branch(struct bpf_prog *prog, u32 off, bool on);
bool bpf_helper_changes_pkt_data(void *func);
static inline bool bpf_dump_raw_ok(const struct cred *cred)
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index aca5ed065731..8aafb0eddd1c 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -932,6 +932,7 @@ enum bpf_cmd {
BPF_LINK_DETACH,
BPF_PROG_BIND_MAP,
BPF_TOKEN_CREATE,
+ BPF_STATIC_BRANCH_UPDATE,
__MAX_BPF_CMD,
};
@@ -1787,6 +1788,12 @@ union bpf_attr {
__u32 bpffs_fd;
} token_create;
+ struct { /* struct used by BPF_STATIC_BRANCH_UPDATE command */
+ __u32 prog_fd;
+ __u32 insn_off;
+ __u32 on;
+ } static_branch;
+
} __attribute__((aligned(8)));
/* The description below is an attempt at providing documentation to eBPF
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 8e99c1563a7f..fec185354ea3 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -3042,6 +3042,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_prog *prog, u32 off, 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 36b8fdcfba75..9e2e12a0bdfe 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1540,6 +1540,63 @@ static int map_lookup_elem(union bpf_attr *attr)
return err;
}
+static int parse_static_branch_insn(struct bpf_insn *insn, bool *inverse)
+{
+ __u8 code = insn->code;
+
+ if (code != (BPF_JMP | BPF_JA) && code != (BPF_JMP32 | BPF_JA))
+ return -EINVAL;
+
+ if (insn->src_reg & ~BPF_STATIC_BRANCH_MASK)
+ return -EINVAL;
+
+ if (!(insn->src_reg & BPF_STATIC_BRANCH_JA))
+ return -EINVAL;
+
+ if (insn->dst_reg)
+ return -EINVAL;
+
+ *inverse = !(insn->src_reg & BPF_STATIC_BRANCH_NOP);
+
+ return 0;
+}
+
+#define BPF_STATIC_BRANCH_UPDATE_LAST_FIELD static_branch.on
+
+static int bpf_static_branch_update(union bpf_attr *attr)
+{
+ bool on = attr->static_branch.on & 1;
+ struct bpf_prog *prog;
+ u32 insn_off;
+ bool inverse;
+ int ret;
+
+ if (CHECK_ATTR(BPF_STATIC_BRANCH_UPDATE))
+ return -EINVAL;
+
+ if (attr->static_branch.on & ~1)
+ return -EINVAL;
+
+ prog = bpf_prog_get(attr->static_branch.prog_fd);
+ if (IS_ERR(prog))
+ return PTR_ERR(prog);
+
+ insn_off = attr->static_branch.insn_off;
+ if (insn_off >= prog->len) {
+ ret = -ERANGE;
+ goto put_prog;
+ }
+
+ ret = parse_static_branch_insn(&prog->insnsi[insn_off], &inverse);
+ if (ret)
+ goto put_prog;
+
+ ret = bpf_arch_poke_static_branch(prog, insn_off, on ^ inverse);
+
+put_prog:
+ bpf_prog_put(prog);
+ return ret;
+}
#define BPF_MAP_UPDATE_ELEM_LAST_FIELD flags
@@ -5694,6 +5751,9 @@ static int __sys_bpf(int cmd, bpfptr_t uattr, unsigned int size)
case BPF_MAP_DELETE_BATCH:
err = bpf_map_do_batch(&attr, uattr.user, BPF_MAP_DELETE_BATCH);
break;
+ case BPF_STATIC_BRANCH_UPDATE:
+ err = bpf_static_branch_update(&attr);
+ break;
case BPF_LINK_CREATE:
err = link_create(&attr, uattr);
break;
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index aca5ed065731..8aafb0eddd1c 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -932,6 +932,7 @@ enum bpf_cmd {
BPF_LINK_DETACH,
BPF_PROG_BIND_MAP,
BPF_TOKEN_CREATE,
+ BPF_STATIC_BRANCH_UPDATE,
__MAX_BPF_CMD,
};
@@ -1787,6 +1788,12 @@ union bpf_attr {
__u32 bpffs_fd;
} token_create;
+ struct { /* struct used by BPF_STATIC_BRANCH_UPDATE command */
+ __u32 prog_fd;
+ __u32 insn_off;
+ __u32 on;
+ } static_branch;
+
} __attribute__((aligned(8)));
/* The description below is an attempt at providing documentation to eBPF
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* [PATCH v1 bpf-next 9/9] selftests/bpf: Add tests for new ja* instructions
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (7 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 8/9] bpf: add BPF_STATIC_BRANCH_UPDATE syscall Anton Protopopov
@ 2024-02-02 16:28 ` Anton Protopopov
2024-02-02 22:39 ` [PATCH v1 bpf-next 0/9] BPF static branches Andrii Nakryiko
9 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-02 16:28 UTC (permalink / raw)
To: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
Cc: Anton Protopopov
Add several self-tests to test the new instructions and the new
BPF_STATIC_BRANCH_UPDATE syscall.
Signed-off-by: Anton Protopopov <aspsk@isovalent.com>
---
.../bpf/prog_tests/bpf_static_branches.c | 269 ++++++++++++++++++
1 file changed, 269 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c
diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c b/tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c
new file mode 100644
index 000000000000..6f54002e6e15
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c
@@ -0,0 +1,269 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2024 Isovalent */
+
+#include <test_progs.h>
+
+#include <sys/syscall.h>
+#include <bpf/bpf.h>
+
+static inline int _bpf_prog_load(struct bpf_insn *insns, __u32 insn_cnt)
+{
+ union bpf_attr attr = {
+ .prog_type = BPF_PROG_TYPE_XDP, /* we don't care */
+ .insns = ptr_to_u64(insns),
+ .insn_cnt = insn_cnt,
+ .license = ptr_to_u64("GPL"),
+ };
+
+ return syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+}
+
+enum {
+ OFF,
+ ON
+};
+
+static inline int bpf_static_branch_update(int prog_fd, __u32 insn_off, __u32 on)
+{
+ union bpf_attr attr = {
+ .static_branch.prog_fd = (__u32)prog_fd,
+ .static_branch.insn_off = insn_off,
+ .static_branch.on = on,
+ };
+
+ return syscall(__NR_bpf, BPF_STATIC_BRANCH_UPDATE, &attr, sizeof(attr));
+}
+
+#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_ops(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(),
+ };
+ union bpf_attr attr = {
+ .prog_type = BPF_PROG_TYPE_XDP,
+ .insns = ptr_to_u64(insns),
+ .insn_cnt = ARRAY_SIZE(insns),
+ .license = ptr_to_u64("GPL"),
+ };
+ 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], -1, "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], -1, "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], -1, "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], -1, "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], -1, "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], -1, "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], -1, "incorrect field"))
+ return;
+ }
+}
+
+static void check_syscall(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(),
+ };
+ union bpf_attr attr = {
+ .prog_type = BPF_PROG_TYPE_XDP,
+ .insns = ptr_to_u64(insns),
+ .insn_cnt = ARRAY_SIZE(insns),
+ .license = ptr_to_u64("GPL"),
+ };
+ bool stop = false;
+ int prog_fd[4];
+ __u32 insn_off;
+ int ret;
+ 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;
+ }
+
+ if (stop)
+ goto end;
+
+ for (i = 0; i < 4; i++) {
+ /* we can set branch off */
+ ret = bpf_static_branch_update(prog_fd[i], 0, OFF);
+ if (!ASSERT_EQ(ret, 0, "correct update"))
+ goto end;
+
+ /* we can set branch on */
+ ret = bpf_static_branch_update(prog_fd[i], 0, ON);
+ if (!ASSERT_EQ(ret, 0, "correct update"))
+ goto end;
+
+ /* incorrect.static_branch.on: can only be 0|1 */
+ ret = bpf_static_branch_update(prog_fd[i], 0, 2);
+ if (!ASSERT_EQ(ret, -1, "incorrect static_branch.on value"))
+ goto end;
+
+ /* incorrect static_branch.insn_off: can only be 0 in this case */
+ for (insn_off = 1; insn_off < 5; insn_off++) {
+ ret = bpf_static_branch_update(prog_fd[i], insn_off, OFF);
+ if (!ASSERT_EQ(ret, -1, "incorrect insn_off: not a correct insns"))
+ goto end;
+ if (!ASSERT_EQ(errno, EINVAL, "incorrect insn_off: not a correct insns"))
+ goto end;
+ }
+ ret = bpf_static_branch_update(prog_fd[i], 666, OFF);
+ if (!ASSERT_EQ(ret, -1, "incorrect insn_off: out of range"))
+ goto end;
+ if (!ASSERT_EQ(errno, ERANGE, "incorrect insn_off: out puf range"))
+ goto end;
+
+ /* bad file descriptor: no open file */
+ ret = bpf_static_branch_update(-1, 0, OFF);
+ if (!ASSERT_EQ(ret, -1, "incorrect prog_fd: no file"))
+ goto end;
+ if (!ASSERT_EQ(errno, EBADF, "incorrect prog_fd: no file"))
+ goto end;
+
+ /* bad file descriptor: not a bpf prog */
+ ret = bpf_static_branch_update(0, 0, OFF);
+ if (!ASSERT_EQ(ret, -1, "incorrect prog_fd: not a bpf prog"))
+ goto end;
+ if (!ASSERT_EQ(errno, EINVAL, "incorrect prog_fd: not a bpf prog"))
+ goto end;
+ }
+
+end:
+ for (i = 0; i < 4; i++)
+ close(prog_fd[i]);
+
+}
+
+void test_bpf_static_branches(void)
+{
+ if (test__start_subtest("check_ops"))
+ check_ops();
+
+ if (test__start_subtest("check_syscall"))
+ check_syscall();
+}
--
2.34.1
^ permalink raw reply related [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 0/9] BPF static branches
2024-02-02 16:28 [PATCH v1 bpf-next 0/9] BPF static branches Anton Protopopov
` (8 preceding siblings ...)
2024-02-02 16:28 ` [PATCH v1 bpf-next 9/9] selftests/bpf: Add tests for new ja* instructions Anton Protopopov
@ 2024-02-02 22:39 ` Andrii Nakryiko
2024-02-04 16:05 ` Anton Protopopov
9 siblings, 1 reply; 32+ messages in thread
From: Andrii Nakryiko @ 2024-02-02 22:39 UTC (permalink / raw)
To: Anton Protopopov
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
>
> This series adds support for mapping between xlated and original
> instructions offsets, mapping between xlated and jitted instructions
> offsets (x86), support for two new BPF instruction JA[SRC=1]
> (goto[l]_or_nop) and JA[SRC=3] (nop_or_goto[l]), and a new syscall to
> configure the jitted values of such instructions.
>
> This a follow up to the previous attempt to add static keys support
> (see [1], [2]) which implements lower-level functionality than what
> was proposed before.
>
> The first patch .
> The second patch adds xlated -> original mapping.
> The third patch adds .
>
> The fourth patch adds support for new instructions.
> And the fifth patch adds support for new syscall.
>
> The following patches are included:
> Patch 1 is a formal bug fix
> Patch 2 adds the xlated -> original mapping
> Patch 3 adds the xlated -> jitted mapping
> Patch 4 adds tests for instructions mappings
> Patch 5 adds bpftool support for printing new instructions
> Patch 6 add support for an extended JA instruction
> Patch 7 add support for kernel/bpftool to display new instructions
> Patch 8 adds a new BPF_STATIC_BRANCH_UPDATE syscall
> Patch 9 adds tests for the new ja* instructions and the new syscall
>
> Altogether this provides enough functionality to dynamically patch
> programs and support simple static keys.
>
> rfc -> v1:
> - converted to v1 based on the feedback (there was none)
> - bpftool support was added to dump new instructions
> - self-tests were added
> - minor fixes & checkpatch warnings
>
> [1] https://lpc.events/event/17/contributions/1608/attachments/1278/2578/bpf-static-keys.pdf
> [2] https://lore.kernel.org/bpf/20231206141030.1478753-1-aspsk@isovalent.com/
> [3] https://github.com/llvm/llvm-project/pull/75110
>
> Anton Protopopov (9):
> bpf: fix potential error return
> bpf: keep track of and expose xlated insn offsets
> bpf: expose how xlated insns map to jitted insns
> selftests/bpf: Add tests for instructions mappings
> bpftool: dump new fields of bpf prog info
> bpf: add support for an extended JA instruction
> bpf: Add kernel/bpftool asm support for new instructions
> bpf: add BPF_STATIC_BRANCH_UPDATE syscall
> selftests/bpf: Add tests for new ja* instructions
>
> arch/x86/net/bpf_jit_comp.c | 73 ++++-
> include/linux/bpf.h | 11 +
> include/linux/bpf_verifier.h | 1 -
> include/linux/filter.h | 1 +
> include/uapi/linux/bpf.h | 26 ++
> kernel/bpf/core.c | 67 ++++-
> kernel/bpf/disasm.c | 33 ++-
> kernel/bpf/syscall.c | 115 ++++++++
> kernel/bpf/verifier.c | 58 +++-
> tools/bpf/bpftool/prog.c | 14 +
> tools/bpf/bpftool/xlated_dumper.c | 18 ++
> tools/bpf/bpftool/xlated_dumper.h | 2 +
> tools/include/uapi/linux/bpf.h | 26 ++
> .../bpf/prog_tests/bpf_insns_mappings.c | 156 ++++++++++
> .../bpf/prog_tests/bpf_static_branches.c | 269 ++++++++++++++++++
> .../selftests/bpf/progs/bpf_insns_mappings.c | 155 ++++++++++
> 16 files changed, 1002 insertions(+), 23 deletions(-)
> create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c
> create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c
> create mode 100644 tools/testing/selftests/bpf/progs/bpf_insns_mappings.c
>
> --
> 2.34.1
>
This fails to build in CI ([0]). I'll take a look at the patches next
week, sorry for the delay.
[0] https://github.com/kernel-patches/bpf/actions/runs/7762232524/job/21172303431?pr=6380#step:11:77
^ permalink raw reply [flat|nested] 32+ messages in thread* Re: [PATCH v1 bpf-next 0/9] BPF static branches
2024-02-02 22:39 ` [PATCH v1 bpf-next 0/9] BPF static branches Andrii Nakryiko
@ 2024-02-04 16:05 ` Anton Protopopov
0 siblings, 0 replies; 32+ messages in thread
From: Anton Protopopov @ 2024-02-04 16:05 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann, Jiri Olsa,
Martin KaFai Lau, Stanislav Fomichev, Yonghong Song,
Eduard Zingerman, Quentin Monnet, bpf
On Fri, Feb 02, 2024 at 02:39:24PM -0800, Andrii Nakryiko wrote:
> On Fri, Feb 2, 2024 at 8:34 AM Anton Protopopov <aspsk@isovalent.com> wrote:
> >
> > This series adds support for mapping between xlated and original
> > instructions offsets, mapping between xlated and jitted instructions
> > offsets (x86), support for two new BPF instruction JA[SRC=1]
> > (goto[l]_or_nop) and JA[SRC=3] (nop_or_goto[l]), and a new syscall to
> > configure the jitted values of such instructions.
> >
> > This a follow up to the previous attempt to add static keys support
> > (see [1], [2]) which implements lower-level functionality than what
> > was proposed before.
> >
> > The first patch .
> > The second patch adds xlated -> original mapping.
> > The third patch adds .
> >
> > The fourth patch adds support for new instructions.
> > And the fifth patch adds support for new syscall.
> >
> > The following patches are included:
> > Patch 1 is a formal bug fix
> > Patch 2 adds the xlated -> original mapping
> > Patch 3 adds the xlated -> jitted mapping
> > Patch 4 adds tests for instructions mappings
> > Patch 5 adds bpftool support for printing new instructions
> > Patch 6 add support for an extended JA instruction
> > Patch 7 add support for kernel/bpftool to display new instructions
> > Patch 8 adds a new BPF_STATIC_BRANCH_UPDATE syscall
> > Patch 9 adds tests for the new ja* instructions and the new syscall
> >
> > Altogether this provides enough functionality to dynamically patch
> > programs and support simple static keys.
> >
> > rfc -> v1:
> > - converted to v1 based on the feedback (there was none)
> > - bpftool support was added to dump new instructions
> > - self-tests were added
> > - minor fixes & checkpatch warnings
> >
> > [1] https://lpc.events/event/17/contributions/1608/attachments/1278/2578/bpf-static-keys.pdf
> > [2] https://lore.kernel.org/bpf/20231206141030.1478753-1-aspsk@isovalent.com/
> > [3] https://github.com/llvm/llvm-project/pull/75110
> >
> > Anton Protopopov (9):
> > bpf: fix potential error return
> > bpf: keep track of and expose xlated insn offsets
> > bpf: expose how xlated insns map to jitted insns
> > selftests/bpf: Add tests for instructions mappings
> > bpftool: dump new fields of bpf prog info
> > bpf: add support for an extended JA instruction
> > bpf: Add kernel/bpftool asm support for new instructions
> > bpf: add BPF_STATIC_BRANCH_UPDATE syscall
> > selftests/bpf: Add tests for new ja* instructions
> >
> > arch/x86/net/bpf_jit_comp.c | 73 ++++-
> > include/linux/bpf.h | 11 +
> > include/linux/bpf_verifier.h | 1 -
> > include/linux/filter.h | 1 +
> > include/uapi/linux/bpf.h | 26 ++
> > kernel/bpf/core.c | 67 ++++-
> > kernel/bpf/disasm.c | 33 ++-
> > kernel/bpf/syscall.c | 115 ++++++++
> > kernel/bpf/verifier.c | 58 +++-
> > tools/bpf/bpftool/prog.c | 14 +
> > tools/bpf/bpftool/xlated_dumper.c | 18 ++
> > tools/bpf/bpftool/xlated_dumper.h | 2 +
> > tools/include/uapi/linux/bpf.h | 26 ++
> > .../bpf/prog_tests/bpf_insns_mappings.c | 156 ++++++++++
> > .../bpf/prog_tests/bpf_static_branches.c | 269 ++++++++++++++++++
> > .../selftests/bpf/progs/bpf_insns_mappings.c | 155 ++++++++++
> > 16 files changed, 1002 insertions(+), 23 deletions(-)
> > create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_insns_mappings.c
> > create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_static_branches.c
> > create mode 100644 tools/testing/selftests/bpf/progs/bpf_insns_mappings.c
> >
> > --
> > 2.34.1
> >
>
> This fails to build in CI ([0]). I'll take a look at the patches next
> week, sorry for the delay.
Thanks Andrii!
> [0] https://github.com/kernel-patches/bpf/actions/runs/7762232524/job/21172303431?pr=6380#step:11:77
Thanks, I will push a fix for this and some more fixes in v2 (besides
this doc build failure there's a missing mutex for poking text and
one NULL deref).
^ permalink raw reply [flat|nested] 32+ messages in thread