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 "BlockAllocator.h"
  26 #include "HeapBlock.h"
  27
  28 #include "HeapOperation.h"
  29 #include "WeakSet.h"
  30 #include <wtf/Bitmap.h>
  31 #include <wtf/DataLog.h>
  32 #include <wtf/DoublyLinkedList.h>
  33 #include <wtf/HashFunctions.h>
  34 #include <wtf/PageAllocationAligned.h>
  35 #include <wtf/StdLibExtras.h>
  36 #include <wtf/Vector.h>
  37
  38 // Set to log state transitions of blocks.
  39 #define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
  40
  41 #if HEAP_LOG_BLOCK_STATE_TRANSITIONS
  42 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) do {                     \
  43         dataLogF(                                                    \
  44             "%s:%d %s: block %s = %p, %d\n",                            \
  45             __FILE__, __LINE__, __FUNCTION__,                           \
  46             #block, (block), (block)->m_state);                         \
  47     } while (false)
  48 #else
  49 #define HEAP_LOG_BLOCK_STATE_TRANSITION(block) ((void)0)
  50 #endif
  51
  52 namespace JSC {
  53
  54     class Heap;
  55     class JSCell;
  56     class MarkedAllocator;
  57
  58     typedef uintptr_t Bits;
  59
  60     static const size_t MB = 1024 * 1024;
  61
  62     bool isZapped(const JSCell*);
  63
  64     // A marked block is a page-aligned container for heap-allocated objects.
  65     // Objects are allocated within cells of the marked block. For a given
  66     // marked block, all cells have the same size. Objects smaller than the
  67     // cell size may be allocated in the marked block, in which case the
  68     // allocation suffers from internal fragmentation: wasted space whose
  69     // size is equal to the difference between the cell size and the object
  70     // size.
  71
  72     class MarkedBlock : public HeapBlock<MarkedBlock> {
  73         friend class LLIntOffsetsExtractor;
  74         friend struct VerifyMarkedOrRetired;
  75     public:
  76         static const size_t atomSize = 16; // bytes
  77         static const size_t atomShiftAmount = 4; // log_2(atomSize) FIXME: Change atomSize to 16.
  78         static const size_t blockSize = 64 * KB;
  79         static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
  80
  81         static const size_t atomsPerBlock = blockSize / atomSize;
  82         static const size_t atomMask = atomsPerBlock - 1;
  83
  84         static const size_t markByteShiftAmount = 3; // log_2(word size for m_marks) FIXME: Change word size for m_marks to uint8_t.
  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         enum DestructorType { None, ImmortalStructure, Normal };
 116         static MarkedBlock* create(DeadBlock*, MarkedAllocator*, size_t cellSize, DestructorType);
 117
 118         static bool isAtomAligned(const void*);
 119         static MarkedBlock* blockFor(const void*);
 120         static size_t firstAtom();
 121
 122         void lastChanceToFinalize();
 123
 124         MarkedAllocator* allocator() const;
 125         Heap* heap() const;
 126         VM* vm() const;
 127         WeakSet& weakSet();
 128
 129         enum SweepMode { SweepOnly, SweepToFreeList };
 130         FreeList sweep(SweepMode = SweepOnly);
 131
 132         void shrink();
 133
 134         void visitWeakSet(HeapRootVisitor&);
 135         void reapWeakSet();
 136
 137         // While allocating from a free list, MarkedBlock temporarily has bogus
 138         // cell liveness data. To restore accurate cell liveness data, call one
 139         // of these functions:
 140         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
 141         void stopAllocating(const FreeList&);
 142         FreeList resumeAllocating(); // Call this if you canonicalized a block for some non-collection related purpose.
 143         void didConsumeEmptyFreeList(); // Call this if you sweep a block, but the returned FreeList is empty.
 144         void didSweepToNoAvail(); // Call this if you sweep a block and get an empty free list back.
 145
 146         // Returns true if the "newly allocated" bitmap was non-null
 147         // and was successfully cleared and false otherwise.
 148         bool clearNewlyAllocated();
 149         void clearMarks();
 150         void clearRememberedSet();
 151         template <HeapOperation collectionType>
 152         void clearMarksWithCollectionType();
 153
 154         size_t markCount();
 155         bool isEmpty();
 156
 157         size_t cellSize();
 158         DestructorType destructorType();
 159
 160         size_t size();
 161         size_t capacity();
 162
 163         bool isMarked(const void*);
 164         bool testAndSetMarked(const void*);
 165         bool isLive(const JSCell*);
 166         bool isLiveCell(const void*);
 167         void setMarked(const void*);
 168         void clearMarked(const void*);
 169
 170         void setRemembered(const void*);
 171         void clearRemembered(const void*);
 172         void atomicClearRemembered(const void*);
 173         bool isRemembered(const void*);
 174
 175         bool isNewlyAllocated(const void*);
 176         void setNewlyAllocated(const void*);
 177         void clearNewlyAllocated(const void*);
 178
 179         bool needsSweeping();
 180         void didRetireBlock(const FreeList&);
 181         void willRemoveBlock();
 182
 183         template <typename Functor> void forEachCell(Functor&);
 184         template <typename Functor> void forEachLiveCell(Functor&);
 185         template <typename Functor> void forEachDeadCell(Functor&);
 186
 187         static ptrdiff_t offsetOfMarks() { return OBJECT_OFFSETOF(MarkedBlock, m_marks); }
 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, Retired };
 193         template<DestructorType> FreeList sweepHelper(SweepMode = SweepOnly);
 194
 195         typedef char Atom[atomSize];
 196
 197         MarkedBlock(Region*, MarkedAllocator*, size_t cellSize, DestructorType);
 198         Atom* atoms();
 199         size_t atomNumber(const void*);
 200         template<DestructorType> void callDestructor(JSCell*);
 201         template<BlockState, SweepMode, DestructorType> FreeList specializedSweep();
 202
 203         size_t m_atomsPerCell;
 204         size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
 205 #if ENABLE(PARALLEL_GC)
 206         WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_marks;
 207         WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_rememberedSet;
 208 #else
 209         WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic, uint8_t> m_marks;
 210         WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic, uint8_t> m_rememberedSet;
 211 #endif
 212         OwnPtr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
 213
 214         DestructorType m_destructorType;
 215         MarkedAllocator* m_allocator;
 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 MarkedAllocator* MarkedBlock::allocator() const
 253     {
 254         return m_allocator;
 255     }
 256
 257     inline Heap* MarkedBlock::heap() const
 258     {
 259         return m_weakSet.heap();
 260     }
 261
 262     inline VM* MarkedBlock::vm() const
 263     {
 264         return m_weakSet.vm();
 265     }
 266
 267     inline WeakSet& MarkedBlock::weakSet()
 268     {
 269         return m_weakSet;
 270     }
 271
 272     inline void MarkedBlock::shrink()
 273     {
 274         m_weakSet.shrink();
 275     }
 276
 277     inline void MarkedBlock::visitWeakSet(HeapRootVisitor& heapRootVisitor)
 278     {
 279         m_weakSet.visit(heapRootVisitor);
 280     }
 281
 282     inline void MarkedBlock::reapWeakSet()
 283     {
 284         m_weakSet.reap();
 285     }
 286
 287     inline void MarkedBlock::willRemoveBlock()
 288     {
 289         ASSERT(m_state != Retired);
 290     }
 291
 292     inline void MarkedBlock::didConsumeFreeList()
 293     {
 294         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
 295
 296         ASSERT(m_state == FreeListed);
 297         m_state = Allocated;
 298     }
 299
 300     inline void MarkedBlock::didConsumeEmptyFreeList()
 301     {
 302         HEAP_LOG_BLOCK_STATE_TRANSITION(this);
 303
 304         ASSERT(!m_newlyAllocated);
 305         ASSERT(m_state == FreeListed);
 306         m_state = Marked;
 307     }
 308
 309     inline size_t MarkedBlock::markCount()
 310     {
 311         return m_marks.count();
 312     }
 313
 314     inline bool MarkedBlock::isEmpty()
 315     {
 316         return m_marks.isEmpty() && m_weakSet.isEmpty() && (!m_newlyAllocated || m_newlyAllocated->isEmpty());
 317     }
 318
 319     inline size_t MarkedBlock::cellSize()
 320     {
 321         return m_atomsPerCell * atomSize;
 322     }
 323
 324     inline MarkedBlock::DestructorType MarkedBlock::destructorType()
 325     {
 326         return m_destructorType;
 327     }
 328
 329     inline size_t MarkedBlock::size()
 330     {
 331         return markCount() * cellSize();
 332     }
 333
 334     inline size_t MarkedBlock::capacity()
 335     {
 336         return region()->blockSize();
 337     }
 338
 339     inline size_t MarkedBlock::atomNumber(const void* p)
 340     {
 341         return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
 342     }
 343
 344     inline void MarkedBlock::setRemembered(const void* p)
 345     {
 346         m_rememberedSet.set(atomNumber(p));
 347     }
 348
 349     inline void MarkedBlock::clearRemembered(const void* p)
 350     {
 351         m_rememberedSet.clear(atomNumber(p));
 352     }
 353
 354     inline void MarkedBlock::atomicClearRemembered(const void* p)
 355     {
 356         m_rememberedSet.concurrentTestAndClear(atomNumber(p));
 357     }
 358
 359     inline bool MarkedBlock::isRemembered(const void* p)
 360     {
 361         return m_rememberedSet.get(atomNumber(p));
 362     }
 363
 364     inline bool MarkedBlock::isMarked(const void* p)
 365     {
 366         return m_marks.get(atomNumber(p));
 367     }
 368
 369     inline bool MarkedBlock::testAndSetMarked(const void* p)
 370     {
 371         return m_marks.concurrentTestAndSet(atomNumber(p));
 372     }
 373
 374     inline void MarkedBlock::setMarked(const void* p)
 375     {
 376         m_marks.set(atomNumber(p));
 377     }
 378
 379     inline void MarkedBlock::clearMarked(const void* p)
 380     {
 381         ASSERT(m_marks.get(atomNumber(p)));
 382         m_marks.clear(atomNumber(p));
 383     }
 384
 385     inline bool MarkedBlock::isNewlyAllocated(const void* p)
 386     {
 387         return m_newlyAllocated->get(atomNumber(p));
 388     }
 389
 390     inline void MarkedBlock::setNewlyAllocated(const void* p)
 391     {
 392         m_newlyAllocated->set(atomNumber(p));
 393     }
 394
 395     inline void MarkedBlock::clearNewlyAllocated(const void* p)
 396     {
 397         m_newlyAllocated->clear(atomNumber(p));
 398     }
 399
 400     inline bool MarkedBlock::clearNewlyAllocated()
 401     {
 402         if (m_newlyAllocated) {
 403             m_newlyAllocated.clear();
 404             return true;
 405         }
 406         return false;
 407     }
 408
 409     inline bool MarkedBlock::isLive(const JSCell* cell)
 410     {
 411         switch (m_state) {
 412         case Allocated:
 413             return true;
 414
 415         case Retired:
 416         case Marked:
 417             return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
 418
 419         case New:
 420         case FreeListed:
 421             RELEASE_ASSERT_NOT_REACHED();
 422             return false;
 423         }
 424
 425         RELEASE_ASSERT_NOT_REACHED();
 426         return false;
 427     }
 428
 429     inline bool MarkedBlock::isLiveCell(const void* p)
 430     {
 431         ASSERT(MarkedBlock::isAtomAligned(p));
 432         size_t atomNumber = this->atomNumber(p);
 433         size_t firstAtom = this->firstAtom();
 434         if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
 435             return false;
 436         if ((atomNumber - firstAtom) % m_atomsPerCell) // Filters pointers into cell middles.
 437             return false;
 438         if (atomNumber >= m_endAtom) // Filters pointers into invalid cells out of the range.
 439             return false;
 440
 441         return isLive(static_cast<const JSCell*>(p));
 442     }
 443
 444     template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
 445     {
 446         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
 447             JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
 448             functor(cell);
 449         }
 450     }
 451
 452     template <typename Functor> inline void MarkedBlock::forEachLiveCell(Functor& functor)
 453     {
 454         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
 455             JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
 456             if (!isLive(cell))
 457                 continue;
 458
 459             functor(cell);
 460         }
 461     }
 462
 463     template <typename Functor> inline void MarkedBlock::forEachDeadCell(Functor& functor)
 464     {
 465         for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
 466             JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
 467             if (isLive(cell))
 468                 continue;
 469
 470             functor(cell);
 471         }
 472     }
 473
 474     inline bool MarkedBlock::needsSweeping()
 475     {
 476         return m_state == Marked;
 477     }
 478
 479 } // namespace JSC
 480
 481 namespace WTF {
 482
 483     struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
 484         static unsigned hash(JSC::MarkedBlock* const& key)
 485         {
 486             // Aligned VM regions tend to be monotonically increasing integers,
 487             // which is a great hash function, but we have to remove the low bits,
 488             // since they're always zero, which is a terrible hash function!
 489             return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
 490         }
 491     };
 492
 493     template<> struct DefaultHash<JSC::MarkedBlock*> {
 494         typedef MarkedBlockHash Hash;
 495     };
 496
 497 } // namespace WTF
 498
 499 #endif // MarkedBlock_h