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 "CardSet.h"
  26 #include "HeapBlock.h"
  27
  28 #include "WeakSet.h"
  29 #include <wtf/Bitmap.h>
  30 #include <wtf/DataLog.h>
  31 #include <wtf/DoublyLinkedList.h>
  32 #include <wtf/HashFunctions.h>
  33 #include <wtf/PageAllocationAligned.h>
  34 #include <wtf/StdLibExtras.h>
  35 #include <wtf/Vector.h>
  36
  37 // Set to log state transitions of blocks.
  38 #define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
  39
  40 #if HEAP_LOG_BLOCK_STATE_TRANSITIONS
  41 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) do {                     \
  42         dataLog(                                                    \
  43             "%s:%d %s: block %s = %p, %d\n",                            \
  44             __FILE__, __LINE__, __FUNCTION__,                           \
  45             #block, (block), (block)->m_state);                         \
  46     } while (false)
  47 #else
  48 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) ((void)0)
  49 #endif
  50
  51 namespace JSC {
  52
  53     class Heap;
  54     class JSCell;
  55
  56     typedef uintptr_t Bits;
  57
  58     static const size_t MB = 1024 * 1024;
  59
  60     bool isZapped(const JSCell*);
  61
  62     // A marked block is a page-aligned container for heap-allocated objects.
  63     // Objects are allocated within cells of the marked block. For a given
  64     // marked block, all cells have the same size. Objects smaller than the
  65     // cell size may be allocated in the marked block, in which case the
  66     // allocation suffers from internal fragmentation: wasted space whose
  67     // size is equal to the difference between the cell size and the object
  68     // size.
  69
  70     class MarkedBlock : public HeapBlock<MarkedBlock> {
  71     public:
  72         // Ensure natural alignment for native types whilst recognizing that the smallest
  73         // object the heap will commonly allocate is four words.
  74         static const size_t atomSize = 4 * sizeof(void*);
  75         static const size_t atomShift = 5;
  76         static const size_t blockSize = 64 * KB;
  77         static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
  78
  79         static const size_t atomsPerBlock = blockSize / atomSize; // ~0.4% overhead
  80         static const size_t atomMask = atomsPerBlock - 1;
  81         static const int cardShift = 8; // This is log2 of bytes per card.
  82         static const size_t bytesPerCard = 1 << cardShift;
  83         static const int cardCount = blockSize / bytesPerCard;
  84         static const int cardMask = cardCount - 1;
  85
  86         struct FreeCell {
  87             FreeCell* next;
  88         };
  89
  90         struct FreeList {
  91             FreeCell* head;
  92             size_t bytes;
  93
  94             FreeList();
  95             FreeList(FreeCell*, size_t);
  96         };
  97
  98         struct VoidFunctor {
  99             typedef void ReturnType;
 100             void returnValue() { }
 101         };
 102
 103         class CountFunctor {
 104         public:
 105             typedef size_t ReturnType;
 106
 107             CountFunctor() : m_count(0) { }
 108             void count(size_t count) { m_count += count; }
 109             ReturnType returnValue() { return m_count; }
 110
 111         private:
 112             ReturnType m_count;
 113         };
 114
 115         static MarkedBlock* create(const PageAllocationAligned&, Heap*, size_t cellSize, bool cellsNeedDestruction, bool onlyContainsStructures);
 116
 117         static bool isAtomAligned(const void*);
 118         static MarkedBlock* blockFor(const void*);
 119         static size_t firstAtom();
 120
 121         void lastChanceToFinalize();
 122
 123         Heap* heap() const;
 124         WeakSet& weakSet();
 125
 126         enum SweepMode { SweepOnly, SweepToFreeList };
 127         FreeList sweep(SweepMode = SweepOnly);
 128
 129         void shrink();
 130
 131         void visitWeakSet(HeapRootVisitor&);
 132         void reapWeakSet();
 133
 134         // While allocating from a free list, MarkedBlock temporarily has bogus
 135         // cell liveness data. To restore accurate cell liveness data, call one
 136         // of these functions:
 137         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
 138         void zapFreeList(const FreeList&); // Call this to undo the free list.
 139
 140         void clearMarks();
 141         size_t markCount();
 142         bool isEmpty();
 143
 144         size_t cellSize();
 145         bool cellsNeedDestruction();
 146         bool onlyContainsStructures();
 147
 148         size_t size();
 149         size_t capacity();
 150
 151         bool isMarked(const void*);
 152         bool testAndSetMarked(const void*);
 153         bool isLive(const JSCell*);
 154         bool isLiveCell(const void*);
 155         void setMarked(const void*);
 156
 157         bool needsSweeping();
 158
 159 #if ENABLE(GGC)
 160         void setDirtyObject(const void* atom)
 161         {
 162             ASSERT(MarkedBlock::blockFor(atom) == this);
 163             m_cards.markCardForAtom(atom);
 164         }
 165
 166         uint8_t* addressOfCardFor(const void* atom)
 167         {
 168             ASSERT(MarkedBlock::blockFor(atom) == this);
 169             return &m_cards.cardForAtom(atom);
 170         }
 171
 172         static inline size_t offsetOfCards()
 173         {
 174             return OBJECT_OFFSETOF(MarkedBlock, m_cards);
 175         }
 176
 177         static inline size_t offsetOfMarks()
 178         {
 179             return OBJECT_OFFSETOF(MarkedBlock, m_marks);
 180         }
 181
 182         typedef Vector<JSCell*, 32> DirtyCellVector;
 183         inline void gatherDirtyCells(DirtyCellVector&);
 184         template <int size> inline void gatherDirtyCellsWithSize(DirtyCellVector&);
 185 #endif
 186
 187         template <typename Functor> void forEachCell(Functor&);
 188
 189     private:
 190         static const size_t atomAlignmentMask = atomSize - 1; // atomSize must be a power of two.
 191
 192         enum BlockState { New, FreeListed, Allocated, Marked, Zapped };
 193         template<bool destructorCallNeeded> FreeList sweepHelper(SweepMode = SweepOnly);
 194
 195         typedef char Atom[atomSize];
 196
 197         MarkedBlock(const PageAllocationAligned&, Heap*, size_t cellSize, bool cellsNeedDestruction, bool onlyContainsStructures);
 198         Atom* atoms();
 199         size_t atomNumber(const void*);
 200         void callDestructor(JSCell*);
 201         template<BlockState, SweepMode, bool destructorCallNeeded> FreeList specializedSweep();
 202
 203 #if ENABLE(GGC)
 204         CardSet<bytesPerCard, blockSize> m_cards;
 205 #endif
 206
 207         size_t m_atomsPerCell;
 208         size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
 209 #if ENABLE(PARALLEL_GC)
 210         WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic> m_marks;
 211 #else
 212         WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic> m_marks;
 213 #endif
 214         bool m_cellsNeedDestruction;
 215         bool m_onlyContainsStructures;
 216         BlockState m_state;
 217         WeakSet m_weakSet;
 218     };
 219
 220     inline MarkedBlock::FreeList::FreeList()
 221         : head(0)
 222         , bytes(0)
 223     {
 224     }
 225
 226     inline MarkedBlock::FreeList::FreeList(FreeCell* head, size_t bytes)
 227         : head(head)
 228         , bytes(bytes)
 229     {
 230     }
 231
 232     inline size_t MarkedBlock::firstAtom()
 233     {
 234         return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
 235     }
 236
 237     inline MarkedBlock::Atom* MarkedBlock::atoms()
 238     {
 239         return reinterpret_cast<Atom*>(this);
 240     }
 241
 242     inline bool MarkedBlock::isAtomAligned(const void* p)
 243     {
 244         return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
 245     }
 246
 247     inline MarkedBlock* MarkedBlock::blockFor(const void* p)
 248     {
 249         return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
 250     }
 251
 252     inline void MarkedBlock::lastChanceToFinalize()
 253     {
 254         m_weakSet.lastChanceToFinalize();
 255
 256         clearMarks();
 257         sweep();
 258     }
 259
 260     inline Heap* MarkedBlock::heap() const
 261     {
 262         return m_weakSet.heap();
 263     }
 264
 265     inline WeakSet& MarkedBlock::weakSet()
 266     {
 267         return m_weakSet;
 268     }
 269
 270     inline void MarkedBlock::shrink()
 271     {
 272         m_weakSet.shrink();
 273     }
 274
 275     inline void MarkedBlock::visitWeakSet(HeapRootVisitor& heapRootVisitor)
 276     {
 277         m_weakSet.visit(heapRootVisitor);
 278     }
 279
 280     inline void MarkedBlock::reapWeakSet()
 281     {
 282         m_weakSet.reap();
 283     }
 284
 285     inline void MarkedBlock::didConsumeFreeList()
 286     {
 287         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
 288
 289         ASSERT(m_state == FreeListed);
 290         m_state = Allocated;
 291     }
 292
 293     inline void MarkedBlock::clearMarks()
 294     {
 295         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
 296
 297         ASSERT(m_state != New && m_state != FreeListed);
 298         m_marks.clearAll();
 299
 300         // This will become true at the end of the mark phase. We set it now to
 301         // avoid an extra pass to do so later.
 302         m_state = Marked;
 303     }
 304
 305     inline size_t MarkedBlock::markCount()
 306     {
 307         return m_marks.count();
 308     }
 309
 310     inline bool MarkedBlock::isEmpty()
 311     {
 312         return m_marks.isEmpty() && m_weakSet.isEmpty();
 313     }
 314
 315     inline size_t MarkedBlock::cellSize()
 316     {
 317         return m_atomsPerCell * atomSize;
 318     }
 319
 320     inline bool MarkedBlock::cellsNeedDestruction()
 321     {
 322         return m_cellsNeedDestruction;
 323     }
 324
 325     inline bool MarkedBlock::onlyContainsStructures()
 326     {
 327         return m_onlyContainsStructures;
 328     }
 329
 330     inline size_t MarkedBlock::size()
 331     {
 332         return markCount() * cellSize();
 333     }
 334
 335     inline size_t MarkedBlock::capacity()
 336     {
 337         return allocation().size();
 338     }
 339
 340     inline size_t MarkedBlock::atomNumber(const void* p)
 341     {
 342         return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
 343     }
 344
 345     inline bool MarkedBlock::isMarked(const void* p)
 346     {
 347         return m_marks.get(atomNumber(p));
 348     }
 349
 350     inline bool MarkedBlock::testAndSetMarked(const void* p)
 351     {
 352         return m_marks.concurrentTestAndSet(atomNumber(p));
 353     }
 354
 355     inline void MarkedBlock::setMarked(const void* p)
 356     {
 357         m_marks.set(atomNumber(p));
 358     }
 359
 360     inline bool MarkedBlock::isLive(const JSCell* cell)
 361     {
 362         switch (m_state) {
 363         case Allocated:
 364             return true;
 365         case Zapped:
 366             if (isZapped(cell)) {
 367                 // Object dead in previous collection, not allocated since previous collection: mark bit should not be set.
 368                 ASSERT(!m_marks.get(atomNumber(cell)));
 369                 return false;
 370             }
 371
 372             // Newly allocated objects: mark bit not set.
 373             // Objects that survived prior collection: mark bit set.
 374             return true;
 375         case Marked:
 376             return m_marks.get(atomNumber(cell));
 377
 378         case New:
 379         case FreeListed:
 380             ASSERT_NOT_REACHED();
 381             return false;
 382         }
 383
 384         ASSERT_NOT_REACHED();
 385         return false;
 386     }
 387
 388     inline bool MarkedBlock::isLiveCell(const void* p)
 389     {
 390         ASSERT(MarkedBlock::isAtomAligned(p));
 391         size_t atomNumber = this->atomNumber(p);
 392         size_t firstAtom = this->firstAtom();
 393         if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
 394             return false;
 395         if ((atomNumber - firstAtom) % m_atomsPerCell) // Filters pointers into cell middles.
 396             return false;
 397         if (atomNumber >= m_endAtom) // Filters pointers into invalid cells out of the range.
 398             return false;
 399
 400         return isLive(static_cast<const JSCell*>(p));
 401     }
 402
 403     template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
 404     {
 405         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
 406             JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
 407             if (!isLive(cell))
 408                 continue;
 409
 410             functor(cell);
 411         }
 412     }
 413
 414     inline bool MarkedBlock::needsSweeping()
 415     {
 416         return m_state == Marked;
 417     }
 418
 419 #if ENABLE(GGC)
 420 template <int _cellSize> void MarkedBlock::gatherDirtyCellsWithSize(DirtyCellVector& dirtyCells)
 421 {
 422     if (m_cards.testAndClear(0)) {
 423         char* ptr = reinterpret_cast<char*>(&atoms()[firstAtom()]);
 424         const char* end = reinterpret_cast<char*>(this) + bytesPerCard;
 425         while (ptr < end) {
 426             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
 427             if (isMarked(cell))
 428                 dirtyCells.append(cell);
 429             ptr += _cellSize;
 430         }
 431     }
 432
 433     const size_t cellOffset = firstAtom() * atomSize % _cellSize;
 434     for (size_t i = 1; i < m_cards.cardCount; i++) {
 435         if (!m_cards.testAndClear(i))
 436             continue;
 437         char* ptr = reinterpret_cast<char*>(this) + i * bytesPerCard + cellOffset;
 438         char* end = reinterpret_cast<char*>(this) + (i + 1) * bytesPerCard;
 439
 440         while (ptr < end) {
 441             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
 442             if (isMarked(cell))
 443                 dirtyCells.append(cell);
 444             ptr += _cellSize;
 445         }
 446     }
 447 }
 448
 449 void MarkedBlock::gatherDirtyCells(DirtyCellVector& dirtyCells)
 450 {
 451     COMPILE_ASSERT((int)m_cards.cardCount == (int)cardCount, MarkedBlockCardCountsMatch);
 452
 453     ASSERT(m_state != New && m_state != FreeListed);
 454
 455     // This is an optimisation to avoid having to walk the set of marked
 456     // blocks twice during GC.
 457     m_state = Marked;
 458
 459     if (isEmpty())
 460         return;
 461
 462     size_t cellSize = this->cellSize();
 463     if (cellSize == 32) {
 464         gatherDirtyCellsWithSize<32>(dirtyCells);
 465         return;
 466     }
 467     if (cellSize == 64) {
 468         gatherDirtyCellsWithSize<64>(dirtyCells);
 469         return;
 470     }
 471
 472     const size_t firstCellOffset = firstAtom() * atomSize % cellSize;
 473
 474     if (m_cards.testAndClear(0)) {
 475         char* ptr = reinterpret_cast<char*>(this) + firstAtom() * atomSize;
 476         char* end = reinterpret_cast<char*>(this) + bytesPerCard;
 477         while (ptr < end) {
 478             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
 479             if (isMarked(cell))
 480                 dirtyCells.append(cell);
 481             ptr += cellSize;
 482         }
 483     }
 484     for (size_t i = 1; i < m_cards.cardCount; i++) {
 485         if (!m_cards.testAndClear(i))
 486             continue;
 487         char* ptr = reinterpret_cast<char*>(this) + firstCellOffset + cellSize * ((i * bytesPerCard + cellSize - 1 - firstCellOffset) / cellSize);
 488         char* end = reinterpret_cast<char*>(this) + std::min((i + 1) * bytesPerCard, m_endAtom * atomSize);
 489
 490         while (ptr < end) {
 491             JSCell* cell = reinterpret_cast<JSCell*>(ptr);
 492             if (isMarked(cell))
 493                 dirtyCells.append(cell);
 494             ptr += cellSize;
 495         }
 496     }
 497 }
 498 #endif
 499
 500 } // namespace JSC
 501
 502 namespace WTF {
 503
 504     struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
 505         static unsigned hash(JSC::MarkedBlock* const& key)
 506         {
 507             // Aligned VM regions tend to be monotonically increasing integers,
 508             // which is a great hash function, but we have to remove the low bits,
 509             // since they're always zero, which is a terrible hash function!
 510             return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
 511         }
 512     };
 513
 514     template<> struct DefaultHash<JSC::MarkedBlock*> {
 515         typedef MarkedBlockHash Hash;
 516     };
 517
 518 } // namespace WTF
 519
 520 #endif // MarkedBlock_h