[BPF] Check jump and memory offsets to avoid truncation

[eddyz87]

Summary

The following assembly code should issue two errors specifying that
both jump and load offsets are out of range:

if r1 > r2 goto +100500
r1 = *(u64 *)(r1 - 100500)

This commit updates BPFAsmParser to check that:

• offset specified for jump is either identifier (label) or a 16-bit signed constant;
• offset specified for memory operations is a signed 16-bit constant.

(Which matches expectations in the BPFELFObjectWriter and
BPFMCCodeEmitter).

[eddyz87]

Hi Yonghong,

Could you please take a look?
This is a follow-up for this kernel mailing list thread. I diverged from the suggested implementation and used approach described in this thread. I used the following reasoning:

• range checks are needed for offsets and immediates, which are used in many instructions;
• if check is done in BPFMCCodeEmitter::encodeInstruction correct per-instruction operand indexes are needed to extract opreand from MCInst => big switch which duplicates information already encoded in the BPFInstrInfo.td;
• on the other hand, adjusting operand declarations in BPFInstrInfo.td is much more concise.

What do you think?

[yonghong-song]

Thanks. This is indeed much better to detect during insn matching stage.

[eddyz87]

Rebase, will merge this in after CI run.

llvm/lib/Target/BPF/AsmParser/BPFAsmParser.cpp

bool isConstantImm() const {
     return isImm() && isa<MCConstantExpr>(getImm());
   }
 
   int64_t getConstantImm() const {
     const MCExpr *Val = getImm();
     return static_cast<const MCConstantExpr *>(Val)->getValue();
   }
 
-  bool isSImm12() const {
-    return (isConstantImm() && isInt<12>(getConstantImm()));
+  bool isSImm16() const {
+    return (isConstantImm() && isInt<16>(getConstantImm()));
   }
 
+  bool isSymbolRef() const { return isImm() && isa<MCSymbolRefExpr>(getImm()); }
+
+  bool isBrTarget() const { return isSymbolRef() || isSImm16(); }
+
   /// getStartLoc - Gets location of the first token of this operand
   SMLoc getStartLoc() const override { return StartLoc; }
   /// getEndLoc - Gets location of the last token of this operand
   SMLoc getEndLoc() const override { return EndLoc; }
 
   unsigned getReg() const override {
     assert(Kind == Register && "Invalid type access!");
     return Reg.RegNum;
if (ErrorInfo != ~0U) {
 
       ErrorLoc = ((BPFOperand &)*Operands[ErrorInfo]).getStartLoc();
 
       if (ErrorLoc == SMLoc())
         ErrorLoc = IDLoc;
     }
 
     return Error(ErrorLoc, "invalid operand for instruction");
+  case Match_InvalidBrTarget:
+    return Error(Operands[ErrorInfo]->getStartLoc(),
+                 "operand is not an identifier or 16-bit signed integer");
+  case Match_InvalidSImm16:
+    return Error(Operands[ErrorInfo]->getStartLoc(),
+                 "operand is not a 16-bit signed integer");
   }
 
   llvm_unreachable("Unknown match type detected!");
 }
 
 bool BPFAsmParser::parseRegister(MCRegister &Reg, SMLoc &StartLoc,
                                  SMLoc &EndLoc) {
   if (!tryParseRegister(Reg, StartLoc, EndLoc).isSuccess())

llvm/lib/Target/BPF/BPFInstrInfo.td

 def BPFHasLdsx : Predicate<"Subtarget->hasLdsx()">;
 def BPFHasMovsx : Predicate<"Subtarget->hasMovsx()">;
 def BPFHasBswap : Predicate<"Subtarget->hasBswap()">;
 def BPFHasSdivSmod : Predicate<"Subtarget->hasSdivSmod()">;
 def BPFNoMovsx : Predicate<"!Subtarget->hasMovsx()">;
 def BPFNoBswap : Predicate<"!Subtarget->hasBswap()">;
 def BPFHasStoreImm : Predicate<"Subtarget->hasStoreImm()">;
 
+class ImmediateAsmOperand<string name> : AsmOperandClass {
+  let Name = name;
+  let RenderMethod = "addImmOperands";
+  let DiagnosticType = !strconcat("Invalid", name);
+}
+
+def SImm16AsmOperand : ImmediateAsmOperand<"SImm16">;
+
 def brtarget : Operand<OtherVT> {
   let PrintMethod = "printBrTargetOperand";
+  let ParserMatchClass = ImmediateAsmOperand<"BrTarget">;
 }
 def calltarget : Operand<i64>;
 
 def u64imm   : Operand<i64> {
   let PrintMethod = "printImm64Operand";
 }
 
+def s16imm : Operand<i16> {
+  let ParserMatchClass = SImm16AsmOperand;
+}
+
 def gpr_or_imm : Operand<i64>;
 
 def i64immSExt32 : PatLeaf<(i64 imm),
                 [{return isInt<32>(N->getSExtValue()); }]>;
 def i32immSExt32 : PatLeaf<(i32 imm),
                 [{return isInt<32>(N->getSExtValue()); }]>;
 def i64immZExt32 : PatLeaf<(i64 imm),
                 [{return isUInt<32>(N->getZExtValue()); }]>;
 
 def imm_to_i64 : SDNodeXForm<timm, [{
   return CurDAG->getTargetConstant(N->getZExtValue(), SDLoc(N), MVT::i64);
 }]>;
 
 // Addressing modes.
 def ADDRri : ComplexPattern<i64, 2, "SelectAddr", [], []>;
 def FIri : ComplexPattern<i64, 2, "SelectFIAddr", [add, or], []>;
 
 // Address operands
 def MEMri : Operand<i64> {
   let PrintMethod = "printMemOperand";
   let EncoderMethod = "getMemoryOpValue";
   let DecoderMethod = "decodeMemoryOpValue";
-  let MIOperandInfo = (ops GPR, i16imm);
+  let MIOperandInfo = (ops GPR, s16imm);
 }
 
 // Conditional code predicates - used for pattern matching for jump instructions
 def BPF_CC_EQ  : PatLeaf<(i64 imm),
                          [{return (N->getZExtValue() == ISD::SETEQ);}]>;
 def BPF_CC_NE  : PatLeaf<(i64 imm),
                          [{return (N->getZExtValue() == ISD::SETNE);}]>;
 def BPF_CC_GE  : PatLeaf<(i64 imm),

llvm/test/MC/BPF/bad-offsets.s

+# RUN: not llvm-mc -mcpu=v4 -triple bpfel < %s 2>&1 \
+# RUN:   | grep 'error: operand is not an identifier or 16-bit signed integer' \
+# RUN:   | count 2
+# RUN: not llvm-mc -mcpu=v4 -triple bpfel < %s 2>&1 \
+# RUN:   | grep 'error: operand is not a 16-bit signed integer' \
+# RUN:   | count 25
+        if r1 > r2 goto +70000
+        if r1 > r2 goto -70000
+        *(u64 *)(r1 + 70000) = 10
+        *(u32 *)(r1 - 70000) = 10
+        *(u16 *)(r1 - 70000) = 10
+        *(u8  *)(r1 - 70000) = 10
+        *(u64 *)(r1 + 70000) = r1
+        *(u32 *)(r1 - 70000) = r1
+        *(u16 *)(r1 - 70000) = r1
+        *(u8  *)(r1 - 70000) = r1
+        r1 = *(u64 *)(r1 + 70000)
+        r1 = *(u32 *)(r1 - 70000)
+        r1 = *(u16 *)(r1 - 70000)
+        r1 = *(u8  *)(r1 - 70000)
+        r1 = *(s32 *)(r1 + 70000)
+        r1 = *(s16 *)(r1 - 70000)
+        r1 = *(s8  *)(r1 - 70000)
+        lock *(u32*)(r1 + 70000) += w2
+        lock *(u32*)(r1 - 70000) &= w2
+        lock *(u32*)(r1 - 70000) |= w2
+        lock *(u32*)(r1 - 70000) ^= w2
+        r0 = atomic_fetch_add((u64 *)(r1 + 70000), r0)
+        r0 = atomic_fetch_and((u64 *)(r1 + 70000), r0)
+        r0 = atomic_fetch_xor((u64 *)(r1 + 70000), r0)
+        r0 = atomic_fetch_or((u64 *)(r1 + 70000), r0)
+        w0 = cmpxchg32_32(r1 + 70000, w0, w1)
+        r0 = cmpxchg_64(r1 + 70000, r0, r1)

llvm/test/MC/BPF/expr-offset.s

+# RUN: llvm-mc -triple bpfel -filetype=obj < %s \
+# RUN:       | llvm-objdump --no-print-imm-hex --no-show-raw-insn -d - \
+# RUN:       | FileCheck %s
+
+.equ foo, -1
+        if r1 > r2 goto foo + 2
+        exit
+        exit
+
+# CHECK: if r1 > r2 goto +1
+# CHECK: exit
+# CHECK: exit