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 "MarkedBlock.h"
  27 #include "PageAllocationAligned.h"
  28 #include <wtf/Bitmap.h>
  29 #include <wtf/DoublyLinkedList.h>
  30 #include <wtf/FixedArray.h>
  31 #include <wtf/HashSet.h>
  32 #include <wtf/Noncopyable.h>
  33 #include <wtf/Vector.h>
  34
  35 #define ASSERT_CLASS_FITS_IN_CELL(class) COMPILE_ASSERT(sizeof(class) < MarkedSpace::maxCellSize, class_fits_in_cell)
  36
  37 namespace JSC {
  38
  39     class Heap;
  40     class JSCell;
  41     class JSGlobalData;
  42     class LiveObjectIterator;
  43     class MarkStack;
  44     class WeakGCHandle;
  45     typedef MarkStack SlotVisitor;
  46
  47     class MarkedSpace {
  48         WTF_MAKE_NONCOPYABLE(MarkedSpace);
  49     public:
  50         // Currently public for use in assertions.
  51         static const size_t maxCellSize = 1024;
  52
  53         static Heap* heap(JSCell*);
  54
  55         static bool isMarked(const JSCell*);
  56         static bool testAndSetMarked(const JSCell*);
  57         static void setMarked(const JSCell*);
  58
  59         MarkedSpace(JSGlobalData*);
  60         void destroy();
  61
  62         JSGlobalData* globalData();
  63
  64         size_t highWaterMark();
  65         void setHighWaterMark(size_t);
  66
  67         void* allocate(size_t);
  68
  69         void clearMarks();
  70         void markRoots();
  71         void reset();
  72         void sweep();
  73         void shrink();
  74
  75         size_t size() const;
  76         size_t capacity() const;
  77         size_t objectCount() const;
  78
  79         bool contains(const void*);
  80
  81         template<typename Functor> void forEach(Functor&);
  82
  83     private:
  84         // [ 8, 16... 128 )
  85         static const size_t preciseStep = MarkedBlock::atomSize;
  86         static const size_t preciseCutoff = 128;
  87         static const size_t preciseCount = preciseCutoff / preciseStep - 1;
  88
  89         // [ 128, 256... 1024 )
  90         static const size_t impreciseStep = preciseCutoff;
  91         static const size_t impreciseCutoff = maxCellSize;
  92         static const size_t impreciseCount = impreciseCutoff / impreciseStep - 1;
  93
  94         typedef HashSet<MarkedBlock*>::iterator BlockIterator;
  95
  96         struct SizeClass {
  97             SizeClass();
  98             void reset();
  99
 100             MarkedBlock* nextBlock;
 101             DoublyLinkedList<MarkedBlock> blockList;
 102             size_t cellSize;
 103         };
 104
 105         MarkedBlock* allocateBlock(SizeClass&);
 106         void freeBlocks(DoublyLinkedList<MarkedBlock>&);
 107
 108         SizeClass& sizeClassFor(size_t);
 109         void* allocateFromSizeClass(SizeClass&);
 110
 111         void clearMarks(MarkedBlock*);
 112
 113         SizeClass m_preciseSizeClasses[preciseCount];
 114         SizeClass m_impreciseSizeClasses[impreciseCount];
 115         HashSet<MarkedBlock*> m_blocks;
 116         size_t m_waterMark;
 117         size_t m_highWaterMark;
 118         JSGlobalData* m_globalData;
 119     };
 120
 121     inline Heap* MarkedSpace::heap(JSCell* cell)
 122     {
 123         return MarkedBlock::blockFor(cell)->heap();
 124     }
 125
 126     inline bool MarkedSpace::isMarked(const JSCell* cell)
 127     {
 128         return MarkedBlock::blockFor(cell)->isMarked(cell);
 129     }
 130
 131     inline bool MarkedSpace::testAndSetMarked(const JSCell* cell)
 132     {
 133         return MarkedBlock::blockFor(cell)->testAndSetMarked(cell);
 134     }
 135
 136     inline void MarkedSpace::setMarked(const JSCell* cell)
 137     {
 138         MarkedBlock::blockFor(cell)->setMarked(cell);
 139     }
 140
 141     inline bool MarkedSpace::contains(const void* x)
 142     {
 143         if (!MarkedBlock::isAtomAligned(x))
 144             return false;
 145
 146         MarkedBlock* block = MarkedBlock::blockFor(x);
 147         if (!block || !m_blocks.contains(block))
 148             return false;
 149
 150         return block->contains(x);
 151     }
 152
 153     template <typename Functor> inline void MarkedSpace::forEach(Functor& functor)
 154     {
 155         BlockIterator end = m_blocks.end();
 156         for (BlockIterator it = m_blocks.begin(); it != end; ++it)
 157             (*it)->forEach(functor);
 158     }
 159
 160     inline JSGlobalData* MarkedSpace::globalData()
 161     {
 162         return m_globalData;
 163     }
 164
 165     inline size_t MarkedSpace::highWaterMark()
 166     {
 167         return m_highWaterMark;
 168     }
 169
 170     inline void MarkedSpace::setHighWaterMark(size_t highWaterMark)
 171     {
 172         m_highWaterMark = highWaterMark;
 173     }
 174
 175     inline MarkedSpace::SizeClass::SizeClass()
 176         : nextBlock(0)
 177         , cellSize(0)
 178     {
 179     }
 180
 181     inline void MarkedSpace::SizeClass::reset()
 182     {
 183         nextBlock = blockList.head();
 184     }
 185
 186 } // namespace JSC
 187
 188 #endif // MarkedSpace_h