Extending step-over range past calls was causing deadlocks, fix that.

[jingham]

Summary

This change:

https://reviews.llvm.org/D58678

made lldb extend it's "next branch breakpoint" over IsCall instructions as a way to speed up stepping. However, the change wasn't quite complete. When lldb runs to the "next branch breakpoint" it always stops other threads when doing so. That is because as much as possible we want users to be able to focus on the thread they are debugging, and not have events from other threads disrupt their attention.

It was safe to do this for code in a function because, except in very odd circumstances, the actions that might deadlock are always function calls.

Before this change we would run to the call, step into a function, then step out. And we always run all threads when we step out of a function call.

With the change, we were extending the range past the call, but treating it as "code in the function", which it no longer was. That would mean we were running arbitrary code with only on thread running, and that causes deadlocks in the target, and then the "step-over" would never complete.

This patch adds a parameter to GetIndexOfNextBranchInstruction telling whether we did extend past a call or not. Then in ThreadPlanStepOverRange, we check this parameter and run one thread or all threads depending on whether we extended past a call.

I also added a test case for this behavior. It is a little unfortunate that the failure of the test will really be a timeout since if we do it wrong the step-over doesn't return. But I can't think of a better way of doing it. I don't want to add a watchdog timer because then I'd get spurious failures on slow machines or fight against the overall timeouts...

[clayborg]

That must have been fun to find! LGTM.

[labath]

This looks like a tricky bug. Thanks for tracking it down.

I have two questions though: :D

• could you use c++11 locking primitives in the test? pthreads do not work on windows
• what exactly will be the effect of this? Will we start all threads immediately, or will we do the usual dance of trying to run one thread for a short period of time, and then resume all of them if that times out? If it's the latter, I'm wondering if we really need this call detection logic -- we could theoretically just use the "run all" method all the time (except if explicitly disabled), with the knowledge that all reasonable call-less sequences will finish before the "run single thread" timeout expires. And it would automatically also handle weird call-less sequences with spinlocks or what not...

[jingham]

In D71440#1783197, @labath wrote:

This looks like a tricky bug. Thanks for tracking it down.

I have two questions though: :D

• could you use c++11 locking primitives in the test? pthreads do not work on windows

I copied the test from somewhere else, so I'll have to change the original too. Let me give this a go.

• what exactly will be the effect of this? Will we start all threads immediately, or will we do the usual dance of trying to run one thread for a short period of time, and then resume all of them if that times out? If it's the latter, I'm wondering if we really need this call detection logic -- we could theoretically just use the "run all" method all the time (except if explicitly disabled), with the knowledge that all reasonable call-less sequences will finish before the "run single thread" timeout expires. And it would automatically also handle weird call-less sequences with spinlocks or what not...

Currently, the actually stepping plans don't do "try a bit on one thread, then resume all". They are conservative, and will let all threads run anytime they run "arbitrary" code. It's only running expressions that does the one and then many dance.

The original idea was that the "Process::RunThreadPlan" would be used for all the thread plans that might stall if run on only one thread. But before it got wired up for that it became dedicated to expression evaluation. It's more important to try to stay on one thread for expressions, since the user stopped the process somehow and has a reasonable expectation that it will stay stopped. But as a side effect, I never got around to wiring that dance up to the regular stepping.

However, since I've been playing around with this trick for expression evaluation I'm a little less sure I want to extend it to regular operation. OTOH, that WOULD fix problems with stepping over call-less spinlocks. More importantly - since I've never had any reports of that theoretical problem being an actual problem - we would get better at keeping stepping operations on one thread.

OTOH, interrupting a process is not cost-free. We have to send a signal to interrupt it and that can cause EINTR's in places people weren't expecting. This has caused problems in the past, where the interrupt from running an expression will cause a read call to raise an unhandled EINTR. Of course you should always check for EINTR etc so these probably are actually bugs in code, and you'd think people would thank me for surfacing the bug. But when I point that out it doesn't seem to mollify the users who have reported the problem.

This is a common enough "mis-pattern" that I am hesitant to add a stepping method that would really spam the inferior with interrupts. I think our current method is the best compromise between trying to keep focus on the active thread, and changing normal flow of execution as little as possible.

[jingham]

Changed the test case from locking.c - using pthreads directly - to locking.cpp using std::thread & Co.

I also changed the test I cobbed this one from to use std::thread as well. I prospectively removed the expected fail Windows from the expression test, since this should build now.

[labath]

Thanks for the explanation (and for updating the test). This actually explains why it sometimes seemed that I lose control over other threads while stepping one of them. I'll be sure to use the --run-mode argument next time. This seems fine given how the current stepping logic works, though I personally would expect that the other also threads stay stopped when i do something called "thread step-over", but I get the feeling I expect a different kind of threading behavior from my debugger than most people...

lldb/include/lldb/Core/Disassembler.h

public:
   /// @param[in] target
   ///     A LLDB target object that is used to resolve addresses.
   ///    
   /// @param[in] ignore_calls
   ///     It true, then fine the first branch instruction that isn't
   ///     a function call (a branch that calls and returns to the next
   ///     instruction). If false, find the instruction index of any 
   ///     branch in the list.
-  ///    
+  ///     
+  /// @param[out] found_calls
+  ///     If non-null, this will be set to true if any calls were found in 
+  ///     extending the range.
+  ///    
   /// @return
   ///     The instruction index of the first branch that is at or past
   ///     \a start. Returns UINT32_MAX if no matching branches are 
   ///     found.
   //------------------------------------------------------------------
   uint32_t GetIndexOfNextBranchInstruction(uint32_t start,
                                            Target &target,
-                                           bool ignore_calls) const;
+                                           bool ignore_calls,
+                                           bool *found_calls) const;
 
   uint32_t GetIndexOfInstructionAtLoadAddress(lldb::addr_t load_addr,
                                               Target &target);
 
   uint32_t GetIndexOfInstructionAtAddress(const Address &addr);
 
   void Clear();
 

lldb/include/lldb/Target/ThreadPlanStepRange.h

protected:
   bool m_no_more_plans;   // Need this one so we can tell if we stepped into a
                           // call,
                           // but can't continue, in which case we are done.
   bool m_first_run_event; // We want to broadcast only one running event, our
                           // first.
   lldb::BreakpointSP m_next_branch_bp_sp;
   bool m_use_fast_step;
   bool m_given_ranges_only;
+  bool m_found_calls = false; // When we set the next branch breakpoint for
+                              // step over, we now extend them past call insns
+                              // that directly return.  But if we do that we
+                              // need to run all threads, or we might cause
+                              // deadlocks.  This tells us whether we found
+                              // any calls in setting the next branch breakpoint.
 
 private:
   std::vector<lldb::DisassemblerSP> m_instruction_ranges;
 
   DISALLOW_COPY_AND_ASSIGN(ThreadPlanStepRange);
 };
 
 } // namespace lldb_private
 
 #endif // liblldb_ThreadPlanStepRange_h_

lldb/packages/Python/lldbsuite/test/commands/expression/no-deadlock/Makefile

-C_SOURCES := locking.c
+CXX_SOURCES := locking.cpp
 ENABLE_THREADS := YES
 
 include Makefile.rules

lldb/packages/Python/lldbsuite/test/commands/expression/no-deadlock/TestExprDoesntBlock.py

 from lldbsuite.test import lldbutil
 
 
 class ExprDoesntDeadlockTestCase(TestBase):
 
     mydir = TestBase.compute_mydir(__file__)
 
     @expectedFailureAll(oslist=['freebsd'], bugnumber='llvm.org/pr17946')
-    @expectedFailureAll(
-        oslist=["windows"],
-        bugnumber="Windows doesn't have pthreads, test needs to be ported")
     @add_test_categories(["basic_process"])
     def test_with_run_command(self):
         """Test that expr will time out and allow other threads to run if it blocks."""
         self.build()
         exe = self.getBuildArtifact("a.out")
 
         # Create a target by the debugger.
         target = self.dbg.CreateTarget(exe)
         self.assertTrue(target, VALID_TARGET)
 
         # Now create a breakpoint at source line before call_me_to_get_lock
         # gets called.
 
-        main_file_spec = lldb.SBFileSpec("locking.c")
+        main_file_spec = lldb.SBFileSpec("locking.cpp")
         breakpoint = target.BreakpointCreateBySourceRegex(
             'Break here', main_file_spec)
         if self.TraceOn():
             print("breakpoint:", breakpoint)
         self.assertTrue(breakpoint and
                         breakpoint.GetNumLocations() == 1,
                         VALID_BREAKPOINT)
 
         # Now launch the process, and do not stop at entry point.
         process = target.LaunchSimple(
             None, None, self.get_process_working_directory())
         self.assertTrue(process, PROCESS_IS_VALID)
 
         # Frame #0 should be on self.line1 and the break condition should hold.
         from lldbsuite.test.lldbutil import get_stopped_thread
         thread = get_stopped_thread(process, lldb.eStopReasonBreakpoint)
         self.assertTrue(
             thread.IsValid(),
             "There should be a thread stopped due to breakpoint condition")
 
         frame0 = thread.GetFrameAtIndex(0)
 
-        var = frame0.EvaluateExpression("call_me_to_get_lock()")
+        var = frame0.EvaluateExpression("call_me_to_get_lock(get_int())")
         self.assertTrue(var.IsValid())
-        self.assertTrue(var.GetValueAsSigned(0) == 567)
+        self.assertEqual(var.GetValueAsSigned(0), 567)

lldb/packages/Python/lldbsuite/test/commands/expression/no-deadlock/locking.c

-#include <pthread.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <stdio.h>
-
-pthread_mutex_t contended_mutex = PTHREAD_MUTEX_INITIALIZER;
-
-pthread_mutex_t control_mutex = PTHREAD_MUTEX_INITIALIZER;
-pthread_cond_t  control_condition;
-
-pthread_mutex_t thread_started_mutex = PTHREAD_MUTEX_INITIALIZER;
-pthread_cond_t  thread_started_condition;
-
-// This function runs in a thread.  The locking dance is to make sure that 
-// by the time the main thread reaches the pthread_join below, this thread
-// has for sure acquired the contended_mutex.  So then the call_me_to_get_lock
-// function will block trying to get the mutex, and only succeed once it
-// signals this thread, then lets it run to wake up from the cond_wait and
-// release the mutex.
-
-void *
-lock_acquirer_1 (void *input)
-{
-  pthread_mutex_lock (&contended_mutex);
-  
-  // Grab this mutex, that will ensure that the main thread
-  // is in its cond_wait for it (since that's when it drops the mutex.
-
-  pthread_mutex_lock (&thread_started_mutex);
-  pthread_mutex_unlock(&thread_started_mutex);
-
-  // Now signal the main thread that it can continue, we have the contended lock
-  // so the call to call_me_to_get_lock won't make any progress till  this
-  // thread gets a chance to run.
-
-  pthread_mutex_lock (&control_mutex);
-
-  pthread_cond_signal (&thread_started_condition);
-
-  pthread_cond_wait (&control_condition, &control_mutex);
-
-  pthread_mutex_unlock (&contended_mutex);
-  return NULL;
-}
-
-int
-call_me_to_get_lock ()
-{
-  pthread_cond_signal (&control_condition);
-  pthread_mutex_lock (&contended_mutex);
-  return 567;
-}
-
-int main ()
-{
-  pthread_t thread_1;
-
-  pthread_cond_init (&control_condition, NULL);
-  pthread_cond_init (&thread_started_condition, NULL);
-
-  pthread_mutex_lock (&thread_started_mutex);
-
-  pthread_create (&thread_1, NULL, lock_acquirer_1, NULL);
-  
-  pthread_cond_wait (&thread_started_condition, &thread_started_mutex);
-
-  pthread_mutex_lock (&control_mutex);
-  pthread_mutex_unlock (&control_mutex);
-
-  // Break here.  At this point the other thread will have the contended_mutex,
-  // and be sitting in its cond_wait for the control condition.  So there is
-  // no way that our by-hand calling of call_me_to_get_lock will proceed
-  // without running the first thread at least somewhat.
-
-  call_me_to_get_lock();
-  pthread_join (thread_1, NULL);
-
-  return 0;
-
-}

lldb/packages/Python/lldbsuite/test/commands/expression/no-deadlock/locking.cpp

+#include <stdio.h>
+#include <thread>
+
+std::mutex contended_mutex;
+
+std::mutex control_mutex;
+std::condition_variable  control_condition;
+
+std::mutex thread_started_mutex;
+std::condition_variable  thread_started_condition;
+
+// This function runs in a thread.  The locking dance is to make sure that 
+// by the time the main thread reaches the pthread_join below, this thread
+// has for sure acquired the contended_mutex.  So then the call_me_to_get_lock
+// function will block trying to get the mutex, and only succeed once it
+// signals this thread, then lets it run to wake up from the cond_wait and
+// release the mutex.
+
+void
+lock_acquirer_1 (void)
+{
+  std::unique_lock<std::mutex> contended_lock(contended_mutex);
+  
+  // Grab this mutex, that will ensure that the main thread
+  // is in its cond_wait for it (since that's when it drops the mutex.
+
+  thread_started_mutex.lock();
+  thread_started_mutex.unlock();
+
+  // Now signal the main thread that it can continue, we have the contended lock
+  // so the call to call_me_to_get_lock won't make any progress till  this
+  // thread gets a chance to run.
+
+  std::unique_lock<std::mutex> control_lock(control_mutex);
+
+  thread_started_condition.notify_all();
+
+  control_condition.wait(control_lock);
+
+}
+
+int
+call_me_to_get_lock (int ret_val)
+{
+  control_condition.notify_all();
+  contended_mutex.lock();
+  return ret_val;
+}
+
+int
+get_int() {
+  return 567;
+}
+
+int main ()
+{
+  std::unique_lock<std::mutex> thread_started_lock(thread_started_mutex);
+
+  std::thread thread_1(lock_acquirer_1);
+
+  thread_started_condition.wait(thread_started_lock);
+
+  control_mutex.lock();
+  control_mutex.unlock();
+
+  // Break here.  At this point the other thread will have the contended_mutex,
+  // and be sitting in its cond_wait for the control condition.  So there is
+  // no way that our by-hand calling of call_me_to_get_lock will proceed
+  // without running the first thread at least somewhat.
+
+  int result = call_me_to_get_lock(get_int());
+  thread_1.join();
+
+  return 0;
+
+}

lldb/packages/Python/lldbsuite/test/lang/c/step_over_no_deadlock/Makefile

-C_SOURCES := locking.c
+CXX_SOURCES := locking.cpp
 ENABLE_THREADS := YES
 
 include Makefile.rules

lldb/packages/Python/lldbsuite/test/lang/c/step_over_no_deadlock/TestStepOverDoesntBlock.py

+"""
+Test that step over will let other threads run when necessary
+"""
+
+from __future__ import print_function
+
+
+import lldb
+from lldbsuite.test.decorators import *
+from lldbsuite.test.lldbtest import *
+from lldbsuite.test import lldbutil
+
+
+class StepOverDoesntDeadlockTestCase(TestBase):
+
+    mydir = TestBase.compute_mydir(__file__)
+
+    def test_step_over(self):
+        """Test that when step over steps over a function it lets other threads run."""
+        self.build()
+        (target, process, thread, bkpt) = lldbutil.run_to_source_breakpoint(self,
+                                                                            "without running the first thread at least somewhat",
+                                                                            lldb.SBFileSpec("locking.cpp"))
+        # This is just testing that the step over actually completes.
+        # If the test fails this step never return, so failure is really
+        # signaled by the test timing out.
+        
+        thread.StepOver()
+        state = process.GetState()
+        self.assertEqual(state, lldb.eStateStopped)

lldb/packages/Python/lldbsuite/test/lang/c/step_over_no_deadlock/locking.cpp

+#include <stdio.h>
+#include <thread>
+
+std::mutex contended_mutex;
+
+std::mutex control_mutex;
+std::condition_variable  control_condition;
+
+std::mutex thread_started_mutex;
+std::condition_variable  thread_started_condition;
+
+// This function runs in a thread.  The locking dance is to make sure that 
+// by the time the main thread reaches the pthread_join below, this thread
+// has for sure acquired the contended_mutex.  So then the call_me_to_get_lock
+// function will block trying to get the mutex, and only succeed once it
+// signals this thread, then lets it run to wake up from the cond_wait and
+// release the mutex.
+
+void
+lock_acquirer_1 (void)
+{
+  std::unique_lock<std::mutex> contended_lock(contended_mutex);
+  
+  // Grab this mutex, that will ensure that the main thread
+  // is in its cond_wait for it (since that's when it drops the mutex.
+
+  thread_started_mutex.lock();
+  thread_started_mutex.unlock();
+
+  // Now signal the main thread that it can continue, we have the contended lock
+  // so the call to call_me_to_get_lock won't make any progress till  this
+  // thread gets a chance to run.
+
+  std::unique_lock<std::mutex> control_lock(control_mutex);
+
+  thread_started_condition.notify_all();
+
+  control_condition.wait(control_lock);
+
+}
+
+int
+call_me_to_get_lock (int ret_val)
+{
+  control_condition.notify_all();
+  contended_mutex.lock();
+  return ret_val;
+}
+
+int
+get_int() {
+  return 567;
+}
+
+int main ()
+{
+  std::unique_lock<std::mutex> thread_started_lock(thread_started_mutex);
+
+  std::thread thread_1(lock_acquirer_1);
+
+  thread_started_condition.wait(thread_started_lock);
+
+  control_mutex.lock();
+  control_mutex.unlock();
+
+  // Break here.  At this point the other thread will have the contended_mutex,
+  // and be sitting in its cond_wait for the control condition.  So there is
+  // no way that our by-hand calling of call_me_to_get_lock will proceed
+  // without running the first thread at least somewhat.
+
+  int result = call_me_to_get_lock(get_int());
+  thread_1.join();
+
+  return 0;
+
+}

lldb/source/Core/Disassembler.cpp

 void InstructionList::Append(lldb::InstructionSP &inst_sp) {
   if (inst_sp)
     m_instructions.push_back(inst_sp);
 }
 
 uint32_t
 InstructionList::GetIndexOfNextBranchInstruction(uint32_t start,
                                                  Target &target,
-                                                 bool ignore_calls) const {
+                                                 bool ignore_calls,
+                                                 bool *found_calls) const {
   size_t num_instructions = m_instructions.size();
 
   uint32_t next_branch = UINT32_MAX;
   size_t i;
+  
+  if (found_calls)
+    *found_calls = false;
   for (i = start; i < num_instructions; i++) {
     if (m_instructions[i]->DoesBranch()) {
-      if (ignore_calls && m_instructions[i]->IsCall())
+      if (ignore_calls && m_instructions[i]->IsCall()) {
+        if (found_calls)
+          *found_calls = true;
         continue;
+      }
       next_branch = i;
       break;
     }
   }
 
   // Hexagon needs the first instruction of the packet with the branch. Go
   // backwards until we find an instruction marked end-of-packet, or until we
   // hit start.

lldb/source/Target/Process.cpp

Process::AdvanceAddressToNextBranchInstruction(Address default_stop_addr,
   size_t insn_offset =
       insn_list->GetIndexOfInstructionAtAddress(default_stop_addr);
   if (insn_offset == UINT32_MAX) {
     return retval;
   }
 
   uint32_t branch_index =
       insn_list->GetIndexOfNextBranchInstruction(insn_offset, target,
-                                                 false /* ignore_calls*/);
+                                                 false /* ignore_calls*/,
+                                                 nullptr);
   if (branch_index == UINT32_MAX) {
     return retval;
   }
 
   if (branch_index > insn_offset) {
     Address next_branch_insn_address =
         insn_list->GetInstructionAtIndex(branch_index)->GetAddress();
     if (next_branch_insn_address.IsValid() &&

lldb/source/Target/ThreadPlanStepRange.cpp

if (m_parent_stack_id.IsValid() && cur_parent_id.IsValid() &&
       frame_order = eFrameCompareSameParent;
     else
       frame_order = eFrameCompareOlder;
   }
   return frame_order;
 }
 
 bool ThreadPlanStepRange::StopOthers() {
-  return (m_stop_others == lldb::eOnlyThisThread ||
-          m_stop_others == lldb::eOnlyDuringStepping);
+  switch (m_stop_others) {
+  case lldb::eOnlyThisThread:
+    return true;
+  case lldb::eOnlyDuringStepping:
+    // If there is a call in the range of the next branch breakpoint,
+    // then we should always run all threads, since a call can execute
+    // arbitrary code which might for instance take a lock that's held
+    // by another thread.
+    return !m_found_calls;
+  case lldb::eAllThreads:
+    return false;
+  }
 }
 
 InstructionList *ThreadPlanStepRange::GetInstructionsForAddress(
     lldb::addr_t addr, size_t &range_index, size_t &insn_offset) {
   size_t num_ranges = m_address_ranges.size();
   for (size_t i = 0; i < num_ranges; i++) {
     if (m_address_ranges[i].ContainsLoadAddress(addr, &GetTarget())) {
       // Some joker added a zero size range to the stepping range...

 void ThreadPlanStepRange::ClearNextBranchBreakpoint() {
   if (m_next_branch_bp_sp) {
     Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
     LLDB_LOGF(log, "Removing next branch breakpoint: %d.",
               m_next_branch_bp_sp->GetID());
     GetTarget().RemoveBreakpointByID(m_next_branch_bp_sp->GetID());
     m_next_branch_bp_sp.reset();
     m_could_not_resolve_hw_bp = false;
+    m_found_calls = false;
   }
 }
 
 bool ThreadPlanStepRange::SetNextBranchBreakpoint() {
   if (m_next_branch_bp_sp)
     return true;
 
   Log *log(lldb_private::GetLogIfAllCategoriesSet(LIBLLDB_LOG_STEP));
   // Stepping through ranges using breakpoints doesn't work yet, but with this
   // off we fall back to instruction single stepping.
   if (!m_use_fast_step)
     return false;
 
+  // clear the m_found_calls, we'll rediscover it for this range.
+  m_found_calls = false;
+  
   lldb::addr_t cur_addr = GetThread().GetRegisterContext()->GetPC();
   // Find the current address in our address ranges, and fetch the disassembly
   // if we haven't already:
   size_t pc_index;
   size_t range_index;
   InstructionList *instructions =
       GetInstructionsForAddress(cur_addr, range_index, pc_index);
   if (instructions == nullptr)
     return false;
   else {
     Target &target = GetThread().GetProcess()->GetTarget();
     const bool ignore_calls = GetKind() == eKindStepOverRange;
+    bool found_calls;
     uint32_t branch_index =
         instructions->GetIndexOfNextBranchInstruction(pc_index, target,
-                                                      ignore_calls);
+                                                      ignore_calls, 
+                                                      &m_found_calls);
 
     Address run_to_address;
 
     // If we didn't find a branch, run to the end of the range.
     if (branch_index == UINT32_MAX) {
       uint32_t last_index = instructions->GetSize() - 1;
       if (last_index - pc_index > 1) {
         InstructionSP last_inst =