Bug (mark-stack) – Stack overflow crash in JavaScript garbage collector mark pass

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[David Carson]

In relation to the bug:
http://bugs.webkit.org/show_bug.cgi?id=3743
If I add two more zeros in the for loop below (taken from the test case for the bug), a stack overflow occurs in the Mark() GC functionality, before it makes it to the ary.toString() call.

var ary=[0];
for(var i=1; i<1000000; i++)
  ary=[ary, i];

shouldThrow("ary.toString()");

It seems that the mac dumps out at a stack depth of 174580 frames.
Below is a copy of the stack dump with the repeating part removed. The current stack overflow protection relies on JS going through the method JSObject::call(). However, as can be seen by the stack dump, it does not go through it. We can check depth in mark() and throw exception. But it implies we will never mark the inner objects and they won't be gc later.


#0	0x0053a957 in KJS::JSImmediate::isImmediate at JSImmediate.h:64
#1	0x0053b0af in KJS::JSValue::downcast at value.h:249
#2	0x0053b240 in KJS::JSValue::marked at value.h:357
#3	0x004e458f in KJS::JSObject::mark at object.cpp:122
#4	0x004ba49f in KJS::ArrayInstance::mark at array_object.cpp:278
#5	0x0053b219 in KJS::JSValue::mark at value.h:352
#6	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
#7	0x0053b219 in KJS::JSValue::mark at value.h:352
#8	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
#9	0x0053b219 in KJS::JSValue::mark at value.h:352
#10	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
....
#174509	0x0053b219 in KJS::JSValue::mark at value.h:352
#174510	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
#174511	0x0053b219 in KJS::JSValue::mark at value.h:352
#174512	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
#174513	0x0053b219 in KJS::JSValue::mark at value.h:352
#174514	0x004ba4fb in KJS::ArrayInstance::mark at array_object.cpp:283
#174515	0x0053b219 in KJS::JSValue::mark at value.h:352
#174516	0x004e7456 in KJS::PropertyMap::mark at property_map.cpp:551
#174517	0x004e45ae in KJS::JSObject::mark at object.cpp:125
#174518	0x012680c7 in KJS::Window::mark at kjs_window.cpp:465
#174519	0x005434ee in KJS::ScopeChain::mark at object.h:596
#174520	0x0052eab4 in KJS::Context::mark at Context.cpp:92
#174521	0x004cb3ae in KJS::Interpreter::mark at interpreter.cpp:657
#174522	0x0124fc10 in KJS::ScriptInterpreter::mark at kjs_binding.cpp:227
#174523	0x004bf45d in KJS::Collector::collect at collector.cpp:474
#174524	0x004bf984 in KJS::Collector::allocate at collector.cpp:123
#174525	0x004f3371 in KJS::JSCell::operator new at value.cpp:41
#174526	0x004baba3 in KJS::ArrayObjectImp::construct at array_object.cpp:960
#174527	0x004dc51f in KJS::ElementNode::evaluate at nodes.cpp:413
#174528	0x004dc38a in KJS::ArrayNode::evaluate at nodes.cpp:438
#174529	0x004dea09 in KJS::AssignResolveNode::evaluate at nodes.cpp:1420
#174530	0x004d836c in KJS::ExprStatementNode::execute at nodes.cpp:1672
#174531	0x004d7484 in KJS::ForNode::execute at nodes.cpp:1819
#174532	0x004d609a in KJS::SourceElementsNode::execute at nodes.cpp:2455
#174533	0x004d489c in KJS::BlockNode::execute at nodes.cpp:1648
#174534	0x004cdec1 in KJS::Interpreter::evaluate at interpreter.cpp:478
#174535	0x01266e9d in WebCore::KJSProxy::evaluate at kjs_proxy.cpp:65
#174536	0x0139d3f5 in WebCore::FrameLoader::executeScript at FrameLoader.cpp:690
#174537	0x0101dc0a in WebCore::HTMLTokenizer::scriptExecution at HTMLTokenizer.cpp:501
#174538	0x010203e8 in WebCore::HTMLTokenizer::scriptHandler at HTMLTokenizer.cpp:451
#174539	0x010208ff in WebCore::HTMLTokenizer::parseSpecial at HTMLTokenizer.cpp:308
#174540	0x0102277c in WebCore::HTMLTokenizer::parseTag at HTMLTokenizer.cpp:1228
#174541	0x01022f84 in WebCore::HTMLTokenizer::write at HTMLTokenizer.cpp:1442
#174542	0x01393302 in WebCore::FrameLoader::write at FrameLoader.cpp:891
#174543	0x0139342b in WebCore::FrameLoader::addData at FrameLoader.cpp:1511
#174544	0x010fbf4f in -[WebCoreFrameBridge addData:] at WebCoreFrameBridge.mm:298
#174545	0x010ff7b6 in -[WebCoreFrameBridge receivedData:textEncodingName:] at WebCoreFrameBridge.mm:1621
#174546	0x00331db1 in -[WebHTMLRepresentation receivedData:withDataSource:] at WebHTMLRepresentation.mm:157
#174547	0x0032c2c7 in -[WebDataSource(WebInternal) _receivedData:] at WebDataSource.mm:175
#174548	0x00394087 in WebFrameLoaderClient::committedLoad at WebFrameLoaderClient.mm:623
#174549	0x0138fedf in WebCore::FrameLoader::committedLoad at FrameLoader.cpp:2861
#174550	0x0139f8d1 in WebCore::DocumentLoader::commitLoad at DocumentLoader.cpp:329
#174551	0x0139f92a in WebCore::DocumentLoader::receivedData at DocumentLoader.cpp:341
#174552	0x0138f35b in WebCore::FrameLoader::receivedData at FrameLoader.cpp:1901
#174553	0x01376078 in WebCore::MainResourceLoader::addData at MainResourceLoaderMac.mm:144
#174554	0x01374e31 in WebCore::ResourceLoader::didReceiveData at ResourceLoaderMac.mm:225
#174555	0x013763ad in WebCore::MainResourceLoader::didReceiveData at MainResourceLoaderMac.mm:314
#174556	0x01374a1e in WebCore::ResourceLoader::didReceiveData at ResourceLoaderMac.mm:385
#174557	0x01383424 in -[WebCoreResourceHandleAsDelegate connection:didReceiveData:lengthReceived:] at ResourceHandleMac.mm:291
#174558	0x9265eb86 in -[NSURLConnection(NSURLConnectionInternal) _sendDidReceiveDataCallback]
#174559	0x9265ce67 in -[NSURLConnection(NSURLConnectionInternal) _sendCallbacks]
#174560	0x9265cb41 in _sendCallbacks
#174561	0x9082afd2 in CFRunLoopRunSpecific
#174562	0x9082ab0e in CFRunLoopRunInMode
#174563	0x9262ddc6 in -[NSRunLoop runMode:beforeDate:]
#174564	0x9267b970 in -[NSRunLoop runUntilDate:]
#174565	0x9352f0c0 in NSCoreDragReceiveProc
#174566	0x917f517d in DoDropMessage
#174567	0x917f633d in CoreDragMessageHandler
#174568	0x90872b7a in __CFMessagePortPerform
#174569	0x9082b66d in CFRunLoopRunSpecific
#174570	0x9082ab0e in CFRunLoopRunInMode
#174571	0x92ddabef in RunCurrentEventLoopInMode
#174572	0x92dda2fd in ReceiveNextEventCommon
#174573	0x92dda154 in BlockUntilNextEventMatchingListInMode
#174574	0x9327f465 in _DPSNextEvent
#174575	0x9327f056 in -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:]
#174576	0x00006cea in ??
#174577	0x93278ddb in -[NSApplication run]
#174578	0x9326cd2f in NSApplicationMain
#174579	0x0005f54a in ??
#174580	0x0005f471 in ??

[David Carson]

Created attachment 12371 [details]
Opening this file _WILL_ cause WebKit to crash

This file shows the crash. Careful clicking on it, as it will cause Safari to crash. Save it to your filesystem before opening.

[Geoffrey Garen]

Reproducible crash => p1.

[Darin Adler]

Clearly we can fix this by changing the marking system to not mark recursively. Instead the mark functions can simply add the items to mark to a vector passed into the mark function, and the caller can then mark those in turn. The tricky part may be doing this efficiently!

[Mark Rowe (bdash)]

<rdar://problem/4928697>

[M.E. O'Neill]

Here's another example, found while playing with ways to work around bug 4045

http://www.cs.hmc.edu/~oneill/cps-sum.html

[Cameron Zwarich (cpst)]

(In reply to comment #3)
> Clearly we can fix this by changing the marking system to not mark recursively.
> Instead the mark functions can simply add the items to mark to a vector passed
> into the mark function, and the caller can then mark those in turn. The tricky
> part may be doing this efficiently!

The only portable way of fixing this that I can see is to essentially convert the marking code to continuation-passing style, so that all temporary storage used during marking is allocated in a few vectors on the heap, and transfer of control between the mark() methods of different cell classes is done using a trampoline. With GCC, one could use tail recursion instead of a trampoline for a slight optimization, but that isn't portable, and doesn't even work with separate compilation in GCC.

Does this sound like a good idea to anyone else? I will gladly implement it if no one has any objections.

[Cameron Zwarich (cpst)]

In my previous comment, I proposed a fix for this bug and said that I didn't see any other portable way of fixing it. Here is another method that is not as portable, but won't require as many changes to existing code as the proposal in my previous comment, and will probably be more efficient, as replacing stack allocation with heap allocation gives a performance hit on modern x86 processors. It also lets you fall back to the existing code with #ifdef if some of the non-portable things are not supported properly.

To avoid the stack overflow, one can implement "segmented stacks" using setjmp() and longjmp(). Before beginning the marking process, malloc a new region to be used as the stack. Construct the proper jmp_buf (this is non-portable) that uses this new region as a stack and longjmp() to it. Now, every time you are going to call another method, double check that you have enough stack space left by whatever method you would like (calling the usual functions to get the stack pointer, comparing pointers, or checking SP with some inline assembly). If you don't, allocate a new region of memory to be used as a stack, dump a setjmp() into the beginning of it, manufacture another jmp_buf that uses this region as a stack, and then resume business as usual. When the other method returns, free the new stack you allocated, and longjmp() back to where you were. You don't even need to do this every method call, only once whenever another method call from the current method call could possibly overflow the stack. Of course, if you know the size of the usual stack, you could avoid the initial allocation.

This does kill any chance of using C++ exceptions in the new stack, but it will probably be a lot more efficient than using continuation-passing style. Beyond a stack comparison and a branch that will likely be predicted properly, it only kicks in when the stack overflows, whereas with CPS you always take a bit of a hit in order to handle the unusual case.

[Maciej Stachowiak]

Created attachment 17110 [details]
incomplete patch that uses an explicit mark stack - this is actually a speedup

[Maciej Stachowiak]

Comment on attachment 17110 [details]
incomplete patch that uses an explicit mark stack - this is actually a speedup

I didn't mean to flag this for review.

[Maciej Stachowiak]

Created attachment 17544 [details]
[1/4]         Not reviewed.


        Fix DumpRenderTree ObjC bug comparing strings.

        * DumpRenderTree/mac/ObjCController.m:
        (-[ObjCController identityIsEqual::]): Compare strings with string
        equality instead of identiy equality.
---
 WebKitTools/ChangeLog                           |   13 +++++++++++++
 WebKitTools/DumpRenderTree/mac/ObjCController.m |    2 ++
 2 files changed, 15 insertions(+), 0 deletions(-)

[Maciej Stachowiak]

Created attachment 17545 [details]
[2/4] JavaScriptCore:


        Not reviewed.

        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.

        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:
        * JavaScriptCore.xcodeproj/project.pbxproj:
        * 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/collector.cpp:
        (KJS::Collector::heapAllocate):
        (KJS::drainMarkStack):
        (KJS::Collector::markStackObjectsConservatively):
        (KJS::Collector::markCurrentThreadConservatively):
        (KJS::Collector::markOtherThreadConservatively):
        (KJS::Collector::markProtectedObjects):
        (KJS::Collector::markMainThreadOnlyObjects):
        (KJS::Collector::collect):
        * kjs/collector.h:
        (KJS::Collector::cellMayHaveRefs):
        * 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:
        * kjs/value.h:
        (KJS::JSValue::markChildren):

JavaScriptGlue:

        Not reviewed.

        Fixups for JavaScriptCore mark stack.

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

WebCore:

        Not reviewed.

        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:

        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.

        Not reviewed.

        Add the actual mark stack. Forgot to include this in my original commit.

        * kjs/MarkStack.h: Added.
        (KJS::MarkStack::push):
        (KJS::MarkStack::pushAtom):
        (KJS::MarkStack::pop):
        (KJS::MarkStack::isEmpty):
        (KJS::MarkStack::reserveCapacity):

        Not reviewed.

        - remove over-optimistic assert

        * kjs/value.h:
---
 JavaScriptCore/ChangeLog                           |  168 ++++++++++++++
 JavaScriptCore/JavaScriptCore.exp                  |    9 +-
 .../JavaScriptCore.xcodeproj/project.pbxproj       |    4 +
 JavaScriptCore/kjs/ExecState.cpp                   |    4 +-
 JavaScriptCore/kjs/ExecState.h                     |    2 +-
 JavaScriptCore/kjs/JSWrapperObject.cpp             |    7 +-
 JavaScriptCore/kjs/JSWrapperObject.h               |    8 +-
 JavaScriptCore/kjs/MarkStack.h                     |  229 ++++++++++++++++++++
 JavaScriptCore/kjs/array_instance.cpp              |   17 +-
 JavaScriptCore/kjs/array_instance.h                |    2 +-
 JavaScriptCore/kjs/bool_object.cpp                 |   19 +-
 JavaScriptCore/kjs/bool_object.h                   |    3 +-
 JavaScriptCore/kjs/collector.cpp                   |   64 ++++--
 JavaScriptCore/kjs/collector.h                     |   25 ++-
 JavaScriptCore/kjs/date_object.cpp                 |   13 +-
 JavaScriptCore/kjs/date_object.h                   |    6 +-
 JavaScriptCore/kjs/error_object.cpp                |    6 -
 JavaScriptCore/kjs/error_object.h                  |    2 -
 JavaScriptCore/kjs/function.cpp                    |   39 ++--
 JavaScriptCore/kjs/function.h                      |    6 +-
 JavaScriptCore/kjs/internal.cpp                    |   12 +-
 JavaScriptCore/kjs/interpreter.cpp                 |  144 ++++++------
 JavaScriptCore/kjs/interpreter.h                   |    2 +-
 JavaScriptCore/kjs/list.cpp                        |    9 +-
 JavaScriptCore/kjs/list.h                          |    6 +-
 JavaScriptCore/kjs/number_object.cpp               |   16 +-
 JavaScriptCore/kjs/number_object.h                 |    4 +-
 JavaScriptCore/kjs/object.cpp                      |   11 +-
 JavaScriptCore/kjs/object.h                        |   14 +-
 JavaScriptCore/kjs/property_map.cpp                |   16 +-
 JavaScriptCore/kjs/property_map.h                  |    3 +-
 JavaScriptCore/kjs/scope_chain.h                   |    2 +-
 JavaScriptCore/kjs/string_object.cpp               |   38 ++--
 JavaScriptCore/kjs/string_object.h                 |   12 +-
 JavaScriptCore/kjs/value.h                         |   15 +-
 JavaScriptGlue/ChangeLog                           |   15 ++
 JavaScriptGlue/JSObject.cpp                        |    4 +-
 JavaScriptGlue/JSObject.h                          |    4 +-
 JavaScriptGlue/JSValueWrapper.cpp                  |    4 +-
 JavaScriptGlue/JSValueWrapper.h                    |    2 +-
 JavaScriptGlue/UserObjectImp.cpp                   |    6 +-
 JavaScriptGlue/UserObjectImp.h                     |    2 +-
 LayoutTests/ChangeLog                              |   19 ++
 LayoutTests/fast/js/gc-breadth-2-expected.txt      |    9 +
 LayoutTests/fast/js/gc-breadth-2.html              |   13 ++
 LayoutTests/fast/js/gc-breadth-expected.txt        |    9 +
 LayoutTests/fast/js/gc-breadth.html                |   13 ++
 LayoutTests/fast/js/gc-depth-expected.txt          |    9 +
 LayoutTests/fast/js/gc-depth.html                  |   13 ++
 LayoutTests/fast/js/resources/gc-breadth-2.js      |   13 ++
 LayoutTests/fast/js/resources/gc-breadth.js        |   13 ++
 LayoutTests/fast/js/resources/gc-depth.js          |   13 ++
 WebCore/ChangeLog                                  |   56 +++++
 .../bindings/js/JSCSSStyleDeclarationCustom.cpp    |    2 +-
 WebCore/bindings/js/JSDocumentCustom.cpp           |    6 +-
 WebCore/bindings/js/JSNodeCustom.cpp               |   33 +---
 WebCore/bindings/js/JSNodeFilterCondition.cpp      |    4 +-
 WebCore/bindings/js/JSNodeFilterCondition.h        |    2 +-
 WebCore/bindings/js/JSNodeFilterCustom.cpp         |    6 +-
 WebCore/bindings/js/JSNodeIteratorCustom.cpp       |    6 +-
 WebCore/bindings/js/JSTreeWalkerCustom.cpp         |    6 +-
 WebCore/bindings/js/JSXMLHttpRequest.cpp           |   10 +-
 WebCore/bindings/js/JSXMLHttpRequest.h             |    2 +-
 WebCore/bindings/js/kjs_binding.cpp                |    8 +-
 WebCore/bindings/js/kjs_binding.h                  |    2 +-
 WebCore/bindings/js/kjs_events.cpp                 |    6 +-
 WebCore/bindings/js/kjs_events.h                   |    2 +-
 WebCore/bindings/js/kjs_window.cpp                 |    8 +-
 WebCore/bindings/js/kjs_window.h                   |    2 +-
 WebCore/bindings/scripts/CodeGeneratorJS.pm        |    2 +-
 WebCore/dom/Node.cpp                               |    3 +-
 WebCore/dom/Node.h                                 |    4 +-
 WebCore/dom/NodeFilter.h                           |    6 +-
 WebCore/dom/NodeFilterCondition.h                  |    6 +-
 74 files changed, 919 insertions(+), 361 deletions(-)

[Maciej Stachowiak]

Created attachment 17546 [details]
[3/4]         Not reviewed.


        - push large PropertyMaps as ranges too

        This seems to be a wash on SunSpider.

        The high-water mark for the stack on the SunSpider benchmark goes
        from 1979 to 220.

        * kjs/MarkStack.h:
        (KJS::RangeTag): Tempate class to aid tagging both JSValue** and PropertyMap*
        ranges.
        (KJS::MarkStack::getValue): Overloaded helper for newly templatized
        algorithms.
        (KJS::MarkStack::safeToAccess): ditto
        (KJS::MarkStack::advanceRangeStartToCellWithRefs): Templatized.
        (KJS::MarkStack::pushWholeRange): ditto
        (KJS::MarkStack::pushOneItemAndAdvance): ditto
        (KJS::MarkStack::advanceUntil126ItemsPushed): ditto
        (KJS::MarkStack::pushRange): ditto
        (KJS::MarkStack::pop): Handle both kinds of ranges now.
        * kjs/property_map.cpp:
        (KJS::PropertyMap::markChildren): Use pushRanges.
        * kjs/property_map.h:
        (KJS::PropertyMapEntry::PropertyMapEntry): Made this public in the header.
---
 JavaScriptCore/ChangeLog            |   28 ++++++++++
 JavaScriptCore/kjs/MarkStack.h      |   98 ++++++++++++++++++++++++++---------
 JavaScriptCore/kjs/property_map.cpp |   16 +-----
 JavaScriptCore/kjs/property_map.h   |   13 ++++-
 4 files changed, 116 insertions(+), 39 deletions(-)

[Maciej Stachowiak]

Created attachment 17547 [details]
[4/4] JavaScriptCore:


        Not reviewed.

        Use a fixed-size mark stack so that we don't trigger huge
        allocations when garbage collecting. In the unlikely case of
        overflowing the mark stack, use a slow fallback path where we
        crawl the whole heap, looking for objects with the mark bit set
        and pushing their children.

        This is an 0.2% SunSpider speedup (but in retrospect I'm not sure
        the last patch was a speedup).

        * kjs/JSLock.cpp:
        (KJS::JSLock::registerThread):
        * kjs/MarkStack.h:
        (KJS::MarkStack::append):
        (KJS::MarkStack::push):
        (KJS::MarkStack::pushOneItemAndAdvance):
        (KJS::MarkStack::advanceUntil126ItemsPushed):
        (KJS::MarkStack::pushRange):
        (KJS::MarkStack::pop):
        (KJS::MarkStack::reset):
        (KJS::MarkStack::size):
        (KJS::MarkStack::overflowed):
        * kjs/collector.cpp:
        (KJS::):
        (KJS::initializeRegisteredThreadKey):
        (KJS::Collector::registerThread):
        (KJS::slowFallbackMarkIfNeeded):
        (KJS::Collector::collect):

LayoutTests:

        Not reviewed.

        - Test case that hits the worst case of range stack marking, to ensure that the slow
        fallback path has coverage.

        * fast/js/gc-pathological-expected.txt: Added.
        * fast/js/gc-pathological.html: Added.
        * fast/js/resources/gc-pathological.js: Added.
---
 JavaScriptCore/ChangeLog                         |   32 +++++++++++
 JavaScriptCore/kjs/JSLock.cpp                    |   14 ++---
 JavaScriptCore/kjs/MarkStack.h                   |   46 +++++++++++-----
 JavaScriptCore/kjs/collector.cpp                 |   64 +++++++++++++++++++---
 LayoutTests/ChangeLog                            |   11 ++++
 LayoutTests/fast/js/gc-pathological-expected.txt |    9 +++
 LayoutTests/fast/js/gc-pathological.html         |   13 +++++
 LayoutTests/fast/js/resources/gc-pathological.js |   25 +++++++++
 8 files changed, 183 insertions(+), 31 deletions(-)

[Maciej Stachowiak]

Created attachment 17548 [details]
[1/6]         Not reviewed.


        Fix DumpRenderTree ObjC bug comparing strings.

        * DumpRenderTree/mac/ObjCController.m:
        (-[ObjCController identityIsEqual::]): Compare strings with string
        equality instead of identiy equality.
---
 WebKitTools/ChangeLog                           |   13 ++++++++++++-
 WebKitTools/DumpRenderTree/mac/ObjCController.m |    2 ++
 2 files changed, 14 insertions(+), 1 deletions(-)

[Maciej Stachowiak]

Created attachment 17549 [details]
[2/6] JavaScriptCore:


        Not reviewed.

        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.

        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:
        * JavaScriptCore.xcodeproj/project.pbxproj:
        * 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/collector.cpp:
        (KJS::Collector::heapAllocate):
        (KJS::drainMarkStack):
        (KJS::Collector::markStackObjectsConservatively):
        (KJS::Collector::markCurrentThreadConservatively):
        (KJS::Collector::markOtherThreadConservatively):
        (KJS::Collector::markProtectedObjects):
        (KJS::Collector::markMainThreadOnlyObjects):
        (KJS::Collector::collect):
        * kjs/collector.h:
        (KJS::Collector::cellMayHaveRefs):
        * 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:
        * kjs/value.h:
        (KJS::JSValue::markChildren):

JavaScriptGlue:

        Not reviewed.

        Fixups for JavaScriptCore mark stack.

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

WebCore:

        Not reviewed.

        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:

        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.

        Not reviewed.

        Add the actual mark stack. Forgot to include this in my original commit.

        * kjs/MarkStack.h: Added.
        (KJS::MarkStack::push):
        (KJS::MarkStack::pushAtom):
        (KJS::MarkStack::pop):
        (KJS::MarkStack::isEmpty):
        (KJS::MarkStack::reserveCapacity):

        Not reviewed.

        - remove over-optimistic assert

        * kjs/value.h:
---
 JavaScriptCore/ChangeLog                           |   93 +++++++++++++
 JavaScriptCore/JavaScriptCore.exp                  |    6 +-
 .../JavaScriptCore.xcodeproj/project.pbxproj       |    4 +
 JavaScriptCore/kjs/ExecState.cpp                   |    4 +-
 JavaScriptCore/kjs/ExecState.h                     |    2 +-
 JavaScriptCore/kjs/JSWrapperObject.cpp             |    7 +-
 JavaScriptCore/kjs/JSWrapperObject.h               |    4 +-
 JavaScriptCore/kjs/MarkStack.h                     |   96 +++++++++++++
 JavaScriptCore/kjs/array_instance.cpp              |   15 +--
 JavaScriptCore/kjs/array_instance.h                |    2 +-
 JavaScriptCore/kjs/bool_object.cpp                 |    6 +
 JavaScriptCore/kjs/bool_object.h                   |    1 +
 JavaScriptCore/kjs/collector.cpp                   |   64 ++++++----
 JavaScriptCore/kjs/collector.h                     |   25 +++-
 JavaScriptCore/kjs/error_object.cpp                |    6 -
 JavaScriptCore/kjs/error_object.h                  |    2 -
 JavaScriptCore/kjs/function.cpp                    |   39 ++---
 JavaScriptCore/kjs/function.h                      |    6 +-
 JavaScriptCore/kjs/internal.cpp                    |   12 +-
 JavaScriptCore/kjs/interpreter.cpp                 |  144 ++++++++++----------
 JavaScriptCore/kjs/interpreter.h                   |    2 +-
 JavaScriptCore/kjs/list.cpp                        |    9 +-
 JavaScriptCore/kjs/list.h                          |    6 +-
 JavaScriptCore/kjs/object.cpp                      |   11 +-
 JavaScriptCore/kjs/object.h                        |   14 +-
 JavaScriptCore/kjs/property_map.cpp                |   16 +--
 JavaScriptCore/kjs/property_map.h                  |    3 +-
 JavaScriptCore/kjs/scope_chain.h                   |    2 +-
 JavaScriptCore/kjs/string_object.cpp               |    6 +
 JavaScriptCore/kjs/string_object.h                 |    1 +
 JavaScriptCore/kjs/value.h                         |   15 +-
 JavaScriptGlue/ChangeLog                           |   15 ++
 JavaScriptGlue/JSObject.cpp                        |    4 +-
 JavaScriptGlue/JSObject.h                          |    4 +-
 JavaScriptGlue/JSValueWrapper.cpp                  |    4 +-
 JavaScriptGlue/JSValueWrapper.h                    |    2 +-
 JavaScriptGlue/UserObjectImp.cpp                   |    6 +-
 JavaScriptGlue/UserObjectImp.h                     |    2 +-
 LayoutTests/ChangeLog                              |   19 +++
 LayoutTests/fast/js/gc-breadth-2-expected.txt      |    9 ++
 LayoutTests/fast/js/gc-breadth-2.html              |   13 ++
 LayoutTests/fast/js/gc-breadth-expected.txt        |    9 ++
 LayoutTests/fast/js/gc-breadth.html                |   13 ++
 LayoutTests/fast/js/gc-depth-expected.txt          |    9 ++
 LayoutTests/fast/js/gc-depth.html                  |   13 ++
 LayoutTests/fast/js/resources/gc-breadth-2.js      |   13 ++
 LayoutTests/fast/js/resources/gc-breadth.js        |   13 ++
 LayoutTests/fast/js/resources/gc-depth.js          |   13 ++
 WebCore/ChangeLog                                  |   45 ++++++
 WebCore/bindings/js/JSDocumentCustom.cpp           |    6 +-
 WebCore/bindings/js/JSNodeCustom.cpp               |   33 +----
 WebCore/bindings/js/JSNodeFilterCondition.cpp      |    4 +-
 WebCore/bindings/js/JSNodeFilterCondition.h        |    2 +-
 WebCore/bindings/js/JSNodeFilterCustom.cpp         |    6 +-
 WebCore/bindings/js/JSNodeIteratorCustom.cpp       |    6 +-
 WebCore/bindings/js/JSTreeWalkerCustom.cpp         |    6 +-
 WebCore/bindings/js/JSXMLHttpRequest.cpp           |   10 +-
 WebCore/bindings/js/JSXMLHttpRequest.h             |    2 +-
 WebCore/bindings/js/kjs_binding.cpp                |    8 +-
 WebCore/bindings/js/kjs_binding.h                  |    2 +-
 WebCore/bindings/js/kjs_events.cpp                 |    6 +-
 WebCore/bindings/js/kjs_events.h                   |    2 +-
 WebCore/bindings/js/kjs_window.cpp                 |    8 +-
 WebCore/bindings/js/kjs_window.h                   |    2 +-
 WebCore/bindings/scripts/CodeGeneratorJS.pm        |    2 +-
 WebCore/dom/Node.cpp                               |    3 +-
 WebCore/dom/Node.h                                 |    4 +-
 WebCore/dom/NodeFilter.h                           |    6 +-
 WebCore/dom/NodeFilterCondition.h                  |    6 +-
 69 files changed, 661 insertions(+), 292 deletions(-)

[Maciej Stachowiak]

Created attachment 17550 [details]
[3/6] JavaScriptCore:


        Not reviewed.

        Change things around so JSWrapperObject takes the internal value
        as a constructor argument, instead of initially filling in
        jsUndefined(). Plus corresponding cleanup.

        * JavaScriptCore.exp:
        * kjs/JSWrapperObject.h:
        * kjs/bool_object.cpp:
        (BooleanPrototype::BooleanPrototype):
        (BooleanObjectImp::construct):
        * kjs/bool_object.h:
        * kjs/date_object.cpp:
        (KJS::DateObjectImp::construct):
        * kjs/date_object.h:
        * kjs/number_object.cpp:
        (NumberPrototype::NumberPrototype):
        (NumberObjectImp::construct):
        * kjs/number_object.h:
        * kjs/string_object.cpp:
        (KJS::StringInstance::StringInstance):
        (KJS::StringObjectImp::construct):
        * kjs/string_object.h:

WebCore:

        Not reviewed.

        Change things around so JSWrapperObject takes the internal value
        as a constructor argument, instead of initially filling in
        jsUndefined(). Plus corresponding cleanup.

        * bindings/js/JSCSSStyleDeclarationCustom.cpp:
        (WebCore::JSCSSStyleDeclaration::nameGetter):
---
 JavaScriptCore/ChangeLog                           |   26 ++++++++++++++++
 JavaScriptCore/JavaScriptCore.exp                  |    3 +-
 JavaScriptCore/kjs/JSWrapperObject.h               |    6 ++--
 JavaScriptCore/kjs/bool_object.cpp                 |   13 ++-----
 JavaScriptCore/kjs/bool_object.h                   |    2 +-
 JavaScriptCore/kjs/date_object.cpp                 |   13 +++-----
 JavaScriptCore/kjs/date_object.h                   |    6 ++-
 JavaScriptCore/kjs/number_object.cpp               |   16 +++-------
 JavaScriptCore/kjs/number_object.h                 |    4 +-
 JavaScriptCore/kjs/string_object.cpp               |   32 ++++++-------------
 JavaScriptCore/kjs/string_object.h                 |   11 +++----
 WebCore/ChangeLog                                  |   11 +++++++
 .../bindings/js/JSCSSStyleDeclarationCustom.cpp    |    2 +-
 13 files changed, 78 insertions(+), 67 deletions(-)

[Maciej Stachowiak]

Created attachment 17551 [details]
[4/6]         Not reviewed.


        - push ranges onto the stack to avoid making a huge mark stack for large arrays.

        This is an 0.6% SunSpider speedup (baseline for this branch being
        about on par with trunk).

        This patch lowers the high-water mark for the most array-intensive tests from
        2687 to 316. Unfortunately, the unpack-code test creates a very large object and
        has a high-water mark of 1979.

        We need to get the high-water mark as low as possible so that we
        can use a fixed-size mark stack with a slow fallback algorithm for
        the rare cases that it fails.

        Remaining open-ended storages that can blow out the mark stack include:

        - PropertyMap
        - LocalStorage
        - SparseArrayValueMap

        Somewhat annoyingly, each has different rules for traversal. Only
        the PropertyMap seems likely to get huge in relatively common
        cases so the next step will be to take care of that.

        * kjs/MarkStack.h:
        (KJS::MarkStack::push): Define this as a separate inline outside of the class
        declaration.
        (KJS::MarkStack::pushAtom): ditto
        (KJS::MarkStack::isEmpty): ditto
        (KJS::MarkStack::reserveCapacity): ditto

        (KJS::MarkStack::pushRange): New function to handle pushing a
        range. For small enough ranges or ranges that only contain known
        atomic values, they are handled immediately. Bigger ranges are saved on
        the stack and only the first chunk is pushed.

        (KJS::MarkStack::pop): Accomodate the possibility of ranges on the
        stack. We handle this by pulling out the range, repushing it, and then
        popping.

        (KJS::MarkStack::size): Added. Useful for debugging.
        (KJS::MarkStack::advanceRangeStartToCellWithRefs): Helper for
        pushRange
        (KJS::MarkStack::pushWholeRange): ditto
        (KJS::MarkStack::pushOneItemAndAdvance): ditto
        (KJS::MarkStack::advanceUntil126ItemsPushed): ditto
        * kjs/array_instance.cpp:
        (KJS::ArrayInstance::markChildren): Use pushRange.
---
 JavaScriptCore/ChangeLog              |  112 ++++++++++++++++
 JavaScriptCore/kjs/MarkStack.h        |  227 ++++++++++++++++++++++++++-------
 JavaScriptCore/kjs/array_instance.cpp |    6 +-
 3 files changed, 293 insertions(+), 52 deletions(-)

[Maciej Stachowiak]

Created attachment 17552 [details]
[5/6]         Not reviewed.


        - push large PropertyMaps as ranges too

        This appears to be a wash on SunSpider.

        The high-water mark for the stack on the SunSpider benchmark goes
        from 1979 to 220.

        * kjs/MarkStack.h:
        (KJS::RangeTag): Tempate class to aid tagging both JSValue** and PropertyMap*
        ranges.
        (KJS::MarkStack::getValue): Overloaded helper for newly templatized
        algorithms.
        (KJS::MarkStack::safeToAccess): ditto
        (KJS::MarkStack::advanceRangeStartToCellWithRefs): Templatized.
        (KJS::MarkStack::pushWholeRange): ditto
        (KJS::MarkStack::pushOneItemAndAdvance): ditto
        (KJS::MarkStack::advanceUntil126ItemsPushed): ditto
        (KJS::MarkStack::pushRange): ditto
        (KJS::MarkStack::pop): Handle both kinds of ranges now.
        * kjs/property_map.cpp:
        (KJS::PropertyMap::markChildren): Use pushRanges.
        * kjs/property_map.h:
        (KJS::PropertyMapEntry::PropertyMapEntry): Made this public in the header.
---
 JavaScriptCore/ChangeLog            |   40 +++++++++++----
 JavaScriptCore/kjs/MarkStack.h      |   98 ++++++++++++++++++++++++++---------
 JavaScriptCore/kjs/property_map.cpp |   16 +-----
 JavaScriptCore/kjs/property_map.h   |   13 ++++-
 4 files changed, 118 insertions(+), 49 deletions(-)

[Maciej Stachowiak]

Created attachment 17553 [details]
[6/6] JavaScriptCore:


        Not reviewed.

        Use a fixed-size mark stack so that we don't trigger huge
        allocations when garbage collecting. In the unlikely case of
        overflowing the mark stack, use a slow fallback path where we
        crawl the whole heap, looking for objects with the mark bit set
        and pushing their children.

        This is an 0.2% SunSpider speedup (but in retrospect I'm not sure
        the last patch was a speedup).

        * kjs/JSLock.cpp:
        (KJS::JSLock::registerThread):
        * kjs/MarkStack.h:
        (KJS::MarkStack::append):
        (KJS::MarkStack::push):
        (KJS::MarkStack::pushOneItemAndAdvance):
        (KJS::MarkStack::advanceUntil126ItemsPushed):
        (KJS::MarkStack::pushRange):
        (KJS::MarkStack::pop):
        (KJS::MarkStack::reset):
        (KJS::MarkStack::size):
        (KJS::MarkStack::overflowed):
        * kjs/collector.cpp:
        (KJS::):
        (KJS::initializeRegisteredThreadKey):
        (KJS::Collector::registerThread):
        (KJS::slowFallbackMarkIfNeeded):
        (KJS::Collector::collect):

LayoutTests:

        Not reviewed.

        - Test case that hits the worst case of range stack marking, to ensure that the slow
        fallback path has coverage.

        * fast/js/gc-pathological-expected.txt: Added.
        * fast/js/gc-pathological.html: Added.
        * fast/js/resources/gc-pathological.js: Added.
---
 JavaScriptCore/ChangeLog                         |   31 +++++++++++
 JavaScriptCore/kjs/JSLock.cpp                    |   14 ++---
 JavaScriptCore/kjs/MarkStack.h                   |   46 +++++++++++-----
 JavaScriptCore/kjs/collector.cpp                 |   64 +++++++++++++++++++---
 LayoutTests/ChangeLog                            |   11 ++++
 LayoutTests/fast/js/gc-pathological-expected.txt |    9 +++
 LayoutTests/fast/js/gc-pathological.html         |   13 +++++
 LayoutTests/fast/js/resources/gc-pathological.js |   25 +++++++++
 8 files changed, 182 insertions(+), 31 deletions(-)

[Maciej Stachowiak]

Comment on attachment 17548 [details]
[1/6]         Not reviewed.

I'll fix the bogus ChangeLog changes when I actually commit this.

[Darin Adler]

Comment on attachment 17548 [details]
[1/6]         Not reviewed.

Looks like ChangeLog was merged incorrectly.

r=me

[Darin Adler]

Comment on attachment 17549 [details]
[2/6] JavaScriptCore:

Do we really need BooleanInstance::markChildren? Seems like it does no good and just makes things a little slower.

 35     virtual void markChildren(MarkStack& stack);

I'd prefer to not name the argument in declarations like these.

I think the variable name "stack" is confusing in the context of the Collector class, where we have something else called stackPointer and stackBase. Maybe in some cases you should just use the name markStack.

r=me

[Darin Adler]

Comment on attachment 17550 [details]
[3/6] JavaScriptCore:

r=me -- no clear on how this relates to the other patches here

[Darin Adler]

Comment on attachment 17551 [details]
[4/6]         Not reviewed.

Looks like the ChangeLog has some duplication in it.

 34         void push(JSValue* value);
 35         void push(JSCell* cell);

 38         void pushAtom(JSValue* value);
 39         void pushAtom(JSCell* cell);

 47         void reserveCapacity(size_t size);

No need to name the arguments here.

 45         bool isEmpty();
 46         size_t size();

These should be const.

I'd slightly prefer for loops for these:

 101         while (start != end) {
...
 109             ++start;

I can read them better than a while with a ++.

 155         // after processing arange on the stack there is always at

Missing space in "arange".

r=me

[Darin Adler]

Comment on attachment 17552 [details]
[5/6]         Not reviewed.

 7         This seems tobe a wash on SunSpider.

Missing space here.

 42         // used to push JSValue** or PopertyMapEntry* ranges

Missing "r" here.

I'm concerned that the change to property_map.h might cause a compilation failure on platforms that don't compile all at once. You may need to move an include from the .cpp to the .h.

r=me

[Darin Adler]

Comment on attachment 17553 [details]
[6/6] JavaScriptCore:

 50         bool overflowed();

Should be const.

All the places that use markStack.storage could probably just use markStack -- all that matters is that the size is large enough and aligned appropriately, you don't have to use the array inside the union.

r=me

[Sam Weinig]

The license in MarkStack.h is LGPL, I think we should make it BSD.

[Geoffrey Garen]

Comment on attachment 17548 [details]
[1/6]         Not reviewed.

a and b here should probably be given the type "id" instead of "WebScriptObject", if we don't know what actual type they'll have.

[Geoffrey Garen]

Comment on attachment 17549 [details]
[2/6] JavaScriptCore:

"getChildren" might be a better name than "markChildren" since the function doesn't actually do the marking -- it only pushes the children onto a stack.

[Geoffrey Garen]

Comment on attachment 17550 [details]
[3/6] JavaScriptCore:

+        ASSERT(m_stack.size() < m_stack.capacity());
+        m_stack.uncheckedAppend(cell);

You can remove the ASSERT here and elsewhere; uncheckedAppend does that already.

[Geoffrey Garen]

Comment on attachment 17552 [details]
[5/6]         Not reviewed.

-            startSlot = reinterpret_cast<JSCell*>(reinterpret_cast<uintptr_t>(start) | 1);
+            startSlot = reinterpret_cast<JSCell*>(reinterpret_cast<uintptr_t>(start) | RangeTag<T>::m_tag);
             return;

+            JSValue** start = reinterpret_cast<JSValue**>(reinterpret_cast<uintptr_t>(cell) & ~3L);
+            JSValue** end = reinterpret_cast<JSValue**>(m_stack.last());
+            m_stack.removeLast();

I think it would help readability to encapsulate the bit shifting here into inline "tag" and "untag" functions, as we do in JSImmediate.

[Geoffrey Garen]

Comment on attachment 17553 [details]
[6/6] JavaScriptCore:

+    inline void MarkStack::reset() 
     {
-        m_stack.reserveCapacity(size);
+        m_stack.reserveCapacity(512);
+        m_overflowed = false;
     }

Calling reserveCapacity doesn't shrink the Vector's buffer once it has grown. So, if a single mark pass overflows big-time, the MarkStack will remain huge for the lifetime of the process. Is that a problem? Do we want to explicitly shrink the Vector's buffer instead?

[Maciej Stachowiak]

Comment on attachment 17548 [details]
[1/6]         Not reviewed.

I landed this patch with the ChangeLog fixed.

[Darin Adler]

Maciej, is this bug fixed yet? Why is it still open? It's showing up in the "patches to commit" queue.

[Mark Rowe (bdash)]

*** Bug 20076 has been marked as a duplicate of this bug. ***

[Oliver Hunt]

Created attachment 34331 [details]
JSC portion of fix

[Oliver Hunt]

Created attachment 34332 [details]
JavaScriptGlue

[Oliver Hunt]

Created attachment 34333 [details]
WebCore portion

[Oliver Hunt]

Created attachment 34334 [details]
Layout test

[Oliver Hunt]

Comment on attachment 34331 [details]
JSC portion of fix

Removing r? flag from the jsc portion, as it is not the final version (i have some style tweaks and a bug fix that i hadn't committed locally so i achieved patch creation fail).

[Oliver Hunt]

Created attachment 34344 [details]
Shorter layout test

[Oliver Hunt]

Created attachment 34345 [details]
JavaScriptCore portion

[Sam Weinig]

Comment on attachment 34344 [details]
Shorter layout test

> +
> +successfullyParsed = true;
> \ No newline at end of file

You need a newline.

[Oliver Hunt]

Created attachment 34351 [details]
JavaScriptCore portion

[Eric Seidel (no email)]

Comment on attachment 34351 [details]
JavaScriptCore portion

This change is not explained in the ChangeLog:
51  OTHER_CFLAGS_normal_GCC_42 = -fomit-frame-pointer -funwind-tables;
 51 OTHER_CFLAGS_normal_GCC_42 = -funwind-tables;

Style:
 383     inline void MarkStack::drain() {

I don't understand this part of the change:
123     , propertyNameIteratorStructure(JSPropertyNameIterator::createStructure(jsNull()))
 124     , getterSetterStructure(GetterSetter::createStructure(jsNull()))

These parts don't seem explained in the ChangeLog.


Space:
namespace JSC {
 33 void* MarkStack::allocateStack(size_t size)

Regarding the rest of the substance of the change, it looks fine.  I think you'll probably want a more regular JSC contributer to look at this though.  If it's still up for review come monday, I'm happy to take a second look and r+ it for you.

My primary complaint as this patch stands is that the ChangeLog needs more explanation of what you're doing, particularly the two changes I highlighted above (compile flags and the structures strored off of GlobalData).

[Oliver Hunt]

(In reply to comment #45)
> (From update of attachment 34351 [details])
> This change is not explained in the ChangeLog:
> 51  OTHER_CFLAGS_normal_GCC_42 = -fomit-frame-pointer -funwind-tables;
>  51 OTHER_CFLAGS_normal_GCC_42 = -funwind-tables;

Yeah, fixed locally already.

> Style:
>  383     inline void MarkStack::drain() {
Goddammit

[Gavin Barraclough]

Comment on attachment 34351 [details]
JavaScriptCore portion

Please comment CompoundType.

[Oliver Hunt]

Committed in r47022

[Eric Seidel (no email)]

No updates in 11 days.  I assume these are all landed, but I'll leave Oliver to confirm that and close the bug.

[Oliver Hunt]

This has been fixed, but the fixeration got eaten by the great bugzilla disaster of '09