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