max<min after jset

max<min after jset

[Tao Lyu]

Hi,

The eBPF program shown below leads to an reversed min and max
after insn 6 "if w0 & 0x894b6a55 goto +2",
whic means max < min.

Here is the introduction how it happens.

Before insn 6,
the range of r0 expressed by the min and max field is
min1 = 884670597, max1 = 900354100
And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
is min2=872415232, max2=905928639.

---min2-----------------------min1-----max1-----max2---

Here we can see that the range expressed by var_off is wider than that of min and max.

When verifying insn6,
it first uses the var_off and immediate "0x894b6a55" to
calculate the new var_off=(0x34b00000; 0x415aa).
The range expressed by the new var_off is:
min3=883949568, max3=884217258

---min2-----min3-----max3-----min1-----max1-----max2---

And then it will calculate the new min and max by:
(1) new-min = MAX(min3, min1) = min1
(2) new-max = MIN(max3, max1) = max3

---min2-----min3-----max3-----min1-----max1-----max2---
         "new-max"          "new-min" 

Now, the new-max becomes less than the new min.

Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
and thus cannot goes the fall-through branch.
In other words, actually the fall-trough branch is a dead path.

BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
in the c inline assembly code.
So I can only attach the bytecodes.

Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
---
 .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c

diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
new file mode 100644
index 000000000000..734f492a2a96
--- /dev/null
+++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
@@ -0,0 +1,15 @@
+{
+    "BPF_JSET: incorrect scalar range",
+    .insns = {
+    BPF_MOV64_IMM(BPF_REG_5, 100),
+    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
+    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
+    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
+    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
+    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
+    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
+    BPF_MOV64_IMM(BPF_REG_0, 1),
+    BPF_MOV64_IMM(BPF_REG_0, 0),
+    BPF_EXIT_INSN(),
+    },
+},
-- 
2.25.1

Re: max<min after jset

[Yonghong Song]

On 11/21/23 12:32 PM, Tao Lyu wrote:
> Hi,
>
> The eBPF program shown below leads to an reversed min and max
> after insn 6 "if w0 & 0x894b6a55 goto +2",
> whic means max < min.
>
> Here is the introduction how it happens.
>
> Before insn 6,
> the range of r0 expressed by the min and max field is
> min1 = 884670597, max1 = 900354100
> And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
> is min2=872415232, max2=905928639.
>
> ---min2-----------------------min1-----max1-----max2---
>
> Here we can see that the range expressed by var_off is wider than that of min and max.
>
> When verifying insn6,
> it first uses the var_off and immediate "0x894b6a55" to
> calculate the new var_off=(0x34b00000; 0x415aa).
> The range expressed by the new var_off is:
> min3=883949568, max3=884217258
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>
> And then it will calculate the new min and max by:
> (1) new-min = MAX(min3, min1) = min1
> (2) new-max = MIN(max3, max1) = max3
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>           "new-max"          "new-min"
>
> Now, the new-max becomes less than the new min.
>
> Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
> and thus cannot goes the fall-through branch.
> In other words, actually the fall-trough branch is a dead path.
>
> BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
> in the c inline assembly code.

The format "if w0 != 0 goto +2;\" should be supported by recent clang compiler.
Which clang version you are using? Maybe try clang 15/16? Could you also
post the C inline assembly code here so we can investigate?

> So I can only attach the bytecodes.
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>   .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
>   1 file changed, 15 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c
>
> diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> new file mode 100644
> index 000000000000..734f492a2a96
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> @@ -0,0 +1,15 @@
> +{
> +    "BPF_JSET: incorrect scalar range",
> +    .insns = {
> +    BPF_MOV64_IMM(BPF_REG_5, 100),
> +    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
> +    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
> +    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
> +    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
> +    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
> +    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 0),
> +    BPF_EXIT_INSN(),
> +    },
> +},

[PATCH] C inlined assembly for reproducing max<min

[Tao Lyu]

Hi Yonghong,

Thanks for your reply.
The C inlined assembly code is attached.
I'm using clang-16, but it still fails.

Best,
Tao

Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
---
 .../selftests/bpf/prog_tests/verifier.c       |  2 ++
 .../selftests/bpf/progs/verifier_range.c      | 25 +++++++++++++++++++
 2 files changed, 27 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_range.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index e5c61aa6604a..3a5d746f392d 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -77,6 +77,7 @@
 #include "verifier_xadd.skel.h"
 #include "verifier_xdp.skel.h"
 #include "verifier_xdp_direct_packet_access.skel.h"
+#include "verifier_range.skel.h"
 
 #define MAX_ENTRIES 11
 
@@ -184,6 +185,7 @@ void test_verifier_var_off(void)              { RUN(verifier_var_off); }
 void test_verifier_xadd(void)                 { RUN(verifier_xadd); }
 void test_verifier_xdp(void)                  { RUN(verifier_xdp); }
 void test_verifier_xdp_direct_packet_access(void) { RUN(verifier_xdp_direct_packet_access); }
+void test_verifier_range(void)                { RUN(verifier_range); }
 
 static int init_test_val_map(struct bpf_object *obj, char *map_name)
 {
diff --git a/tools/testing/selftests/bpf/progs/verifier_range.c b/tools/testing/selftests/bpf/progs/verifier_range.c
new file mode 100644
index 000000000000..27597eb8135c
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_range.c
@@ -0,0 +1,25 @@
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("?tc")
+__log_level(2)
+int test_verifier_range(void)
+{
+    asm volatile (
+        "r5 = 100; \
+        r5 /= 3; \
+        w5 >>= 7; \
+        r5 &= -386969681; \
+        r5 -= -884670597; \
+        w0 = w5; \
+        if w0 & 0x894b6a55 goto +2; \
+        r2 = 1; \
+        r2 = 1; \
+        r0 = 0; \
+        "
+    );
+    return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.25.1

Re: [PATCH] C inlined assembly for reproducing max<min

[Yonghong Song]

On 11/22/23 9:40 AM, Tao Lyu wrote:
> Hi Yonghong,
>
> Thanks for your reply.
> The C inlined assembly code is attached.
> I'm using clang-16, but it still fails.
>
> Best,
> Tao
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>   .../selftests/bpf/prog_tests/verifier.c       |  2 ++
>   .../selftests/bpf/progs/verifier_range.c      | 25 +++++++++++++++++++
>   2 files changed, 27 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/progs/verifier_range.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
> index e5c61aa6604a..3a5d746f392d 100644
> --- a/tools/testing/selftests/bpf/prog_tests/verifier.c
> +++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
> @@ -77,6 +77,7 @@
>   #include "verifier_xadd.skel.h"
>   #include "verifier_xdp.skel.h"
>   #include "verifier_xdp_direct_packet_access.skel.h"
> +#include "verifier_range.skel.h"
>   
>   #define MAX_ENTRIES 11
>   
> @@ -184,6 +185,7 @@ void test_verifier_var_off(void)              { RUN(verifier_var_off); }
>   void test_verifier_xadd(void)                 { RUN(verifier_xadd); }
>   void test_verifier_xdp(void)                  { RUN(verifier_xdp); }
>   void test_verifier_xdp_direct_packet_access(void) { RUN(verifier_xdp_direct_packet_access); }
> +void test_verifier_range(void)                { RUN(verifier_range); }
>   
>   static int init_test_val_map(struct bpf_object *obj, char *map_name)
>   {
> diff --git a/tools/testing/selftests/bpf/progs/verifier_range.c b/tools/testing/selftests/bpf/progs/verifier_range.c
> new file mode 100644
> index 000000000000..27597eb8135c
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/verifier_range.c
> @@ -0,0 +1,25 @@
> +#include <linux/bpf.h>
> +#include <bpf/bpf_helpers.h>
> +#include "bpf_misc.h"
> +
> +SEC("?tc")
> +__log_level(2)
> +int test_verifier_range(void)
> +{
> +    asm volatile (
> +        "r5 = 100; \
> +        r5 /= 3; \
> +        w5 >>= 7; \
> +        r5 &= -386969681; \
> +        r5 -= -884670597; \
> +        w0 = w5; \
> +        if w0 & 0x894b6a55 goto +2; \

So actually it is 'if w0 & 0x894b6a55 goto +2' failed
the compilation.

Indeed, the above operation is not supported in llvm.
See
   https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/BPF/BPFInstrFormats.td#L62-L74
the missing BPFJumpOp<0x4> which corresponds to JSET.

The following llvm patch (on top of llvm-project main branch):

diff --git a/llvm/lib/Target/BPF/BPFInstrFormats.td b/llvm/lib/Target/BPF/BPFInstrFormats.td
index 841d97efc01c..6ed83d877ac0 100644
--- a/llvm/lib/Target/BPF/BPFInstrFormats.td
+++ b/llvm/lib/Target/BPF/BPFInstrFormats.td
@@ -63,6 +63,7 @@ def BPF_JA   : BPFJumpOp<0x0>;
  def BPF_JEQ  : BPFJumpOp<0x1>;
  def BPF_JGT  : BPFJumpOp<0x2>;
  def BPF_JGE  : BPFJumpOp<0x3>;
+def BPF_JSET : BPFJumpOp<0x4>;
  def BPF_JNE  : BPFJumpOp<0x5>;
  def BPF_JSGT : BPFJumpOp<0x6>;
  def BPF_JSGE : BPFJumpOp<0x7>;
diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td b/llvm/lib/Target/BPF/BPFInstrInfo.td
index 305cbbd34d27..9e75f35efe70 100644
--- a/llvm/lib/Target/BPF/BPFInstrInfo.td
+++ b/llvm/lib/Target/BPF/BPFInstrInfo.td
@@ -246,6 +246,70 @@ class JMP_RI_32<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond>
    let BPFClass = BPF_JMP32;
  }
  
+class JSET_RR<string OpcodeStr>
+    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
+                   (outs),
+                   (ins GPR:$dst, GPR:$src, brtarget:$BrDst),
+                   "if $dst "#OpcodeStr#" $src goto $BrDst",
+                   []> {
+  bits<4> dst;
+  bits<4> src;
+  bits<16> BrDst;
+
+  let Inst{55-52} = src;
+  let Inst{51-48} = dst;
+  let Inst{47-32} = BrDst;
+  let BPFClass = BPF_JMP;
+}
+
+class JSET_RI<string OpcodeStr>
+    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
+                   (outs),
+                   (ins GPR:$dst, i64imm:$imm, brtarget:$BrDst),
+                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
+                   []> {
+  bits<4> dst;
+  bits<16> BrDst;
+  bits<32> imm;
+
+  let Inst{51-48} = dst;
+  let Inst{47-32} = BrDst;
+  let Inst{31-0} = imm;
+  let BPFClass = BPF_JMP;
+}
+
+class JSET_RR_32<string OpcodeStr>
+    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
+                   (outs),
+                   (ins GPR32:$dst, GPR32:$src, brtarget:$BrDst),
+                   "if $dst "#OpcodeStr#" $src goto $BrDst",
+                   []> {
+  bits<4> dst;
+  bits<4> src;
+  bits<16> BrDst;
+
+  let Inst{55-52} = src;
+  let Inst{51-48} = dst;
+  let Inst{47-32} = BrDst;
+  let BPFClass = BPF_JMP32;
+}
+
+class JSET_RI_32<string OpcodeStr>
+    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
+                   (outs),
+                   (ins GPR32:$dst, i32imm:$imm, brtarget:$BrDst),
+                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
+                   []> {
+  bits<4> dst;
+  bits<16> BrDst;
+  bits<32> imm;
+
+  let Inst{51-48} = dst;
+  let Inst{47-32} = BrDst;
+  let Inst{31-0} = imm;
+  let BPFClass = BPF_JMP32;
+}
+
  multiclass J<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond, PatLeaf Cond32> {
    def _rr : JMP_RR<Opc, OpcodeStr, Cond>;
    def _ri : JMP_RI<Opc, OpcodeStr, Cond>;
@@ -265,6 +329,10 @@ defm JULT : J<BPF_JLT, "<", BPF_CC_LTU, BPF_CC_LTU_32>;
  defm JULE : J<BPF_JLE, "<=", BPF_CC_LEU, BPF_CC_LEU_32>;
  defm JSLT : J<BPF_JSLT, "s<", BPF_CC_LT, BPF_CC_LT_32>;
  defm JSLE : J<BPF_JSLE, "s<=", BPF_CC_LE, BPF_CC_LE_32>;
+def JSET_RR    : JSET_RR<"&">;
+def JSET_RI    : JSET_RI<"&">;
+def JSET_RR_32 : JSET_RR_32<"&">;
+def JSET_RI_32 : JSET_RI_32<"&">;
  }
  
  // ALU instructions

can solve your inline asm issue. We will discuss whether llvm compiler
should be implementing this instruction from source or not.


> +        r2 = 1; \
> +        r2 = 1; \
> +        r0 = 0; \
> +        "
> +    );
> +    return 0;
> +}
> +
> +char _license[] SEC("license") = "GPL";

Re: [PATCH] C inlined assembly for reproducing max<min

[Alexei Starovoitov]

On Wed, Nov 22, 2023 at 10:08 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>
> > +SEC("?tc")
> > +__log_level(2)
> > +int test_verifier_range(void)
> > +{
> > +    asm volatile (
> > +        "r5 = 100; \
> > +        r5 /= 3; \
> > +        w5 >>= 7; \
> > +        r5 &= -386969681; \
> > +        r5 -= -884670597; \
> > +        w0 = w5; \
> > +        if w0 & 0x894b6a55 goto +2; \
>
> So actually it is 'if w0 & 0x894b6a55 goto +2' failed
> the compilation.
>
> Indeed, the above operation is not supported in llvm.
> See
>    https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/BPF/BPFInstrFormats.td#L62-L74
> the missing BPFJumpOp<0x4> which corresponds to JSET.
>
> The following llvm patch (on top of llvm-project main branch):
>
> diff --git a/llvm/lib/Target/BPF/BPFInstrFormats.td b/llvm/lib/Target/BPF/BPFInstrFormats.td
> index 841d97efc01c..6ed83d877ac0 100644
> --- a/llvm/lib/Target/BPF/BPFInstrFormats.td
> +++ b/llvm/lib/Target/BPF/BPFInstrFormats.td
> @@ -63,6 +63,7 @@ def BPF_JA   : BPFJumpOp<0x0>;
>   def BPF_JEQ  : BPFJumpOp<0x1>;
>   def BPF_JGT  : BPFJumpOp<0x2>;
>   def BPF_JGE  : BPFJumpOp<0x3>;
> +def BPF_JSET : BPFJumpOp<0x4>;
>   def BPF_JNE  : BPFJumpOp<0x5>;
>   def BPF_JSGT : BPFJumpOp<0x6>;
>   def BPF_JSGE : BPFJumpOp<0x7>;
> diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td b/llvm/lib/Target/BPF/BPFInstrInfo.td
> index 305cbbd34d27..9e75f35efe70 100644
> --- a/llvm/lib/Target/BPF/BPFInstrInfo.td
> +++ b/llvm/lib/Target/BPF/BPFInstrInfo.td
> @@ -246,6 +246,70 @@ class JMP_RI_32<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond>
>     let BPFClass = BPF_JMP32;
>   }
>
> +class JSET_RR<string OpcodeStr>
> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
> +                   (outs),
> +                   (ins GPR:$dst, GPR:$src, brtarget:$BrDst),
> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
> +                   []> {
> +  bits<4> dst;
> +  bits<4> src;
> +  bits<16> BrDst;
> +
> +  let Inst{55-52} = src;
> +  let Inst{51-48} = dst;
> +  let Inst{47-32} = BrDst;
> +  let BPFClass = BPF_JMP;
> +}
> +
> +class JSET_RI<string OpcodeStr>
> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
> +                   (outs),
> +                   (ins GPR:$dst, i64imm:$imm, brtarget:$BrDst),
> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
> +                   []> {
> +  bits<4> dst;
> +  bits<16> BrDst;
> +  bits<32> imm;
> +
> +  let Inst{51-48} = dst;
> +  let Inst{47-32} = BrDst;
> +  let Inst{31-0} = imm;
> +  let BPFClass = BPF_JMP;
> +}
> +
> +class JSET_RR_32<string OpcodeStr>
> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
> +                   (outs),
> +                   (ins GPR32:$dst, GPR32:$src, brtarget:$BrDst),
> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
> +                   []> {
> +  bits<4> dst;
> +  bits<4> src;
> +  bits<16> BrDst;
> +
> +  let Inst{55-52} = src;
> +  let Inst{51-48} = dst;
> +  let Inst{47-32} = BrDst;
> +  let BPFClass = BPF_JMP32;
> +}
> +
> +class JSET_RI_32<string OpcodeStr>
> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
> +                   (outs),
> +                   (ins GPR32:$dst, i32imm:$imm, brtarget:$BrDst),
> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
> +                   []> {
> +  bits<4> dst;
> +  bits<16> BrDst;
> +  bits<32> imm;
> +
> +  let Inst{51-48} = dst;
> +  let Inst{47-32} = BrDst;
> +  let Inst{31-0} = imm;
> +  let BPFClass = BPF_JMP32;
> +}
> +
>   multiclass J<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond, PatLeaf Cond32> {
>     def _rr : JMP_RR<Opc, OpcodeStr, Cond>;
>     def _ri : JMP_RI<Opc, OpcodeStr, Cond>;
> @@ -265,6 +329,10 @@ defm JULT : J<BPF_JLT, "<", BPF_CC_LTU, BPF_CC_LTU_32>;
>   defm JULE : J<BPF_JLE, "<=", BPF_CC_LEU, BPF_CC_LEU_32>;
>   defm JSLT : J<BPF_JSLT, "s<", BPF_CC_LT, BPF_CC_LT_32>;
>   defm JSLE : J<BPF_JSLE, "s<=", BPF_CC_LE, BPF_CC_LE_32>;
> +def JSET_RR    : JSET_RR<"&">;
> +def JSET_RI    : JSET_RI<"&">;
> +def JSET_RR_32 : JSET_RR_32<"&">;
> +def JSET_RI_32 : JSET_RI_32<"&">;
>   }
>
>   // ALU instructions
>
> can solve your inline asm issue. We will discuss whether llvm compiler
> should be implementing this instruction from source or not.

I'd say 'yes'. clang/llvm should support such asm syntax.

Jose, Eduard,
Thoughts?

Re: [PATCH] C inlined assembly for reproducing max<min

[Jose E. Marchesi]

> On Wed, Nov 22, 2023 at 10:08 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>>
>> > +SEC("?tc")
>> > +__log_level(2)
>> > +int test_verifier_range(void)
>> > +{
>> > +    asm volatile (
>> > +        "r5 = 100; \
>> > +        r5 /= 3; \
>> > +        w5 >>= 7; \
>> > +        r5 &= -386969681; \
>> > +        r5 -= -884670597; \
>> > +        w0 = w5; \
>> > +        if w0 & 0x894b6a55 goto +2; \
>>
>> So actually it is 'if w0 & 0x894b6a55 goto +2' failed
>> the compilation.
>>
>> Indeed, the above operation is not supported in llvm.
>> See
>>    https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/BPF/BPFInstrFormats.td#L62-L74
>> the missing BPFJumpOp<0x4> which corresponds to JSET.
>>
>> The following llvm patch (on top of llvm-project main branch):
>>
>> diff --git a/llvm/lib/Target/BPF/BPFInstrFormats.td b/llvm/lib/Target/BPF/BPFInstrFormats.td
>> index 841d97efc01c..6ed83d877ac0 100644
>> --- a/llvm/lib/Target/BPF/BPFInstrFormats.td
>> +++ b/llvm/lib/Target/BPF/BPFInstrFormats.td
>> @@ -63,6 +63,7 @@ def BPF_JA   : BPFJumpOp<0x0>;
>>   def BPF_JEQ  : BPFJumpOp<0x1>;
>>   def BPF_JGT  : BPFJumpOp<0x2>;
>>   def BPF_JGE  : BPFJumpOp<0x3>;
>> +def BPF_JSET : BPFJumpOp<0x4>;
>>   def BPF_JNE  : BPFJumpOp<0x5>;
>>   def BPF_JSGT : BPFJumpOp<0x6>;
>>   def BPF_JSGE : BPFJumpOp<0x7>;
>> diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td b/llvm/lib/Target/BPF/BPFInstrInfo.td
>> index 305cbbd34d27..9e75f35efe70 100644
>> --- a/llvm/lib/Target/BPF/BPFInstrInfo.td
>> +++ b/llvm/lib/Target/BPF/BPFInstrInfo.td
>> @@ -246,6 +246,70 @@ class JMP_RI_32<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond>
>>     let BPFClass = BPF_JMP32;
>>   }
>>
>> +class JSET_RR<string OpcodeStr>
>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
>> +                   (outs),
>> +                   (ins GPR:$dst, GPR:$src, brtarget:$BrDst),
>> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
>> +                   []> {
>> +  bits<4> dst;
>> +  bits<4> src;
>> +  bits<16> BrDst;
>> +
>> +  let Inst{55-52} = src;
>> +  let Inst{51-48} = dst;
>> +  let Inst{47-32} = BrDst;
>> +  let BPFClass = BPF_JMP;
>> +}
>> +
>> +class JSET_RI<string OpcodeStr>
>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
>> +                   (outs),
>> +                   (ins GPR:$dst, i64imm:$imm, brtarget:$BrDst),
>> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
>> +                   []> {
>> +  bits<4> dst;
>> +  bits<16> BrDst;
>> +  bits<32> imm;
>> +
>> +  let Inst{51-48} = dst;
>> +  let Inst{47-32} = BrDst;
>> +  let Inst{31-0} = imm;
>> +  let BPFClass = BPF_JMP;
>> +}
>> +
>> +class JSET_RR_32<string OpcodeStr>
>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
>> +                   (outs),
>> +                   (ins GPR32:$dst, GPR32:$src, brtarget:$BrDst),
>> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
>> +                   []> {
>> +  bits<4> dst;
>> +  bits<4> src;
>> +  bits<16> BrDst;
>> +
>> +  let Inst{55-52} = src;
>> +  let Inst{51-48} = dst;
>> +  let Inst{47-32} = BrDst;
>> +  let BPFClass = BPF_JMP32;
>> +}
>> +
>> +class JSET_RI_32<string OpcodeStr>
>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
>> +                   (outs),
>> +                   (ins GPR32:$dst, i32imm:$imm, brtarget:$BrDst),
>> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
>> +                   []> {
>> +  bits<4> dst;
>> +  bits<16> BrDst;
>> +  bits<32> imm;
>> +
>> +  let Inst{51-48} = dst;
>> +  let Inst{47-32} = BrDst;
>> +  let Inst{31-0} = imm;
>> +  let BPFClass = BPF_JMP32;
>> +}
>> +
>>   multiclass J<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond, PatLeaf Cond32> {
>>     def _rr : JMP_RR<Opc, OpcodeStr, Cond>;
>>     def _ri : JMP_RI<Opc, OpcodeStr, Cond>;
>> @@ -265,6 +329,10 @@ defm JULT : J<BPF_JLT, "<", BPF_CC_LTU, BPF_CC_LTU_32>;
>>   defm JULE : J<BPF_JLE, "<=", BPF_CC_LEU, BPF_CC_LEU_32>;
>>   defm JSLT : J<BPF_JSLT, "s<", BPF_CC_LT, BPF_CC_LT_32>;
>>   defm JSLE : J<BPF_JSLE, "s<=", BPF_CC_LE, BPF_CC_LE_32>;
>> +def JSET_RR    : JSET_RR<"&">;
>> +def JSET_RI    : JSET_RI<"&">;
>> +def JSET_RR_32 : JSET_RR_32<"&">;
>> +def JSET_RI_32 : JSET_RI_32<"&">;
>>   }
>>
>>   // ALU instructions
>>
>> can solve your inline asm issue. We will discuss whether llvm compiler
>> should be implementing this instruction from source or not.
>
> I'd say 'yes'. clang/llvm should support such asm syntax.
>
> Jose, Eduard,
> Thoughts?

We already support it in GAS:


  $ echo 'if w0 & 0x894b6a55 goto +2' | bpf-unknown-none-as -mdialect=pseudoc -
  $ bpf-unknown-none-objdump -M hex,pseudoc -d a.out
  
  a.out:     file format elf64-bpfle
  
  
  Disassembly of section .text:
  
  0000000000000000 <.text>:
     0:	46 00 02 00 55 6a 4b 89 	if w0&0x894b6a55 goto 0x2


We weren't aware we were diverging with llvm by doing so.  We support
syntax for all the conditional jump instructions using the following
operators:

  BPF_JEQ    ==
  BPF_JGT    >
  BPF_JSGT   s>
  BPF_JGE    >=
  BPF_JSGE   s>=
  BPF_JLT    <
  BPF_JLST   s<
  BPF_JLE    <=
  BPF_JSLE   s<=
  BPF_JSET   &
  BPF_JNE    !=

Re: [PATCH] C inlined assembly for reproducing max<min

[Yonghong Song]

On 11/22/23 1:37 PM, Jose E. Marchesi wrote:
>> On Wed, Nov 22, 2023 at 10:08 AM Yonghong Song <yonghong.song@linux.dev> wrote:
>>>> +SEC("?tc")
>>>> +__log_level(2)
>>>> +int test_verifier_range(void)
>>>> +{
>>>> +    asm volatile (
>>>> +        "r5 = 100; \
>>>> +        r5 /= 3; \
>>>> +        w5 >>= 7; \
>>>> +        r5 &= -386969681; \
>>>> +        r5 -= -884670597; \
>>>> +        w0 = w5; \
>>>> +        if w0 & 0x894b6a55 goto +2; \
>>> So actually it is 'if w0 & 0x894b6a55 goto +2' failed
>>> the compilation.
>>>
>>> Indeed, the above operation is not supported in llvm.
>>> See
>>>     https://github.com/llvm/llvm-project/blob/main/llvm/lib/Target/BPF/BPFInstrFormats.td#L62-L74
>>> the missing BPFJumpOp<0x4> which corresponds to JSET.
>>>
>>> The following llvm patch (on top of llvm-project main branch):
>>>
>>> diff --git a/llvm/lib/Target/BPF/BPFInstrFormats.td b/llvm/lib/Target/BPF/BPFInstrFormats.td
>>> index 841d97efc01c..6ed83d877ac0 100644
>>> --- a/llvm/lib/Target/BPF/BPFInstrFormats.td
>>> +++ b/llvm/lib/Target/BPF/BPFInstrFormats.td
>>> @@ -63,6 +63,7 @@ def BPF_JA   : BPFJumpOp<0x0>;
>>>    def BPF_JEQ  : BPFJumpOp<0x1>;
>>>    def BPF_JGT  : BPFJumpOp<0x2>;
>>>    def BPF_JGE  : BPFJumpOp<0x3>;
>>> +def BPF_JSET : BPFJumpOp<0x4>;
>>>    def BPF_JNE  : BPFJumpOp<0x5>;
>>>    def BPF_JSGT : BPFJumpOp<0x6>;
>>>    def BPF_JSGE : BPFJumpOp<0x7>;
>>> diff --git a/llvm/lib/Target/BPF/BPFInstrInfo.td b/llvm/lib/Target/BPF/BPFInstrInfo.td
>>> index 305cbbd34d27..9e75f35efe70 100644
>>> --- a/llvm/lib/Target/BPF/BPFInstrInfo.td
>>> +++ b/llvm/lib/Target/BPF/BPFInstrInfo.td
>>> @@ -246,6 +246,70 @@ class JMP_RI_32<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond>
>>>      let BPFClass = BPF_JMP32;
>>>    }
>>>
>>> +class JSET_RR<string OpcodeStr>
>>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
>>> +                   (outs),
>>> +                   (ins GPR:$dst, GPR:$src, brtarget:$BrDst),
>>> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
>>> +                   []> {
>>> +  bits<4> dst;
>>> +  bits<4> src;
>>> +  bits<16> BrDst;
>>> +
>>> +  let Inst{55-52} = src;
>>> +  let Inst{51-48} = dst;
>>> +  let Inst{47-32} = BrDst;
>>> +  let BPFClass = BPF_JMP;
>>> +}
>>> +
>>> +class JSET_RI<string OpcodeStr>
>>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
>>> +                   (outs),
>>> +                   (ins GPR:$dst, i64imm:$imm, brtarget:$BrDst),
>>> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
>>> +                   []> {
>>> +  bits<4> dst;
>>> +  bits<16> BrDst;
>>> +  bits<32> imm;
>>> +
>>> +  let Inst{51-48} = dst;
>>> +  let Inst{47-32} = BrDst;
>>> +  let Inst{31-0} = imm;
>>> +  let BPFClass = BPF_JMP;
>>> +}
>>> +
>>> +class JSET_RR_32<string OpcodeStr>
>>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_X.Value,
>>> +                   (outs),
>>> +                   (ins GPR32:$dst, GPR32:$src, brtarget:$BrDst),
>>> +                   "if $dst "#OpcodeStr#" $src goto $BrDst",
>>> +                   []> {
>>> +  bits<4> dst;
>>> +  bits<4> src;
>>> +  bits<16> BrDst;
>>> +
>>> +  let Inst{55-52} = src;
>>> +  let Inst{51-48} = dst;
>>> +  let Inst{47-32} = BrDst;
>>> +  let BPFClass = BPF_JMP32;
>>> +}
>>> +
>>> +class JSET_RI_32<string OpcodeStr>
>>> +    : TYPE_ALU_JMP<BPF_JSET.Value, BPF_K.Value,
>>> +                   (outs),
>>> +                   (ins GPR32:$dst, i32imm:$imm, brtarget:$BrDst),
>>> +                   "if $dst "#OpcodeStr#" $imm goto $BrDst",
>>> +                   []> {
>>> +  bits<4> dst;
>>> +  bits<16> BrDst;
>>> +  bits<32> imm;
>>> +
>>> +  let Inst{51-48} = dst;
>>> +  let Inst{47-32} = BrDst;
>>> +  let Inst{31-0} = imm;
>>> +  let BPFClass = BPF_JMP32;
>>> +}
>>> +
>>>    multiclass J<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond, PatLeaf Cond32> {
>>>      def _rr : JMP_RR<Opc, OpcodeStr, Cond>;
>>>      def _ri : JMP_RI<Opc, OpcodeStr, Cond>;
>>> @@ -265,6 +329,10 @@ defm JULT : J<BPF_JLT, "<", BPF_CC_LTU, BPF_CC_LTU_32>;
>>>    defm JULE : J<BPF_JLE, "<=", BPF_CC_LEU, BPF_CC_LEU_32>;
>>>    defm JSLT : J<BPF_JSLT, "s<", BPF_CC_LT, BPF_CC_LT_32>;
>>>    defm JSLE : J<BPF_JSLE, "s<=", BPF_CC_LE, BPF_CC_LE_32>;
>>> +def JSET_RR    : JSET_RR<"&">;
>>> +def JSET_RI    : JSET_RI<"&">;
>>> +def JSET_RR_32 : JSET_RR_32<"&">;
>>> +def JSET_RI_32 : JSET_RI_32<"&">;
>>>    }
>>>
>>>    // ALU instructions
>>>
>>> can solve your inline asm issue. We will discuss whether llvm compiler
>>> should be implementing this instruction from source or not.
>> I'd say 'yes'. clang/llvm should support such asm syntax.
>>
>> Jose, Eduard,
>> Thoughts?
> We already support it in GAS:
>
>
>    $ echo 'if w0 & 0x894b6a55 goto +2' | bpf-unknown-none-as -mdialect=pseudoc -
>    $ bpf-unknown-none-objdump -M hex,pseudoc -d a.out
>    
>    a.out:     file format elf64-bpfle
>    
>    
>    Disassembly of section .text:
>    
>    0000000000000000 <.text>:
>       0:	46 00 02 00 55 6a 4b 89 	if w0&0x894b6a55 goto 0x2
>
>
> We weren't aware we were diverging with llvm by doing so.  We support
> syntax for all the conditional jump instructions using the following
> operators:
>
>    BPF_JEQ    ==
>    BPF_JGT    >
>    BPF_JSGT   s>
>    BPF_JGE    >=
>    BPF_JSGE   s>=
>    BPF_JLT    <
>    BPF_JLST   s<
>    BPF_JLE    <=
>    BPF_JSLE   s<=
>    BPF_JSET   &
>    BPF_JNE    !=

Sounds good. Eduard inthe other thread has similar opinion. Will add asm support in llvm soon.

Re: [PATCH] C inlined assembly for reproducing max<min

[Eduard Zingerman]

On Wed, 2023-11-22 at 10:15 -0800, Alexei Starovoitov wrote:
[...]
> >   multiclass J<BPFJumpOp Opc, string OpcodeStr, PatLeaf Cond, PatLeaf Cond32> {
> >     def _rr : JMP_RR<Opc, OpcodeStr, Cond>;
> >     def _ri : JMP_RI<Opc, OpcodeStr, Cond>;
> > @@ -265,6 +329,10 @@ defm JULT : J<BPF_JLT, "<", BPF_CC_LTU, BPF_CC_LTU_32>;
> >   defm JULE : J<BPF_JLE, "<=", BPF_CC_LEU, BPF_CC_LEU_32>;
> >   defm JSLT : J<BPF_JSLT, "s<", BPF_CC_LT, BPF_CC_LT_32>;
> >   defm JSLE : J<BPF_JSLE, "s<=", BPF_CC_LE, BPF_CC_LE_32>;
> > +def JSET_RR    : JSET_RR<"&">;
> > +def JSET_RI    : JSET_RI<"&">;
> > +def JSET_RR_32 : JSET_RR_32<"&">;
> > +def JSET_RI_32 : JSET_RI_32<"&">;
> >   }
> > 
> >   // ALU instructions
> > 
> > can solve your inline asm issue. We will discuss whether llvm compiler
> > should be implementing this instruction from source or not.
> 
> I'd say 'yes'. clang/llvm should support such asm syntax.
> 
> Jose, Eduard,
> Thoughts?

I agree, since instruction is documented it should have assembly
representation. All other instructions from instruction-set.rst seem
to have one.

Re: max<min after jset

[Yonghong Song]

On 11/21/23 12:32 PM, Tao Lyu wrote:
> Hi,
>
> The eBPF program shown below leads to an reversed min and max
> after insn 6 "if w0 & 0x894b6a55 goto +2",
> whic means max < min.
>
> Here is the introduction how it happens.
>
> Before insn 6,
> the range of r0 expressed by the min and max field is
> min1 = 884670597, max1 = 900354100
> And the range expressed by the var_off=(0x34000000; 0x1ff5fbf))
> is min2=872415232, max2=905928639.
>
> ---min2-----------------------min1-----max1-----max2---
>
> Here we can see that the range expressed by var_off is wider than that of min and max.
>
> When verifying insn6,
> it first uses the var_off and immediate "0x894b6a55" to
> calculate the new var_off=(0x34b00000; 0x415aa).
> The range expressed by the new var_off is:
> min3=883949568, max3=884217258
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>
> And then it will calculate the new min and max by:
> (1) new-min = MAX(min3, min1) = min1
> (2) new-max = MIN(max3, max1) = max3
>
> ---min2-----min3-----max3-----min1-----max1-----max2---
>           "new-max"          "new-min"
>
> Now, the new-max becomes less than the new min.
>
> Notably, [min1, max1] can never make "w0 & 0x894b6a55 == 0"
> and thus cannot goes the fall-through branch.
> In other words, actually the fall-trough branch is a dead path.
>
> BTW, I cannot successfully compile this instruciton "if w0 != 0 goto +2;\"
> in the c inline assembly code.
> So I can only attach the bytecodes.
>
> Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
> ---
>   .../selftests/bpf/verifier/jset_reversed_range.c  | 15 +++++++++++++++
>   1 file changed, 15 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/verifier/jset_reversed_range.c
>
> diff --git a/tools/testing/selftests/bpf/verifier/jset_reversed_range.c b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> new file mode 100644
> index 000000000000..734f492a2a96
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/verifier/jset_reversed_range.c
> @@ -0,0 +1,15 @@
> +{
> +    "BPF_JSET: incorrect scalar range",
> +    .insns = {
> +    BPF_MOV64_IMM(BPF_REG_5, 100),
> +    BPF_ALU64_IMM(BPF_DIV, BPF_REG_5, 3),
> +    BPF_ALU32_IMM(BPF_RSH, BPF_REG_5, 7),
> +    BPF_ALU64_IMM(BPF_AND, BPF_REG_5, -386969681),
> +    BPF_ALU64_IMM(BPF_SUB, BPF_REG_5, -884670597),
> +    BPF_MOV32_REG(BPF_REG_0, BPF_REG_5),
> +    BPF_JMP32_IMM(BPF_JSET, BPF_REG_0, 0x894b6a55, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 1),
> +    BPF_MOV64_IMM(BPF_REG_0, 0),
> +    BPF_EXIT_INSN(),
> +    },
> +},

Tao Lyu,

The llvm patch to support BPF_JSET asm has been merged into upstream.
    https://github.com/yonghong-song/llvm-project/commit/e247e6ff272ce70003ca67f62be178f332f9de0f

Now you can write inline asm code with BPF_JSET insn with latest llvm18.
If you intend to submit a patch to the kernel, please guard the test case
with
     #if __clang_major__ >= 18

This should also facilitate to add inline asm test cases with BPF_JSET
in bpf selftests.

Thanks,
Yonghong

[PATCH] C inlined assembly for reproducing max<min

[Tao Lyu]

Hi,

We discussed the max<min issue in [1].
But it cannot reproduced with a C inlined assembly test,
as llvm doesn't support 'jset' assembly.

Thanks to Yonghong's patch [2], 
it is now supported in the latest llvm-18.

So, I resubmit the C inlined assembly test for the max<min issue here again.

[1] https://lore.kernel.org/bpf/20231121173206.3594040-1-tao.lyu@epfl.ch/
[2] https://github.com/yonghong-song/llvm-project/commit/e247e6ff272ce70003ca67f62be178f332f9de0f

Signed-off-by: Tao Lyu <tao.lyu@epfl.ch>
---
 .../selftests/bpf/prog_tests/verifier.c       |  2 ++
 .../selftests/bpf/progs/verifier_range.c      | 29 +++++++++++++++++++
 2 files changed, 31 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_range.c

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index e5c61aa6604a..3a5d746f392d 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -77,6 +77,7 @@
 #include "verifier_xadd.skel.h"
 #include "verifier_xdp.skel.h"
 #include "verifier_xdp_direct_packet_access.skel.h"
+#include "verifier_range.skel.h"
 
 #define MAX_ENTRIES 11
 
@@ -184,6 +185,7 @@ void test_verifier_var_off(void)              { RUN(verifier_var_off); }
 void test_verifier_xadd(void)                 { RUN(verifier_xadd); }
 void test_verifier_xdp(void)                  { RUN(verifier_xdp); }
 void test_verifier_xdp_direct_packet_access(void) { RUN(verifier_xdp_direct_packet_access); }
+void test_verifier_range(void)                { RUN(verifier_range); }
 
 static int init_test_val_map(struct bpf_object *obj, char *map_name)
 {
diff --git a/tools/testing/selftests/bpf/progs/verifier_range.c b/tools/testing/selftests/bpf/progs/verifier_range.c
new file mode 100644
index 000000000000..affe09117b0f
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_range.c
@@ -0,0 +1,29 @@
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+#if __clang_major__ >= 18
+
+SEC("?tc")
+__log_level(2)
+int test_verifier_range(void)
+{
+    asm volatile (
+        "r5 = 100; \
+        r5 /= 3; \
+        w5 >>= 7; \
+        r5 &= -386969681; \
+        r5 -= -884670597; \
+        w0 = w5; \
+        if w0 & 0x894b6a55 goto +2; \
+        r2 = 1; \
+        r2 = 1; \
+        r0 = 0; \
+        "
+    );
+    return 0;
+}
+
+char _license[] SEC("license") = "GPL";
+
+#endif
-- 
2.25.1