Changeset 170677 in webkit

Timestamp:

Jul 1, 2014 4:40:32 PM (10 years ago)

Author:

mark.lam@apple.com

Message:

Debugger's breakpoint list should not be a Vector.
<​https://webkit.org/b/134514>

Reviewed by Geoffrey Garen.

The debugger currently stores breakpoint data as entries in a Vector (see
BreakpointsInLine). It also keeps a fast map look up of breakpoint IDs to
the breakpoint data (see m_breakpointIDToBreakpoint). Because a Vector can
compact or reallocate its backing store, this can causes all sorts of havoc.
The m_breakpointIDToBreakpoint map assumes that the breakpoint data doesn't
move in memory.

The fix is to replace the BreakpointsInLine Vector with a BreakpointsList
doubly linked list.

• debugger/Breakpoint.h:

(JSC::Breakpoint::Breakpoint):
(JSC::BreakpointsList::~BreakpointsList):

• debugger/Debugger.cpp:

(JSC::Debugger::setBreakpoint):
(JSC::Debugger::removeBreakpoint):
(JSC::Debugger::hasBreakpoint):

• debugger/Debugger.h:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• debugger/Breakpoint.h (modified) (3 diffs)
• debugger/Debugger.cpp (modified) (7 diffs)
• debugger/Debugger.h (modified) (2 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2014-07-01  Mark Lam  <mark.lam@apple.com>
+
+        Debugger's breakpoint list should not be a Vector.
+        <https://webkit.org/b/134514>
+
+        Reviewed by Geoffrey Garen.
+
+        The debugger currently stores breakpoint data as entries in a Vector (see
+        BreakpointsInLine).  It also keeps a fast map look up of breakpoint IDs to
+        the breakpoint data (see m_breakpointIDToBreakpoint).  Because a Vector can
+        compact or reallocate its backing store, this can causes all sorts of havoc.
+        The m_breakpointIDToBreakpoint map assumes that the breakpoint data doesn't
+        move in memory.
+
+        The fix is to replace the BreakpointsInLine Vector with a BreakpointsList
+        doubly linked list.
+
+        * debugger/Breakpoint.h:
+        (JSC::Breakpoint::Breakpoint):
+        (JSC::BreakpointsList::~BreakpointsList):
+        * debugger/Debugger.cpp:
+        (JSC::Debugger::setBreakpoint):
+        (JSC::Debugger::removeBreakpoint):
+        (JSC::Debugger::hasBreakpoint):
+        * debugger/Debugger.h:
+
 2014-06-30  Michael Saboff  <msaboff@apple.com>
 

trunk/Source/JavaScriptCore/debugger/Breakpoint.h

@@ -28 +28 @@
 
 #include "DebuggerPrimitives.h"
+#include <wtf/DoublyLinkedList.h>
+#include <wtf/RefCounted.h>
 #include <wtf/text/WTFString.h>
 
 namespace JSC {
 
-struct Breakpoint {
+struct Breakpoint : public DoublyLinkedListNode<Breakpoint> {
     Breakpoint()
         : id(noBreakpointID)
@@ -52 +54 @@
     }
 
+    Breakpoint(const Breakpoint& other)
+        : id(other.id)
+        , sourceID(other.sourceID)
+        , line(other.line)
+        , column(other.column)
+        , condition(other.condition)
+        , autoContinue(other.autoContinue)
+    {
+    }
+
     BreakpointID id;
     SourceID sourceID;
@@ -60 +72 @@
 
     static const unsigned unspecifiedColumn = UINT_MAX;
+
+private:
+    Breakpoint* m_prev;
+    Breakpoint* m_next;
+
+    friend class WTF::DoublyLinkedListNode<Breakpoint>;
+};
+
+class BreakpointsList : public DoublyLinkedList<Breakpoint>,
+    public RefCounted<BreakpointsList> {
+public:
+    ~BreakpointsList()
+    {
+        Breakpoint* breakpoint;
+        while ((breakpoint = removeHead()))
+            delete breakpoint;
+        ASSERT(isEmpty());
+    }
 };
 

trunk/Source/JavaScriptCore/debugger/Debugger.cpp

@@ -358 +358 @@
     LineToBreakpointsMap::iterator breaksIt = it->value.find(line);
     if (breaksIt == it->value.end())
-        breaksIt = it->value.set(line, BreakpointsInLine()).iterator;
-
-    BreakpointsInLine& breakpoints = breaksIt->value;
-    unsigned breakpointsCount = breakpoints.size();
-    for (unsigned i = 0; i < breakpointsCount; i++)
-        if (breakpoints[i].column == column) {
+        breaksIt = it->value.set(line, adoptRef(new BreakpointsList)).iterator;
+
+    BreakpointsList& breakpoints = *breaksIt->value;
+    for (Breakpoint* current = breakpoints.head(); current; current = current->next()) {
+        if (current->column == column) {
             // The breakpoint already exists. We're not allowed to create a new
             // breakpoint at this location. Rather than returning the breakpointID
@@ -370 +369 @@
             return noBreakpointID;
         }
+    }
 
     BreakpointID id = ++m_topBreakpointID;
@@ -378 +378 @@
     actualColumn = column;
 
-    breakpoints.append(breakpoint);
-    m_breakpointIDToBreakpoint.set(id, &breakpoints.last());
+    Breakpoint* newBreakpoint = new Breakpoint(breakpoint);
+    breakpoints.append(newBreakpoint);
+    m_breakpointIDToBreakpoint.set(id, newBreakpoint);
 
     toggleBreakpoint(breakpoint, BreakpointEnabled);
@@ -392 +393 @@
     BreakpointIDToBreakpointMap::iterator idIt = m_breakpointIDToBreakpoint.find(id);
     ASSERT(idIt != m_breakpointIDToBreakpoint.end());
-    Breakpoint& breakpoint = *idIt->value;
-
-    SourceID sourceID = breakpoint.sourceID;
+    Breakpoint* breakpoint = idIt->value;
+
+    SourceID sourceID = breakpoint->sourceID;
     ASSERT(sourceID);
     SourceIDToBreakpointsMap::iterator it = m_sourceIDToBreakpoints.find(sourceID);
     ASSERT(it != m_sourceIDToBreakpoints.end());
-    LineToBreakpointsMap::iterator breaksIt = it->value.find(breakpoint.line);
+    LineToBreakpointsMap::iterator breaksIt = it->value.find(breakpoint->line);
     ASSERT(breaksIt != it->value.end());
 
-    toggleBreakpoint(breakpoint, BreakpointDisabled);
-
-    BreakpointsInLine& breakpoints = breaksIt->value;
-    unsigned breakpointsCount = breakpoints.size();
-    for (unsigned i = 0; i < breakpointsCount; i++) {
-        if (breakpoints[i].id == breakpoint.id) {
-            breakpoints.remove(i);
-            m_breakpointIDToBreakpoint.remove(idIt);
-
-            if (breakpoints.isEmpty()) {
-                it->value.remove(breaksIt);
-                if (it->value.isEmpty())
-                    m_sourceIDToBreakpoints.remove(it);
-            }
-            break;
-        }
+    toggleBreakpoint(*breakpoint, BreakpointDisabled);
+
+    BreakpointsList& breakpoints = *breaksIt->value;
+#if !ASSERT_DISABLED
+    bool found = false;
+    for (Breakpoint* current = breakpoints.head(); current && !found; current = current->next()) {
+        if (current->id == breakpoint->id)
+            found = true;
+    }
+    ASSERT(found);
+#endif
+
+    m_breakpointIDToBreakpoint.remove(idIt);
+    breakpoints.remove(breakpoint);
+    delete breakpoint;
+
+    if (breakpoints.isEmpty()) {
+        it->value.remove(breaksIt);
+        if (it->value.isEmpty())
+            m_sourceIDToBreakpoints.remove(it);
     }
 }
@@ -437 +442 @@
 
     bool hit = false;
-    const BreakpointsInLine& breakpoints = breaksIt->value;
-    unsigned breakpointsCount = breakpoints.size();
-    unsigned i;
-    for (i = 0; i < breakpointsCount; i++) {
-        unsigned breakLine = breakpoints[i].line;
-        unsigned breakColumn = breakpoints[i].column;
+    const BreakpointsList& breakpoints = *breaksIt->value;
+    Breakpoint* breakpoint;
+    for (breakpoint = breakpoints.head(); breakpoint; breakpoint = breakpoint->next()) {
+        unsigned breakLine = breakpoint->line;
+        unsigned breakColumn = breakpoint->column;
         // Since frontend truncates the indent, the first statement in a line must match the breakpoint (line,0).
         ASSERT(this == m_currentCallFrame->codeBlock()->globalObject()->debugger());
@@ -455 +459 @@
 
     if (hitBreakpoint)
-        *hitBreakpoint = breakpoints[i];
-
-    if (breakpoints[i].condition.isEmpty())
+        *hitBreakpoint = *breakpoint;
+
+    if (breakpoint->condition.isEmpty())
         return true;
 
@@ -466 +470 @@
     JSValue exception;
     DebuggerCallFrame* debuggerCallFrame = currentDebuggerCallFrame();
-    JSValue result = debuggerCallFrame->evaluate(breakpoints[i].condition, exception);
+    JSValue result = debuggerCallFrame->evaluate(breakpoint->condition, exception);
 
     // We can lose the debugger while executing JavaScript.

trunk/Source/JavaScriptCore/debugger/Debugger.h

@@ -30 +30 @@
 #include <wtf/HashSet.h>
 #include <wtf/RefPtr.h>
-#include <wtf/Vector.h>
 #include <wtf/text/TextPosition.h>
 
@@ -129 +128 @@
     typedef HashMap<BreakpointID, Breakpoint*> BreakpointIDToBreakpointMap;
 
-    typedef Vector<Breakpoint> BreakpointsInLine;
-    typedef HashMap<unsigned, BreakpointsInLine, WTF::IntHash<int>, WTF::UnsignedWithZeroKeyHashTraits<int>> LineToBreakpointsMap;
+    typedef HashMap<unsigned, RefPtr<BreakpointsList>, WTF::IntHash<int>, WTF::UnsignedWithZeroKeyHashTraits<int>> LineToBreakpointsMap;
     typedef HashMap<SourceID, LineToBreakpointsMap, WTF::IntHash<SourceID>, WTF::UnsignedWithZeroKeyHashTraits<SourceID>> SourceIDToBreakpointsMap;