Improve UnwindLLDB with better detection for unwinding failures

[tberghammer]

Summary

Improve UnwindLLDB with better detection for unwinding failures

Previously we accepted a frame as correct result if the PC pointed into an executable section of code. The isse with that approac is that if we calculated PC correctly but messed up the value of CFA then unwinding from the next fram will most likely fail.

With this change I modify the logic with keeping the requirement for PC to point to an executable section and also check that we can continue the unwind from the frame we calculated. If continuing from the frame calculated with the primary unwind plan isn't working then fall back to the fallback plan with the hope for a better frame (if the fallback plan won't help then we acceot the frame from the primary plan).

[jasonmolenda]

I'm fine with trying this approach. These heuristics for falling back to alternate unwind methods are tricky to get right; often the best approach is to live on them for a bit and pay close attention to the unwinder in complicated unwind situations.

The only question I have about the patch is the UnwindLLDB::CursorSP UnwindLLDB::GetOneMoreFrame (ABI* abi) method - you have 'return nullptr;' as a shortcut in a few places. Is that safe? Normally in a function that returns a shared pointer we'll write 'return CursorSP();' for this. I'm sure the nullptr gets converted to an empty shared pointer via a copy constructor, or something like that. I'm fine with coding it this way, just wanted to check if anyone knows it's OK.

[tberghammer]

std::shared_ptr have an implicit constructor just for this purpose to make code simpler (without a typedef it would be odd to always write "return std::shared_ptr<Cursor>();")

constexpr shared_ptr( std::nullptr_t );

source/Plugins/Process/Utility/UnwindLLDB.h

struct RegisterLocation {
             uint64_t     inferred_value;        // eRegisterValueInferred - e.g. stack pointer == cfa + offset
         } location;
     };
 
     void
     DoClear()
     {
         m_frames.clear();
+        m_candidate_frame.reset();
         m_unwind_complete = false;
     }
 
     virtual uint32_t
     DoGetFrameCount();
 
     bool
     DoGetFrameInfoAtIndex (uint32_t frame_idx,
struct Cursor
 
         Cursor () : start_pc (LLDB_INVALID_ADDRESS), cfa (LLDB_INVALID_ADDRESS), sctx(), reg_ctx_lldb_sp() { }
     private:
         DISALLOW_COPY_AND_ASSIGN (Cursor);
     };
 
     typedef std::shared_ptr<Cursor> CursorSP;
     std::vector<CursorSP> m_frames;
+    CursorSP m_candidate_frame;
     bool m_unwind_complete; // If this is true, we've enumerated all the frames in the stack, and m_frames.size() is the 
                             // number of frames, etc.  Otherwise we've only gone as far as directly asked, and m_frames.size()
                             // is how far we've currently gone.
  
     std::vector<ConstString> m_user_supplied_trap_handler_functions;
 
-    bool AddOneMoreFrame (ABI *abi);
-    bool AddFirstFrame ();
+    CursorSP
+    GetOneMoreFrame (ABI* abi);
+
+    bool
+    AddOneMoreFrame (ABI *abi);
+
+    bool
+    AddFirstFrame ();
 
     //------------------------------------------------------------------
     // For UnwindLLDB only
     //------------------------------------------------------------------
     DISALLOW_COPY_AND_ASSIGN (UnwindLLDB);
 };
 
 }   // namespace lldb_private
 
 #endif  // lldb_UnwindLLDB_h_

source/Plugins/Process/Utility/UnwindLLDB.cpp

unwind_done:
     if (log)
     {
         log->Printf ("th%d Unwind of this thread is complete.", m_thread.GetIndexID());
     }
     m_unwind_complete = true;
     return false;
 }
 
-// For adding a non-zero stack frame to m_frames.
-bool
-UnwindLLDB::AddOneMoreFrame (ABI *abi)
+UnwindLLDB::CursorSP
+UnwindLLDB::GetOneMoreFrame (ABI* abi)
 {
+    assert (m_frames.size() != 0 && "Get one more frame called with empty frame list");
+
     // If we've already gotten to the end of the stack, don't bother to try again...
     if (m_unwind_complete)
-        return false;
+        return nullptr;
         
     Log *log(GetLogIfAllCategoriesSet (LIBLLDB_LOG_UNWIND));
-    CursorSP cursor_sp(new Cursor ());
-
-    // Frame zero is a little different
-    if (m_frames.size() == 0)
-        return false;
 
-    uint32_t cur_idx = m_frames.size ();
+    CursorSP prev_frame = m_frames.back();
+    uint32_t cur_idx = m_frames.size();
+
+    CursorSP cursor_sp(new Cursor ());
     RegisterContextLLDBSP reg_ctx_sp(new RegisterContextLLDB (m_thread, 
-                                                              m_frames[cur_idx - 1]->reg_ctx_lldb_sp, 
+                                                              prev_frame->reg_ctx_lldb_sp, 
                                                               cursor_sp->sctx, 
                                                               cur_idx, 
                                                               *this));
 
-    // We want to detect an unwind that cycles erronously and stop backtracing.
+    // We want to detect an unwind that cycles erroneously and stop backtracing.
     // Don't want this maximum unwind limit to be too low -- if you have a backtrace
     // with an "infinitely recursing" bug, it will crash when the stack blows out
     // and the first 35,000 frames are uninteresting - it's the top most 5 frames that
     // you actually care about.  So you can't just cap the unwind at 10,000 or something.
     // Realistically anything over around 200,000 is going to blow out the stack space.
     // If we're still unwinding at that point, we're probably never going to finish.
     if (cur_idx > 300000)
     {
         if (log)
             log->Printf ("%*sFrame %d unwound too many frames, assuming unwind has gone astray, stopping.", 
                          cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        goto unwind_done;
+        return nullptr;
     }
 
     if (reg_ctx_sp.get() == NULL)
     {
         // If the RegisterContextLLDB has a fallback UnwindPlan, it will switch to that and return
         // true.  Subsequent calls to TryFallbackUnwindPlan() will return false.
-        if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-        {
-            return AddOneMoreFrame (abi);
-        }
+        if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+            return GetOneMoreFrame (abi);
+
         if (log)
             log->Printf ("%*sFrame %d did not get a RegisterContext, stopping.",
                          cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        goto unwind_done;
+        return nullptr;
     }
 
     if (!reg_ctx_sp->IsValid())
     {
         // We failed to get a valid RegisterContext.
         // See if the regctx below this on the stack has a fallback unwind plan it can use.
         // Subsequent calls to TryFallbackUnwindPlan() will return false.
-        if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-        {
-            return AddOneMoreFrame (abi);
-        }
+        if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+            return GetOneMoreFrame (abi);
+
         if (log)
-        {
             log->Printf("%*sFrame %d invalid RegisterContext for this frame, stopping stack walk", 
                         cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        }
-        goto unwind_done;
+        return nullptr;
     }
     if (!reg_ctx_sp->GetCFA (cursor_sp->cfa))
     {
         // If the RegisterContextLLDB has a fallback UnwindPlan, it will switch to that and return
         // true.  Subsequent calls to TryFallbackUnwindPlan() will return false.
-        if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-        {
-            return AddOneMoreFrame (abi);
-        }
+        if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+            return GetOneMoreFrame (abi);
+
         if (log)
-        {
             log->Printf("%*sFrame %d did not get CFA for this frame, stopping stack walk",
                         cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        }
-        goto unwind_done;
+        return nullptr;
     }
     if (abi && !abi->CallFrameAddressIsValid(cursor_sp->cfa))
     {
         // On Mac OS X, the _sigtramp asynchronous signal trampoline frame may not have
         // its (constructed) CFA aligned correctly -- don't do the abi alignment check for
         // these.
         if (reg_ctx_sp->IsTrapHandlerFrame() == false)
         {
             // See if we can find a fallback unwind plan for THIS frame.  It may be
             // that the UnwindPlan we're using for THIS frame was bad and gave us a
             // bad CFA.  
             // If that's not it, then see if we can change the UnwindPlan for the frame
             // below us ("NEXT") -- see if using that other UnwindPlan gets us a better
             // unwind state.
             if (reg_ctx_sp->TryFallbackUnwindPlan() == false
                 || reg_ctx_sp->GetCFA (cursor_sp->cfa) == false
                 || abi->CallFrameAddressIsValid(cursor_sp->cfa) == false)
             {
-                if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-                {
-                    return AddOneMoreFrame (abi);
-                }
+                if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+                    return GetOneMoreFrame (abi);
+
                 if (log)
-                {
                     log->Printf("%*sFrame %d did not get a valid CFA for this frame, stopping stack walk",
                                 cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-                }
-                goto unwind_done;
+                return nullptr;
             }
             else
             {
                 if (log)
-                {
                     log->Printf("%*sFrame %d had a bad CFA value but we switched the UnwindPlan being used and got one that looks more realistic.",
                                 cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-                }
-            }
-        }
-    }
     if (!reg_ctx_sp->ReadPC (cursor_sp->start_pc))
     {
         // If the RegisterContextLLDB has a fallback UnwindPlan, it will switch to that and return
         // true.  Subsequent calls to TryFallbackUnwindPlan() will return false.
-        if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-        {
-            return AddOneMoreFrame (abi);
-        }
+        if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+            return GetOneMoreFrame (abi);
+
         if (log)
-        {
             log->Printf("%*sFrame %d did not get PC for this frame, stopping stack walk",
                         cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        }
-        goto unwind_done;
+        return nullptr;
     }
     if (abi && !abi->CodeAddressIsValid (cursor_sp->start_pc))
     {
         // If the RegisterContextLLDB has a fallback UnwindPlan, it will switch to that and return
         // true.  Subsequent calls to TryFallbackUnwindPlan() will return false.
-        if (m_frames[cur_idx - 1]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
-        {
-            return AddOneMoreFrame (abi);
-        }
+        if (prev_frame->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+            return GetOneMoreFrame (abi);
+
         if (log)
-        {
             log->Printf("%*sFrame %d did not get a valid PC, stopping stack walk",
                         cur_idx < 100 ? cur_idx : 100, "", cur_idx);
-        }
-        goto unwind_done;
-    }
-    if (!m_frames.empty())
-    {
-        // Infinite loop where the current cursor is the same as the previous one...
-        if (m_frames.back()->start_pc == cursor_sp->start_pc && m_frames.back()->cfa == cursor_sp->cfa)
-        {
-            if (log)
-                log->Printf ("th%d pc of this frame is the same as the previous frame and CFAs for both frames are identical -- stopping unwind", m_thread.GetIndexID());
-            goto unwind_done; 
-        }
+        return nullptr;
+    if (prev_frame->start_pc == cursor_sp->start_pc && prev_frame->cfa == cursor_sp->cfa)
+        return nullptr;
     }
 
     cursor_sp->reg_ctx_lldb_sp = reg_ctx_sp;
-    m_frames.push_back (cursor_sp);
-    return true;
-    
-unwind_done:
-    if (log)
+    return cursor_sp;
+}
+bool
+UnwindLLDB::AddOneMoreFrame (ABI *abi)
+{
+    Log *log(GetLogIfAllCategoriesSet (LIBLLDB_LOG_UNWIND));
+
+    // Frame zero is a little different
+    if (m_frames.empty())
+        return false;
+
+    // If we've already gotten to the end of the stack, don't bother to try again...
+    if (m_unwind_complete)
+        return false;
+
+    CursorSP new_frame = m_candidate_frame;
+    if (new_frame == nullptr)
+        new_frame = GetOneMoreFrame(abi);
+
+    if (new_frame == nullptr)
     {
+        if (log)
             log->Printf ("th%d Unwind of this thread is complete.", m_thread.GetIndexID());
-    }
         m_unwind_complete = true;
         return false;
     }
 
+    m_frames.push_back(new_frame);
+
+    // If we can get one more frame further then accept that we get back a correct frame.
+    m_candidate_frame = GetOneMoreFrame(abi);
+    if (m_candidate_frame)
+        return true;
+
+    // We can't go further from the frame returned by GetOneMore frame. Lets try to get a
+    // different frame with using the fallback unwind plan.
+    if (!m_frames[m_frames.size() - 2]->reg_ctx_lldb_sp->TryFallbackUnwindPlan())
+    {
+        // We don't have a valid fallback unwind plan. Accept the frame as it is. This is a
+        // valid situation when we are at the bottom of the stack.
+        return true;
+    }
+
+    // Remove the possibly incorrect frame from the frame list and try to add a different one with
+    // the newly selected fallback unwind plan.
+    m_frames.pop_back();
+    CursorSP new_frame_v2 = GetOneMoreFrame(abi);
+    if (new_frame_v2 == nullptr)
+    {
+        // We haven't got a new frame from the fallback unwind plan. Accept the frame from the
+        // original unwind plan. This is a valid situation when we are at the bottom of the stack.
+        m_frames.push_back(new_frame);
+        return true;
+    }
+
+    // Push the new frame to the list and try to continue from this frame. If we can get a new frame
+    // then accept it as the correct one.
+    m_frames.push_back(new_frame_v2);
+    m_candidate_frame = GetOneMoreFrame(abi);
+    if (m_candidate_frame)
+        return true;
+
+    // The new frame isn't helped in unwinding. Fall back to the original one as the default unwind
+    // plan is usually more reliable then the fallback one.
+    m_frames.pop_back();
+    m_frames.push_back(new_frame);
+    return true;
+}
+
 bool
 UnwindLLDB::DoGetFrameInfoAtIndex (uint32_t idx, addr_t& cfa, addr_t& pc)
 {
     if (m_frames.size() == 0)
     {
         if (!AddFirstFrame())
             return false;
     }