code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/heap/MarkedBlock.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 MarkedBlock_h
  23 #define MarkedBlock_h
  24
  25 #include <wtf/Bitmap.h>
  26 #include <wtf/DoublyLinkedList.h>
  27 #include <wtf/HashFunctions.h>
  28 #include <wtf/PageAllocationAligned.h>
  29 #include <wtf/StdLibExtras.h>
  30
  31 // Set to log state transitions of blocks.
  32 #define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
  33
  34 #if HEAP_LOG_BLOCK_STATE_TRANSITIONS
  35 #define HEAP_DEBUG_BLOCK(block) do {                                    \
  36         printf("%s:%d %s: block %s = %p\n",                             \
  37                __FILE__, __LINE__, __FUNCTION__, #block, (block));      \
  38     } while (false)
  39 #else
  40 #define HEAP_DEBUG_BLOCK(block) ((void)0)
  41 #endif
  42
  43 namespace JSC {
  44
  45     class Heap;
  46     class JSCell;
  47
  48     typedef uintptr_t Bits;
  49
  50     static const size_t KB = 1024;
  51     static const size_t MB = 1024 * 1024;
  52
  53     // A marked block is a page-aligned container for heap-allocated objects.
  54     // Objects are allocated within cells of the marked block. For a given
  55     // marked block, all cells have the same size. Objects smaller than the
  56     // cell size may be allocated in the marked block, in which case the
  57     // allocation suffers from internal fragmentation: wasted space whose
  58     // size is equal to the difference between the cell size and the object
  59     // size.
  60
  61     class MarkedBlock : public DoublyLinkedListNode<MarkedBlock> {
  62         friend class WTF::DoublyLinkedListNode<MarkedBlock>;
  63     public:
  64         // Ensure natural alignment for native types whilst recognizing that the smallest
  65         // object the heap will commonly allocate is four words.
  66         static const size_t atomSize = 4 * sizeof(void*);
  67         static const size_t blockSize = 16 * KB;
  68
  69         static const size_t atomsPerBlock = blockSize / atomSize; // ~1.5% overhead
  70         static const size_t ownerSetsPerBlock = 8; // ~2% overhead.
  71
  72         struct FreeCell {
  73             FreeCell* next;
  74
  75             void setNoObject()
  76             {
  77                 // This relies on FreeCell not having a vtable, and the next field
  78                 // falling exactly where a vtable would have been.
  79                 next = 0;
  80             }
  81         };
  82
  83         struct VoidFunctor {
  84             typedef void ReturnType;
  85             void returnValue() { }
  86         };
  87
  88         static MarkedBlock* create(Heap*, size_t cellSize);
  89         static void destroy(MarkedBlock*);
  90
  91         static bool isAtomAligned(const void*);
  92         static MarkedBlock* blockFor(const void*);
  93         static size_t firstAtom();
  94
  95         Heap* heap() const;
  96
  97         bool inNewSpace();
  98         void setInNewSpace(bool);
  99
 100         void* allocate();
 101         void sweep();
 102
 103         // This invokes destructors on all cells that are not marked, marks
 104         // them, and returns a linked list of those cells.
 105         FreeCell* lazySweep();
 106
 107         // Notify the block that destructors may have to be called again.
 108         void notifyMayHaveFreshFreeCells();
 109
 110         void initForCellSize(size_t cellSize);
 111
 112         // These should be called immediately after a block is created.
 113         // Blessing for fast path creates a linked list, while blessing for
 114         // slow path creates dummy cells.
 115         FreeCell* blessNewBlockForFastPath();
 116         void blessNewBlockForSlowPath();
 117
 118         void reset();
 119
 120         // This unmarks all cells on the free list, and allocates dummy JSCells
 121         // in their place.
 122         void canonicalizeBlock(FreeCell* firstFreeCell);
 123
 124         bool isEmpty();
 125
 126         void clearMarks();
 127         size_t markCount();
 128
 129         size_t cellSize();
 130
 131         size_t size();
 132         size_t capacity();
 133
 134         bool isMarked(const void*);
 135         bool testAndSetMarked(const void*);
 136         bool testAndClearMarked(const void*);
 137         void setMarked(const void*);
 138
 139         template <typename Functor> void forEachCell(Functor&);
 140
 141     private:
 142         static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
 143         static const size_t atomMask = ~(atomSize - 1); // atomSize must be a power of two.
 144
 145         enum DestructorState { FreeCellsDontHaveObjects, SomeFreeCellsStillHaveObjects, AllFreeCellsHaveObjects };
 146
 147         typedef char Atom[atomSize];
 148
 149         MarkedBlock(const PageAllocationAligned&, Heap*, size_t cellSize);
 150         Atom* atoms();
 151
 152         size_t atomNumber(const void*);
 153         size_t ownerSetNumber(const JSCell*);
 154
 155         template<DestructorState destructorState>
 156         void callDestructor(JSCell*, void* jsFinalObjectVPtr);
 157
 158         template<DestructorState destructorState>
 159         void specializedReset();
 160
 161         template<DestructorState destructorState>
 162         void specializedSweep();
 163
 164         template<DestructorState destructorState>
 165         MarkedBlock::FreeCell* produceFreeList();
 166
 167         void setDestructorState(DestructorState destructorState)
 168         {
 169             m_destructorState = static_cast<int8_t>(destructorState);
 170         }
 171
 172         DestructorState destructorState()
 173         {
 174             return static_cast<DestructorState>(m_destructorState);
 175         }
 176
 177         size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
 178         size_t m_atomsPerCell;
 179         WTF::Bitmap<blockSize / atomSize> m_marks;
 180         bool m_inNewSpace;
 181         int8_t m_destructorState; // use getters/setters for this, particularly since we may want to compact this (effectively log(3)/log(2)-bit) field into other fields
 182         PageAllocationAligned m_allocation;
 183         Heap* m_heap;
 184         MarkedBlock* m_prev;
 185         MarkedBlock* m_next;
 186     };
 187
 188     inline size_t MarkedBlock::firstAtom()
 189     {
 190         return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
 191     }
 192
 193     inline MarkedBlock::Atom* MarkedBlock::atoms()
 194     {
 195         return reinterpret_cast<Atom*>(this);
 196     }
 197
 198     inline bool MarkedBlock::isAtomAligned(const void* p)
 199     {
 200         return !(reinterpret_cast<Bits>(p) & ~atomMask);
 201     }
 202
 203     inline MarkedBlock* MarkedBlock::blockFor(const void* p)
 204     {
 205         return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
 206     }
 207
 208     inline Heap* MarkedBlock::heap() const
 209     {
 210         return m_heap;
 211     }
 212
 213     inline bool MarkedBlock::inNewSpace()
 214     {
 215         return m_inNewSpace;
 216     }
 217
 218     inline void MarkedBlock::setInNewSpace(bool inNewSpace)
 219     {
 220         m_inNewSpace = inNewSpace;
 221     }
 222
 223     inline void MarkedBlock::notifyMayHaveFreshFreeCells()
 224     {
 225         HEAP_DEBUG_BLOCK(this);
 226
 227         // This is called at the beginning of GC. If this block is
 228         // AllFreeCellsHaveObjects, then it means that we filled up
 229         // the block in this collection. If it's in any other state,
 230         // then this collection will potentially produce new free
 231         // cells; new free cells always have objects. Hence if the
 232         // state currently claims that there are no objects in free
 233         // cells then we need to bump it over. Otherwise leave it be.
 234         // This all crucially relies on the collector canonicalizing
 235         // blocks before doing anything else, as canonicalizeBlocks
 236         // will correctly set SomeFreeCellsStillHaveObjects for
 237         // blocks that were only partially filled during this
 238         // mutation cycle.
 239
 240         if (destructorState() == FreeCellsDontHaveObjects)
 241             setDestructorState(SomeFreeCellsStillHaveObjects);
 242     }
 243
 244     inline bool MarkedBlock::isEmpty()
 245     {
 246         return m_marks.isEmpty();
 247     }
 248
 249     inline void MarkedBlock::clearMarks()
 250     {
 251         m_marks.clearAll();
 252     }
 253
 254     inline size_t MarkedBlock::markCount()
 255     {
 256         return m_marks.count();
 257     }
 258
 259     inline size_t MarkedBlock::cellSize()
 260     {
 261         return m_atomsPerCell * atomSize;
 262     }
 263
 264     inline size_t MarkedBlock::size()
 265     {
 266         return markCount() * cellSize();
 267     }
 268
 269     inline size_t MarkedBlock::capacity()
 270     {
 271         return m_allocation.size();
 272     }
 273
 274     inline size_t MarkedBlock::atomNumber(const void* p)
 275     {
 276         return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
 277     }
 278
 279     inline bool MarkedBlock::isMarked(const void* p)
 280     {
 281         return m_marks.get(atomNumber(p));
 282     }
 283
 284     inline bool MarkedBlock::testAndSetMarked(const void* p)
 285     {
 286         return m_marks.testAndSet(atomNumber(p));
 287     }
 288
 289     inline bool MarkedBlock::testAndClearMarked(const void* p)
 290     {
 291         return m_marks.testAndClear(atomNumber(p));
 292     }
 293
 294     inline void MarkedBlock::setMarked(const void* p)
 295     {
 296         m_marks.set(atomNumber(p));
 297     }
 298
 299     template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
 300     {
 301         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
 302             if (!m_marks.get(i))
 303                 continue;
 304             functor(reinterpret_cast<JSCell*>(&atoms()[i]));
 305         }
 306     }
 307
 308     inline size_t MarkedBlock::ownerSetNumber(const JSCell* cell)
 309     {
 310         return (reinterpret_cast<Bits>(cell) - reinterpret_cast<Bits>(this)) * ownerSetsPerBlock / blockSize;
 311     }
 312
 313 } // namespace JSC
 314
 315 namespace WTF {
 316
 317     struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
 318         static unsigned hash(JSC::MarkedBlock* const& key)
 319         {
 320             // Aligned VM regions tend to be monotonically increasing integers,
 321             // which is a great hash function, but we have to remove the low bits,
 322             // since they're always zero, which is a terrible hash function!
 323             return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
 324         }
 325     };
 326
 327     template<> struct DefaultHash<JSC::MarkedBlock*> {
 328         typedef MarkedBlockHash Hash;
 329     };
 330
 331 } // namespace WTF
 332
 333 #endif // MarkedBlock_h