heap/MarkedAllocator.cpp

   1 /*
   2  * Copyright (C) 2012, 2013 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 "MarkedAllocator.h"
  28
  29 #include "DelayedReleaseScope.h"
  30 #include "GCActivityCallback.h"
  31 #include "Heap.h"
  32 #include "IncrementalSweeper.h"
  33 #include "JSCInlines.h"
  34 #include "VM.h"
  35 #include <wtf/CurrentTime.h>
  36
  37 namespace JSC {
  38
  39 static bool isListPagedOut(double deadline, DoublyLinkedList<MarkedBlock>& list)
  40 {
  41     unsigned itersSinceLastTimeCheck = 0;
  42     MarkedBlock* block = list.head();
  43     while (block) {
  44         block = block->next();
  45         ++itersSinceLastTimeCheck;
  46         if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
  47             double currentTime = WTF::monotonicallyIncreasingTime();
  48             if (currentTime > deadline)
  49                 return true;
  50             itersSinceLastTimeCheck = 0;
  51         }
  52     }
  53     return false;
  54 }
  55
  56 bool MarkedAllocator::isPagedOut(double deadline)
  57 {
  58     if (isListPagedOut(deadline, m_blockList))
  59         return true;
  60     return false;
  61 }
  62
  63 inline void* MarkedAllocator::tryAllocateHelper(size_t bytes)
  64 {
  65     // We need a while loop to check the free list because the DelayedReleaseScope
  66     // could cause arbitrary code to execute and exhaust the free list that we
  67     // thought had elements in it.
  68     while (!m_freeList.head) {
  69         DelayedReleaseScope delayedReleaseScope(*m_markedSpace);
  70         if (m_currentBlock) {
  71             ASSERT(m_currentBlock == m_nextBlockToSweep);
  72             m_currentBlock->didConsumeFreeList();
  73             m_nextBlockToSweep = m_currentBlock->next();
  74         }
  75
  76         MarkedBlock* next;
  77         for (MarkedBlock*& block = m_nextBlockToSweep; block; block = next) {
  78             next = block->next();
  79
  80             MarkedBlock::FreeList freeList = block->sweep(MarkedBlock::SweepToFreeList);
  81
  82             double utilization = ((double)MarkedBlock::blockSize - (double)freeList.bytes) / (double)MarkedBlock::blockSize;
  83             if (utilization >= Options::minMarkedBlockUtilization()) {
  84                 ASSERT(freeList.bytes || !freeList.head);
  85                 m_blockList.remove(block);
  86                 m_retiredBlocks.push(block);
  87                 block->didRetireBlock(freeList);
  88                 continue;
  89             }
  90
  91             if (bytes > block->cellSize()) {
  92                 block->stopAllocating(freeList);
  93                 continue;
  94             }
  95
  96             m_currentBlock = block;
  97             m_freeList = freeList;
  98             break;
  99         }
 100
 101         if (!m_freeList.head) {
 102             m_currentBlock = 0;
 103             return 0;
 104         }
 105     }
 106
 107     ASSERT(m_freeList.head);
 108     void* head = tryPopFreeList(bytes);
 109     ASSERT(head);
 110     m_markedSpace->didAllocateInBlock(m_currentBlock);
 111     return head;
 112 }
 113
 114 inline void* MarkedAllocator::tryPopFreeList(size_t bytes)
 115 {
 116     ASSERT(m_currentBlock);
 117     if (bytes > m_currentBlock->cellSize())
 118         return 0;
 119
 120     MarkedBlock::FreeCell* head = m_freeList.head;
 121     m_freeList.head = head->next;
 122     return head;
 123 }
 124
 125 inline void* MarkedAllocator::tryAllocate(size_t bytes)
 126 {
 127     ASSERT(!m_heap->isBusy());
 128     m_heap->m_operationInProgress = Allocation;
 129     void* result = tryAllocateHelper(bytes);
 130
 131     // Due to the DelayedReleaseScope in tryAllocateHelper, some other thread might have
 132     // created a new block after we thought we didn't find any free cells.
 133     while (!result && m_currentBlock) {
 134         // A new block was added by another thread so try popping the free list.
 135         result = tryPopFreeList(bytes);
 136         if (result)
 137             break;
 138         // The free list was empty, so call tryAllocateHelper to do the normal sweeping stuff.
 139         result = tryAllocateHelper(bytes);
 140     }
 141
 142     m_heap->m_operationInProgress = NoOperation;
 143     ASSERT(result || !m_currentBlock);
 144     return result;
 145 }
 146
 147 ALWAYS_INLINE void MarkedAllocator::doTestCollectionsIfNeeded()
 148 {
 149     if (!Options::slowPathAllocsBetweenGCs())
 150         return;
 151
 152     static unsigned allocationCount = 0;
 153     if (!allocationCount) {
 154         if (!m_heap->isDeferred())
 155             m_heap->collectAllGarbage();
 156         ASSERT(m_heap->m_operationInProgress == NoOperation);
 157     }
 158     if (++allocationCount >= Options::slowPathAllocsBetweenGCs())
 159         allocationCount = 0;
 160 }
 161
 162 void* MarkedAllocator::allocateSlowCase(size_t bytes)
 163 {
 164     ASSERT(m_heap->vm()->currentThreadIsHoldingAPILock());
 165     doTestCollectionsIfNeeded();
 166
 167     ASSERT(!m_markedSpace->isIterating());
 168     ASSERT(!m_freeList.head);
 169     m_heap->didAllocate(m_freeList.bytes);
 170
 171     void* result = tryAllocate(bytes);
 172
 173     if (LIKELY(result != 0))
 174         return result;
 175
 176     if (m_heap->collectIfNecessaryOrDefer()) {
 177         result = tryAllocate(bytes);
 178         if (result)
 179             return result;
 180     }
 181
 182     ASSERT(!m_heap->shouldCollect());
 183
 184     MarkedBlock* block = allocateBlock(bytes);
 185     ASSERT(block);
 186     addBlock(block);
 187
 188     result = tryAllocate(bytes);
 189     ASSERT(result);
 190     return result;
 191 }
 192
 193 MarkedBlock* MarkedAllocator::allocateBlock(size_t bytes)
 194 {
 195     size_t minBlockSize = MarkedBlock::blockSize;
 196     size_t minAllocationSize = WTF::roundUpToMultipleOf(WTF::pageSize(), sizeof(MarkedBlock) + bytes);
 197     size_t blockSize = std::max(minBlockSize, minAllocationSize);
 198
 199     size_t cellSize = m_cellSize ? m_cellSize : WTF::roundUpToMultipleOf<MarkedBlock::atomSize>(bytes);
 200
 201     if (blockSize == MarkedBlock::blockSize)
 202         return MarkedBlock::create(m_heap->blockAllocator().allocate<MarkedBlock>(), this, cellSize, m_destructorType);
 203     return MarkedBlock::create(m_heap->blockAllocator().allocateCustomSize(blockSize, MarkedBlock::blockSize), this, cellSize, m_destructorType);
 204 }
 205
 206 void MarkedAllocator::addBlock(MarkedBlock* block)
 207 {
 208     ASSERT(!m_currentBlock);
 209     ASSERT(!m_freeList.head);
 210
 211     m_blockList.append(block);
 212     m_nextBlockToSweep = block;
 213     m_markedSpace->didAddBlock(block);
 214 }
 215
 216 void MarkedAllocator::removeBlock(MarkedBlock* block)
 217 {
 218     if (m_currentBlock == block) {
 219         m_currentBlock = m_currentBlock->next();
 220         m_freeList = MarkedBlock::FreeList();
 221     }
 222     if (m_nextBlockToSweep == block)
 223         m_nextBlockToSweep = m_nextBlockToSweep->next();
 224
 225     block->willRemoveBlock();
 226     m_blockList.remove(block);
 227 }
 228
 229 void MarkedAllocator::reset()
 230 {
 231     m_lastActiveBlock = 0;
 232     m_currentBlock = 0;
 233     m_freeList = MarkedBlock::FreeList();
 234     if (m_heap->operationInProgress() == FullCollection)
 235         m_blockList.append(m_retiredBlocks);
 236
 237     m_nextBlockToSweep = m_blockList.head();
 238 }
 239
 240 struct LastChanceToFinalize : MarkedBlock::VoidFunctor {
 241     void operator()(MarkedBlock* block) { block->lastChanceToFinalize(); }
 242 };
 243
 244 void MarkedAllocator::lastChanceToFinalize()
 245 {
 246     m_blockList.append(m_retiredBlocks);
 247     LastChanceToFinalize functor;
 248     forEachBlock(functor);
 249 }
 250
 251 } // namespace JSC