Changeset 83938 in webkit


Ignore:
Timestamp:
Apr 14, 2011 8:39:49 PM (13 years ago)
Author:
ggaren@apple.com
Message:

2011-04-14 Geoffrey Garen <ggaren@apple.com>

Reviewed by Oliver Hunt.

Use opaque roots instead of direct marking for nodes in the DOM
https://bugs.webkit.org/show_bug.cgi?id=58624

A node treats the root of its tree (usually the document) as its opaque
root during GC.


This is needed for correctness in a generational GC world, but it also
happens to be a 3.5X speedup in a DOM-heavy GC test (scratch-gc-dom2.html).

  • bindings/js/DOMWrapperWorld.cpp: (WebCore::isObservable): (WebCore::isReachableFromDOM): Moved a helper function from JSDOMBinding. We use this function to determine whether a node is observable.

(WebCore::JSNodeHandleOwner::isReachableFromOpaqueRoots): Start using
our weak handle callback to determine reachability, instead of direct
marking traversal through the DOM.

  • bindings/js/JSAttrCustom.cpp: (WebCore::JSAttr::markChildren): Updated to use the opaque roots mechanism instead of direct marking.
  • bindings/js/JSDOMBinding.cpp:
  • bindings/js/JSDOMBinding.h: Moved code mentioned above. Removed markDOMNodeWrapper because it is now unused. This is a good thing because markDOMNodeWrapper used deprecatedAppend, which is not compatible with generational GC.
  • bindings/js/JSDOMImplementationCustom.cpp: (WebCore::JSDOMImplementation::markChildren): Updated to use opaque roots.
  • bindings/js/JSDocumentCustom.cpp: (WebCore::JSDocument::markChildren): No need to mark our child nodes directly, since they will take care of themselves through the opaque roots mechanism.
  • bindings/js/JSNamedNodeMapCustom.cpp: (WebCore::JSNamedNodeMap::markChildren): Updated to use opaque roots.
  • bindings/js/JSNodeCustom.cpp: (WebCore::JSNode::markChildren): No need to mark our tree or our document directly, since they will take care of themselves through the opaque roots mechanism.
  • bindings/js/JSNodeCustom.h: (WebCore::root): Helper function for accessing the root of a node tree. This is O(1) while you're in the document, O(log(N)) when you're in a reasonably balanced disconnected tree, and O(N) in the pathological case of a disconnected tree that's shaped like a linked list. If average case O(long(N)) turns out to be too slow, we can optimize through use of rare data or an external hash table, but it is so uncommon that I have ignored it for now.
  • bindings/js/JSSVGElementInstanceCustom.cpp: (WebCore::JSSVGElementInstance::markChildren): Updated to use opaque roots.
Location:
trunk/Source/WebCore
Files:
11 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r83936 r83938  
     12011-04-14  Geoffrey Garen  <ggaren@apple.com>
     2
     3        Reviewed by Oliver Hunt.
     4
     5        Use opaque roots instead of direct marking for nodes in the DOM
     6        https://bugs.webkit.org/show_bug.cgi?id=58624
     7
     8        A node treats the root of its tree (usually the document) as its opaque
     9        root during GC.
     10       
     11        This is needed for correctness in a generational GC world, but it also
     12        happens to be a 3.5X speedup in a DOM-heavy GC test (scratch-gc-dom2.html).
     13
     14        * bindings/js/DOMWrapperWorld.cpp:
     15        (WebCore::isObservable):
     16        (WebCore::isReachableFromDOM): Moved a helper function from JSDOMBinding.
     17        We use this function to determine whether a node is observable.
     18
     19        (WebCore::JSNodeHandleOwner::isReachableFromOpaqueRoots): Start using
     20        our weak handle callback to determine reachability, instead of direct
     21        marking traversal through the DOM.
     22
     23        * bindings/js/JSAttrCustom.cpp:
     24        (WebCore::JSAttr::markChildren): Updated to use the opaque roots mechanism
     25        instead of direct marking.
     26
     27        * bindings/js/JSDOMBinding.cpp:
     28        * bindings/js/JSDOMBinding.h: Moved code mentioned above. Removed
     29        markDOMNodeWrapper because it is now unused. This is a good thing because
     30        markDOMNodeWrapper used deprecatedAppend, which is not compatible
     31        with generational GC.
     32
     33        * bindings/js/JSDOMImplementationCustom.cpp:
     34        (WebCore::JSDOMImplementation::markChildren): Updated to use opaque roots.
     35
     36        * bindings/js/JSDocumentCustom.cpp:
     37        (WebCore::JSDocument::markChildren): No need to mark our child nodes directly,
     38        since they will take care of themselves through the opaque roots mechanism.
     39
     40        * bindings/js/JSNamedNodeMapCustom.cpp:
     41        (WebCore::JSNamedNodeMap::markChildren): Updated to use opaque roots.
     42
     43        * bindings/js/JSNodeCustom.cpp:
     44        (WebCore::JSNode::markChildren): No need to mark our tree or our document
     45        directly, since they will take care of themselves through the opaque
     46        roots mechanism.
     47
     48        * bindings/js/JSNodeCustom.h:
     49        (WebCore::root): Helper function for accessing the root of a node tree.
     50        This is O(1) while you're in the document, O(log(N)) when you're in a
     51        reasonably balanced disconnected tree, and O(N) in the pathological case
     52        of a disconnected tree that's shaped like a linked list. If average case
     53        O(long(N)) turns out to be too slow, we can optimize through use of
     54        rare data or an external hash table, but it is so uncommon that I have
     55        ignored it for now.
     56
     57        * bindings/js/JSSVGElementInstanceCustom.cpp:
     58        (WebCore::JSSVGElementInstance::markChildren): Updated to use opaque roots.
     59
    1602011-04-14  Mike Reed  <reed@google.com>
    261
  • trunk/Source/WebCore/bindings/js/DOMWrapperWorld.cpp

    r83773 r83938  
    2222#include "DOMWrapperWorld.h"
    2323
     24#include "HTMLAudioElement.h"
     25#include "HTMLCanvasElement.h"
     26#include "HTMLFrameElementBase.h"
     27#include "HTMLImageElement.h"
     28#include "HTMLLinkElement.h"
     29#include "HTMLNames.h"
     30#include "HTMLScriptElement.h"
     31#include "HTMLStyleElement.h"
    2432#include "JSDOMWindow.h"
    2533#include "JSNode.h"
     34#include "ProcessingInstruction.h"
    2635#include "ScriptController.h"
     36#include "StyleSheet.h"
     37#include "StyledElement.h"
    2738#include "WebCoreJSClientData.h"
    2839#include <heap/Weak.h>
     
    3142
    3243namespace WebCore {
     44
     45using namespace HTMLNames;
     46
     47static bool isObservable(JSNode* jsNode, Node* node, DOMWrapperWorld* world)
     48{
     49    // Certain conditions implicitly make existence of a JS DOM node wrapper observable
     50    // through the DOM, even if no explicit reference to it remains.
     51   
     52    // The DOM doesn't know how to keep a tree of nodes alive without the root
     53    // being explicitly referenced. So, we artificially treat the root of
     54    // every tree as observable.
     55    // FIXME: Resolve this lifetime issue in the DOM, and remove this inefficiency.
     56    if (!node->parentNode())
     57        return true;
     58
     59    // If a node is in the document, and its wrapper has custom properties,
     60    // the wrapper is observable because future access to the node through the
     61    // DOM must reflect those properties.
     62    if (jsNode->hasCustomProperties())
     63        return true;
     64
     65    // If a node is in the document, and has event listeners, its wrapper is
     66    // observable because its wrapper is responsible for marking those event listeners.
     67    if (node->hasEventListeners())
     68        return true;
     69
     70    // If a node owns another object with a wrapper with custom properties,
     71    // the wrapper must be treated as observable, because future access to
     72    // those objects through the DOM must reflect those properties.
     73    // FIXME: It would be better if this logic could be in the node next to
     74    // the custom markChildren functions rather than here.
     75    // Note that for some compound objects like stylesheets and CSSStyleDeclarations,
     76    // we don't descend to check children for custom properties, and just conservatively
     77    // keep the node wrappers protecting them alive.
     78    if (node->isElementNode()) {
     79        if (NamedNodeMap* attributes = static_cast<Element*>(node)->attributeMap()) {
     80            if (DOMObject* wrapper = world->m_wrappers.get(attributes).get()) {
     81                // FIXME: This check seems insufficient, because NamedNodeMap items can have custom properties themselves.
     82                // Maybe it would be OK to just keep the wrapper alive, as it is done for CSSOM objects below.
     83                if (wrapper->hasCustomProperties())
     84                    return true;
     85            }
     86        }
     87        if (node->isStyledElement()) {
     88            if (CSSMutableStyleDeclaration* style = static_cast<StyledElement*>(node)->inlineStyleDecl()) {
     89                if (world->m_wrappers.get(style))
     90                    return true;
     91            }
     92        }
     93        if (static_cast<Element*>(node)->hasTagName(canvasTag)) {
     94            if (CanvasRenderingContext* context = static_cast<HTMLCanvasElement*>(node)->renderingContext()) {
     95                if (DOMObject* wrapper = world->m_wrappers.get(context).get()) {
     96                    if (wrapper->hasCustomProperties())
     97                        return true;
     98                }
     99            }
     100        } else if (static_cast<Element*>(node)->hasTagName(linkTag)) {
     101            if (StyleSheet* sheet = static_cast<HTMLLinkElement*>(node)->sheet()) {
     102                if (world->m_wrappers.get(sheet))
     103                    return true;
     104            }
     105        } else if (static_cast<Element*>(node)->hasTagName(styleTag)) {
     106            if (StyleSheet* sheet = static_cast<HTMLStyleElement*>(node)->sheet()) {
     107                if (world->m_wrappers.get(sheet))
     108                    return true;
     109            }
     110        }
     111    } else if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {
     112        if (StyleSheet* sheet = static_cast<ProcessingInstruction*>(node)->sheet()) {
     113            if (world->m_wrappers.get(sheet))
     114                return true;
     115        }
     116    }
     117
     118    return false;
     119}
     120
     121static inline bool isReachableFromDOM(JSNode* jsNode, Node* node, DOMWrapperWorld* world, MarkStack& markStack)
     122{
     123    if (node->inDocument())
     124        return isObservable(jsNode, node, world) && markStack.containsOpaqueRoot(root(node));
     125
     126    // If a wrapper is the last reference to an image or script element
     127    // that is loading but not in the document, the wrapper is observable
     128    // because it is the only thing keeping the image element alive, and if
     129    // the image element is destroyed, its load event will not fire.
     130    // FIXME: The DOM should manage this issue without the help of JavaScript wrappers.
     131    if (node->hasTagName(imgTag) && !static_cast<HTMLImageElement*>(node)->haveFiredLoadEvent())
     132        return true;
     133    if (node->hasTagName(scriptTag) && !static_cast<HTMLScriptElement*>(node)->haveFiredLoadEvent())
     134        return true;
     135#if ENABLE(VIDEO)
     136    if (node->hasTagName(audioTag) && !static_cast<HTMLAudioElement*>(node)->paused())
     137        return true;
     138#endif
     139
     140    // If a node is firing event listeners, its wrapper is observable because
     141    // its wrapper is responsible for marking those event listeners.
     142    if (node->isFiringEventListeners())
     143        return true;
     144
     145    return isObservable(jsNode, node, world) && markStack.containsOpaqueRoot(root(node));
     146}
    33147
    34148DOMWrapperWorld::DOMWrapperWorld(JSC::JSGlobalData* globalData, bool isNormal)
     
    84198}
    85199
    86 bool JSNodeHandleOwner::isReachableFromOpaqueRoots(JSC::Handle<JSC::Unknown>, void*, JSC::MarkStack&)
    87 {
    88     return false;
     200bool JSNodeHandleOwner::isReachableFromOpaqueRoots(JSC::Handle<JSC::Unknown> handle, void*, JSC::MarkStack& markStack)
     201{
     202    JSNode* jsNode = static_cast<JSNode*>(handle.get().asCell());
     203    return isReachableFromDOM(jsNode, jsNode->impl(), m_world, markStack);
    89204}
    90205
  • trunk/Source/WebCore/bindings/js/JSAttrCustom.cpp

    r68854 r83938  
    4444    Base::markChildren(markStack);
    4545
    46     // Mark the element so that this will work to access the attribute even if the last
    47     // other reference goes away.
    48     if (Element* element = impl()->ownerElement())
    49         markDOMNodeWrapper(markStack, element->document(), element);
     46    Element* element = impl()->ownerElement();
     47    if (!element)
     48        return;
     49    markStack.addOpaqueRoot(root(element));
    5050}
    5151
  • trunk/Source/WebCore/bindings/js/JSDOMBinding.cpp

    r83808 r83938  
    195195}
    196196
    197 static inline bool isObservableThroughDOM(JSNode* jsNode, DOMWrapperWorld* world)
    198 {
    199     // Certain conditions implicitly make existence of a JS DOM node wrapper observable
    200     // through the DOM, even if no explicit reference to it remains.
    201 
    202     Node* node = jsNode->impl();
    203 
    204     if (node->inDocument()) {
    205         // If a node is in the document, and its wrapper has custom properties,
    206         // the wrapper is observable because future access to the node through the
    207         // DOM must reflect those properties.
    208         if (jsNode->hasCustomProperties())
    209             return true;
    210 
    211         // If a node is in the document, and has event listeners, its wrapper is
    212         // observable because its wrapper is responsible for marking those event listeners.
    213         if (node->hasEventListeners())
    214             return true; // Technically, we may overzealously mark a wrapper for a node that has only non-JS event listeners. Oh well.
    215 
    216         // If a node owns another object with a wrapper with custom properties,
    217         // the wrapper must be treated as observable, because future access to
    218         // those objects through the DOM must reflect those properties.
    219         // FIXME: It would be better if this logic could be in the node next to
    220         // the custom markChildren functions rather than here.
    221         // Note that for some compound objects like stylesheets and CSSStyleDeclarations,
    222         // we don't descend to check children for custom properties, and just conservatively
    223         // keep the node wrappers protecting them alive.
    224         if (node->isElementNode()) {
    225             if (NamedNodeMap* attributes = static_cast<Element*>(node)->attributeMap()) {
    226                 if (DOMObject* wrapper = world->m_wrappers.get(attributes).get()) {
    227                     // FIXME: This check seems insufficient, because NamedNodeMap items can have custom properties themselves.
    228                     // Maybe it would be OK to just keep the wrapper alive, as it is done for CSSOM objects below.
    229                     if (wrapper->hasCustomProperties())
    230                         return true;
    231                 }
    232             }
    233             if (node->isStyledElement()) {
    234                 if (CSSMutableStyleDeclaration* style = static_cast<StyledElement*>(node)->inlineStyleDecl()) {
    235                     if (world->m_wrappers.get(style))
    236                         return true;
    237                 }
    238             }
    239             if (static_cast<Element*>(node)->hasTagName(canvasTag)) {
    240                 if (CanvasRenderingContext* context = static_cast<HTMLCanvasElement*>(node)->renderingContext()) {
    241                     if (DOMObject* wrapper = world->m_wrappers.get(context).get()) {
    242                         if (wrapper->hasCustomProperties())
    243                             return true;
    244                     }
    245                 }
    246             } else if (static_cast<Element*>(node)->hasTagName(linkTag)) {
    247                 if (StyleSheet* sheet = static_cast<HTMLLinkElement*>(node)->sheet()) {
    248                     if (world->m_wrappers.get(sheet))
    249                         return true;
    250                 }
    251             } else if (static_cast<Element*>(node)->hasTagName(styleTag)) {
    252                 if (StyleSheet* sheet = static_cast<HTMLStyleElement*>(node)->sheet()) {
    253                     if (world->m_wrappers.get(sheet))
    254                         return true;
    255                 }
    256             }
    257         } else if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE) {
    258             if (StyleSheet* sheet = static_cast<ProcessingInstruction*>(node)->sheet()) {
    259                 if (world->m_wrappers.get(sheet))
    260                     return true;
    261             }
    262         }
    263     } else {
    264         // If a wrapper is the last reference to an image or script element
    265         // that is loading but not in the document, the wrapper is observable
    266         // because it is the only thing keeping the image element alive, and if
    267         // the image element is destroyed, its load event will not fire.
    268         // FIXME: The DOM should manage this issue without the help of JavaScript wrappers.
    269         if (node->hasTagName(imgTag) && !static_cast<HTMLImageElement*>(node)->haveFiredLoadEvent())
    270             return true;
    271         if (node->hasTagName(scriptTag) && !static_cast<HTMLScriptElement*>(node)->haveFiredLoadEvent())
    272             return true;
    273 #if ENABLE(VIDEO)
    274         if (node->hasTagName(audioTag) && !static_cast<HTMLAudioElement*>(node)->paused())
    275             return true;
    276 #endif
    277     }
    278 
    279     // If a node is firing event listeners, its wrapper is observable because
    280     // its wrapper is responsible for marking those event listeners.
    281     if (node->isFiringEventListeners())
    282         return true;
    283 
    284     return false;
    285 }
    286 
    287 void markDOMNodesForDocument(MarkStack& markStack, Document* document)
    288 {
    289     JSWrapperCacheMap& wrapperCacheMap = document->wrapperCacheMap();
    290     for (JSWrapperCacheMap::iterator wrappersIter = wrapperCacheMap.begin(); wrappersIter != wrapperCacheMap.end(); ++wrappersIter) {
    291         DOMWrapperWorld* world = wrappersIter->first;
    292         JSWrapperCache* nodeDict = wrappersIter->second;
    293 
    294         JSWrapperCache::iterator nodeEnd = nodeDict->end();
    295         for (JSWrapperCache::iterator nodeIt = nodeDict->begin(); nodeIt != nodeEnd; ++nodeIt) {
    296             JSNode* node = nodeIt->second.get();
    297             if (!isObservableThroughDOM(node, world))
    298                 continue;
    299             markStack.deprecatedAppend(reinterpret_cast<JSCell**>(&node));
    300         }
    301     }
    302 }
    303 
    304197void markActiveObjectsForContext(MarkStack& markStack, JSGlobalData& globalData, ScriptExecutionContext* scriptExecutionContext)
    305198{
     
    378271}
    379272
    380 void markDOMNodeWrapper(MarkStack& markStack, Document* document, Node* node)
    381 {
    382     if (document) {
    383         JSWrapperCacheMap& wrapperCacheMap = document->wrapperCacheMap();
    384         for (JSWrapperCacheMap::iterator iter = wrapperCacheMap.begin(); iter != wrapperCacheMap.end(); ++iter) {
    385             JSNode* wrapper = iter->second->get(node).get();
    386             if (!wrapper)
    387                 continue;
    388             markStack.deprecatedAppend(reinterpret_cast<JSCell**>(&wrapper));
    389         }
    390         return;
    391     }
    392 
    393     for (JSGlobalDataWorldIterator worldIter(JSDOMWindow::commonJSGlobalData()); worldIter; ++worldIter) {
    394         if (DOMObject* wrapper = worldIter->m_wrappers.get(node).get())
    395             markStack.deprecatedAppend(reinterpret_cast<JSCell**>(&wrapper));
    396     }
    397 }
    398 
    399273static void stringWrapperDestroyed(JSString*, void* context)
    400274{
  • trunk/Source/WebCore/bindings/js/JSDOMBinding.h

    r83808 r83938  
    122122    void updateDOMNodeDocument(Node*, Document* oldDocument, Document* newDocument);
    123123
    124     void markDOMNodesForDocument(JSC::MarkStack&, Document*);
    125124    void markActiveObjectsForContext(JSC::MarkStack&, JSC::JSGlobalData&, ScriptExecutionContext*);
    126125    void markDOMObjectWrapper(JSC::MarkStack&, JSC::JSGlobalData& globalData, void* object);
    127     void markDOMNodeWrapper(JSC::MarkStack& markStack, Document* document, Node* node);
    128126    bool hasCachedDOMObjectWrapperUnchecked(JSC::JSGlobalData*, void* objectHandle);
    129127    bool hasCachedDOMNodeWrapperUnchecked(Document*, Node*);
  • trunk/Source/WebCore/bindings/js/JSDOMImplementationCustom.cpp

    r79225 r83938  
    3434    Base::markChildren(markStack);
    3535
    36     DOMImplementation* domImplementation = impl();
    37     Document* ownerDocument = domImplementation->ownerDocument();
    38     if (ownerDocument)
    39         markDOMNodeWrapper(markStack, ownerDocument, ownerDocument);
     36    Document* ownerDocument = impl()->ownerDocument();
     37    if (!ownerDocument)
     38        return;
     39    markStack.addOpaqueRoot(ownerDocument);
    4040}
    4141
  • trunk/Source/WebCore/bindings/js/JSDocumentCustom.cpp

    r76600 r83938  
    5656    JSGlobalData& globalData = *Heap::heap(this)->globalData();
    5757
    58     markDOMNodesForDocument(markStack, document);
    5958    markActiveObjectsForContext(markStack, globalData, document);
    6059    markDOMObjectWrapper(markStack, globalData, document->implementation());
  • trunk/Source/WebCore/bindings/js/JSNamedNodeMapCustom.cpp

    r60022 r83938  
    5151    Base::markChildren(markStack);
    5252
    53     // Mark the element so that this will work to access the attribute even if the last
    54     // other reference goes away.
    55     if (Element* element = impl()->element())
    56         markDOMNodeWrapper(markStack, element->document(), element);
     53    Element* element = impl()->element();
     54    if (!element)
     55        return;
     56    markStack.addOpaqueRoot(root(element));
    5757}
    5858
  • trunk/Source/WebCore/bindings/js/JSNodeCustom.cpp

    r79904 r83938  
    125125    node->markJSEventListeners(markStack);
    126126
    127     // Nodes in the document are kept alive by JSDocument::mark, so, if we're in
    128     // the document, we need to mark the document, but we don't need to explicitly
    129     // mark any other nodes.
    130     if (node->inDocument()) {
    131         // FIXME: Do we really want to call a virtual function, ownerDocument here,
    132         // when the non-virtual inline function, document, is so much faster?!
    133         if (Document* doc = node->ownerDocument())
    134             markDOMNodeWrapper(markStack, doc, doc);
    135         return;
    136     }
    137 
    138     // This is a node outside the document.
    139     // Find the the root, and the highest ancestor with a wrapper.
    140     Node* root = node;
    141     Node* outermostNodeWithWrapper = node;
    142     for (Node* current = m_impl.get(); current; current = current->parentNode()) {
    143         root = current;
    144         if (hasCachedDOMNodeWrapperUnchecked(current->document(), current))
    145             outermostNodeWithWrapper = current;
    146     }
    147 
    148     // Only nodes that have no ancestors with wrappers mark the subtree. In the common
    149     // case, the root of the detached subtree has a wrapper, so the tree will only
    150     // get marked once. Nodes that aren't outermost need to mark the outermost
    151     // in case it is otherwise unreachable.
    152     // FIXME: In the non-common case of root not having a wrapper, this is still an O(n^2) algorithm,
    153     // as we will traverse the whole tree as many times as there are nodes with wrappers in it.
    154     if (node != outermostNodeWithWrapper) {
    155         markDOMNodeWrapper(markStack, m_impl->document(), outermostNodeWithWrapper);
    156         return;
    157     }
    158 
    159     // Mark the whole tree subtree.
    160     for (Node* nodeToMark = root; nodeToMark; nodeToMark = nodeToMark->traverseNextNode())
    161         markDOMNodeWrapper(markStack, m_impl->document(), nodeToMark);
     127    markStack.addOpaqueRoot(root(node));
    162128}
    163129
  • trunk/Source/WebCore/bindings/js/JSNodeCustom.h

    r83773 r83938  
    5858}
    5959
     60static inline Node* root(Node* node)
     61{
     62    if (node->inDocument())
     63        return node->document();
     64
     65    while (node->parentNode())
     66        node = node->parentNode();
     67    return node;
     68}
     69
    6070}
    6171
  • trunk/Source/WebCore/bindings/js/JSSVGElementInstanceCustom.cpp

    r58960 r83938  
    2929
    3030#if ENABLE(SVG)
     31#include "JSNode.h"
    3132#include "SVGElementInstance.h"
    3233
     
    3637{
    3738    Base::markChildren(markStack);
    38 
    39     // Mark the wrapper for our corresponding element, so it can mark its event handlers.
    40     markDOMNodeWrapper(markStack, impl()->correspondingElement()->document(), impl()->correspondingElement());
     39    markStack.addOpaqueRoot(root(impl()->correspondingElement()));
    4140}
    4241
Note: See TracChangeset for help on using the changeset viewer.