Changeset 28106 in webkit for trunk/JavaScriptCore/kjs/collector.cpp

Timestamp:

Nov 28, 2007, 2:08:09 AM (18 years ago)

Author:

[email protected]

Message:

JavaScriptCore:

Reviewed by Darin and Geoff.

• Fixed "Stack overflow crash in JavaScript garbage collector mark pass" ​http://bugs.webkit.org/show_bug.cgi?id=12216

Implement mark stack. This version is not suitable for prime time because it makes a
huge allocation on every collect, and potentially makes marking of detached subtrees
slow. But it is an 0.4% SunSpider speedup even without much tweaking.

The basic approach is to replace mark() methods with
markChildren(MarkStack&) methods. Reachable references are pushed
onto a mark stack (which encapsulates ignoring already-marked
references).

Objects are no longer responsible for actually setting their own
mark bits, the collector does that. This means that for objects on
the number heap we don't have to call markChildren() at all since
we know there aren't any.

The mark phase of collect pushes roots onto the mark stack
and drains it as often as possible.

To make this approach viable requires a constant-size mark stack
and a slow fallback approach for when the stack size is exceeded,
plus optimizations to make the required stack small in common
cases. This should be doable.

• JavaScriptCore.exp: Export new symbols.
• JavaScriptCore.xcodeproj/project.pbxproj: Add new file.
• kjs/collector.cpp: (KJS::Collector::heapAllocate): (KJS::drainMarkStack): Helper for all of the below. (KJS::Collector::markStackObjectsConservatively): Use mark stack. (KJS::Collector::markCurrentThreadConservatively): ditto (KJS::Collector::markOtherThreadConservatively): ditto (KJS::Collector::markProtectedObjects): ditto (KJS::Collector::markMainThreadOnlyObjects): ditto (KJS::Collector::collect): ditto
• kjs/collector.h: (KJS::Collector::cellMayHaveRefs): Helper for MarkStack.

• kjs/MarkStack.h: Added. The actual mark stack implementation. (KJS::MarkStack::push): (KJS::MarkStack::pushAtom): (KJS::MarkStack::pop): (KJS::MarkStack::isEmpty): (KJS::MarkStack::reserveCapacity):

Changed mark() methods to markChildren() methods:

• kjs/ExecState.cpp: (KJS::ExecState::markChildren):
• kjs/ExecState.h:
• kjs/JSWrapperObject.cpp: (KJS::JSWrapperObject::markChildren):
• kjs/JSWrapperObject.h:
• kjs/array_instance.cpp: (KJS::ArrayInstance::markChildren):
• kjs/array_instance.h:
• kjs/bool_object.cpp: (BooleanInstance::markChildren):
• kjs/bool_object.h:
• kjs/error_object.cpp:
• kjs/error_object.h:
• kjs/function.cpp: (KJS::FunctionImp::markChildren): (KJS::Arguments::Arguments): (KJS::Arguments::markChildren): (KJS::ActivationImp::markChildren):
• kjs/function.h:
• kjs/internal.cpp: (KJS::GetterSetterImp::markChildren):
• kjs/interpreter.cpp: (KJS::Interpreter::markRoots):
• kjs/interpreter.h:
• kjs/list.cpp: (KJS::List::markProtectedListsSlowCase):
• kjs/list.h: (KJS::List::markProtectedLists):
• kjs/object.cpp: (KJS::JSObject::markChildren):
• kjs/object.h: (KJS::ScopeChain::markChildren):
• kjs/property_map.cpp: (KJS::PropertyMap::markChildren):
• kjs/property_map.h:
• kjs/scope_chain.h:
• kjs/string_object.cpp: (KJS::StringInstance::markChildren):
• kjs/string_object.h:

JavaScriptGlue:

Reviewed by Darin and Geoff.

Fixups for JavaScriptCore mark stack.

• JSObject.cpp: (JSUserObject::Mark):
• JSObject.h:
• JSValueWrapper.cpp: (JSValueWrapper::JSObjectMark):
• JSValueWrapper.h:
• UserObjectImp.cpp:
• UserObjectImp.h:

WebCore:

Reviewed by Darin and Geoff.

Implement mark stack. This version is not suitable for prime time because it makes a
huge allocation on every collect, and potentially makes marking of detached subtrees
slow. But it is a .2% - .4% speedup even without much tweaking.

I replaced mark() methods with markChildren() as usual. One
optimization that is lost is avoiding walking detached DOM
subtrees more than once to mark them; since marking is not
recursive there's no obvious way to bracket operation on the tree
any more.

• bindings/js/JSDocumentCustom.cpp: (WebCore::JSDocument::markChildren):
• bindings/js/JSNodeCustom.cpp: (WebCore::JSNode::markChildren):
• bindings/js/JSNodeFilterCondition.cpp:
• bindings/js/JSNodeFilterCondition.h:
• bindings/js/JSNodeFilterCustom.cpp: (WebCore::JSNodeFilter::markChildren):
• bindings/js/JSNodeIteratorCustom.cpp: (WebCore::JSNodeIterator::markChildren):
• bindings/js/JSTreeWalkerCustom.cpp: (WebCore::JSTreeWalker::markChildren):
• bindings/js/JSXMLHttpRequest.cpp: (KJS::JSXMLHttpRequest::markChildren):
• bindings/js/JSXMLHttpRequest.h:
• bindings/js/kjs_binding.cpp: (KJS::ScriptInterpreter::markDOMNodesForDocument):
• bindings/js/kjs_binding.h:
• bindings/js/kjs_events.cpp: (WebCore::JSUnprotectedEventListener::markChildren):
• bindings/js/kjs_events.h:
• bindings/js/kjs_window.cpp: (KJS::Window::markChildren):
• bindings/js/kjs_window.h:
• bindings/scripts/CodeGeneratorJS.pm:
• dom/Node.cpp: (WebCore::Node::Node):
• dom/Node.h:
• dom/NodeFilter.h:
• dom/NodeFilterCondition.h:

LayoutTests:

Not reviewed.

• Test cases for "Stack overflow crash in JavaScript garbage collector mark pass" ​http://bugs.webkit.org/show_bug.cgi?id=12216

I have fixed this with the mark stack work.

• fast/js/gc-breadth-2-expected.txt: Added.
• fast/js/gc-breadth-2.html: Added.
• fast/js/gc-breadth-expected.txt: Added.
• fast/js/gc-breadth.html: Added.
• fast/js/gc-depth-expected.txt: Added.
• fast/js/gc-depth.html: Added.
• fast/js/resources/gc-breadth-2.js: Added.
• fast/js/resources/gc-breadth.js: Added.
• fast/js/resources/gc-depth.js: Added.

File:

• trunk/JavaScriptCore/kjs/collector.cpp (modified) (14 diffs)

trunk/JavaScriptCore/kjs/collector.cpp

@@ -27 +27 @@
 #include "internal.h"
 #include "list.h"
+#include "MarkStack.h"
 #include "value.h"
 #include <algorithm>
@@ -278 +279 @@
     targetBlock = (Block*)allocateBlock();
     targetBlock->freeList = targetBlock->cells;
+    if (heapType == PrimaryHeap)
+        targetBlock->mayHaveRefs = 1;
     targetBlockUsedCells = 0;
     heap.blocks[usedBlocks] = (CollectorBlock*)targetBlock;
@@ -480 +483 @@
 #define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
 
-void Collector::markStackObjectsConservatively(void *start, void *end)
+static inline void drainMarkStack(MarkStack& stack)
+{
+    while (!stack.isEmpty())
+        stack.pop()->markChildren(stack);
+}
+
+
+void Collector::markStackObjectsConservatively(MarkStack& stack, void *start, void *end)
 {
   if (start > end) {
@@ -522 +532 @@
                   if (((CollectorCell*)xAsBits)->u.freeCell.zeroIfFree != 0) {
                       JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
-                      if (!imp->marked())
-                          imp->mark();
+                      stack.push(imp);
+                      drainMarkStack(stack);
                   }
                   break;
@@ -534 +544 @@
 }
 
-void Collector::markCurrentThreadConservatively()
+void Collector::markCurrentThreadConservatively(MarkStack& stack)
 {
     // setjmp forces volatile registers onto the stack
@@ -551 +561 @@
     void* stackBase = currentThreadStackBase();
 
-    markStackObjectsConservatively(stackPointer, stackBase);
+    markStackObjectsConservatively(stack, stackPointer, stackBase);
 }
 
@@ -694 +704 @@
 }
 
-void Collector::markOtherThreadConservatively(Thread* thread)
+void Collector::markOtherThreadConservatively(MarkStack& stack, Thread* thread)
 {
   suspendThread(thread->platformThread);
@@ -702 +712 @@
 
   // mark the thread's registers
-  markStackObjectsConservatively((void*)&regs, (void*)((char*)&regs + regSize));
+  markStackObjectsConservatively(stack, (void*)&regs, (void*)((char*)&regs + regSize));
  
   void* stackPointer = otherThreadStackPointer(regs);
   void* stackBase = otherThreadStackBase(regs, thread);
-  markStackObjectsConservatively(stackPointer, stackBase);
+  markStackObjectsConservatively(stack, stackPointer, stackBase);
 
   resumeThread(thread->platformThread);
@@ -713 +723 @@
 #endif
 
-void Collector::markStackObjectsConservatively()
-{
-  markCurrentThreadConservatively();
+void Collector::markStackObjectsConservatively(MarkStack& stack)
+{
+  markCurrentThreadConservatively(stack);
 
 #if USE(MULTIPLE_THREADS)
   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
     if (!pthread_equal(thread->posixThread, pthread_self())) {
-      markOtherThreadConservatively(thread);
+        markOtherThreadConservatively(stack, thread);
     }
   }
@@ -772 +782 @@
 }
 
-void Collector::markProtectedObjects()
+void Collector::markProtectedObjects(MarkStack& stack)
 {
   ProtectCountSet& protectedValues = KJS::protectedValues();
   ProtectCountSet::iterator end = protectedValues.end();
   for (ProtectCountSet::iterator it = protectedValues.begin(); it != end; ++it) {
-    JSCell *val = it->first;
-    if (!val->marked())
-      val->mark();
-  }
-}
-
-void Collector::markMainThreadOnlyObjects()
+    stack.push(it->first);
+    drainMarkStack(stack);
+  }
+}
+
+void Collector::markMainThreadOnlyObjects(MarkStack& stack)
 {
 #if USE(MULTIPLE_THREADS)
@@ -815 +824 @@
                     if (!curBlock->marked.get(i)) {
                         JSCell* imp = reinterpret_cast<JSCell*>(cell);
-                        imp->mark();
+                        stack.push(imp);
+                        drainMarkStack(stack);
                     }
                     if (++count == mainThreadOnlyObjectCount)
@@ -951 +961 @@
   // MARK: first mark all referenced objects recursively starting out from the set of root objects
 
+  size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
+
+  MarkStack stack;
+  stack.reserveCapacity(primaryHeap.numLiveObjects);
+
 #ifndef NDEBUG
   // Forbid malloc during the mark phase. Marking a thread suspends it, so 
-  // a malloc inside mark() would risk a deadlock with a thread that had been 
+  // a malloc inside markChildren() would risk a deadlock with a thread that had been 
   // suspended while holding the malloc lock.
   fastMallocForbid();
@@ -961 +976 @@
     Interpreter* scr = Interpreter::s_hook;
     do {
-      scr->mark();
+      scr->markRoots(stack);
+      drainMarkStack(stack);
       scr = scr->next;
     } while (scr != Interpreter::s_hook);
   }
 
-  markStackObjectsConservatively();
-  markProtectedObjects();
-  List::markProtectedLists();
+  markStackObjectsConservatively(stack);
+  markProtectedObjects(stack);
+  List::markProtectedLists(stack);
+  drainMarkStack(stack);
 #if USE(MULTIPLE_THREADS)
   if (!currentThreadIsMainThread)
-    markMainThreadOnlyObjects();
+    markMainThreadOnlyObjects(stack);
 #endif
 
@@ -978 +995 @@
 #endif
     
-  size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
   size_t numLiveObjects = sweep<PrimaryHeap>(currentThreadIsMainThread);
   numLiveObjects += sweep<NumberHeap>(currentThreadIsMainThread);