Detect x86 mid-function epilogues that end in a jump

[jasonmolenda]

Summary

This patch adds a few new instruction recognizers to the x86 assembly inspection engine to recognize relative branches & jumps, adds support for recognizing a mid-function epilogue that ends in a jump instruction, and tests this.

The x86 unwinder still uses the initial algorithm for detecting mid-function epilogues: recognizing the end of an epilogue (relatively easy on x86 when it's usually a RET), we re-instate the unwind state from the end of the prologue. This patch adds recognition of a jump outside the function as a final epilogue instruction.

The second attempt at recognizing mid-function epilogues is implemented in UnwindAssemblyInstEmulation and is a much better approach -- it recognizes branch instructions and forwards the unwind state to the target instruction. This means that a branch over a mid-function epilogue will forward the unwind state past the epilogue; no detection of prologues or epilogues is needed.

I've added more instruction recognition machinery than is technically necessary for the bug I needed to fix - but it'll be needed for the better algorithm to be implemented in the x86 inspection engine. I didn't want to take on that larger bit of work right now, but it's something that should be done - this current algorithm is always going to be more fragile.

A more ambitious way to fix this would be to add an InstEmulation plugin for x86 and update UnwindAssemblyInstEmulation to handle all of the x86 features needed for unwinding, retire the x86AssemblyInspectionEngine.

[fixathon]

flagging suspicious duplicate code

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.cpp

707–713

This looks like duplicate code

[jasonmolenda]

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.cpp

707–713

At least it does the same thing in both of them! :)

[fixathon]

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.cpp

707–713

It does indeed, but the comments above the code are different for the 2 identical blocks of code. Do you want to fix it then? :)

[jasonmolenda]

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.cpp

707–713

:) I see there's a comment intended for this first entry a dozen lines earlier in the source file, it's probably gotten confusing over time & edits. yah I'll fix it, thanks for catching it.

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.h

private:
   bool push_reg_p(int &regno);
   bool pop_reg_p(int &regno);
   bool pop_rbp_pattern_p();
   bool pop_misc_reg_p();
   bool leave_pattern_p();
   bool call_next_insn_pattern_p();
   bool mov_reg_to_local_stack_frame_p(int &regno, int &rbp_offset);
   bool ret_pattern_p();
+  bool jmp_to_reg_p();
+  bool pc_rel_branch_or_jump_p (const int instruction_length, int &offset);
+  bool non_local_branch_p (const lldb::addr_t current_func_text_offset, 
+                           const lldb_private::AddressRange &func_range,
+                           const int instruction_length);
+  bool local_branch_p (const lldb::addr_t current_func_text_offset, 
+                       const lldb_private::AddressRange &func_range,
+                       const int instruction_length,
+                       lldb::addr_t &target_insn_offset);
+  uint16_t extract_2(uint8_t *b);
+  int16_t extract_2_signed(uint8_t *b);
   uint32_t extract_4(uint8_t *b);
+  int32_t extract_4_signed(uint8_t *b);
 
   bool instruction_length(uint8_t *insn, int &length, uint32_t buffer_remaining_bytes);
 
   bool machine_regno_to_lldb_regno(int machine_regno, uint32_t &lldb_regno);
 
   enum CPU { k_i386, k_x86_64, k_cpu_unspecified };
 
   enum i386_register_numbers {

lldb/trunk/source/Plugins/UnwindAssembly/x86/x86AssemblyInspectionEngine.cpp

if (*p == 0x89) {
 
     regno = ((*(p + 1) >> 3) & 0x7) | src_reg_prefix_bit;
     rbp_offset = offset > 0 ? offset : -offset;
     return true;
   }
   return false;
 }
 
+// Returns true if this is a jmp instruction where we can't
+// know the destination address statically. 
+//
+// ff e0                                   jmpq   *%rax
+// ff e1                                   jmpq   *%rcx
+// ff 60 28                                jmpq   *0x28(%rax)
+// ff 60 60                                jmpq   *0x60(%rax)
+bool x86AssemblyInspectionEngine::jmp_to_reg_p() {
+  if (*m_cur_insn != 0xff)
+    return false;
+
+  // The second byte is a ModR/M /4 byte, strip off the registers
+  uint8_t second_byte_sans_reg = *(m_cur_insn + 1) & ~7;
+
+  // Don't handle 0x24 disp32, because the target address is
+  // knowable statically - pc_rel_branch_or_jump_p() will
+  // return the target address.
+
+  // [reg]
+  if (second_byte_sans_reg == 0x20)
+    return true;
+
+  // [reg]+disp8
+  if (second_byte_sans_reg == 0x60)
+    return true;
+
+  // [reg]+disp32
+  if (second_byte_sans_reg == 0xa0)
+    return true;
+
+  // reg
+  if (second_byte_sans_reg == 0xe0)
+    return true;
+
+  // disp32
+  // jumps to an address stored in memory, the value can't be cached
+  // in an unwind plan.
+  if (second_byte_sans_reg == 0x24)
+    return true;
+
+  // use SIB byte
+  // ff 24 fe  jmpq   *(%rsi,%rdi,8)
+  if (second_byte_sans_reg == 0x24)
+    return true;
+
+  return false;
+}
+
+// Detect branches to fixed pc-relative offsets.
+// Returns the offset from the address of the next instruction
+// that may be branch/jumped to.
+//
+// Cannot determine the offset of a JMP that jumps to the address in
+// a register ("jmpq *%rax") or offset from a register value 
+// ("jmpq *0x28(%rax)"), this method will return false on those
+// instructions.
+//
+// These instructions all end in either a relative 8/16/32 bit value
+// depending on the instruction and the current execution mode of the
+// inferior process.  Once we know the size of the opcode instruction, 
+// we can use the total instruction length to determine the size of
+// the relative offset without having to compute it correctly.
+
+bool x86AssemblyInspectionEngine::pc_rel_branch_or_jump_p (
+    const int instruction_length, int &offset)
+{
+  int opcode_size = 0;
+
+  uint8_t b1 = m_cur_insn[0];
+  uint8_t b2 = m_cur_insn[1];
+
+  switch (b1) {
+    case 0x77: // JA/JNBE rel8
+    case 0x73: // JAE/JNB/JNC rel8
+    case 0x72: // JB/JC/JNAE rel8
+    case 0x76: // JBE/JNA rel8
+    case 0xe3: // JCXZ/JECXZ/JRCXZ rel8
+    case 0x74: // JE/JZ rel8
+    case 0x7f: // JG/JNLE rel8
+    case 0x7d: // JGE/JNL rel8
+    case 0x7c: // JL/JNGE rel8
+    case 0x7e: // JNG/JLE rel8
+    case 0x71: // JNO rel8
+    case 0x7b: // JNP/JPO rel8
+    case 0x79: // JNS rel8
+    case 0x75: // JNE/JNZ rel8
+    case 0x70: // JO rel8
+    case 0x7a: // JP/JPE rel8
+    case 0x78: // JS rel8
+    case 0xeb: // JMP rel8
+    case 0xe9: // JMP rel16/rel32
+      opcode_size = 1;
+      break;
+    default:
+      break;
+  }
+  if (b1 == 0x0f && opcode_size == 0) {
+    switch (b2) {
+      case 0x87: // JA/JNBE rel16/rel32
+      case 0x86: // JBE/JNA rel16/rel32
+      case 0x84: // JE/JZ rel16/rel32
+      case 0x8f: // JG/JNLE rel16/rel32
+      case 0x8d: // JNL/JGE rel16/rel32
+      case 0x8e: // JLE rel16/rel32
+      case 0x82: // JB/JC/JNAE rel16/rel32
+      case 0x83: // JAE/JNB/JNC rel16/rel32
+      case 0x85: // JNE/JNZ rel16/rel32
+      case 0x8c: // JL/JNGE rel16/rel32
+      case 0x81: // JNO rel16/rel32
+      case 0x8b: // JNP/JPO rel16/rel32
+      case 0x89: // JNS rel16/rel32
+      case 0x80: // JO rel16/rel32
+      case 0x8a: // JP rel16/rel32
+      case 0x88: // JS rel16/rel32
+        opcode_size = 2;
+        break;
+      default:
+        break;
+    }
+  }
+
+  if (opcode_size == 0)
+    return false;
+
+  offset = 0;
+  if (instruction_length - opcode_size == 1) {
+    int8_t rel8 = (int8_t) *(m_cur_insn + opcode_size);
+    offset = rel8;
+  } else if (instruction_length - opcode_size == 2) {
+    int16_t rel16 = extract_2_signed (m_cur_insn + opcode_size);
+    offset = rel16;
+  } else if (instruction_length - opcode_size == 4) {
+    int32_t rel32 = extract_4_signed (m_cur_insn + opcode_size);
+    offset = rel32;
+  } else {
+    return false;
+  }
+  return true;
+}
+
+// Returns true if this instruction is a intra-function branch or jump -
+// a branch/jump within the bounds of this same function.
+// Cannot predict where a jump through a register value ("jmpq *%rax")
+// will go, so it will return false on that instruction.
+bool x86AssemblyInspectionEngine::local_branch_p (
+    const addr_t current_func_text_offset,
+    const AddressRange &func_range,
+    const int instruction_length,
+    addr_t &target_insn_offset) {
+  int offset;
+  if (pc_rel_branch_or_jump_p (instruction_length, offset) && offset != 0) {
+    addr_t next_pc_value = current_func_text_offset + instruction_length;
+    if (offset < 0 && -offset > current_func_text_offset) {
+      // Branch target is before the start of this function
+      return false;
+    }
+    if (offset + next_pc_value > func_range.GetByteSize()) {
+      // Branch targets outside this function's bounds
+      return false;
+    }
+    // This instruction branches to target_insn_offset (byte offset into the function)
+    target_insn_offset = next_pc_value + offset;
+    return true;
+  }
+  return false;
+}
+
+// Returns true if this instruction is a inter-function branch or jump - a
+// branch/jump to another function.
+// Cannot predict where a jump through a register value ("jmpq *%rax")
+// will go, so it will return false on that instruction.
+bool x86AssemblyInspectionEngine::non_local_branch_p (
+    const addr_t current_func_text_offset,
+    const AddressRange &func_range,
+    const int instruction_length) {
+  int offset;
+  addr_t target_insn_offset;
+  if (pc_rel_branch_or_jump_p (instruction_length, offset)) {
+    return !local_branch_p(current_func_text_offset,func_range,instruction_length,target_insn_offset);
+  }
+  return false;
+}
+
 // ret [0xc3] or [0xcb] or [0xc2 imm16] or [0xca imm16]
 bool x86AssemblyInspectionEngine::ret_pattern_p() {
   uint8_t *p = m_cur_insn;
   return *p == 0xc3 || *p == 0xc2 || *p == 0xca || *p == 0xcb;
 }
 
+uint16_t x86AssemblyInspectionEngine::extract_2(uint8_t *b) {
+  uint16_t v = 0;
+  for (int i = 1; i >= 0; i--)
+    v = (v << 8) | b[i];
+  return v;
+}
+
+int16_t x86AssemblyInspectionEngine::extract_2_signed(uint8_t *b) {
+  int16_t v = 0;
+  for (int i = 1; i >= 0; i--)
+    v = (v << 8) | b[i];
+  return v;
+}
+
 uint32_t x86AssemblyInspectionEngine::extract_4(uint8_t *b) {
   uint32_t v = 0;
   for (int i = 3; i >= 0; i--)
     v = (v << 8) | b[i];
   return v;
 }
 
+int32_t x86AssemblyInspectionEngine::extract_4_signed(uint8_t *b) {
+  int32_t v = 0;
+  for (int i = 3; i >= 0; i--)
+    v = (v << 8) | b[i];
+  return v;
+}
+
+
 bool x86AssemblyInspectionEngine::instruction_length(uint8_t *insn_p,
                                                      int &length, 
                                                      uint32_t buffer_remaining_bytes) {
 
   uint32_t max_op_byte_size = std::min(buffer_remaining_bytes, m_arch.GetMaximumOpcodeByteSize());
   llvm::SmallVector<uint8_t, 32> opcode_data;
   opcode_data.resize(max_op_byte_size);
 

 bool x86AssemblyInspectionEngine::machine_regno_to_lldb_regno(
     int machine_regno, uint32_t &lldb_regno) {
   MachineRegnumToNameAndLLDBRegnum::iterator it = m_reg_map.find(machine_regno);
   if (it != m_reg_map.end()) {
     lldb_regno = it->second.lldb_regnum;
     return true;
   }
   return false;
-  return false;
 }
 
 bool x86AssemblyInspectionEngine::GetNonCallSiteUnwindPlanFromAssembly(
     uint8_t *data, size_t size, AddressRange &func_range,
     UnwindPlan &unwind_plan) {
   unwind_plan.Clear();
 
   if (data == nullptr || size == 0)
else if (lea_rbx_rsp_pattern_p(stack_offset)) {
         afa_value.SetUnspecified();
         row_updated = true;
       }
       if (fa_value_ptr->GetRegisterNumber() == m_lldb_alt_fp_regnum) {
         current_sp_bytes_offset_from_fa = fa_value_ptr->GetOffset() - stack_offset;
       }
     }
 
-    else if (ret_pattern_p() && prologue_completed_row.get()) {
+    else if (prologue_completed_row.get() && 
+             (ret_pattern_p() ||
+              non_local_branch_p (current_func_text_offset, func_range, insn_len) ||
+              jmp_to_reg_p())) {
+      // Check if the current instruction is the end of an epilogue sequence,
+      // and if so, re-instate the prologue-completed unwind state.
+
+      // The current instruction is a branch/jump outside this function, 
+      // a ret, or a jump through a register value which we cannot 
+      // determine the effcts of.  Verify that the stack frame state 
+      // has been unwound to the same as it was at function entry to avoid 
+      // mis-identifying a JMP instruction as an epilogue.
+      UnwindPlan::Row::RegisterLocation sp, pc;
+      if (row->GetRegisterInfo(m_lldb_sp_regnum, sp) &&
+          row->GetRegisterInfo(m_lldb_ip_regnum, pc)) {
+        // Any ret instruction variant is definitely indicative of an
+        // epilogue; for other insn patterns verify that we're back to
+        // the original unwind state.
+        if (ret_pattern_p() ||
+            (sp.IsCFAPlusOffset() && sp.GetOffset() == 0 &&
+            pc.IsAtCFAPlusOffset() && pc.GetOffset() == -m_wordsize)) {
           // Reinstate the saved prologue setup for any instructions that come
-      // after the ret instruction
+          // after the epilogue
 
           UnwindPlan::Row *newrow = new UnwindPlan::Row;
           *newrow = *prologue_completed_row.get();
           row.reset(newrow);
           current_sp_bytes_offset_from_fa =
               prologue_completed_sp_bytes_offset_from_cfa;
           is_aligned = prologue_completed_is_aligned;
 
           saved_registers.clear();
           saved_registers.resize(prologue_completed_saved_registers.size(), false);
           for (size_t i = 0; i < prologue_completed_saved_registers.size(); ++i) {
             saved_registers[i] = prologue_completed_saved_registers[i];
           }
 
           in_epilogue = true;
           row_updated = true;
         }
+      }
+    }
 
     // call next instruction
     //     call 0
     //  => pop  %ebx
     // This is used in i386 programs to get the PIC base address for finding
     // global data
     else if (call_next_insn_pattern_p()) {
       current_sp_bytes_offset_from_fa += m_wordsize;

lldb/trunk/unittests/UnwindAssembly/x86/Testx86AssemblyInspectionEngine.cpp

TEST_F(Testx86AssemblyInspectionEngine, TestReturnDetect) {
   EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_rbp);
   EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
   EXPECT_EQ(16, row_sp->GetCFAValue().GetOffset());
 
   EXPECT_TRUE(row_sp->GetRegisterInfo(k_rip, regloc));
   EXPECT_TRUE(regloc.IsAtCFAPlusOffset());
   EXPECT_EQ(-8, regloc.GetOffset());
 }
+
+
+// Test mid-function epilogues - the unwind state post-prologue
+// should be re-instated.
+
+TEST_F(Testx86AssemblyInspectionEngine, TestDisassemblyMidFunctionEpilogues) {
+  AddressRange sample_range;
+  UnwindPlan unwind_plan(eRegisterKindLLDB);
+  std::unique_ptr<x86AssemblyInspectionEngine> engine32 = Geti386Inspector();
+  std::unique_ptr<x86AssemblyInspectionEngine> engine64 = Getx86_64Inspector();
+
+  uint8_t data[] = {
+    0x55,                   // <+0>: pushq %rbp
+    0x48, 0x89, 0xe5,       // <+1>: movq %rsp, %rbp
+    0x48, 0x83, 0xec, 0x70, // <+4>: subq $0x70, %rsp
+    0x90,                   // <+8>: nop               // prologue set up
+
+    0x74, 0x7,              // <+9>: je 7 <+18>
+    0x48, 0x83, 0xc4, 0x70, // <+11>: addq $0x70, %rsp
+    0x5d,                   // <+15>: popq %rbp
+    0xff, 0xe0,             // <+16>: jmpq *%rax      // epilogue completed
+
+    0x90,                   // <+18>: nop             // prologue setup back
+
+    0x74, 0x7,              // <+19>: je 6 <+27>
+    0x48, 0x83, 0xc4, 0x70, // <+21>: addq $0x70, %rsp
+    0x5d,                   // <+25>: popq %rbp
+    0xc3,                   // <+26>: retq            // epilogue completed
+
+    0x90,                   // <+27>: nop             // prologue setup back
+
+    0x48, 0x83, 0xc4, 0x70, // <+28>: addq $0x70, %rsp
+    0x5d,                   // <+32>: popq %rbp
+    0xc3,                   // <+33>: retq            // epilogue completed
+
+  };
+
+  sample_range = AddressRange(0x1000, sizeof(data));
+
+  int wordsize = 4;
+  EXPECT_TRUE(engine32->GetNonCallSiteUnwindPlanFromAssembly(
+      data, sizeof(data), sample_range, unwind_plan));
+
+  // Check that we've unwound the stack after the first mid-function epilogue
+  // row:   CFA=esp +4 => esp=CFA+0 eip=[CFA-4]
+  UnwindPlan::RowSP row_sp = unwind_plan.GetRowForFunctionOffset(16);
+  EXPECT_EQ(16ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_esp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize, row_sp->GetCFAValue().GetOffset());
+
+  // Check that we've reinstated the stack frame setup 
+  // unwind instructions after a jmpq *%eax
+  // row:   CFA=ebp +8 => esp=CFA+0 eip=[CFA-8]
+  row_sp = unwind_plan.GetRowForFunctionOffset(18);
+  EXPECT_EQ(18ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_ebp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize * 2, row_sp->GetCFAValue().GetOffset());
+
+  // Check that we've reinstated the stack frame setup 
+  // unwind instructions after a mid-function retq
+  // row:   CFA=ebp +8 => esp=CFA+0 eip=[CFA-8]
+  row_sp = unwind_plan.GetRowForFunctionOffset(27);
+  EXPECT_EQ(27ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_ebp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize * 2, row_sp->GetCFAValue().GetOffset());
+
+  // After last instruction in the function, verify that
+  // the stack frame has been unwound
+  // row:   CFA=esp +4 => esp=CFA+0 eip=[CFA-4]
+  row_sp = unwind_plan.GetRowForFunctionOffset(33);
+  EXPECT_EQ(33ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_esp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize, row_sp->GetCFAValue().GetOffset());
+
+
+  unwind_plan.Clear();
+
+  wordsize = 8;
+  EXPECT_TRUE(engine64->GetNonCallSiteUnwindPlanFromAssembly(
+      data, sizeof(data), sample_range, unwind_plan));
+
+  // Check that we've unwound the stack after the first mid-function epilogue
+  // row:   CFA=rsp +8 => rsp=CFA+0 rip=[CFA-8]
+  row_sp = unwind_plan.GetRowForFunctionOffset(16);
+  EXPECT_EQ(16ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_rsp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize, row_sp->GetCFAValue().GetOffset());
+
+  // Check that we've reinstated the stack frame setup 
+  // unwind instructions after a jmpq *%eax
+  // row:   CFA=rbp+16 => rsp=CFA+0 rip=[CFA-16]
+  row_sp = unwind_plan.GetRowForFunctionOffset(18);
+  EXPECT_EQ(18ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_rbp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize * 2, row_sp->GetCFAValue().GetOffset());
+
+  // Check that we've reinstated the stack frame setup 
+  // unwind instructions after a mid-function retq
+  // row:   CFA=rbp+16 => rsp=CFA+0 rip=[CFA-16]
+  row_sp = unwind_plan.GetRowForFunctionOffset(27);
+  EXPECT_EQ(27ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_rbp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize * 2, row_sp->GetCFAValue().GetOffset());
+
+  // After last instruction in the function, verify that
+  // the stack frame has been unwound
+  // row:   CFA=rsp +8 => esp=CFA+0 rip=[CFA-8]
+  row_sp = unwind_plan.GetRowForFunctionOffset(33);
+  EXPECT_EQ(33ull, row_sp->GetOffset());
+  EXPECT_TRUE(row_sp->GetCFAValue().GetRegisterNumber() == k_rsp);
+  EXPECT_TRUE(row_sp->GetCFAValue().IsRegisterPlusOffset() == true);
+  EXPECT_EQ(wordsize, row_sp->GetCFAValue().GetOffset());
+
+
+}