Skip to contentSkip to conversation

bpf, x64: Fix a jit convergence issue

PATCH Superseded Yonghong Song 3 participants 11 messages Aug 25, 2024 – Aug 30, 2024

Subsystems (3)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

PATCH 1/1 bpf, x64: Fix a jit convergence issue

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

...
pass4, final_proglen=4391:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    289:    48 85 ff                test   rdi,rdi
    28c:    74 17                   je     0x2a5
    28e:    e9 7f ff ff ff          jmp    0x212
    293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

pass5, final_proglen=4392:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    48 85 ff                test   rdi,rdi
    290:    74 1a                   je     0x2ac
    292:    eb 84                   jmp    0x218
    294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    249:    48 85 d2                test   rdx,rdx
    24c:    74 21                   je     0x26f
    24e:    48 01 f7                add    rdi,rsi
    ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14
addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

---
 arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 46 insertions(+), 1 deletion(-)
arch/x86/net/bpf_jit_comp.c +46 -1
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
 	return value <= 127 && value >= -128;
 }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */
+static bool is_imm8_cond_offset(int value)
+{
+	return value <= 124 && value >= -128;
+}
+
 static bool is_simm32(s64 value)
 {
 	return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:			if (is_imm8(insn->off))
 				return -EFAULT;
 			}
 			jmp_offset = addrs[i + insn->off] - addrs[i];
-			if (is_imm8(jmp_offset)) {
+			if (is_imm8_cond_offset(jmp_offset)) {
 				if (jmp_padding) {
 					/* To keep the jmp_offset valid, the extra bytes are
 					 * padded before the jump insn, so we subtract the
Signature · 1 line
2.43.5
#1 lore raw
Quoted 75 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

...
pass4, final_proglen=4391:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    289:    48 85 ff                test   rdi,rdi
    28c:    74 17                   je     0x2a5
    28e:    e9 7f ff ff ff          jmp    0x212
    293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

pass5, final_proglen=4392:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    48 85 ff                test   rdi,rdi
    290:    74 1a                   je     0x2ac
    292:    eb 84                   jmp    0x218
    294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    249:    48 85 d2                test   rdx,rdx
    24c:    74 21                   je     0x26f
    24e:    48 01 f7                add    rdi,rsi
    ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14
addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

Quoted 6 lines
---
 arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 46 insertions(+), 1 deletion(-)

Probably a stupid question. But instead of hacking things like this to help convergence in some particular cases, why not just add a condition that we should stop jitting as soon as jitted length stops shrinking (and correct the comment that claims "JITed image shrinks with every pass" because that's not true).

We have if (proglen == oldproglen) condition right now. What will happen if we just change it to if (proglen >= oldproglen)? That might be sup-optimal for these rare non-convergent cases, but that seems fine. We can of course do one extra pass to hopefully get back the second-to-last shorter image if proglen > oldproglen, but that seems excessive to me.

Quoted 68 lines
arch/x86/net/bpf_jit_comp.c +46 -2
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
        return value <= 127 && value >= -128;
 }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;
+}
+
 static bool is_simm32(s64 value)
 {
        return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                return -EFAULT;
                        }
                        jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                if (jmp_padding) {
                                        /* To keep the jmp_offset valid, the extra bytes are
                                         * padded before the jump insn, so we subtract the
--

2.43.5

author reviewer
#2 lore raw
Quoted 87 lines · Andrii Nakryiko
Quoted 74 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

   ...
   pass4, final_proglen=4391:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     289:    48 85 ff                test   rdi,rdi
     28c:    74 17                   je     0x2a5
     28e:    e9 7f ff ff ff          jmp    0x212
     293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

   pass5, final_proglen=4392:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    48 85 ff                test   rdi,rdi
     290:    74 1a                   je     0x2ac
     292:    eb 84                   jmp    0x218
     294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     249:    48 85 d2                test   rdx,rdx
     24c:    74 21                   je     0x26f
     24e:    48 01 f7                add    rdi,rsi
     ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14 addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

Quoted 6 lines
---
  arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
  1 file changed, 46 insertions(+), 1 deletion(-)

Probably a stupid question. But instead of hacking things like this to help convergence in some particular cases, why not just add a condition that we should stop jitting as soon as jitted length stops shrinking (and correct the comment that claims "JITed image shrinks with every pass" because that's not true).

Quoted 6 lines

We have if (proglen == oldproglen) condition right now. What will happen if we just change it to if (proglen >= oldproglen)? That might be sup-optimal for these rare non-convergent cases, but that seems fine. We can of course do one extra pass to hopefully get back the second-to-last shorter image if proglen > oldproglen, but that seems excessive to me.

We need convergence. Looks at some comments below:

+ * pass5, final_proglen=4392:

+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3

Without convergence, you can see je/jmp target may not be correct.

Quoted 70 lines
Quoted 70 lines
arch/x86/net/bpf_jit_comp.c +46 -2
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
         return value <= 127 && value >= -128;
  }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;
+}
+
  static bool is_simm32(s64 value)
  {
         return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                 return -EFAULT;
                         }
                         jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                 if (jmp_padding) {
                                         /* To keep the jmp_offset valid, the extra bytes are
                                          * padded before the jump insn, so we subtract the
--

2.43.5

#3 lore raw
Quoted 110 lines · Yonghong Song
Quoted 87 lines · Andrii Nakryiko
Quoted 74 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

   ...
   pass4, final_proglen=4391:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     289:    48 85 ff                test   rdi,rdi
     28c:    74 17                   je     0x2a5
     28e:    e9 7f ff ff ff          jmp    0x212
     293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

   pass5, final_proglen=4392:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    48 85 ff                test   rdi,rdi
     290:    74 1a                   je     0x2ac
     292:    eb 84                   jmp    0x218
     294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     249:    48 85 d2                test   rdx,rdx
     24c:    74 21                   je     0x26f
     24e:    48 01 f7                add    rdi,rsi
     ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14 addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

Quoted 6 lines
---
  arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
  1 file changed, 46 insertions(+), 1 deletion(-)

Probably a stupid question. But instead of hacking things like this to help convergence in some particular cases, why not just add a condition that we should stop jitting as soon as jitted length stops shrinking (and correct the comment that claims "JITed image shrinks with every pass" because that's not true).

Quoted 6 lines

We have if (proglen == oldproglen) condition right now. What will happen if we just change it to if (proglen >= oldproglen)? That might be sup-optimal for these rare non-convergent cases, but that seems fine. We can of course do one extra pass to hopefully get back the second-to-last shorter image if proglen > oldproglen, but that seems excessive to me.

We need convergence. Looks at some comments below:

+ * pass5, final_proglen=4392:

+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
Quoted 2 lines

Without convergence, you can see je/jmp target may not be correct.

I see, thanks. As I said, probably was a stupid question, I didn't realize that do_jit() can generate invalid image.

This whole guessing of acceptable range of relative offset still seems like a fragile game (what if you have few instructions that expand and then 124 bound isn't conservative enough anymore). I was wondering if there is some more generic solution where we can mark jump instructions that went from shorter to longer, and if that happened, on subsequent passes don't try to shorten them.

Again, I have no clue how actual code in JIT works and what are all the nuances, so feel free to ignore me completely, I won't be offended :)

Quoted 70 lines
Quoted 70 lines
Quoted 70 lines
arch/x86/net/bpf_jit_comp.c +46 -2
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
         return value <= 127 && value >= -128;
  }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;
+}
+
  static bool is_simm32(s64 value)
  {
         return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                 return -EFAULT;
                         }
                         jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                 if (jmp_padding) {
                                         /* To keep the jmp_offset valid, the extra bytes are
                                          * padded before the jump insn, so we subtract the
--

2.43.5

author reviewer
#4 lore raw
Quoted 114 lines · Andrii Nakryiko
Quoted 108 lines · Yonghong Song
Quoted 87 lines · Andrii Nakryiko
Quoted 71 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

    ...
    pass4, final_proglen=4391:
      ...
      20e:    48 85 ff                test   rdi,rdi
      211:    74 7d                   je     0x290
      213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
      ...
      289:    48 85 ff                test   rdi,rdi
      28c:    74 17                   je     0x2a5
      28e:    e9 7f ff ff ff          jmp    0x212
      293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

    pass5, final_proglen=4392:
      ...
      20e:    48 85 ff                test   rdi,rdi
      211:    0f 84 80 00 00 00       je     0x297
      217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
      ...
      28d:    48 85 ff                test   rdi,rdi
      290:    74 1a                   je     0x2ac
      292:    eb 84                   jmp    0x218
      294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

      211:    0f 84 80 00 00 00       je     0x297
      217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

      211:    74 7d                   je     0x290
      213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
      ...
      249:    48 85 d2                test   rdx,rdx
      24c:    74 21                   je     0x26f
      24e:    48 01 f7                add    rdi,rsi
      ...

Before generating the following insn,

    250:    74 21                   je     0x273

"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,

    addrs[i] = 0x24e // from pass14
    addrs[i-1] = 0x24d // from pass15
    prog - temp = 3 // from 'test rdx,rdx' in pass15
so
    nops = -4
Quoted 9 lines

and this triggers the failure.
Making jit prog convergable can fix the above error.

---
   arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
   1 file changed, 46 insertions(+), 1 deletion(-)

Probably a stupid question. But instead of hacking things like this to help convergence in some particular cases, why not just add a condition that we should stop jitting as soon as jitted length stops shrinking (and correct the comment that claims "JITed image shrinks with every pass" because that's not true).

Quoted 6 lines

We have if (proglen == oldproglen) condition right now. What will happen if we just change it to if (proglen >= oldproglen)? That might be sup-optimal for these rare non-convergent cases, but that seems fine. We can of course do one extra pass to hopefully get back the second-to-last shorter image if proglen > oldproglen, but that seems excessive to me.

We need convergence. Looks at some comments below:

+ * pass5, final_proglen=4392:

+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
Quoted 2 lines

Without convergence, you can see je/jmp target may not be correct.

I see, thanks. As I said, probably was a stupid question, I didn't realize that do_jit() can generate invalid image.

Quoted 6 lines

This whole guessing of acceptable range of relative offset still seems like a fragile game (what if you have few instructions that expand and then 124 bound isn't conservative enough anymore). I was wondering if there is some more generic solution where we can mark jump instructions that went from shorter to longer, and if that happened, on subsequent passes don't try to shorten them.

I digged out the git history and found that this pass convergence based approach is actually implemented from the beginning from the following patch

=====
commit 0a14842f5a3c0e88a1e59fac5c3025db39721f74 (HEAD -> t2)

Author: Eric Dumazet <[email protected]>
Date:   Wed Apr 20 09:27:32 2011 +0000

net: filter: Just In Time compiler for x86-64
=====

I cannot find the discussion context for this patch then. Do we have a better approach for this? I do not know, the issue is that for the same branch/jmp insn, the length of the insn could change depending on the 'offset' value. One possible solution is to assume all branch/jmp insn is 8bit long and whenever it won't work, replace previous one with 32bit and continue to enumerate following branch/jmp insn with 8bit. This may take a lot of time though.

Quoted 74 lines

Again, I have no clue how actual code in JIT works and what are all the nuances, so feel free to ignore me completely, I won't be offended :)

Quoted 69 lines
Quoted 69 lines
Quoted 69 lines
arch/x86/net/bpf_jit_comp.c +46 -2
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
          return value <= 127 && value >= -128;
   }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;
+}
+
   static bool is_simm32(s64 value)
   {
          return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                  return -EFAULT;
                          }
                          jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                  if (jmp_padding) {
                                          /* To keep the jmp_offset valid, the extra bytes are
                                           * padded before the jump insn, so we subtract the
--

2.43.5

#5 lore raw
In reply to Yonghong Song
Quoted 119 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

...
pass4, final_proglen=4391:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    289:    48 85 ff                test   rdi,rdi
    28c:    74 17                   je     0x2a5
    28e:    e9 7f ff ff ff          jmp    0x212
    293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

pass5, final_proglen=4392:

    ...
    20e:    48 85 ff                test   rdi,rdi
    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    48 85 ff                test   rdi,rdi
    290:    74 1a                   je     0x2ac
    292:    eb 84                   jmp    0x218
    294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

    211:    0f 84 80 00 00 00       je     0x297
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

    211:    74 7d                   je     0x290
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    249:    48 85 d2                test   rdx,rdx
    24c:    74 21                   je     0x26f
    24e:    48 01 f7                add    rdi,rsi
    ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14
addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

---
 arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
 1 file changed, 46 insertions(+), 1 deletion(-)
arch/x86/net/bpf_jit_comp.c +30 -0
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
        return value <= 127 && value >= -128;
 }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 106

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +10 -0
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */

je<->jmp

It can be je/je too, no?

so 128 - 4 instead of 128 - 3 ?

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 109

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;

the other side needs the same treatment, no ?

Quoted 17 lines
arch/x86/net/bpf_jit_comp.c +3 -2
+}
+
 static bool is_simm32(s64 value)
 {
        return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                return -EFAULT;
                        }
                        jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                if (jmp_padding) {
                                        /* To keep the jmp_offset valid, the extra bytes are
                                         * padded before the jump insn, so we subtract the
--

2.43.5

author reviewer
#6 lore raw
Quoted 131 lines · Alexei Starovoitov
Quoted 118 lines · Yonghong Song

Daniel Hodges reported a jit error when playing with a sched-ext program. The error message is:
unexpected jmp_cond padding: -4 bytes

But further investigation shows the error is actual due to failed convergence. The following are some analysis:

   ...
   pass4, final_proglen=4391:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     289:    48 85 ff                test   rdi,rdi
     28c:    74 17                   je     0x2a5
     28e:    e9 7f ff ff ff          jmp    0x212
     293:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125) and insn at 0x28e is 5-byte jmp insn with offset -129.

   pass5, final_proglen=4392:
     ...
     20e:    48 85 ff                test   rdi,rdi
     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    48 85 ff                test   rdi,rdi
     290:    74 1a                   je     0x2ac
     292:    eb 84                   jmp    0x218
     294:    bf 03 00 00 00          mov    edi,0x3

Note that insn at 0x211 is 5-byte cond jump insn now since its offset becomes 0x80 based on previous round (0x293 - 0x213 = 0x80). At the same time, insn at 0x292 is a 2-byte insn since its offset is -124.

pass6 will repeat the same code as in pass4. pass7 will repeat the same code as in pass5, and so on. This will prevent eventual convergence.

Passes 1-14 are with padding = 0. At pass15, padding is 1 and related insn looks like:

     211:    0f 84 80 00 00 00       je     0x297
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]

...
24d: 48 85 d2 test rdx,rdx

The similar code in pass14:

     211:    74 7d                   je     0x290
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     249:    48 85 d2                test   rdx,rdx
     24c:    74 21                   je     0x26f
     24e:    48 01 f7                add    rdi,rsi
     ...

Before generating the following insn,
250: 74 21 je 0x273
"padding = 1" enables some checking to ensure nops is either 0 or 4 where
#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp))) nops = INSN_SZ_DIFF - 2

In this specific case,
addrs[i] = 0x24e // from pass14 addrs[i-1] = 0x24d // from pass15
prog - temp = 3 // from 'test rdx,rdx' in pass15
so
nops = -4
and this triggers the failure.
Making jit prog convergable can fix the above error.

---
  arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
  1 file changed, 46 insertions(+), 1 deletion(-)
arch/x86/net/bpf_jit_comp.c +30 -0
index 074b41fafbe3..ec541aae5d9b 100644
@@ -64,6 +64,51 @@ static bool is_imm8(int value)
         return value <= 127 && value >= -128;
  }
 
+/*
+ * Let us limit the positive offset to be <= 124.
+ * This is to ensure eventual jit convergence For the following patterns:
+ * ...
+ * pass4, final_proglen=4391:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    74 7d                   je     0x290
+ *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   289:    48 85 ff                test   rdi,rdi
+ *   28c:    74 17                   je     0x2a5
+ *   28e:    e9 7f ff ff ff          jmp    0x212
+ *   293:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
+ * and insn at 0x28e is 5-byte jmp insn with offset -129.
+ *
+ * pass5, final_proglen=4392:
+ *   ...
+ *   20e:    48 85 ff                test   rdi,rdi
+ *   211:    0f 84 80 00 00 00       je     0x297
+ *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
+ *   ...
+ *   28d:    48 85 ff                test   rdi,rdi
+ *   290:    74 1a                   je     0x2ac
+ *   292:    eb 84                   jmp    0x218
+ *   294:    bf 03 00 00 00          mov    edi,0x3
+ * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
+ * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
+ * At the same time, insn at 0x292 is a 2-byte insn since its offset is

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 106

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +10 -0
+ * -124.
+ *
+ * pass6 will repeat the same code as in pass4 and this will prevent
+ * eventual convergence.
+ *
+ * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
+ * cycle in the above. Let us limit the positive offset for 8bit cond jump
+ * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
+ * and the jit pass can eventually converge.
+ */

je<->jmp

Quoted 1 line

It can be je/je too, no?

Yes. It is possible.

Quoted 2 lines

so 128 - 4 instead of 128 - 3 ?

You probably mean "127 - 4 instead of 127 - 3" since the maximum value is 127.

I checked 127 - 4 = 0x7c and indeed we should. See below examples:

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX                   je     0x291
   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   28d:    XX XX XX XX XX XX       je     0x212
   293:    bf 03 00 00 00          mov    edi,0x3

=>

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   291:    XX XX                   je     0x217 (0x217 - 0x293)
   293:    bf 03 00 00 00          mov    edi,0x3

=>

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX                   je     0x28f (0x293 - 0x217)
   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   28d:    XX XX                   je     0x213 (0x213 - 0x293)  // -0x80 allowed
   293:    bf 03 00 00 00          mov    edi,0x3

=>

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX XX XX XX XX       je     0x28f (0x293 - 0x213)
   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   291:    XX XX                   je     0x217 (0x217 - 0x293)
   293:    bf 03 00 00 00          mov    edi,0x3

=>
...

Here 0x293 - 0x217 = 0x7c

Quoted 5 lines

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 109

Quoted 4 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;

the other side needs the same treatment, no ?

good question. From my understanding, the non-convergence in the above needs both forward and backport conditions. The solution we are using is based on putting a limitation on forward conditions w.r.t. jit code gen.

Another solution is actually to put a limitation on backward conditions. For example, let us say the above is_imm8_cond_offset() has

	return value <= 127 && value > -124

See below example:

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX                   je     0x291
   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   28d:    XX XX XX XX XX XX       je     0x212
   293:    bf 03 00 00 00          mov    edi,0x3

=>

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   291:    XX XX XX XX XX XX       je     0x21b (0x217 - 0x293)
   297:    bf 03 00 00 00          mov    edi,0x3

=>

   20e:    48 85 ff                test   rdi,rdi
   211:    XX XX XX XX XX XX       je     0x297 (0x297 - 0x217)
   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
   ...
   291:    XX XX XX XX XX XX       je     0x217 (0x217 - 0x297)
   297:    bf 03 00 00 00          mov    edi,0x3

converged here.

So I think we do not need to limit both sides. One side should be enough.

Quoted 18 lines
Quoted 18 lines
arch/x86/net/bpf_jit_comp.c +3 -2
+}
+
  static bool is_simm32(s64 value)
  {
         return value == (s64)(s32)value;
@@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
                                 return -EFAULT;
                         }
                         jmp_offset = addrs[i + insn->off] - addrs[i];
-                       if (is_imm8(jmp_offset)) {
+                       if (is_imm8_cond_offset(jmp_offset)) {
                                 if (jmp_padding) {
                                         /* To keep the jmp_offset valid, the extra bytes are
                                          * padded before the jump insn, so we subtract the
--

2.43.5

#7 lore raw
Quoted 10 lines · Yonghong Song
Quoted 2 lines

It can be je/je too, no?

Yes. It is possible.

Quoted 2 lines

so 128 - 4 instead of 128 - 3 ?

You probably mean "127 - 4 instead of 127 - 3" since the maximum value is 127.

Yes, of course :)

Quoted 36 lines

I checked 127 - 4 = 0x7c and indeed we should. See below examples:

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX                   je     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX XX XX XX XX       je     0x212
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX                   je     0x217 (0x217 - 0x293)
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX                   je     0x28f (0x293 - 0x217)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX                   je     0x213 (0x213 - 0x293)  // -0x80 allowed
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX XX XX XX XX       je     0x28f (0x293 - 0x213)
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX                   je     0x217 (0x217 - 0x293)
    293:    bf 03 00 00 00          mov    edi,0x3
Quoted 5 lines

=>

    ...

Here 0x293 - 0x217 = 0x7c

How did you craft such a test?
Can we add it as a selftest somehow?

Quoted 44 lines
Quoted 6 lines

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 109

Quoted 5 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;

the other side needs the same treatment, no ?

good question. From my understanding, the non-convergence in the above needs both forward and backport conditions. The solution we are using is based on putting a limitation on forward conditions w.r.t. jit code gen.

Another solution is actually to put a limitation on backward conditions. For example, let us say the above is_imm8_cond_offset() has

        return value <= 127 && value > -124

See below example:

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX                   je     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX XX XX XX XX       je     0x212
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX XX XX XX XX       je     0x21b (0x217 - 0x293)
    297:    bf 03 00 00 00          mov    edi,0x3

=>

    20e:    48 85 ff                test   rdi,rdi
    211:    XX XX XX XX XX XX       je     0x297 (0x297 - 0x217)
    217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX XX XX XX XX       je     0x217 (0x217 - 0x297)
    297:    bf 03 00 00 00          mov    edi,0x3
Quoted 3 lines

converged here.

So I think we do not need to limit both sides. One side should be enough.

I see and agree when both sides are je/je.
What if the earlier one is a jmp ?

Then we can hit:

           if (nops != 0 && nops != 3) {
                     pr_err("unexpected jump padding: %d bytes\n",
                                             nops);

?

So one side of "jmp_cond padding" and the same side in "jump padding" needs to do it?

author reviewer
#8 lore raw
Quoted 45 lines · Alexei Starovoitov
Quoted 6 lines · Yonghong Song
Quoted 1 line

It can be je/je too, no?

Yes. It is possible.

Quoted 1 line

so 128 - 4 instead of 128 - 3 ?

You probably mean "127 - 4 instead of 127 - 3" since the maximum value is 127.

Yes, of course :)

Quoted 36 lines

I checked 127 - 4 = 0x7c and indeed we should. See below examples:

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX                   je     0x291
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    XX XX XX XX XX XX       je     0x212
     293:    bf 03 00 00 00          mov    edi,0x3

=>

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     291:    XX XX                   je     0x217 (0x217 - 0x293)
     293:    bf 03 00 00 00          mov    edi,0x3

=>

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX                   je     0x28f (0x293 - 0x217)
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    XX XX                   je     0x213 (0x213 - 0x293)  // -0x80 allowed
     293:    bf 03 00 00 00          mov    edi,0x3

=>

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX XX XX XX XX       je     0x28f (0x293 - 0x213)
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     291:    XX XX                   je     0x217 (0x217 - 0x293)
     293:    bf 03 00 00 00          mov    edi,0x3
Quoted 7 lines
Quoted 5 lines

=>

     ...

Here 0x293 - 0x217 = 0x7c

How did you craft such a test?
Can we add it as a selftest somehow?

This is not from a complete test. I assumed some state during convergence and from there to further derive states. But I will try to see whether I can construct actual test cases or not.

Quoted 48 lines
Quoted 42 lines
Quoted 5 lines

arch/x86/net/bpf_jit_comp.c static bool is_imm8(int value) · line 109

Quoted 4 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+static bool is_imm8_cond_offset(int value)
+{
+       return value <= 124 && value >= -128;

the other side needs the same treatment, no ?

good question. From my understanding, the non-convergence in the above needs both forward and backport conditions. The solution we are using is based on putting a limitation on forward conditions w.r.t. jit code gen.

Another solution is actually to put a limitation on backward conditions. For example, let us say the above is_imm8_cond_offset() has

         return value <= 127 && value > -124

See below example:

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX                   je     0x291
     213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     28d:    XX XX XX XX XX XX       je     0x212
     293:    bf 03 00 00 00          mov    edi,0x3

=>

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX XX XX XX XX       je     0x297 (0x293 - 0x213)
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     291:    XX XX XX XX XX XX       je     0x21b (0x217 - 0x293)
     297:    bf 03 00 00 00          mov    edi,0x3

=>

     20e:    48 85 ff                test   rdi,rdi
     211:    XX XX XX XX XX XX       je     0x297 (0x297 - 0x217)
     217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
     ...
     291:    XX XX XX XX XX XX       je     0x217 (0x217 - 0x297)
     297:    bf 03 00 00 00          mov    edi,0x3
Quoted 3 lines

converged here.

So I think we do not need to limit both sides. One side should be enough.

I see and agree when both sides are je/je.
What if the earlier one is a jmp ?

Quoted 8 lines

Then we can hit:

            if (nops != 0 && nops != 3) {
                      pr_err("unexpected jump padding: %d bytes\n",
                                              nops);

?

So one side of "jmp_cond padding" and the same side in "jump padding" needs to do it?

I did some further experiments with pattern like
jmp <-> je
and
jmp <-> jmp

The below is the illustration (not from a complete test):

================

    211:    XX XX                   jmp     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX XX XX XX XX       je     0x212
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX XX XX XX          jmp     (0x293 - 0x213)
    216:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX                   je      (0x216 - 0x293)
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp     (0x293 - 0x216 = 0x7d)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX                   je      (0x213 - 0x293)
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX XX XX XX          jmp     (0x293 - 0x213)
    216:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    291:    XX XX                   je      (0x216 - 0x293)
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    ...

not converged!

================

    211:    XX XX                   jmp     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28c:    XX XX XX XX XX XX       je     0x212
    292:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp     (0x292 - 0x213)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28c:    XX XX                   je     (0x213 - 0x292)
    28e:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp     (0x28e - 0x213 = 0x7b)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28c:    XX XX                   je     (0x213 - 0x28e)
    28e:    bf 03 00 00 00          mov    edi,0x3

converged!

=================

    211:    XX XX                   jmp     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28e:    XX XX XX XX XX          jmp     0x212
    293:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX XX XX XX          jmp    (0x293 - 0x213)
    216:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    292:    XX XX                   jmp    (0x216 - 0x293)
    294:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp    (0x294 - 0x216 = 0x7e)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28e:    XX XX XX XX XX          jmp    (0x213 - 0x294)
    294:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp    (0x294 - 0x216 = 0x7e)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28e:    XX XX XX XX XX          jmp    (0x213 - 0x294)
    294:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX XX XX XX          jmp    (0x294 - 0x213)
    216:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    292:    XX XX                   jmp    (0x216 - 0x294)
    294:    bf 03 00 00 00          mov    edi,0x3

=>
...

no converged!

===================================

    211:    XX XX                   jmp     0x291
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX XX XX XX          jmp     0x212
    292:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp     (0x292 - 0x213)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX                   jmp     (0x213 - 0x292)
    290:    bf 03 00 00 00          mov    edi,0x3

=>

    211:    XX XX                   jmp     (0x290 - 0x213 = 0x7d)
    213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
    ...
    28d:    XX XX                   jmp     (0x213 - 0x290)
    290:    bf 03 00 00 00          mov    edi,0x3

converged!

So I emulated je <-> je, je <-> jmp, jmp <-> je and jmp <-> jmp.

So we need to apply the same checking is_imm8_cond_offset() to jmp insn. This should cover all cases.

Hitting the following

           if (nops != 0 && nops != 3) {
                     pr_err("unexpected jump padding: %d bytes\n",
                                             nops);

is not due to the above illustration with 'jmp' insn as indeed its insn length changes with 0 or 3. But it is due to some jmp/cond_jmp insn inside je/jmp <-> je/jmp.

#9 lore raw
Quoted 5 lines · Yonghong Song

So we need to apply the same checking is_imm8_cond_offset() to jmp insn. This should cover all cases.

Looks like it.
If I'm reading it correctly is_imm8_cond_offset() doesn't need to be 127-4 for jmp. It can be 127-3, since jmp insn can grow by 3 bytes. But to avoid thinking twice I'd use the same is_imm8_cond_offset() for both jmp_cond and jmp.

author reviewer
#10 lore raw
Quoted 8 lines · Alexei Starovoitov
Quoted 4 lines · Yonghong Song

So we need to apply the same checking is_imm8_cond_offset() to jmp insn. This should cover all cases.

Looks like it.
If I'm reading it correctly is_imm8_cond_offset() doesn't need to be 127-4 for jmp. It can be 127-3, since jmp insn can grow by 3 bytes.

Right, 127-3 should work for jmp insn.

Quoted 2 lines

But to avoid thinking twice I'd use the same is_imm8_cond_offset() for both jmp_cond and jmp.

Sounds good. I will add this into commit message as well.