On 1/16/25 5:45 PM, Alexei Starovoitov wrote:
On Thu, Jan 16, 2025 at 11:42 AM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
On Wed, 2025-01-15 at 21:51 -0800, Yonghong Song wrote:
Since 'may_goto 0' insns are actually no-op, let us remove them.
Otherwise, verifier will generate code like
/* r10 - 8 stores the implicit loop count */
r11 = *(u64 *)(r10 -8)
if r11 == 0x0 goto pc+2
r11 -= 1
*(u64 *)(r10 -8) = r11
which is the pure overhead.
The following code patterns (from the previous commit) are also
handled:
may_goto 2
may_goto 1
may_goto 0
With this commit, the above three 'may_goto' insns are all
eliminated.
Signed-off-by: Yonghong Song <yonghong.song@xxxxxxxxx>
---
Technically this is a side-effect, it subtracts 1 from total loop budget.
An alternative transformation might be:
r11 = *(u64 *)(r10 -8)
if r11 == 0x0 goto pc+2
r11 -= 3 <---------------- note 3 here
*(u64 *)(r10 -8) = r11
On the other hand, it looks like there is no way to trick verifier
into an infinite loop by removing these statements, so this should be
safe modulo exceeding the 8M iterations budget.
Acked-by: Eduard Zingerman <eddyz87@xxxxxxxxx>
kernel/bpf/verifier.c | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index edf3cc42a220..72b474bfba2d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -20133,6 +20133,40 @@ static int opt_remove_nops(struct bpf_verifier_env *env)
return 0;
}
+static int opt_remove_useless_may_gotos(struct bpf_verifier_env *env)
+{
+ struct bpf_insn *insn = env->prog->insnsi;
+ int i, j, err, last_may_goto, removed_cnt;
+ int insn_cnt = env->prog->len;
+
+ for (i = 0; i < insn_cnt; i++) {
+ if (!is_may_goto_insn(&insn[i]))
+ continue;
+
+ for (j = i + 1; j < insn_cnt; j++) {
+ if (!is_may_goto_insn(&insn[j]))
+ break;
+ }
+
+ last_may_goto = --j;
+ removed_cnt = 0;
+ while (j >= i) {
+ if (insn[j].off == 0) {
+ err = verifier_remove_insns(env, j, 1);
Nit: given how ineffective the verifier_remove_insns() is I'd count
the number of matching may_goto's and removed them using one call
to verifier_remove_insns().
True,
but more generally I don't see why may_goto needs special treatment.
opt_remove_nops() should handle both.
if (memcmp(&insn[i], &ja, sizeof(ja)) &&
memcmp(&insn[i], &may_goto0, sizeof(ja)))
continue;
will almost work.
In the sequence of may_goto +2, +1, +0
only the last one will be removed, I think,
but opt_remove_nops() can be tweaked to achieve that as well.
- i--;
+ i -= 2;
will do ?
Okay. Let me give a try.
pw-bot: cr
