1/*
2 * Copyright (C) 2012-2019 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 "BlockDirectory.h"
28
29#include "BlockDirectoryInlines.h"
30#include "GCActivityCallback.h"
31#include "Heap.h"
32#include "IncrementalSweeper.h"
33#include "JSCInlines.h"
34#include "MarkedBlockInlines.h"
35#include "SubspaceInlines.h"
36#include "SuperSampler.h"
37#include "VM.h"
38
39namespace JSC {
40
41BlockDirectory::BlockDirectory(Heap* heap, size_t cellSize)
42 : m_cellSize(static_cast<unsigned>(cellSize))
43 , m_heap(heap)
44{
45}
46
47BlockDirectory::~BlockDirectory()
48{
49 auto locker = holdLock(m_localAllocatorsLock);
50 while (!m_localAllocators.isEmpty())
51 m_localAllocators.begin()->remove();
52}
53
54void BlockDirectory::setSubspace(Subspace* subspace)
55{
56 m_attributes = subspace->attributes();
57 m_subspace = subspace;
58}
59
60bool BlockDirectory::isPagedOut(MonotonicTime deadline)
61{
62 unsigned itersSinceLastTimeCheck = 0;
63 for (auto* block : m_blocks) {
64 if (block)
65 block->block().populatePage();
66 ++itersSinceLastTimeCheck;
67 if (itersSinceLastTimeCheck >= Heap::s_timeCheckResolution) {
68 MonotonicTime currentTime = MonotonicTime::now();
69 if (currentTime > deadline)
70 return true;
71 itersSinceLastTimeCheck = 0;
72 }
73 }
74 return false;
75}
76
77MarkedBlock::Handle* BlockDirectory::findEmptyBlockToSteal()
78{
79 m_emptyCursor = m_empty.findBit(m_emptyCursor, true);
80 if (m_emptyCursor >= m_blocks.size())
81 return nullptr;
82 return m_blocks[m_emptyCursor];
83}
84
85MarkedBlock::Handle* BlockDirectory::findBlockForAllocation(LocalAllocator& allocator)
86{
87 for (;;) {
88 allocator.m_allocationCursor = (m_canAllocateButNotEmpty | m_empty).findBit(allocator.m_allocationCursor, true);
89 if (allocator.m_allocationCursor >= m_blocks.size())
90 return nullptr;
91
92 size_t blockIndex = allocator.m_allocationCursor++;
93 MarkedBlock::Handle* result = m_blocks[blockIndex];
94 setIsCanAllocateButNotEmpty(NoLockingNecessary, blockIndex, false);
95 return result;
96 }
97}
98
99MarkedBlock::Handle* BlockDirectory::tryAllocateBlock()
100{
101 SuperSamplerScope superSamplerScope(false);
102
103 MarkedBlock::Handle* handle = MarkedBlock::tryCreate(*m_heap, subspace()->alignedMemoryAllocator());
104 if (!handle)
105 return nullptr;
106
107 markedSpace().didAddBlock(handle);
108
109 return handle;
110}
111
112void BlockDirectory::addBlock(MarkedBlock::Handle* block)
113{
114 size_t index;
115 if (m_freeBlockIndices.isEmpty()) {
116 index = m_blocks.size();
117
118 size_t oldCapacity = m_blocks.capacity();
119 m_blocks.append(block);
120 if (m_blocks.capacity() != oldCapacity) {
121 forEachBitVector(
122 NoLockingNecessary,
123 [&] (FastBitVector& vector) {
124 ASSERT_UNUSED(vector, vector.numBits() == oldCapacity);
125 });
126
127 ASSERT(m_blocks.capacity() > oldCapacity);
128
129 LockHolder locker(m_bitvectorLock);
130 subspace()->didResizeBits(m_blocks.capacity());
131 forEachBitVector(
132 locker,
133 [&] (FastBitVector& vector) {
134 vector.resize(m_blocks.capacity());
135 });
136 }
137 } else {
138 index = m_freeBlockIndices.takeLast();
139 ASSERT(!m_blocks[index]);
140 m_blocks[index] = block;
141 }
142
143 forEachBitVector(
144 NoLockingNecessary,
145 [&] (FastBitVector& vector) {
146 ASSERT_UNUSED(vector, !vector[index]);
147 });
148
149 // This is the point at which the block learns of its cellSize() and attributes().
150 block->didAddToDirectory(this, index);
151
152 setIsLive(NoLockingNecessary, index, true);
153 setIsEmpty(NoLockingNecessary, index, true);
154}
155
156void BlockDirectory::removeBlock(MarkedBlock::Handle* block)
157{
158 ASSERT(block->directory() == this);
159 ASSERT(m_blocks[block->index()] == block);
160
161 subspace()->didRemoveBlock(block->index());
162
163 m_blocks[block->index()] = nullptr;
164 m_freeBlockIndices.append(block->index());
165
166 forEachBitVector(
167 holdLock(m_bitvectorLock),
168 [&] (FastBitVector& vector) {
169 vector[block->index()] = false;
170 });
171
172 block->didRemoveFromDirectory();
173}
174
175void BlockDirectory::stopAllocating()
176{
177 if (false)
178 dataLog(RawPointer(this), ": BlockDirectory::stopAllocating!\n");
179 m_localAllocators.forEach(
180 [&] (LocalAllocator* allocator) {
181 allocator->stopAllocating();
182 });
183}
184
185void BlockDirectory::prepareForAllocation()
186{
187 m_localAllocators.forEach(
188 [&] (LocalAllocator* allocator) {
189 allocator->prepareForAllocation();
190 });
191
192 m_unsweptCursor = 0;
193 m_emptyCursor = 0;
194
195 m_eden.clearAll();
196
197 if (UNLIKELY(Options::useImmortalObjects())) {
198 // FIXME: Make this work again.
199 // https://bugs.webkit.org/show_bug.cgi?id=162296
200 RELEASE_ASSERT_NOT_REACHED();
201 }
202}
203
204void BlockDirectory::stopAllocatingForGood()
205{
206 if (false)
207 dataLog(RawPointer(this), ": BlockDirectory::stopAllocatingForGood!\n");
208
209 m_localAllocators.forEach(
210 [&] (LocalAllocator* allocator) {
211 allocator->stopAllocatingForGood();
212 });
213
214 auto locker = holdLock(m_localAllocatorsLock);
215 while (!m_localAllocators.isEmpty())
216 m_localAllocators.begin()->remove();
217}
218
219void BlockDirectory::lastChanceToFinalize()
220{
221 forEachBlock(
222 [&] (MarkedBlock::Handle* block) {
223 block->lastChanceToFinalize();
224 });
225}
226
227void BlockDirectory::resumeAllocating()
228{
229 m_localAllocators.forEach(
230 [&] (LocalAllocator* allocator) {
231 allocator->resumeAllocating();
232 });
233}
234
235void BlockDirectory::beginMarkingForFullCollection()
236{
237 // Mark bits are sticky and so is our summary of mark bits. We only clear these during full
238 // collections, so if you survived the last collection you will survive the next one so long
239 // as the next one is eden.
240 m_markingNotEmpty.clearAll();
241 m_markingRetired.clearAll();
242}
243
244void BlockDirectory::endMarking()
245{
246 m_allocated.clearAll();
247
248 // It's surprising and frustrating to comprehend, but the end-of-marking flip does not need to
249 // know what kind of collection it is. That knowledge is already encoded in the m_markingXYZ
250 // vectors.
251
252 m_empty = m_live & ~m_markingNotEmpty;
253 m_canAllocateButNotEmpty = m_live & m_markingNotEmpty & ~m_markingRetired;
254
255 if (needsDestruction()) {
256 // There are some blocks that we didn't allocate out of in the last cycle, but we swept them. This
257 // will forget that we did that and we will end up sweeping them again and attempting to call their
258 // destructors again. That's fine because of zapping. The only time when we cannot forget is when
259 // we just allocate a block or when we move a block from one size class to another. That doesn't
260 // happen here.
261 m_destructible = m_live;
262 }
263
264 if (false) {
265 dataLog("Bits for ", m_cellSize, ", ", m_attributes, " after endMarking:\n");
266 dumpBits(WTF::dataFile());
267 }
268}
269
270void BlockDirectory::snapshotUnsweptForEdenCollection()
271{
272 m_unswept |= m_eden;
273}
274
275void BlockDirectory::snapshotUnsweptForFullCollection()
276{
277 m_unswept = m_live;
278}
279
280MarkedBlock::Handle* BlockDirectory::findBlockToSweep()
281{
282 m_unsweptCursor = m_unswept.findBit(m_unsweptCursor, true);
283 if (m_unsweptCursor >= m_blocks.size())
284 return nullptr;
285 return m_blocks[m_unsweptCursor];
286}
287
288void BlockDirectory::sweep()
289{
290 m_unswept.forEachSetBit(
291 [&] (size_t index) {
292 MarkedBlock::Handle* block = m_blocks[index];
293 block->sweep(nullptr);
294 });
295}
296
297void BlockDirectory::shrink()
298{
299 (m_empty & ~m_destructible).forEachSetBit(
300 [&] (size_t index) {
301 markedSpace().freeBlock(m_blocks[index]);
302 });
303}
304
305void BlockDirectory::assertNoUnswept()
306{
307 if (ASSERT_DISABLED)
308 return;
309
310 if (m_unswept.isEmpty())
311 return;
312
313 dataLog("Assertion failed: unswept not empty in ", *this, ".\n");
314 dumpBits();
315 ASSERT_NOT_REACHED();
316}
317
318RefPtr<SharedTask<MarkedBlock::Handle*()>> BlockDirectory::parallelNotEmptyBlockSource()
319{
320 class Task : public SharedTask<MarkedBlock::Handle*()> {
321 public:
322 Task(BlockDirectory& directory)
323 : m_directory(directory)
324 {
325 }
326
327 MarkedBlock::Handle* run() override
328 {
329 if (m_done)
330 return nullptr;
331 auto locker = holdLock(m_lock);
332 m_index = m_directory.m_markingNotEmpty.findBit(m_index, true);
333 if (m_index >= m_directory.m_blocks.size()) {
334 m_done = true;
335 return nullptr;
336 }
337 return m_directory.m_blocks[m_index++];
338 }
339
340 private:
341 BlockDirectory& m_directory;
342 size_t m_index { 0 };
343 Lock m_lock;
344 bool m_done { false };
345 };
346
347 return adoptRef(new Task(*this));
348}
349
350void BlockDirectory::dump(PrintStream& out) const
351{
352 out.print(RawPointer(this), ":", m_cellSize, "/", m_attributes);
353}
354
355void BlockDirectory::dumpBits(PrintStream& out)
356{
357 unsigned maxNameLength = 0;
358 forEachBitVectorWithName(
359 NoLockingNecessary,
360 [&] (FastBitVector&, const char* name) {
361 unsigned length = strlen(name);
362 maxNameLength = std::max(maxNameLength, length);
363 });
364
365 forEachBitVectorWithName(
366 NoLockingNecessary,
367 [&] (FastBitVector& vector, const char* name) {
368 out.print(" ", name, ": ");
369 for (unsigned i = maxNameLength - strlen(name); i--;)
370 out.print(" ");
371 out.print(vector, "\n");
372 });
373}
374
375MarkedSpace& BlockDirectory::markedSpace() const
376{
377 return m_subspace->space();
378}
379
380bool BlockDirectory::isFreeListedCell(const void* target)
381{
382 bool result = false;
383 m_localAllocators.forEach(
384 [&] (LocalAllocator* allocator) {
385 result |= allocator->isFreeListedCell(target);
386 });
387 return result;
388}
389
390} // namespace JSC
391
392