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 #define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) <= MarkedSpace::maxCellSize, class_fits_in_cell)
  38
  39 namespace JSC {
  40
  41 class Heap;
  42 class JSCell;
  43 class LiveObjectIterator;
  44 class LLIntOffsetsExtractor;
  45 class WeakGCHandle;
  46 class SlotVisitor;
  47
  48 class MarkedSpace {
  49     WTF_MAKE_NONCOPYABLE(MarkedSpace);
  50 public:
  51     static const size_t maxCellSize = 2048;
  52
  53     MarkedSpace(Heap*);
  54
  55     MarkedAllocator& firstAllocator();
  56     MarkedAllocator& allocatorFor(size_t);
  57     MarkedAllocator& allocatorFor(MarkedBlock*);
  58     MarkedAllocator& destructorAllocatorFor(size_t);
  59     void* allocateWithDestructor(size_t);
  60     void* allocateWithoutDestructor(size_t);
  61
  62     void resetAllocators();
  63
  64     MarkedBlockSet& blocks() { return m_blocks; }
  65
  66     void canonicalizeCellLivenessData();
  67
  68     typedef HashSet<MarkedBlock*>::iterator BlockIterator;
  69
  70     template<typename Functor> typename Functor::ReturnType forEachCell(Functor&);
  71     template<typename Functor> typename Functor::ReturnType forEachCell();
  72     template<typename Functor> typename Functor::ReturnType forEachBlock(Functor&);
  73     template<typename Functor> typename Functor::ReturnType forEachBlock();
  74
  75     void shrink();
  76     void freeBlocks(MarkedBlock* head);
  77
  78     void didAddBlock(MarkedBlock*);
  79     void didConsumeFreeList(MarkedBlock*);
  80
  81     bool isPagedOut(double deadline);
  82
  83 private:
  84     friend class LLIntOffsetsExtractor;
  85
  86     // [ 32... 256 ]
  87     static const size_t preciseStep = MarkedBlock::atomSize;
  88     static const size_t preciseCutoff = 256;
  89     static const size_t preciseCount = preciseCutoff / preciseStep;
  90
  91     // [ 512... 2048 ]
  92     static const size_t impreciseStep = preciseCutoff;
  93     static const size_t impreciseCutoff = maxCellSize;
  94     static const size_t impreciseCount = impreciseCutoff / impreciseStep;
  95
  96     struct Subspace {
  97         FixedArray<MarkedAllocator, preciseCount> preciseAllocators;
  98         FixedArray<MarkedAllocator, impreciseCount> impreciseAllocators;
  99     };
 100
 101     Subspace m_destructorSpace;
 102     Subspace m_normalSpace;
 103
 104     Heap* m_heap;
 105     MarkedBlockSet m_blocks;
 106 };
 107
 108 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachCell(Functor& functor)
 109 {
 110     canonicalizeCellLivenessData();
 111
 112     BlockIterator end = m_blocks.set().end();
 113     for (BlockIterator it = m_blocks.set().begin(); it != end; ++it)
 114         (*it)->forEachCell(functor);
 115     return functor.returnValue();
 116 }
 117
 118 template<typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachCell()
 119 {
 120     Functor functor;
 121     return forEachCell(functor);
 122 }
 123
 124 inline MarkedAllocator& MarkedSpace::firstAllocator()
 125 {
 126     return m_normalSpace.preciseAllocators[0];
 127 }
 128
 129 inline MarkedAllocator& MarkedSpace::allocatorFor(size_t bytes)
 130 {
 131     ASSERT(bytes && bytes <= maxCellSize);
 132     if (bytes <= preciseCutoff)
 133         return m_normalSpace.preciseAllocators[(bytes - 1) / preciseStep];
 134     return m_normalSpace.impreciseAllocators[(bytes - 1) / impreciseStep];
 135 }
 136
 137 inline MarkedAllocator& MarkedSpace::allocatorFor(MarkedBlock* block)
 138 {
 139     if (block->cellsNeedDestruction())
 140         return destructorAllocatorFor(block->cellSize());
 141     return allocatorFor(block->cellSize());
 142 }
 143
 144 inline MarkedAllocator& MarkedSpace::destructorAllocatorFor(size_t bytes)
 145 {
 146     ASSERT(bytes && bytes <= maxCellSize);
 147     if (bytes <= preciseCutoff)
 148         return m_destructorSpace.preciseAllocators[(bytes - 1) / preciseStep];
 149     return m_destructorSpace.impreciseAllocators[(bytes - 1) / impreciseStep];
 150 }
 151
 152 inline void* MarkedSpace::allocateWithoutDestructor(size_t bytes)
 153 {
 154     return allocatorFor(bytes).allocate();
 155 }
 156
 157 inline void* MarkedSpace::allocateWithDestructor(size_t bytes)
 158 {
 159     return destructorAllocatorFor(bytes).allocate();
 160 }
 161
 162 template <typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachBlock(Functor& functor)
 163 {
 164     for (size_t i = 0; i < preciseCount; ++i) {
 165         m_normalSpace.preciseAllocators[i].forEachBlock(functor);
 166         m_destructorSpace.preciseAllocators[i].forEachBlock(functor);
 167     }
 168
 169     for (size_t i = 0; i < impreciseCount; ++i) {
 170         m_normalSpace.impreciseAllocators[i].forEachBlock(functor);
 171         m_destructorSpace.impreciseAllocators[i].forEachBlock(functor);
 172     }
 173
 174     return functor.returnValue();
 175 }
 176
 177 template <typename Functor> inline typename Functor::ReturnType MarkedSpace::forEachBlock()
 178 {
 179     Functor functor;
 180     return forEachBlock(functor);
 181 }
 182
 183 inline void MarkedSpace::didAddBlock(MarkedBlock* block)
 184 {
 185     m_blocks.add(block);
 186 }
 187
 188 } // namespace JSC
 189
 190 #endif // MarkedSpace_h