Diagnose if a SLEB128 is too large to fit in an int64_t.

[rsmith]

Summary

Previously we'd hit UB due to an invalid left shift operand.

Also fix the WASM emitter to properly use SLEB128 encoding instead of
ULEB128 encoding for signed fields so that negative numbers don't
result in overly-large values that we can't read back any more.

In passing, don't diagnose a non-canonical ULEB128 that fits in a uint64_t but
has redundant trailing zero bytes.

[dblaikie]

Looks good - thanks!

[sbc100]

llvm/lib/ObjectYAML/WasmEmitter.cpp

585

I'm not sure about this part. The addend is currently defined to be the same data type regardless of the encoding of the relocation itself.

The addend is the value is added to the to the value before writing to relocation location. The encoding used when writing to the relocation address (LEB vs SLEB vs I32, etc) I think is independent of this.

See the definition of addend in https://github.com/WebAssembly/tool-conventions/blob/master/Linking.md

585

Regardless of the discussion here it might make sense to split out this wasm-specific part of the change.

[sbc100]

llvm/lib/ObjectYAML/WasmEmitter.cpp

585

It looks like perhaps the correct fix it to use encodeSLEB128 universally here.

[rsmith]

Always use SLEB for Wasm reloc addeds.

[nlguillemot]

I think this conveniently solves the TODO that I had in my in-review patch here: https://reviews.llvm.org/D78797
Thanks!

llvm/include/llvm/Support/LEB128.h

do {
     if (p == end) {
       if (error)
         *error = "malformed uleb128, extends past end";
       if (n)
         *n = (unsigned)(p - orig_p);
       return 0;
     }
     uint64_t Slice = *p & 0x7f;
-    if (Shift >= 64 || Slice << Shift >> Shift != Slice) {
+    if ((Shift >= 64 && Slice != 0) || Slice << Shift >> Shift != Slice) {
       if (error)
         *error = "uleb128 too big for uint64";
       if (n)
         *n = (unsigned)(p - orig_p);
       return 0;
     }
-    Value += uint64_t(*p & 0x7f) << Shift;
+    Value += Slice << Shift;
     Shift += 7;
   } while (*p++ >= 128);
   if (n)
     *n = (unsigned)(p - orig_p);
   return Value;
 }
 
 /// Utility function to decode a SLEB128 value.
inline int64_t decodeSLEB128(const uint8_t *p, unsigned *n = nullptr,
   do {
     if (p == end) {
       if (error)
         *error = "malformed sleb128, extends past end";
       if (n)
         *n = (unsigned)(p - orig_p);
       return 0;
     }
-    Byte = *p++;
-    Value |= (uint64_t(Byte & 0x7f) << Shift);
+    Byte = *p;
+    int64_t Slice = Byte & 0x7f;
+    if ((Shift >= 64 && Slice != (Value < 0 ? 0x7f : 0x00)) ||
+        (Shift == 63 && Slice != 0 && Slice != 0x7f)) {
+      if (error)
+        *error = "sleb128 too big for int64";
+      if (n)
+        *n = (unsigned)(p - orig_p);
+      return 0;
+    }
+    Value |= Slice << Shift;
     Shift += 7;
+    ++p;
   } while (Byte >= 128);
   // Sign extend negative numbers if needed.
   if (Shift < 64 && (Byte & 0x40))
     Value |= (-1ULL) << Shift;
   if (n)
     *n = (unsigned)(p - orig_p);
   return Value;
 }

llvm/lib/ObjectYAML/WasmEmitter.cpp

for (auto Reloc : Sec.Relocations) {
     case wasm::R_WASM_MEMORY_ADDR_LEB64:
     case wasm::R_WASM_MEMORY_ADDR_SLEB:
     case wasm::R_WASM_MEMORY_ADDR_SLEB64:
     case wasm::R_WASM_MEMORY_ADDR_I32:
     case wasm::R_WASM_MEMORY_ADDR_I64:
     case wasm::R_WASM_FUNCTION_OFFSET_I32:
     case wasm::R_WASM_FUNCTION_OFFSET_I64:
     case wasm::R_WASM_SECTION_OFFSET_I32:
-      encodeULEB128(Reloc.Addend, OS);
+      encodeSLEB128(Reloc.Addend, OS);
+      break;
     }
   }
 }
 
 bool WasmWriter::writeWasm(raw_ostream &OS) {
   // Write headers
   OS.write(wasm::WasmMagic, sizeof(wasm::WasmMagic));
   writeUint32(OS, Obj.Header.Version);
 
   // Write each section
   llvm::object::WasmSectionOrderChecker Checker;
   for (const std::unique_ptr<WasmYAML::Section> &Sec : Obj.Sections) {
     StringRef SecName = "";
     if (auto S = dyn_cast<WasmYAML::CustomSection>(Sec.get()))

llvm/unittests/Support/LEB128Test.cpp

#define EXPECT_DECODE_ULEB128_EQ(EXPECTED, VALUE) \
 
   // Decode ULEB128 with extra padding bytes
   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x00");
   EXPECT_DECODE_ULEB128_EQ(0u, "\x80\x80\x00");
   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x00");
   EXPECT_DECODE_ULEB128_EQ(0x7fu, "\xff\x80\x00");
   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x00");
   EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x80\x00");
+  EXPECT_DECODE_ULEB128_EQ(0x80u, "\x80\x81\x80\x80\x80\x80\x80\x80\x80\x00");
+  EXPECT_DECODE_ULEB128_EQ(0x80000000'00000000ul,
+                           "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x01");
 
 #undef EXPECT_DECODE_ULEB128_EQ
 }
 
+TEST(LEB128Test, DecodeInvalidULEB128) {
+#define EXPECT_INVALID_ULEB128(VALUE, ERROR_OFFSET)                            \
+  do {                                                                         \
+    const uint8_t *Value = reinterpret_cast<const uint8_t *>(VALUE);           \
+    const char *Error = nullptr;                                               \
+    unsigned ErrorOffset = 0;                                                  \
+    uint64_t Actual =                                                          \
+        decodeULEB128(Value, &ErrorOffset, Value + strlen(VALUE), &Error);     \
+    EXPECT_NE(Error, nullptr);                                                 \
+    EXPECT_EQ(0ul, Actual);                                                    \
+    EXPECT_EQ(ERROR_OFFSET, ErrorOffset);                                      \
+  } while (0)
+
+  // Buffer overflow.
+  EXPECT_INVALID_ULEB128("", 0u);
+  EXPECT_INVALID_ULEB128("\x80", 1u);
+
+  // Does not fit in 64 bits.
+  EXPECT_INVALID_ULEB128("\x80\x80\x80\x80\x80\x80\x80\x80\x80\x02", 9u);
+  EXPECT_INVALID_ULEB128("\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x02", 10u);
+
+#undef EXPECT_INVALID_ULEB128
+}
+
 TEST(LEB128Test, DecodeSLEB128) {
 #define EXPECT_DECODE_SLEB128_EQ(EXPECTED, VALUE) \
   do { \
     unsigned ActualSize = 0; \
     int64_t Actual = decodeSLEB128(reinterpret_cast<const uint8_t *>(VALUE), \
                                     &ActualSize); \
     EXPECT_EQ(sizeof(VALUE) - 1, ActualSize); \
     EXPECT_EQ(EXPECTED, Actual); \
#define EXPECT_DECODE_SLEB128_EQ(EXPECTED, VALUE) \
 
   // Decode unnormalized SLEB128 with extra padding bytes.
   EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x00");
   EXPECT_DECODE_SLEB128_EQ(0L, "\x80\x80\x00");
   EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x00");
   EXPECT_DECODE_SLEB128_EQ(0x7fL, "\xff\x80\x00");
   EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x00");
   EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x80\x00");
+  EXPECT_DECODE_SLEB128_EQ(0x80L, "\x80\x81\x80\x80\x80\x80\x80\x80\x80\x00");
+  EXPECT_DECODE_SLEB128_EQ(-2L, "\xFE\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7F");
+  EXPECT_DECODE_SLEB128_EQ(INT64_MIN,
+                           "\x80\x80\x80\x80\x80\x80\x80\x80\x80\x7F");
+  EXPECT_DECODE_SLEB128_EQ(INT64_MAX,
+                           "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x00");
 
 #undef EXPECT_DECODE_SLEB128_EQ
 }
 
+TEST(LEB128Test, DecodeInvalidSLEB128) {
+#define EXPECT_INVALID_SLEB128(VALUE, ERROR_OFFSET)                            \
+  do {                                                                         \
+    const uint8_t *Value = reinterpret_cast<const uint8_t *>(VALUE);           \
+    const char *Error = nullptr;                                               \
+    unsigned ErrorOffset = 0;                                                  \
+    uint64_t Actual =                                                          \
+        decodeSLEB128(Value, &ErrorOffset, Value + strlen(VALUE), &Error);     \
+    EXPECT_NE(Error, nullptr);                                                 \
+    EXPECT_EQ(0ul, Actual);                                                    \
+    EXPECT_EQ(ERROR_OFFSET, ErrorOffset);                                      \
+  } while (0)
+
+  // Buffer overflow.
+  EXPECT_INVALID_SLEB128("", 0u);
+  EXPECT_INVALID_SLEB128("\x80", 1u);
+
+  // Does not fit in 64 bits.
+  EXPECT_INVALID_SLEB128("\x80\x80\x80\x80\x80\x80\x80\x80\x80\x01", 9u);
+  EXPECT_INVALID_SLEB128("\x80\x80\x80\x80\x80\x80\x80\x80\x80\x7E", 9u);
+  EXPECT_INVALID_SLEB128("\x80\x80\x80\x80\x80\x80\x80\x80\x80\x80\x02", 10u);
+  EXPECT_INVALID_SLEB128("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7E", 9u);
+  EXPECT_INVALID_SLEB128("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x01", 9u);
+  EXPECT_INVALID_SLEB128("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x7E", 10u);
+  EXPECT_INVALID_SLEB128("\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x00", 10u);
+
+#undef EXPECT_INVALID_SLEB128
+}
+
 TEST(LEB128Test, SLEB128Size) {
   // Positive Value Testing Plan:
   // (1) 128 ^ n - 1 ........ need (n+1) bytes
   // (2) 128 ^ n ............ need (n+1) bytes
   // (3) 128 ^ n * 63 ....... need (n+1) bytes
   // (4) 128 ^ n * 64 - 1 ... need (n+1) bytes
   // (5) 128 ^ n * 64 ....... need (n+2) bytes