heap/CopiedSpace.cpp

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "CopiedSpace.h"
  28
  29 #include "CopiedSpaceInlines.h"
  30 #include "GCActivityCallback.h"
  31 #include "Operations.h"
  32 #include "Options.h"
  33
  34 namespace JSC {
  35
  36 CopiedSpace::CopiedSpace(Heap* heap)
  37     : m_heap(heap)
  38     , m_toSpace(0)
  39     , m_fromSpace(0)
  40     , m_inCopyingPhase(false)
  41     , m_shouldDoCopyPhase(false)
  42     , m_numberOfLoanedBlocks(0)
  43 {
  44     m_toSpaceLock.Init();
  45 }
  46
  47 CopiedSpace::~CopiedSpace()
  48 {
  49     while (!m_toSpace->isEmpty())
  50         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(m_toSpace->removeHead()));
  51
  52     while (!m_fromSpace->isEmpty())
  53         m_heap->blockAllocator().deallocate(CopiedBlock::destroy(m_fromSpace->removeHead()));
  54
  55     while (!m_oversizeBlocks.isEmpty())
  56         m_heap->blockAllocator().deallocateCustomSize(CopiedBlock::destroy(m_oversizeBlocks.removeHead()));
  57 }
  58
  59 void CopiedSpace::init()
  60 {
  61     m_toSpace = &m_blocks1;
  62     m_fromSpace = &m_blocks2;
  63
  64     allocateBlock();
  65 }
  66
  67 CheckedBoolean CopiedSpace::tryAllocateSlowCase(size_t bytes, void** outPtr)
  68 {
  69     if (isOversize(bytes))
  70         return tryAllocateOversize(bytes, outPtr);
  71
  72     ASSERT(m_heap->vm()->apiLock().currentThreadIsHoldingLock());
  73     m_heap->didAllocate(m_allocator.currentCapacity());
  74
  75     allocateBlock();
  76
  77     *outPtr = m_allocator.forceAllocate(bytes);
  78     return true;
  79 }
  80
  81 CheckedBoolean CopiedSpace::tryAllocateOversize(size_t bytes, void** outPtr)
  82 {
  83     ASSERT(isOversize(bytes));
  84
  85     CopiedBlock* block = CopiedBlock::create(m_heap->blockAllocator().allocateCustomSize(sizeof(CopiedBlock) + bytes, CopiedBlock::blockSize));
  86     m_oversizeBlocks.push(block);
  87     m_blockFilter.add(reinterpret_cast<Bits>(block));
  88     m_blockSet.add(block);
  89
  90     CopiedAllocator allocator;
  91     allocator.setCurrentBlock(block);
  92     *outPtr = allocator.forceAllocate(bytes);
  93     allocator.resetCurrentBlock();
  94
  95     m_heap->didAllocate(block->region()->blockSize());
  96
  97     return true;
  98 }
  99
 100 CheckedBoolean CopiedSpace::tryReallocate(void** ptr, size_t oldSize, size_t newSize)
 101 {
 102     if (oldSize >= newSize)
 103         return true;
 104
 105     void* oldPtr = *ptr;
 106     ASSERT(!m_heap->vm()->isInitializingObject());
 107
 108     if (CopiedSpace::blockFor(oldPtr)->isOversize() || isOversize(newSize))
 109         return tryReallocateOversize(ptr, oldSize, newSize);
 110
 111     if (m_allocator.tryReallocate(oldPtr, oldSize, newSize))
 112         return true;
 113
 114     void* result = 0;
 115     if (!tryAllocate(newSize, &result)) {
 116         *ptr = 0;
 117         return false;
 118     }
 119     memcpy(result, oldPtr, oldSize);
 120     *ptr = result;
 121     return true;
 122 }
 123
 124 CheckedBoolean CopiedSpace::tryReallocateOversize(void** ptr, size_t oldSize, size_t newSize)
 125 {
 126     ASSERT(isOversize(oldSize) || isOversize(newSize));
 127     ASSERT(newSize > oldSize);
 128
 129     void* oldPtr = *ptr;
 130
 131     void* newPtr = 0;
 132     if (!tryAllocateOversize(newSize, &newPtr)) {
 133         *ptr = 0;
 134         return false;
 135     }
 136
 137     memcpy(newPtr, oldPtr, oldSize);
 138
 139     CopiedBlock* oldBlock = CopiedSpace::blockFor(oldPtr);
 140     if (oldBlock->isOversize()) {
 141         m_oversizeBlocks.remove(oldBlock);
 142         m_blockSet.remove(oldBlock);
 143         m_heap->blockAllocator().deallocateCustomSize(CopiedBlock::destroy(oldBlock));
 144     }
 145
 146     *ptr = newPtr;
 147     return true;
 148 }
 149
 150 void CopiedSpace::doneFillingBlock(CopiedBlock* block, CopiedBlock** exchange)
 151 {
 152     ASSERT(m_inCopyingPhase);
 153
 154     if (exchange)
 155         *exchange = allocateBlockForCopyingPhase();
 156
 157     if (!block)
 158         return;
 159
 160     if (!block->dataSize()) {
 161         recycleBorrowedBlock(block);
 162         return;
 163     }
 164
 165     block->zeroFillWilderness();
 166
 167     {
 168         SpinLockHolder locker(&m_toSpaceLock);
 169         m_toSpace->push(block);
 170         m_blockSet.add(block);
 171         m_blockFilter.add(reinterpret_cast<Bits>(block));
 172     }
 173
 174     {
 175         MutexLocker locker(m_loanedBlocksLock);
 176         ASSERT(m_numberOfLoanedBlocks > 0);
 177         ASSERT(m_inCopyingPhase);
 178         m_numberOfLoanedBlocks--;
 179         if (!m_numberOfLoanedBlocks)
 180             m_loanedBlocksCondition.signal();
 181     }
 182 }
 183
 184 void CopiedSpace::startedCopying()
 185 {
 186     std::swap(m_fromSpace, m_toSpace);
 187
 188     m_blockFilter.reset();
 189     m_allocator.resetCurrentBlock();
 190
 191     CopiedBlock* next = 0;
 192     size_t totalLiveBytes = 0;
 193     size_t totalUsableBytes = 0;
 194     for (CopiedBlock* block = m_fromSpace->head(); block; block = next) {
 195         next = block->next();
 196         if (!block->isPinned() && block->canBeRecycled()) {
 197             recycleEvacuatedBlock(block);
 198             continue;
 199         }
 200         totalLiveBytes += block->liveBytes();
 201         totalUsableBytes += block->payloadCapacity();
 202     }
 203
 204     CopiedBlock* block = m_oversizeBlocks.head();
 205     while (block) {
 206         CopiedBlock* next = block->next();
 207         if (block->isPinned()) {
 208             m_blockFilter.add(reinterpret_cast<Bits>(block));
 209             totalLiveBytes += block->payloadCapacity();
 210             totalUsableBytes += block->payloadCapacity();
 211             block->didSurviveGC();
 212         } else {
 213             m_oversizeBlocks.remove(block);
 214             m_blockSet.remove(block);
 215             m_heap->blockAllocator().deallocateCustomSize(CopiedBlock::destroy(block));
 216         }
 217         block = next;
 218     }
 219
 220     double markedSpaceBytes = m_heap->objectSpace().capacity();
 221     double totalFragmentation = ((double)totalLiveBytes + markedSpaceBytes) / ((double)totalUsableBytes + markedSpaceBytes);
 222     m_shouldDoCopyPhase = totalFragmentation <= Options::minHeapUtilization();
 223     if (!m_shouldDoCopyPhase)
 224         return;
 225
 226     ASSERT(m_shouldDoCopyPhase);
 227     ASSERT(!m_inCopyingPhase);
 228     ASSERT(!m_numberOfLoanedBlocks);
 229     m_inCopyingPhase = true;
 230 }
 231
 232 void CopiedSpace::doneCopying()
 233 {
 234     {
 235         MutexLocker locker(m_loanedBlocksLock);
 236         while (m_numberOfLoanedBlocks > 0)
 237             m_loanedBlocksCondition.wait(m_loanedBlocksLock);
 238     }
 239
 240     ASSERT(m_inCopyingPhase == m_shouldDoCopyPhase);
 241     m_inCopyingPhase = false;
 242
 243     while (!m_fromSpace->isEmpty()) {
 244         CopiedBlock* block = m_fromSpace->removeHead();
 245         // All non-pinned blocks in from-space should have been reclaimed as they were evacuated.
 246         ASSERT(block->isPinned() || !m_shouldDoCopyPhase);
 247         block->didSurviveGC();
 248         // We don't add the block to the blockSet because it was never removed.
 249         ASSERT(m_blockSet.contains(block));
 250         m_blockFilter.add(reinterpret_cast<Bits>(block));
 251         m_toSpace->push(block);
 252     }
 253
 254     if (!m_toSpace->head())
 255         allocateBlock();
 256     else
 257         m_allocator.setCurrentBlock(m_toSpace->head());
 258
 259     m_shouldDoCopyPhase = false;
 260 }
 261
 262 size_t CopiedSpace::size()
 263 {
 264     size_t calculatedSize = 0;
 265
 266     for (CopiedBlock* block = m_toSpace->head(); block; block = block->next())
 267         calculatedSize += block->size();
 268
 269     for (CopiedBlock* block = m_fromSpace->head(); block; block = block->next())
 270         calculatedSize += block->size();
 271
 272     for (CopiedBlock* block = m_oversizeBlocks.head(); block; block = block->next())
 273         calculatedSize += block->size();
 274
 275     return calculatedSize;
 276 }
 277
 278 size_t CopiedSpace::capacity()
 279 {
 280     size_t calculatedCapacity = 0;
 281
 282     for (CopiedBlock* block = m_toSpace->head(); block; block = block->next())
 283         calculatedCapacity += block->capacity();
 284
 285     for (CopiedBlock* block = m_fromSpace->head(); block; block = block->next())
 286         calculatedCapacity += block->capacity();
 287
 288     for (CopiedBlock* block = m_oversizeBlocks.head(); block; block = block->next())
 289         calculatedCapacity += block->capacity();
 290
 291     return calculatedCapacity;
 292 }
 293
 294 static bool isBlockListPagedOut(double deadline, DoublyLinkedList<CopiedBlock>* list)
 295 {
 296     unsigned itersSinceLastTimeCheck = 0;
 297     CopiedBlock* current = list->head();
 298     while (current) {
 299         current = current->next();
 300         ++itersSinceLastTimeCheck;
 301         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
 302             double currentTime = WTF::monotonicallyIncreasingTime();
 303             if (currentTime > deadline)
 304                 return true;
 305             itersSinceLastTimeCheck = 0;
 306         }
 307     }
 308
 309     return false;
 310 }
 311
 312 bool CopiedSpace::isPagedOut(double deadline)
 313 {
 314     return isBlockListPagedOut(deadline, m_toSpace)
 315         || isBlockListPagedOut(deadline, m_fromSpace)
 316         || isBlockListPagedOut(deadline, &m_oversizeBlocks);
 317 }
 318
 319 } // namespace JSC