Changeset 28106 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Nov 28, 2007, 2:08:09 AM (18 years ago)
Author:
[email protected]
Message:

JavaScriptCore:

Reviewed by Darin and Geoff.


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 an 0.4% SunSpider 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: Export new symbols.
  • JavaScriptCore.xcodeproj/project.pbxproj: Add new file.
  • kjs/collector.cpp: (KJS::Collector::heapAllocate): (KJS::drainMarkStack): Helper for all of the below. (KJS::Collector::markStackObjectsConservatively): Use mark stack. (KJS::Collector::markCurrentThreadConservatively): ditto (KJS::Collector::markOtherThreadConservatively): ditto (KJS::Collector::markProtectedObjects): ditto (KJS::Collector::markMainThreadOnlyObjects): ditto (KJS::Collector::collect): ditto
  • kjs/collector.h: (KJS::Collector::cellMayHaveRefs): Helper for MarkStack.
  • kjs/MarkStack.h: Added. The actual mark stack implementation. (KJS::MarkStack::push): (KJS::MarkStack::pushAtom): (KJS::MarkStack::pop): (KJS::MarkStack::isEmpty): (KJS::MarkStack::reserveCapacity):

Changed mark() methods to markChildren() methods:


  • 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/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:

JavaScriptGlue:

Reviewed by Darin and Geoff.

Fixups for JavaScriptCore mark stack.

  • JSObject.cpp: (JSUserObject::Mark):
  • JSObject.h:
  • JSValueWrapper.cpp: (JSValueWrapper::JSObjectMark):
  • JSValueWrapper.h:
  • UserObjectImp.cpp:
  • UserObjectImp.h:

WebCore:

Reviewed by Darin and Geoff.

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:

LayoutTests:

Not reviewed.


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.
Location:
trunk/JavaScriptCore
Files:
30 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r28103 r28106  
     12007-11-28  Maciej Stachowiak  <[email protected]>
     2
     3        Reviewed by Darin and Geoff.
     4
     5        - Fixed "Stack overflow crash in JavaScript garbage collector mark pass"
     6        http://bugs.webkit.org/show_bug.cgi?id=12216
     7       
     8        Implement mark stack. This version is not suitable for prime time because it makes a
     9        huge allocation on every collect, and potentially makes marking of detached subtrees
     10        slow. But it is an 0.4% SunSpider speedup even without much tweaking.
     11       
     12        The basic approach is to replace mark() methods with
     13        markChildren(MarkStack&) methods. Reachable references are pushed
     14        onto a mark stack (which encapsulates ignoring already-marked
     15        references).
     16       
     17        Objects are no longer responsible for actually setting their own
     18        mark bits, the collector does that. This means that for objects on
     19        the number heap we don't have to call markChildren() at all since
     20        we know there aren't any.
     21       
     22        The mark phase of collect pushes roots onto the mark stack
     23        and drains it as often as possible.
     24       
     25        To make this approach viable requires a constant-size mark stack
     26        and a slow fallback approach for when the stack size is exceeded,
     27        plus optimizations to make the required stack small in common
     28        cases. This should be doable.
     29
     30        * JavaScriptCore.exp: Export new symbols.
     31        * JavaScriptCore.xcodeproj/project.pbxproj: Add new file.
     32        * kjs/collector.cpp:
     33        (KJS::Collector::heapAllocate):
     34        (KJS::drainMarkStack): Helper for all of the below.
     35        (KJS::Collector::markStackObjectsConservatively): Use mark stack.
     36        (KJS::Collector::markCurrentThreadConservatively): ditto
     37        (KJS::Collector::markOtherThreadConservatively): ditto
     38        (KJS::Collector::markProtectedObjects): ditto
     39        (KJS::Collector::markMainThreadOnlyObjects): ditto
     40        (KJS::Collector::collect): ditto
     41        * kjs/collector.h:
     42        (KJS::Collector::cellMayHaveRefs): Helper for MarkStack.
     43
     44        * kjs/MarkStack.h: Added. The actual mark stack implementation.
     45        (KJS::MarkStack::push):
     46        (KJS::MarkStack::pushAtom):
     47        (KJS::MarkStack::pop):
     48        (KJS::MarkStack::isEmpty):
     49        (KJS::MarkStack::reserveCapacity):
     50
     51        Changed mark() methods to markChildren() methods:
     52       
     53        * kjs/ExecState.cpp:
     54        (KJS::ExecState::markChildren):
     55        * kjs/ExecState.h:
     56        * kjs/JSWrapperObject.cpp:
     57        (KJS::JSWrapperObject::markChildren):
     58        * kjs/JSWrapperObject.h:
     59        * kjs/array_instance.cpp:
     60        (KJS::ArrayInstance::markChildren):
     61        * kjs/array_instance.h:
     62        * kjs/bool_object.cpp:
     63        (BooleanInstance::markChildren):
     64        * kjs/bool_object.h:
     65        * kjs/error_object.cpp:
     66        * kjs/error_object.h:
     67        * kjs/function.cpp:
     68        (KJS::FunctionImp::markChildren):
     69        (KJS::Arguments::Arguments):
     70        (KJS::Arguments::markChildren):
     71        (KJS::ActivationImp::markChildren):
     72        * kjs/function.h:
     73        * kjs/internal.cpp:
     74        (KJS::GetterSetterImp::markChildren):
     75        * kjs/interpreter.cpp:
     76        (KJS::Interpreter::markRoots):
     77        * kjs/interpreter.h:
     78        * kjs/list.cpp:
     79        (KJS::List::markProtectedListsSlowCase):
     80        * kjs/list.h:
     81        (KJS::List::markProtectedLists):
     82        * kjs/object.cpp:
     83        (KJS::JSObject::markChildren):
     84        * kjs/object.h:
     85        (KJS::ScopeChain::markChildren):
     86        * kjs/property_map.cpp:
     87        (KJS::PropertyMap::markChildren):
     88        * kjs/property_map.h:
     89        * kjs/scope_chain.h:
     90        * kjs/string_object.cpp:
     91        (KJS::StringInstance::markChildren):
     92        * kjs/string_object.h:
     93
    1942007-11-27  Alp Toker  <[email protected]>
    295

  • trunk/JavaScriptCore/JavaScriptCore.exp

    r27885 r28106  
    123123__ZN3KJS11Interpreter24setShouldPrintExceptionsEb
    124124__ZN3KJS11Interpreter27resetGlobalObjectPropertiesEv
    125 __ZN3KJS11Interpreter4markEv
    126125__ZN3KJS11Interpreter6s_hookE
    127126__ZN3KJS11Interpreter8evaluateERKNS_7UStringEiPKNS_5UCharEiPNS_7JSValueE
    128127__ZN3KJS11Interpreter8evaluateERKNS_7UStringEiS3_PNS_7JSValueE
     128__ZN3KJS11Interpreter9markRootsERNS_9MarkStackE
    129129__ZN3KJS11InterpreterC1Ev
    130130__ZN3KJS11InterpreterC2Ev
    … …  
    145145__ZN3KJS13SavedBuiltinsD1Ev
    146146__ZN3KJS13jsOwnedStringERKNS_7UStringE
     147__ZN3KJS14StringInstance12markChildrenERNS_9MarkStackE
    147148__ZN3KJS14StringInstance14deletePropertyEPNS_9ExecStateERKNS_10IdentifierE
    148149__ZN3KJS14StringInstance16getPropertyNamesEPNS_9ExecStateERNS_17PropertyNameArrayE
    … …  
    153154__ZN3KJS14StringInstanceC1EPNS_8JSObjectERKNS_7UStringE
    154155__ZN3KJS14StringInstanceC2EPNS_8JSObjectERKNS_7UStringE
    155 __ZN3KJS15JSWrapperObject4markEv
    156156__ZN3KJS15SavedPropertiesC1Ev
    157157__ZN3KJS15SavedPropertiesD1Ev
    … …  
    202202__ZN3KJS8DebuggerD2Ev
    203203__ZN3KJS8JSObject11hasInstanceEPNS_9ExecStateEPNS_7JSValueE
     204__ZN3KJS8JSObject12markChildrenERNS_9MarkStackE
    204205__ZN3KJS8JSObject12removeDirectERKNS_10IdentifierE
    205206__ZN3KJS8JSObject14callAsFunctionEPNS_9ExecStateEPS0_RKNS_4ListE
    … …  
    213214__ZN3KJS8JSObject3putEPNS_9ExecStateEjPNS_7JSValueEi
    214215__ZN3KJS8JSObject4callEPNS_9ExecStateEPS0_RKNS_4ListE
    215 __ZN3KJS8JSObject4markEv
    216216__ZN3KJS8JSObject9constructEPNS_9ExecStateERKNS_4ListE
    217217__ZN3KJS8JSObject9constructEPNS_9ExecStateERKNS_4ListERKNS_10IdentifierERKNS_7UStringEi

  • trunk/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj

    r27845 r28106  
    100100                6592C319098B7DE10003D4F6 /* VectorTraits.h in Headers */ = {isa = PBXBuildFile; fileRef = 6592C317098B7DE10003D4F6 /* VectorTraits.h */; settings = {ATTRIBUTES = (Private, ); }; };
    101101                65A7A5E00CD1D50E00061F8E /* LabelStack.h in Headers */ = {isa = PBXBuildFile; fileRef = 65B813A80CD1D01900DF59D6 /* LabelStack.h */; settings = {ATTRIBUTES = (Private, ); }; };
     102                65A8B8DB0CF408F400DC7C27 /* MarkStack.h in Headers */ = {isa = PBXBuildFile; fileRef = 65A8B8D80CF408E900DC7C27 /* MarkStack.h */; settings = {ATTRIBUTES = (Private, ); }; };
    102103                65B1749A09D0FEB700820339 /* array_object.lut.h in Headers */ = {isa = PBXBuildFile; fileRef = 65B1749909D0FEB700820339 /* array_object.lut.h */; };
    103104                65B174F509D100FA00820339 /* math_object.lut.h in Headers */ = {isa = PBXBuildFile; fileRef = 65B174F109D100FA00820339 /* math_object.lut.h */; };
    … …  
    511512                6592C316098B7DE10003D4F6 /* Vector.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = Vector.h; sourceTree = "<group>"; };
    512513                6592C317098B7DE10003D4F6 /* VectorTraits.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = VectorTraits.h; sourceTree = "<group>"; };
     514                65A8B8D80CF408E900DC7C27 /* MarkStack.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = MarkStack.h; sourceTree = "<group>"; };
    513515                65B1749909D0FEB700820339 /* array_object.lut.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = file; name = array_object.lut.h; path = ../../../../../symroots/Debug/DerivedSources/JavaScriptCore/array_object.lut.h; sourceTree = "<group>"; };
    514516                65B174BE09D1000200820339 /* chartables.c */ = {isa = PBXFileReference; explicitFileType = sourcecode.c.c; fileEncoding = 30; path = chartables.c; sourceTree = "<group>"; };
    … …  
    10091011                                F692A8690255597D01FF60F7 /* lookup.h */,
    10101012                                F692A86A0255597D01FF60F7 /* math_object.cpp */,
     1013                                65A8B8D80CF408E900DC7C27 /* MarkStack.h */,
    10111014                                F692A86B0255597D01FF60F7 /* math_object.h */,
    10121015                                F692A86D0255597D01FF60F7 /* nodes.cpp */,
    … …  
    11711174                                65F340940CD6C1C000C0CA8B /* LocalStorage.h in Headers */,
    11721175                                5DBD18B00C5401A700C15EAE /* MallocZoneSupport.h in Headers */,
     1176                                65A8B8DB0CF408F400DC7C27 /* MarkStack.h in Headers */,
    11731177                                BCF655590A2049710038A194 /* MathExtras.h in Headers */,
    11741178                                932F5B840822A1C700736975 /* NP_jsobject.h in Headers */,

  • trunk/JavaScriptCore/kjs/ExecState.cpp

    r27885 r28106  
    8989}
    9090
    91 void ExecState::mark()
     91void ExecState::markChildren(MarkStack& stack)
    9292{
    9393    for (ExecState* exec = this; exec; exec = exec->m_callingExecState)
    94         exec->m_scopeChain.mark();
     94        exec->m_scopeChain.markChildren(stack);
    9595}
    9696

  • trunk/JavaScriptCore/kjs/ExecState.h

    r27885 r28106  
    101101        void setGlobalObject(JSGlobalObject*);
    102102       
    103         void mark();
     103        void markChildren(MarkStack&);
    104104       
    105105        // This is a workaround to avoid accessing the global variables for these identifiers in

  • trunk/JavaScriptCore/kjs/JSWrapperObject.cpp

    r15846 r28106  
    2525namespace KJS {
    2626
    27 void JSWrapperObject::mark()
     27void JSWrapperObject::markChildren(MarkStack& stack)
    2828{
    29     JSObject::mark();
    30     if (m_internalValue && !m_internalValue->marked())
    31         m_internalValue->mark();
     29    JSObject::markChildren(stack);
     30    stack.pushAtom(m_internalValue);
    3231}
    3332

  • trunk/JavaScriptCore/kjs/JSWrapperObject.h

    r15846 r28106  
    5757        void setInternalValue(JSValue* v);
    5858       
    59         virtual void mark();
     59        virtual void markChildren(MarkStack& stack);
    6060       
    6161    private:
    … …  
    6565    inline JSWrapperObject::JSWrapperObject(JSValue* proto)
    6666        : JSObject(proto)
    67         , m_internalValue(0)
     67        , m_internalValue(jsNull())
    6868    {
    6969    }

  • trunk/JavaScriptCore/kjs/array_instance.cpp

    r27711 r28106  
    403403}
    404404
    405 void ArrayInstance::mark()
    406 {
    407     JSObject::mark();
     405void ArrayInstance::markChildren(MarkStack& stack)
     406{
     407    JSObject::markChildren(stack);
    408408
    409409    ArrayStorage* storage = m_storage;
    … …  
    412412    for (unsigned i = 0; i < usedVectorLength; ++i) {
    413413        JSValue* value = storage->m_vector[i];
    414         if (value && !value->marked())
    415             value->mark();
     414        if (value)
     415            stack.push(value);
    416416    }
    417417
    418418    if (SparseArrayValueMap* map = storage->m_sparseValueMap) {
    419419        SparseArrayValueMap::iterator end = map->end();
    420         for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it) {
    421             JSValue* value = it->second;
    422             if (!value->marked())
    423                 value->mark();
    424         }
     420        for (SparseArrayValueMap::iterator it = map->begin(); it != end; ++it)
     421            stack.push(it->second);
    425422    }
    426423}

  • trunk/JavaScriptCore/kjs/array_instance.h

    r26881 r28106  
    4343    virtual void getPropertyNames(ExecState*, PropertyNameArray&);
    4444
    45     virtual void mark();
     45    virtual void markChildren(MarkStack&);
    4646
    4747    virtual const ClassInfo* classInfo() const { return &info; }

  • trunk/JavaScriptCore/kjs/bool_object.cpp

    r27448 r28106  
    3737  : JSWrapperObject(proto)
    3838{
     39}
     40
     41void BooleanInstance::markChildren(MarkStack& stack)
     42{
     43    JSObject::markChildren(stack);
     44    ASSERT(JSImmediate::isImmediate(internalValue()));
    3945}
    4046

  • trunk/JavaScriptCore/kjs/bool_object.h

    r15846 r28106  
    3333
    3434    virtual const ClassInfo *classInfo() const { return &info; }
     35    virtual void markChildren(MarkStack& stack);
    3536    static const ClassInfo info;
    3637  };

  • trunk/JavaScriptCore/kjs/collector.cpp

    r27574 r28106  
    2727#include "internal.h"
    2828#include "list.h"
     29#include "MarkStack.h"
    2930#include "value.h"
    3031#include <algorithm>
    … …  
    278279    targetBlock = (Block*)allocateBlock();
    279280    targetBlock->freeList = targetBlock->cells;
     281    if (heapType == PrimaryHeap)
     282        targetBlock->mayHaveRefs = 1;
    280283    targetBlockUsedCells = 0;
    281284    heap.blocks[usedBlocks] = (CollectorBlock*)targetBlock;
    … …  
    480483#define IS_HALF_CELL_ALIGNED(p) (((intptr_t)(p) & (CELL_MASK >> 1)) == 0)
    481484
    482 void Collector::markStackObjectsConservatively(void *start, void *end)
     485static inline void drainMarkStack(MarkStack& stack)
     486{
     487    while (!stack.isEmpty())
     488        stack.pop()->markChildren(stack);
     489}
     490
     491
     492void Collector::markStackObjectsConservatively(MarkStack& stack, void *start, void *end)
    483493{
    484494  if (start > end) {
    … …  
    522532                  if (((CollectorCell*)xAsBits)->u.freeCell.zeroIfFree != 0) {
    523533                      JSCell* imp = reinterpret_cast<JSCell*>(xAsBits);
    524                       if (!imp->marked())
    525                           imp->mark();
     534                      stack.push(imp);
     535                      drainMarkStack(stack);
    526536                  }
    527537                  break;
    … …  
    534544}
    535545
    536 void Collector::markCurrentThreadConservatively()
     546void Collector::markCurrentThreadConservatively(MarkStack& stack)
    537547{
    538548    // setjmp forces volatile registers onto the stack
    … …  
    551561    void* stackBase = currentThreadStackBase();
    552562
    553     markStackObjectsConservatively(stackPointer, stackBase);
     563    markStackObjectsConservatively(stack, stackPointer, stackBase);
    554564}
    555565
    … …  
    694704}
    695705
    696 void Collector::markOtherThreadConservatively(Thread* thread)
     706void Collector::markOtherThreadConservatively(MarkStack& stack, Thread* thread)
    697707{
    698708  suspendThread(thread->platformThread);
    … …  
    702712
    703713  // mark the thread's registers
    704   markStackObjectsConservatively((void*)&regs, (void*)((char*)&regs + regSize));
     714  markStackObjectsConservatively(stack, (void*)&regs, (void*)((char*)&regs + regSize));
    705715 
    706716  void* stackPointer = otherThreadStackPointer(regs);
    707717  void* stackBase = otherThreadStackBase(regs, thread);
    708   markStackObjectsConservatively(stackPointer, stackBase);
     718  markStackObjectsConservatively(stack, stackPointer, stackBase);
    709719
    710720  resumeThread(thread->platformThread);
    … …  
    713723#endif
    714724
    715 void Collector::markStackObjectsConservatively()
    716 {
    717   markCurrentThreadConservatively();
     725void Collector::markStackObjectsConservatively(MarkStack& stack)
     726{
     727  markCurrentThreadConservatively(stack);
    718728
    719729#if USE(MULTIPLE_THREADS)
    720730  for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
    721731    if (!pthread_equal(thread->posixThread, pthread_self())) {
    722       markOtherThreadConservatively(thread);
     732        markOtherThreadConservatively(stack, thread);
    723733    }
    724734  }
    … …  
    772782}
    773783
    774 void Collector::markProtectedObjects()
     784void Collector::markProtectedObjects(MarkStack& stack)
    775785{
    776786  ProtectCountSet& protectedValues = KJS::protectedValues();
    777787  ProtectCountSet::iterator end = protectedValues.end();
    778788  for (ProtectCountSet::iterator it = protectedValues.begin(); it != end; ++it) {
    779     JSCell *val = it->first;
    780     if (!val->marked())
    781       val->mark();
    782   }
    783 }
    784 
    785 void Collector::markMainThreadOnlyObjects()
     789    stack.push(it->first);
     790    drainMarkStack(stack);
     791  }
     792}
     793
     794void Collector::markMainThreadOnlyObjects(MarkStack& stack)
    786795{
    787796#if USE(MULTIPLE_THREADS)
    … …  
    815824                    if (!curBlock->marked.get(i)) {
    816825                        JSCell* imp = reinterpret_cast<JSCell*>(cell);
    817                         imp->mark();
     826                        stack.push(imp);
     827                        drainMarkStack(stack);
    818828                    }
    819829                    if (++count == mainThreadOnlyObjectCount)
    … …  
    951961  // MARK: first mark all referenced objects recursively starting out from the set of root objects
    952962
     963  size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
     964
     965  MarkStack stack;
     966  stack.reserveCapacity(primaryHeap.numLiveObjects);
     967
    953968#ifndef NDEBUG
    954969  // Forbid malloc during the mark phase. Marking a thread suspends it, so
    955   // a malloc inside mark() would risk a deadlock with a thread that had been
     970  // a malloc inside markChildren() would risk a deadlock with a thread that had been
    956971  // suspended while holding the malloc lock.
    957972  fastMallocForbid();
    … …  
    961976    Interpreter* scr = Interpreter::s_hook;
    962977    do {
    963       scr->mark();
     978      scr->markRoots(stack);
     979      drainMarkStack(stack);
    964980      scr = scr->next;
    965981    } while (scr != Interpreter::s_hook);
    966982  }
    967983
    968   markStackObjectsConservatively();
    969   markProtectedObjects();
    970   List::markProtectedLists();
     984  markStackObjectsConservatively(stack);
     985  markProtectedObjects(stack);
     986  List::markProtectedLists(stack);
     987  drainMarkStack(stack);
    971988#if USE(MULTIPLE_THREADS)
    972989  if (!currentThreadIsMainThread)
    973     markMainThreadOnlyObjects();
     990    markMainThreadOnlyObjects(stack);
    974991#endif
    975992
    … …  
    978995#endif
    979996   
    980   size_t originalLiveObjects = primaryHeap.numLiveObjects + numberHeap.numLiveObjects;
    981997  size_t numLiveObjects = sweep<PrimaryHeap>(currentThreadIsMainThread);
    982998  numLiveObjects += sweep<NumberHeap>(currentThreadIsMainThread);

  • trunk/JavaScriptCore/kjs/collector.h

    r27298 r28106  
    3232namespace KJS {
    3333
     34  class CollectorBlock;
    3435  class JSCell;
    3536  class JSValue;
    36   class CollectorBlock;
     37  class MarkStack;
    3738
    3839  class Collector {
    … …  
    6667    static bool isCellMarked(const JSCell*);
    6768    static void markCell(JSCell*);
     69    static bool cellMayHaveRefs(const JSCell*);
    6870
    6971    enum HeapType { PrimaryHeap, NumberHeap };
    … …  
    7981
    8082    static void recordExtraCost(size_t);
    81     static void markProtectedObjects();
    82     static void markMainThreadOnlyObjects();
    83     static void markCurrentThreadConservatively();
    84     static void markOtherThreadConservatively(Thread*);
    85     static void markStackObjectsConservatively();
    86     static void markStackObjectsConservatively(void* start, void* end);
     83    static void markProtectedObjects(MarkStack&);
     84    static void markMainThreadOnlyObjects(MarkStack&);
     85    static void markCurrentThreadConservatively(MarkStack&);
     86    static void markOtherThreadConservatively(MarkStack&, Thread*);
     87    static void markStackObjectsConservatively(MarkStack&);
     88    static void markStackObjectsConservatively(MarkStack&, void* start, void* end);
    8789
    8890    static size_t mainThreadOnlyObjectCount;
    … …  
    108110  const size_t CELL_MASK = CELL_SIZE - 1;
    109111  const size_t CELL_ALIGN_MASK = ~CELL_MASK;
    110   const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
     112  const size_t CELLS_PER_BLOCK = (BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8 - 2 * (7 + 3 * 8)) / (CELL_SIZE * 8 + 2);
    111113  const size_t SMALL_CELLS_PER_BLOCK = 2 * CELLS_PER_BLOCK;
    112114  const size_t BITMAP_SIZE = (CELLS_PER_BLOCK + 7) / 8;
    … …  
    146148    uint32_t usedCells;
    147149    CollectorCell* freeList;
     150    uint32_t mayHaveRefs;
    148151    CollectorBitmap marked;
    149152    CollectorBitmap collectOnMainThreadOnly;
    … …  
    155158    uint32_t usedCells;
    156159    SmallCollectorCell* freeList;
     160    uint32_t mayHaveRefs;
    157161    CollectorBitmap marked;
    158162    CollectorBitmap collectOnMainThreadOnly;
    … …  
    182186  {
    183187    cellBlock(cell)->marked.set(cellOffset(cell));
     188  }
     189
     190  inline bool Collector::cellMayHaveRefs(const JSCell* cell)
     191  {
     192    return cellBlock(cell)->mayHaveRefs;
    184193  }
    185194

  • trunk/JavaScriptCore/kjs/error_object.cpp

    r27413 r28106  
    157157}
    158158
    159 void NativeErrorImp::mark()
    160 {
    161   JSObject::mark();
    162   if (proto && !proto->marked())
    163     proto->mark();
    164 }

  • trunk/JavaScriptCore/kjs/error_object.h

    r13821 r28106  
    7676    virtual JSValue *callAsFunction(ExecState *exec, JSObject *thisObj, const List &args);
    7777
    78     virtual void mark();
    79 
    8078    virtual const ClassInfo *classInfo() const { return &info; }
    8179    static const ClassInfo info;

  • trunk/JavaScriptCore/kjs/function.cpp

    r28053 r28106  
    6262}
    6363
    64 void FunctionImp::mark()
    65 {
    66     InternalFunctionImp::mark();
    67     _scope.mark();
     64void FunctionImp::markChildren(MarkStack& stack)
     65{
     66    InternalFunctionImp::markChildren(stack);
     67    _scope.markChildren(stack);
    6868}
    6969
    … …  
    332332// ECMA 10.1.8
    333333Arguments::Arguments(ExecState* exec, FunctionImp* func, const List& args, ActivationImp* act)
    334 : JSObject(exec->lexicalInterpreter()->builtinObjectPrototype()),
    335 _activationObject(act),
    336 indexToNameMap(func, args)
     334  : JSObject(exec->lexicalInterpreter()->builtinObjectPrototype())
     335  , _activationObject(act)
     336  , indexToNameMap(func, args)
    337337{
    338338  putDirect(exec->propertyNames().callee, func, DontEnum);
    … …  
    348348}
    349349
    350 void Arguments::mark()
    351 {
    352   JSObject::mark();
    353   if (_activationObject && !_activationObject->marked())
    354     _activationObject->mark();
     350void Arguments::markChildren(MarkStack& stack)
     351{
     352  JSObject::markChildren(stack);
     353  stack.push(_activationObject);
    355354}
    356355
    … …  
    485484}
    486485
    487 void ActivationImp::mark()
    488 {
    489     JSObject::mark();
     486void ActivationImp::markChildren(MarkStack& stack)
     487{
     488    JSObject::markChildren(stack);
    490489
    491490    size_t size = d->localStorage.size();
    492     for (size_t i = 0; i < size; ++i) {
    493         JSValue* value = d->localStorage[i].value;
    494         if (!value->marked())
    495             value->mark();
    496     }
     491    for (size_t i = 0; i < size; ++i)
     492        stack.push(d->localStorage[i].value);
    497493   
    498     ASSERT(d->function);
    499     if (!d->function->marked())
    500         d->function->mark();
    501 
    502     if (d->argumentsObject && !d->argumentsObject->marked())
    503         d->argumentsObject->mark();
     494    stack.push(d->function);
     495    if (d->argumentsObject)
     496      stack.push(d->argumentsObject);
    504497}
    505498

  • trunk/JavaScriptCore/kjs/function.h

    r28053 r28106  
    9696    const ScopeChain& scope() const { return _scope; }
    9797
    98     virtual void mark();
     98    virtual void markChildren(MarkStack&);
    9999
    100100  private:
    … …  
    125125  public:
    126126    Arguments(ExecState*, FunctionImp* func, const List& args, ActivationImp* act);
    127     virtual void mark();
     127    virtual void markChildren(MarkStack&);
    128128    virtual bool getOwnPropertySlot(ExecState*, const Identifier&, PropertySlot&);
    129129    virtual void put(ExecState*, const Identifier& propertyName, JSValue* value, int attr = None);
    … …  
    165165    static const ClassInfo info;
    166166
    167     virtual void mark();
     167    virtual void markChildren(MarkStack&);
    168168
    169169    bool isActivation() { return true; }

  • trunk/JavaScriptCore/kjs/internal.cpp

    r27695 r28106  
    145145
    146146// --------------------------- GetterSetterImp ---------------------------------
    147 void GetterSetterImp::mark()
    148 {
    149     JSCell::mark();
    150    
    151     if (getter && !getter->marked())
    152         getter->mark();
    153     if (setter && !setter->marked())
    154         setter->mark();
     147void GetterSetterImp::markChildren(MarkStack& stack)
     148{
     149    if (getter)
     150        stack.push(getter);
     151    if (setter)
     152        stack.push(setter);
    155153}
    156154

  • trunk/JavaScriptCore/kjs/interpreter.cpp

    r27885 r28106  
    545545}
    546546
    547 void Interpreter::mark()
     547void Interpreter::markRoots(MarkStack& stack)
    548548{
    549549    if (m_currentExec)
    550         m_currentExec->mark();
    551 
    552     if (m_globalExec.exception() && !m_globalExec.exception()->marked())
    553         m_globalExec.exception()->mark();
    554 
    555     if (m_globalObject && !m_globalObject->marked())
    556         m_globalObject->mark();
    557 
    558     if (m_Object && !m_Object->marked())
    559         m_Object->mark();
    560     if (m_Function && !m_Function->marked())
    561         m_Function->mark();
    562     if (m_Array && !m_Array->marked())
    563         m_Array->mark();
    564     if (m_Boolean && !m_Boolean->marked())
    565         m_Boolean->mark();
    566     if (m_String && !m_String->marked())
    567         m_String->mark();
    568     if (m_Number && !m_Number->marked())
    569         m_Number->mark();
    570     if (m_Date && !m_Date->marked())
    571         m_Date->mark();
    572     if (m_RegExp && !m_RegExp->marked())
    573         m_RegExp->mark();
    574     if (m_Error && !m_Error->marked())
    575         m_Error->mark();
    576    
    577     if (m_ObjectPrototype && !m_ObjectPrototype->marked())
    578         m_ObjectPrototype->mark();
    579     if (m_FunctionPrototype && !m_FunctionPrototype->marked())
    580         m_FunctionPrototype->mark();
    581     if (m_ArrayPrototype && !m_ArrayPrototype->marked())
    582         m_ArrayPrototype->mark();
    583     if (m_BooleanPrototype && !m_BooleanPrototype->marked())
    584         m_BooleanPrototype->mark();
    585     if (m_StringPrototype && !m_StringPrototype->marked())
    586         m_StringPrototype->mark();
    587     if (m_NumberPrototype && !m_NumberPrototype->marked())
    588         m_NumberPrototype->mark();
    589     if (m_DatePrototype && !m_DatePrototype->marked())
    590         m_DatePrototype->mark();
    591     if (m_RegExpPrototype && !m_RegExpPrototype->marked())
    592         m_RegExpPrototype->mark();
    593     if (m_ErrorPrototype && !m_ErrorPrototype->marked())
    594         m_ErrorPrototype->mark();
    595    
    596     if (m_EvalError && !m_EvalError->marked())
    597         m_EvalError->mark();
    598     if (m_RangeError && !m_RangeError->marked())
    599         m_RangeError->mark();
    600     if (m_ReferenceError && !m_ReferenceError->marked())
    601         m_ReferenceError->mark();
    602     if (m_SyntaxError && !m_SyntaxError->marked())
    603         m_SyntaxError->mark();
    604     if (m_TypeError && !m_TypeError->marked())
    605         m_TypeError->mark();
    606     if (m_UriError && !m_UriError->marked())
    607         m_UriError->mark();
    608    
    609     if (m_EvalErrorPrototype && !m_EvalErrorPrototype->marked())
    610         m_EvalErrorPrototype->mark();
    611     if (m_RangeErrorPrototype && !m_RangeErrorPrototype->marked())
    612         m_RangeErrorPrototype->mark();
    613     if (m_ReferenceErrorPrototype && !m_ReferenceErrorPrototype->marked())
    614         m_ReferenceErrorPrototype->mark();
    615     if (m_SyntaxErrorPrototype && !m_SyntaxErrorPrototype->marked())
    616         m_SyntaxErrorPrototype->mark();
    617     if (m_TypeErrorPrototype && !m_TypeErrorPrototype->marked())
    618         m_TypeErrorPrototype->mark();
    619     if (m_UriErrorPrototype && !m_UriErrorPrototype->marked())
    620         m_UriErrorPrototype->mark();
     550        m_currentExec->markChildren(stack);
     551
     552    if (m_globalExec.exception())
     553        stack.push(m_globalExec.exception());
     554
     555    if (m_globalObject)
     556        stack.push(m_globalObject);
     557
     558    if (m_Object)
     559       stack.push(m_Object);
     560    if (m_Function)
     561        stack.push(m_Function);
     562    if (m_Array)
     563        stack.push(m_Array);
     564    if (m_Boolean)
     565        stack.push(m_Boolean);
     566    if (m_String)
     567        stack.push(m_String);
     568    if (m_Number)
     569        stack.push(m_Number);
     570    if (m_Date)
     571        stack.push(m_Date);
     572    if (m_RegExp)
     573        stack.push(m_RegExp);
     574    if (m_Error)
     575        stack.push(m_Error);
     576   
     577    if (m_ObjectPrototype)
     578        stack.push(m_ObjectPrototype);
     579    if (m_FunctionPrototype)
     580        stack.push(m_FunctionPrototype);
     581    if (m_ArrayPrototype)
     582        stack.push(m_ArrayPrototype);
     583    if (m_BooleanPrototype)
     584        stack.push(m_BooleanPrototype);
     585    if (m_StringPrototype)
     586        stack.push(m_StringPrototype);
     587    if (m_NumberPrototype)
     588        stack.push(m_NumberPrototype);
     589    if (m_DatePrototype)
     590        stack.push(m_DatePrototype);
     591    if (m_RegExpPrototype)
     592        stack.push(m_RegExpPrototype);
     593    if (m_ErrorPrototype)
     594        stack.push(m_ErrorPrototype);
     595   
     596    if (m_EvalError)
     597        stack.push(m_EvalError);
     598    if (m_RangeError)
     599        stack.push(m_RangeError);
     600    if (m_ReferenceError)
     601        stack.push(m_ReferenceError);
     602    if (m_SyntaxError)
     603        stack.push(m_SyntaxError);
     604    if (m_TypeError)
     605        stack.push(m_TypeError);
     606    if (m_UriError)
     607        stack.push(m_UriError);
     608   
     609    if (m_EvalErrorPrototype)
     610        stack.push(m_EvalErrorPrototype);
     611    if (m_RangeErrorPrototype)
     612        stack.push(m_RangeErrorPrototype);
     613    if (m_ReferenceErrorPrototype)
     614        stack.push(m_ReferenceErrorPrototype);
     615    if (m_SyntaxErrorPrototype)
     616        stack.push(m_SyntaxErrorPrototype);
     617    if (m_TypeErrorPrototype)
     618        stack.push(m_TypeErrorPrototype);
     619    if (m_UriErrorPrototype)
     620        stack.push(m_UriErrorPrototype);
    621621}
    622622

  • trunk/JavaScriptCore/kjs/interpreter.h

    r27885 r28106  
    291291     * implementing custom mark methods must make sure to chain to this one.
    292292     */
    293     virtual void mark();
     293    virtual void markRoots(MarkStack&);
    294294
    295295    static bool shouldPrintExceptions();

  • trunk/JavaScriptCore/kjs/list.cpp

    r27453 r28106  
    4444}
    4545
    46 void List::markProtectedListsSlowCase()
     46void List::markProtectedListsSlowCase(MarkStack& stack)
    4747{
    4848    ListSet::iterator end = markSet().end();
    … …  
    5151
    5252        iterator end2 = list->end();
    53         for (iterator it2 = list->begin(); it2 != end2; ++it2) {
    54             JSValue* v = *it2;
    55             if (!v->marked())
    56                 v->mark();
    57         }
     53        for (iterator it2 = list->begin(); it2 != end2; ++it2)
     54            stack.push(*it2);
    5855    }
    5956}

  • trunk/JavaScriptCore/kjs/list.h

    r27472 r28106  
    8686        const_iterator end() const { return m_vector.end(); }
    8787
    88         static void markProtectedLists()
     88        static void markProtectedLists(MarkStack& stack)
    8989        {
    9090            if (!markSet().size())
    9191                return;
    92             markProtectedListsSlowCase();
     92            markProtectedListsSlowCase(stack);
    9393        }
    9494
    … …  
    9797    private:
    9898        static ListSet& markSet();
    99         static void markProtectedListsSlowCase();
     99        static void markProtectedListsSlowCase(MarkStack&);
    100100
    101101        void expandAndAppend(JSValue*);

  • trunk/JavaScriptCore/kjs/object.cpp

    r27695 r28106  
    114114// ------------------------------ JSObject ------------------------------------
    115115
    116 void JSObject::mark()
    117 {
    118   JSCell::mark();
    119 
     116void JSObject::markChildren(MarkStack& stack)
     117{
    120118#if JAVASCRIPT_MARK_TRACING
    121119  static int markStackDepth = 0;
    … …  
    127125#endif
    128126 
    129   JSValue *proto = _proto;
    130   if (!proto->marked())
    131     proto->mark();
    132 
    133   _prop.mark();
     127  stack.push(_proto);
     128  _prop.markChildren(stack);
    134129 
    135130#if JAVASCRIPT_MARK_TRACING

  • trunk/JavaScriptCore/kjs/object.h

    r27695 r28106  
    2828#include "JSType.h"
    2929#include "CommonIdentifiers.h"
     30#include "MarkStack.h"
    3031#include "interpreter.h"
    3132#include "property_map.h"
    … …  
    8586    virtual JSObject *toObject(ExecState *exec) const;
    8687     
    87     virtual void mark();
     88    virtual void markChildren(MarkStack&);
    8889     
    8990    JSObject *getGetter() { return getter; }
    … …  
    112113    JSObject();
    113114
    114     virtual void mark();
     115    virtual void markChildren(MarkStack&);
    115116    virtual JSType type() const;
    116117
    … …  
    587588// FIXME: Put this function in a separate file named something like scope_chain_mark.h -- can't put it in scope_chain.h since it depends on JSObject.
    588589
    589 inline void ScopeChain::mark()
    590 {
    591     for (ScopeChainNode *n = _node; n; n = n->next) {
    592         JSObject *o = n->object;
    593         if (!o->marked())
    594             o->mark();
     590inline void ScopeChain::markChildren(MarkStack& stack)
     591{
     592    for (ScopeChainNode* n = _node; n; n = n->next) {
     593        JSObject* o = n->object;
     594        stack.push(o);
    595595    }
    596596}

  • trunk/JavaScriptCore/kjs/property_map.cpp

    r27711 r28106  
    623623}
    624624
    625 void PropertyMap::mark() const
    626 {
    627     if (!m_usingTable) {
    628 #if USE_SINGLE_ENTRY
    629         if (m_singleEntryKey) {
    630             JSValue* v = m_u.singleEntryValue;
    631             if (!v->marked())
    632                 v->mark();
    633         }
     625void PropertyMap::markChildren(MarkStack& stack) const
     626{
     627    if (!m_usingTable) {
     628#if USE_SINGLE_ENTRY
     629        if (m_singleEntryKey)
     630            stack.push(m_u.singleEntryValue);
    634631#endif
    635632        return;
    … …  
    637634
    638635    unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
    639     for (unsigned i = 1; i <= entryCount; i++) {
    640         JSValue* v = m_u.table->entries()[i].value;
    641         if (!v->marked())
    642             v->mark();
    643     }
     636    for (unsigned i = 1; i <= entryCount; i++)
     637        stack.push(m_u.table->entries()[i].value);
    644638}
    645639

  • trunk/JavaScriptCore/kjs/property_map.h

    r27387 r28106  
    3030    class JSObject;
    3131    class JSValue;
     32    class MarkStack;
    3233    class PropertyNameArray;
    3334   
    … …  
    6061        JSValue** getLocation(const Identifier& name);
    6162
    62         void mark() const;
     63        void markChildren(MarkStack&) const;
    6364        void getEnumerablePropertyNames(PropertyNameArray&) const;
    6465

  • trunk/JavaScriptCore/kjs/scope_chain.h

    r28079 r28106  
    8383        void pop();
    8484       
    85         void mark();
     85        void markChildren(MarkStack&);
    8686
    8787#ifndef NDEBUG       

  • trunk/JavaScriptCore/kjs/string_object.cpp

    r27633 r28106  
    128128    propertyNames.add(Identifier(UString::from(i)));
    129129  return JSObject::getPropertyNames(exec, propertyNames);
     130}
     131
     132void StringInstance::markChildren(MarkStack& stack)
     133{
     134    JSObject::markChildren(stack);
     135    stack.pushAtom(internalValue());
    130136}
    131137

  • trunk/JavaScriptCore/kjs/string_object.h

    r27608 r28106  
    4747
    4848    StringImp* internalValue() const { return static_cast<StringImp*>(JSWrapperObject::internalValue());}
     49    virtual void markChildren(MarkStack& stack);
    4950
    5051  private:

  • trunk/JavaScriptCore/kjs/value.h

    r27747 r28106  
    3434class JSObject;
    3535class JSCell;
     36class MarkStack;
    3637
    3738struct ClassInfo;
    … …  
    4849    friend class JSCell; // so it can derive from this class
    4950    friend class Collector; // so it can call asCell()
     51    friend class MarkStack; // so it can call asCell()
    5052
    5153private:
    … …  
    106108
    107109    // Garbage collection.
    108     void mark();
     110    void markChildren(MarkStack&);
    109111    bool marked() const;
    110112
    … …  
    165167    // Garbage collection.
    166168    void *operator new(size_t);
    167     virtual void mark();
     169    virtual void markChildren(MarkStack&);
    168170    bool marked() const;
    169171};
    … …  
    291293}
    292294
    293 inline void JSCell::mark()
    294 {
    295     return Collector::markCell(this);
     295inline void JSCell::markChildren(MarkStack&)
     296{
    296297}
    297298
    … …  
    407408}
    408409
    409 inline void JSValue::mark()
    410 {
    411     ASSERT(!JSImmediate::isImmediate(this)); // callers should check !marked() before calling mark()
    412     asCell()->mark();
     410inline void JSValue::markChildren(MarkStack& stack)
     411{
     412    ASSERT(!JSImmediate::isImmediate(this)); // callers should check !marked() before calling markChildren()
     413    asCell()->markChildren(stack);
    413414}
    414415
Note: See TracChangeset for help on using the changeset viewer.