[BPF] handle unsigned icmp ops in BPFAdjustOpt pass
authorYonghong Song <yhs@fb.com>
Thu, 17 Mar 2022 05:09:59 +0000 (22:09 -0700)
committerYonghong Song <yhs@fb.com>
Thu, 17 Mar 2022 23:24:39 +0000 (16:24 -0700)
commit2e94d8e67a91fc84f48cf6b44c8558c3d9712f87
treedd8767f20c495191febb4a3d730e7af8b4c1fa4f
parent6c4931e7d085510930e56656ad141e745b1ca72e
[BPF] handle unsigned icmp ops in BPFAdjustOpt pass

When investigating an issue with bcc tool inject.py, I found
a verifier failure with latest clang. The portion of code
can be illustrated as below:
  struct pid_struct {
    u64 curr_call;
    u64 conds_met;
    u64 stack[2];
  };
  struct pid_struct *bpf_map_lookup_elem();
  int foo() {
    struct pid_struct *p = bpf_map_lookup_elem();
    if (!p) return 0;
    p->curr_call--;
    if (p->conds_met < 1 || p->conds_met >= 3)
        return 0;
    if (p->stack[p->conds_met - 1] == p->curr_call)
        p->conds_met--;
    ...
  }

The verifier failure looks like:
  ...
  8: (79) r1 = *(u64 *)(r0 +0)
   R0_w=map_value(id=0,off=0,ks=4,vs=32,imm=0) R10=fp0 fp-8=mmmm????
  9: (07) r1 += -1
  10: (7b) *(u64 *)(r0 +0) = r1
   R0_w=map_value(id=0,off=0,ks=4,vs=32,imm=0) R1_w=inv(id=0) R10=fp0 fp-8=mmmm????
  11: (79) r2 = *(u64 *)(r0 +8)
   R0_w=map_value(id=0,off=0,ks=4,vs=32,imm=0) R1_w=inv(id=0) R10=fp0 fp-8=mmmm????
  12: (bf) r3 = r2
  13: (07) r3 += -3
  14: (b7) r4 = -2
  15: (2d) if r4 > r3 goto pc+13
   R0=map_value(id=0,off=0,ks=4,vs=32,imm=0) R1=inv(id=0) R2=inv(id=2)
   R3=inv(id=0,umin_value=18446744073709551614,var_off=(0xffffffff00000000; 0xffffffff))
   R4=inv-2 R10=fp0 fp-8=mmmm????
  16: (07) r2 += -1
  17: (bf) r3 = r2
  18: (67) r3 <<= 3
  19: (bf) r4 = r0
  20: (0f) r4 += r3
  math between map_value pointer and register with unbounded min value is not allowed

Here the compiler optimized "p->conds_met < 1 || p->conds_met >= 3" to
  r2 = p->conds_met
  r3 = r2
  r3 += -3
  r4 = -2
  if (r3 < r4) return 0
  r2 += -1
  r3 = r2
  ...
In the above, r3 is initially equal to r2, but is modified used by the comparison.
But later on r2 is used again. This caused verification failure.

BPF backend has a pass, AdjustOpt, to prevent such transformation, but only
focused on signed integers since typical bpf helper returns signed integers.
To fix this case, let us handle unsigned integers as well.

Differential Revision: https://reviews.llvm.org/D121937
llvm/lib/Target/BPF/BPFAdjustOpt.cpp
llvm/test/CodeGen/BPF/adjust-opt-icmp6.ll [new file with mode: 0644]