heap/MarkedSpace.h

   1 /*
   2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
   4  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2011 Apple Inc. All rights reserved.
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation; either
   9  *  version 2 of the License, or (at your option) any later version.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #ifndef MarkedSpace_h
  23 #define MarkedSpace_h
  24
  25 #include "MachineStackMarker.h"
  26 #include "MarkedAllocator.h"
  27 #include "MarkedBlock.h"
  28 #include "MarkedBlockSet.h"
  29 #include <wtf/PageAllocationAligned.h>
  30 #include <wtf/Bitmap.h>
  31 #include <wtf/DoublyLinkedList.h>
  32 #include <wtf/FixedArray.h>
  33 #include <wtf/HashSet.h>
  34 #include <wtf/Noncopyable.h>
  35 #include <wtf/Vector.h>
  36
  37 namespace JSC {
  38
  39 class Heap;
  40 class JSCell;
  41 class LiveObjectIterator;
  42 class LLIntOffsetsExtractor;
  43 class WeakGCHandle;
  44 class SlotVisitor;
  45
  46 struct ClearMarks : MarkedBlock::VoidFunctor {
  47     void operator()(MarkedBlock* block) { block->clearMarks(); }
  48 };
  49
  50 struct Sweep : MarkedBlock::VoidFunctor {
  51     void operator()(MarkedBlock* block) { block->sweep(); }
  52 };
  53
  54 struct MarkCount : MarkedBlock::CountFunctor {
  55     void operator()(MarkedBlock* block) { count(block->markCount()); }
  56 };
  57
  58 struct Size : MarkedBlock::CountFunctor {
  59     void operator()(MarkedBlock* block) { count(block->markCount() * block->cellSize()); }
  60 };
  61
  62 struct Capacity : MarkedBlock::CountFunctor {
  63     void operator()(MarkedBlock* block) { count(block->capacity()); }
  64 };
  65
  66 class MarkedSpace {
  67     WTF_MAKE_NONCOPYABLE(MarkedSpace);
  68 public:
  69     MarkedSpace(Heap*);
  70     ~MarkedSpace();
  71     void lastChanceToFinalize();
  72
  73     MarkedAllocator& firstAllocator();
  74     MarkedAllocator& allocatorFor(size_t);
  75     MarkedAllocator& immortalStructureDestructorAllocatorFor(size_t);
  76     MarkedAllocator& normalDestructorAllocatorFor(size_t);
  77     void* allocateWithNormalDestructor(size_t);
  78     void* allocateWithImmortalStructureDestructor(size_t);
  79     void* allocateWithoutDestructor(size_t);
  80
  81     void resetAllocators();
  82
  83     void visitWeakSets(HeapRootVisitor&);
  84     void reapWeakSets();
  85
  86     MarkedBlockSet& blocks() { return m_blocks; }
  87
  88     void canonicalizeCellLivenessData();
  89
  90     typedef HashSet<MarkedBlock*>::iterator BlockIterator;
  91
  92     template<typename Functor> typename Functor::ReturnType forEachLiveCell(Functor&);
  93     template<typename Functor> typename Functor::ReturnType forEachLiveCell();
  94     template<typename Functor> typename Functor::ReturnType forEachDeadCell(Functor&);
  95     template<typename Functor> typename Functor::ReturnType forEachDeadCell();
  96     template<typename Functor> typename Functor::ReturnType forEachBlock(Functor&);
  97     template<typename Functor> typename Functor::ReturnType forEachBlock();
  98
  99     void shrink();
 100     void freeBlock(MarkedBlock*);
 101     void freeOrShrinkBlock(MarkedBlock*);
 102
 103     void didAddBlock(MarkedBlock*);
 104     void didConsumeFreeList(MarkedBlock*);
 105
 106     void clearMarks();
 107     void sweep();
 108     size_t objectCount();
 109     size_t size();
 110     size_t capacity();
 111
 112     bool isPagedOut(double deadline);
 113
 114 private:
 115     friend class LLIntOffsetsExtractor;
 116
 117     // [ 32... 128 ]
 118     static const size_t preciseStep = MarkedBlock::atomSize;
 119     static const size_t preciseCutoff = 128;
 120     static const size_t preciseCount = preciseCutoff / preciseStep;
 121
 122     // [ 1024... blockSize ]
 123     static const size_t impreciseStep = 2 * preciseCutoff;
 124     static const size_t impreciseCutoff = MarkedBlock::blockSize / 2;
 125     static const size_t impreciseCount = impreciseCutoff / impreciseStep;
 126
 127     struct Subspace {
 128         FixedArray<MarkedAllocator, preciseCount> preciseAllocators;
 129         FixedArray<MarkedAllocator, impreciseCount> impreciseAllocators;
 130         MarkedAllocator largeAllocator;
 131     };
 132
 133     Subspace m_normalDestructorSpace;
 134     Subspace m_immortalStructureDestructorSpace;
 135     Subspace m_normalSpace;
 136
 137     Heap* m_heap;
 138     MarkedBlockSet m_blocks;
 139 };
 140
 141 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachLiveCell(Functor& functor)
 142 {
 143     canonicalizeCellLivenessData();
 144
 145     BlockIterator end = m_blocks.set().end();
 146     for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
 147         (*it)->forEachLiveCell(functor);
 148     return functor.returnValue();
 149 }
 150
 151 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachLiveCell()
 152 {
 153     Functor functor;
 154     return forEachLiveCell(functor);
 155 }
 156
 157 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachDeadCell(Functor& functor)
 158 {
 159     canonicalizeCellLivenessData();
 160
 161     BlockIterator end = m_blocks.set().end();
 162     for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
 163         (*it)->forEachDeadCell(functor);
 164     return functor.returnValue();
 165 }
 166
 167 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachDeadCell()
 168 {
 169     Functor functor;
 170     return forEachDeadCell(functor);
 171 }
 172
 173 inline MarkedAllocator& MarkedSpace::allocatorFor(size_t bytes)
 174 {
 175     ASSERT(bytes);
 176     if (bytes <= preciseCutoff)
 177         return m_normalSpace.preciseAllocators[(bytes - 1) / preciseStep];
 178     if (bytes <= impreciseCutoff)
 179         return m_normalSpace.impreciseAllocators[(bytes - 1) / impreciseStep];
 180     return m_normalSpace.largeAllocator;
 181 }
 182
 183 inline MarkedAllocator& MarkedSpace::immortalStructureDestructorAllocatorFor(size_t bytes)
 184 {
 185     ASSERT(bytes);
 186     if (bytes <= preciseCutoff)
 187         return m_immortalStructureDestructorSpace.preciseAllocators[(bytes - 1) / preciseStep];
 188     if (bytes <= impreciseCutoff)
 189         return m_immortalStructureDestructorSpace.impreciseAllocators[(bytes - 1) / impreciseStep];
 190     return m_immortalStructureDestructorSpace.largeAllocator;
 191 }
 192
 193 inline MarkedAllocator& MarkedSpace::normalDestructorAllocatorFor(size_t bytes)
 194 {
 195     ASSERT(bytes);
 196     if (bytes <= preciseCutoff)
 197         return m_normalDestructorSpace.preciseAllocators[(bytes - 1) / preciseStep];
 198     if (bytes <= impreciseCutoff)
 199         return m_normalDestructorSpace.impreciseAllocators[(bytes - 1) / impreciseStep];
 200     return m_normalDestructorSpace.largeAllocator;
 201 }
 202
 203 inline void* MarkedSpace::allocateWithoutDestructor(size_t bytes)
 204 {
 205     return allocatorFor(bytes).allocate(bytes);
 206 }
 207
 208 inline void* MarkedSpace::allocateWithImmortalStructureDestructor(size_t bytes)
 209 {
 210     return immortalStructureDestructorAllocatorFor(bytes).allocate(bytes);
 211 }
 212
 213 inline void* MarkedSpace::allocateWithNormalDestructor(size_t bytes)
 214 {
 215     return normalDestructorAllocatorFor(bytes).allocate(bytes);
 216 }
 217
 218 template <typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachBlock(Functor& functor)
 219 {
 220     for (size_t i = 0; i < preciseCount; ++i) {
 221         m_normalSpace.preciseAllocators[i].forEachBlock(functor);
 222         m_normalDestructorSpace.preciseAllocators[i].forEachBlock(functor);
 223         m_immortalStructureDestructorSpace.preciseAllocators[i].forEachBlock(functor);
 224     }
 225
 226     for (size_t i = 0; i < impreciseCount; ++i) {
 227         m_normalSpace.impreciseAllocators[i].forEachBlock(functor);
 228         m_normalDestructorSpace.impreciseAllocators[i].forEachBlock(functor);
 229         m_immortalStructureDestructorSpace.impreciseAllocators[i].forEachBlock(functor);
 230     }
 231
 232     m_normalSpace.largeAllocator.forEachBlock(functor);
 233     m_normalDestructorSpace.largeAllocator.forEachBlock(functor);
 234     m_immortalStructureDestructorSpace.largeAllocator.forEachBlock(functor);
 235
 236     return functor.returnValue();
 237 }
 238
 239 template <typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachBlock()
 240 {
 241     Functor functor;
 242     return forEachBlock(functor);
 243 }
 244
 245 inline void MarkedSpace::didAddBlock(MarkedBlock* block)
 246 {
 247     m_blocks.add(block);
 248 }
 249
 250 inline void MarkedSpace::clearMarks()
 251 {
 252     forEachBlock<ClearMarks>();
 253 }
 254
 255 inline size_t MarkedSpace::objectCount()
 256 {
 257     return forEachBlock<MarkCount>();
 258 }
 259
 260 inline size_t MarkedSpace::size()
 261 {
 262     return forEachBlock<Size>();
 263 }
 264
 265 inline size_t MarkedSpace::capacity()
 266 {
 267     return forEachBlock<Capacity>();
 268 }
 269
 270 } // namespace JSC
 271
 272 #endif // MarkedSpace_h