Changeset 207179 in webkit


Ignore:
Timestamp:
Oct 11, 2016 4:52:02 PM (8 years ago)
Author:
fpizlo@apple.com
Message:

MarkedBlock should know what objects are live during marking
​https://bugs.webkit.org/show_bug.cgi?id=162309

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

It used to be that we would forget which objects are live the moment we started collection.
That's because the flip at the beginning clears all mark bits.

But we already have a facility for tracking objects that are live-but-not-marked. It's called
newlyAllocated. So, instead of clearing mark bits, we want to just transfer them to
newlyAllocated. Then we want to clear all newlyAllocated after GC.

This implements such an approach, along with a versioning optimization for newlyAllocated.
Instead of walking the whole heap to clear newlyAllocated bits at the end of the GC, we bump
the newlyAllocatedVersion, which causes MarkedBlock to treat newlyAllocated as if it was
clear.

We could have even avoided allocating newlyAllocated in most cases, since empirically most
blocks are either completely empty or completely full. An earlier version of this patch did
this, but it was not better than this patch. In fact, it seemed to actually be worse for PLT
and membuster.

To validate this change, we now run the conservative scan after the beginMarking flip. And it
totally works!

This is a huge step towards concurrent GC. It means that we ought to be able to run the
allocator while marking. Since we already separately made it possible to run the barrier
while marking, this means that we're pretty much ready for some serious concurrency action.

This appears to be perf-neutral and space-neutral.

  • JavaScriptCore.xcodeproj/project.pbxproj:
  • bytecode/CodeBlock.cpp:
  • bytecode/CodeBlock.h:

(JSC::CodeBlockSet::mark): Deleted.

  • heap/CodeBlockSet.cpp:

(JSC::CodeBlockSet::writeBarrierCurrentlyExecuting):
(JSC::CodeBlockSet::clearCurrentlyExecuting):
(JSC::CodeBlockSet::writeBarrierCurrentlyExecutingCodeBlocks): Deleted.

  • heap/CodeBlockSet.h:
  • heap/CodeBlockSetInlines.h: Added.

(JSC::CodeBlockSet::mark):

  • heap/ConservativeRoots.cpp:
  • heap/Heap.cpp:

(JSC::Heap::markRoots):
(JSC::Heap::beginMarking):
(JSC::Heap::collectImpl):
(JSC::Heap::writeBarrierCurrentlyExecutingCodeBlocks):
(JSC::Heap::clearCurrentlyExecutingCodeBlocks):

  • heap/Heap.h:
  • heap/HeapUtil.h:

(JSC::HeapUtil::findGCObjectPointersForMarking):

  • heap/MarkedAllocator.cpp:

(JSC::MarkedAllocator::isPagedOut):

  • heap/MarkedBlock.cpp:

(JSC::MarkedBlock::Handle::Handle):
(JSC::MarkedBlock::Handle::sweepHelperSelectHasNewlyAllocated):
(JSC::MarkedBlock::Handle::stopAllocating):
(JSC::MarkedBlock::Handle::lastChanceToFinalize):
(JSC::MarkedBlock::Handle::resumeAllocating):
(JSC::MarkedBlock::aboutToMarkSlow):
(JSC::MarkedBlock::Handle::resetAllocated):
(JSC::MarkedBlock::resetMarks):
(JSC::MarkedBlock::setNeedsDestruction):
(JSC::MarkedBlock::Handle::didAddToAllocator):
(JSC::MarkedBlock::Handle::isLive):
(JSC::MarkedBlock::Handle::isLiveCell):
(JSC::MarkedBlock::clearMarks): Deleted.

  • heap/MarkedBlock.h:

(JSC::MarkedBlock::Handle::newlyAllocatedVersion):
(JSC::MarkedBlock::Handle::hasAnyNewlyAllocated): Deleted.
(JSC::MarkedBlock::Handle::clearNewlyAllocated): Deleted.

  • heap/MarkedBlockInlines.h:

(JSC::MarkedBlock::Handle::cellsPerBlock):
(JSC::MarkedBlock::Handle::isLive):
(JSC::MarkedBlock::Handle::isLiveCell):
(JSC::MarkedBlock::Handle::isNewlyAllocatedStale):
(JSC::MarkedBlock::Handle::hasAnyNewlyAllocatedWithSweep):
(JSC::MarkedBlock::Handle::hasAnyNewlyAllocated):
(JSC::MarkedBlock::heap):
(JSC::MarkedBlock::space):
(JSC::MarkedBlock::Handle::space):
(JSC::MarkedBlock::resetMarkingVersion): Deleted.

  • heap/MarkedSpace.cpp:

(JSC::MarkedSpace::beginMarking):
(JSC::MarkedSpace::endMarking):
(JSC::MarkedSpace::clearNewlyAllocated): Deleted.

  • heap/MarkedSpace.h:

(JSC::MarkedSpace::nextVersion):
(JSC::MarkedSpace::newlyAllocatedVersion):
(JSC::MarkedSpace::markingVersion): Deleted.

  • runtime/SamplingProfiler.cpp:

Source/WTF:

This removes the atomicity mode, because it's not really used: it only affects the
concurrentBlah methods, but their only users turn on atomicity. This was useful because
previously, some binary Bitmap methods (like merge(const Bitmap&)) couldn't be used
effectively in the GC because some of the GC's bitmaps set the atomic mode and some didn't.
Removing this useless mode is the best solution.

Also added some new binary Bitmap methods: mergeAndClear(Bitmap& other) and
setAndClear(Bitmap& other). They perform their action on 'this' (either merge or set,
respectively) while also clearing the contents of 'other'. This is great for one of the GC
hot paths.

  • wtf/Bitmap.h:

(WTF::WordType>::Bitmap):
(WTF::WordType>::get):
(WTF::WordType>::set):
(WTF::WordType>::testAndSet):
(WTF::WordType>::testAndClear):
(WTF::WordType>::concurrentTestAndSet):
(WTF::WordType>::concurrentTestAndClear):
(WTF::WordType>::clear):
(WTF::WordType>::clearAll):
(WTF::WordType>::nextPossiblyUnset):
(WTF::WordType>::findRunOfZeros):
(WTF::WordType>::count):
(WTF::WordType>::isEmpty):
(WTF::WordType>::isFull):
(WTF::WordType>::merge):
(WTF::WordType>::filter):
(WTF::WordType>::exclude):
(WTF::WordType>::forEachSetBit):
(WTF::WordType>::mergeAndClear):
(WTF::WordType>::setAndClear):
(WTF::=):
(WTF::WordType>::hash):

Location:
trunk/Source
Files:
1 added
20 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r207178 r207179  
     12016-10-06  Filip Pizlo  <fpizlo@apple.com>
     2
     3        MarkedBlock should know what objects are live during marking
     4        https://bugs.webkit.org/show_bug.cgi?id=162309
     5
     6        Reviewed by Geoffrey Garen.
     7       
     8        It used to be that we would forget which objects are live the moment we started collection.
     9        That's because the flip at the beginning clears all mark bits.
     10       
     11        But we already have a facility for tracking objects that are live-but-not-marked. It's called
     12        newlyAllocated. So, instead of clearing mark bits, we want to just transfer them to
     13        newlyAllocated. Then we want to clear all newlyAllocated after GC.
     14       
     15        This implements such an approach, along with a versioning optimization for newlyAllocated.
     16        Instead of walking the whole heap to clear newlyAllocated bits at the end of the GC, we bump
     17        the newlyAllocatedVersion, which causes MarkedBlock to treat newlyAllocated as if it was
     18        clear.
     19       
     20        We could have even avoided allocating newlyAllocated in most cases, since empirically most
     21        blocks are either completely empty or completely full. An earlier version of this patch did
     22        this, but it was not better than this patch. In fact, it seemed to actually be worse for PLT
     23        and membuster.
     24       
     25        To validate this change, we now run the conservative scan after the beginMarking flip. And it
     26        totally works!
     27       
     28        This is a huge step towards concurrent GC. It means that we ought to be able to run the
     29        allocator while marking. Since we already separately made it possible to run the barrier
     30        while marking, this means that we're pretty much ready for some serious concurrency action.
     31       
     32        This appears to be perf-neutral and space-neutral.
     33
     34        * JavaScriptCore.xcodeproj/project.pbxproj:
     35        * bytecode/CodeBlock.cpp:
     36        * bytecode/CodeBlock.h:
     37        (JSC::CodeBlockSet::mark): Deleted.
     38        * heap/CodeBlockSet.cpp:
     39        (JSC::CodeBlockSet::writeBarrierCurrentlyExecuting):
     40        (JSC::CodeBlockSet::clearCurrentlyExecuting):
     41        (JSC::CodeBlockSet::writeBarrierCurrentlyExecutingCodeBlocks): Deleted.
     42        * heap/CodeBlockSet.h:
     43        * heap/CodeBlockSetInlines.h: Added.
     44        (JSC::CodeBlockSet::mark):
     45        * heap/ConservativeRoots.cpp:
     46        * heap/Heap.cpp:
     47        (JSC::Heap::markRoots):
     48        (JSC::Heap::beginMarking):
     49        (JSC::Heap::collectImpl):
     50        (JSC::Heap::writeBarrierCurrentlyExecutingCodeBlocks):
     51        (JSC::Heap::clearCurrentlyExecutingCodeBlocks):
     52        * heap/Heap.h:
     53        * heap/HeapUtil.h:
     54        (JSC::HeapUtil::findGCObjectPointersForMarking):
     55        * heap/MarkedAllocator.cpp:
     56        (JSC::MarkedAllocator::isPagedOut):
     57        * heap/MarkedBlock.cpp:
     58        (JSC::MarkedBlock::Handle::Handle):
     59        (JSC::MarkedBlock::Handle::sweepHelperSelectHasNewlyAllocated):
     60        (JSC::MarkedBlock::Handle::stopAllocating):
     61        (JSC::MarkedBlock::Handle::lastChanceToFinalize):
     62        (JSC::MarkedBlock::Handle::resumeAllocating):
     63        (JSC::MarkedBlock::aboutToMarkSlow):
     64        (JSC::MarkedBlock::Handle::resetAllocated):
     65        (JSC::MarkedBlock::resetMarks):
     66        (JSC::MarkedBlock::setNeedsDestruction):
     67        (JSC::MarkedBlock::Handle::didAddToAllocator):
     68        (JSC::MarkedBlock::Handle::isLive):
     69        (JSC::MarkedBlock::Handle::isLiveCell):
     70        (JSC::MarkedBlock::clearMarks): Deleted.
     71        * heap/MarkedBlock.h:
     72        (JSC::MarkedBlock::Handle::newlyAllocatedVersion):
     73        (JSC::MarkedBlock::Handle::hasAnyNewlyAllocated): Deleted.
     74        (JSC::MarkedBlock::Handle::clearNewlyAllocated): Deleted.
     75        * heap/MarkedBlockInlines.h:
     76        (JSC::MarkedBlock::Handle::cellsPerBlock):
     77        (JSC::MarkedBlock::Handle::isLive):
     78        (JSC::MarkedBlock::Handle::isLiveCell):
     79        (JSC::MarkedBlock::Handle::isNewlyAllocatedStale):
     80        (JSC::MarkedBlock::Handle::hasAnyNewlyAllocatedWithSweep):
     81        (JSC::MarkedBlock::Handle::hasAnyNewlyAllocated):
     82        (JSC::MarkedBlock::heap):
     83        (JSC::MarkedBlock::space):
     84        (JSC::MarkedBlock::Handle::space):
     85        (JSC::MarkedBlock::resetMarkingVersion): Deleted.
     86        * heap/MarkedSpace.cpp:
     87        (JSC::MarkedSpace::beginMarking):
     88        (JSC::MarkedSpace::endMarking):
     89        (JSC::MarkedSpace::clearNewlyAllocated): Deleted.
     90        * heap/MarkedSpace.h:
     91        (JSC::MarkedSpace::nextVersion):
     92        (JSC::MarkedSpace::newlyAllocatedVersion):
     93        (JSC::MarkedSpace::markingVersion): Deleted.
     94        * runtime/SamplingProfiler.cpp:
     95
    1962016-10-11  Mark Lam  <mark.lam@apple.com>
    297

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

    r207166 r207179  
    446446                0F64B27A1A7957B2006E4E66 /* CallEdge.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F64B2781A7957B2006E4E66 /* CallEdge.h */; settings = {ATTRIBUTES = (Private, ); }; };
    447447                0F64EAF31C4ECD0600621E9B /* AirArgInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F64EAF21C4ECD0600621E9B /* AirArgInlines.h */; };
     448                0F664CE81DA304EF00B00A11 /* CodeBlockSetInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F664CE71DA304ED00B00A11 /* CodeBlockSetInlines.h */; };
    448449                0F666EC0183566F900D017F1 /* BytecodeLivenessAnalysisInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F666EBE183566F900D017F1 /* BytecodeLivenessAnalysisInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
    449450                0F666EC1183566F900D017F1 /* FullBytecodeLiveness.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F666EBF183566F900D017F1 /* FullBytecodeLiveness.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    27102711                0F64B2781A7957B2006E4E66 /* CallEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CallEdge.h; sourceTree = "<group>"; };
    27112712                0F64EAF21C4ECD0600621E9B /* AirArgInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AirArgInlines.h; path = b3/air/AirArgInlines.h; sourceTree = "<group>"; };
     2713                0F664CE71DA304ED00B00A11 /* CodeBlockSetInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CodeBlockSetInlines.h; sourceTree = "<group>"; };
    27122714                0F666EBE183566F900D017F1 /* BytecodeLivenessAnalysisInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = BytecodeLivenessAnalysisInlines.h; sourceTree = "<group>"; };
    27132715                0F666EBF183566F900D017F1 /* FullBytecodeLiveness.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FullBytecodeLiveness.h; sourceTree = "<group>"; };
    … …  
    53265328                                0FD8A31117D4326C00CA2C40 /* CodeBlockSet.cpp */,
    53275329                                0FD8A31217D4326C00CA2C40 /* CodeBlockSet.h */,
     5330                                0F664CE71DA304ED00B00A11 /* CodeBlockSetInlines.h */,
    53285331                                146B14DB12EB5B12001BEC1B /* ConservativeRoots.cpp */,
    53295332                                149DAAF212EB559D0083B12B /* ConservativeRoots.h */,
    … …  
    79617964                                657CF45919BF6662004ACBF2 /* JSCallee.h in Headers */,
    79627965                                A7D801A91880D6A80026C39B /* JSCBuiltins.h in Headers */,
     7966                                0F664CE81DA304EF00B00A11 /* CodeBlockSetInlines.h in Headers */,
    79637967                                BC1167DA0E19BCC9008066DD /* JSCell.h in Headers */,
    79647968                                0F9749711687ADE400A4FF6A /* JSCellInlines.h in Headers */,

  • trunk/Source/JavaScriptCore/bytecode/CodeBlock.cpp

    r206853 r207179  
    3737#include "BytecodeUseDef.h"
    3838#include "CallLinkStatus.h"
     39#include "CodeBlockSet.h"
    3940#include "DFGCapabilities.h"
    4041#include "DFGCommon.h"

  • trunk/Source/JavaScriptCore/bytecode/CodeBlock.h

    r206525 r207179  
    3636#include "CallReturnOffsetToBytecodeOffset.h"
    3737#include "CodeBlockHash.h"
    38 #include "CodeBlockSet.h"
    3938#include "CodeOrigin.h"
    4039#include "CodeType.h"
    … …  
    7776
    7877class BytecodeLivenessAnalysis;
     78class CodeBlockSet;
    7979class ExecState;
    8080class JSModuleEnvironment;
    … …  
    13121312}
    13131313
    1314 inline void CodeBlockSet::mark(const LockHolder& locker, void* candidateCodeBlock)
    1315 {
    1316     ASSERT(m_lock.isLocked());
    1317     // We have to check for 0 and -1 because those are used by the HashMap as markers.
    1318     uintptr_t value = reinterpret_cast<uintptr_t>(candidateCodeBlock);
    1319    
    1320     // This checks for both of those nasty cases in one go.
    1321     // 0 + 1 = 1
    1322     // -1 + 1 = 0
    1323     if (value + 1 <= 1)
    1324         return;
    1325 
    1326     CodeBlock* codeBlock = static_cast<CodeBlock*>(candidateCodeBlock);
    1327     if (!m_oldCodeBlocks.contains(codeBlock) && !m_newCodeBlocks.contains(codeBlock))
    1328         return;
    1329 
    1330     mark(locker, codeBlock);
    1331 }
    1332 
    1333 inline void CodeBlockSet::mark(const LockHolder&, CodeBlock* codeBlock)
    1334 {
    1335     if (!codeBlock)
    1336         return;
    1337 
    1338     // Try to recover gracefully if we forget to execute a barrier for a
    1339     // CodeBlock that does value profiling. This is probably overkill, but we
    1340     // have always done it.
    1341     Heap::heap(codeBlock)->writeBarrier(codeBlock);
    1342 
    1343     m_currentlyExecuting.add(codeBlock);
    1344 }
    1345 
    13461314template <typename Functor> inline void ScriptExecutable::forEachCodeBlock(Functor&& functor)
    13471315{

  • trunk/Source/JavaScriptCore/heap/CodeBlockSet.cpp

    r206267 r207179  
    108108}
    109109
    110 void CodeBlockSet::writeBarrierCurrentlyExecutingCodeBlocks(Heap* heap)
     110void CodeBlockSet::writeBarrierCurrentlyExecuting(Heap* heap)
    111111{
    112112    LockHolder locker(&m_lock);
    … …  
    115115    for (CodeBlock* codeBlock : m_currentlyExecuting)
    116116        heap->writeBarrier(codeBlock);
     117}
    117118
    118     // It's safe to clear this set because we won't delete the CodeBlocks
    119     // in it until the next GC, and we'll recompute it at that time.
     119void CodeBlockSet::clearCurrentlyExecuting()
     120{
    120121    m_currentlyExecuting.clear();
    121122}

  • trunk/Source/JavaScriptCore/heap/CodeBlockSet.h

    r206525 r207179  
    7272    // Add all currently executing CodeBlocks to the remembered set to be
    7373    // re-scanned during the next collection.
    74     void writeBarrierCurrentlyExecutingCodeBlocks(Heap*);
     74    void writeBarrierCurrentlyExecuting(Heap*);
     75
     76    void clearCurrentlyExecuting();
    7577
    7678    bool contains(const LockHolder&, void* candidateCodeBlock);

  • trunk/Source/JavaScriptCore/heap/ConservativeRoots.cpp

    r206172 r207179  
    2828
    2929#include "CodeBlock.h"
    30 #include "CodeBlockSet.h"
     30#include "CodeBlockSetInlines.h"
    3131#include "HeapInlines.h"
    3232#include "HeapUtil.h"

  • trunk/Source/JavaScriptCore/heap/Heap.cpp

    r206555 r207179  
    2323
    2424#include "CodeBlock.h"
     25#include "CodeBlockSet.h"
    2526#include "ConservativeRoots.h"
    2627#include "DFGWorklist.h"
    … …  
    389390    HeapRootVisitor heapRootVisitor(m_slotVisitor);
    390391   
    391     ConservativeRoots conservativeRoots(*this);
    392392    {
    393393        TimingScope preConvergenceTimingScope(*this, "Heap::markRoots before convergence");
    394         // We gather conservative roots before clearing mark bits because conservative
    395         // gathering uses the mark bits to determine whether a reference is valid.
    396         {
    397             TimingScope preConvergenceTimingScope(*this, "Heap::markRoots conservative scan");
    398             SuperSamplerScope superSamplerScope(false);
    399             gatherStackRoots(conservativeRoots, stackOrigin, stackTop, calleeSavedRegisters);
    400             gatherJSStackRoots(conservativeRoots);
    401             gatherScratchBufferRoots(conservativeRoots);
    402         }
    403394
    404395#if ENABLE(DFG_JIT)
    … …  
    464455       
    465456        m_slotVisitor.donateAndDrain();
     457
     458        {
     459            TimingScope preConvergenceTimingScope(*this, "Heap::markRoots conservative scan");
     460            ConservativeRoots conservativeRoots(*this);
     461            SuperSamplerScope superSamplerScope(false);
     462            gatherStackRoots(conservativeRoots, stackOrigin, stackTop, calleeSavedRegisters);
     463            gatherJSStackRoots(conservativeRoots);
     464            gatherScratchBufferRoots(conservativeRoots);
     465            visitConservativeRoots(conservativeRoots);
     466           
     467            // We want to do this to conservatively ensure that we rescan any code blocks that are
     468            // running right now. However, we need to be sure to do it *after* we mark the code block
     469            // so that we know for sure if it really needs a barrier.
     470            m_codeBlocks->writeBarrierCurrentlyExecuting(this);
     471        }
     472
    466473        visitExternalRememberedSet();
    467474        visitSmallStrings();
    468         visitConservativeRoots(conservativeRoots);
    469475        visitProtectedObjects(heapRootVisitor);
    470476        visitArgumentBuffers(heapRootVisitor);
    … …  
    523529    if (m_operationInProgress == FullCollection)
    524530        m_codeBlocks->clearMarksForFullCollection();
    525    
    526     {
    527         TimingScope clearNewlyAllocatedTimingScope(*this, "m_objectSpace.clearNewlyAllocated");
    528         m_objectSpace.clearNewlyAllocated();
    529     }
    530531   
    531532    {
    … …  
    10601061
    10611062    notifyIncrementalSweeper();
    1062     writeBarrierCurrentlyExecutingCodeBlocks();
     1063    m_codeBlocks->writeBarrierCurrentlyExecuting(this);
     1064    m_codeBlocks->clearCurrentlyExecuting();
    10631065
    10641066    prepareForAllocation();
    … …  
    12001202
    12011203    m_sweeper->startSweeping();
    1202 }
    1203 
    1204 void Heap::writeBarrierCurrentlyExecutingCodeBlocks()
    1205 {
    1206     m_codeBlocks->writeBarrierCurrentlyExecutingCodeBlocks(this);
    12071204}
    12081205

  • trunk/Source/JavaScriptCore/heap/Heap.h

    r206555 r207179  
    350350    void deleteSourceProviderCaches();
    351351    void notifyIncrementalSweeper();
    352     void writeBarrierCurrentlyExecutingCodeBlocks();
    353352    void prepareForAllocation();
    354353    void harvestWeakReferences();

  • trunk/Source/JavaScriptCore/heap/HeapUtil.h

    r206172 r207179  
    5252        const HashSet<MarkedBlock*>& set = heap.objectSpace().blocks().set();
    5353       
     54        ASSERT(heap.objectSpace().isMarking());
     55        static const bool isMarking = true;
     56       
    5457        char* pointer = static_cast<char*>(passedPointer);
    5558       
    … …  
    8689                && previousCandidate->handle().cellKind() == HeapCell::Auxiliary) {
    8790                previousPointer = static_cast<char*>(previousCandidate->handle().cellAlign(previousPointer));
    88                 if (previousCandidate->handle().isLiveCell(markingVersion, previousPointer))
     91                if (previousCandidate->handle().isLiveCell(markingVersion, isMarking, previousPointer))
    8992                    func(previousPointer);
    9093            }
    … …  
    100103       
    101104        auto tryPointer = [&] (void* pointer) {
    102             if (candidate->handle().isLiveCell(markingVersion, pointer))
     105            if (candidate->handle().isLiveCell(markingVersion, isMarking, pointer))
    103106                func(pointer);
    104107        };

  • trunk/Source/JavaScriptCore/heap/MarkedAllocator.cpp

    r206555 r207179  
    5454    for (size_t index = 0; index < m_blocks.size(); ++index) {
    5555        MarkedBlock::Handle* block = m_blocks[index];
    56         if (block) {
    57             // Forces us to touch the memory of the block, but has no semantic effect.
    58             if (block->areMarksStale())
    59                 block->block().resetMarkingVersion();
    60         }
     56        if (block)
     57            block->block().updateNeedsDestruction();
    6158        ++itersSinceLastTimeCheck;
    6259        if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
    … …  
    437434    m_unswept.forEachSetBit(
    438435        [&] (size_t index) {
    439             m_blocks[index]->sweep();
     436            MarkedBlock::Handle* block = m_blocks[index];
     437            block->sweep();
    440438        });
    441439}

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.cpp

    r206709 r207179  
    5555MarkedBlock::Handle::Handle(Heap& heap, void* blockSpace)
    5656    : m_weakSet(heap.vm(), CellContainer())
     57    , m_newlyAllocatedVersion(MarkedSpace::nullVersion)
    5758{
    5859    m_block = new (NotNull, blockSpace) MarkedBlock(*heap.vm(), *this);
    … …  
    126127        if (emptyMode == NotEmpty
    127128            && ((marksMode == MarksNotStale && block.m_marks.get(i))
    128                 || (newlyAllocatedMode == HasNewlyAllocated && m_newlyAllocated->get(i)))) {
     129                || (newlyAllocatedMode == HasNewlyAllocated && m_newlyAllocated.get(i)))) {
    129130            isEmpty = false;
    130131            continue;
    … …  
    149150    // otherwise we would lose information on what's currently alive.
    150151    if (sweepMode == SweepToFreeList && newlyAllocatedMode == HasNewlyAllocated)
    151         m_newlyAllocated = nullptr;
     152        m_newlyAllocatedVersion = MarkedSpace::nullVersion;
    152153
    153154    FreeList result = FreeList::list(head, count * cellSize());
    … …  
    208209FreeList MarkedBlock::Handle::sweepHelperSelectHasNewlyAllocated(SweepMode sweepMode)
    209210{
    210     if (m_newlyAllocated)
     211    if (hasAnyNewlyAllocated())
    211212        return sweepHelperSelectSweepMode<emptyMode, destructionMode, scribbleMode, HasNewlyAllocated>(sweepMode);
    212213    return sweepHelperSelectSweepMode<emptyMode, destructionMode, scribbleMode, DoesNotHaveNewlyAllocated>(sweepMode);
    … …  
    276277    // way to tell what's live vs dead.
    277278   
    278     ASSERT(!m_newlyAllocated);
    279     m_newlyAllocated = std::make_unique<WTF::Bitmap<atomsPerBlock>>();
     279    m_newlyAllocated.clearAll();
     280    m_newlyAllocatedVersion = heap()->objectSpace().newlyAllocatedVersion();
    280281
    281282    SetNewlyAllocatedFunctor functor(this);
    … …  
    296297{
    297298    allocator()->setIsAllocated(this, false);
    298     m_block->clearMarks();
     299    m_block->m_marks.clearAll();
     300    m_block->clearHasAnyMarked();
     301    m_block->m_markingVersion = heap()->objectSpace().markingVersion();
    299302    m_weakSet.lastChanceToFinalize();
    300 
    301     clearNewlyAllocated();
     303    m_newlyAllocated.clearAll();
     304    m_newlyAllocatedVersion = heap()->objectSpace().newlyAllocatedVersion();
    302305    sweep();
    303306}
    … …  
    308311    ASSERT(!isFreeListed());
    309312
    310     if (!m_newlyAllocated) {
     313    if (!hasAnyNewlyAllocated()) {
    311314        // This means we had already exhausted the block when we stopped allocation.
    312315        return FreeList();
    … …  
    347350    ASSERT(vm()->heap.objectSpace().isMarking());
    348351    LockHolder locker(m_lock);
    349     if (areMarksStale(markingVersion)) {
    350         clearMarks(markingVersion);
    351         // This means we're the first ones to mark any object in this block.
    352         handle().allocator()->atomicSetAndCheckIsMarkingNotEmpty(&handle(), true);
    353     }
    354 }
    355 
    356 void MarkedBlock::clearMarks()
    357 {
    358     clearMarks(vm()->heap.objectSpace().markingVersion());
    359 }
    360 
    361 void MarkedBlock::clearMarks(HeapVersion markingVersion)
    362 {
    363     m_marks.clearAll();
     352    if (!areMarksStale(markingVersion))
     353        return;
     354   
     355    if (handle().allocator()->isAllocated(&handle())
     356        || !marksConveyLivenessDuringMarking(markingVersion)) {
     357        // We already know that the block is full and is already recognized as such, or that the
     358        // block did not survive the previous GC. So, we can clear mark bits the old fashioned
     359        // way. Note that it's possible for such a block to have newlyAllocated with an up-to-
     360        // date version! If it does, then we want to leave the newlyAllocated alone, since that
     361        // means that we had allocated in this previously empty block but did not fill it up, so
     362        // we created a newlyAllocated.
     363        m_marks.clearAll();
     364    } else {
     365        HeapVersion newlyAllocatedVersion = space()->newlyAllocatedVersion();
     366        if (handle().m_newlyAllocatedVersion == newlyAllocatedVersion) {
     367            // Merge the contents of marked into newlyAllocated. If we get the full set of bits
     368            // then invalidate newlyAllocated and set allocated.
     369            handle().m_newlyAllocated.mergeAndClear(m_marks);
     370        } else {
     371            // Replace the contents of newlyAllocated with marked. If we get the full set of
     372            // bits then invalidate newlyAllocated and set allocated.
     373            handle().m_newlyAllocated.setAndClear(m_marks);
     374        }
     375        handle().m_newlyAllocatedVersion = newlyAllocatedVersion;
     376    }
    364377    clearHasAnyMarked();
    365378    WTF::storeStoreFence();
    366379    m_markingVersion = markingVersion;
     380   
     381    // This means we're the first ones to mark any object in this block.
     382    handle().allocator()->atomicSetAndCheckIsMarkingNotEmpty(&handle(), true);
     383}
     384
     385void MarkedBlock::Handle::resetAllocated()
     386{
     387    m_newlyAllocated.clearAll();
     388    m_newlyAllocatedVersion = MarkedSpace::nullVersion;
     389}
     390
     391void MarkedBlock::resetMarks()
     392{
     393    // We want aboutToMarkSlow() to see what the mark bits were after the last collection. It uses
     394    // the version number to distinguish between the marks having already been stale before
     395    // beginMarking(), or just stale now that beginMarking() bumped the version. If we have a version
     396    // wraparound, then we will call this method before resetting the version to null. When the
     397    // version is null, aboutToMarkSlow() will assume that the marks were not stale as of before
     398    // beginMarking(). Hence the need to whip the marks into shape.
     399    if (areMarksStale())
     400        m_marks.clearAll();
     401    m_markingVersion = MarkedSpace::nullVersion;
    367402}
    368403
    … …  
    426461}
    427462
     463void MarkedBlock::updateNeedsDestruction()
     464{
     465    m_needsDestruction = handle().needsDestruction();
     466}
     467
    428468void MarkedBlock::Handle::didAddToAllocator(MarkedAllocator* allocator, size_t index)
    429469{
    … …  
    443483        RELEASE_ASSERT(m_attributes.destruction == DoesNotNeedDestruction);
    444484   
    445     block().m_needsDestruction = needsDestruction();
    446    
    447     unsigned cellsPerBlock = MarkedSpace::blockPayload / cellSize;
    448     double markCountBias = -(Options::minMarkedBlockUtilization() * cellsPerBlock);
     485    block().updateNeedsDestruction();
     486   
     487    double markCountBias = -(Options::minMarkedBlockUtilization() * cellsPerBlock());
    449488   
    450489    // The mark count bias should be comfortably within this range.
    … …  
    467506bool MarkedBlock::Handle::isLive(const HeapCell* cell)
    468507{
    469     return isLive(vm()->heap.objectSpace().markingVersion(), cell);
     508    return isLive(space()->markingVersion(), space()->isMarking(), cell);
    470509}
    471510
    472511bool MarkedBlock::Handle::isLiveCell(const void* p)
    473512{
    474     return isLiveCell(vm()->heap.objectSpace().markingVersion(), p);
     513    return isLiveCell(space()->markingVersion(), space()->isMarking(), p);
    475514}
    476515

  • trunk/Source/JavaScriptCore/heap/MarkedBlock.h

    r206709 r207179  
    4141class JSCell;
    4242class MarkedAllocator;
     43class MarkedSpace;
    4344
    4445typedef uintptr_t Bits;
    … …  
    111112        MarkedAllocator* allocator() const;
    112113        Heap* heap() const;
     114        inline MarkedSpace* space() const;
    113115        VM* vm() const;
    114116        WeakSet& weakSet();
    … …  
    142144        FreeList resumeAllocating(); // Call this if you canonicalized a block for some non-collection related purpose.
    143145           
    144         // Returns true if the "newly allocated" bitmap was non-null
    145         // and was successfully cleared and false otherwise.
    146         bool clearNewlyAllocated();
    147            
    148146        size_t cellSize();
     147        inline unsigned cellsPerBlock();
     148       
    149149        const AllocatorAttributes& attributes() const;
    150150        DestructionMode destruction() const;
    … …  
    154154        size_t markCount();
    155155        size_t size();
    156            
    157         inline bool isLive(HeapVersion markingVersion, const HeapCell*);
    158         inline bool isLiveCell(HeapVersion markingVersion, const void*);
     156       
     157        inline bool isLive(HeapVersion markingVersion, bool isMarking, const HeapCell*);
     158        inline bool isLiveCell(HeapVersion markingVersion, bool isMarking, const void*);
    159159
    160160        bool isLive(const HeapCell*);
    … …  
    165165        void clearNewlyAllocated(const void*);
    166166       
    167         bool hasAnyNewlyAllocated() const { return !!m_newlyAllocated; }
    168            
     167        HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
     168       
     169        inline bool isNewlyAllocatedStale() const;
     170       
     171        inline bool hasAnyNewlyAllocated();
     172        void resetAllocated();
     173       
    169174        template <typename Functor> IterationStatus forEachCell(const Functor&);
    170175        template <typename Functor> inline IterationStatus forEachLiveCell(const Functor&);
    … …  
    186191    private:
    187192        Handle(Heap&, void*);
    188            
     193       
    189194        template<DestructionMode>
    190195        FreeList sweepHelperSelectScribbleMode(SweepMode = SweepOnly);
    … …  
    224229        size_t m_endAtom { std::numeric_limits<size_t>::max() }; // This is a fuzzy end. Always test for < m_endAtom.
    225230           
    226         std::unique_ptr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
     231        WTF::Bitmap<atomsPerBlock> m_newlyAllocated;
    227232           
    228233        AllocatorAttributes m_attributes;
    … …  
    232237        size_t m_index { std::numeric_limits<size_t>::max() };
    233238        WeakSet m_weakSet;
     239       
     240        HeapVersion m_newlyAllocatedVersion;
    234241           
    235242        MarkedBlock* m_block { nullptr };
    … …  
    241248       
    242249    VM* vm() const;
     250    inline Heap* heap() const;
     251    inline MarkedSpace* space() const;
    243252
    244253    static bool isAtomAligned(const void*);
    … …  
    279288    bool needsDestruction() const { return m_needsDestruction; }
    280289   
    281     inline void resetMarkingVersion();
     290    // This is usually a no-op, and we use it as a no-op that touches the page in isPagedOut().
     291    void updateNeedsDestruction();
     292   
     293    void resetMarks();
    282294   
    283295private:
    … …  
    290302       
    291303    void aboutToMarkSlow(HeapVersion markingVersion);
    292     void clearMarks();
    293     void clearMarks(HeapVersion markingVersion);
    294304    void clearHasAnyMarked();
    295305   
    296306    void noteMarkedSlow();
    297        
    298     WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_marks;
     307   
     308    inline bool marksConveyLivenessDuringMarking(HeapVersion markingVersion);
     309       
     310    WTF::Bitmap<atomsPerBlock> m_marks;
    299311
    300312    bool m_needsDestruction;
    … …  
    522534inline bool MarkedBlock::Handle::isNewlyAllocated(const void* p)
    523535{
    524     return m_newlyAllocated->get(m_block->atomNumber(p));
     536    return m_newlyAllocated.get(m_block->atomNumber(p));
    525537}
    526538
    527539inline void MarkedBlock::Handle::setNewlyAllocated(const void* p)
    528540{
    529     m_newlyAllocated->set(m_block->atomNumber(p));
     541    m_newlyAllocated.set(m_block->atomNumber(p));
    530542}
    531543
    532544inline void MarkedBlock::Handle::clearNewlyAllocated(const void* p)
    533545{
    534     m_newlyAllocated->clear(m_block->atomNumber(p));
    535 }
    536 
    537 inline bool MarkedBlock::Handle::clearNewlyAllocated()
    538 {
    539     if (m_newlyAllocated) {
    540         m_newlyAllocated = nullptr;
    541         return true;
    542     }
    543     return false;
     546    m_newlyAllocated.clear(m_block->atomNumber(p));
    544547}
    545548

  • trunk/Source/JavaScriptCore/heap/MarkedBlockInlines.h

    r206172 r207179  
    2828#include "MarkedAllocator.h"
    2929#include "MarkedBlock.h"
     30#include "MarkedSpace.h"
    3031
    3132namespace JSC {
    3233
    33 inline bool MarkedBlock::Handle::isLive(HeapVersion markingVersion, const HeapCell* cell)
     34inline unsigned MarkedBlock::Handle::cellsPerBlock()
     35{
     36    return MarkedSpace::blockPayload / cellSize();
     37}
     38
     39inline bool MarkedBlock::marksConveyLivenessDuringMarking(HeapVersion markingVersion)
     40{
     41    // This returns true if any of these is true:
     42    // - We just created the block and so the bits are clear already.
     43    // - This block has objects marked during the last GC, and so its version was up-to-date just
     44    //   before the current collection did beginMarking(). This means that any objects that have
     45    //   their mark bit set are valid objects that were never deleted, and so are candidates for
     46    //   marking in any conservative scan. Using our jargon, they are "live".
     47    // - We did ~2^32 collections and rotated the version back to null, so we needed to hard-reset
     48    //   everything. If the marks had been stale, we would have cleared them. So, we can be sure that
     49    //   any set mark bit reflects objects marked during last GC, i.e. "live" objects.
     50    // It would be absurd to use this method when not collecting, since this special "one version
     51    // back" state only makes sense when we're in a concurrent collection and have to be
     52    // conservative.
     53    ASSERT(space()->isMarking());
     54    return m_markingVersion == MarkedSpace::nullVersion
     55        || MarkedSpace::nextVersion(m_markingVersion) == markingVersion;
     56}
     57
     58inline bool MarkedBlock::Handle::isLive(HeapVersion markingVersion, bool isMarking, const HeapCell* cell)
    3459{
    3560    ASSERT(!isFreeListed());
    … …  
    4065    }
    4166   
    42     MarkedBlock& block = this->block();
    43    
    4467    if (allocator()->isAllocated(this))
    4568        return true;
    4669   
    47     if (block.areMarksStale(markingVersion))
    48         return false;
     70    MarkedBlock& block = this->block();
     71   
     72    if (block.areMarksStale()) {
     73        if (!isMarking)
     74            return false;
     75        if (!block.marksConveyLivenessDuringMarking(markingVersion))
     76            return false;
     77    }
    4978
    50     return block.isMarked(cell);
     79    return block.m_marks.get(block.atomNumber(cell));
    5180}
    5281
    53 inline bool MarkedBlock::Handle::isLiveCell(HeapVersion markingVersion, const void* p)
     82inline bool MarkedBlock::Handle::isLiveCell(HeapVersion markingVersion, bool isMarking, const void* p)
    5483{
    5584    if (!m_block->isAtom(p))
    5685        return false;
    57     return isLive(markingVersion, static_cast<const HeapCell*>(p));
     86    return isLive(markingVersion, isMarking, static_cast<const HeapCell*>(p));
     87}
     88
     89inline bool MarkedBlock::Handle::isNewlyAllocatedStale() const
     90{
     91    return m_newlyAllocatedVersion != space()->newlyAllocatedVersion();
     92}
     93
     94inline bool MarkedBlock::Handle::hasAnyNewlyAllocated()
     95{
     96    return !isNewlyAllocatedStale();
    5897}
    5998
    … …  
    88127}
    89128
    90 inline void MarkedBlock::resetMarkingVersion()
     129inline Heap* MarkedBlock::heap() const
    91130{
    92     m_markingVersion = MarkedSpace::nullVersion;
     131    return &vm()->heap;
     132}
     133
     134inline MarkedSpace* MarkedBlock::space() const
     135{
     136    return &heap()->objectSpace();
     137}
     138
     139inline MarkedSpace* MarkedBlock::Handle::space() const
     140{
     141    return &heap()->objectSpace();
    93142}
    94143

  • trunk/Source/JavaScriptCore/heap/MarkedSpace.cpp

    r206555 r207179  
    452452}
    453453
    454 void MarkedSpace::clearNewlyAllocated()
    455 {
    456     forEachAllocator(
    457         [&] (MarkedAllocator& allocator) -> IterationStatus {
    458             if (MarkedBlock::Handle* block = allocator.takeLastActiveBlock())
    459                 block->clearNewlyAllocated();
    460             return IterationStatus::Continue;
    461         });
    462    
    463     for (unsigned i = m_largeAllocationsOffsetForThisCollection; i < m_largeAllocations.size(); ++i)
    464         m_largeAllocations[i]->clearNewlyAllocated();
    465 
    466     if (!ASSERT_DISABLED) {
    467         forEachBlock(
    468             [&] (MarkedBlock::Handle* block) {
    469                 ASSERT_UNUSED(block, !block->clearNewlyAllocated());
    470             });
    471        
    472         for (LargeAllocation* allocation : m_largeAllocations)
    473             ASSERT_UNUSED(allocation, !allocation->isNewlyAllocated());
    474     }
    475 }
    476 
    477454void MarkedSpace::beginMarking()
    478455{
    … …  
    484461            });
    485462
    486         m_markingVersion = nextVersion(m_markingVersion);
    487        
    488         if (UNLIKELY(m_markingVersion == initialVersion)) {
    489             // Oh no! Version wrap-around! We handle this by setting all block versions to null.
     463        if (UNLIKELY(nextVersion(m_markingVersion) == initialVersion)) {
    490464            forEachBlock(
    491465                [&] (MarkedBlock::Handle* handle) {
    492                     handle->block().resetMarkingVersion();
     466                    handle->block().resetMarks();
    493467                });
    494468        }
     469       
     470        m_markingVersion = nextVersion(m_markingVersion);
    495471       
    496472        for (LargeAllocation* allocation : m_largeAllocations)
    … …  
    512488void MarkedSpace::endMarking()
    513489{
     490    if (UNLIKELY(nextVersion(m_newlyAllocatedVersion) == initialVersion)) {
     491        forEachBlock(
     492            [&] (MarkedBlock::Handle* handle) {
     493                handle->resetAllocated();
     494            });
     495    }
     496       
     497    m_newlyAllocatedVersion = nextVersion(m_newlyAllocatedVersion);
     498   
     499    for (unsigned i = m_largeAllocationsOffsetForThisCollection; i < m_largeAllocations.size(); ++i)
     500        m_largeAllocations[i]->clearNewlyAllocated();
     501
     502    if (!ASSERT_DISABLED) {
     503        for (LargeAllocation* allocation : m_largeAllocations)
     504            ASSERT_UNUSED(allocation, !allocation->isNewlyAllocated());
     505    }
     506
    514507    forEachAllocator(
    515508        [&] (MarkedAllocator& allocator) -> IterationStatus {

  • trunk/Source/JavaScriptCore/heap/MarkedSpace.h

    r206555 r207179  
    6666   
    6767    static const HeapVersion nullVersion = 0; // The version of freshly allocated blocks.
    68     static const HeapVersion initialVersion = 1; // The version that the heap starts out with.
    69    
    70     HeapVersion nextVersion(HeapVersion version)
     68    static const HeapVersion initialVersion = 2; // The version that the heap starts out with. Set to make sure that nextVersion(nullVersion) != initialVersion.
     69   
     70    static HeapVersion nextVersion(HeapVersion version)
    7171    {
    7272        version++;
    7373        if (version == nullVersion)
    74             version++;
     74            version = initialVersion;
    7575        return version;
    7676    }
    … …  
    172172   
    173173    HeapVersion markingVersion() const { return m_markingVersion; }
     174    HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
    174175
    175176    const Vector<LargeAllocation*>& largeAllocations() const { return m_largeAllocations; }
    … …  
    218219    Heap* m_heap;
    219220    HeapVersion m_markingVersion { initialVersion };
     221    HeapVersion m_newlyAllocatedVersion { initialVersion };
    220222    size_t m_capacity;
    221223    bool m_isIterating;

  • trunk/Source/JavaScriptCore/heap/SlotVisitor.cpp

    r206530 r207179  
    191191    validate(cell);
    192192#endif
    193    
    194     //dataLog("    Marking ", RawPointer(cell), "\n");
    195193   
    196194    if (cell->isLargeAllocation())

  • trunk/Source/JavaScriptCore/runtime/SamplingProfiler.cpp

    r206459 r207179  
    3131#include "CallFrame.h"
    3232#include "CodeBlock.h"
     33#include "CodeBlockSet.h"
    3334#include "Executable.h"
    3435#include "HeapInlines.h"

  • trunk/Source/WTF/ChangeLog

    r207156 r207179  
     12016-10-08  Filip Pizlo  <fpizlo@apple.com>
     2
     3        MarkedBlock should know what objects are live during marking
     4        https://bugs.webkit.org/show_bug.cgi?id=162309
     5
     6        Reviewed by Geoffrey Garen.
     7       
     8        This removes the atomicity mode, because it's not really used: it only affects the
     9        concurrentBlah methods, but their only users turn on atomicity. This was useful because
     10        previously, some binary Bitmap methods (like merge(const Bitmap&)) couldn't be used
     11        effectively in the GC because some of the GC's bitmaps set the atomic mode and some didn't.
     12        Removing this useless mode is the best solution.
     13       
     14        Also added some new binary Bitmap methods: mergeAndClear(Bitmap& other) and
     15        setAndClear(Bitmap& other). They perform their action on 'this' (either merge or set,
     16        respectively) while also clearing the contents of 'other'. This is great for one of the GC
     17        hot paths.
     18
     19        * wtf/Bitmap.h:
     20        (WTF::WordType>::Bitmap):
     21        (WTF::WordType>::get):
     22        (WTF::WordType>::set):
     23        (WTF::WordType>::testAndSet):
     24        (WTF::WordType>::testAndClear):
     25        (WTF::WordType>::concurrentTestAndSet):
     26        (WTF::WordType>::concurrentTestAndClear):
     27        (WTF::WordType>::clear):
     28        (WTF::WordType>::clearAll):
     29        (WTF::WordType>::nextPossiblyUnset):
     30        (WTF::WordType>::findRunOfZeros):
     31        (WTF::WordType>::count):
     32        (WTF::WordType>::isEmpty):
     33        (WTF::WordType>::isFull):
     34        (WTF::WordType>::merge):
     35        (WTF::WordType>::filter):
     36        (WTF::WordType>::exclude):
     37        (WTF::WordType>::forEachSetBit):
     38        (WTF::WordType>::mergeAndClear):
     39        (WTF::WordType>::setAndClear):
     40        (WTF::=):
     41        (WTF::WordType>::hash):
     42
    1432016-10-11  Said Abou-Hallawa  <sabouhallawa@apple.com>
    244

  • trunk/Source/WTF/wtf/Bitmap.h

    r203365 r207179  
    2828namespace WTF {
    2929
    30 enum BitmapAtomicMode {
    31     // This makes concurrentTestAndSet behave just like testAndSet.
    32     BitmapNotAtomic,
    33 
    34     // This makes concurrentTestAndSet use compareAndSwap, so that it's
    35     // atomic even when used concurrently.
    36     BitmapAtomic
    37 };
    38 
    39 template<size_t bitmapSize, BitmapAtomicMode atomicMode = BitmapNotAtomic, typename WordType = uint32_t>
     30template<size_t bitmapSize, typename WordType = uint32_t>
    4031class Bitmap {
    4132    WTF_MAKE_FAST_ALLOCATED;
    … …  
    6051    void clear(size_t);
    6152    void clearAll();
    62     int64_t findRunOfZeros(size_t) const;
    63     size_t count(size_t = 0) const;
     53    int64_t findRunOfZeros(size_t runLength) const;
     54    size_t count(size_t start = 0) const;
    6455    size_t isEmpty() const;
    6556    size_t isFull() const;
    … …  
    7162    template<typename Func>
    7263    void forEachSetBit(const Func&) const;
     64   
     65    void mergeAndClear(Bitmap&);
     66    void setAndClear(Bitmap&);
    7367   
    7468    bool operator==(const Bitmap&) const;
    … …  
    9185};
    9286
    93 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    94 inline Bitmap<bitmapSize, atomicMode, WordType>::Bitmap()
     87template<size_t bitmapSize, typename WordType>
     88inline Bitmap<bitmapSize, WordType>::Bitmap()
    9589{
    9690    clearAll();
    9791}
    9892
    99 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    100 inline bool Bitmap<bitmapSize, atomicMode, WordType>::get(size_t n) const
     93template<size_t bitmapSize, typename WordType>
     94inline bool Bitmap<bitmapSize, WordType>::get(size_t n) const
    10195{
    10296    return !!(bits[n / wordSize] & (one << (n % wordSize)));
    10397}
    10498
    105 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    106 inline void Bitmap<bitmapSize, atomicMode, WordType>::set(size_t n)
     99template<size_t bitmapSize, typename WordType>
     100inline void Bitmap<bitmapSize, WordType>::set(size_t n)
    107101{
    108102    bits[n / wordSize] |= (one << (n % wordSize));
    109103}
    110104
    111 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    112 inline void Bitmap<bitmapSize, atomicMode, WordType>::set(size_t n, bool value)
     105template<size_t bitmapSize, typename WordType>
     106inline void Bitmap<bitmapSize, WordType>::set(size_t n, bool value)
    113107{
    114108    if (value)
    … …  
    118112}
    119113
    120 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    121 inline bool Bitmap<bitmapSize, atomicMode, WordType>::testAndSet(size_t n)
     114template<size_t bitmapSize, typename WordType>
     115inline bool Bitmap<bitmapSize, WordType>::testAndSet(size_t n)
    122116{
    123117    WordType mask = one << (n % wordSize);
    … …  
    128122}
    129123
    130 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    131 inline bool Bitmap<bitmapSize, atomicMode, WordType>::testAndClear(size_t n)
     124template<size_t bitmapSize, typename WordType>
     125inline bool Bitmap<bitmapSize, WordType>::testAndClear(size_t n)
    132126{
    133127    WordType mask = one << (n % wordSize);
    … …  
    138132}
    139133
    140 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    141 inline bool Bitmap<bitmapSize, atomicMode, WordType>::concurrentTestAndSet(size_t n)
    142 {
    143     if (atomicMode == BitmapNotAtomic)
    144         return testAndSet(n);
    145 
    146     ASSERT(atomicMode == BitmapAtomic);
    147    
     134template<size_t bitmapSize, typename WordType>
     135inline bool Bitmap<bitmapSize, WordType>::concurrentTestAndSet(size_t n)
     136{
    148137    WordType mask = one << (n % wordSize);
    149138    size_t index = n / wordSize;
    … …  
    158147}
    159148
    160 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    161 inline bool Bitmap<bitmapSize, atomicMode, WordType>::concurrentTestAndClear(size_t n)
    162 {
    163     if (atomicMode == BitmapNotAtomic)
    164         return testAndClear(n);
    165 
    166     ASSERT(atomicMode == BitmapAtomic);
    167    
     149template<size_t bitmapSize, typename WordType>
     150inline bool Bitmap<bitmapSize, WordType>::concurrentTestAndClear(size_t n)
     151{
    168152    WordType mask = one << (n % wordSize);
    169153    size_t index = n / wordSize;
    … …  
    178162}
    179163
    180 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    181 inline void Bitmap<bitmapSize, atomicMode, WordType>::clear(size_t n)
     164template<size_t bitmapSize, typename WordType>
     165inline void Bitmap<bitmapSize, WordType>::clear(size_t n)
    182166{
    183167    bits[n / wordSize] &= ~(one << (n % wordSize));
    184168}
    185169
    186 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    187 inline void Bitmap<bitmapSize, atomicMode, WordType>::clearAll()
     170template<size_t bitmapSize, typename WordType>
     171inline void Bitmap<bitmapSize, WordType>::clearAll()
    188172{
    189173    memset(bits.data(), 0, sizeof(bits));
    190174}
    191175
    192 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    193 inline size_t Bitmap<bitmapSize, atomicMode, WordType>::nextPossiblyUnset(size_t start) const
     176template<size_t bitmapSize, typename WordType>
     177inline size_t Bitmap<bitmapSize, WordType>::nextPossiblyUnset(size_t start) const
    194178{
    195179    if (!~bits[start / wordSize])
    … …  
    198182}
    199183
    200 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    201 inline int64_t Bitmap<bitmapSize, atomicMode, WordType>::findRunOfZeros(size_t runLength) const
     184template<size_t bitmapSize, typename WordType>
     185inline int64_t Bitmap<bitmapSize, WordType>::findRunOfZeros(size_t runLength) const
    202186{
    203187    if (!runLength)
    … …  
    218202}
    219203
    220 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    221 inline size_t Bitmap<bitmapSize, atomicMode, WordType>::count(size_t start) const
     204template<size_t bitmapSize, typename WordType>
     205inline size_t Bitmap<bitmapSize, WordType>::count(size_t start) const
    222206{
    223207    size_t result = 0;
    … …  
    231215}
    232216
    233 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    234 inline size_t Bitmap<bitmapSize, atomicMode, WordType>::isEmpty() const
     217template<size_t bitmapSize, typename WordType>
     218inline size_t Bitmap<bitmapSize, WordType>::isEmpty() const
    235219{
    236220    for (size_t i = 0; i < words; ++i)
    … …  
    240224}
    241225
    242 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    243 inline size_t Bitmap<bitmapSize, atomicMode, WordType>::isFull() const
     226template<size_t bitmapSize, typename WordType>
     227inline size_t Bitmap<bitmapSize, WordType>::isFull() const
    244228{
    245229    for (size_t i = 0; i < words; ++i)
    … …  
    249233}
    250234
    251 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    252 inline void Bitmap<bitmapSize, atomicMode, WordType>::merge(const Bitmap& other)
     235template<size_t bitmapSize, typename WordType>
     236inline void Bitmap<bitmapSize, WordType>::merge(const Bitmap& other)
    253237{
    254238    for (size_t i = 0; i < words; ++i)
    … …  
    256240}
    257241
    258 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    259 inline void Bitmap<bitmapSize, atomicMode, WordType>::filter(const Bitmap& other)
     242template<size_t bitmapSize, typename WordType>
     243inline void Bitmap<bitmapSize, WordType>::filter(const Bitmap& other)
    260244{
    261245    for (size_t i = 0; i < words; ++i)
    … …  
    263247}
    264248
    265 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    266 inline void Bitmap<bitmapSize, atomicMode, WordType>::exclude(const Bitmap& other)
     249template<size_t bitmapSize, typename WordType>
     250inline void Bitmap<bitmapSize, WordType>::exclude(const Bitmap& other)
    267251{
    268252    for (size_t i = 0; i < words; ++i)
    … …  
    270254}
    271255
    272 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
     256template<size_t bitmapSize, typename WordType>
    273257template<typename Func>
    274 inline void Bitmap<bitmapSize, atomicMode, WordType>::forEachSetBit(const Func& func) const
     258inline void Bitmap<bitmapSize, WordType>::forEachSetBit(const Func& func) const
    275259{
    276260    for (size_t i = 0; i < words; ++i) {
    … …  
    287271}
    288272
    289 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    290 inline bool Bitmap<bitmapSize, atomicMode, WordType>::operator==(const Bitmap& other) const
     273template<size_t bitmapSize, typename WordType>
     274inline void Bitmap<bitmapSize, WordType>::mergeAndClear(Bitmap& other)
     275{
     276    for (size_t i = 0; i < words; ++i) {
     277        bits[i] |= other.bits[i];
     278        other.bits[i] = 0;
     279    }
     280}
     281
     282template<size_t bitmapSize, typename WordType>
     283inline void Bitmap<bitmapSize, WordType>::setAndClear(Bitmap& other)
     284{
     285    for (size_t i = 0; i < words; ++i) {
     286        bits[i] = other.bits[i];
     287        other.bits[i] = 0;
     288    }
     289}
     290
     291template<size_t bitmapSize, typename WordType>
     292inline bool Bitmap<bitmapSize, WordType>::operator==(const Bitmap& other) const
    291293{
    292294    for (size_t i = 0; i < words; ++i) {
    … …  
    297299}
    298300
    299 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    300 inline bool Bitmap<bitmapSize, atomicMode, WordType>::operator!=(const Bitmap& other) const
     301template<size_t bitmapSize, typename WordType>
     302inline bool Bitmap<bitmapSize, WordType>::operator!=(const Bitmap& other) const
    301303{
    302304    return !(*this == other);
    303305}
    304306
    305 template<size_t bitmapSize, BitmapAtomicMode atomicMode, typename WordType>
    306 inline unsigned Bitmap<bitmapSize, atomicMode, WordType>::hash() const
     307template<size_t bitmapSize, typename WordType>
     308inline unsigned Bitmap<bitmapSize, WordType>::hash() const
    307309{
    308310    unsigned result = 0;
Note: See TracChangeset for help on using the changeset viewer.