[webkit-reviews] review requested: [Bug 12216] Stack overflow crash in JavaScript garbage collector mark pass : [Attachment 17545] [2/4] JavaScriptCore:

Tue Nov 27 00:50:13 PST 2007

Maciej Stachowiak <mjs at apple.com> has asked  for review:
Bug 12216: Stack overflow crash in JavaScript garbage collector mark pass
http://bugs.webkit.org/show_bug.cgi?id=12216

Attachment 17545: [2/4] JavaScriptCore:
http://bugs.webkit.org/attachment.cgi?id=17545&action=edit

------- Additional Comments from Maciej Stachowiak <mjs at apple.com>

	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(-)