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 52namespace 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 481namespace 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 500