Fix UB in EmulateInstructionARM64.cpp

[aprantl]

Summary

This fixes an unhandled signed integer overflow in AddWithCarry() by using the llvm::checkedAdd() function. Thats to @vsk for the suggestion!

[vsk]

Any chance we can export AddWithCarry via EmulateInstructionARM64.h, then add a unit test in TestArm64InstEmulation.cpp?

[vsk]

I should add: otherwise, this looks good!

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

92

The docs [1] say 'integer signed_sum = SInt(x) + SInt(y) + UInt(carry_in)', but I bet checkedAdd doesn't support that, and anyway carry_in is 1-bit so it doesn't matter.

[1] https://developer.arm.com/docs/ddi0596/e/shared-pseudocode-functions/shared-functionsinteger-pseudocode#impl-shared.AddWithCarry.3

[jasonmolenda]

Nice cleanup of a long standing undefined behavior warning.

[shafik]

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

25

Why? also should be cstdlib in C++.

[davide]

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

25

It's just something shuffled around, probably a side effect of clang-format.

[davide]

This is great Adrian. I feel like there are several other instances of additions that should use llvm::checkAdd here instead of +. Is this the only UB triggered in the testsuite?

[aprantl]

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

92

Am I misreading this or are we also setting the C(arry) flag inverted according to the documentation?

[aprantl]

This is great Adrian. I feel like there are several other instances of additions that should use llvm::checkAdd here instead of +. Is this the only UB triggered in the testsuite?

It's the only UB caught by the green dragon / ci.swift.org bots.

[vsk]

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

92

Oh wow.. nice catch.

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.h

uint32_t N : 1, V : 1, C : 1,
         M : 5,  // AArch32 only – mode encodings
         RW : 1, // Current register width – 0 is AArch64, 1 is AArch32
         EL : 2, // Current exception level (see ExceptionLevel enum)
         SP : 1; // AArch64 only - Stack Pointer selection (see
                 // StackPointerSelection enum)
   } ProcState;
 
 protected:
+  static uint64_t AddWithCarry(uint32_t N, uint64_t x, uint64_t y, bool carry_in,
+                               EmulateInstructionARM64::ProcState &proc_state);
+
   typedef struct {
     uint32_t mask;
     uint32_t value;
     uint32_t vfp_variants;
     bool (EmulateInstructionARM64::*callback)(const uint32_t opcode);
     const char *name;
   } Opcode;
 

lldb/source/Plugins/Instruction/ARM64/EmulateInstructionARM64.cpp

 //===-- EmulateInstructionARM64.cpp ---------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "EmulateInstructionARM64.h"
 
-#include <stdlib.h>
-
 #include "lldb/Core/Address.h"
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Symbol/UnwindPlan.h"
 #include "lldb/Utility/ArchSpec.h"
 #include "lldb/Utility/ConstString.h"
 #include "lldb/Utility/RegisterValue.h"
 #include "lldb/Utility/Stream.h"
 
+#include "llvm/Support/CheckedArithmetic.h"
+
 #include "Plugins/Process/Utility/ARMDefines.h"
 #include "Plugins/Process/Utility/ARMUtils.h"
 #include "Plugins/Process/Utility/lldb-arm64-register-enums.h"
 
+#include <cstdlib>
+
 #define GPR_OFFSET(idx) ((idx)*8)
 #define GPR_OFFSET_NAME(reg) 0
 #define FPU_OFFSET(idx) ((idx)*16)
 #define FPU_OFFSET_NAME(reg) 0
 #define EXC_OFFSET_NAME(reg) 0
 #define DBG_OFFSET_NAME(reg) 0
 #define DBG_OFFSET_NAME(reg) 0
 #define DEFINE_DBG(re, y)                                                      \

 // =====
 
 static inline uint64_t LSL(uint64_t x, integer shift) {
   if (shift == 0)
     return x;
   return x << shift;
 }
 
-// AddWithCarry()
-// ===============
-static inline uint64_t
-AddWithCarry(uint32_t N, uint64_t x, uint64_t y, bit carry_in,
-             EmulateInstructionARM64::ProcState &proc_state) {
-  uint64_t unsigned_sum = UInt(x) + UInt(y) + UInt(carry_in);
-  int64_t signed_sum = SInt(x) + SInt(y) + UInt(carry_in);
-  uint64_t result = unsigned_sum;
-  if (N < 64)
-    result = Bits64(result, N - 1, 0);
-  proc_state.N = Bit64(result, N - 1);
-  proc_state.Z = IsZero(result);
-  proc_state.C = UInt(result) == unsigned_sum;
-  proc_state.V = SInt(result) == signed_sum;
-  return result;
-}
-
 // ConstrainUnpredictable()
 // ========================
 
 EmulateInstructionARM64::ConstraintType
 ConstrainUnpredictable(EmulateInstructionARM64::Unpredictable which) {
   EmulateInstructionARM64::ConstraintType result =
       EmulateInstructionARM64::Constraint_UNKNOWN;
   switch (which) {
   case EmulateInstructionARM64::Unpredictable_WBOVERLAP:
   case EmulateInstructionARM64::Unpredictable_LDPOVERLAP:
     // TODO: don't know what to really do here? Pseudo code says:
case 7:
     return true;
   }
 
   if (cond & 1)
     result = !result;
   return result;
 }
 
+uint64_t EmulateInstructionARM64::
+AddWithCarry(uint32_t N, uint64_t x, uint64_t y, bit carry_in,
+             EmulateInstructionARM64::ProcState &proc_state) {
+  uint64_t unsigned_sum = UInt(x) + UInt(y) + UInt(carry_in);
+  llvm::Optional<int64_t> signed_sum = llvm::checkedAdd(SInt(x), SInt(y));
+  bool overflow = !signed_sum;
+  if (!overflow)
+    overflow |= !llvm::checkedAdd(*signed_sum, SInt(carry_in));
+  uint64_t result = unsigned_sum;
+  if (N < 64)
+    result = Bits64(result, N - 1, 0);
+  proc_state.N = Bit64(result, N - 1);
+  proc_state.Z = IsZero(result);
+  proc_state.C = UInt(result) != unsigned_sum;
+  proc_state.V = overflow;
+  return result;
+}
+
 bool EmulateInstructionARM64::EmulateADDSUBImm(const uint32_t opcode) {
   // integer d = UInt(Rd);
   // integer n = UInt(Rn);
   // integer datasize = if sf == 1 then 64 else 32;
   // boolean sub_op = (op == 1);
   // boolean setflags = (S == 1);
   // bits(datasize) imm;
   //

lldb/unittests/CMakeLists.txt

 add_subdirectory(Breakpoint)
 add_subdirectory(Core)
 add_subdirectory(DataFormatter)
 add_subdirectory(Disassembler)
 add_subdirectory(Editline)
 add_subdirectory(Expression)
 add_subdirectory(Host)
 add_subdirectory(Interpreter)
+add_subdirectory(Instruction)
 add_subdirectory(Language)
 add_subdirectory(ObjectFile)
 add_subdirectory(Platform)
 add_subdirectory(Process)
 add_subdirectory(ScriptInterpreter)
 add_subdirectory(Signals)
 add_subdirectory(Symbol)
 add_subdirectory(SymbolFile)
 add_subdirectory(Target)
 add_subdirectory(tools)
 add_subdirectory(UnwindAssembly)
 add_subdirectory(Utility)
 
 if(LLDB_CAN_USE_DEBUGSERVER AND LLDB_TOOL_DEBUGSERVER_BUILD AND NOT LLDB_USE_SYSTEM_DEBUGSERVER)
   add_subdirectory(debugserver)
 endif()

lldb/unittests/Instruction/CMakeLists.txt

+if("ARM" IN_LIST LLVM_TARGETS_TO_BUILD)
+  add_lldb_unittest(EmulatorTests
+    TestAArch64Emulator.cpp
+    LINK_LIBS
+      lldbCore
+      lldbSymbol
+      lldbTarget
+      lldbPluginInstructionARM64
+    LINK_COMPONENTS
+      Support
+      ${LLVM_TARGETS_TO_BUILD})
+endif()

lldb/unittests/Instruction/TestAArch64Emulator.cpp

+//===-- TestAArch64Emulator.cpp ------------------------------------------===//
+
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+
+#include "lldb/Core/Address.h"
+#include "lldb/Core/Disassembler.h"
+#include "lldb/Target/ExecutionContext.h"
+#include "lldb/Utility/ArchSpec.h"
+
+#include "Plugins/Instruction/ARM64/EmulateInstructionARM64.h"
+
+using namespace lldb;
+using namespace lldb_private;
+
+struct Arch64EmulatorTester : public EmulateInstructionARM64 {
+  Arch64EmulatorTester()
+      : EmulateInstructionARM64(ArchSpec("arm64-apple-ios")) {}
+
+  static uint64_t AddWithCarry(uint32_t N, uint64_t x, uint64_t y, bool carry_in,
+                               EmulateInstructionARM64::ProcState &proc_state) {
+    return EmulateInstructionARM64::AddWithCarry(N, x, y, carry_in, proc_state);
+  }
+};
+
+class TestAArch64Emulator : public testing::Test {
+public:
+  static void SetUpTestCase();
+  static void TearDownTestCase();
+
+protected:
+};
+
+void TestAArch64Emulator::SetUpTestCase() {
+  EmulateInstructionARM64::Initialize();
+}
+
+void TestAArch64Emulator::TearDownTestCase() {
+  EmulateInstructionARM64::Terminate();
+}
+
+TEST_F(TestAArch64Emulator, TestOverflow) {
+  EmulateInstructionARM64::ProcState pstate;
+  memset(&pstate, 0, sizeof(pstate));
+  uint64_t ll_max = std::numeric_limits<int64_t>::max();
+  Arch64EmulatorTester emu;
+  ASSERT_EQ(emu.AddWithCarry(64, ll_max, 0, 0, pstate), ll_max);
+  ASSERT_EQ(pstate.V, 0ULL);
+  ASSERT_EQ(pstate.C, 0ULL);
+  ASSERT_EQ(emu.AddWithCarry(64, ll_max, 1, 0, pstate), (uint64_t)(ll_max + 1));
+  ASSERT_EQ(pstate.V, 1ULL);
+  ASSERT_EQ(pstate.C, 0ULL);
+  ASSERT_EQ(emu.AddWithCarry(64, ll_max, 0, 1, pstate), (uint64_t)(ll_max + 1));
+  ASSERT_EQ(pstate.V, 1ULL);
+  ASSERT_EQ(pstate.C, 0ULL);
+}