Source/JavaScriptCore/runtime/MarkedSpace.cpp

   1 /*
   2  *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
   3  *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public
   7  *  License as published by the Free Software Foundation; either
   8  *  version 2 of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free Software
  17  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  18  *
  19  */
  20
  21 #include "config.h"
  22 #include "MarkedSpace.h"
  23
  24 #include "CollectorHeapIterator.h"
  25 #include "JSCell.h"
  26 #include "JSGlobalData.h"
  27 #include "JSLock.h"
  28
  29 using std::max;
  30
  31 namespace JSC {
  32
  33 class Structure;
  34
  35 // tunable parameters
  36
  37 const size_t GROWTH_FACTOR = 2;
  38 const size_t LOW_WATER_FACTOR = 4;
  39 const size_t ALLOCATIONS_PER_COLLECTION = 3600;
  40 // This value has to be a macro to be used in max() without introducing
  41 // a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
  42 #define MIN_ARRAY_SIZE (static_cast<size_t>(14))
  43
  44 MarkedSpace::MarkedSpace(JSGlobalData* globalData)
  45     : m_globalData(globalData)
  46 {
  47     memset(&m_heap, 0, sizeof(CollectorHeap));
  48     allocateBlock();
  49 }
  50
  51 void MarkedSpace::destroy(ProtectCountSet& protectedValuesCopy)
  52 {
  53     clearMarkBits();
  54     ProtectCountSet::iterator protectedValuesEnd = protectedValuesCopy.end();
  55     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
  56         markCell(it->first);
  57
  58     m_heap.nextCell = 0;
  59     m_heap.nextBlock = 0;
  60     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
  61     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
  62     for ( ; it != end; ++it)
  63         (*it)->~JSCell();
  64
  65     protectedValuesEnd = protectedValuesCopy.end();
  66     for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)
  67         it->first->~JSCell();
  68
  69     for (size_t block = 0; block < m_heap.usedBlocks; ++block)
  70         m_heap.blocks[block].deallocate();
  71
  72     fastFree(m_heap.blocks);
  73
  74     memset(&m_heap, 0, sizeof(CollectorHeap));
  75 }
  76
  77 NEVER_INLINE CollectorBlock* MarkedSpace::allocateBlock()
  78 {
  79     PageAllocationAligned allocation = PageAllocationAligned::allocate(BLOCK_SIZE, BLOCK_SIZE, OSAllocator::JSGCHeapPages);
  80     CollectorBlock* block = static_cast<CollectorBlock*>(allocation.base());
  81     if (!block)
  82         CRASH();
  83
  84     // Initialize block.
  85
  86     block->heap = &globalData()->heap;
  87     clearMarkBits(block);
  88
  89     Structure* dummyMarkableCellStructure = globalData()->dummyMarkableCellStructure.get();
  90     for (size_t i = 0; i < HeapConstants::cellsPerBlock; ++i)
  91         new (&block->cells[i]) JSCell(dummyMarkableCellStructure);
  92
  93     // Add block to blocks vector.
  94
  95     size_t numBlocks = m_heap.numBlocks;
  96     if (m_heap.usedBlocks == numBlocks) {
  97         static const size_t maxNumBlocks = ULONG_MAX / sizeof(PageAllocationAligned) / GROWTH_FACTOR;
  98         if (numBlocks > maxNumBlocks)
  99             CRASH();
 100         numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
 101         m_heap.numBlocks = numBlocks;
 102         m_heap.blocks = static_cast<PageAllocationAligned*>(fastRealloc(m_heap.blocks, numBlocks * sizeof(PageAllocationAligned)));
 103     }
 104     m_heap.blocks[m_heap.usedBlocks++] = allocation;
 105
 106     return block;
 107 }
 108
 109 NEVER_INLINE void MarkedSpace::freeBlock(size_t block)
 110 {
 111     ObjectIterator it(m_heap, block);
 112     ObjectIterator end(m_heap, block + 1);
 113     for ( ; it != end; ++it)
 114         (*it)->~JSCell();
 115     m_heap.blocks[block].deallocate();
 116
 117     // swap with the last block so we compact as we go
 118     m_heap.blocks[block] = m_heap.blocks[m_heap.usedBlocks - 1];
 119     m_heap.usedBlocks--;
 120
 121     if (m_heap.numBlocks > MIN_ARRAY_SIZE && m_heap.usedBlocks < m_heap.numBlocks / LOW_WATER_FACTOR) {
 122         m_heap.numBlocks = m_heap.numBlocks / GROWTH_FACTOR;
 123         m_heap.blocks = static_cast<PageAllocationAligned*>(fastRealloc(m_heap.blocks, m_heap.numBlocks * sizeof(PageAllocationAligned)));
 124     }
 125 }
 126
 127 void* MarkedSpace::allocate(size_t s)
 128 {
 129     ASSERT(globalData()->identifierTable == wtfThreadData().currentIdentifierTable());
 130     typedef HeapConstants::Block Block;
 131     typedef HeapConstants::Cell Cell;
 132
 133     ASSERT(JSLock::lockCount() > 0);
 134     ASSERT(JSLock::currentThreadIsHoldingLock());
 135     ASSERT_UNUSED(s, s <= HeapConstants::cellSize);
 136
 137     // Fast case: find the next garbage cell and recycle it.
 138
 139     do {
 140         ASSERT(m_heap.nextBlock < m_heap.usedBlocks);
 141         Block* block = m_heap.collectorBlock(m_heap.nextBlock);
 142         do {
 143             ASSERT(m_heap.nextCell < HeapConstants::cellsPerBlock);
 144             if (!block->marked.get(m_heap.nextCell)) { // Always false for the last cell in the block
 145                 Cell* cell = &block->cells[m_heap.nextCell];
 146
 147                 JSCell* imp = reinterpret_cast<JSCell*>(cell);
 148                 imp->~JSCell();
 149
 150                 ++m_heap.nextCell;
 151                 return cell;
 152             }
 153             block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);
 154         } while (m_heap.nextCell != HeapConstants::cellsPerBlock);
 155         m_heap.nextCell = 0;
 156     } while (++m_heap.nextBlock != m_heap.usedBlocks);
 157
 158     return 0;
 159 }
 160
 161 void MarkedSpace::resizeBlocks()
 162 {
 163     size_t usedCellCount = markedCells();
 164     size_t minCellCount = usedCellCount + max(ALLOCATIONS_PER_COLLECTION, usedCellCount);
 165     size_t minBlockCount = (minCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
 166
 167     size_t maxCellCount = 1.25f * minCellCount;
 168     size_t maxBlockCount = (maxCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;
 169
 170     if (m_heap.usedBlocks < minBlockCount)
 171         growBlocks(minBlockCount);
 172     else if (m_heap.usedBlocks > maxBlockCount)
 173         shrinkBlocks(maxBlockCount);
 174 }
 175
 176 void MarkedSpace::growBlocks(size_t neededBlocks)
 177 {
 178     ASSERT(m_heap.usedBlocks < neededBlocks);
 179     while (m_heap.usedBlocks < neededBlocks)
 180         allocateBlock();
 181 }
 182
 183 void MarkedSpace::shrinkBlocks(size_t neededBlocks)
 184 {
 185     ASSERT(m_heap.usedBlocks > neededBlocks);
 186
 187     // Clear the always-on last bit, so isEmpty() isn't fooled by it.
 188     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 189         m_heap.collectorBlock(i)->marked.clear(HeapConstants::cellsPerBlock - 1);
 190
 191     for (size_t i = 0; i != m_heap.usedBlocks && m_heap.usedBlocks != neededBlocks; ) {
 192         if (m_heap.collectorBlock(i)->marked.isEmpty()) {
 193             freeBlock(i);
 194         } else
 195             ++i;
 196     }
 197
 198     // Reset the always-on last bit.
 199     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 200         m_heap.collectorBlock(i)->marked.set(HeapConstants::cellsPerBlock - 1);
 201 }
 202
 203 bool MarkedSpace::containsSlowCase(void* x)
 204 {
 205     uintptr_t xAsBits = reinterpret_cast<uintptr_t>(x);
 206     xAsBits &= CELL_ALIGN_MASK;
 207
 208     uintptr_t offset = xAsBits & BLOCK_OFFSET_MASK;
 209     const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 210     if (offset > lastCellOffset)
 211         return false;
 212
 213     CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(xAsBits - offset);
 214     size_t usedBlocks = m_heap.usedBlocks;
 215     for (size_t block = 0; block < usedBlocks; block++) {
 216         if (m_heap.collectorBlock(block) != blockAddr)
 217             continue;
 218
 219         // x is a pointer into the heap. Now, verify that the cell it
 220         // points to is live. (If the cell is dead, we must not mark it,
 221         // since that would revive it in a zombie state.)
 222         if (block < m_heap.nextBlock)
 223             return true;
 224
 225         size_t cellOffset = offset / CELL_SIZE;
 226
 227         if (block == m_heap.nextBlock && cellOffset < m_heap.nextCell)
 228             return true;
 229
 230         return blockAddr->marked.get(cellOffset);
 231     }
 232
 233     return false;
 234 }
 235
 236 void MarkedSpace::clearMarkBits()
 237 {
 238     for (size_t i = 0; i < m_heap.usedBlocks; ++i)
 239         clearMarkBits(m_heap.collectorBlock(i));
 240 }
 241
 242 void MarkedSpace::clearMarkBits(CollectorBlock* block)
 243 {
 244     // allocate assumes that the last cell in every block is marked.
 245     block->marked.clearAll();
 246     block->marked.set(HeapConstants::cellsPerBlock - 1);
 247 }
 248
 249 size_t MarkedSpace::markedCells(size_t startBlock, size_t startCell) const
 250 {
 251     ASSERT(startBlock <= m_heap.usedBlocks);
 252     ASSERT(startCell < HeapConstants::cellsPerBlock);
 253
 254     if (startBlock >= m_heap.usedBlocks)
 255         return 0;
 256
 257     size_t result = 0;
 258     result += m_heap.collectorBlock(startBlock)->marked.count(startCell);
 259     for (size_t i = startBlock + 1; i < m_heap.usedBlocks; ++i)
 260         result += m_heap.collectorBlock(i)->marked.count();
 261
 262     return result;
 263 }
 264
 265 void MarkedSpace::sweep()
 266 {
 267 #if !ENABLE(JSC_ZOMBIES)
 268     Structure* dummyMarkableCellStructure = globalData()->dummyMarkableCellStructure.get();
 269 #endif
 270
 271     DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);
 272     DeadObjectIterator end(m_heap, m_heap.usedBlocks);
 273     for ( ; it != end; ++it) {
 274         JSCell* cell = *it;
 275 #if ENABLE(JSC_ZOMBIES)
 276         if (!cell->isZombie()) {
 277             const ClassInfo* info = cell->classInfo();
 278             cell->~JSCell();
 279             new (cell) JSZombie(info, JSZombie::leakedZombieStructure());
 280             Heap::markCell(cell);
 281         }
 282 #else
 283         cell->~JSCell();
 284         // Callers of sweep assume it's safe to mark any cell in the heap.
 285         new (cell) JSCell(dummyMarkableCellStructure);
 286 #endif
 287     }
 288 }
 289
 290 size_t MarkedSpace::objectCount() const
 291 {
 292     return m_heap.nextBlock * HeapConstants::cellsPerBlock // allocated full blocks
 293            + m_heap.nextCell // allocated cells in current block
 294            + markedCells(m_heap.nextBlock, m_heap.nextCell) // marked cells in remainder of m_heap
 295            - m_heap.usedBlocks; // 1 cell per block is a dummy sentinel
 296 }
 297
 298 size_t MarkedSpace::size() const
 299 {
 300     return objectCount() * HeapConstants::cellSize;
 301 }
 302
 303 size_t MarkedSpace::capacity() const
 304 {
 305     return m_heap.usedBlocks * BLOCK_SIZE;
 306 }
 307
 308 void MarkedSpace::reset()
 309 {
 310     m_heap.nextCell = 0;
 311     m_heap.nextBlock = 0;
 312 #if ENABLE(JSC_ZOMBIES)
 313     sweep();
 314 #endif
 315     resizeBlocks();
 316 }
 317
 318 LiveObjectIterator MarkedSpace::primaryHeapBegin()
 319 {
 320     return LiveObjectIterator(m_heap, 0);
 321 }
 322
 323 LiveObjectIterator MarkedSpace::primaryHeapEnd()
 324 {
 325     return LiveObjectIterator(m_heap, m_heap.usedBlocks);
 326 }
 327
 328 } // namespace JSC