Unwind: Add a stack scanning mechanism to support win32 unwinding

Summary:
Windows unwinding is weird. The unwind rules do not (always) describe
the precise layout of the stack, but rather expect the debugger to scan
the stack for something which looks like a plausible return address, and
the unwind based on that. The reason this works somewhat reliably is
because the the unwinder also has access to the frame sizes of the
functions on the stack. This allows it (in most cases) to skip function
pointers in local variables or function arguments, which could otherwise
be mistaken for return addresses.

Implementing this kind of unwind mechanism in lldb was a bit challenging
because we expect to be able to statically describe (in the UnwindPlan)
structure, the layout of the stack for any given instruction. Giving a
precise desription of this is not possible, because it requires
correlating information from two functions -- the pushed arguments to a
function are considered a part of the callers stack frame, and their
size needs to be considered when unwinding the caller, but they are only
present in the unwind entry of the callee. The callee may end up being
in a completely different module, or it may not even be possible to
determine it statically (indirect calls).

This patch implements this functionality by introducing a couple of new
APIs:
SymbolFile::GetParameterStackSize - return the amount of stack space
  taken up by parameters of this function.
SymbolFile::GetOwnFrameSize - the size of this function's frame. This
  excludes the parameters, but includes stuff like local variables and
  spilled registers.

These functions are then used by the unwinder to compute the estimated
location of the return address. This address is not always exact,
because the stack may contain some additional values -- for instance, if
we're getting ready to call a function then the stack will also contain
partially set up arguments, but we will not know their size because we
haven't called the function yet. For this reason the unwinder will crawl
up the stack from the return address position, and look for something
that looks like a possible return address. Currently, we assume that
something is a valid return address if it ends up pointing to an
executable section.

All of this logic kicks in when the UnwindPlan sets the value of CFA as
"isHeuristicallyDetected", which is also the final new API here. Right
now, only SymbolFileBreakpad implements these APIs, but in the future
SymbolFilePDB will use them too.

Differential Revision: https://reviews.llvm.org/D66638

llvm-svn: 373072

4 files changed, 85 insertions, 5 deletions

diff --git a/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.cpp b/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.cpp
index 0da687ad0b9..50795c09f28 100644
--- a/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.cpp
+++ b/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.cpp
@@ -18,6 +18,7 @@
 #include "lldb/Symbol/ObjectFile.h"
 #include "lldb/Symbol/Symbol.h"
 #include "lldb/Symbol/SymbolContext.h"
+#include "lldb/Symbol/SymbolFile.h"
 #include "lldb/Target/ABI.h"
 #include "lldb/Target/DynamicLoader.h"
 #include "lldb/Target/ExecutionContext.h"
@@ -1852,12 +1853,66 @@ bool RegisterContextLLDB::ReadFrameAddress(
                  error.AsCString());
     break;
   }
+  case UnwindPlan::Row::FAValue::isRaSearch: {
+    Process &process = *m_thread.GetProcess();
+    lldb::addr_t return_address_hint = GetReturnAddressHint(fa.GetOffset());
+    if (return_address_hint == LLDB_INVALID_ADDRESS)
+      return false;
+    const unsigned max_iterations = 256;
+    for (unsigned i = 0; i < max_iterations; ++i) {
+      Status st;
+      lldb::addr_t candidate_addr =
+          return_address_hint + i * process.GetAddressByteSize();
+      lldb::addr_t candidate =
+          process.ReadPointerFromMemory(candidate_addr, st);
+      if (st.Fail()) {
+        UnwindLogMsg("Cannot read memory at 0x%" PRIx64 ": %s", candidate_addr,
+                     st.AsCString());
+        return false;
+      }
+      Address addr;
+      uint32_t permissions;
+      if (process.GetLoadAddressPermissions(candidate, permissions) &&
+          permissions & lldb::ePermissionsExecutable) {
+        address = candidate_addr;
+        UnwindLogMsg("Heuristically found CFA: 0x%" PRIx64, address);
+        return true;
+      }
+    }
+    UnwindLogMsg("No suitable CFA found");
+    break;
+  }
   default:
     return false;
   }
   return false;
 }
 
+lldb::addr_t RegisterContextLLDB::GetReturnAddressHint(int32_t plan_offset) {
+  addr_t hint;
+  if (!ReadGPRValue(eRegisterKindGeneric, LLDB_REGNUM_GENERIC_SP, hint))
+    return LLDB_INVALID_ADDRESS;
+  if (!m_sym_ctx.module_sp || !m_sym_ctx.symbol)
+    return LLDB_INVALID_ADDRESS;
+
+  hint += plan_offset;
+
+  if (auto next = GetNextFrame()) {
+    if (!next->m_sym_ctx.module_sp || !next->m_sym_ctx.symbol)
+      return LLDB_INVALID_ADDRESS;
+    if (auto expected_size =
+            next->m_sym_ctx.module_sp->GetSymbolFile()->GetParameterStackSize(
+                *next->m_sym_ctx.symbol))
+      hint += *expected_size;
+    else {
+      UnwindLogMsgVerbose("Could not retrieve parameter size: %s",
+                          llvm::toString(expected_size.takeError()).c_str());
+      return LLDB_INVALID_ADDRESS;
+    }
+  }
+  return hint;
+}
+
 // Retrieve a general purpose register value for THIS frame, as saved by the
 // NEXT frame, i.e. the frame that
 // this frame called.  e.g.
diff --git a/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.h b/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.h
index 1ca663906ed..114ac35591e 100644
--- a/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.h
+++ b/lldb/source/Plugins/Process/Utility/RegisterContextLLDB.h
@@ -201,6 +201,8 @@ private:
   bool IsUnwindPlanValidForCurrentPC(lldb::UnwindPlanSP unwind_plan_sp,
                                      int &valid_pc_offset);
 
+  lldb::addr_t GetReturnAddressHint(int32_t plan_offset);
+
   lldb_private::Thread &m_thread;
 
   ///
diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
index d946ae84a0e..b15091cf418 100644
--- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
+++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
@@ -374,6 +374,20 @@ void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
   symtab.CalculateSymbolSizes();
 }
 
+llvm::Expected<lldb::addr_t>
+SymbolFileBreakpad::GetParameterStackSize(Symbol &symbol) {
+  ParseUnwindData();
+  if (auto *entry = m_unwind_data->win.FindEntryThatContains(
+          symbol.GetAddress().GetFileAddress())) {
+    auto record = StackWinRecord::parse(
+        *LineIterator(*m_objfile_sp, Record::StackWin, entry->data));
+    assert(record.hasValue());
+    return record->ParameterSize;
+  }
+  return llvm::createStringError(llvm::inconvertibleErrorCode(),
+                                 "Parameter size unknown.");
+}
+
 static llvm::Optional<std::pair<llvm::StringRef, llvm::StringRef>>
 GetRule(llvm::StringRef &unwind_rules) {
   // Unwind rules are of the form
@@ -585,12 +599,19 @@ SymbolFileBreakpad::ParseWinUnwindPlan(const Bookmark &bookmark,
 
   // We assume the first value will be the CFA. It is usually called T0, but
   // clang will use T1, if it needs to realign the stack.
-  if (!postfix::ResolveSymbols(it->second, symbol_resolver)) {
-    LLDB_LOG(log, "Resolving symbols in `{0}` failed.", record->ProgramString);
-    return nullptr;
+  auto *symbol = llvm::dyn_cast<postfix::SymbolNode>(it->second);
+  if (symbol && symbol->GetName() == ".raSearch") {
+    row_sp->GetCFAValue().SetRaSearch(record->LocalSize +
+                                      record->SavedRegisterSize);
+  } else {
+    if (!postfix::ResolveSymbols(it->second, symbol_resolver)) {
+      LLDB_LOG(log, "Resolving symbols in `{0}` failed.",
+               record->ProgramString);
+      return nullptr;
+    }
+    llvm::ArrayRef<uint8_t> saved  = SaveAsDWARF(*it->second);
+    row_sp->GetCFAValue().SetIsDWARFExpression(saved.data(), saved.size());
   }
-  llvm::ArrayRef<uint8_t> saved = SaveAsDWARF(*it->second);
-  row_sp->GetCFAValue().SetIsDWARFExpression(saved.data(), saved.size());
 
   // Replace the node value with InitialValueNode, so that subsequent
   // expressions refer to the CFA value instead of recomputing the whole
diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
index dc309094c17..d7fe897a107 100644
--- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
+++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
@@ -135,6 +135,8 @@ public:
 
   void AddSymbols(Symtab &symtab) override;
 
+  llvm::Expected<lldb::addr_t> GetParameterStackSize(Symbol &symbol) override;
+
   lldb::UnwindPlanSP
   GetUnwindPlan(const Address &address,
                 const RegisterInfoResolver &resolver) override;