Bug 37181 – REGRESSION (r54400): Hangs when doing AJAX update with large amount of data

• Status: RESOLVED
• Resolution: FIXED
• Component: WebCore JavaScript

[Naofumi Kagami]

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.

[Alexey Proskuryakov]

<rdar://problem/7835374>

[Geoffrey Garen]

~/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]

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]

Created attachment 52816 [details]
reduced test case (will hang)

[Geoffrey Garen]

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]

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]

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]

Created attachment 52926 [details]
proposed fix

Geoff helped find a better solution.

[Alexey Proskuryakov]

Fixed in <http://trac.webkit.org/changeset/57340>.