From: Eduard Zingerman <eddyz87@gmail.com>
To: bpf@vger.kernel.org, ast@kernel.org, andrii@kernel.org
Cc: daniel@iogearbox.net, martin.lau@linux.dev, kernel-team@fb.com,
yonghong.song@linux.dev, eddyz87@gmail.com
Subject: [PATCH bpf-next v1 10/10] bpf: table based bpf_insn_successors()
Date: Wed, 10 Sep 2025 18:04:35 -0700 [thread overview]
Message-ID: <20250911010437.2779173-11-eddyz87@gmail.com> (raw)
In-Reply-To: <20250911010437.2779173-1-eddyz87@gmail.com>
Converting bpf_insn_successors() to use lookup table makes it ~1.5
times faster.
Also remove unnecessary conditionals:
- `idx + 1 < prog->len` is unnecessary because after check_cfg() all
jump targets are guaranteed to be within a program;
- `i == 0 || succ[0] != dst` is unnecessary because any client of
bpf_insn_successors() can handle duplicate edges:
- compute_live_registers()
- compute_scc()
Moving bpf_insn_successors() to liveness.c allows its inlining in
liveness.c:__update_stack_liveness().
Such inlining speeds up __update_stack_liveness() by ~40%.
bpf_insn_successors() is used in both verifier.c and liveness.c.
perf shows such move does not negatively impact users in verifier.c,
as these are executed only once before main varification pass.
Unlike __update_stack_liveness() which can be triggered multiple
times.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
include/linux/bpf_verifier.h | 1 +
kernel/bpf/liveness.c | 51 +++++++++++++++++++++++++
kernel/bpf/verifier.c | 72 +-----------------------------------
3 files changed, 53 insertions(+), 71 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index c7515da8500c..4c497e839526 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -1049,6 +1049,7 @@ void print_insn_state(struct bpf_verifier_env *env, const struct bpf_verifier_st
u32 frameno);
struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *env, int off);
+int bpf_jmp_offset(struct bpf_insn *insn);
int bpf_insn_successors(struct bpf_prog *prog, u32 idx, u32 succ[2]);
void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx);
diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
index 2b2e909ec944..6fb79a63d216 100644
--- a/kernel/bpf/liveness.c
+++ b/kernel/bpf/liveness.c
@@ -428,6 +428,57 @@ static void log_mask_change(struct bpf_verifier_env *env, struct callchain *call
bpf_log(&env->log, "\n");
}
+int bpf_jmp_offset(struct bpf_insn *insn)
+{
+ u8 code = insn->code;
+
+ if (code == (BPF_JMP32 | BPF_JA))
+ return insn->imm;
+ return insn->off;
+}
+
+inline int bpf_insn_successors(struct bpf_prog *prog, u32 idx, u32 succ[2])
+{
+ static const struct opcode_info {
+ bool can_jump;
+ bool can_fallthrough;
+ } opcode_info_tbl[256] = {
+ [0 ... 255] = {.can_jump = false, .can_fallthrough = true},
+ #define _J(code, ...) \
+ [BPF_JMP | code] = __VA_ARGS__, \
+ [BPF_JMP32 | code] = __VA_ARGS__
+
+ _J(BPF_EXIT, {.can_jump = false, .can_fallthrough = false}),
+ _J(BPF_JA, {.can_jump = true, .can_fallthrough = false}),
+ _J(BPF_JEQ, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JNE, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JLT, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JLE, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JGT, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JGE, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JSGT, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JSGE, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JSLT, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JSLE, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JCOND, {.can_jump = true, .can_fallthrough = true}),
+ _J(BPF_JSET, {.can_jump = true, .can_fallthrough = true}),
+ #undef _J
+ };
+ struct bpf_insn *insn = &prog->insnsi[idx];
+ const struct opcode_info *opcode_info;
+ int i = 0, insn_sz;
+
+ opcode_info = &opcode_info_tbl[BPF_CLASS(insn->code) | BPF_OP(insn->code)];
+ insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
+ if (opcode_info->can_fallthrough)
+ succ[i++] = idx + insn_sz;
+
+ if (opcode_info->can_jump)
+ succ[i++] = idx + bpf_jmp_offset(insn) + 1;
+
+ return i;
+}
+
static struct func_instance *get_outer_instance(struct bpf_verifier_env *env,
struct func_instance *instance)
{
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6efb555a1e8a..9fd75a3e45b3 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3470,15 +3470,6 @@ static int add_subprog_and_kfunc(struct bpf_verifier_env *env)
return 0;
}
-static int jmp_offset(struct bpf_insn *insn)
-{
- u8 code = insn->code;
-
- if (code == (BPF_JMP32 | BPF_JA))
- return insn->imm;
- return insn->off;
-}
-
static int check_subprogs(struct bpf_verifier_env *env)
{
int i, subprog_start, subprog_end, off, cur_subprog = 0;
@@ -3505,7 +3496,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
goto next;
if (BPF_OP(code) == BPF_EXIT || BPF_OP(code) == BPF_CALL)
goto next;
- off = i + jmp_offset(&insn[i]) + 1;
+ off = i + bpf_jmp_offset(&insn[i]) + 1;
if (off < subprog_start || off >= subprog_end) {
verbose(env, "jump out of range from insn %d to %d\n", i, off);
return -EINVAL;
@@ -23907,67 +23898,6 @@ static int process_fd_array(struct bpf_verifier_env *env, union bpf_attr *attr,
return 0;
}
-static bool can_fallthrough(struct bpf_insn *insn)
-{
- u8 class = BPF_CLASS(insn->code);
- u8 opcode = BPF_OP(insn->code);
-
- if (class != BPF_JMP && class != BPF_JMP32)
- return true;
-
- if (opcode == BPF_EXIT || opcode == BPF_JA)
- return false;
-
- return true;
-}
-
-static bool can_jump(struct bpf_insn *insn)
-{
- u8 class = BPF_CLASS(insn->code);
- u8 opcode = BPF_OP(insn->code);
-
- if (class != BPF_JMP && class != BPF_JMP32)
- return false;
-
- switch (opcode) {
- case BPF_JA:
- case BPF_JEQ:
- case BPF_JNE:
- case BPF_JLT:
- case BPF_JLE:
- case BPF_JGT:
- case BPF_JGE:
- case BPF_JSGT:
- case BPF_JSGE:
- case BPF_JSLT:
- case BPF_JSLE:
- case BPF_JCOND:
- case BPF_JSET:
- return true;
- }
-
- return false;
-}
-
-int bpf_insn_successors(struct bpf_prog *prog, u32 idx, u32 succ[2])
-{
- struct bpf_insn *insn = &prog->insnsi[idx];
- int i = 0, insn_sz;
- u32 dst;
-
- insn_sz = bpf_is_ldimm64(insn) ? 2 : 1;
- if (can_fallthrough(insn) && idx + 1 < prog->len)
- succ[i++] = idx + insn_sz;
-
- if (can_jump(insn)) {
- dst = idx + jmp_offset(insn) + 1;
- if (i == 0 || succ[0] != dst)
- succ[i++] = dst;
- }
-
- return i;
-}
-
/* Each field is a register bitmask */
struct insn_live_regs {
u16 use; /* registers read by instruction */
--
2.47.3
next prev parent reply other threads:[~2025-09-11 1:05 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-09-11 1:04 [PATCH bpf-next v1 00/10] bpf: replace path-sensitive with path-insensitive live stack analysis Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 01/10] bpf: bpf_verifier_state->cleaned flag instead of REG_LIVE_DONE Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 02/10] bpf: use compute_live_registers() info in clean_func_state Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 03/10] bpf: remove redundant REG_LIVE_READ check in stacksafe() Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 04/10] bpf: declare a few utility functions as internal api Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 05/10] bpf: compute instructions postorder per subprogram Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 06/10] bpf: callchain sensitive stack liveness tracking using CFG Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 07/10] bpf: enable callchain sensitive stack liveness tracking Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 08/10] bpf: signal error if old liveness is more conservative than new Eduard Zingerman
2025-09-11 1:04 ` [PATCH bpf-next v1 09/10] bpf: disable and remove registers chain based liveness Eduard Zingerman
2025-09-11 14:19 ` kernel test robot
2025-09-11 21:26 ` Eduard Zingerman
2025-09-11 22:00 ` Alexei Starovoitov
2025-09-11 22:07 ` Eduard Zingerman
2025-09-12 8:17 ` Dan Carpenter
2025-09-12 16:48 ` Eduard Zingerman
2025-09-11 1:04 ` Eduard Zingerman [this message]
2025-09-11 6:57 ` [syzbot ci] Re: bpf: replace path-sensitive with path-insensitive live stack analysis syzbot ci
2025-09-11 21:09 ` Eduard Zingerman
2025-09-11 21:58 ` Alexei Starovoitov
2025-09-11 22:06 ` Eduard Zingerman
2025-09-11 22:11 ` Alexei Starovoitov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250911010437.2779173-11-eddyz87@gmail.com \
--to=eddyz87@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=kernel-team@fb.com \
--cc=martin.lau@linux.dev \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox