[bpf,1/2] bpf: Fix the corner case where may_goto is a 1st insn.

Commit Message

Alexei Starovoitov June 18, 2024, 6:42 p.m. UTC

From: Alexei Starovoitov <[e-mail]>

When the following program is processed by the verifier:
L1: may_goto L2
    goto L1
L2: w0 = 0
    exit

the may_goto insn is first converted to:
L1: r11 = *(u64 *)(r10 -8)
    if r11 == 0x0 goto L2
    r11 -= 1
    *(u64 *)(r10 -8) = r11
    goto L1
L2: w0 = 0
    exit

then later as the last step the verifier inserts:
  *(u64 *)(r10 -8) = BPF_MAX_LOOPS
as the first insn of the program to initialize loop count.

When the first insn happens to be a branch target of some jmp the
bpf_patch_insn_data() logic will produce:
L1: *(u64 *)(r10 -8) = BPF_MAX_LOOPS
    r11 = *(u64 *)(r10 -8)
    if r11 == 0x0 goto L2
    r11 -= 1
    *(u64 *)(r10 -8) = r11
    goto L1
L2: w0 = 0
    exit

because instruction patching adjusts all jmps and calls, but for this
particular corner case it's incorrect and the L1 label should be one
instruction down, like:
    *(u64 *)(r10 -8) = BPF_MAX_LOOPS
L1: r11 = *(u64 *)(r10 -8)
    if r11 == 0x0 goto L2
    r11 -= 1
    *(u64 *)(r10 -8) = r11
    goto L1
L2: w0 = 0
    exit

and that's what this patch is fixing.
After bpf_patch_insn_data() call adjust_jmp_off() to adjust all jmps
that point to newly insert BPF_ST insn to point to insn after.

Note that bpf_patch_insn_data() cannot easily be changed to accommodate
this logic, since jumps that point before or after a sequence of patched
instructions have to be adjusted with the full length of the patch.

Conceptually it's somewhat similar to "insert" of instructions between other
instructions with weird semantics. Like "insert" before 1st insn would require
adjustment of CALL insns to point to newly inserted 1st insn, but not an
adjustment JMP insns that point to 1st, yet still adjusting JMP insns that
cross over 1st insn (point to insn before or insn after), hence use simple
adjust_jmp_off() logic to fix this corner case. Ideally bpf_patch_insn_data()
would have an auxiliary info to say where 'the start of newly inserted patch
is', but it would be too complex for backport.

Reported-by: Zac Ecob <[e-mail]>
Closes: https://lore.kernel.org/bpf/CAADnVQJ_WWx8w4b=[e-mail]/
Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
Signed-off-by: Alexei Starovoitov <[e-mail]>
---
 kernel/bpf/verifier.c | 51 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)

Comments

Eduard Zingerman June 19, 2024, 12:13 a.m. UTC | #1

On Tue, 2024-06-18 at 11:42 -0700, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <[e-mail]>
> 
> When the following program is processed by the verifier:
> L1: may_goto L2
>     goto L1
> L2: w0 = 0
>     exit
> 
> the may_goto insn is first converted to:
> L1: r11 = *(u64 *)(r10 -8)
>     if r11 == 0x0 goto L2
>     r11 -= 1
>     *(u64 *)(r10 -8) = r11
>     goto L1
> L2: w0 = 0
>     exit

[...]

> 
> Reported-by: Zac Ecob <[e-mail]>
> Closes: https://lore.kernel.org/bpf/CAADnVQJ_WWx8w4b=[e-mail]/
> Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction")
> Signed-off-by: Alexei Starovoitov <[e-mail]>
> ---

A tricky corner case indeed.
We should probably switch to normal basic blocks one day...

Acked-by: Eduard Zingerman <[e-mail]>

Zac Ecob June 19, 2024, 7:38 a.m. UTC | #2

Hi,

Have applied the changes - moved to 6.10-rc4.
Prevents the repro I gave earlier from stalling, however I think it has introduced some new bugs, in part involved with ldimm64.

Attached is a new repro that stalls.
Additionally, when minimising it to what it is, some of the intermediate programs would crash, complaining about 'unknown opcode 0' - relating to ldimm64.

Alexei Starovoitov June 19, 2024, 9:56 p.m. UTC | #3

On Wed, Jun 19, 2024 at 12:38 AM Zac Ecob <[e-mail]> wrote:
>
> Hi,
>
> Have applied the changes - moved to 6.10-rc4.
> Prevents the repro I gave earlier from stalling, however I think it has introduced some new bugs, in part involved with ldimm64.
>
> Attached is a new repro that stalls.

This is a separate issue. Not related to imm64 at all.
Actually two issues. One is verifier related and another
in may_goto patching.
Will work on separate fixes for those.

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e0a398a97d32..2b8738160ce6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -12721,6 +12721,16 @@  static bool signed_add32_overflows(s32 a, s32 b)
 	return res < a;
 }
 
+static bool signed_add16_overflows(s16 a, s16 b)
+{
+	/* Do the add in u16, where overflow is well-defined */
+	s16 res = (s16)((u16)a + (u16)b);
+
+	if (b < 0)
+		return res > a;
+	return res < a;
+}
+
 static bool signed_sub_overflows(s64 a, s64 b)
 {
 	/* Do the sub in u64, where overflow is well-defined */
@@ -18732,6 +18742,40 @@  static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	return new_prog;
 }
 
+/*
+ * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
+ * jump offset by 'delta'.
+ */
+static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
+{
+	struct bpf_insn *insn = prog->insnsi;
+	u32 insn_cnt = prog->len, idx, i;
+	int ret = 0;
+
+	for (i = 0; i < insn_cnt; i++, insn++) {
+		u8 code = insn->code;
+
+		if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
+		    BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT)
+			continue;
+
+		if (insn->code == (BPF_JMP32 | BPF_JA)) {
+			if (i + 1 + insn->imm != tgt_idx)
+				continue;
+			if (signed_add32_overflows(insn->imm, delta))
+				return -ERANGE;
+			insn->imm += delta;
+		} else {
+			if (i + 1 + insn->off != tgt_idx)
+				continue;
+			if (signed_add16_overflows(insn->imm, delta))
+				return -ERANGE;
+			insn->off += delta;
+		}
+	}
+	return 0;
+}
+
 static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
 					      u32 off, u32 cnt)
 {
@@ -20548,6 +20592,13 @@  static int do_misc_fixups(struct bpf_verifier_env *env)
 		if (!new_prog)
 			return -ENOMEM;
 		env->prog = prog = new_prog;
+		/*
+		 * If may_goto is a first insn of a prog there could be a jmp
+		 * insn that points to it, hence adjust all such jmps to point
+		 * to insn after BPF_ST that inits may_goto count.
+		 * Adjustment will succeed because bpf_patch_insn_data() didn't fail.
+		 */
+		WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1));
 	}
 
 	/* Since poke tab is now finalized, publish aux to tracker. */