Bug 12216 - (mark-stack) Stack overflow crash in JavaScript garbage collector mark pass
(mark-stack)
: Stack overflow crash in JavaScript garbage collector mark pass
Status: RESOLVED FIXED
: WebKit
JavaScriptCore
: 420+
: Macintosh Mac OS X 10.4
: P1 Critical
Assigned To:
:
: InRadar, ReviewedForRadar
:
:
  Show dependency treegraph
 
Reported: 2007-01-11 15:28 PST by
Modified: 2009-08-21 14:49 PST (History)


Attachments
Opening this file _WILL_ cause WebKit to crash (201 bytes, text/html)
2007-01-11 15:30 PST, David Carson
no flags Details
incomplete patch that uses an explicit mark stack - this is actually a speedup (33.74 KB, patch)
2007-11-07 06:57 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[1/4] Not reviewed. (1.68 KB, patch)
2007-11-27 00:50 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[2/4] JavaScriptCore: (92.75 KB, patch)
2007-11-27 00:50 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[3/4] Not reviewed. (10.10 KB, patch)
2007-11-27 00:50 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[4/4] JavaScriptCore: (12.91 KB, patch)
2007-11-27 00:50 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[1/6] Not reviewed. (1.63 KB, patch)
2007-11-27 01:21 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[2/6] JavaScriptCore: (73.76 KB, patch)
2007-11-27 01:21 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[3/6] JavaScriptCore: (15.22 KB, patch)
2007-11-27 01:21 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[4/6] Not reviewed. (13.46 KB, patch)
2007-11-27 01:21 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[5/6] Not reviewed. (10.73 KB, patch)
2007-11-27 01:22 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
[6/6] JavaScriptCore: (12.85 KB, patch)
2007-11-27 01:22 PST, Maciej Stachowiak
no flags Review Patch | Details | Formatted Diff | Diff
JSC portion of fix (94.31 KB, patch)
2009-08-07 14:54 PST, Oliver Hunt
no flags Review Patch | Details | Formatted Diff | Diff
JavaScriptGlue (3.35 KB, patch)
2009-08-07 14:55 PST, Oliver Hunt
sam: review+
Review Patch | Details | Formatted Diff | Diff
WebCore portion (50.95 KB, patch)
2009-08-07 14:56 PST, Oliver Hunt
sam: review+
Review Patch | Details | Formatted Diff | Diff
Layout test (3.03 KB, patch)
2009-08-07 14:56 PST, Oliver Hunt
no flags Review Patch | Details | Formatted Diff | Diff
Shorter layout test (3.21 KB, patch)
2009-08-07 17:19 PST, Oliver Hunt
sam: review+
Review Patch | Details | Formatted Diff | Diff
JavaScriptCore portion (94.29 KB, patch)
2009-08-07 17:20 PST, Oliver Hunt
no flags Review Patch | Details | Formatted Diff | Diff
JavaScriptCore portion (94.41 KB, patch)
2009-08-07 17:58 PST, Oliver Hunt
barraclough: review+
Review Patch | Details | Formatted Diff | Diff


Note

You need to log in before you can comment on or make changes to this bug.


Description From 2007-01-11 15:28:14 PST
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 ??
------- Comment #1 From 2007-01-11 15:30:14 PST -------
Created an attachment (id=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.
------- Comment #2 From 2007-01-11 17:03:02 PST -------
Reproducible crash => p1.
------- Comment #3 From 2007-01-16 00:04:11 PST -------
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!
------- Comment #4 From 2007-01-16 19:48:57 PST -------
<rdar://problem/4928697>
------- Comment #5 From 2007-04-10 23:18:24 PST -------
Here's another example, found while playing with ways to work around bug 4045

http://www.cs.hmc.edu/~oneill/cps-sum.html
------- Comment #6 From 2007-07-14 17:38:57 PST -------
(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.
------- Comment #7 From 2007-07-14 19:28:58 PST -------
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.
------- Comment #8 From 2007-11-07 06:57:39 PST -------
Created an attachment (id=17110) [details]
incomplete patch that uses an explicit mark stack - this is actually a speedup
------- Comment #9 From 2007-11-07 10:43:15 PST -------
(From update of attachment 17110 [details])
I didn't mean to flag this for review.
------- Comment #10 From 2007-11-27 00:50:07 PST -------
Created an attachment (id=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(-)
------- Comment #11 From 2007-11-27 00:50:12 PST -------
Created an attachment (id=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(-)
------- Comment #12 From 2007-11-27 00:50:14 PST -------
Created an attachment (id=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(-)
------- Comment #13 From 2007-11-27 00:50:16 PST -------
Created an attachment (id=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(-)
------- Comment #14 From 2007-11-27 01:21:52 PST -------
Created an attachment (id=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(-)
------- Comment #15 From 2007-11-27 01:21:55 PST -------
Created an attachment (id=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(-)
------- Comment #16 From 2007-11-27 01:21:57 PST -------
Created an attachment (id=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(-)
------- Comment #17 From 2007-11-27 01:21:59 PST -------
Created an attachment (id=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(-)
------- Comment #18 From 2007-11-27 01:22:01 PST -------
Created an attachment (id=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(-)
------- Comment #19 From 2007-11-27 01:22:02 PST -------
Created an attachment (id=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(-)
------- Comment #20 From 2007-11-27 01:30:57 PST -------
(From update of attachment 17548 [details])
I'll fix the bogus ChangeLog changes when I actually commit this.
------- Comment #21 From 2007-11-27 09:18:46 PST -------
(From update of attachment 17548 [details])
Looks like ChangeLog was merged incorrectly.

r=me
------- Comment #22 From 2007-11-27 09:25:12 PST -------
(From update of attachment 17549 [details])
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
------- Comment #23 From 2007-11-27 09:27:15 PST -------
(From update of attachment 17550 [details])
r=me -- no clear on how this relates to the other patches here
------- Comment #24 From 2007-11-27 09:30:52 PST -------
(From update of attachment 17551 [details])
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
------- Comment #25 From 2007-11-27 09:33:09 PST -------
(From update of attachment 17552 [details])
 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
------- Comment #26 From 2007-11-27 09:36:49 PST -------
(From update of attachment 17553 [details])
 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
------- Comment #27 From 2007-11-27 10:09:27 PST -------
The license in MarkStack.h is LGPL, I think we should make it BSD.
------- Comment #28 From 2007-11-27 11:40:01 PST -------
(From update of attachment 17548 [details])
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.
------- Comment #29 From 2007-11-27 11:49:13 PST -------
(From update of attachment 17549 [details])
"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.
------- Comment #30 From 2007-11-27 11:52:51 PST -------
(From update of attachment 17550 [details])
+        ASSERT(m_stack.size() < m_stack.capacity());
+        m_stack.uncheckedAppend(cell);

You can remove the ASSERT here and elsewhere; uncheckedAppend does that already.
------- Comment #31 From 2007-11-27 11:58:42 PST -------
(From update of attachment 17552 [details])
-            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.
------- Comment #32 From 2007-11-27 12:06:20 PST -------
(From update of attachment 17553 [details])
+    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?
------- Comment #33 From 2007-11-27 22:04:14 PST -------
(From update of attachment 17548 [details])
I landed this patch with the ChangeLog fixed.
------- Comment #34 From 2007-12-05 22:59:50 PST -------
Maciej, is this bug fixed yet? Why is it still open? It's showing up in the "patches to commit" queue.
------- Comment #35 From 2008-07-17 14:01:25 PST -------
*** Bug 20076 has been marked as a duplicate of this bug. ***
------- Comment #36 From 2009-08-07 14:54:29 PST -------
Created an attachment (id=34331) [details]
JSC portion of fix
------- Comment #37 From 2009-08-07 14:55:30 PST -------
Created an attachment (id=34332) [details]
JavaScriptGlue
------- Comment #38 From 2009-08-07 14:56:03 PST -------
Created an attachment (id=34333) [details]
WebCore portion
------- Comment #39 From 2009-08-07 14:56:40 PST -------
Created an attachment (id=34334) [details]
Layout test
------- Comment #40 From 2009-08-07 15:40:21 PST -------
(From update of attachment 34331 [details])
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).
------- Comment #41 From 2009-08-07 17:19:41 PST -------
Created an attachment (id=34344) [details]
Shorter layout test
------- Comment #42 From 2009-08-07 17:20:19 PST -------
Created an attachment (id=34345) [details]
JavaScriptCore portion
------- Comment #43 From 2009-08-07 17:26:24 PST -------
(From update of attachment 34344 [details])
> +
> +successfullyParsed = true;
> \ No newline at end of file

You need a newline.
------- Comment #44 From 2009-08-07 17:58:04 PST -------
Created an attachment (id=34351) [details]
JavaScriptCore portion
------- Comment #45 From 2009-08-07 21:54:50 PST -------
(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;

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).
------- Comment #46 From 2009-08-07 21:58:47 PST -------
(In reply to comment #45)
> (From update of attachment 34351 [details] [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
------- Comment #47 From 2009-08-10 15:33:13 PST -------
(From update of attachment 34351 [details])
Please comment CompoundType.
------- Comment #48 From 2009-08-10 21:36:17 PST -------
Committed in r47022
------- Comment #49 From 2009-08-21 14:47:27 PST -------
No updates in 11 days.  I assume these are all landed, but I'll leave Oliver to confirm that and close the bug.
------- Comment #50 From 2009-08-21 14:49:03 PST -------
This has been fixed, but the fixeration got eaten by the great bugzilla disaster of '09