Bug 37181

Summary: REGRESSION (r54400): Hangs when doing AJAX update with large amount of data
Product: WebKit Reporter: Naofumi Kagami <naofumi>
Component: WebCore JavaScriptAssignee: Alexey Proskuryakov <ap>
Status: RESOLVED FIXED    
Severity: Normal CC: ap, ggaren
Priority: P2 Keywords: InRadar, Regression
Version: 528+ (Nightly build)   
Hardware: Mac (Intel)   
OS: OS X 10.6   
URL: http://catalog.castle104.com/
Attachments:
Description Flags
reduced test case (will hang)
none
proposed fix darin: review+

Naofumi Kagami
Reported 2010-04-06 17:52:11 PDT
Regression introduced in Nightly #54415. Works fine with Nightly #54326 and current Safari release. How to reproduce: Go to http://catalog.castle104.com/ In the lower portion of the page, scroll down until you see the the link at the bottom which says something like "7594ページすべてのリンクを表示する" (the number may vary). This button sends an AJAX request that returns HTML for more than 7,000 links. On the current Safari release and Nightly up till #54326, this works fine. However, since Nightly #54415, this hangs WebKit.
Attachments
reduced test case (will hang) (392 bytes, text/html)
2010-04-07 18:00 PDT, Alexey Proskuryakov 		no flags
Details
proposed fix (5.53 KB, patch)
2010-04-08 18:04 PDT, Alexey Proskuryakov 		darin: review+
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Alexey Proskuryakov
Comment 1 2010-04-06 20:56:24 PDT
<rdar://problem/7835374>
Geoffrey Garen
Comment 2 2010-04-07 12:26:25 PDT
~/webkit/JavaScriptCore$ cat /tmp/RealSafari_3191.Ga4mEa.sample.txt Analysis of sampling RealSafari (pid 3191) every 1 millisecond Call graph: 7757 Thread_115733 DispatchQueue_1: com.apple.main-thread (serial) 7756 0x102ec77c0 7756 JSC::Interpreter::execute(JSC::EvalExecutable*, JSC::ExecState*, JSC::JSObject*, int, JSC::ScopeChainNode*, JSC::JSValue*) 7756 0x2a7db4cc31fa 7756 cti_op_put_by_id_generic 7756 WebCore::JSHTMLDivElement::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 7756 WebCore::JSHTMLElement::put(JSC::ExecState*, JSC::Identifier const&, JSC::JSValue, JSC::PutPropertySlot&) 7756 WebCore::setJSHTMLElementInnerHTML(JSC::ExecState*, JSC::JSObject*, JSC::JSValue) 7756 WebCore::HTMLElement::setInnerHTML(WebCore::String const&, int&) 7756 WebCore::HTMLElement::createContextualFragment(WebCore::String const&, WebCore::FragmentScriptingPermission) 7756 WebCore::Element::createContextualFragment(WebCore::String const&, WebCore::FragmentScriptingPermission) 7756 WebCore::parseHTMLDocumentFragment(WebCore::String const&, WebCore::DocumentFragment*, WebCore::FragmentScriptingPermission) 7756 WebCore::HTMLTokenizer::write(WebCore::SegmentedString const&, bool) 7756 WebCore::HTMLTokenizer::parseTag(WebCore::SegmentedString&, WebCore::HTMLTokenizer::State) 7756 WebCore::HTMLTokenizer::processToken() 7756 WebCore::HTMLParser::parseToken(WebCore::Token*) 7756 WebCore::Element::setAttributeMap(WTF::PassRefPtr<WebCore::NamedNodeMap>, WebCore::FragmentScriptingPermission) 7756 WebCore::StyledElement::attributeChanged(WebCore::Attribute*, bool) 7756 WebCore::HTMLAnchorElement::parseMappedAttribute(WebCore::MappedAttribute*) 7756 WebCore::HTMLElement::parseMappedAttribute(WebCore::MappedAttribute*) 7756 WebCore::createAttributeEventListener(WebCore::Node*, WebCore::Attribute*) 7756 WebCore::createWrapper(JSC::ExecState*, WebCore::JSDOMGlobalObject*, WebCore::Node*) 7756 WebCore::createJSHTMLWrapper(JSC::ExecState*, WebCore::JSDOMGlobalObject*, WTF::PassRefPtr<WebCore::HTMLElement>) 7756 WebCore::createHTMLAnchorElementWrapper(JSC::ExecState*, WebCore::JSDOMGlobalObject*, WTF::PassRefPtr<WebCore::HTMLElement>) 7756 JSC::Heap::allocate(unsigned long) 7756 JSC::Heap::reset() 7756 JSC::Heap::markRoots() 7756 JSC::Heap::markStackObjectsConservatively(JSC::MarkStack&) 7756 JSC::Heap::markCurrentThreadConservatively(JSC::MarkStack&) 7756 JSC::Heap::markCurrentThreadConservativelyInternal(JSC::MarkStack&) 7756 JSC::Heap::markConservatively(JSC::MarkStack&, void*, void*) 7650 JSC::MarkStack::markChildren(JSC::JSCell*) 7650 WebCore::JSElement::markChildren(JSC::MarkStack&) 7649 WebCore::JSNode::markChildren(JSC::MarkStack&) 6708 WebCore::markDOMNodeWrapper(JSC::MarkStack&, WebCore::Document*, WebCore::Node*) 4521 WebCore::markDOMNodeWrapper(JSC::MarkStack&, WebCore::Document*, WebCore::Node*) 2187 WTF::HashMap<WebCore::Node*, WebCore::JSNode*, WTF::PtrHash<WebCore::Node*>, WTF::HashTraits<WebCore::Node*>, WTF::HashTraits<WebCore::JSNode*> >::get(WebCore::Node* const&) const 772 WebCore::Node::traverseNextNode(WebCore::Node const*) const 165 WebCore::JSNode::markChildren(JSC::MarkStack&) 2 WebCore::Node::eventTargetData() 1 WebCore::Node::eventTargetData() 1 WebCore::Node::rareData() const 1 WTF::HashMap<WebCore::Node const*, WebCore::NodeRareData*, WTF::PtrHash<WebCore::Node const*>, WTF::HashTraits<WebCore::Node const*>, WTF::HashTraits<WebCore::NodeRareData*> >::get(WebCore::Node const* const&) const 1 JSC::JSObject::markChildren(JSC::MarkStack&) 1 WebCore::hasCachedDOMNodeWrapperUnchecked(WebCore::Document*, WebCore::Node*) 1 WebCore::markDOMObjectWrapper(JSC::MarkStack&, JSC::JSGlobalData&, void*) 1 WTF::HashMap<void*, WebCore::DOMObject*, WTF::PtrHash<void*>, WTF::HashTraits<void*>, WTF::HashTraits<WebCore::DOMObject*> >::get(void* const&) const 106 JSC::Heap::markConservatively(JSC::MarkStack&, void*, void*) 1 0x841f0f 1 JSC::JSArray::~JSArray() 1 0x7bf 1 JSC::MarkStack::markChildren(JSC::JSCell*) 1 WebCore::JSElement::markChildren(JSC::MarkStack&) 7757 Thread_115744 DispatchQueue_2: com.apple.libdispatch-manager (serial) 7757 start_wqthread 7757 _pthread_wqthread 7757 _dispatch_worker_thread2 7757 _dispatch_queue_invoke 7757 _dispatch_mgr_invoke 7757 kevent 7757 Thread_115747: WebCore: IconDatabase 7757 thread_start 7757 _pthread_start 7757 WebCore::IconDatabase::iconDatabaseSyncThread() 7757 WebCore::IconDatabase::syncThreadMainLoop() 7757 _pthread_cond_wait 7757 __semwait_signal 7757 Thread_115749: Safari: SafeBrowsingManager 7757 thread_start 7757 _pthread_start 7757 0x100025873 7757 0x1000258e3 7757 CFRunLoopRunSpecific 7757 __CFRunLoopRun 7757 mach_msg 7757 mach_msg_trap 7757 Thread_115750: Safari: SnapshotStore 7757 thread_start 7757 _pthread_start 7757 0x100040f81 7757 0x100041101 7757 0x1001a1c21 7757 WTF::ThreadCondition::timedWait(WTF::Mutex&, double) 7757 _pthread_cond_wait 7757 __semwait_signal 7757 Thread_115760 7757 thread_start 7757 _pthread_start 7757 __NSThread__main__ 7757 +[NSURLConnection(NSURLConnectionReallyInternal) _resourceLoadLoop:] 7757 CFRunLoopRunSpecific 7757 __CFRunLoopRun 7757 mach_msg 7757 mach_msg_trap 7757 Thread_115764 7757 thread_start 7757 _pthread_start 7757 __CFSocketManager 7757 select$DARWIN_EXTSN 7756 Thread_115745 7756 start_wqthread 7756 _pthread_wqthread 7756 __workq_kernreturn 1 Thread_115745 DispatchQueue_24: com.apple.CFURLCACHE_work_queue (serial) 1 start_wqthread 1 _pthread_wqthread 1 _dispatch_worker_thread2 1 _dispatch_queue_invoke 1 _dispatch_queue_drain 1 _dispatch_queue_invoke 1 _dispatch_source_invoke 1 __CFURLCacheCreate_block_invoke_3 1 _CFURLCacheTimerCallback(void*) 1 asl_log 1 asl_vlog 1 _asl_send_level_message 1 notify_get_state 1 _notify_server_get_state 1 mach_msg 1 mach_msg_trap Total number in stack (recursive counted multiple, when >=5): 5 _pthread_start 5 thread_start Sort by top of stack, same collapsed (when >= 5): mach_msg_trap 15515 __semwait_signal 15514 kevent 7757 select$DARWIN_EXTSN 7757 __workq_kernreturn 7756 WebCore::markDOMNodeWrapper(JSC::MarkStack&, WebCore::Document*, WebCore::Node*) 4521 WTF::HashMap<WebCore::Node*, WebCore::JSNode*, WTF::PtrHash<WebCore::Node*>, WTF::HashTraits<WebCore::Node*>, WTF::HashTraits<WebCore::JSNode*> >::get(WebCore::Node* const&) const 2187 WebCore::Node::traverseNextNode(WebCore::Node const*) const 772 WebCore::JSNode::markChildren(JSC::MarkStack&) 165 JSC::Heap::markConservatively(JSC::MarkStack&, void*, void*) 106 ~/webkit/JavaScriptCore$
Alexey Proskuryakov
Comment 3 2010-04-07 17:02:52 PDT
This doesn't look like an infinite loop - just an incredibly slow operation. We do actually return from GC to HTMLTokenizer::write(). It's much slower in debug builds - due to locking in HashMap checking code, we never return from GC.
Alexey Proskuryakov
Comment 4 2010-04-07 18:00:04 PDT
Created attachment 52816 [details] reduced test case (will hang)
Geoffrey Garen
Comment 5 2010-04-08 08:28:45 PDT
One obvious missing optimization here, though probably not the main problem, is that markDOMNodeWrapper is missing the optimization in getCachedDOMNodeWrapper, which, for the normal world, gets a node's wrapper directly from the node, instead of doing a hash table lookup.
Geoffrey Garen
Comment 6 2010-04-08 08:33:03 PDT
The main problem seems to be that WebCore::markDOMNodeWrapper is called more than once for the same Node*, which probably makes this algorithm n^2 at least. If you set breakpoints on JSC::Collector::markRoots and WebCore::markDOMNodeWrapper, pick a Node* at random, and do a text search in the scrollback, you'll see your node appear many times. My current count is 9.
Alexey Proskuryakov
Comment 7 2010-04-08 13:26:02 PDT
Adding a check to JSNode::markChildren fixes this: if (Heap::isCellMarked(this)) return; I have no idea if it's a sensible approach.
Alexey Proskuryakov
Comment 8 2010-04-08 18:04:20 PDT
Created attachment 52926 [details] proposed fix Geoff helped find a better solution.
Alexey Proskuryakov
Comment 9 2010-04-09 09:35:45 PDT
Fixed in <http://trac.webkit.org/changeset/57340>.
Note You need to log in before you can comment on or make changes to this bug.