* [PATCH bpf-next v2] bpf: Refactor check_cfg to use a structured loop.
@ 2020-11-21 1:55 Wedson Almeida Filho
2020-11-25 6:40 ` patchwork-bot+netdevbpf
0 siblings, 1 reply; 3+ messages in thread
From: Wedson Almeida Filho @ 2020-11-21 1:55 UTC (permalink / raw)
To: bpf, daniel; +Cc: ast, Wedson Almeida Filho
The current implementation uses a number of gotos to implement a loop
and different paths within the loop, which makes the code less readable
than it would be with an explicit while-loop. This patch also replaces a
chain of if/if-elses keyed on the same expression with a switch
statement.
No change in behaviour is intended.
Signed-off-by: Wedson Almeida Filho <wedsonaf@google.com>
---
kernel/bpf/verifier.c | 179 ++++++++++++++++++++++--------------------
1 file changed, 95 insertions(+), 84 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fb2943ea715d..e333ce43f281 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8047,6 +8047,11 @@ static void init_explored_state(struct bpf_verifier_env *env, int idx)
env->insn_aux_data[idx].prune_point = true;
}
+enum {
+ DONE_EXPLORING = 0,
+ KEEP_EXPLORING = 1,
+};
+
/* t, w, e - match pseudo-code above:
* t - index of current instruction
* w - next instruction
@@ -8059,10 +8064,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
int *insn_state = env->cfg.insn_state;
if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
- return 0;
+ return DONE_EXPLORING;
if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
- return 0;
+ return DONE_EXPLORING;
if (w < 0 || w >= env->prog->len) {
verbose_linfo(env, t, "%d: ", t);
@@ -8081,10 +8086,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
if (env->cfg.cur_stack >= env->prog->len)
return -E2BIG;
insn_stack[env->cfg.cur_stack++] = w;
- return 1;
+ return KEEP_EXPLORING;
} else if ((insn_state[w] & 0xF0) == DISCOVERED) {
if (loop_ok && env->bpf_capable)
- return 0;
+ return DONE_EXPLORING;
verbose_linfo(env, t, "%d: ", t);
verbose_linfo(env, w, "%d: ", w);
verbose(env, "back-edge from insn %d to %d\n", t, w);
@@ -8096,7 +8101,74 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
verbose(env, "insn state internal bug\n");
return -EFAULT;
}
- return 0;
+ return DONE_EXPLORING;
+}
+
+/* Visits the instruction at index t and returns one of the following:
+ * < 0 - an error occurred
+ * DONE_EXPLORING - the instruction was fully explored
+ * KEEP_EXPLORING - there is still work to be done before it is fully explored
+ */
+static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
+{
+ struct bpf_insn *insns = env->prog->insnsi;
+ int ret;
+
+ /* All non-branch instructions have a single fall-through edge. */
+ if (BPF_CLASS(insns[t].code) != BPF_JMP &&
+ BPF_CLASS(insns[t].code) != BPF_JMP32)
+ return push_insn(t, t + 1, FALLTHROUGH, env, false);
+
+ switch (BPF_OP(insns[t].code)) {
+ case BPF_EXIT:
+ return DONE_EXPLORING;
+
+ case BPF_CALL:
+ ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
+ if (ret)
+ return ret;
+
+ if (t + 1 < insn_cnt)
+ init_explored_state(env, t + 1);
+ if (insns[t].src_reg == BPF_PSEUDO_CALL) {
+ init_explored_state(env, t);
+ ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
+ env, false);
+ }
+ return ret;
+
+ case BPF_JA:
+ if (BPF_SRC(insns[t].code) != BPF_K)
+ return -EINVAL;
+
+ /* unconditional jump with single edge */
+ ret = push_insn(t, t + insns[t].off + 1, FALLTHROUGH, env,
+ true);
+ if (ret)
+ return ret;
+
+ /* unconditional jmp is not a good pruning point,
+ * but it's marked, since backtracking needs
+ * to record jmp history in is_state_visited().
+ */
+ init_explored_state(env, t + insns[t].off + 1);
+ /* tell verifier to check for equivalent states
+ * after every call and jump
+ */
+ if (t + 1 < insn_cnt)
+ init_explored_state(env, t + 1);
+
+ return ret;
+
+ default:
+ /* conditional jump with two edges */
+ init_explored_state(env, t);
+ ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
+ if (ret)
+ return ret;
+
+ return push_insn(t, t + insns[t].off + 1, BRANCH, env, true);
+ }
}
/* non-recursive depth-first-search to detect loops in BPF program
@@ -8104,11 +8176,10 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
*/
static int check_cfg(struct bpf_verifier_env *env)
{
- struct bpf_insn *insns = env->prog->insnsi;
int insn_cnt = env->prog->len;
int *insn_stack, *insn_state;
int ret = 0;
- int i, t;
+ int i;
insn_state = env->cfg.insn_state = kvcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
if (!insn_state)
@@ -8124,92 +8195,32 @@ static int check_cfg(struct bpf_verifier_env *env)
insn_stack[0] = 0; /* 0 is the first instruction */
env->cfg.cur_stack = 1;
-peek_stack:
- if (env->cfg.cur_stack == 0)
- goto check_state;
- t = insn_stack[env->cfg.cur_stack - 1];
-
- if (BPF_CLASS(insns[t].code) == BPF_JMP ||
- BPF_CLASS(insns[t].code) == BPF_JMP32) {
- u8 opcode = BPF_OP(insns[t].code);
-
- if (opcode == BPF_EXIT) {
- goto mark_explored;
- } else if (opcode == BPF_CALL) {
- ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
- goto err_free;
- if (t + 1 < insn_cnt)
- init_explored_state(env, t + 1);
- if (insns[t].src_reg == BPF_PSEUDO_CALL) {
- init_explored_state(env, t);
- ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
- env, false);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
- goto err_free;
- }
- } else if (opcode == BPF_JA) {
- if (BPF_SRC(insns[t].code) != BPF_K) {
- ret = -EINVAL;
- goto err_free;
- }
- /* unconditional jump with single edge */
- ret = push_insn(t, t + insns[t].off + 1,
- FALLTHROUGH, env, true);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
- goto err_free;
- /* unconditional jmp is not a good pruning point,
- * but it's marked, since backtracking needs
- * to record jmp history in is_state_visited().
- */
- init_explored_state(env, t + insns[t].off + 1);
- /* tell verifier to check for equivalent states
- * after every call and jump
- */
- if (t + 1 < insn_cnt)
- init_explored_state(env, t + 1);
- } else {
- /* conditional jump with two edges */
- init_explored_state(env, t);
- ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
- goto err_free;
+ while (env->cfg.cur_stack > 0) {
+ int t = insn_stack[env->cfg.cur_stack - 1];
- ret = push_insn(t, t + insns[t].off + 1, BRANCH, env, true);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
- goto err_free;
- }
- } else {
- /* all other non-branch instructions with single
- * fall-through edge
- */
- ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
- if (ret == 1)
- goto peek_stack;
- else if (ret < 0)
+ ret = visit_insn(t, insn_cnt, env);
+ switch (ret) {
+ case DONE_EXPLORING:
+ insn_state[t] = EXPLORED;
+ env->cfg.cur_stack--;
+ break;
+ case KEEP_EXPLORING:
+ break;
+ default:
+ if (ret > 0) {
+ verbose(env, "visit_insn internal bug\n");
+ ret = -EFAULT;
+ }
goto err_free;
+ }
}
-mark_explored:
- insn_state[t] = EXPLORED;
- if (env->cfg.cur_stack-- <= 0) {
+ if (env->cfg.cur_stack < 0) {
verbose(env, "pop stack internal bug\n");
ret = -EFAULT;
goto err_free;
}
- goto peek_stack;
-check_state:
for (i = 0; i < insn_cnt; i++) {
if (insn_state[i] != EXPLORED) {
verbose(env, "unreachable insn %d\n", i);
--
2.29.2.454.gaff20da3a2-goog
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH bpf-next v2] bpf: Refactor check_cfg to use a structured loop.
2020-11-21 1:55 [PATCH bpf-next v2] bpf: Refactor check_cfg to use a structured loop Wedson Almeida Filho
@ 2020-11-25 6:40 ` patchwork-bot+netdevbpf
0 siblings, 0 replies; 3+ messages in thread
From: patchwork-bot+netdevbpf @ 2020-11-25 6:40 UTC (permalink / raw)
To: Wedson Almeida Filho; +Cc: bpf, daniel, ast
Hello:
This patch was applied to bpf/bpf-next.git (refs/heads/master):
On Sat, 21 Nov 2020 01:55:09 +0000 you wrote:
> The current implementation uses a number of gotos to implement a loop
> and different paths within the loop, which makes the code less readable
> than it would be with an explicit while-loop. This patch also replaces a
> chain of if/if-elses keyed on the same expression with a switch
> statement.
>
> No change in behaviour is intended.
>
> [...]
Here is the summary with links:
- [bpf-next,v2] bpf: Refactor check_cfg to use a structured loop.
https://git.kernel.org/bpf/bpf-next/c/59e2e27d227a
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH bpf-next v2] bpf: Refactor check_cfg to use a structured loop.
@ 2020-11-21 3:33 kernel test robot
0 siblings, 0 replies; 3+ messages in thread
From: kernel test robot @ 2020-11-21 3:33 UTC (permalink / raw)
To: kbuild
[-- Attachment #1: Type: text/plain, Size: 8291 bytes --]
CC: kbuild-all(a)lists.01.org
In-Reply-To: <20201121015509.3594191-1-wedsonaf@google.com>
References: <20201121015509.3594191-1-wedsonaf@google.com>
TO: Wedson Almeida Filho <wedsonaf@google.com>
TO: bpf(a)vger.kernel.org
TO: daniel(a)iogearbox.net
CC: ast(a)kernel.org
CC: Wedson Almeida Filho <wedsonaf@google.com>
Hi Wedson,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on bpf-next/master]
url: https://github.com/0day-ci/linux/commits/Wedson-Almeida-Filho/bpf-Refactor-check_cfg-to-use-a-structured-loop/20201121-100148
base: https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
:::::: branch date: 2 hours ago
:::::: commit date: 2 hours ago
compiler: arceb-elf-gcc (GCC) 9.3.0
If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
cppcheck possible warnings: (new ones prefixed by >>, may not real problems)
kernel/bpf/verifier.c:2670:9: warning: Identical condition 'err', second condition is always false [identicalConditionAfterEarlyExit]
return err;
^
kernel/bpf/verifier.c:2653:6: note: first condition
if (err)
^
kernel/bpf/verifier.c:2670:9: note: second condition
return err;
^
>> kernel/bpf/verifier.c:8161:10: warning: Identical condition 'ret', second condition is always false [identicalConditionAfterEarlyExit]
return ret;
^
kernel/bpf/verifier.c:8147:7: note: first condition
if (ret)
^
kernel/bpf/verifier.c:8161:10: note: second condition
return ret;
^
kernel/bpf/verifier.c:1994:25: warning: Local variable func shadows outer function [shadowFunction]
struct bpf_func_state *func;
^
kernel/bpf/verifier.c:551:31: note: Shadowed declaration
static struct bpf_func_state *func(struct bpf_verifier_env *env,
^
kernel/bpf/verifier.c:1994:25: note: Shadow variable
struct bpf_func_state *func;
^
kernel/bpf/verifier.c:2027:25: warning: Local variable func shadows outer function [shadowFunction]
struct bpf_func_state *func;
^
kernel/bpf/verifier.c:551:31: note: Shadowed declaration
static struct bpf_func_state *func(struct bpf_verifier_env *env,
^
kernel/bpf/verifier.c:2027:25: note: Shadow variable
struct bpf_func_state *func;
vim +/ret +8161 kernel/bpf/verifier.c
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8106
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8107 /* Visits the instruction at index t and returns one of the following:
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8108 * < 0 - an error occurred
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8109 * DONE_EXPLORING - the instruction was fully explored
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8110 * KEEP_EXPLORING - there is still work to be done before it is fully explored
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8111 */
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8112 static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8113 {
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8114 struct bpf_insn *insns = env->prog->insnsi;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8115 int ret;
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8116
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8117 /* All non-branch instructions have a single fall-through edge. */
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8118 if (BPF_CLASS(insns[t].code) != BPF_JMP &&
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8119 BPF_CLASS(insns[t].code) != BPF_JMP32)
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8120 return push_insn(t, t + 1, FALLTHROUGH, env, false);
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8121
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8122 switch (BPF_OP(insns[t].code)) {
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8123 case BPF_EXIT:
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8124 return DONE_EXPLORING;
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8125
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8126 case BPF_CALL:
2589726d12a1b12 Alexei Starovoitov 2019-06-15 8127 ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8128 if (ret)
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8129 return ret;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8130
07016151a446d25 Daniel Borkmann 2016-04-05 8131 if (t + 1 < insn_cnt)
5d839021675a2e1 Alexei Starovoitov 2019-05-21 8132 init_explored_state(env, t + 1);
cc8b0b92a1699bc Alexei Starovoitov 2017-12-14 8133 if (insns[t].src_reg == BPF_PSEUDO_CALL) {
5d839021675a2e1 Alexei Starovoitov 2019-05-21 8134 init_explored_state(env, t);
2589726d12a1b12 Alexei Starovoitov 2019-06-15 8135 ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
2589726d12a1b12 Alexei Starovoitov 2019-06-15 8136 env, false);
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8137 }
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8138 return ret;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8139
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8140 case BPF_JA:
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8141 if (BPF_SRC(insns[t].code) != BPF_K)
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8142 return -EINVAL;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8143
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8144 /* unconditional jump with single edge */
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8145 ret = push_insn(t, t + insns[t].off + 1, FALLTHROUGH, env,
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8146 true);
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8147 if (ret)
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8148 return ret;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8149
b5dc0163d8fd78e Alexei Starovoitov 2019-06-15 8150 /* unconditional jmp is not a good pruning point,
b5dc0163d8fd78e Alexei Starovoitov 2019-06-15 8151 * but it's marked, since backtracking needs
b5dc0163d8fd78e Alexei Starovoitov 2019-06-15 8152 * to record jmp history in is_state_visited().
b5dc0163d8fd78e Alexei Starovoitov 2019-06-15 8153 */
b5dc0163d8fd78e Alexei Starovoitov 2019-06-15 8154 init_explored_state(env, t + insns[t].off + 1);
f1bca824dabba4f Alexei Starovoitov 2014-09-29 8155 /* tell verifier to check for equivalent states
f1bca824dabba4f Alexei Starovoitov 2014-09-29 8156 * after every call and jump
f1bca824dabba4f Alexei Starovoitov 2014-09-29 8157 */
c3de6317d748e23 Alexei Starovoitov 2015-04-14 8158 if (t + 1 < insn_cnt)
5d839021675a2e1 Alexei Starovoitov 2019-05-21 8159 init_explored_state(env, t + 1);
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8160
13a826a70281cfb Wedson Almeida Filho 2020-11-21 @8161 return ret;
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8162
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8163 default:
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8164 /* conditional jump with two edges */
5d839021675a2e1 Alexei Starovoitov 2019-05-21 8165 init_explored_state(env, t);
2589726d12a1b12 Alexei Starovoitov 2019-06-15 8166 ret = push_insn(t, t + 1, FALLTHROUGH, env, true);
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8167 if (ret)
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8168 return ret;
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8169
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8170 return push_insn(t, t + insns[t].off + 1, BRANCH, env, true);
475fb78fbf48592 Alexei Starovoitov 2014-09-26 8171 }
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8172 }
13a826a70281cfb Wedson Almeida Filho 2020-11-21 8173
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all@lists.01.org
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-11-25 6:40 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-11-21 1:55 [PATCH bpf-next v2] bpf: Refactor check_cfg to use a structured loop Wedson Almeida Filho
2020-11-25 6:40 ` patchwork-bot+netdevbpf
2020-11-21 3:33 kernel test robot
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.