heap/MarkedSpace.cpp

   1 /*
   2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   3  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  */
  20
  21 #include "config.h"
  22 #include "MarkedSpace.h"
  23
  24 #include "DelayedReleaseScope.h"
  25 #include "IncrementalSweeper.h"
  26 #include "JSGlobalObject.h"
  27 #include "JSLock.h"
  28 #include "JSObject.h"
  29 #include "JSCInlines.h"
  30
  31 namespace JSC {
  32
  33 class Structure;
  34
  35 class Free {
  36 public:
  37     typedef MarkedBlock* ReturnType;
  38
  39     enum FreeMode { FreeOrShrink, FreeAll };
  40
  41     Free(FreeMode, MarkedSpace*);
  42     void operator()(MarkedBlock*);
  43     ReturnType returnValue();
  44
  45 private:
  46     FreeMode m_freeMode;
  47     MarkedSpace* m_markedSpace;
  48     DoublyLinkedList<MarkedBlock> m_blocks;
  49 };
  50
  51 inline Free::Free(FreeMode freeMode, MarkedSpace* newSpace)
  52     : m_freeMode(freeMode)
  53     , m_markedSpace(newSpace)
  54 {
  55 }
  56
  57 inline void Free::operator()(MarkedBlock* block)
  58 {
  59     if (m_freeMode == FreeOrShrink)
  60         m_markedSpace->freeOrShrinkBlock(block);
  61     else
  62         m_markedSpace->freeBlock(block);
  63 }
  64
  65 inline Free::ReturnType Free::returnValue()
  66 {
  67     return m_blocks.head();
  68 }
  69
  70 struct VisitWeakSet : MarkedBlock::VoidFunctor {
  71     VisitWeakSet(HeapRootVisitor& heapRootVisitor) : m_heapRootVisitor(heapRootVisitor) { }
  72     void operator()(MarkedBlock* block) { block->visitWeakSet(m_heapRootVisitor); }
  73 private:
  74     HeapRootVisitor& m_heapRootVisitor;
  75 };
  76
  77 struct ReapWeakSet : MarkedBlock::VoidFunctor {
  78     void operator()(MarkedBlock* block) { block->reapWeakSet(); }
  79 };
  80
  81 MarkedSpace::MarkedSpace(Heap* heap)
  82     : m_heap(heap)
  83     , m_capacity(0)
  84     , m_isIterating(false)
  85     , m_currentDelayedReleaseScope(nullptr)
  86 {
  87     for (size_t cellSize = preciseStep; cellSize <= preciseCutoff; cellSize += preciseStep) {
  88         allocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::None);
  89         normalDestructorAllocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::Normal);
  90         immortalStructureDestructorAllocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::ImmortalStructure);
  91     }
  92
  93     for (size_t cellSize = impreciseStep; cellSize <= impreciseCutoff; cellSize += impreciseStep) {
  94         allocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::None);
  95         normalDestructorAllocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::Normal);
  96         immortalStructureDestructorAllocatorFor(cellSize).init(heap, this, cellSize, MarkedBlock::ImmortalStructure);
  97     }
  98
  99     m_normalSpace.largeAllocator.init(heap, this, 0, MarkedBlock::None);
 100     m_normalDestructorSpace.largeAllocator.init(heap, this, 0, MarkedBlock::Normal);
 101     m_immortalStructureDestructorSpace.largeAllocator.init(heap, this, 0, MarkedBlock::ImmortalStructure);
 102 }
 103
 104 MarkedSpace::~MarkedSpace()
 105 {
 106     Free free(Free::FreeAll, this);
 107     forEachBlock(free);
 108     ASSERT(!m_blocks.set().size());
 109 }
 110
 111 struct LastChanceToFinalize {
 112     void operator()(MarkedAllocator& allocator) { allocator.lastChanceToFinalize(); }
 113 };
 114
 115 void MarkedSpace::lastChanceToFinalize()
 116 {
 117     DelayedReleaseScope delayedReleaseScope(*this);
 118     stopAllocating();
 119     forEachAllocator<LastChanceToFinalize>();
 120 }
 121
 122 void MarkedSpace::sweep()
 123 {
 124     if (Options::logGC())
 125         dataLog("Eagerly sweeping...");
 126     m_heap->sweeper()->willFinishSweeping();
 127     forEachBlock<Sweep>();
 128 }
 129
 130 void MarkedSpace::zombifySweep()
 131 {
 132     if (Options::logGC())
 133         dataLog("Zombifying sweep...");
 134     m_heap->sweeper()->willFinishSweeping();
 135     forEachBlock<ZombifySweep>();
 136 }
 137
 138 void MarkedSpace::resetAllocators()
 139 {
 140     for (size_t cellSize = preciseStep; cellSize <= preciseCutoff; cellSize += preciseStep) {
 141         allocatorFor(cellSize).reset();
 142         normalDestructorAllocatorFor(cellSize).reset();
 143         immortalStructureDestructorAllocatorFor(cellSize).reset();
 144     }
 145
 146     for (size_t cellSize = impreciseStep; cellSize <= impreciseCutoff; cellSize += impreciseStep) {
 147         allocatorFor(cellSize).reset();
 148         normalDestructorAllocatorFor(cellSize).reset();
 149         immortalStructureDestructorAllocatorFor(cellSize).reset();
 150     }
 151
 152     m_normalSpace.largeAllocator.reset();
 153     m_normalDestructorSpace.largeAllocator.reset();
 154     m_immortalStructureDestructorSpace.largeAllocator.reset();
 155
 156 #if ENABLE(GGC)
 157     m_blocksWithNewObjects.clear();
 158 #endif
 159 }
 160
 161 void MarkedSpace::visitWeakSets(HeapRootVisitor& heapRootVisitor)
 162 {
 163     VisitWeakSet visitWeakSet(heapRootVisitor);
 164     if (m_heap->operationInProgress() == EdenCollection) {
 165         for (unsigned i = 0; i < m_blocksWithNewObjects.size(); ++i)
 166             visitWeakSet(m_blocksWithNewObjects[i]);
 167     } else
 168         forEachBlock(visitWeakSet);
 169 }
 170
 171 void MarkedSpace::reapWeakSets()
 172 {
 173     if (m_heap->operationInProgress() == EdenCollection) {
 174         for (unsigned i = 0; i < m_blocksWithNewObjects.size(); ++i)
 175             m_blocksWithNewObjects[i]->reapWeakSet();
 176     } else
 177         forEachBlock<ReapWeakSet>();
 178 }
 179
 180 template <typename Functor>
 181 void MarkedSpace::forEachAllocator()
 182 {
 183     Functor functor;
 184     forEachAllocator(functor);
 185 }
 186
 187 template <typename Functor>
 188 void MarkedSpace::forEachAllocator(Functor& functor)
 189 {
 190     for (size_t cellSize = preciseStep; cellSize <= preciseCutoff; cellSize += preciseStep) {
 191         functor(allocatorFor(cellSize));
 192         functor(normalDestructorAllocatorFor(cellSize));
 193         functor(immortalStructureDestructorAllocatorFor(cellSize));
 194     }
 195
 196     for (size_t cellSize = impreciseStep; cellSize <= impreciseCutoff; cellSize += impreciseStep) {
 197         functor(allocatorFor(cellSize));
 198         functor(normalDestructorAllocatorFor(cellSize));
 199         functor(immortalStructureDestructorAllocatorFor(cellSize));
 200     }
 201
 202     functor(m_normalSpace.largeAllocator);
 203     functor(m_normalDestructorSpace.largeAllocator);
 204     functor(m_immortalStructureDestructorSpace.largeAllocator);
 205 }
 206
 207 struct StopAllocatingFunctor {
 208     void operator()(MarkedAllocator& allocator) { allocator.stopAllocating(); }
 209 };
 210
 211 void MarkedSpace::stopAllocating()
 212 {
 213     ASSERT(!isIterating());
 214     forEachAllocator<StopAllocatingFunctor>();
 215 }
 216
 217 struct ResumeAllocatingFunctor {
 218     void operator()(MarkedAllocator& allocator) { allocator.resumeAllocating(); }
 219 };
 220
 221 void MarkedSpace::resumeAllocating()
 222 {
 223     ASSERT(isIterating());
 224     forEachAllocator<ResumeAllocatingFunctor>();
 225 }
 226
 227 bool MarkedSpace::isPagedOut(double deadline)
 228 {
 229     for (size_t cellSize = preciseStep; cellSize <= preciseCutoff; cellSize += preciseStep) {
 230         if (allocatorFor(cellSize).isPagedOut(deadline)
 231             || normalDestructorAllocatorFor(cellSize).isPagedOut(deadline)
 232             || immortalStructureDestructorAllocatorFor(cellSize).isPagedOut(deadline))
 233             return true;
 234     }
 235
 236     for (size_t cellSize = impreciseStep; cellSize <= impreciseCutoff; cellSize += impreciseStep) {
 237         if (allocatorFor(cellSize).isPagedOut(deadline)
 238             || normalDestructorAllocatorFor(cellSize).isPagedOut(deadline)
 239             || immortalStructureDestructorAllocatorFor(cellSize).isPagedOut(deadline))
 240             return true;
 241     }
 242
 243     if (m_normalSpace.largeAllocator.isPagedOut(deadline)
 244         || m_normalDestructorSpace.largeAllocator.isPagedOut(deadline)
 245         || m_immortalStructureDestructorSpace.largeAllocator.isPagedOut(deadline))
 246         return true;
 247
 248     return false;
 249 }
 250
 251 void MarkedSpace::freeBlock(MarkedBlock* block)
 252 {
 253     block->allocator()->removeBlock(block);
 254     m_capacity -= block->capacity();
 255     m_blocks.remove(block);
 256     if (block->capacity() == MarkedBlock::blockSize) {
 257         m_heap->blockAllocator().deallocate(MarkedBlock::destroy(block));
 258         return;
 259     }
 260     m_heap->blockAllocator().deallocateCustomSize(MarkedBlock::destroy(block));
 261 }
 262
 263 void MarkedSpace::freeOrShrinkBlock(MarkedBlock* block)
 264 {
 265     if (!block->isEmpty()) {
 266         block->shrink();
 267         return;
 268     }
 269
 270     freeBlock(block);
 271 }
 272
 273 struct Shrink : MarkedBlock::VoidFunctor {
 274     void operator()(MarkedBlock* block) { block->shrink(); }
 275 };
 276
 277 void MarkedSpace::shrink()
 278 {
 279     Free freeOrShrink(Free::FreeOrShrink, this);
 280     forEachBlock(freeOrShrink);
 281 }
 282
 283 static void clearNewlyAllocatedInBlock(MarkedBlock* block)
 284 {
 285     if (!block)
 286         return;
 287     block->clearNewlyAllocated();
 288 }
 289
 290 struct ClearNewlyAllocated : MarkedBlock::VoidFunctor {
 291     void operator()(MarkedBlock* block) { block->clearNewlyAllocated(); }
 292 };
 293
 294 #ifndef NDEBUG
 295 struct VerifyNewlyAllocated : MarkedBlock::VoidFunctor {
 296     void operator()(MarkedBlock* block) { ASSERT(!block->clearNewlyAllocated()); }
 297 };
 298 #endif
 299
 300 void MarkedSpace::clearNewlyAllocated()
 301 {
 302     for (size_t i = 0; i < preciseCount; ++i) {
 303         clearNewlyAllocatedInBlock(m_normalSpace.preciseAllocators[i].takeLastActiveBlock());
 304         clearNewlyAllocatedInBlock(m_normalDestructorSpace.preciseAllocators[i].takeLastActiveBlock());
 305         clearNewlyAllocatedInBlock(m_immortalStructureDestructorSpace.preciseAllocators[i].takeLastActiveBlock());
 306     }
 307
 308     for (size_t i = 0; i < impreciseCount; ++i) {
 309         clearNewlyAllocatedInBlock(m_normalSpace.impreciseAllocators[i].takeLastActiveBlock());
 310         clearNewlyAllocatedInBlock(m_normalDestructorSpace.impreciseAllocators[i].takeLastActiveBlock());
 311         clearNewlyAllocatedInBlock(m_immortalStructureDestructorSpace.impreciseAllocators[i].takeLastActiveBlock());
 312     }
 313
 314     // We have to iterate all of the blocks in the large allocators because they are
 315     // canonicalized as they are used up (see MarkedAllocator::tryAllocateHelper)
 316     // which creates the m_newlyAllocated bitmap.
 317     ClearNewlyAllocated functor;
 318     m_normalSpace.largeAllocator.forEachBlock(functor);
 319     m_normalDestructorSpace.largeAllocator.forEachBlock(functor);
 320     m_immortalStructureDestructorSpace.largeAllocator.forEachBlock(functor);
 321
 322 #ifndef NDEBUG
 323     VerifyNewlyAllocated verifyFunctor;
 324     forEachBlock(verifyFunctor);
 325 #endif
 326 }
 327
 328 #ifndef NDEBUG
 329 struct VerifyMarkedOrRetired : MarkedBlock::VoidFunctor {
 330     void operator()(MarkedBlock* block)
 331     {
 332         switch (block->m_state) {
 333         case MarkedBlock::Marked:
 334         case MarkedBlock::Retired:
 335             return;
 336         default:
 337             RELEASE_ASSERT_NOT_REACHED();
 338         }
 339     }
 340 };
 341 #endif
 342
 343 void MarkedSpace::clearMarks()
 344 {
 345     if (m_heap->operationInProgress() == EdenCollection) {
 346         for (unsigned i = 0; i < m_blocksWithNewObjects.size(); ++i)
 347             m_blocksWithNewObjects[i]->clearMarks();
 348     } else
 349         forEachBlock<ClearMarks>();
 350
 351 #ifndef NDEBUG
 352     VerifyMarkedOrRetired verifyFunctor;
 353     forEachBlock(verifyFunctor);
 354 #endif
 355 }
 356
 357 void MarkedSpace::willStartIterating()
 358 {
 359     ASSERT(!isIterating());
 360     stopAllocating();
 361     m_isIterating = true;
 362 }
 363
 364 void MarkedSpace::didFinishIterating()
 365 {
 366     ASSERT(isIterating());
 367     DelayedReleaseScope scope(*this);
 368     resumeAllocating();
 369     m_isIterating = false;
 370 }
 371
 372 } // namespace JSC