Huge performance improvements when one breakpoint contains many locations.

325,000 breakpoints for running "breakpoint set --func-regex ." on lldb itself (after hitting a breakpoint at main so that LLDB.framework is loaded) used to take up to an hour to set, now we are down under a minute. With warm file caches, we are at 40 seconds, and that is with setting 325,000 breakpoint through the GDB remote API. Linux and the native debuggers might be faster. I haven't timed what how much is debug info parsing and how much is the protocol traffic to/from GDB remote.

That there were many performance issues. Most of them were due to storing breakpoints in the wrong data structures, or using the wrong iterators to traverse the lists, traversing the lists in inefficient ways, and not optimizing certain function name lookups/symbol merges correctly.

Debugging after that is also now very efficient. There were issues with replacing the breakpoint opcodes in memory that was read, and those routines were also fixed.

llvm-svn: 183820

1 files changed, 102 insertions, 190 deletions

diff --git a/lldb/tools/debugserver/source/DNBBreakpoint.cpp b/lldb/tools/debugserver/source/DNBBreakpoint.cpp
index 66706870305..246797c8dae 100644
--- a/lldb/tools/debugserver/source/DNBBreakpoint.cpp
+++ b/lldb/tools/debugserver/source/DNBBreakpoint.cpp
@@ -12,16 +12,17 @@
 //===----------------------------------------------------------------------===//
 
 #include "DNBBreakpoint.h"
+#include "MachProcess.h"
+#include <assert.h>
 #include <algorithm>
 #include <inttypes.h>
 #include "DNBLog.h"
 
 
 #pragma mark -- DNBBreakpoint
-DNBBreakpoint::DNBBreakpoint(nub_addr_t addr, nub_size_t byte_size, nub_thread_t tid, bool hardware) :
-    m_breakID(GetNextID()),
-    m_tid(tid),
-    m_byte_size(byte_size),
+DNBBreakpoint::DNBBreakpoint(nub_addr_t addr, nub_size_t byte_size, bool hardware) :
+    m_retain_count (1),
+    m_byte_size (byte_size),
     m_opcode(),
     m_addr(addr),
     m_enabled(0),
@@ -29,11 +30,7 @@ DNBBreakpoint::DNBBreakpoint(nub_addr_t addr, nub_size_t byte_size, nub_thread_t
     m_is_watchpoint(0),
     m_watch_read(0),
     m_watch_write(0),
-    m_hw_index(INVALID_NUB_HW_INDEX),
-    m_hit_count(0),
-    m_ignore_count(0),
-    m_callback(NULL),
-    m_callback_baton(NULL)
+    m_hw_index(INVALID_NUB_HW_INDEX)
 {
 }
 
@@ -41,71 +38,27 @@ DNBBreakpoint::~DNBBreakpoint()
 {
 }
 
-nub_break_t
-DNBBreakpoint::GetNextID()
-{
-    static uint32_t g_nextBreakID = 0;
-    return ++g_nextBreakID;
-}
-
-void
-DNBBreakpoint::SetCallback(DNBCallbackBreakpointHit callback, void *callback_baton)
-{
-    m_callback = callback;
-    m_callback_baton = callback_baton;
-}
-
-
-// RETURNS - true if we should stop at this breakpoint, false if we
-// should continue.
-
-bool
-DNBBreakpoint::BreakpointHit(nub_process_t pid, nub_thread_t tid)
-{
-    m_hit_count++;
-
-    if (m_hit_count > m_ignore_count)
-    {
-        if (m_callback)
-            return m_callback(pid, tid, GetID(), m_callback_baton);
-        return true;
-    }
-    return false;
-}
-
 void
 DNBBreakpoint::Dump() const
 {
     if (IsBreakpoint())
     {
-        DNBLog ("DNBBreakpoint %u: tid = %8.8" PRIx64 "  addr = 0x%llx  state = %s  type = %s breakpoint  hw_index = %i  hit_count = %-4u  ignore_count = %-4u  callback = %p baton = %p",
-                m_breakID,
-                m_tid,
+        DNBLog ("DNBBreakpoint addr = 0x%llx  state = %s  type = %s breakpoint  hw_index = %i",
                 (uint64_t)m_addr,
                 m_enabled ? "enabled " : "disabled",
                 IsHardware() ? "hardware" : "software",
-                GetHardwareIndex(),
-                GetHitCount(),
-                GetIgnoreCount(),
-                m_callback,
-                m_callback_baton);
+                GetHardwareIndex());
     }
     else
     {
-        DNBLog ("DNBBreakpoint %u: tid = %8.8" PRIx64 "  addr = 0x%llx  size = %llu  state = %s  type = %s watchpoint (%s%s)  hw_index = %i  hit_count = %-4u  ignore_count = %-4u  callback = %p baton = %p",
-                m_breakID,
-                m_tid,
+        DNBLog ("DNBBreakpoint addr = 0x%llx  size = %llu  state = %s  type = %s watchpoint (%s%s)  hw_index = %i",
                 (uint64_t)m_addr,
                 (uint64_t)m_byte_size,
                 m_enabled ? "enabled " : "disabled",
                 IsHardware() ? "hardware" : "software",
                 m_watch_read ? "r" : "",
                 m_watch_write ? "w" : "",
-                GetHardwareIndex(),
-                GetHitCount(),
-                GetIgnoreCount(),
-                m_callback,
-                m_callback_baton);
+                GetHardwareIndex());
     }
 }
 
@@ -120,46 +73,18 @@ DNBBreakpointList::~DNBBreakpointList()
 }
 
 
-nub_break_t
-DNBBreakpointList::Add(const DNBBreakpoint& bp)
-{
-    m_breakpoints.push_back(bp);
-    return m_breakpoints.back().GetID();
-}
-
-bool
-DNBBreakpointList::ShouldStop(nub_process_t pid, nub_thread_t tid, nub_break_t breakID)
-{
-    DNBBreakpoint *bp = FindByID (breakID);
-    if (bp)
-    {
-        // Let the breakpoint decide if it should stop here (could not have
-        // reached it's target hit count yet, or it could have a callback
-        // that decided it shouldn't stop (shared library loads/unloads).
-        return bp->BreakpointHit(pid, tid);
-    }
-    // We should stop here since this breakpoint isn't valid anymore or it
-    // doesn't exist.
-    return true;
-}
-
-nub_break_t
-DNBBreakpointList::FindIDByAddress (nub_addr_t addr)
+DNBBreakpoint *
+DNBBreakpointList::Add(nub_addr_t addr, nub_size_t length, bool hardware)
 {
-    DNBBreakpoint *bp = FindByAddress (addr);
-    if (bp)
-    {
-        DNBLogThreadedIf(LOG_BREAKPOINTS, "DNBBreakpointList::%s ( addr = 0x%16.16llx ) => %u", __FUNCTION__, (uint64_t)addr, bp->GetID());
-        return bp->GetID();
-    }
-    DNBLogThreadedIf(LOG_BREAKPOINTS, "DNBBreakpointList::%s ( addr = 0x%16.16llx ) => NONE", __FUNCTION__, (uint64_t)addr);
-    return INVALID_NUB_BREAK_ID;
+    m_breakpoints.insert(std::make_pair(addr, DNBBreakpoint(addr, length, hardware)));
+    iterator pos = m_breakpoints.find (addr);
+    return &pos->second;
 }
 
 bool
-DNBBreakpointList::Remove (nub_break_t breakID)
+DNBBreakpointList::Remove (nub_addr_t addr)
 {
-    iterator pos = GetBreakIDIterator(breakID);    // Predicate
+    iterator pos = m_breakpoints.find(addr);
     if (pos != m_breakpoints.end())
     {
         m_breakpoints.erase(pos);
@@ -168,146 +93,133 @@ DNBBreakpointList::Remove (nub_break_t breakID)
     return false;
 }
 
-
-class BreakpointIDMatches
-{
-public:
-    BreakpointIDMatches (nub_break_t breakID) : m_breakID(breakID) {}
-    bool operator() (const DNBBreakpoint& bp) const
-    {
-        return m_breakID == bp.GetID();
-    }
- private:
-   const nub_break_t m_breakID;
-};
-
-class BreakpointAddressMatches
-{
-public:
-    BreakpointAddressMatches (nub_addr_t addr) : m_addr(addr) {}
-    bool operator() (const DNBBreakpoint& bp) const
-    {
-        return m_addr == bp.Address();
-    }
- private:
-   const nub_addr_t m_addr;
-};
-
-DNBBreakpointList::iterator
-DNBBreakpointList::GetBreakIDIterator (nub_break_t breakID)
-{
-    return std::find_if(m_breakpoints.begin(), m_breakpoints.end(), // Search full range
-                        BreakpointIDMatches(breakID));              // Predicate
-}
-
-DNBBreakpointList::const_iterator
-DNBBreakpointList::GetBreakIDConstIterator (nub_break_t breakID) const
-{
-    return std::find_if(m_breakpoints.begin(), m_breakpoints.end(), // Search full range
-                        BreakpointIDMatches(breakID));              // Predicate
-}
-
 DNBBreakpoint *
-DNBBreakpointList::FindByID (nub_break_t breakID)
+DNBBreakpointList::FindByAddress (nub_addr_t addr)
 {
-    iterator pos = GetBreakIDIterator(breakID);
+    iterator pos = m_breakpoints.find(addr);
     if (pos != m_breakpoints.end())
-        return &(*pos);
+        return &pos->second;
 
     return NULL;
 }
 
 const DNBBreakpoint *
-DNBBreakpointList::FindByID (nub_break_t breakID) const
+DNBBreakpointList::FindByAddress (nub_addr_t addr) const
 {
-    const_iterator pos = GetBreakIDConstIterator(breakID);
+    const_iterator pos = m_breakpoints.find(addr);
     if (pos != m_breakpoints.end())
-        return &(*pos);
-
+        return &pos->second;
+    
     return NULL;
 }
 
-DNBBreakpoint *
-DNBBreakpointList::FindByAddress (nub_addr_t addr)
+// Finds the next breakpoint at an address greater than or equal to "addr"
+size_t
+DNBBreakpointList::FindBreakpointsThatOverlapRange (nub_addr_t addr,
+                                                    nub_addr_t size,
+                                                    std::vector<DNBBreakpoint *> &bps)
 {
+    bps.clear();
     iterator end = m_breakpoints.end();
-    iterator pos = std::find_if(m_breakpoints.begin(), end,             // Search full range
-                                BreakpointAddressMatches(addr));        // Predicate
+    // Find the first breakpoint with an address >= to "addr"
+    iterator pos = m_breakpoints.lower_bound(addr);
     if (pos != end)
-        return &(*pos);
-
-    return NULL;
-}
-
-const DNBBreakpoint *
-DNBBreakpointList::FindByAddress (nub_addr_t addr) const
-{
-    const_iterator end = m_breakpoints.end();
-    const_iterator pos = std::find_if(m_breakpoints.begin(), end,       // Search full range
-                                      BreakpointAddressMatches(addr));  // Predicate
-    if (pos != end)
-        return &(*pos);
-
-    return NULL;
-}
-
-bool
-DNBBreakpointList::SetCallback(nub_break_t breakID, DNBCallbackBreakpointHit callback, void *callback_baton)
-{
-    DNBBreakpoint *bp = FindByID (breakID);
-    if (bp)
     {
-        bp->SetCallback(callback, callback_baton);
-        return true;
+        if (pos != m_breakpoints.begin())
+        {
+            // Watch out for a breakpoint at an address less than "addr" that might still overlap
+            iterator prev_pos = pos;
+            --prev_pos;
+            if (prev_pos->second.IntersectsRange (addr, size, NULL, NULL, NULL))
+                bps.push_back (&pos->second);
+            
+        }
+
+        while (pos != end)
+        {
+            // When we hit a breakpoint whose start address is greater than "addr + size" we are done.
+            // Do the math in a way that doesn't risk unsigned overflow with bad input.
+            if ((pos->second.Address() - addr) >= size)
+                break;
+                
+            // Check if this breakpoint overlaps, and if it does, add it to the list
+            if (pos->second.IntersectsRange (addr, size, NULL, NULL, NULL))
+            {
+                bps.push_back (&pos->second);
+                ++pos;
+            }
+        }
     }
-    return false;
+    return bps.size();
 }
 
-
 void
 DNBBreakpointList::Dump() const
 {
     const_iterator pos;
     const_iterator end = m_breakpoints.end();
     for (pos = m_breakpoints.begin(); pos != end; ++pos)
-        (*pos).Dump();
+        pos->second.Dump();
+}
+
+void
+DNBBreakpointList::DisableAll ()
+{
+    iterator pos, end = m_breakpoints.end();
+    for (pos = m_breakpoints.begin(); pos != end; ++pos)
+        pos->second.SetEnabled(false);
 }
 
 
-DNBBreakpoint *
-DNBBreakpointList::GetByIndex (uint32_t i)
+void
+DNBBreakpointList::RemoveTrapsFromBuffer (nub_addr_t addr, nub_size_t size, void *p) const
 {
-    iterator end = m_breakpoints.end();
-    iterator pos;
-    uint32_t curr_i = 0;
-    for (pos = m_breakpoints.begin(), curr_i = 0; pos != end; ++pos, ++curr_i)
+    uint8_t *buf = (uint8_t *)p;
+    const_iterator end = m_breakpoints.end();
+    const_iterator pos = m_breakpoints.lower_bound(addr);
+    while (pos != end && (pos->first < (addr + size)))
     {
-        if (curr_i == i)
-            return &(*pos);
+        nub_addr_t intersect_addr;
+        nub_size_t intersect_size;
+        nub_size_t opcode_offset;
+        const DNBBreakpoint &bp = pos->second;
+        if (bp.IntersectsRange(addr, size, &intersect_addr, &intersect_size, &opcode_offset))
+        {
+            assert(addr <= intersect_addr && intersect_addr < addr + size);
+            assert(addr < intersect_addr + intersect_size && intersect_addr + intersect_size <= addr + size);
+            assert(opcode_offset + intersect_size <= bp.ByteSize());
+            nub_size_t buf_offset = intersect_addr - addr;
+            ::memcpy(buf + buf_offset, bp.SavedOpcodeBytes() + opcode_offset, intersect_size);
+        }
+        ++pos;
     }
-    return NULL;
 }
 
 void
-DNBBreakpointList::DisableAll ()
+DNBBreakpointList::DisableAllBreakpoints(MachProcess *process)
 {
     iterator pos, end = m_breakpoints.end();
     for (pos = m_breakpoints.begin(); pos != end; ++pos)
-        (*pos).SetEnabled(false);
+        process->DisableBreakpoint(pos->second.Address(), false);    
 }
 
+void
+DNBBreakpointList::DisableAllWatchpoints(MachProcess *process)
+{
+    iterator pos, end = m_breakpoints.end();
+    for (pos = m_breakpoints.begin(); pos != end; ++pos)
+        process->DisableWatchpoint(pos->second.Address(), false);
+}
 
-const DNBBreakpoint *
-DNBBreakpointList::GetByIndex (uint32_t i) const
+void
+DNBBreakpointList::RemoveDisabled()
 {
-    const_iterator end = m_breakpoints.end();
-    const_iterator pos;
-    uint32_t curr_i = 0;
-    for (pos = m_breakpoints.begin(), curr_i = 0; pos != end; ++pos, ++curr_i)
+    iterator pos = m_breakpoints.begin();
+    while (pos != m_breakpoints.end())
     {
-        if (curr_i == i)
-            return &(*pos);
+        if (!pos->second.IsEnabled())
+            pos = m_breakpoints.erase(pos);
+        else
+            ++pos;
     }
-    return NULL;
 }
-